CS3331 Reading List: Week 12

Agent
-----

while (1) {
   pick two ingredients, say i and j
   signal semaphore i;
   signal semaphore j;
   wait until the table is cleared;
}

Smoker who has ingredient k
---------------------------

while (1) {
     wait on semaphore i;
     wait on semaphore j;
     signal semaphore table;
     make a cigarette;
}

• Acquire_Table(...): This procedure is called by the agent before he needs the table. You may add two arguments indicating which ingredients will be put on the table. The time period the agent stays in the monitor means the agent is waiting for the table to be cleared. Upon return, these two ingredients are on the table. The agent must wait for a while before making another round.
• Acquire_Paper(...): A smoker who needs paper will call this procedure with the only argument being the smoker who needs paper. Upon return, the calling smoker has the needed paper.
• Acquire_Matches(...): A smoker who needs matches will call this procedure with the only argument being the smoker who needs matches. Upon return, the calling smoker has the needed matches.
• Acquire_Tobacco(...): A smoker who needs tabacco will call this procedure with the only argument being the smoker who needs tobacco. Upon return, the calling smoker has the needed tabacco.

Since we need mutually exclusive monitor boundary, we need a Mutex, with initial value 1, for each monitor. A process must execute Mutex.Wait() before entering the monitor and must execute Mutex.Signal() after leaving the monitor. This is exactly what MonitorBegin() and MonitorEnd() are doing in ThreadMentor.

Since a signaling process must wait until the resumed process either leaves the monitor or waits on a condition variable, we need a semaphore Next, with initial value 0, to block the suspended processes. A signaling process can use Next to block itself. To keep a record of how many suspended processes are blocked by semaphore Next , we need a counter Next_Count. Therefore, in each public monitor procedure, its code looks like the following:

Mutex.Wait();
   // monitor procedure code
if (Next_Count > 0)  // there are suspended processes
   Next.Signal();    // release one of them
else
   Mutex.Signal();   // release an entering process

To implement a condition variable CV, we need a semaphore for blocking processes CV_Sem and a variable for counting the number of waiting processes CV_Count. Both are initialized to 0.

Condition wait CV.Wait() is implement as follows:

CV_Count++;           // waiting is increased by 1
if (Next_Count > 0)   // if there are suspended processes
   Next.Signal();     //    release one of them to take the monitor
else                  // otherwise,
   Mutex.Signal();    //    release the monitor
CV_Sem.Wait();        // block myself
CV_Count--;           // if I am released, the number of wait is reduced by 1

The following implements CV.Signal():

if (CV_Count > 0) {   // if there are waiting processes,
   Next_Count++;      //    the signaler will join the Next waiting
   CV_Sem.Signal();   //    release one of them
   Next.Wait();       //    the signaler suspends itself
   Next_Count--;      //    the signaler is released
}                     // otherwise, do nothing.

Study this implementation and make sure you understand it. Therefore, a monitor can be implemented using semaphores, and, of course, monitors and semaphores are equivalent.

Note that this implementation is for the Hoare type monitors. Can you modify it to implement the Mesa type monitors?