Dining Philosopher Problem | Process Synchronisation | Operating System | Teachers Assessment PPT

This presentation dives into the Dining Philosopher Problem, a classic synchronization issue in Operating Systems, commonly used to illustrate the challenges of resource allocation, deadlock, and starvation in concurrent processing. As part of the Teacher's Assessment at Ramdeobaba College of Engineering and Management, Nagpur, this PPT was prepared by a B.Tech (Artificial Intelligence and Data Science) student.

The slides include:

Clear explanation of the problem and its real-world relevance

Visual diagrams for better conceptual understanding

Pseudocode and logic implementation

Techniques to prevent deadlock and starvation

Perfect for Computer Science and Engineering students, educators, and tech enthusiasts who want a simplified yet insightful overview of process synchronization concepts.

1. Dining Philosophers Problem Unit : Process Synchronization Course: Operating Systems Group Members: 1 Roll No Name 26 Ansh Zade 27 Madhura Dehare 28 Manish Pande 29 Yug Khandelwal 30 Shantanu Gaddewar

2. Dining Philosophers Problem The Dining Philosophers Problem is a classic synchronization and concurrency problem that deals with resource sharing, deadlock, and starvation in systems where multiple processes require limited resources. The problem involves ‘n’ philosophers sitting around a circular table, alternating between thinking and eating. To eat, a philosopher needs two chopsticks, one on their left and one on their right. However, the number of chopsticks equals the number of philosophers, and each chopstick is shared between two neighboring philosophers. The standard problem considers the value of ‘n’ as 5.

3. Conditions: 1 Two Forks Needed Every Philosopher needs two forks to eat. 2 One Fork at a Time Every Philosopher may pick up the forks on the left or right but only one fork at once. 3 Eating Protocol Philosophers only eat when they have two forks. Design a protocol that ensures a philosopher only eats if he or she has two forks.

4. Correctness Properties Mutual Exclusion No two Philosophers can have the two forks simultaneously. Deadlock Prevention Each philosopher can get the chance to eat in a certain finite time. Free from Starvation When few Philosophers are waiting then one gets a chance to eat in a while.

5. A semaphore is a synchronization mechanism used to control access to shared resources in concurrent processes. It operates with two atomic actions: wait() (P operation) – Decreases the semaphore value; if it's zero, the process waits. signal() (V operation) – Increases the semaphore value, allowing waiting processes to proceed. Types: Binary Semaphore (0 or 1, like a mutex) Counting Semaphore (allows multiple accesses) Semaphores help in process synchronization , mutual exclusion , and deadlock prevention . S emaphores

6. Solution Using Binary Semaphores Forks as Semaphores: Each fork is represented as a semaphore initialized to 1 (available). Philosophers as Threads: Each philosopher tries to pick up two semaphores (forks) before eating. Implementation Steps: Wait (P operation) before picking up a fork. Eat when both forks are acquired. Signal (V operation) after finishing to release the forks.

7. Semaphore mutex = 1 // Binary semaphore for mutual exclusion int solution = 0 // Shared variable Process P: repeat: wait(mutex) // Acquire the lock solution = solution + 1 signal(mutex) // Release the lock until (condition met) Process Q: repeat: wait(mutex) // Acquire the lock solution = solution + 1 signal(mutex) // Release the lock until (condition met)

8. Pseudocode for Dining Philosophers Problem (Using Semaphores): Semaphore fork[5] = {1, 1, 1, ..., 1} // One semaphore for each fork Semaphore mutex = 1 // Binary semaphore for critical section Process Philosopher[ i ]: repeat: think() // Philosopher is thinking wait(mutex) // Ensure mutual exclusion while picking up forks Do { wait(fork[ i ]) // Pick left fork wait(fork[(i+1) % 5]) // Pick right fork signal(mutex) // Release the lock eat() // Philosopher is eating signal(fork[ i ]) // Put down left fork signal(fork[(i+1) % 5]) // Put down right fork } while(TRUE)

9. Deadlock Prevention: Semaphores only ensures that no two neighbours are eating simultaneously. This solution may cause deadlock , where all philosophers pick up their left fork and wait forever for the right fork. Solution: Implement a strategy like: Use an asymmetric approach (odd-indexed philosophers pick the right fork first, even-indexed pick the left fork first). Use a waiter (central authority) to ensure at most N-1 philosophers can eat at the same time. Means Allow only 4 philosphers to eat at same time

10. Dining Philosophers Problem Using Monitors Monitors are a high-level synchronization mechanism that helps manage concurrent processes by encapsulating shared variables, procedures, and condition variables. Monitors provide a structured approach that ensures: ✅ Automatic mutual exclusion (Only one philosopher can execute a monitor function at a time). ✅ Condition variables to handle waiting and signaling. ✅ Simpler, safer synchronization compared to semaphores .

11. Explanation of Monitor Solution: Each philosopher has three states : THINKING : Not hungry, doesn't need forks. HUNGRY : Wants to eat but must wait for forks. EATING : Holding both forks and eating. Monitor Ensures Mutual Exclusion Only one philosopher at a time can execute pickup() or putdown() safely. No explicit mutex is needed since monitors automatically prevent race conditions . Condition Variables for Waiting If a philosopher is HUNGRY but cannot get both forks, they wait ( wait(self[ i ]) ). Once forks are available, they are signaled ( signal(self[ i ]) ). Deadlock Prevention A philosopher only eats if neither of their neighbors are eating . This ensures no circular waiting and avoids deadlocks .

12. enum { THINKING, HUNGRY, EATING } state[5] condition self[5] // Condition variables for each philosopher Procedure pickup(int i ): state[ i ] = HUNGRY // Philosopher wants to eat test( i ) ; // Try to acquire both forks if (state[ i ] != EATING): wait(self[ i ]) // Wait if forks are not available void putdown(int i ): state[ i ] = THINKING // Philosopher is done eating test(( i + N - 1) % N) // Test left neighbor test(( i + 1) % N) // Test right neighbor void test(int i ): if (state[ i ] == HUNGRY && state[( i + N - 1) % N] != EATING && //Checking if right and left are eating state[( i + 1) % N] != EATING): state[ i ] = EATING signal(self[ i ]); // Wake up the waiting philosopher Ex. Philospher can delay himself if hungry but unable to obtain forks. Procedure dine(int i ): repeat: think() pickup( i ) eat() putdown( i ) until (done)

13. Feature Semaphores Monitors Complexity Harder (manual synchronization) Easier (built-in handling) Deadlock Possibility Possible (needs extra logic) Avoided by monitor rules Starvation Possible (if not handled properly) Less likely (fair scheduling) Ease of Use Requires careful handling More structured and safer Automatic Mutual Exclusion No (needs manual mutex) Yes (handled by the monitor)

14. Conclusion: Which One is Better : Use Monitors whenever possible for their simplicity and safety . They prevent deadlocks and make concurrency easier to manage . Use Semaphores if you need low-level control over resource access and can carefully handle synchronization manually .

15. Conclusion The Dining Philosopher Problem teaches us how to handle shared resources in a system while avoiding issues like deadlock and starvation. It highlights challenges like deadlock and starvation and teaches how to prevent them using proper synchronization techniques. The problem is a classic example used to study synchronization and resource allocation in concurrent systems.

16. Questions Session