CS3331 Reading List: Week 12

Course Material
Monitor and Deadlocks slides used in class is available in the common directory with filenames 10-Monitors.pdf and 11-Deadlocks.pdf
Study the monitor section of Multithreaded Programming with ThreadMentor: A Tutorial
  • If you wish to install ThreadMentor on your home machine, the common directory has three files: ThreadMentor-Fedora.tar.gz for Linux 32-bit, ThreadMentor-Linux64.tar.gz for Linux 64-bit, and ThreadMentor-Win32-VSNet2005.zip. Sorry, there is no Mac version.
  • A ThreadMentor FAQ page for Linux and Windows is available here.
If you wish to print these slides, print them double-sided and print as many slides as possible on the same page. Let us save a tree!

Programming Material
Do Programming Assignment V.

Homework Assignment
Do the following problems:
  • Why is nested monitor calls (i.e., calling a monitor procedure from within a monitor) not a good practice?
  • Why is it a bad idea to use a semaphore in a monitor?
  • Design a monitor that manages a shared resource which must be accessed in a mutual exclusive way. This monitor has two methods: acquire() and release(). Before using this shared resource, a thread must call acquire(). If the resource is being used by another thread, the monitor blocks the calling thread. Otherwise, the calling thread has the permission to use. After using this shared resources, a thread calls release() so that another thread can use.
  • Design a barrier monitor with a Barrier_Wait() method. In last week's reading, we mentioned the cascading signals technique. If you use the Hoare type for this monitor, what is the safe way in releasing all blocked thread? Is the cascading signals more reliable? What if your monitor is of the Mesa type, would cascading signals make a difference?
  • Implement a semaphore using a monitor.
  • Recall the smokers problem discussed in class. Suppose one semaphore is used to control the table, and a semaphore is assigned to each ingredient. In this way, the agent will pick two ingredients on the table and signal the corresponding semaphores:
    Agent
    -----
    
    while (1) {
       pick two ingredients, say i and j
       signal semaphore i;
       signal semaphore j;
       wait until the table is cleared;
    }
    
    The smoker who has ingredient k and needs ingredients i and j to make a cigarette does the following:
    Smoker who has ingredient k
    ---------------------------
    
    while (1) {
         wait on semaphore i;
         wait on semaphore j;
         signal semaphore table;
         make a cigarette;
    }
    
    Is this solution to the smokers problem deadlock free? If it is not deadlock free, show an execution sequence. Otherwise, prove rigorously that this solution is deadlock free.
  • Design a monitor to solve this general smokers problem. More precisely, design a monitor with name General_Smoker and a number of monitor procedures as follows:
    • 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.
    In this way, a smoker who has tabacco will call Acquire_Matches(...) and Acquire_Paper(...). He will make a cigarette only after returning from the call to the second monitor call (i.e., from Acquire_Paper(...)). Note that the monitor must: (1) know the ingredients made available by the agent for every round; (2) releases a smoker who has both the needed ingredient; (3) should not cause a deadlock; (4) should allow immediately the smoker whose needed ingredients are available to continue rather than blocking this smoker un-necessary; and (5) your monitor has to be deadlock-free.
  • Suppose all chopstick are placed at the center of the table, and any two of them can be used by a philosopher. Assume that requests for chopsticks are made one at a time. Design a simple rule for determining whether a particular request can be satisfied without causing deadlock given the current allocation of chopsticks to philosophers.
  • In the semaphore and monitor solutions to the Readers-Writers problem, a common semaphore or condition variable are used to block BOTH readers and writers. As a result, when that semaphore/condition variable is signaled, a reader or writer could be released, and there is no rule to guarantee the released process/thread is of a particular kind. We may resolve this situation with four counters: the first one counts the number of active readers, the second one counts the number of waiting readers, the third one counts the number of active writers which should be no more than 1, and the fourth one counts the number of waiting writers. Use this scheme to solve the reader-priority version with semaphores. Do the same using a monitor.
  • Slides 22-26 of 10-Monitors.pdf show a way of implementing a version of the reader-writer problem. This implementation uses the Hoare type of monitors. Redo this with the Mesa type.
  • Implementing a semaphore with a monitor is an easy task. See a previous problem. How can we implement a monitor with semaphores?

    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
    
    Note that if there are suspended processes, this leaving process allows one of them to go but does not release the monitor. In this way, when the released process that was suspended before starts execution, it has the monitor. In other word, the leaving process passes the monitor to the released 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
    
    Note that in this implementation, we give a higher priority to the re-entering processes. In general, this is not always the case in other systems.

    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?

We do not collect your practice work; but, similar problems will appear in quizzes and exams in the future. Note that I will not make any announcement in class for these short quizzes. In other word, short quizzes may take place at any time as long as I see it is appropriate.