Solved

Dining philosophers problem - questions...

Posted on 2004-10-13
1
1,141 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
ID: 12311827
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

Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

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 a recent article here at Experts Exchange (http://www.experts-exchange.com/articles/18880/PaperPort-14-in-Windows-10-A-First-Look.html), I discussed my nine-month sandbox testing of the Windows 10 Technical Preview, specifically with respect to r…
This is used to tweak the memory usage for your computer, it is used for servers more so than workstations but just be careful editing registry settings as it may cause irreversible results. I hold no responsibility for anything you do to the regist…
Hi friends,  in this video  I'll show you how new windows 10 user can learn the using of windows 10. Thank you.

776 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