We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Dining Philosophers

Number: 1340

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Five philosophers are sitting around a circular table, each with a bowl of spaghetti. There is one fork between each pair of philosophers. A philosopher must pick up both forks (their left and right neighbors’ forks) to eat. After finishing eating, they put both forks down. Philosophers think when not eating. Implement the function wantsToEat where a philosopher picks up the two forks, eats, and then puts the forks down. The algorithm must ensure that no philosopher will ever starve.

Key Insights

  • Use mutual exclusion (mutexes/locks) to represent forks.
  • Enforce a total ordering when picking up forks to prevent circular wait and avoid deadlock.
  • Each philosopher attempts to pick up the lower indexed fork first and the higher indexed fork second.
  • After eating, forks are released so they become available for others.
  • The solution is built for concurrent execution among five threads.

Space and Time Complexity

Time Complexity: O(1) per call, since fork acquisition, eating, and releasing are constant-time operations. Space Complexity: O(1) as the amount of memory used does not depend on input size (only five locks are used).

Solution

We solve the Dining Philosophers problem by assigning a lock to each fork. When a philosopher wants to eat, they first determine the indices of their two forks (left and right) and then pick up the forks in a fixed order: first the one with the lower index and then the one with the higher index. This order eliminates circular waiting and prevents deadlock. Once both forks are acquired, the philosopher eats and then releases the locks in reverse order. This approach guarantees that every philosopher gets a chance to eat without starvation.

Code Solutions

import threading

class DiningPhilosophers:
    def __init__(self):
        # Initialize a lock for each of the five forks.
        self.forks = [threading.Lock() for _ in range(5)]
    
    def wantsToEat(self, philosopher: int,
                   pickLeftFork: 'Callable[[], None]',
                   pickRightFork: 'Callable[[], None]',
                   eat: 'Callable[[], None]',
                   putLeftFork: 'Callable[[], None]',
                   putRightFork: 'Callable[[], None]') -> None:
        left = philosopher
        right = (philosopher + 1) % 5
        
        # Order forks by index to prevent deadlock.
        firstFork = min(left, right)
        secondFork = max(left, right)
        
        # Acquire the first fork.
        with self.forks[firstFork]:
            if firstFork == left:
                pickLeftFork()
            else:
                pickRightFork()
            # Acquire the second fork.
            with self.forks[secondFork]:
                if secondFork == left:
                    pickLeftFork()
                else:
                    pickRightFork()
                
                # Eat.
                eat()
                
                # Release the second fork.
                if secondFork == left:
                    putLeftFork()
                else:
                    putRightFork()
            # Release the first fork.
            if firstFork == left:
                putLeftFork()
            else:
                putRightFork()
← Back to All Questions