Demonstrate that monitors conditional critical regions and semaphores are all equivalent insofar as the same types of synchronization problems can be implemented with them?

Answer 1

1. Semaphore waiting lists are often implemented as FIFO queues. Could they be implemented as stacks? What problems would this implementation cause?

2. As discussed in class, a monitor is the result of a fusion between shared data and the functions (methods) that operate on this data. The code below makes the assumption that a monitor can declared just like a class in C++. This is a hypothetical situation.

   Consider the following solution to the dining philosopher's problem: monitor Chopsticks { private: // variable declarations go here public: void pickup( int philosopherNumber ); void putdown( int philosopherNumber ); }; Chopsticks::pickup( int philosopherNumber ) { // function body goes here } Chopsticks::putdown( int philosopherNumber ) { // function body goes here } //-------------------------------------------- Chopsticks chopsticks; void philosopher( int n ) { while ( true ) { think(); chopsticks.pickup( n ); eat(); chopsticks.putdown( n ); } }

   Write declarations for the shared variables needed by the monitor and the pseudo-code for the bodies of the two monitor functions. Be sure that your solution is deadlock and starvation free.

3. Write a solution of the dining philosophers problem that uses message passing and a central coordinating process the the philosophers communicate with when they want to start or stop eating.

4. Do problem 6.9 in the text: Demonstrate that monitors, conditional critical regions, and semaphores are all equivalent, insofar as the same types of synchronization problems can be implemented with them.

   Hint: Show that if one of the mechanisms is available then another can be implemented. Then show that if that mechanism is available then the third can be implemented. Finally, show that if the third is available then the first can be implemented. That is: if each of the mechanisms is represented by one of the letters A, B or C, show thatA => B => C => A

   which shows that these mechanisms are all logically equivalent.

5. Suppose that an operating system supported message passing, but did not directly support semaphores. Show how you could implement semaphores by the use of suitable library routines. (Hint: Use a semaphore manager process that receives wait() and signal() messages from other processes).

6. (Optional for extra credit) Your answers to the last two problems show that message passing is at least as powerful as the other three process coordination primitives that rely on shared memory. (Given message passing, you could implement semaphores, etc.) Show how you could implement the message passing primitives send() and receive() on a shared memory system using any of the other three schemes (your choice).