diningphilosopherproblemoperatingsystem.pptx

The Dining Philosophers Problem is a classic synchronization and concurrency problem used to illustrate the difficulties of resource sharing and the potential for deadlock and starvation in concurrent computing systems. It was formulated by the computer scientist Edsger Dijkstra in 1965.

Problem Description:
The problem involves five philosophers sitting at a round table. Each philosopher thinks deeply and occasionally gets hungry. Between each pair of philosophers, there is a single fork. To eat, a philosopher must use two forks — one from their left side and one from their right side. Since the forks are shared between adjacent philosophers, the problem arises of how to ensure that the philosophers can all eat without causing conflicts, deadlocks, or starvation.

Key Points:
Philosophers: There are typically 5 philosophers, each alternating between thinking and eating.
Forks: There are 5 forks, placed between the philosophers. A philosopher needs two forks to eat: one on their left side and one on their right side.
Thinking and Eating: Philosophers spend most of their time thinking. When they are hungry, they try to pick up the two forks (one on each side) to eat. Once they have eaten, they put down the forks and resume thinking.
Concurrency Issue: Philosophers cannot eat at the same time if they do not have both forks. Additionally, the shared resources (forks) must be managed carefully to avoid deadlock (where no philosopher can eat) and starvation (where a philosopher is perpetually unable to eat).
Potential Problems:
Deadlock: If every philosopher picks up the fork on their left simultaneously, they will all be waiting for the fork on their right, resulting in a deadlock where no one can eat.

Starvation: If a philosopher is never able to acquire both forks (e.g., because neighboring philosophers keep taking them), that philosopher may starve, even though others are eating.

Solutions:
To solve the problem, several strategies are used to avoid deadlock and starvation. Some common approaches include:

Resource Hierarchy Solution: Philosophers pick up the left fork first, then the right fork. If the right fork is not available, the philosopher puts down the left fork and tries again later. This reduces the chance of deadlock.

Chandy/Misra Solution: This is a solution that uses a system of "tokens" to ensure no philosopher can hold onto a fork indefinitely. Philosophers must request permission before picking up forks, and once done eating, they release the forks back into a shared pool.

Arbitrator Solution: An external entity (called the "arbitrator") controls access to the forks. Philosophers must ask the arbitrator for permission to pick up both forks, and the arbitrator ensures that only one philosopher can use each fork at a time, thus avoiding deadlock.

Semaphore or Mutex-Based Solutions: Semaphores or mutexes can be used to manage access to the forks, ensuring that only one philosopher can access a fork at a time and that no deadlock

1. DAVANGERE UNIVERSITY GUIDED BY – Mr ANUP RITTI THE DINING PHILOSOPHERS PROBLEM

2. What is Dining Philosophers Problem? The dining philosophers problem is a classic synchronization problem. It is used to evaluate situations where there is a need of allocating multiple resources to multiple processes.

3. What is Dining Philosophers Problem? Demonstrates a large class of concurrency control problems. It was designed to illustrate challenges of avoiding deadlock. It was originally formulated by Edsger Dijkstra in 1965. Later, Tony Hoare gave the problem its present formulation.

4. Need of Dining Philosopher Problem It is a simple representation of the need to allocate several resources among several processes. It represents a deadlock-free system. It ensures a starvation-free structure.

5. The Problem Statement Consider five philosophers who spend their lives thinking and eating. The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher. In the center of the table is a bowl of rice, and the table is laid with five single chopsticks.

6. The Problem Statement When a philosopher thinks, he does not interact with her colleagues. From time to time, a philosopher gets hungry. He tries to pick up the two chopsticks that are closest to him, i.e. the chopsticks that are between him and his left and right neighbors.

7. The Problem Statement A philosopher may pick up only one chopstick at a time. He cannot pick up a chopstick that is already in the hand of a neighbor. When a hungry philosopher has both his chopsticks at the same time, he eats without releasing his chopsticks. When he is finished eating, he puts down both of his chopsticks and starts thinking again.

8. Lets understand the problem with a code…... Let's use the given figure as a reference to understand the problem exactly. The five Philosophers are represented as P0, P1, P2, P3, and P4 and five chopsticks by C0, C1, C2, C3, and C4.

9. Lets understand the problem with a code…... Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[(i+1) % 5] ; ... // EAT ... put_chopstick[i]; put_chopstick[(i+1) % 5] ; … // THINKING .. } }

10. Lets understand the problem with a code…... Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute take_chopstick[i] by doing this it holds C0 chopstick after that it execute take_chopstick[(i+1) % 5] by doing this it holds C1 chopstick ( since i =0, therefore (0 + 1) % 5 = 1) Similarly suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute take_chopstick(i) by doing this it holds C1 chopstick after that it execute take_chopstick[(i+1) % 5] by doing this it holds C2 chopstick ( since i =1, therefore (1 + 1) % 5 = 2) But Practically Chopstick C1 is not available as it has already been taken by philosopher P0, hence the above code generates problems and produces race condition.

11. The solution of the Dining Philosophers Problem We use a semaphore to represent a chopstick and this truly acts as a solution of the Dining Philosophers Problem. Wait and Signal operations will be used for the solution of the Dining Philosophers Problem, for picking a chopstick wait operation can be executed while for releasing a chopstick signal semaphore can be executed. Semaphore: A semaphore S is an integer variable, that apart from initialization is accessed by only two standard atomic operations - wait and signal. Semaphore is simply a variable that is non-negative and shared between threads. A semaphore is a signaling mechanism, and a thread that is waiting on a semaphore can be signaled by another thread. It uses two atomic operations, 1)wait, and 2) signal for the process synchronization.

12. The definition of wait() is as follows: wait(S) { while S <= 0 ; // no-op S--; } The definition of signal() is as follows: signal(S) { S++; } Semaphores All modifications to the integer value of the semaphore in the wait() and signal() operations must be executed indivisibly. That is, when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value. In case of wait(S), the testing of the integer value of S (S ≤ 0), as well as its possible modification (S--), must be executed without interruption.

13. The solution of the Dining Philosophers Problem The structure of the chopstick is an array of a semaphore which is represented as shown below - semaphore chopstick[5] Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.

14. Solution of Dining Philosopher Problem void Philosopher { while(1) { wait( take_chopstickC[i]); wait( take_chopstickC[(i+1) % 5] ) ; . . EATING THE NOODLE . . . signal( put_chopstickC[i] ); Signal( put_chopstickC[(i+1) % 5]) ; . . . THINKING } }

15. Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute wait( take_chopstickC[i] ). By doing this it holds C0 chopstick and reduces semaphore C0 to 0 . After that it execute wait( take_chopstickC[(i+1) % 5] ) . By doing this it holds C1 chopstick ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0. Solution of Dining Philosopher Problem

16. Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute wait( take_chopstickC[i] ). By doing this it will try to hold C1 chopstick but will not be able to do that , since the value of semaphore C1 has already been set to 0 by philosopher P0. Therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1. Solution of Dining Philosopher Problem

17. Whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute wait( take_chopstickC[i] ); by doing this it holds C2 chopstick and reduces semaphore C2 to 0. After that, it executes wait( take_chopstickC[(i+1) % 5] ); by doing this it holds C3 chopstick ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0. Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher P0 and P2, P1 and P3 & P2 and P4 can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem) Solution of Dining Philosopher Problem

18. Drawbacks of Dining Philosopher Problem From the above solution of the dining philosopher problem, we can figure out that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time. It will lead to the condition of deadlock and none of the philosophers can eat. This will result in a condition of starvation.

19. Possible Solutions To avoid deadlock, some of the solutions are as follows - Maximum number of philosophers on the table should not be more than four. in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat. A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.

20. Possible Solutions Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.

21. Conclusion The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows: The philosopher is instructed to think till the left fork is available, when it is available, hold it. The philosopher is instructed to think till the right fork is available, when it is available, hold it. The philosopher is instructed to eat when both forks are available. then, put the right fork down first then, put the left fork down next repeat from the beginning.

22. THANK YOU