CS3331 Reading List: Week 8

Course Material
Slides used in class is available in the common directory with filename 07-Cpp-TM.pdf. Sample programs are in 07-Cpp-TM.tar.gz for Windows. The set of semaphores slides is 08-Semaphores.pdf.
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 III.

Homework Assignment
Answer the following questions:
  • In the definition of a semaphore, the counter and waiting list are private members, and, as a result, it is impossible to know the current value of the counter. Suppose a public member function GetCounter() is added, and suppose this member function, just like the Signal() and Wait() functions, is also atomic. If the counter value is negative, its absolute value is the number of processes in the waiting list. Discuss the accuracy of the returned value by member function GetCounter(). In other word, is it always the case that the returned value provides an accurate count of waiting processes?
  • Show, by an execution sequence, that if the method Wait() is not atomic (but the method Signal() is) then mutual exclusion cannot be guaranteed by the use of a semaphore.
  • Show, by an execution sequence, that if the method Signal() is not atomic (but the method Wait() is) then mutual exclusion cannot be guaranteed by the use of a semaphore.
  • Show that if the Wait() and Signal() methods are atomic then the following implementation of mutual exclusion is correct. More precisely, prove rigorously that the following code guarantees mutual exclusion among all processes. 
    Semaphore S = 1;

Process i (i = 1, 2, 3, ..., n >= 2) 

while (1) { 
  ...         
  Wait(S);
  // in critical section
  Signal(S);
  ... 
}
  • Suppose we have three processes P1, P2 and P3 and process Pi only prints the value of i as follows: 
    Process 1        Process 2         Process 3

while (1) {      while (1) {       while (1) {
  ...               ...               ...
  cout << "1";      cout << "2";      cout << "3";
  ...               ...               ...
}                }                 }
    Add semaphores and cout if necessary to the above processes so that the three processes will print out the following sequence 1 2 3 2 1 2 3 2 1 2 3 2 1 ...
  • Modify the above template so that it will print out the following sequence 1 2 3 1 2 3 1 2 3 1 2 3 ...
  • We know that a semaphore with an appropriate initial value can guarantee mutual exclusion. Does the semaphore solution satisfy the progress condition and the bounded waiting condition? Use execution sequences to answer this question.
  • Use the Test-and-Set instruction to implement semaphore wait and semaphore signal.
  • It was shown in class that deadlocks can occur in the naive solution to the dining philosophers problem. We also showed that to avoid deadlocks from happening a righty philosopher may be introduced or add a restriction that at most four philosophers may sit down and eat. Do the following problems:
    • Rigorously prove that the righty solution does not cause any deadlock.
    • Rigorously prove that the four-chair solution does not cause any deadlocks.
    • Show, with execution sequences, that the naive, righty and four-chair solutions can have starvation. More precisely, use execution sequences to show that there are philosophers who are hungry and have no chance to eat.
    Note that a rigorous proof means an argument with sound logical reasoning rather than an observation, an instance, or a vague claim.
  • It was suggested that to avoid possible deadlocks in the philosophers problem one may add more resources which should be arranged in a different way. The following shows some attempts:
    1. Add a single chopstick at the center of the table. A philosopher picks up his left chopstick and then competes to grab the chopstick at the center. If he can get both, then he eats.
      • Does this approach avoid any possible deadlock?
      • Any bad consequence that attempt could have such as maximum parallelism?
      • With semaphores, is it possible to implement the following protocol? Why?
        • Each philosopher picks up his left chopstick.
        • If he fails to do so, then try to get the center one. Otherwise, he waits until his left chopstick becomes available.
        • Do the same for his right chopstick.
        Discuss the efficiency and deadlock issues of this "suggested" solution.
    2. Instead of having the chopsticks arranged as discussed in class, we make all five chopsticks in a tray next to the table so that any philosopher can pick any chopstick. In this attempt, each philosopher picks up his first chopstick, and, then picks the second. Is deadlock possible? How about parallelism?
  • We discussed in class that the waiting processes on a semaphore should be better considered as a set (with any ordering) rather than a queue. As a result, there is no particular order when releasing a waiting process, and starvation could occur. On the other hand, with multiple semaphores we are able to come up with a starvation-free solution to the critical section problem.

    The following solution, due to Morris (1979), uses three semaphores. Semaphores FirstBarrier and SecondBarrier are used to setup two barriers, and semaphore Lock is used to protect counter FirstCount for mutual exclusion purpose. Two counters are used: FirstCount counts the number of processes ready to cross the first barrier represented by semaphore FirstBarrier, and SecondCount counts the number of processes having already crossed the first barrier but not barrier SecondBarrier. 

    Semaphore:  FirstBarrier    = 1,
            SecondBarrier   = 0,
            Lock            = 1;

int         FirstCount      = 0,
            SecondCount     = 0;

    The following shows the enter and exit protocol: 

    // Enter Protocol

Wait(Lock);                              // I am ready and prepared to cross the 1st barrier
     FirstCount++;                       // increase the counter
Signal(Lock);

Wait(FirstBarrier);                      // wait on the 1st barrier
     SecondCount++;                      // I have successfully crossed the 1st barrier
     Wait(Lock);                         // Have to lock the counter to decrease
          FirstCount--;                  // Now I am about to cross the 2nd barrier
          if (FirstCount == 0) {         // if I was the only one crossing the 1st barrier
               Signal(Lock);             //     then release the lock
               Signal(SecondBarrier);    //     and signal the 2nd barrier so that I could cross
          }
          else {                         // if I am not the only one, I have to wait; but
               Signal(Lock);             //     I have to release the lock, and
               Signal(FirstBarrier);     //     also open the 1st barrier
          }
Wait(SecondBarrier);                     // wait on the second barrier
SecondCount--;                           // I am no more waiting to cross the 2nd barrier

// in critical section 

// Exit protocol

if (SecondCount == 0)                    // if there is no one wait on the 2nd barrier
     Signal(FirstBarrier);               //     open the 1st barrier
else								 // otherwise,
     Signal(SecondBarrier);              //     open the 2nd barrier

    Try to understand the above protocol, and convince yourself that mutual exclusion and starvation freedom are satisfied. How about the progress and bounded waiting conditions?

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.