CS4411 Reading List: Week 4

• Section 6.1 to Section 6.5

• How to declare and initialize a semaphore? What functions are for Wait() and Signal()?
• Read all example programs (read ahead).
• Compile the sample programs and use the visualization system to make sure you can ``play back'' the events.

• Chapter 6: 6.15, 6.18, 6.20 (pp. 270)
• What if the TS instruction is not atomic? More precisely, the implementation steps of this instruction are not executed in a single unit. Can you fine potential race conditions?
• On page 233 (Figure 6.8), there is a solution to the critical section problem, using the test-and-set instruction, that satisfies all three conditions. Study this solution thoroughly.
• Almost all CPUs for larger systems have the TS and similar synchronization related instructions as privileged instructions. However, some CPUs for personal systems may have similar instructions non-privileged. Discuss why would CPU designers take this approach.

This is a solution to the second version of the Readers-and-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.

You do not have to turn in your paper. What I really expect you to do is using these problems to gauge your understanding of the subject. So, do the problems after finish reading the above sections.