Homework 1

CS42

Solution

1. (24 pts.) 2.1, 2.6--2.8.
   1. 2.1

      Buffering will work so long as the job's computation does not consume data faster than it can be read or produce it faster than it can be written. If this is not the case, then computation will be stalled waiting for the I/O to catch up. Because of the speed differences between CPUs and I/O subsystems, this could be a frequent occurrence, especially on input. If there are enough output buffers, output won't stall cause the computation to stall.

      Spooling, on the other hand, seeks to overlap the computation and I/O of independent jobs. The dependencies which exist between the phases of one job in the buffering scheme aren't present when spooling is used. There are fewer opportunities for computation to stall. Of course, there must be sufficient memory to hold all the input data and to buffer the output data, and also enough jobs to run.

   2. 2.6
      1. Set value of timer --- This should be privileged Otherwise, there is no way of enforcing quantums and the realtime clock may be wrong.

      2. Read the clock --- This doesn't need to be privileged.

      3. Clear memory --- This should be privileged. Otherwise, a user could crash the system at will.

      4. Turn off interrupts --- This should be privileged. Otherwise, a user could gain complete control of the CPU by disabling interrupts and sitting in a tight no-op loop.

      5. Switch from user to monitor mode --- This should be privileged. Otherwise, a user could gain complete control of the system by simply entering monitor mode.

   3. 2.7

      It is possible: All one has to do is implement a virtual machine with the appropriate protection mechanisms. Any user program runs within the virtual machine (which is really a simulator) and cannot directly access the hardware).

      It isn't possible: If the system has no inherent protection, all one has to do is subvert the software-supplied protection system. To use the IBM PC as an example, we could just reset the system and boot our own, non-protected version of the OS from the floppy drive.

   4. 2.8
      1. The OS will need to keep some data structures, which it must be able to update. Obviously, these data structures can't be stored in the read-only area and can, therefore, be modified directly by user processes.

      2. One user job can scribble over another user job.

2. (8 pts.) 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?

   Here's the set of conditions:

   • The critical section code must execute with interrupts disabled. This implies that it executes in kernel mode, because the disable interrupts instruction is a privileged instruction.

   • The critical section code must contain no instructions which would result in an instruction trap. This pertains to obvious cases, such as divide by zero and illegal instruction, as well as cases such as a page fault.

   • Finally, the critical section code may make no system calls.

   This is a poor method for achieving atomicity for long critical sections because interrupts are disabled (ignored) for a long time. It is never a good idea to ignore interrupts for long.

   The disable interrupts instruction should be privileged because if it were available to user-mode processes, they could cause the system to hang by disabling interrupts and entering an infinite no-op loop.

3. (18 pts.) 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.

   In this problem, the buffer pool is maintained as a set of three queues --- emptyqu, inputqu, outputqu.

   The four system calls and the interrupt handlers use the buffers available in these queues for their computation. In addition, the two channels, INCH and OUTCH use temporary buffers for storing the data being read in or written out. inptr and outptr are pointers to buffers in the buffer pool which are being currently read by INCH or written by OUTCH.

   Gbufin() {
     return(remqu(inputqu));
   }
   

   Rbufin(bufptr) {
     if (!input_busy){           /* INCH had to wait for an empty buffer */
        inptr = bufptr;          /* now, there's an empty buffer         */
        startread(INCH,inptr);
        input_busy = TRUE;
     }
     else
        insqu(emptyqu,bufptr);
   }
   
   Gbufout() {
     return(remqu(emptyqu));
   }
   
   Rbufout(bufptr) {
     if (!output_busy) {         /* OUTCH had no buffers to write */
       outptr = bufptr;          /* now, it does                  */
       startwrite(OUTCH,outptr);
       output_busy = TRUE;
     }
     else
       insqu(outputqu,bufptr);
   }
   

   The interrupt handlers :

   IHinput(){
     insqu(inputqu,inptr);
     inptr = remqu(emptyqu);
     if (inptr != NULL)
       startread(INCH,inptr)
     else
       input_busy = FALSE;    /* couldn't get a buffer */
   }
   

   IHoutput(){
     if (!input_busy) {       /* INCH had to wait for an empty buffer */
       inptr = outptr;        /* now, there's an empty buffer         */
       startread(INCH,inptr);
       input_busy = TRUE;
     }
     else
       insqu(emptyqu,outptr);
   
     outptr = remqu(outqu);
     if (outptr != NULL)
       startwrite(OUTCH,outptr);
     else
       output_busy = FALSE;   /* no output buffers, OUTCH is idle */
   }
   

   Initialization :

   init() {
     input_busy = TRUE;
     output_busy = FALSE;
     inputqu = outputqu = NULL;
     for (i=0;i<MAXBUF;i++)
       /* Insert the buffer node in the emptyqu */
     inptr = remqu(emptyqu);
     startread(INCH,inptr);
   }
   

   insqu(queue,nodeptr) : this function inserts the node pointed to by nodeptr at the end of the queue whose head pointer is queue.
   remqu(queue) : this function returns the first node of the queue queue, returning NULL if the queue is empty.