The smoker who has ingredient k and needs ingredients i and j to make a cigarette does the following:Agent ----- while (1) { pick two ingredients, say i and j signal semaphore i; signal semaphore j; wait until the table is cleared; }
Is this solution to the smokers problem deadlock free? If it is not deadlock free, show an execution sequence. Otherwise, prove rigorously that this solution is deadlock free.Smoker who has ingredient k --------------------------- while (1) { wait on semaphore i; wait on semaphore j; signal semaphore table; make a cigarette; }
Since we need mutually exclusive monitor boundary, we need a Mutex, with initial value 1, for each monitor. A process must execute Mutex.Wait() before entering the monitor and must execute Mutex.Signal() after leaving the monitor. This is exactly what MonitorBegin() and MonitorEnd() are doing in ThreadMentor.
Since a signaling process must wait until the resumed process either leaves the monitor or waits on a condition variable, we need a semaphore Next, with initial value 0, to block the suspended processes. A signaling process can use Next to block itself. To keep a record of how many suspended processes are blocked by semaphore Next , we need a counter Next_Count. Therefore, in each public monitor procedure, its code looks like the following:
Note that if there are suspended processes, this leaving process allows one of them to go but does not release the monitor. In this way, when the released process that was suspended before starts execution, it has the monitor. In other word, the leaving process passes the monitor to the released process.Mutex.Wait(); // monitor procedure code if (Next_Count > 0) // there are suspended processes Next.Signal(); // release one of them else Mutex.Signal(); // release an entering process
To implement a condition variable CV, we need a semaphore for blocking processes CV_Sem and a variable for counting the number of waiting processes CV_Count. Both are initialized to 0.
Condition wait CV.Wait() is implement as follows:
Note that in this implementation, we give a higher priority to the re-entering processes. In general, this is not always the case in other systems.CV_Count++; // waiting is increased by 1 if (Next_Count > 0) // if there are suspended processes Next.Signal(); // release one of them to take the monitor else // otherwise, Mutex.Signal(); // release the monitor CV_Sem.Wait(); // block myself CV_Count--; // if I am released, the number of wait is reduced by 1
The following implements CV.Signal():
if (CV_Count > 0) { // if there are waiting processes, Next_Count++; // the signaler will join the Next waiting CV_Sem.Signal(); // release one of them Next.Wait(); // the signaler suspends itself Next_Count--; // the signaler is released } // otherwise, do nothing.
Study this implementation and make sure you understand it. Therefore, a monitor can be implemented using semaphores, and, of course, monitors and semaphores are equivalent.
Note that this implementation is for the Hoare type monitors. Can you modify it to implement the Mesa type monitors?
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. |