The Elegant Solution

In the previous articles, we explored the deadlock problem and the waiter solution. Now we’ll see the most elegant solution: the Asymmetric Solution, also known as Resource Ordering.

The Key Insight: Deadlock requires circular wait. Break the circle, prevent the deadlock.

The Asymmetric Solution Explained

Instead of all philosophers picking up forks in the same order (left then right), we make ONE philosopher do the opposite:

Philosophers 0-3: Pick up left fork first, then right fork
Philosopher 4: Pick up right fork first, then left fork

This simple change breaks the circular dependency and prevents deadlock!

Why It Works

The Original Circular Wait (Deadlock)

P0: holds F0, wants F1
P1: holds F1, wants F2
P2: holds F2, wants F3
P3: holds F3, wants F4
P4: holds F4, wants F0  ← Creates the cycle!

With Asymmetric Ordering (No Deadlock)

P0: holds F0, wants F1
P1: holds F1, wants F2
P2: holds F2, wants F3
P3: holds F3, wants F4
P4: wants F0 first (not holding F4 yet)  ← No cycle!

Philosopher 4 can’t complete the cycle because they don’t grab F4 until they have F0.

Real-World Applications

This pattern is fundamental in systems programming:

Lock ordering in databases (always lock tables in ID order)
Mutex hierarchies in operating systems
Account transfers (always lock account with lower ID first)
Distributed transactions (order operations by resource ID)
Graph algorithms (topological ordering prevents cycles)

Implementation

package main

import (
	"fmt"
	"sync"
	"time"
)

// Fork represents a dining fork
type Fork struct {
	id int
	sync.Mutex
}

// Philosopher represents a dining philosopher
type Philosopher struct {
	id                  int
	leftFork, rightFork *Fork
	eatenCount          int
	asymmetric          bool // True if this philosopher uses asymmetric ordering
}

// NewPhilosopher creates a philosopher with the correct fork ordering
func NewPhilosopher(id int, forks []*Fork, numPhilosophers int) *Philosopher {
	leftForkID := id
	rightForkID := (id + 1) % numPhilosophers

	// The last philosopher uses asymmetric ordering
	// This breaks the circular wait
	asymmetric := (id == numPhilosophers-1)

	return &Philosopher{
		id:         id,
		leftFork:   forks[leftForkID],
		rightFork:  forks[rightForkID],
		asymmetric: asymmetric,
	}
}

// dine simulates a philosopher's behavior
func (p *Philosopher) dine(wg *sync.WaitGroup) {
	defer wg.Done()

	for i := 0; i < 3; i++ {
		p.think()
		p.pickUpForks()
		p.eat()
		p.putDownForks()
	}
}

func (p *Philosopher) think() {
	fmt.Printf("Philosopher %d is thinking...\n", p.id)
	time.Sleep(time.Duration(100+p.id*10) * time.Millisecond)
}

func (p *Philosopher) pickUpForks() {
	if p.asymmetric {
		// Asymmetric: pick up RIGHT fork first, then LEFT
		p.rightFork.Lock()
		fmt.Printf("Philosopher %d (asymmetric) picked up RIGHT fork %d first\n",
			p.id, p.rightFork.id)

		p.leftFork.Lock()
		fmt.Printf("Philosopher %d (asymmetric) picked up LEFT fork %d second\n",
			p.id, p.leftFork.id)
	} else {
		// Normal: pick up LEFT fork first, then RIGHT
		p.leftFork.Lock()
		fmt.Printf("Philosopher %d picked up LEFT fork %d\n", p.id, p.leftFork.id)

		p.rightFork.Lock()
		fmt.Printf("Philosopher %d picked up RIGHT fork %d\n", p.id, p.rightFork.id)
	}
}

func (p *Philosopher) eat() {
	fmt.Printf("Philosopher %d is eating (meal %d)\n", p.id, p.eatenCount+1)
	p.eatenCount++
	time.Sleep(200 * time.Millisecond)
}

func (p *Philosopher) putDownForks() {
	p.rightFork.Unlock()
	p.leftFork.Unlock()
	fmt.Printf("Philosopher %d put down both forks\n", p.id)
}

func main() {
	fmt.Println("=== Dining Philosophers: Asymmetric Solution ===")
	fmt.Println("Breaking circular wait with resource ordering")
	fmt.Println()

	numPhilosophers := 5

	// Create 5 forks
	forks := make([]*Fork, numPhilosophers)
	for i := 0; i < numPhilosophers; i++ {
		forks[i] = &Fork{id: i}
	}

	// Create philosophers with asymmetric ordering for the last one
	philosophers := make([]*Philosopher, numPhilosophers)
	for i := 0; i < numPhilosophers; i++ {
		philosophers[i] = NewPhilosopher(i, forks, numPhilosophers)
	}

	// Verify the ordering
	fmt.Println("Fork acquisition order:")
	for i, p := range philosophers {
		if p.asymmetric {
			fmt.Printf("  Philosopher %d: RIGHT fork %d → LEFT fork %d (ASYMMETRIC)\n",
				i, p.rightFork.id, p.leftFork.id)
		} else {
			fmt.Printf("  Philosopher %d: LEFT fork %d → RIGHT fork %d\n",
				i, p.leftFork.id, p.rightFork.id)
		}
	}
	fmt.Println()

	// Start dining
	var wg sync.WaitGroup
	startTime := time.Now()

	fmt.Println("Starting philosophers...")
	for i := 0; i < numPhilosophers; i++ {
		wg.Add(1)
		go philosophers[i].dine(&wg)
	}

	// Wait for completion with timeout
	done := make(chan struct{})
	go func() {
		wg.Wait()
		close(done)
	}()

	select {
	case <-done:
		elapsed := time.Since(startTime)
		fmt.Println("\n✓ All philosophers finished dining!")
		fmt.Printf("Total time: %v\n\n", elapsed)

		fmt.Println("Meal counts:")
		totalMeals := 0
		for i, p := range philosophers {
			marker := ""
			if p.asymmetric {
				marker = " (asymmetric)"
			}
			fmt.Printf("  Philosopher %d: %d meals%s\n", i, p.eatenCount, marker)
			totalMeals += p.eatenCount
		}
		fmt.Printf("  Total: %d meals\n", totalMeals)
		fmt.Println("\n✓ No deadlock! Asymmetric solution works!")

	case <-time.After(10 * time.Second):
		fmt.Println("\n✗ Timeout! Unexpected deadlock occurred.")
	}
}

Alternative: Global Resource Ordering

An even more general solution is to assign a global order to all forks and always acquire them in ascending order:

// pickUpForksWithGlobalOrdering always acquires lower-ID fork first
func (p *Philosopher) pickUpForksWithGlobalOrdering() {
	// Determine which fork has lower ID
	first, second := p.leftFork, p.rightFork
	if p.rightFork.id < p.leftFork.id {
		first, second = p.rightFork, p.leftFork
	}

	// Always acquire lower ID first
	first.Lock()
	fmt.Printf("Philosopher %d picked up fork %d (lower ID)\n", p.id, first.id)

	second.Lock()
	fmt.Printf("Philosopher %d picked up fork %d (higher ID)\n", p.id, second.id)
}

This works because:

Everyone agrees on the same global ordering (by fork ID)
No cycle can form when all acquisitions follow the same order
Works for any number of philosophers and forks!

Complete Example with Global Ordering

package main

import (
	"fmt"
	"sync"
	"time"
)

// Fork represents a dining fork with a globally unique ID
type Fork struct {
	id int
	sync.Mutex
}

// Philosopher with global resource ordering
type Philosopher struct {
	id                  int
	leftFork, rightFork *Fork
	eatenCount          int
}

func (p *Philosopher) dine(wg *sync.WaitGroup) {
	defer wg.Done()

	for i := 0; i < 3; i++ {
		p.think()
		p.pickUpForksOrdered()
		p.eat()
		p.putDownForks()
	}
}

func (p *Philosopher) think() {
	time.Sleep(time.Duration(50+p.id*10) * time.Millisecond)
}

func (p *Philosopher) pickUpForksOrdered() {
	// ALWAYS acquire forks in ascending ID order
	first, second := p.leftFork, p.rightFork
	firstName, secondName := "left", "right"

	if p.rightFork.id < p.leftFork.id {
		first, second = p.rightFork, p.leftFork
		firstName, secondName = "right", "left"
	}

	first.Lock()
	fmt.Printf("Philosopher %d: acquired %s fork %d (1st, lower ID)\n",
		p.id, firstName, first.id)

	second.Lock()
	fmt.Printf("Philosopher %d: acquired %s fork %d (2nd, higher ID)\n",
		p.id, secondName, second.id)
}

func (p *Philosopher) eat() {
	p.eatenCount++
	time.Sleep(150 * time.Millisecond)
}

func (p *Philosopher) putDownForks() {
	p.rightFork.Unlock()
	p.leftFork.Unlock()
}

func simulateWithGlobalOrdering(numPhilosophers int) {
	fmt.Printf("\n=== Simulating %d philosophers with global resource ordering ===\n\n",
		numPhilosophers)

	// Create forks
	forks := make([]*Fork, numPhilosophers)
	for i := 0; i < numPhilosophers; i++ {
		forks[i] = &Fork{id: i}
	}

	// Create philosophers
	philosophers := make([]*Philosopher, numPhilosophers)
	for i := 0; i < numPhilosophers; i++ {
		philosophers[i] = &Philosopher{
			id:        i,
			leftFork:  forks[i],
			rightFork: forks[(i+1)%numPhilosophers],
		}
	}

	// Show ordering
	fmt.Println("Resource acquisition order:")
	for _, p := range philosophers {
		if p.leftFork.id < p.rightFork.id {
			fmt.Printf("  Philosopher %d: fork %d → fork %d\n",
				p.id, p.leftFork.id, p.rightFork.id)
		} else {
			fmt.Printf("  Philosopher %d: fork %d → fork %d\n",
				p.id, p.rightFork.id, p.leftFork.id)
		}
	}
	fmt.Println()

	// Start dining
	var wg sync.WaitGroup
	for i := 0; i < numPhilosophers; i++ {
		wg.Add(1)
		go philosophers[i].dine(&wg)
	}

	wg.Wait()
	fmt.Printf("\n✓ All %d philosophers completed successfully!\n", numPhilosophers)
}

func main() {
	// Test with different numbers of philosophers
	simulateWithGlobalOrdering(5)
	simulateWithGlobalOrdering(10)
	simulateWithGlobalOrdering(20)
}

Performance Comparison

Solution	Concurrency	Deadlock Risk	Complexity	Scalability
Naive	High	Yes	Low	Good
Waiter	Medium (N-1)	No	Medium	Fair
Asymmetric	High	No	Low	Excellent

The asymmetric solution offers the best of both worlds: no deadlock AND maximum concurrency!

Key Advantages

✓ No central coordinator - Fully distributed ✓ Maximum concurrency - All philosophers can attempt to eat ✓ Simple to implement - Just change one philosopher’s order ✓ Scales perfectly - Works with any number of resources ✓ Zero overhead - No semaphores or extra synchronization ✓ Provably correct - Breaks circular wait mathematically

When to Use This Pattern

✓ Use when:

Resources can be globally ordered (assigned IDs)
You need maximum concurrency
You want a distributed solution (no coordinator)
Deadlock prevention is critical
Performance matters

✗ Consider alternatives when:

Resources can’t be uniquely ordered
Fairness is more important than throughput
You need explicit resource management
Dynamic resource allocation is required

Real-World Example: Bank Transfers

type Account struct {
	id      int
	balance int
	sync.Mutex
}

// Transfer money between accounts using resource ordering
func Transfer(from, to *Account, amount int) error {
	// Always lock accounts in ascending ID order
	first, second := from, to
	if to.id < from.id {
		first, second = to, from
	}

	first.Lock()
	defer first.Unlock()

	second.Lock()
	defer second.Unlock()

	// Now safely transfer
	if from.balance < amount {
		return fmt.Errorf("insufficient funds")
	}

	from.balance -= amount
	to.balance += amount
	return nil
}

This prevents deadlock even with concurrent transfers:

Transfer(A → B) and Transfer(B → A) won’t deadlock
Both lock accounts in the same order (by ID)

Try It Yourself

Experiment with the code:

Test with more philosophers - Try 10, 20, 100
Remove asymmetric ordering - See it deadlock again
Benchmark both solutions - Compare waiter vs asymmetric
Add starvation detection - Track max wait time per philosopher
Implement priority - Give some philosophers higher priority

The Big Lesson

Resource ordering is one of the most powerful deadlock prevention techniques. It’s used throughout:

Operating systems (lock hierarchies)
Databases (lock ordering)
Distributed systems (global clocks)
File systems (inode ordering)

Understanding this pattern will make you a better concurrent programmer in any language!

This is part 3 of the Dining Philosophers series in “Golang Experiments: Classic Concurrency Problems”

The Elegant Solution#

The Asymmetric Solution Explained#

Why It Works#

The Original Circular Wait (Deadlock)#

With Asymmetric Ordering (No Deadlock)#

Real-World Applications#

Implementation#

Alternative: Global Resource Ordering#

Complete Example with Global Ordering#

Performance Comparison#

Key Advantages#

When to Use This Pattern#

Real-World Example: Bank Transfers#

Try It Yourself#

The Big Lesson#