Queues: Difference between revisions
Yuron [PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+YnVyZWF1Y3JhdDxiciAvPmludGVyZmFjZS1hZG1pbjxiciAvPnN5c29wPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs) m (1 revision imported) |
W81054ch [PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+YnVyZWF1Y3JhdDxiciAvPmludGVyZmFjZS1hZG1pbjxiciAvPnN5c29wPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs) m (1 revision imported) |
||
(One intermediate revision by one other user not shown) | |||
Line 2: | Line 2: | ||
elsewhere). Includes a look at implementation techniques.}}<!-- | elsewhere). Includes a look at implementation techniques.}}<!-- | ||
-->{{#invoke:Dependencies|add|Concepts,3}} | -->{{#invoke:Dependencies|add|Concepts,3}} | ||
A queue is a linear list, <em>ordered</em> in some way. A simple queue may | A queue is a linear list, <em>ordered</em> 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. | ||
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 | Queues, in different forms, are used in many places in an operating system. Some different examples are given here. | ||
system. Some different examples are given here. | |||
---- | ---- | ||
=== Communications – FIFO === | === Communications – FIFO === | ||
A ‘[[Pipes|<strong>pipe</strong>]]’ (for example) provides a <em>buffer</em> | A ‘[[Pipes|<strong>pipe</strong>]]’ (for example) provides a <em>buffer</em> 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. | ||
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 | A queue of people gradually shuffles forwards, with everyone <strong>moving</strong> in an orderly manner … at least in theory. For items in computer memory this is <strong>not</strong> 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. <strong>Pointers</strong> are used to indicate these positions. | ||
<strong>moving</strong> in an orderly manner … at least in theory. For items in | |||
computer memory this is <strong>not</strong> 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. | |||
<strong>Pointers</strong> are used to indicate these positions. | |||
[[Image:buffer.png|link=|alt=Cyclic Buffer]] | [[Image:buffer.png|link=|alt=Cyclic Buffer]] | ||
Moving the queue indefinitely is not sustainable as the memory | Moving the queue indefinitely is not sustainable as the memory (address space) is not infinite. Instead, a <strong>cyclic</strong> buffer is used where the ‘head’ and ‘tail’ pointers chase each other around an allocated space. | ||
(address space) is not infinite. Instead, a <strong>cyclic</strong> 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 <code>read()</code> from it will block, until it is not. | *It is possible for the buffer to become empty, in which case a call to <code>read()</code> from it will block, until it is not. | ||
Line 40: | Line 23: | ||
[[Interprocess_Communication|interprocess communication]]. | [[Interprocess_Communication|interprocess communication]]. | ||
A [[Queues_Extra|more detailed description of FIFO operation]] is | A [[Queues_Extra|more detailed description of FIFO operation]] is available, complete with an interactive demonstration. | ||
available, complete with an interactive demonstration. | |||
---- | ---- | ||
=== I/O buffers === | === I/O buffers === | ||
Typically the same sort of FIFO as above, with two potential (slight) | Typically the same sort of FIFO as above, with two potential (slight) difference. | ||
difference. | |||
*One of the processes (reading or writing) may be hardware moderated, either as an [[Interrupts|interrupt]] service routine or a [[Direct Memory Access (DMA)|DMA]] operation. | *One of the processes (reading or writing) may be hardware moderated, either as an [[Interrupts|interrupt]] service routine or a [[Direct Memory Access (DMA)|DMA]] operation. | ||
Line 55: | Line 36: | ||
=== Ready queue === | === 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 | 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 '''[[Process Control Block (PCB)|PCB]]''') will be queued. A typical approach is to use a <strong>linked list</strong> which allows flexibility of order without altering many data in memory. | ||
we mean some form of process descriptor (e.g. the '''[[Process Control Block (PCB)|PCB]]''') will be queued. A typical approach is to use a <strong>linked list</strong> which allows flexibility of order without altering many data in memory. | |||
[[Image:ready_queue.png|link=|alt=Ready queue]] | [[Image:ready_queue.png|link=|alt=Ready queue]] | ||
In a ‘round-robin’ arrangement this queue may act as a | 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 | ||
strict FIFO: PCBs will only be added at the tail of the queue and are | |||
always removed by unlinking from the head. | always removed by unlinking from the head. | ||
Other schemes, such as applying [[Process_Priority|<strong>priorities</strong>]] | Other schemes, such as applying [[Process_Priority|<strong>priorities</strong>]] 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. | ||
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 | 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 <em>queue</em> is examined (and so on). | ||
have a list of queues where processes are scheduled ‘round | |||
robin’ from the highest priority queue unless it is empty, when | |||
the next <em>queue</em> is examined (and so on). | |||
[[Image:ready_queue_2.png|link=|alt=Multiple ready queues]] | [[Image:ready_queue_2.png|link=|alt=Multiple ready queues]] | ||
Line 79: | Line 51: | ||
=== Timer queue === | === Timer queue === | ||
An obvious not-a-FIFO queue would be a queue of ‘sleeping’ | An obvious not-a-FIFO queue would be a queue of ‘sleeping’ processes. Clearly an indeterminate number of processes can | ||
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 | ||
‘'''[[sleep]]'''’ (block until some future time) there | [[Peripheral devices|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. | ||
is likely to be a queue of processes all waiting on a timer | |||
[[Peripheral devices|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. | |||
[[Image:timer_queue.png|link=|alt=Timer queue]] | [[Image:timer_queue.png|link=|alt=Timer queue]] | ||
Line 92: | Line 59: | ||
=== Semaphore queue === | === Semaphore queue === | ||
In the (hopefully unlikely) event that multiple processes are blocked | In the (hopefully unlikely) event that multiple processes are blocked waiting for a [[Locks|lock]] it may be that [[Process_Priority|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. | ||
waiting for a [[Locks|lock]] it may be that [[Process_Priority|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. | |||
[[Image:mutex_queue.png|link=|alt=Mutex queue]] | [[Image:mutex_queue.png|link=|alt=Mutex queue]] | ||
In the figure, process #2 is running and about to be blocked at the | 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. | ||
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. | |||
---- | ---- | ||
{{PageGraph}} | {{PageGraph}} | ||
{{Category|Concepts}} | {{Category|Concepts}} | ||
{{Category|IO}} | {{Category|IO}} | ||
{{Category|Processes}} | {{Category|Processes}} |
Latest revision as of 10:03, 5 August 2019
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 (^D
in 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.