CMSC 412 S99

EXAM 1

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:

• Its has pcb queues runQ, readyQ, and ioWaitQ.

• It has macro UpdateRunQPCB(), function Scheduler(), and interrupt handlers Syscall(PROC_TERM), Syscall(IO, params), Trap(INVALID_OP), HwIntrpt(TIMER), and HwIntrpt(IO, params).

• It uses interrupt disabling to achieve atomic execution of OS handlers.

• Pcb has the structure

   { status,
     cpuState { gpr, sp, hi, lo, pc,
                ps { mode: (OS, USER),intrptEnabled: (ON, OFF), arithOverflow, etc }
              },
     ioParams
   }

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:

• Every pcb now has two additional integer fields:

  -

  pid             // id of the process

  -

  recBuff       // buffer for storing incoming message

• There are two new pcb queues:

  -

  sendQ       // processes blocked on send

  -

  recQ       // processes blocked on receive

• There are two new system calls:

  -

  interruptHandler Syscall( SEND, int dest, int msg )

  -

  interruptHandler Syscall( REC, int src )

Supply the body of each syscall such that

• The send syscall sends msg to the process with id dest
• The receive syscall receives a message from process with pid src and stores it in the local recBuff.
• Each syscall blocks until the other process is at the corresponding syscall.
• If the two processes are at the corresponding syscalls, then the communication eventually takes place.
• No more than 10 lines of pseudo-code for each body.

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.

a.

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

b.

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.