Homework 1

CS42

50 pts., due Sept. 13

1. 2.1, 2.6--2.8.

2. Recall that the operating system is called into play during any one of the following events:
   • Hardware interrupts
   • Software trap
   • System call
   Anytime the operating system runs, the possibility of the current process losing control of the processor exists. Thus, typically, a process cannot guarantee that a particular code block which accesses shared variables (a so-called critical section) can execute atomically (i.e., without interruption).

   However, if the processor provides a kernel-mode disable interrupts instruction, then it is possible to atomically execute a critical section. Assume that this instruction disables all hardware interrupts and that it is available only in kernel mode.

   State a set of conditions which, if met, would guarantee the atomic execution of a critical section. Why is this a poor method of achieving atomicity for very, very long critical sections? Why should the disable interrupts instruction be privileged?

3. There are several disadvantages to the device I/O scheme using multiple buffers and interrupts discussed in class. For example, the user is required to release buffers strictly in the order in which they were acquired. Also, a collection of buffers has to be dedicated to either input or output, i.e., there is no way to use buffers to accomplish both tasks. This could lead to a situation where there are unused buffers in the system, but it is impossible to do input since all unused buffers are dedicated to hold output data.

   One solution to these problems is to maintain a buffer pool which can be used for both input and output. With this scheme, each buffer is in one of three states at any time:

   1. INFULL --- input buffer full and available to be returned to the user on request.

   2. OUTFULL --- output buffer full and waiting to be output to the I/O device when ready.

   3. EMPTY --- empty buffer available for either input or output.

   There are four system calls that are invoked by the user to accomplish I/O:

   1. Gbufin() --- returns a pointer to the beginning of the next full input buffer.

   2. Rbufin(bufptr) --- places the buffer pointed to by bufptr back into the empty buffer pool (Hint: convert the pointer to an index.).

   3. Gbufout --- returns a pointer to the beginning of an empty buffer into which the user places data to be output.

   4. Rbufout(bufptr) --- places the full output buffer pointed to by bufptr onto the output queue.

   In addition, there are two interrupt handlers, one for input and one for output:

   1. IHinput --- called when an input operation has been completed.

   2. IHoutput --- called when an output operation has been completed.

   The diagram below illustrates how a buffer can move between these different states, and the role of the system software described above.

   Write the pseudo-code for the four system routines and the two interrupt handlers. You may assume that there are no critical section problems, i.e., it is as if each of the routines executes with interrupts disabled. You may assume that high-level data structures such as lists and the appropriate manipulation routines exist, if you wish, but be sure to indicate precisely what you are assuming.