CS414 Operating Systems - Homework 3

Due: (Wed) Feb 27, 10am. No late assignments will be accepted.

Submit your solution using CMS. Prepare your solution using Word (.doc) or some ascii editor (.txt), as follows:

• Use 10 point or larger font.
• Start each problem's solution on a new page.
• Use at most 1 page per problem.

1. Consider a set of N processes, where for i ranging from 1 to N each process proc_i has the form:

   proc_i: PROCESS
        L_i
        barrier
        M_i
        END process
   

   Here, L_i is called the first part and M_i is called the second part of proc_i.

   Unspecified code barrier, which is identical in each process, is intended to synchronize process execution so that no process begins its second part until every process has completed its first part. This kind of synchronization is useful in large-scale scientific computations that are structured as a set of parallel multi-stage pipelines, where no process advances to the next stage until all processes have completed the previous stage. (The example above is a 2-stage pipeline.)

   Design code for barrier by using split binary semaphores. Be sure to give the initialization for any variables and semaphores being used.

   HINT: Let nL be the number of processes that have completed execution of their first parts and let nM be the number of processes that have started execution of their second parts. So, the following must be kept invariant:

     I:  0 <= nL <= N  AND
         0 <= nM <= N  AND
         ( nM = 0 OR  nL = N )
   

---

2. Here is the outline for a monitor to synchronize access for a one-lane bridge:

   BridgeControl: MONITOR
                  VAR numN : INTEGER   // number vehicles on bridge and going North
                      numS : INTEGER   // number vehicles on bridge and going South
                      blkN : INTEGER  // number vehicles blocked waiting to go North
                      blkS : INTEGER  // number vehicles blocked waiting to go South
                      ... others ...
   
         EnterNorth: PROCEDURE();
                     ...
                     END EnterNorth;
   
         ExitNorth: PROCEDURE();
                     ...
                     END ExitNorth;
   
   
         EnterSouth: PROCEDURE();
                     ...
                     END EnterSouth;
   
         ExitSouth: PROCEDURE();
                     ...
                     END ExitSouth;
   
         BEGIN
           ... initialization code ...
         END BridgeControl
   

   Each vehicle is modeled by a process. A vehicle traveling North invokes EnterNorth before reaching the bridge and invokes ExitNorth after traversing the bridge. Vehicles traveling South follow the obvious analogous protocol.

   Fill in the details for EnterNorth and ExitNorth of the above monitor (we will assume the code for EnterSouth and ExitSouth is symmetric) in a way that ensures

   1. vehicles granted simultaneous access to the bridge are not traveling in opposite directions, and
   2. a steady stream of vehicles traveling in one direction will not forever block vehicles attempting to travel in the other.

   Declare any other variables needed and any condition variables. Use c.SIGNAL and c.WAIT with the "signal-urgent" semantics discussed in class (i.e., roughly "signal and wait" in the textbook).

   HINT: Block a vehicle not only if it is heading against traffic but also if it is heading with traffic and vehicles are already waiting to head in the other direction.