Solved

Dining philosophers problem - questions...

Posted on 2004-10-13
1
1,140 Views
Last Modified: 2012-08-14
Could anyone tell me what the pros and cons of the following three solutions to the dining
philosophers problem are?

Algorithm 1:
Wait for left stick to be free.
Pick up left stick.
Wait for right stick to be free.
Pick up right stick.

Algorithm 2:
All philosophers run Algorithm 1,
except philosopher number 5 who runs:

Wait for right stick to be free.
Pick up right stick.
Wait for left stick to be free.
Pick up left stick.

Algorithm 3: Wait for both sticks to be free.
Pick up both sticks (as an atomic operation)
0
Comment
Question by:killer455
1 Comment
 
LVL 1

Accepted Solution

by:
jaguarul earned 75 total points
Comment Utility
These answers depend on your assumptions about the scheduler and the medium, but here are the most usual observations

Algorithm one will clearly deadlock: suppose each process (philosopher) is run in turn, and preempted right after it picks up the left stick. Then each philosopher will have on stick and wait for the other, but noone will free what it already holds. So Algorithm one is incorrect (it blocks).

Algorithm two works as expected, but it is asymetrical, so you have to have a different algorithm running on a special process. If you consider this "the leader" of the group, and you would like to transform it into a symetric solution, you are stuck with the "leader election problem", which reduces to the consensus problem, which is unsolvable (The famous FLP impossibility result). If you need all the details I can expand here.

Algorithm three works, is correct, and symetric, so it's probabily the best solution (considering you can solve the needed atomic operation).
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Just about everyone has an old PC laying around.  Ask anyone in the IT industry, whether they are a professional or play in it as a hobby.  From outdated Desktops to cheap "throwaway" laptops, they are all around and not as hard to "fix up" as you m…
In this article we will discuss all things related to StageFright bug, the most vulnerable bug of android devices.
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This tutorial demonstrates a quick way of adding group price to multiple Magento products.

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now