A processes | B processes |
wait(X) | wait(Y) |
signal(Y) | wait(Y) |
|
signal(X) |
|
signal(Y) |
Identify ALL possible pass-the-baton patterns. You should indicate the following as clear as possible: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
Semaphore WriterOnly = 1; // other semaphores are the same
A writer process has the following form:
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)?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:
The initial values of ReadCount and WriteCount are both 0. Please study this solution and answer the following questions: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); }
to the following?while { Wait(Block); Wait(ReadMutex); Wait(ReadCountMutex); ReadCount++; if (ReadCount == 1) Wait(WriteMutex); Signal(ReadCountMutex); Signal(ReadMutex); Signal(Block); ............... }
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.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); }
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. |