CS3331 Reading List: Week 9

Course Material
Slides used in class is available in the common directory with filename 08-Semaphores.pdf and 09-Race-Conditions.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 IV.

Homework Assignment
Answer the following questions:
  • In 08-Semaphores.pdf we discussed a number of patterns that are frequently used in semaphore related synchonization problems. Study these patterns and find out what patterns are used in the examples discussed on the slides. In particular, you should understand thoroughly the meaning, the technique and the use of the passing the baton pattern.
  • Suppose a system in which there are two types of threads, type A processes and type B processes. All processes of type A execute the same code and all processes of type B execute the same code. There are two semaphores, X and Y, initialized to 2 and 0 respectively. The code of each process type is shown below:

    A processes B processes
    wait(X) wait(Y)
    signal(Y) wait(Y)

    signal(X)

    signal(Y)
    Answer the followingt questions:
    1. Is it possible for processes to finish in the orde AABAB? If so, depict an execution sequence that results in this order. If not, provide a complete and accurate argument.
    2. Is it possible for processes to finish in the order AABBA? If so, depict an execution sequence that results in this order. If not, provide a complete and accurate argument.
    3. Is it possible for processes to finish inthe order AAABB? If so, depict an execution sequence that results in this order. If not, provide a complete and accurate argument.
    4. Can the system deadlock? If so, depict an execution sequence that results in this order. If not, provide a complete and accurate argument.
    5. Modify the code so that processes must finish in the order AABAB.
  • Suppose the smokers problem is changed to the following version.
    • There are three semaphores, one for tobacco, one for matches, and one for paper.
    • The smoker who has tobacco waits on semaphores matches and paper; the smoker who has matches waits on semaphores tobacco and paper; and the smoker who has paper waits on semaphores tobacco and matches.
    • The agent randomly picks up two ingredients and signals the corresponding semaphores.
    • There is a table, of course.
    Does this version work properly without any problem?
  • The above more general smoker version is basically due to waiting on multiple semaphores sequentially. Suppose there is a mechanism to collect multiple semaphores together into a single unit so that a thread can wait on and signal multiple semaphores simultaneously in an atomic way. (In fact, Unix semaphores are of this type.) Would this mechanism solve this general smokers problem?
  • Consider the following code:
    Semaphore   Mutex(1);
    Semaphore   Multiplex(10);
    Semaphore   Block(0);
    Semaphore   Done(0);
    
    int         n = 0;
    
    Thread A Group              Thread B Group
    ==============              ==============
    
    Mutex.Wait();               Multiplex.Wait();
      if (n > 0) {                Mutex.Wait();
        Block.Signal();             n++;
        Done.Wait();              Mutex.Signal();
      }                           Block.Wait();
    Mutex.Signal();             Multiplex.Signal();
                                
    // Something El             // Something Else
                             
                                n--;
                                if (n == 0)
                                  Done.Signal();
                                else
                                  Block.Signal();
    
                                // Something Else
    
    Identify ALL possible pass-the-baton patterns. You should indicate the following as clear as possible:
    1. For each baton, where is it acquired?
    2. For each baton, where is it passed? Also indicate its receiver of this baton.
    3. For each baton, where is it released?
    Draw arrows like we did in class and on slides to indicate the path of baton passing.
  • As you may have noticed that the WrtMutex semaphore is shared by the readers and writers. It blocks no more than one reader and multiple writers (Prove this!). As a result, when an exiting reader or writer signals this semaphore, a reader or a writer could be released. Some argued that this does not satisfy the "reader priority" requirement because there may have already had a reader waiting. Although it is an argument based on when the "reading" starts (i.e., entering at the beginning vs. actual reading), one can certainly improve the situation a little. Here is another reader-priority solution with one added semaphore WriterOnly with initial value 1. The following is the code for writers as readers are not affected:
    Semaphore  WriterOnly = 1; // other semaphores are the same
    

    A writer process has the following form:

    while {
         Wait(WriterOnly);     // wait on our own semaphore
              Wait(WrtMutex);  // then, compete with the only possible reader
                               // writing
              Signal(WrtMutex);
         Signal(WriterOnly);
    }
    
    Do you think this is a "better" version? In other words, does the only waiting reader on semaphore WrtMutex have more chance to take the priority (i.e., reader-priority)?
  • Here is another solution.
    int  ActiveReaders = ActiveWriters = 0;
    int  WaitingReaders = WaitingWriters = 0;
    
    Semaphore Mutex = 1;       // protecting the above declared counters
    Semaphore OKtoRead = 0;
    Semaphore OKtoWrite = 0;
    
    

    A reader process has the following form:

    while (1) {
         Wait(Mutex);                           // the enter part
         if (ActiveWriters + ActiveReaders == 0) {  // no one is reading and writing
              Signal(OKtoWrite);
              ActiveReaders++;                  // I am in
         }
         else 
              WaitingReaders++;                 // otherwise, I must wait
         Signal(Mutex);                         // release the counter lock
    
         Wait(OKtoRead);                        // wait to get the read permission
                                                // read data
    
         Wait(Mutex);                           // the exit part
         ActiveReaders--;                       // I am done reading
         if (ActiveReaders == 0 && WaitingWriters > 0) {
              Signal(OKtoWrite);                // allow writing of no reader and some writers
              ActiveWriters++;                  // we have an active writer
              WaitingWriters--;                 //    and one less waiting writers
         }
         Signal(Mutex);                         // release the counter
    }
    

    A writer process has the following form:

    while (1) {
         Wait(Mutex);                           // the enter part
         if (ActiveWriters + ActiveReaders + WaitingWriters == 0) {  
                                                // no one is reading, writing and waiting
              Signal(OKtoWrite);
              ActiveWriters++;                  // I (writer) am in
         }
         else 
              WaitingWriters++;                 // otherwise, I must wait
         Signal(Mutex);                         // release the counter lock
    
         Wait(OKtoWrite);                       // wait to get the read permission
                                                // write data
    
         Wait(Mutex);                           // the exit part
         ActiveWriters--;                       // I am done writing
         if (WaitingWriters > 0) {              // if there are writers waiting
              Signal(OKtoWrite);                // allow writing of no reader and some writers
              ActiveWriters++;                  // we have an active writer
              WaitingWriters--;                 //    and one less waiting writers
         }
         else {
              while (WaitingReaders > 0) {      // if there are waiting readers
                 Signal(OKtoRead);              //    let them read one-by-one
                 ActiveReaders++;
                 WaitingReaders--;
         Signal(Mutex);                         // release the counter
    }
    

    Study this solution and make sure you understand what it is trying to do. Is this a reader-priority or a writer-priority solution?

  • We discussed the reader-priority version of the readers/writers problem. Here is a solution to the writer-priority version of the readers/writers problem in which writers have higher priority. More precisely, as long as there is at least one writer has declared a desire to write, no new readers are allowed to read. Now, a reader process uses three semaphores Block, ReadMutex and ReadCountMutex, and a writer process uses two semaphores WriteMutex and WriteCountMutex:
    Semaphore:  Block           = 1,
                ReadMutex       = 1,
                ReadCountMutex  = 1,
                WriteMutex      = 1,
                WriteCountMutex = 1;
    

    A reader process has the following form:

    while {
         Wait(Block);
              Wait(ReadMutex);
                   Wait(ReadCountMutex);
                        ReadCount++;
                        if (ReadCount == 1) 
                             Wait(WriteMutex);
                   Signal(ReadCountMutex);
              Signal(ReadMutex);
         Signal(Block);
    
         ..... read the database .....
    
         Wait(ReadCountMutex);
              ReadCount--;
              if (ReadCount == 0)
                   Signal(WriteMutex);
         Signal(ReadCountMutex);
    }
    

    A writer process has the following form:

    while {
         Wait(WriteCountMutex);
              WriteCount++;
              if (WriteCount == 1)
                   Wait(ReadMutex);
         Signal(WriteCountMutex);
         Wait(WriteMutex);
    
         ..... write the database .....
    
         Signal(WriteMutex);
         Wait(WriteCountMutex);
              WriteCount--;
              if (WriteCount == 0)
                   Signal(ReadMutex);
         Signal(WriteCountMutex);
    }
    
    The initial values of ReadCount and WriteCount are both 0. Please study this solution and answer the following questions:
    1. What is the purpose of using Wait(Block) and Wait(ReadMutex)? Before proceed to the next question, think again if your point is correct.
    2. You would say ``semaphores Block and ReadMutex are used to lock the database.'' But, if this were true, the database would be accessed by no more than one reader (or one writer). Is this a correct observation? Or, did I fool you with some bad reasoning? Keep in mind that the readers-and-writers problem requires simultaneous read and exclusive write.
    3. Now, tell me why readers can access the database simultaneously.
    4. But, the initial value of Block is 1. This would only allow one reader to access the database. If this is the case, why don't we change:
      while {
           Wait(Block);
                Wait(ReadMutex);
                     Wait(ReadCountMutex);
                          ReadCount++;
                          if (ReadCount == 1) 
                               Wait(WriteMutex);
                     Signal(ReadCountMutex);
                Signal(ReadMutex);
           Signal(Block);
           ...............
      }
      
      to the following?
      while {
           Wait(ReadMutex);
                Wait(ReadCountMutex);
                     ReadCount++;
                     if (ReadCount == 1) 
                          Wait(WriteMutex);
                Signal(ReadCountMutex);
           Signal(ReadMutex);
      
           ..... read the database .....
      
           Wait(ReadCountMutex);
                ReadCount--;
                if (ReadCount == 0)
                     Signal(WriteMutex);
           Signal(ReadCountMutex);
      }
      
      Removing Block is the most natural suggestion, since it is used in the reader process and is used exactly once. Explain why you cannot do this. If Block is removed, what will happen to the solution.
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.