Thank You Object-Oriented and Concurrent Programming The dining philosopher\'s p
ID: 3666832 • Letter: T
Question
Thank You
Object-Oriented and Concurrent Programming The dining philosopher's problem was invented by E. W. Dijkstra, a concurrency pioneer, to clarify the notions of deadlock and starvation freedom. Imagine five philosophers who spend their lives just thinking and feasting. They sit around a circular table with five chairs. The table has a big plate of rice. However, there are only five chopsticks (in the original formulation forks) available, as shown in Fig. 1.5. Each philosopher thinks. When he gets hungry, he sits down and picks up the two chopsticks that are closest to him. If a philosopher can pick up both chopsticks, he can eat for a while. After a philosopher finishes eating, he puts down the chopsticks and again starts to think. What is wrong with everybody doing the following-other than that the philosophers never get up from the table? think for a while get left chopstick get right chopstick eat for a while return left chopstick return right chopstick return to 1 How can the above be fixed to avoid deadlocks? Is your solution starvation free? Literally! please don't just copy something off the internet and answer the question. This has to be in your own words and not a long rambling from a website or documentation. (The teacher also has access to the internet sites you're copying from) Please no handwritten documents as answers to question I am having a hard time reading handwritten documents.Explanation / Answer
DINING PHILOSOPHERS PROBLEM
IN the dining philosophers problem as mention,
It is just a case of ,each philosopher is implemented as a thread and each chopstick is a shared resource in the concurrent system
There are several possible viable solutions that solve both the issue of deadlock and ensure liveness, four of which are presented here:
Philosophers do not eat rice using chopsticks, but one fork and one spoon. Also you need to consider that at least one Philosopher needs to talk an the rest listen. In the original problem, they just either eat or think, they do not talk, that's not a very funny meal. Well maybe it is, because it must take ages to eat spaghetti with chopsticks.
The intuitive approach to solving this problem is to have each philosopher first pick up his left chopstick then his right. However, this will lead to deadlock as all four of the necessary and sufficient conditions for deadlock come into play: blocking shared resources (chopsticks), no pre-emption (one philosopher cannot ask his adjacents to drop their chopsticks), holding while acquiring (a philosopher holds his left chopstick before trying to pick up his right) and circular waiting (each philosopher shares chopsticks).But we should be able to prevent the deadlock by breaking any one of the conditions as mention.
DeadLock can only occur when threads try to grab several resources at once. Perhaps we should collect a list of "real" programming problems that riskDeadLock.
An obvious way around this is that philosophers who can't get both chopsticks should put them down, go back to thinking and try again later. This is trying to break the third deadlock property above: 'holding while acquiring'. However, if the philosophers are unlucky and keep doing this all in synchrony, none of them will actually get to eat! Each will drop a chopstick only to try and grab it once more. This solution breaks the problem of deadlock but in doing so, we have introduced another potential problem - that of livelock. The philosophers will not grind to a halt but instead can just go round in circles trying to decide who should have the chopsticks but never getting anywhere. The philosophers won't eat and will starve (quite literally!). This solution isn't much good either.
chopsticks can only be used in pairs. Thus, the solution is to simply let philosophers only take two chopsticks at a time— and we are done! Concretely, put all n philosophers in a queue P, and all n chopsticks in a separate queue C (a stack would work just as well). While C contains at least two chopsticks, the philosopher at the top of P takes two chopsticks from C and eats, and so on.
It should be obvious why this approach works. If not: The philosopher at the top of P takes two chopsticks from C, and starts eating. When he is done (feel free to have him eat until he receives a request to release his chopsticks; it does not matter), he adds both chopsticks to C again. Continue until all chopsticks have been distributed. If there are no two chopsticks available, the remaining philosophers wait for their turn. Thus, the first philosopher takes two chopsticks, and eats. Then the second philosopher takes the next two chopsticks, and eats. The third philosopher would only get one chopstick, for the time being, so he waits. Eventually, though, the first philosopher will be done eating, and subsequently put his two chopsticks back to C. Because you always take two chopsticks from C, and philosophers only eat for a finite amount of time, there is neither deadlock nor starvation.
Lastly, note that there is no need to have exactly five philosophers. Presumably, this number is only used due to the historical accident of Dijkstra using that particular number. You need at least two. Some of the solutions we have seen have an administrative overhead, so it will only get more cumbersome the more philosophers we add to the table. However, by using a queue, you could feed an arbitrarily large number of philosophers without any overhead. Also note that whenever there is an odd number of chopsticks, there is one superfluous chopstick, since you cannot properly eat rice with just one chopstick. Thus, there are at least three aspects in the original problem statement that obscure the problem: the number 5, the strange convention of using two forks, and the fact that the fifth fork is superfluous. Lastly, calling the diners philosophers is potentially distracting.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.