Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Dining philosophers problem - questions...

Posted on 2004-10-13
Medium Priority
1,155 Views
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
Question by:killer455
1 Comment

LVL 1

Accepted Solution

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

Question has a verified solution.

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

As the title indicates, I have done this before. It chills me everytime I update the OS on my phone, (http://www.experts-exchange.com/articles/18084/Upgrading-to-Android-5-0-Lollipop.html) because one time I did this and I essentially had a bricked …
Windows 7 does not have the best desktop search built in. This is something Windows 7 users have struggled with. You type something in, and your search results don’t always match what you are looking for, or it doesn’t actually work at all. There ar…
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.
###### Suggested Courses
Course of the Month13 days, left to enroll