There are many times when a process must wait for a system resource.
For example a process may need the VFS inode describing a directory in the file system
and that inode may not be in the buffer cache.
In this case the process must wait for that inode to be fetched from the physical
media containing the file system before it can carry on.
Figure: Wait Queue
The Linux kernel uses a simple data structure, a wait queue (see the figure above),
which consists of a pointer to the processes task_struct and a pointer to the
next element in the wait queue.
When processes are added to the end of a wait queue they can either be interruptible or
Interruptible processes may be interrupted by events such as timers expiring or
signals being delivered whilst they are waiting on a wait queue.
The waiting process' state will reflect this and either be INTERRUPTIBLE or
As this process can not now continue to run, the scheduler is run and, when it selects
a new process to run, the waiting process will be suspended.
When the wait queue is processed, the state of every process in the wait queue is set to
If the process has been removed from the run queue, it is put back onto the run queue.
The next time the scheduler runs, the processes that are on the wait queue are now candidates
to be run as they are now no longer waiting.
When a process on the wait queue is scheduled, the first thing that it will do is remove
itself from the wait queue.
Wait queues can be used to synchronize access to system resources and they are used by Linux in
its implementation of semaphores (see here).