?
Solved

Dining philosophers problem - questions...

Posted on 2004-10-13
1
Medium Priority
?
1,150 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
1 Comment
 
LVL 1

Accepted Solution

by:
jaguarul earned 300 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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

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…
Windows 10 is here and for most admins this means frustration and challenges getting that first working Windows 10 image. As in my previous sysprep articles, I've put together a simple help guide to get you through this process. The aim is to achiev…
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.

762 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