Dining Philosophers Problem and Solutions

Introduction

• Topic: Dining Philosophers Problem (synchronization problem)
• Objective: Understand the problem and solve using semaphores

Understanding the Dining Philosophers Problem

• Scenario: Round dining table with 5 philosophers
  • Philosophers can be in two states: thinking or eating
  • Philosophers alternate between thinking and eating

Dining Rules

• Food (rice/noodles) in front of each philosopher
• Need two forks or chopsticks to eat (one from left and one from right)
  • Can't eat with just one fork
  • Forks are shared between neighboring philosophers

Problem Statement

• Limited resources: 5 philosophers but only 5 forks
  • Adjacent philosophers cannot eat simultaneously
  • Critical problem: Avoid two neighboring philosophers from accessing the same fork simultaneously

Philosophers' Actions

• Thinking: No interaction with others, just thinking
• Eating: Needs to pick up 2 forks; can pick up one fork at a time
• Fork Usage: Cannot pick up a fork already held by another
• After Eating: Puts down forks and resumes thinking

Real-World Relevance

• Analogy: Philosophers = Processes, Forks = Resources
• Operating Systems: Represents the challenge of resource allocation
  • Limited resources shared among processes without conflict

Solving the Problem with Semaphores

Semaphore Basics

• Represent each fork with a semaphore (binary semaphore)
• Wait Operation: Philosopher tries to take a fork
• Signal Operation: Philosopher releases a fork

Implementation Steps

• Array of Semaphores: chopstick[5] initialized to 1
  • Semaphore value 1: Fork is free
  • Semaphore value 0: Fork is in use

Pseudocode for Philosopher

• wait(chopstick[i]) and wait(chopstick[(i+1) % 5]) to pick up forks
  • (i+1) % 5: Handle circular arrangement, especially for the last philosopher
• Eat, then signal(chopstick[i]) and signal(chopstick[(i+1) % 5]) to release forks
• Issue: Guarantees no two neighbors eat simultaneously, but can lead to deadlock

Deadlock Scenario

• Problem: All 5 philosophers become hungry simultaneously and each grabs their left fork
  • Each philosopher stuck waiting for their right fork, leading to deadlock

Avoiding Deadlock

1. At Most Four Philosophers: Allow only four philosophers at the table simultaneously
2. Critical Section for Both Forks: Only pick up forks if both are available
3. Asymmetric Solution:

• Odd philosopher (1, 3, 5): pick left fork first, then right fork
• Even philosopher (2, 4): pick right fork first, then left fork

Conclusion

• Solving with semaphores partially solves the problem by ensuring no two neighbors eat simultaneously
• Additional remedies are necessary to avoid deadlock
• Important classic problem in synchronization related to resource allocation in operating systems

End of Lecture