[Points 3] What is the purpose of a condition variable in a monitor? How is the
ID: 3847873 • Letter: #
Question
[Points 3] What is the purpose of a condition variable in a monitor? How is the condition variable implemented? Explain your answer using an example.
[Points 3] In the monitor solution to the dining-philosopher’s problem (Figure 5.18), what happens when a process i calls test(i). In other words, what is being done in test(i)?
monitor DiningPhilosophers enum THINKING, HUNGRY, EATING) state C5]; condition self [5]; void pickup int i) state Cil HUNGRY tests (i); if (state [i] EATING) self [i] wait(); void putdown (int i) state [i] THINKING test (Ci 4) 5); tests ((i 1) 5); void test (int i) if ((state [(i 4) 5] EATING) && (state [i] HUNGRY) && (state (i 1) 5] EATING)) state [i] EATING self [i] signal(); initialization code for (int i 0; i 5; i++) state[i] THINKING Figure 5.18 A monitor solution to the dining-philosopher problem.Explanation / Answer
Condition variable is queue of threads, associated with a monitor, on which a thread may wait on a condition to become true.
Implementation:
The condition variable data structure contains a double-linked list to use as a queue. It also contains a semaphore to protect operations on this queue. This semaphore should be a spin-lock since it will only be held for very short periods of time.
Example:
struct condition
{
proc next; /* doubly linked list implementation of */
proc prev; /* queue for blocked threads */
mutex mx; /*protects queue */
};
wait() :
The wait() operation adds a thread to the list and then puts it to sleep. The mutex that protects the critical section in the calling function is passed as a parameter to wait(). This allows wait to atomically release the mutex and put the process to sleep.
If this operation is not atomic and a context switch occurs after the release_mutex (mx) and before the thread goes to sleep, it is possible that a process will signal before the process goes to sleep. When the waiting() process is restored to execution, it will enter the sleep queue, but the message to wake it up will be forever gone.
Example:
void wait (condition *cv, mutex *mx)
{
mutex_acquire(&c->listLock); /* protect the queue */
enqueue (&c->next, &c->prev, thr_self()); /* enqueue */
mutex_release (&c->listLock); /* we're done with the list */ /* The suspend and release_mutex() operation should be atomic */
release_mutex (mx);
thr_suspend (self); /* Sleep 'til someone wakes us */
mutex_acquire (mx); /* Woke up -- our turn, get resource lock */
return;
}
signal() :
The signal() operation gets the next thread from the queue and wakes it up. If the queue is empty, it does nothing.
void signal (condition *c)
{
thread_id tid;
mutex_acquire (c->listlock); /* protect the queue */
tid = dequeue(&c->next, &c->prev);
mutex_release (listLock);
if (tid>0) thr_continue (tid);
return;
}
broadcast() :
The broadcast operation wakes up every thread waiting for a particular resource. This generally makes sense only with sharable resources. Perhaps a writer just completed so all of the readers can be awakened.
void broadcast (condition *c)
{
thread_id tid;
mutex_acquire (c->listLock); /* protect the queue */
while (&c->next) /* queue is not empty */
{
tid = dequeue(&c->next, &c->prev); /* wake one */ thr_continue (tid); /* Make it runnable */
}
mutex_release (c->listLock); /* done with the queue */
}
When test(i) is called, based on the value of i the state is changed to one of the enum elements.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.