Out: September 23, 2005.
Due: At the start of lecture,
September 30 (Friday), 2005. We will accept only solutions that are typed-up
and printed out (figures and tables may be drawn by hand).
No written solutions or online handins.
Resources you are allowed to use:
Unless otherwise mentioned, the only resources you can use are the lectures
slides, your notes, the Tanenbaum textbook, and any other textbook on OS's,
architecture, data structures or previous CS material.
You cannot refer to any online resources (unless otherwise mentioned).
You cannot use ready-made solutions under any circumstances..
Relevant Lectures: 8-12.
Points: Unless
otherwise mentioned, a problem is worth 5 points. The HW is worth a total of 20 points. If a question has multiple parts,
the 5 points are split equally among the parts.
Warning: Homeworks are individual efforts. Although you are allowed to
discuss HWs with your
fellow students, you are expected to solve them yourself and type
up the
solution yourself. For detailed information on penalties, cheating and
playing it safe, see
this page.
1. You have been hired to coordinate people trying to cross a river. There is only a single boat, capable of holding at most three people. The boat will sink if more than three people board it at a time. Each person is modeled as a separate process, executing as follows:
Person(int
location) // location is either 0 (left bank) or 1(right bank){
ArriveAtBoat(location);
BoardBoatAndCrossRiver(location);
GetOffOfBoat(location);
}
Provide the code for ArriveAtBoat and GetOffOfBoat. The BoardBoatAndCrossRiver is of no interest since it has no role in synchronization. ArriveAtBoat must not return until it s safe for the person to cross the river in the given direction (it must guarantee the boat will not sink, and the no one will step off the pier into the river when the boat is on the opposite bank). GetOffOfBoat is called to indicate that the caller has finished crossing the river; it can take steps to let other people cross the river. You don't need to worry about starvation in your solution. You are allowed to use only monitors and condition variables for this problem (if you use any other sync primitives, you'll get a 0). For each condition variable x, you can assume (in addition to wait and signal) a third operation x.broadcast() that wakes up all processes currently suspended on x.
2. Implement a synchronization barrier using only semaphores and mutexes. In other words, implement a function call barrier(int processid, int N) that processes can call, and that returns only when the barrier condition is satisfied. As you will recall from class, a barrier is a common paradigm in many parallel applications. A barrier is supposed to block the calling process until all N processes (N known a priori and fixed) have reached the barrier. Be careful that your program still works when the same barrier is called multiple times by processes -- ensure that the "wait until all N processes have reached the barrier" condition is true of each barrier call, and consecutive barrier calls do not interfere with each other). You are allowed to use only semaphores and mutexes for this problem (if you use any other sync primitives, you'll get a 0).
3. Problem 3.20 from text.
4. Problem 3.24 from text.
Updated: Sep. 23, 2005. (c) Indranil Gupta.