HW3
Assigned   9/15/2005
First possible pop quiz   9/22/05
Last possible pop quiz    9/29/05



1.  Scheduling

Suppose that the following processes arrive for execution at the times
indicated.Each process will run with a single burst of CPU activity (i.e., no
I/O) which lasts for the listed amount of time.

process arrival time CPU burst time priority
------- ------------ -------------- --------
p1	10ms	     18ms	    2
p2 	1ms	     12ms	    1
p3 	20ms	     16ms	    3
p4 	31ms	     14ms	    4

What is the job throughput, average waiting time and average turnaround time
with 
  a). non-preemptive, FCFS scheduling?
  b). preemptive RR (quantum = 10ms) scheduling?
  c). preemptive priority scheduling




2. 
  a) Give two important reasons why we can't simply disable interrupts to
   achieve mutual exclusion
  b) Discuss the tradeoff between fairness and throughput of operations in the
  readers-writers problem. Propose a method for solving the readerswriters
  problem without causing starvation  
  



3.  Dining philosophers problem

  a) Solve the dining philosophers problem using semaphores instead of monitor 
  b) The textbook's solution to the dining philosophers (Figure 6.19) problem is
not starvation free. Explain why. 




4.  Sleeping-Barber Problem (p233, question 6.11 in the textbook,)

Consider the Sleeping-Barber Problem with the modification that there are k
barbers and k barber chairs in the barber room, instead of just one. Write a
program to coordinate the barbers and the customers. You can use either
semaphores or monitors. 



5.  Monkey crossing problem

Some monkeys are trying to cross a ravine. A single rope traverses the ravine,
and monkeys can cross hand-over-hand. Up to five monkeys can be hanging on the
rope at any one time. if there are more than five, then the rope will break
and they will all die. Also, if eastward-moving monkeys encounter westward
moving monkeys, all will fall off and die.  

Each monkey operates in a separate thread, which executes the code below:

typedef enum { EAST, WEST} Destination ;

void monkey(int id, Destination dest) {
	WaitUntilSafeToCross(dest);
	CrossRavine(id, dest);
	DoneWithCrossing(dest);
}

Variable id holds a unique number identifying that monkey. CrossRavine(int
monkeyid, Destination d) is a synchronous call provided to you, and it returns
when the calling monkey has safely reached its destination. 

Use semaphores to implement WaitUntilSafeToCross(Destination d) and
DoneWithCrossing(Destination d). Your implementation should ensure that: 
  a) At most 5 monkeys simultaneously execute CrossRavine().
  b) All monkeys executing in CrossRavine() are heading in the same direction.
  c) WaitUntilSafeToCross() does not delay a monkey unnecessarily. (Explain
  your definition of "unnecessarily")