Assignment 10 Solutions

Part of the homework for 22C:112, Spring 2012
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Background: The Unix wait() kernel call waits for a child of the current process to terminate (or any of a number of other signals). Focus here just on the child termination event and ignore all of the other ones. The Unix exit() kernel call terminates the current process and also wakes up the parent process. Note that exit transmits some data about the child to the parent, so that the parent, on calling wait, learns the exit status and identity of one child process.
This implies some kind of kernel data structure to relate parents to children. If the synchronization relationship between parents and children is implemented by semaphores, this implies that there must be some semaphores embedded in this data structure.
The minimum description of a thread or process includes storage to hold the registers of that thread or process, and it is queueable so that the thread or process may wait on the ready list or on the waiting list of any semaphore.
A problem: What data structure (including semaphores, pointers and other components) must you add to the minimum data structure described above in order to implement the semantics of wait() and exit()? Keep your answer short, clear, complete and concise. (1 point)

Each child process needs a pointer to its parent's process description. The parent needs a semaphore on which it can wait for notice of termination by any child (or for notice of any other asynchronous event). There also should be a queue of exit status records so that the parent, on waiting for a termination notice from a chile can receive the termination notices.
Background: Consider the question of queueing discipline in the ready list. Introductory discussions of scheduling always begin with the ready list implemented as a simple FIFO queue. This leads to what is frequently called "round robin" scheduling of ready processes -- each process has, over time, an equal shot at being executed by a CPU. An alterative is to use a priority queue, creating priority scheduling, so that higher priority processes (usually those with a lower numeric priority) have greater access to the CPU than low priority processes. In the abstract, the rule on such a system is that the current running process never have a lower priority than any ready process. When this rule is violated, we say that we have a priority inversion.
The semaphore implementation given in class included a signal operation something like the following:
```
void signal( semaphore s ) {
    disable_interrupts();
    if (empty(s.queue) {
        s.count ++;
    } else {
        enqueue( readylist, dequeue( s.queue ));
    }
    enable_interrupts();
}
```
In class, we also discussed other primitives that are supported by the scheduler, including a wait operation, process creation, destruction, and a relinquish operation that allows one process to become ready and allow another process to run.
a) When priority scheduling is used, the above code can lead to a priority inversion. Explain, concisely, the specific circumstances when this can occur -- identify the processes involved in terms of their relationship to the signal operation, and how this can lead to an inversion. (0.5 points)

If a high priority process is waiting on a semaphore and a low priority process signals it, the high priority process is put on the ready list while the low priority process continues running. This is an inversion.
The most common problem with this question was a failure to read the definition of an inversion. A running process has lower priority than a ready process. Most of the wrong answers involved waiting processes with higher priority than running processes. These do not conform to the definition given.

b) Suggest a trivial change to the above code that eliminates the priority inversion. (Hint: Insert a call to another scheduler primitive in the right place in the above code and the inversion will be eliminated.) (0.5 points)

After any process signals, it should immediately relinquish in order to guarantee that the highest priority ready process is permitted to run.
Background: A deaadlock occurs when all processes in a set of processes are blocked waiting on events that only other processes in that set can signal. For example, process A is waiting for an event that only process B can signal, while process B is waiting for an event that only process A can signal. Deadlocks within an operating system are a classical mode of system failure. A total deadlock occurs when all of the processes in a system are blocked, while a partial deadlock involves only a subset of the processes.
For this problem, consider a scheduler that supports semaphores, with the wait and signal operations, along with primitives for process creation, and destruction, a reliquish operation and preemptive scheduling. Code can be added to one of these scheduler primitives to detect some (but not necessarily all) deadlocks.
a) What condition would you check in which scheduler operation to detect some deadlocks? (Refer to the code or pseudocode for the operations to work this out!) (0.5 points)

If a process waits when the ready list is empty, there must be a deadlock, since there will be no process that can possibly signal.
Wrong answers frequently tried to ask "is some process waiting for this process" when a process waits. Unfortunately, semaphores with the operations wait and signal do not record any data that would allow answering this question, so this is clearly a wrong answer.

b) What class of deadlocks can this detect, and what class of deadlocks does it fail to detect? (0.5 points)

It detect total deadlocks that involve all of the processes in the system. If just two processes deadlock, so each is waiting for the other while the remaining processes are still running, the deadlock will go undetected.