1 [6 pts]. Solution

 interruptHandler HwIntrpt( IO ) {
   UpdateRunQPCB() ; 
   move runQ.pcb to readyQ ;
   move ioWaitQ.head.PCB to head of readyQ ;
   if ioWaitQ is not empty
     then ioDevice.controlReg := ioWaitQ.head.pcb.ioParams ;
   Scheduler() ;
 }

Alternatively,

 interruptHandler HwIntrpt( IO ) {
   UpdateRunQPCB() ;
   move runQ.pcb to readyQ ;
   move ioWaitQ.head.PCB to runQ ;
   if ioWaitQ is not empty
     then ioDevice.controlReg := ioWaitQ.head.pcb.ioParams ;
   Dispatch() ;
 }

2 [12 pts]. Solution

interruptHandler Syscall( SEND, int dest, int msg ) {
     UpdateRunQPCB() ;                                   // 1 point
     if ( recQ has a pcb, say x, with x.pid=dest         // 1 point
                         and x.src=runQ.pcb.pid )        // 1 point
        then { x.recBuff := msg ;                        // 1 point
               move x from recQ to readyQ ;              // 1 point
             }
        else { move runQ pcb to sendQ ;                  // 1 point
               Scheduler() ;
             }

interruptHandler Syscall( REC, int src ) {
     UpdateRunQPCB() ;                                   // 1 point
     if ( sendQ has a pcb, say x, with x.pid=src         // 1 point
                         and x.dest=runQ.pcb.pid )       // 1 point
        then { runQ.pcb.recBuff := x.msg ;               // 1 point
               move x from sendQ to readyQ ;             // 1 point
             }
        else { move runQ pcb to recQ ;                   // 1 point
               Scheduler() ;
             }

For a queued pcb x, the parameters of its system call (i.e., dest, msg, src) can be accessed via x.sp [because the parameters would be at or near the top of x's stack, depending on the compiler's calling convention]. Alternatively, one can add additional fields (e.g., sendBuff, src, dest) to the pcb and have the system call store the parameters there in the event of the process being blocked (i.e., taking the "else" branch).

In the above system calls, if the running process does block then it continues to be running. An alternative design for the system call is that if the running process does not block then it becomes ready (rather than stay running) and the scheduler is called in any case. The send syscall would become

interruptHandler Syscall( SEND, int dest, int msg ) {
     UpdateRunQPCB() ;                                   // 1 point
     if ( recQ has a pcb, say x, with x.pid=dest         // 1 point
                         and x.src=runQ.pcb.pid )        // 1 point
        then { x.recBuff := msg ;                        // 1 point
               move x from recQ to readyQ ;              // 1 point
               move runQ pcb to readyQ ;
             }
        else { move runQ pcb to sendQ ;                  / 1 point
             };
     Scheduler() ;

GRADING: Roughly 1 point per line of code, as indicated above.

COMMON MISTAKES:

• Doing UpdateRunQPCB too late. [If it is used it must appear at the start of the interrupt handler, otherwise it saves the wrong state in the runQ pcb.]
• Answers that were completely out of context of the Toy OS got roughly 5 points total. Examples are: using semaphores (not provided in the Toy OS), using busy waiting (hangs the system since Toy OS interrupt handlers run in interrupt disabled mode), etc.

3 [12 pts]. Solution

Safety property holds.

Proof

Let Z0 denote "(P0 at A2 with x0=FALSE) or (P0 at CS) or (P0 in CS) or (P0 at A5)". Define Z1 symetrically (i.e., Z0 with P0, x0, Ai, replaced by P1, x1, Bi). It suffices to show that at any time Z0 and Z1 cannot both be true.

Consider the first time t1 that Z0 and Z1 both are both true.

Suppose at t1, Z0 becomes true and Z1 was already true. Then at t1, csFree was TRUE, P0 executed A3, and csFree became FALSE. And at some time t2 (< t1), csFree was TRUE, P1 executed B3, and csFree became FALSE. Thus csFree became TRUE between t2 and t1. Thus P0 executed A5 between t2 and t1 (P1 could not have executed B5 since Z1 holds between t2 and t1). But then Z0 and Z1 held at time t2, contradicting the assumption that t1 was the first such time.

The symetric argument holds if at t1, Z1 becomes true and Z0 was already true.

COMMON MISTAKES:

• A common mistake is to show that if P0 enters CS at time t1, then P1 cannot enter CS until P0 leaves CS. This does not account for the case where P1 may already be in CS at t1.
• To treat "P0 enters CS" to be the same as the execution of A3 with csFree=TRUE, whereas the former is actually the execution of A2 with x0=FALSE. Similarly with P1.

Part b [6 points].

Progress does not hold.

Counter-example execution (each entry signifies execution of the statement):

A1, A2, A3, A4, B1, B2, B3, B2, A5, A1, A2, A3, A4, B1, B2, B3, B2, ...