Assignment 11, due Nov. 15

Solutions

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

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

Background: The classical states of a process (from the perspective of a process manager) are ready, running, waiting and dead. What process state changes are associated with each of the following? You must give both the former state and the new states for each process that changes state in each case, and identify the processes as much as possible. (In some cases, you may need to say: "some other process," or say that it changes from or to "either state a or b"). (0.2 points each)
a) A program calls read() and the requested data is not yet available.

The calling process state changes from running to waiting.
Some waiting process changes from waiting to running.

b) The disk interrupt handler signals a process that its write() has completed.

The signalled process changes state from waiting to ready (or running).
(If if the signalled process changed to running, some other process changed from running to ready.) Parenthetic parts of this answer are not mandatory.

c) A user types control c for a process that has no handler installed for the SIGINT signal.

The user's process changes from either running or ready to dead.
If the user's process was running, some other process changes from ready to running.

d) A program calls exit().

The user's process changes from running to dead.
Some other process changes from ready to running.

e) A program calls setpriority() to lower its priority below that of some ready process.

The calling process changes from running to ready.
The highest priority ready process changes state to running.
Background: In the discussion of I/O earlier in the semester, we wrote code like this, in the interrupt-driven FIFO-queue based input/output driver:
```
	while (inq.empty()) do /* polling loop */;
        return inq.dequeue();
```
A Problem: How should we change this now that we have multiple user processes and a scheduler? (0.5 points)
The polling loop is a very bad idea, but it can be made better with this variation (if the scheduler does not have a relinquish() service, there might be alternatives such as sleep():
```
	while (inq.empty()) do relinquish()/* polling loop */;
        return inq.dequeue();
```
The above answer is a poor one. The way it ought to be done involves semaphores:
```
	wait( inq.data );
        return inq.dequeue();
```
Note that problem 1 part a) was included in this assignment specifically as a hint to prime people to guess that the best solutions would involve interaction with the scheduler's waiting state.
Background: Consider the code for the wait() and signal() operations on semaphores. The lecture notes for Nov. 13 include example code to implement semaphores. This code makes good sense under a round-robin scheduler, but it is incorrect under a priority scheduler because it can lead to priority inversions, where the current running process can end up having a lower priority than some ready process. Identify the point in the code where this inversion could begin. (0.5 points)

The code given for the signal() operation always returns to the calling process, even if it moves a higher priority process from the waiting queue to the ready list.
Background: Consider the problem of writing drivers for sequential input and output devices. FIFO queues play an important role. For a FIFO queue connecting two processes at the user level, each enqueue involves a wait() for free space and a signal() that data is available, and each dequeue involves a wait() for data and a signal() that free space has been created.
When one end of the queue is in a user process and the other end of the queue is in an interrupt service routine, things are more complex.
a) When a user process needs to signal an interrupt service routine that a resource it might need is available, can it use a semaphore? Explain any constraints. (0.5 points)

No. Interrupt service routines do not run under the authority of the scheduler, they are "scheduled" by the interrupt hardware. Whan an interrupt service routine wants to wait, about the best thing it can do is disable its interrupt, waiting for some user code to re-enable that interrupt.

b) When an interrupt service rutine needs to signal a use process that a resource it might need is available, can it use a semaphore? Explain any constraints. (0.5 points)

Yes, but since it typically runs with interrupts disabled, it cannot use disable-interrupts and enable-interrupts to guard critical sections in the signal() routine. Instead, it must use a special version of signal() written under the assumption that it will only be called from within interrupt service routines.