Dining Philosophers Algorithm in C# with Real World Implementation

Introduction

The Dining Philosophers problem is a classic synchronization problem that illustrates the challenges of resource allocation in concurrent programming. Introduced by Edsger Dijkstra in 1965, the problem demonstrates how a group of philosophers sitting around a table with a fork between each pair can share limited resources (forks) without causing deadlock or starvation. The problem is highly relevant in real-world scenarios where multiple processes need to access shared resources without conflict. In this article, we will explore the Dining Philosophers algorithm in a real-world context and demonstrate its implementation in C#, highlighting the importance of synchronization in concurrent systems.

The Dining Philosophers' Problem

Imagine five philosophers sitting around a circular table. Each philosopher alternates between thinking and eating. A fork is placed between each pair of adjacent philosophers, and each philosopher needs both the left and right forks to eat. The challenge is to design a protocol that the philosophers can follow to avoid deadlock (where no philosopher can eat) and starvation (where one or more philosophers are perpetually prevented from eating).

Real-World Scenario. Database Connection Pooling

A practical application of the Dining Philosophers problem can be found in database connection pooling. In a multi-threaded application, multiple threads (philosophers) need to access a limited number of database connections (forks). Proper synchronization is essential to ensure that all threads can access the connections without causing deadlock or starvation.

Implementing the Dining Philosophers Algorithm in C#

To solve the Dining Philosophers problem in C#, we need to use threading and synchronization primitives.

Step 1. Setting Up the Project

Create a new C# console application project in Visual Studio. Add a new class file named Philosopher.cs to represent each philosopher.

Step 2. Defining the Philosopher Class

In the Philosopher.cs file, define the Philosopher class, which will represent a philosopher. Each philosopher will have an ID, left fork, and right fork.

using System;
using System.Threading;

public class Philosopher
{
    private readonly int id;
    private readonly Fork leftFork;
    private readonly Fork rightFork;

    public Philosopher(int id, Fork leftFork, Fork rightFork)
    {
        this.id = id;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    public void Dine()
    {
        while (true)
        {
            Think();
            Eat();
        }
    }

    private void Think()
    {
        Console.WriteLine($"Philosopher {id} is thinking.");
        Thread.Sleep(new Random().Next(1000, 2000));
    }

    private void Eat()
    {
        Console.WriteLine($"Philosopher {id} is hungry.");
        
        lock (leftFork)
        {
            Console.WriteLine($"Philosopher {id} picked up left fork.");
            lock (rightFork)
            {
                Console.WriteLine($"Philosopher {id} picked up right fork and is eating.");
                Thread.Sleep(new Random().Next(1000, 2000));
                Console.WriteLine($"Philosopher {id} put down right fork.");
            }
            Console.WriteLine($"Philosopher {id} put down left fork.");
        }
    }
}

Step 3. Defining the Fork Class

Add a new class file named Fork.cs to represent a fork. Each fork will have an ID.

public class Fork
{
    public int Id { get; private set; }

    public Fork(int id)
    {
        Id = id;
    }
}

Step 4. Implementing the Main Program

In the Program.cs file, initialize the philosophers and forks. Create threads for each philosopher and start their Dine method in separate threads.

class Program
{
    static void Main(string[] args)
    {
        int numberOfPhilosophers = 5;
        Philosopher[] philosophers = new Philosopher[numberOfPhilosophers];
        Fork[] forks = new Fork[numberOfPhilosophers];

        for (int i = 0; i < numberOfPhilosophers; i++)
        {
            forks[i] = new Fork(i);
        }

        for (int i = 0; i < numberOfPhilosophers; i++)
        {
            philosophers[i] = new Philosopher(i, forks[i], forks[(i + 1) % numberOfPhilosophers]);
        }

        Thread[] threads = new Thread[numberOfPhilosophers];

        for (int i = 0; i < numberOfPhilosophers; i++)
        {
            threads[i] = new Thread(philosophers[i].Dine);
            threads[i].Start();
        }

        foreach (var thread in threads)
        {
            thread.Join();
        }
    }
}

Step 5. Avoiding Deadlock

In the above implementation, deadlock is a potential issue because each philosopher locks the left fork first and then the right fork. To prevent deadlock, we can introduce an additional condition where the last philosopher picks up the right fork first and then the left fork.

private void Eat()
{
    Console.WriteLine($"Philosopher {id} is hungry.");

    if (id % 2 == 0)
    {
        lock (rightFork)
        {
            Console.WriteLine($"Philosopher {id} picked up right fork.");
            lock (leftFork)
            {
                Console.WriteLine($"Philosopher {id} picked up left fork and is eating.");
                Thread.Sleep(new Random().Next(1000, 2000));
                Console.WriteLine($"Philosopher {id} put down left fork.");
            }
            Console.WriteLine($"Philosopher {id} put down right fork.");
        }
    }
    else
    {
        lock (leftFork)
        {
            Console.WriteLine($"Philosopher {id} picked up left fork.");
            lock (rightFork)
            {
                Console.WriteLine($"Philosopher {id} picked up right fork and is eating.");
                Thread.Sleep(new Random().Next(1000, 2000));
                Console.WriteLine($"Philosopher {id} put down right fork.");
            }
            Console.WriteLine($"Philosopher {id} put down left fork.");
        }
    }
}

Output

Dining Philosophers Algorithm in C#

Conclusion

The Dining Philosophers problem is a fundamental example of synchronization issues in concurrent programming. Implementing the Dining Philosophers algorithm in C# helps us understand the complexities of resource allocation and the importance of avoiding deadlock and starvation. By translating this classic problem to a real-world scenario, such as database connection pooling, we can appreciate the practical applications of these concepts in ensuring efficient and reliable systems. Properly handling synchronization in concurrent systems is crucial for maintaining performance and preventing issues that could disrupt the smooth operation of applications.