594 Operating System Design
after a timeout. PR_CURR means that the process is (the only one) currently running.
The currently running process is not on the ready list. PR_RECV means the process is
blocked waiting to receive a message; PR_RECTIM is like PR_RECV except the pro-
cess is also sleeping for a specified time and will awaken if the timer expires or a mes-
sage arrives, whichever happens first.
Counting semaphores. Semaphores reside in the array semtab. Each entry in the array
corresponds to a semaphore and has a count (scount) and state (sstate). The state is
S_FREE if the semaphore slot is unassigned, and S_USED if the semaphore is in use.
If the count is negative P then the head and tail fields of the entry in the semaphore
table point to the head and tail of a FIFO queue of P processes waiting for the sema-
phore. If the count is nonnegative P then no processes are waiting and the queue is
Blocked processes. A process that is blocked for any reason is not eligible to use the
CPU. Any action that blocks the current processes forces it to relinquish the CPU and
allow another process to execute. A process that is blocked on a semaphore is on the
queue for the semaphore, and a process blocked for a timed delay is on the queue of
sleeping processes. Other blocked processes are not on a queue. Function ready moves
a blocked process to the ready list and makes the process eligible to use the CPU.
Sleeping processes. A process calls sleep to delay for a specified time. The process is
added to a delta list of sleeping processes. A process may only put itself to sleep.
Process queues and ordered lists. There is a single data structure used for all process
lists. The structure contains entries for the head and tail of each list as well as an entry
for each process. The first NPROC entries in the table (0 to NPROC-1) correspond to
the NPROC processes in the system; successive entries in the table are allocated in
pairs, where each pair forms the head and tail of a list.
The advantage of keeping all heads and tails in the same data structure is that enqueu-
ing, dequeuing, testing for empty/nonempty, and removing from the middle (e.g., when
a process is killed) are all handled by a small set of functions (files queue.c and
queue.h). An empty queue has the head and tail pointing to each other. Testing wheth-
er a list is empty is trivial. Lists can be ordered or may be FIFO; each entry has a key
that is ignored if the list is FIFO.
Null process. Process 0 is a null process that is always available to run or is running.
Care must be taken so that process 0 never executes code that could cause it to block
(e.g., it cannot wait for a semaphore). Because the null process may be running during
interrupts, interrupt code may never wait for a semaphore. When the system starts, the
initialization code creates a process to execute main and then becomes the null process
(i.e., executes an infinite loop). Because its priority is lower than that of any other pro-
cess, the null process loop executes only when no other process is ready.