Homework 9 Solutions

22C:116, Spring 2002

Douglas W. Jones
  1. The Problem In the event that some critical variable is updated in both an interrupt service routine and in a regular routine, one of these two code fragments is prone to deadlock. Which of the above is deadlock prone, and how does it deadlock?
    Version 2 is deadlock prone when an interrupt occurs after the first wait on spin lock, and when the interrupt service routine also contains a critical section. The details of the deadlock are given below:
    		wait on spin lock
    			-- interrupt!!
    			-- interrupt service routine:
    			wait on spin lock   -- deadlock occurs!
    			disable interrupts  
    			.. critical section ..
    			enable interrupts
    			release spin lock
    		disable interrupts     -- prevent other activity on this CPU
    		.. critical section ..
    		enable interrupts      -- allow other activity on this CPU
    		release spin lock      -- allow other CPUs into critical section
    

  2. Part A: Outline the logic of the receive kernel call for this approach to implementing a DEMOS-like kernel.
    	receive( b, buffer, etc )
    	   	search incoming list of current
    		process for process trying to send to box b.
    
    		if sender found,
    			copy message etc from sender to receiver
    			unblock sender
    			return
    		else
    			record fact that receiver is waiting
    			block
    			return
    		endif
    

    Part B: Outline the logic of the send kernel call for this approach.

    	send( k, buffer, etc )
    		break link k into box b of process p
    
    		if process b blocked awaiting message in box b
    			copy message etc from sender to receiver
    			unblock receiver
    			return
    		else
    			record details of message being sent
    			enqueue current in incoming list of process p
    			block
    			return
    		eneif
    

    Part C: In light of the above, what is the data structure of one process, at the level of detail presented in lecture 30 (only go into detail for those parts that are different from the notes for lecture 30).

    	each process must include:
    		state (not blocked, blocked receiving, blocked sending)
    		box    -- box number trying to send to or receive from
    		buffer -- address of message being sent or received
    		length -- length of message being sent or received
    		linkq  -- index of first link being sent or received
    		linkr  -- index of second link being sent or received
    

  3. Problems from the text:
    Do problem 22 on page 580.
    When a remote procedure executes a system call, it naturally operates on the system of the local machine and not the system of the remote machine. Therefore, the consequence of calling procedure p that executes, say, open(file) will be quite different if p is on the same machine as the caller or if p is on a remote machine, assuming the machines run some system like UNIX or Windows.

    What we need is an operating system environment where the handles on system objects returned by system calls have universal meaning across the distributed system. Instead of returning an integer that has meaning only in one process on one machine, for example, open should return some kind of universal file handle. We can create a middleware layer to do this, but it would be nicer if the underlying system did it. Demos links solve this problem, for example.


    Do problem 25 on page 580.
    We need to arrange message delivery for messages that were addressed to the process at its old location, and we need to guarantee the validity of all handles the process may have held for system resources on the machine where it originally ran.