Question

Question: The dining philosopher’s problem is a classic problem of synchronization and concurrency. The general problem is stated as philosophers sitting at a round table doing one of two things: eating or thinking. When they are eating, they are not thinking, and when they are thinking, they are not eating. There is a bowl of pasta in the center. A fork is placed in between each philosopher. The result is that each philosopher has one fork to her left and one fork to her right. Given the nature of eating pasta, the philosopher needs two forks to eat, and can only use the forks on her immediate left and right. The philosophers do not speak to one another.

6.8.1 [10] Describe the scenario where none of the philosophers ever eats (i.e., starvation). What is the sequence of events that happen that lead up to this problem?

6.8.2 [10] how we can solve this problem by introducing the concept of a priority? But can we guarantee that we will treat all the philosophers fairly? Explain.

6.8.3 [10] We can implement requests to the waiter as either a queue of requests or as a periodic retry of a request. With a queue, requests are handled in the order they are received. The problem with using the queue is that we may not always be able to service the philosopher whose request is at the head of the queue (due to the unavailability of resources). Describe a scenario with 5 philosophers where a queue is provided, but service is not granted even though there are forks available for another philosopher (whose request is deeper in the queue) to eat.

6.8.4 [10]If we implement requests to the waiter by periodically repeating our request until the resources become available, will this solve the problem described in Exercise 6.8.3? Explain.

Short answer

1. Starvation can occur if forks are not available for the philosophers.

2. We can solve starvation problem by using a priority queue, but we cannot guarantee fairness because the assignment of forks depend on the priority.

3. Even if priority queue is implemented and the philosopher is at the head queue, sometimes we cannot provide forks because the adjacent philosophers may not have the forks available.

4. Even if they send requests periodically, this will not completely solve the problem.

Step-by-step solution

Dining philosopher problem.

Dining philosopher problem is one of the most important situations for explaining synchronization. The problem is that there are a set of philosophers who are sitting around a circular table. A fork is placed between every philosopher. The philosophers can think or eat, but they can do only one thing one time. Each philosopher requires two forks to eat. This is a classical problem of synchronization. There are three states of the philosophers—dining, eating, and hungry. The dining philosopher problem can also be explained in terms of the processors and process. Consider a process is assigned to the processor that needs two access which is read and write (in the case of the Dining philosopher problem the access are forks). Processors have only two options that can run the process or remain idle. The processor cannot communicate with each other according to dining philosopher problem.

(6.8.1)

Starvation problem.

Starvation is a state of the problem in dining philosophers problem where the philosophers are stuck in thinking and in the state of hunger for a long time. There are many algorithms to prevent starvation, it is important to prevent starvation in the CPU. Some of the situations that can lead to starvation are as below:

Consider each philosopher took the right-side fork simultaneously, and there is no fork left on the left side of each philosopher around the table. So, none of the philosophers can complete their tasks which leads to starvation. The other situation can be that each philosopher takes the left side simultaneously and there is no fork left to the right side. As a result, none of the philosophers have another fork for comparing the task and it finally leads to starvation.

(6.8.2)

Introducing priority.

The basic problem in the dining philosopher problem is starvation. If a philosopher picks the left fork and waits for the right fork, then it may lead to starvation. The philosopher can only eat if both the forks are free and accessible. If the philosopher completes eating, then the philosopher will check both sides if any other philosopher needs the forks and release them according to the necessity. If the other philosopher who is adjacent needs the fork, then the philosopher who took two forks will release them after they complete their task. The difficulty is to find forks that are free and check whether the philosopher is interrupting the other philosophers when they are on the task. We can solve this problem by implementing a priority queue. The requests for the fork should be accepted in the centralized queue with priority. The priority is defined by the closet to the head of the queue. This helps prevent deadlock starvation. The philosophers are treated according to their priority and the availability of the forks surrounding them.

(6.8.3)

Implementing the request periodically.

In the dining philosopher problem, if we implement requests to the waiters repeatedly until the forks are provided, It may partially solve the problem. By requesting periodically it may increase the priority of the request but not solve the problem. If requests are made periodically we need to make sure that the philosopher must eat the same amount of time. The line that the philosophers should eat the same amount of time is similar to the processor having only a certain amount of time to access the data. After a certain amount of time, the processor cannot access the data. In the dining philosopher problem after a certain amount of time the philosopher cannot access the food and should release the forks allocated to him. If the philosopher needs forks again, they can request again and a request is added to the queue. When the philosopher is eating and this time can be used to schedule the issuance of the repeated request.