README.md

The Dining Philosophers Code

Generated with ChatGPT

This code implements a solution to the Dining Philosophers Problem, a classic synchronization problem in computer science. The problem describes a scenario where a group of philosophers sits around a circular table. Each philosopher alternates between thinking and eating, and they require two chopsticks (shared resources) to eat. The challenge is to prevent deadlock and ensure that all philosophers can eat eventually.

Modules Overview

1. Chopstick

The Chopstick module simulates a single chopstick. It keeps track of whether the chopstick is in use and handles requests from philosophers to either pick up or release the chopstick.

Functions:

• start/0:
  • Starts a process representing a chopstick.
  • Calls the loop/1 function with an initial state (false), indicating the chopstick is not in use.
• loop/1:
  • A recursive function that manages the chopstick state.
  • Responds to messages:
    • {:request, from}: A philosopher requests the chopstick.
      • If the chopstick is not in use, grants access (:granted) and updates the state to true.
      • If the chopstick is already in use, responds with :busy.
    • {:release}: A philosopher releases the chopstick, resetting its state to false.

2. Philosopher

The Philosopher module simulates the behavior of a philosopher. Each philosopher alternates between thinking and eating and interacts with two chopsticks.

Functions:

• start/3:
  • Starts a process representing a philosopher.
  • Takes the philosopher's name and the PIDs of their left and right chopsticks.
  • Calls the loop/3 function to begin the philosopher's lifecycle.
• loop/3:
  • Simulates the philosopher's lifecycle:
    1. Thinking:
       • Prints a message ("Philosopher X is thinking.") and waits for a random time (:timer.sleep/1).
    2. Hungry and Attempting to Eat:
       • Prints a message indicating that the philosopher is hungry and attempts to pick up chopsticks.
       • Sends a {:request, self()} message to the left chopstick.
       • Waits for a response (:granted or timeout).
         • If the left chopstick is granted:
           • Sends a {:request, self()} message to the right chopstick.
           • Waits for a response from the right chopstick.
             • If the right chopstick is granted:
               • Prints a message ("Philosopher X is eating.") and simulates eating time (:timer.sleep/1).
               • Releases both chopsticks (:release) and prints a message indicating the chopsticks have been released.
             • If the right chopstick is not granted (timeout):
               • Releases the left chopstick and prints a message indicating failure to acquire the right chopstick.
         • If the left chopstick is not granted (timeout):
           • Prints a message indicating failure to acquire the left chopstick.
    3. Repeating the Cycle:
       • Calls itself recursively to repeat the cycle.

3. DiningPhilosophers

The DiningPhilosophers module sets up the simulation for the Dining Philosophers Problem.

Functions:

• start/1:
  • Initializes the simulation for n philosophers.
  • Steps:
    1. Creates n chopsticks using Chopstick.start/0. Each chopstick is represented by a process.
    2. Creates n philosophers using Philosopher.start/3.
       • Each philosopher is assigned a unique name ("Philosopher X") and two chopsticks:
         • Left chopstick: Enum.at(chopsticks, i - 1)
         • Right chopstick: Enum.at(chopsticks, rem(i, n)) (wraps around for the last philosopher).

Key Features and Behaviors

1. Thinking:

   • Philosophers spend random amounts of time thinking before becoming hungry.
   • This randomness helps simulate real-world, unpredictable behavior.

2. Eating:

   • Philosophers need to acquire both their left and right chopsticks to eat.
   • They attempt to pick up the left chopstick first and then the right chopstick.
   • If they fail to acquire a chopstick within 1 second, they release any chopstick they may have acquired and retry the cycle.

3. Deadlock Avoidance:

   • The program avoids deadlock through careful handling of timeouts.
   • If a philosopher cannot acquire both chopsticks within a set period, they release any acquired resources, allowing other philosophers to proceed.

4. Concurrency:

   • Chopsticks and philosophers are modeled as independent processes, enabling concurrent operations.
   • The use of message passing ensures safe communication between processes.

5. Wrap-Around:

   • The rem(i, n) expression ensures the last philosopher's right chopstick is the first chopstick in the list, completing the circular arrangement.

Example Simulation Flow

1. Initialization:

   • Five chopstick processes are created.
   • Five philosopher processes are created and assigned chopsticks.

2. Philosopher Lifecycle:

   • Philosopher 1 starts thinking.
   • Philosopher 2 starts thinking.
   • Philosopher 3 gets hungry, requests the left chopstick, and acquires it.
   • Philosopher 3 requests the right chopstick but may have to wait if it's in use.
   • Philosopher 3 either eats or releases the left chopstick if the right chopstick isn't granted within 1 second.
   • The cycle repeats for all philosophers.

3. Chopstick States:

   • Each chopstick keeps track of whether it is in use and responds to philosophers' requests.

Benefits of This Approach

1. Scalability:

   • The simulation can handle any number of philosophers greater than 1.

2. Concurrency:

   • The use of lightweight processes in Elixir/Erlang ensures efficient handling of concurrent operations.

3. Fairness:

   • The timeout mechanism ensures no philosopher is indefinitely blocked.

Potential Improvements

1. Logging:

   • Add timestamps to logs to track the timeline of events more precisely.

2. Starvation Prevention:

   • Ensure philosophers who wait too long are prioritized for resource access.

3. Visualization:

   • Create a graphical representation of philosophers and chopsticks to observe the simulation visually.

This implementation demonstrates the power of Elixir’s concurrency model to solve synchronization problems elegantly and efficiently.

dining-philosopher.ex

defmodule Chopstick do
  def start do
    spawn(__MODULE__, :loop, [false]) # Initially not in use
  end

  def loop(in_use) do
    receive do
      {:request, from} when not in_use ->
        send(from, :granted)
        loop(true)

      {:release} ->
        loop(false)

      {:request, from} ->
        send(from, :busy)
        loop(in_use)
    end
  end
end

defmodule Philosopher do
  def start(name, left_chopstick, right_chopstick) do
    spawn(__MODULE__, :loop, [name, left_chopstick, right_chopstick])
  end

  def loop(name, left_chopstick, right_chopstick) do
    IO.puts("#{name} is thinking.")
    :timer.sleep(:rand.uniform(1000)) # Simulate thinking time

    IO.puts("#{name} is hungry and trying to pick up chopsticks.")
    send(left_chopstick, {:request, self()})
    receive do
      :granted ->
        send(right_chopstick, {:request, self()})
        receive do
          :granted ->
            IO.puts("#{name} is eating.")
            :timer.sleep(:rand.uniform(1000)) # Simulate eating time
            send(left_chopstick, :release)
            send(right_chopstick, :release)
            IO.puts("#{name} finished eating and released chopsticks.")
        after
          1000 ->
            send(left_chopstick, :release)
            IO.puts("#{name} couldn't get the right chopstick and released the left.")
        end
    after
      1000 ->
        IO.puts("#{name} couldn't get the left chopstick.")
    end

    loop(name, left_chopstick, right_chopstick)
  end
end

defmodule DiningPhilosophers do
  def start(n) when n > 1 do
    # Create chopsticks (n chopsticks for n philosophers)
    chopsticks = Enum.map(1..n, fn _ -> Chopstick.start() end)

    # Create philosophers and assign their left and right chopsticks
    Enum.each(1..n, fn i ->
      left_chopstick = Enum.at(chopsticks, i - 1)
      right_chopstick = Enum.at(chopsticks, rem(i, n)) # Wrap around for the last philosopher
      Philosopher.start("Philosopher #{i}", left_chopstick, right_chopstick)
    end)
  end
end

# Start the simulation for n philosophers
DiningPhilosophers.start(5)