Solving Dining Philosophers

Welcome to another chapter in your concurrency journey! This lesson covers the fascinating dining philosophers problem, a classic concurrency illustration. In our previous lesson, we tackled the producer-consumer problem, managing concurrent access to shared resources. Now, we'll focus on handling multiple goroutines competing for resources in a circular arrangement. This lesson builds upon previous concepts and enhances your ability to prevent deadlocks in complex systems.

In this lesson, you will understand and solve the dining philosophers problem and learn how to prevent deadlocks in concurrent applications using goroutines.

Let's break down the key concepts you'll explore:

1. Dining philosophers problem: Understand the problem statement and its real-world implications.
2. Deadlocks: Learn about deadlocks and how they occur in concurrent applications.
3. Solving deadlocks: Explore strategies to prevent deadlocks and ensure system stability.

Imagine a group of philosophers sitting around a circular table, each with a plate of spaghetti and a fork between them. The philosophers alternate between thinking and eating, using two forks to consume their meal. However, there's a catch: the philosophers can only eat when they have both forks. This constraint leads to a potential deadlock scenario if each philosopher picks up one fork and waits indefinitely for the other.

The dining philosophers problem is a classic synchronization problem that illustrates the challenges of resource allocation and deadlock prevention in concurrent systems. It highlights the need for careful resource allocation and synchronization to avoid deadlocks and ensure system stability.

Let's simulate the dining philosophers problem and explore strategies to prevent deadlocks in concurrent applications using Go:

type Philosopher struct {
    id        int
    leftFork  *sync.Mutex
    rightFork *sync.Mutex
}

func (p *Philosopher) dine(wg *sync.WaitGroup) {
    defer wg.Done()
    
    for i := 0; i < 10; i++ {
        p.think()
        p.eat()
    }
}

func (p *Philosopher) think() {
    time.Sleep(100 * time.Millisecond)
}

func (p *Philosopher) eat() {
    // Prevent deadlock by acquiring locks in a consistent order
    // Always lock the fork with the lower memory address first
    first, second := p.leftFork, p.rightFork
    if uintptr(unsafe.Pointer(p.leftFork)) > uintptr(unsafe.Pointer(p.rightFork)) {
        first, second = p.rightFork, p.leftFork
    }
    
    first.Lock()
    second.Lock()
    
    fmt.Printf("Philosopher %d is eating.\n", p.id)
    time.Sleep(100 * time.Millisecond)
    
    fmt.Printf("Philosopher %d finished eating. Thinking...\n", p.id)
    
    second.Unlock()
    first.Unlock()
}

Let's understand the code snippet above:

• The Philosopher struct represents a philosopher goroutine that thinks and eats.
• The dine method simulates the philosopher's routine of thinking and eating and uses defer wg.Done() to signal completion to the sync.WaitGroup.
• The think method pauses the philosopher for a while to simulate thinking using time.Sleep.
• The eat method acquires locks on both forks in a consistent order to prevent deadlocks.
  • We determine which fork to lock first by comparing memory addresses using uintptr(unsafe.Pointer()), ensuring all philosophers acquire locks in the same global order.
  • This ordering strategy prevents circular wait conditions, eliminating the possibility of deadlock.
  • After acquiring both locks with first.Lock() and second.Lock(), the philosopher eats and then releases both forks in reverse order with second.Unlock() and first.Unlock().
  • Note that fmt.Println and fmt.Printf are goroutine-safe, so we don't need additional synchronization for output.

The code snippet above illustrates how a philosopher acquires locks on two forks by establishing a consistent ordering. This prevents the circular dependency that causes deadlocks. The philosophical journey of thinking and eating is safeguarded by acquiring these locks wisely.