Tanenbaum's Solution: State Tracking with Neighbor Notification

Solution 3
Tanenbaum's solution: Track philosopher states (thinking, hungry, eating). A philosopher can only eat if both neighbors are not eating. Neighbors notify when they finish.
State Machine
THINKINGNot hungryHUNGRYWants to eatEATINGHas both forkswanttest OKdone eating
The test() Function
test(i):
  if state[i] == HUNGRY
    && state[LEFT] != EATING
   && state[RIGHT] != EATING:
      state[i] = EATING
      sem[i].signal()
How It Works
get_forks: Set state to HUNGRY, test self, wait on personal semaphore if test failed.
put_forks: Set state to THINKING, test left neighbor, test right neighbor. This wakes hungry neighbors who can now eat.
Why No Deadlock
No philosopher holds resources while waiting. They either eat (have both forks logically) or wait on their semaphore (hold nothing). The test() function atomically checks and grants both forks.
Trade-offs
Pros: Fair, no deadlock, maximum concurrency (2 can eat simultaneously).
Cons: More complex code. Global mutex protects state changes.
Pattern: State tracking + neighbor notification. Acquire resources atomically (both or neither). Let neighbors know when you release.

💡 Key Takeaways

✓State-based approach: each philosopher has state (thinking/hungry/eating) and private semaphore; global mutex protects state changes; no direct fork semaphores

✓test(i) function: if philosopher i is hungry AND both neighbors are not eating, set state to eating and signal philosopher i's semaphore to unblock them

✓get_forks: set state to hungry, test self, block on own semaphore; put_forks: set state to thinking, test both neighbors (may wake them)

✓Two paths to eating: (1) call get_forks when neighbors not eating, test signals before wait, proceeds immediately; (2) block on semaphore, neighbor finishes and calls test which signals

✓Deadlock-free (mutex is only shared semaphore, never held while waiting on another) but NOT starvation-free; Gingras showed P0 can starve if P2 and P4 alternate eating

📌 Examples

1Immediate eating: P2 calls get_forks; P1 and P3 are thinking; test(2) finds P2 hungry and neighbors not eating; sets state to eating, signals sem[2]; P2.wait() returns immediately

2Delayed eating: P1 hungry but P2 is eating; test(1) fails; P1 blocks on sem[1]; P2 finishes, calls test(1); now P1 hungry and neighbors not eating; sets eating, signals sem[1]; P1 unblocks

3Starvation pattern: P2 eating (P1, P3 blocked), P4 eating; P2 finishes, wakes P3; P4 finishes, wakes nobody; P3 eating, P4 gets hungry; P3 finishes, wakes P4; cycle P2↔P4 continues, P0 never both neighbors free

← Back to Dining Philosophers Problem Overview