Operating System Design

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

empty.

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.