CMSC 412 S99


March 11, 1999

Total points 30. Total time 75 mins. 3 problems over 3 pages. No book, no notes, no calculator.

Unless otherwise mentioned, assume read-write atomicity and weak fairness scheduling.

Program elegance counts. You lose points for long/inelegant code.

For your convenience, we recall some features of the Toy OS with Synchronous IO:
1. [6 pts]  In the Toy OS with Synchrous IO, recall that when a process' io request is completed, the OS makes that process ready. That is,
 interruptHandler HwIntrpt( IO ) {
  /* Control here after io device interrupts. The pcb of the interrupted process is in runQ.
     The interrupt signals completion of the io request of the pcb process at head of ioWaitQ.
   move ioWaitQ.head.PCB to readyQ ;
   if ioWaitQ is not empty
     then ioDevice.controlReg := ioWaitQ.head.pcb.ioParams ;
   Return_from_Interrupt ;

Modify the io device interrupt handler so that the process whose io has just completed is made to run immediately. Your new HwIntrpt(IO) body must be no more than 9 lines of pseudo-code.

2. [12 pts]  You are to add a message-passing service to the Toy OS with Synchronous IO. Messages are integers, and communication involves no intermediate message buffers. Specifically:

Supply the body of each syscall such that

3. [12 pts]  Here is an attempted solution to the 2-process mutual exclusion problem. Processes P0 and P1 share three boolean variables, csFree, x0, and x1, all initially true. In addition to the usual atomicity assumption of the mutual exclusion problem, assume that each of the if-statements A3 and B3 is executed atomically.

P0 executes

   do forever {
  A1:  NCS;
  A2:  while x0 do {
  A3:    if csFree then
          { csFree := FALSE; x0 := FALSE };
  A4:  CS;
  A5:  csFree := TRUE; x0 := TRUE ;
P1 executes
   do forever {
  B1:  NCS;
  B2:  while x1 do {
  B3:    if csFree then
          { csFree := FALSE; x1 := FALSE };
  B4:  CS;
  B5:  csFree := TRUE; x1 := TRUE ;

For each of the following properties, say whether or not the algorithm satisfies the property. If your answer is yes, give a proof that covers all possible executions. If your answer is no, give a counter-example execution.

Safety property: At most one process is in its CS.

Progress property: For each process, if the process is hungry then it eventually eats provided that no process stays eating forever and everything other than NCS is executed with weak fairness.

A. Udaya Shankar
Sun Mar 14 17:21:03 EST 1999