CS3331 Reading List: Week 11

Course Material
Monitor slides used in class is available in the common directory with filename 10-Monitors.pdf.
Many systems provide mutex locks and condition variables in an unstructured way. We can simulate a monitor with mutex locks and condition variables. Read the Mutex and condition variables section of Solaris Multithreaded Programming to learn how this is done. This is required reading!
Study 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 (Most are for THIS week):
  • Find some web sites or tutorials to learn Unix System V semaphores. More specifically, learn how to get a semaphore set with semget(), change the permissions, set initialize values, etc of a semaphore set with semctl(), and perform operations on a semaphore set with semop(). Note that there is no Wiat() and Signal(), since these two functions are integrated into the single function semop(). You will see that the use of Unix semaphores is more complex than what we have learned so far. POSIX semaphores are similar with some differences.
  • Many may have the tendency to return the value of a private variable of a monitor and test it to determine what the next step should be. For example, return the internal counter of a monitor and do something if the returned value is positive. The point is that doing this test outside of a monitor will be more efficient then doing it inside of a monitor because of less locking and unlocking (of the monitor). Whys is this usually not a wise move?
  • Why is calling a monitor procedure in another monitor from within a monitor not a good idea? Explain this with a convincing argument.
  • Why is the use of a semaphore in a monitor prohibited? Explain this with a convincing argument. Just saying that we use condition variable in a monitor is not a convincing argument. There is a much stronger reason.
  • There are commonly two ways of releasing threads from a condition variable. More precisely, the first method is the use of a for as follows: 
    for (i = 0; i < n; i++)
     CV.Signal();
    This method uses a single thread, which is executing in a monitor, to release threads waiting on condition variable CV, where n is sufficiently large so that all blocked threads are released.

    The second method just releases one thread, and allows the released thread to release other threads. This is referred to as cascading signals. 

    // place where threads block
CV.Wait();
CV.Signal();  // this one is released and release the next one

// other work in a monitor

CV.Signal();  // initialize a cascading release here
    Analyze and compare these methods under Hoare type and Mesa type monitors.
  • A barrier is synchronization primitive with a positive initialization value n and a method Barrier_Wait(). When a thread calls Barrier_Wait(), if it is not the n-th thread, it blocks in the barrier. When the n-th thread comes, this "last" thread releases all n-1 threads blocked in the barrier, and, as a result, all n threads, the n-th thread included, continues. Design a barrier monitor of Hoare type and method Barrier_Wait(). Which release method discussed above would you want to use? Again, analyze and compare both methods under Hoare type and Mesa type monitors. Note that before all n-1 blocked threads have been successfully released, your barrier should not allow new threads to join this activity and get "released" as part of the current batch. In other words, threads that come while the blocked threads are being released must be handled in the next batch. What would you do if the monitor is a Mesa type?
  • Do the Roller-Coaster problem discussed on the class note using a Hoare monitor.
  • We discussed in class a solution to the philosophers problem in which each philosopher has three states: THINKING, HUNGRY and EATING. We solved this problem using a monitor. Re-do this problem using only semaphores.
  • Although monitors are more structured than semaphores, deadlocks may still occur if monitors are not designed carefully. Consider the following monitor of Hoare type 
     
monitor  deadlock
   condition  p, q;

   void  stop(void)
   {
      p.wait;
      ......
      q.signal;
   }

   void  go(void);
   {
      ......
      p.signal;
      q.wait;	 
   }
   // no initialization is required
}
    Suppose we have processes P1 and P2 as follows: 
    
P1:    repeat ..... deadlock.stop; ..... until false;
P2:    repeat ..... deadlock.go;   ..... until false;
    The intention of this monitor is that P1 is required to wait on condition p until P2 has completed some task, at which point it calls deadlock.go to release P1. P2 then waits until P1 has performed its task, when it signals condition q to indicate that P2 may continue.

    This program looks correct and seems can perform the indicated task. But, it has the potential to deadlock. Find this deadlock. Would the deadlock still be there is the monitor is a Mesa type?

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.