Homework 2

CS 502

Due:  March 16

1. The U.S. Senate has finally agreed on a protocol for hearing the testimony of witnesses. First, no more than one witness may be in the senate at any time. Second, in order to ensure that there is no witness tampering going on, a witness can not be in the senate unless there is at least one democrat senator and one republican senator present (the senate has not been able to figure out a way to limit the movements of independent senators).
   
   Write a monitor that models this protocol. There should be six entry procedures: EnterDem, LeaveDem, EnterRep, LeaveRep, EnterWitness, and LeaveWitness. State the monitor invariant (the conditions given above) as a predicate using the symbols nd, nr, and nw for the number of democrat senators, republican senators, and witnesses in the senate.
   
   (Hint. Three condition variables, wCanEnter, rCanLeave, and dCanLeave, are sufficient to write this monitor.)
   
2. A problem on binary and general semaphores.

   a.   Give an implementation of binary semaphores using general semaphores.
   
   Hint. Some of you may be tempted to write code like

   ...
   signal(s);
   if (s > 1) s = 1;
   ...

   but this would be incorrect.  The only operations allowed on semaphores (outside of initialization) are signal and wait.

   b.  Consider the following implementation of general semaphore s using binary semaphores.

   gensem s = initval is replaced with

   struct s {
       int count = 0;
       int s = initval;
       binsem mutex = 1;	
       binsem block = 0;
   }

   wait(s) is replaced with

   wait(s.mutex);
   if (s.s == 0) {
       s.count++;
       signal(s.mutex);
       wait(s.block);
   } else {
       s.s--;
       signal(s.mutex);
   }

   signal(s) is replaced with

   wait(s.mutex);
   if (s.count == 0) {
       s.s++;
       signal(s.mutex);
   } else {
       s.count--;
       signal(s.block);
       signal(s.mutex);
   }

   This implementation suffers from a liveness problem (that is, there is a sequence of events that could leave a process waiting forever). Trace an execution which ends with s>0, count=0, and a process waiting on the semaphore block.

3. Suppose that a system is in an unsafe state. Show that it is possible for the processes to complete their execution without entering a deadlock state.
   
4. Consider the following snapshot of a system:

Available
A	B	C	D
1	5	2	0

 

	Max				Allocation
	A	B	C	D	A	B	C	D
P0	0	0	1	2	0	0	1	2
P1	1	7	5	0	1	0	0	0
P2	2	3	5	6	1	3	5	4
P3	0	6	5	2	0	6	3	2
P4	0	6	5	6	0	0	1	4

Answer the following questions using the banker's algorithm:

1. What is the content of the matrix Need?
2. Is the system in a safe state?  (If so, show a safe sequence; if not, be specific about the violating conditions.)
3. If a request from process P1 arrives for (0, 4, 2, 0), can the request be granted immediately? (Be sure and justify your answer.)