Queues
| Depends on | Concepts |
|---|
A queue is a linear list, ordered in some way. A simple queue may preserve the order in which items arrive: a FIFO (First-In, First-Out). Other queues may be sorted such that arriving items may be inserted at other points. The different approaches may be reflected in different implementation techniques.
Queues, in different forms, are used in many places in an operating system. Some different examples are given here.
Communications – FIFO
A ‘pipe’ (for example) provides a buffer between two processes. This handles queuing of data on a FIFO (First-In, First-Out) basis, i.e. the order of the data (such as bytes) is preserved.
A queue of people gradually shuffles forwards, with everyone moving in an orderly manner … at least in theory. For items in computer memory this is not an efficient approach; moving items in memory involves a lot of work. Instead, the usual technique is to move the ‘world’ around the queue by redefining the position of the head and tail, leaving the data stationary. Pointers are used to indicate these positions.
Moving the queue indefinitely is not sustainable as the memory (address space) is not infinite. Instead, a cyclic buffer is used where the ‘head’ and ‘tail’ pointers chase each other around an allocated space.
- It is possible for the buffer to become empty, in which case a call to
read()from it will block, until it is not. - It is possible for the buffer to become full, in which case a call to
write()to it will block, until it is not.
These calls are typically in different processes, facilitating interprocess communication.
A more detailed description of FIFO operation is available, complete with an interactive demonstration.
I/O buffers
Typically the same sort of FIFO as above, with two potential (slight) difference.
- One of the processes (reading or writing) may be hardware moderated, either as an interrupt service routine or a DMA operation.
- For some devices a process (reading or writing) may be done in blocks rather than (say) characters.
- Example: if typing ‘directly’ into a file (e.g. Unix
cat > my_file) characters will be buffered one by one but a write will not be attempted until a whole block is filled or the operation is complete (^Din the above example).
Reading may be handled similarly …
- Example: if typing ‘directly’ into a file (e.g. Unix
Ready queue
In a multitasking system it is likely that several processes may be ‘ready’ at the same time. (“Several”, in this case, is an indeterminate number.) These ‘processes’ will be ‘stored’ in a queue (sometimes several queues); by this we mean some form of process descriptor (e.g. the PCB) will be queued. A typical approach is to use a linked list which allows flexibility of order without altering many data in memory.
In a ‘round-robin’ arrangement this queue may act as a strict FIFO: PCBs will only be added at the tail of the queue and are always removed by unlinking from the head.
Other schemes, such as applying priorities might order the queue differently, e.g. by inserting entries at a deliberate point, with the queue sorted into priority order. This would still leave the next process at the head of the queue, which avoids searching.
Other schemes are a bit more elaborate; for example it is possible to have a list of queues where processes are scheduled ‘round robin’ from the highest priority queue unless it is empty, when the next queue is examined (and so on).
Timer queue
An obvious not-a-FIFO queue would be a queue of ‘sleeping’ processes. Clearly an indeterminate number of processes can ‘sleep’ (block until some future time) there is likely to be a queue of processes all waiting on a timer peripheral device. This queue can conveniently be in chronological order, so processes put to sleep are sorted into the appropriate place (easy enough to insert into a linked list) and removed from the head.
Semaphore queue
In the (hopefully unlikely) event that multiple processes are blocked waiting for a lock it may be that process priority is used when inserting into the queue, so that the highest priority waiting process will be the one freed when the lock is freed.
In the figure, process #2 is running and about to be blocked at the lock. The dashed lines show where it will be inserted – behind #1 but ahead of #4 – if the priorities are taken into account when queuing. In this example, process #3 must have arrived at the lock first and must exit the critical section before any other process can begin it.
