Consider the following Philosopher process for the Dining Philosopher’s problem.

Question

Consider the following Philosopher process for the Dining Philosopher’s problem. If all of our philosophers, concurrently execute as indicated, what problem(s) might arise? Clearly describe a scenario where the problem does arise. Describe two solutions to the problem.

Global semaphore chopsticks[5] // all intialized to 1;

Do {

Wait(chopsticks[i]); //get left chopstick

Wait(chopsticks[ (i+1)%5] );   // get right chopstick

// Critical section eating….

Signal(chopsticks[i]);   // release left chopstick

Signal(chopsticks[ (i+1)%5]);   // release right chopstick

//think non-Critical section

} while (TRUE);

Explanation / Answer

SOlution1 : Arbitrator solution -->reducing parallelism

The philosopher can pick two forks by introducing an arbitrator (waiter in hotel).
To pick the fork he need to take waiters permission.
Waiter gives permisson to only one philosopher at a time
Philosopher can place fork anytime
If philosopher is eating and other one requesting forks,all others must wait till request get
has been fulfilled.

Solution 2 : PArtial Order Solution

It assigns partial forks to resources
All forks will be requested in order, and that no two forks
unrelated by order will ever be used by a single unit of work at the same time
Philosopher will always pick up the lower-numbered fork first,
and then the higher-numbered fork, from among the two forks they plan to use.
This process avoids deadlocks.
It is not always practical,
when the list of required resources is not completely known in advance

template <class L0>
void
lock(L0& l0, L0& l5)
{
if (l0.mutex() < l1.mutex())
{
std::unique_lock<L0> u0(l0);
l1.lock();
u0.release();
}
else
{
std::unique_lock<L0> u1(l5);
l0.lock();
u1.release();
}
}

3) smart Solution

A simple variation of the persistent algorithm is when a try_lock() fails, then block on that mutex.
This eliminates a lot of useless spinning, thus consuming less power, and thus leaving more processing power available to other diners.
The diner needs not only forks to eat, he also needs an available processor. If you don't have the forks, don't waste power.

This is simple to code for the two-mutex variant as:

template <class L0, class L5>
void
lock(L0& l0, L5& l5)
{
while (true)
{
{
std::unique_lock<L0> u0(l0);
if (l1.try_lock())
{
u0.release();
break;
}
}
{
std::unique_lock<L1> u1(l5);
if (l0.try_lock())
{
u1.release();
break;
}
}
}
}

Hope this might help ,

Happy Chegging

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.