Solved

Dining Philosophers problem - easy questions

Posted on 2004-10-13
7
438 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
7 Comments
 
LVL 1

Expert Comment

by:Feldspar
ID: 12304083
The issues that are generally present in multiprogramming systems like this are:
- Deadlock: it wont get to a state where some threads can never run because they are waiting on each other.
- Starvation: a thread doesnt get blocked 'forever' becaue other threads always have the resources it needs
- Fairness: threads get blocked evenly, and no thread is 'favored' over others.  
And like everything, there is also ease of implementation, memory required, overhead, speed, etc.

this page might give you a good guide
http://www.cs.ucsb.edu/~cs170/notes/dphil/
0
 

Author Comment

by:killer455
ID: 12304627
This is more of a general answer, could be be more specific to my question regarding those algorithms rather than general info.
0
 
LVL 84

Accepted Solution

by:
ozo earned 30 total points
ID: 12305123
Algorithm 1 suffers from deadlock.
Algorithm 3 can suffer from starvation.
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 

Author Comment

by:killer455
ID: 12305325
What about algorithm 2?
0
 
LVL 1

Assisted Solution

by:Mistobaan
Mistobaan earned 20 total points
ID: 12306143
Alghoritm 2 is the same as 1
it suffers deadlock, Starvation and fairness.
It depends also on how the stick are released.
0
 
LVL 84

Expert Comment

by:ozo
ID: 12315807
Algorithm 2 does not suffer deadlock
0
 
LVL 2

Expert Comment

by:mtcmedia
ID: 12691147
Algorithm 2 looks like the good one to me :)
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
A short article about a problem I had getting the GPS LocationListener working.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

757 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

24 Experts available now in Live!

Get 1:1 Help Now