CS3331 Reading List: Week 9

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.

• 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.

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

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?

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);
}

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?

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);
}

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.