Solved

Dining Philosophers problem - easy questions

Posted on 2004-10-13
7
441 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
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.

 

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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
This is about my first experience with programming Arduino.
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 …

820 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