1
\$\begingroup\$

I am trying to solve the Dining philosophers problem in CSharp. I didn't use any semaphores and it looks like it's working. I am wondering 1) if my code deadlock is safe and 2) if can I please get some feedback on my method as opposed to using semaphores. Thank you

using System;
using System.Linq;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;

public enum State
{
    Eating, Thinking,
}

internal class Program
{
    private static State[] _states;
    private static bool[] _forks;

    private static void Setup(int n)
    {
        _states = Enumerable.Repeat(State.Thinking, n).ToArray();
        _forks = Enumerable.Repeat(true, n).ToArray();
    }

    private static void Run(int id)
    {
        var random = new Random();
        while (true)
        {
            var leftFork = (id - 1) % _forks.Length;
            var rightFork = (id + 1) % _forks.Length;
        
            // We need both forks available to be able to east
            if (!_forks[leftFork] || !_forks[rightFork]) continue;
            
            // Make sure updating of fork and state happens atomically, without concurrent read/update
            lock (_forks) lock(_states)
            {
                Console.WriteLine($"{id} is starting to eat");
                _forks[leftFork] = false;
                _forks[rightFork] = false;
                _states[id] = State.Eating;
            }

            Thread.Sleep(TimeSpan.FromSeconds(random.Next(1, 5)));
                
            // Make sure updating of fork and state happens atomically, without concurrent read/update
            lock (_forks) lock(_states)
            {
                Console.WriteLine($"{id} finished eating");
                _forks[leftFork] = true;
                _forks[rightFork] = true;
                _states[id] = State.Thinking;
            }
        }
    }
    
    public static void Main(string[] args)
    {
        const int count = 5;
        Setup(count);
        var tasks = new List<Task>();

        for (var i = 0; i < count; i++)
        {
            var icopy = i;
            tasks.Add(Task.Factory.StartNew(() => Run(icopy)));
        }

        Task.WaitAll(tasks.ToArray());
    }
}

Try it yourself

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why don't you use one of the built-in Concurrent collections for states and forks? \$\endgroup\$ Commented Dec 26, 2022 at 6:39
  • 1
    \$\begingroup\$ I highly recommend Patterns for Parallel Programming free mini-book by Stephen Toub. At the end, a solution to the problem of dining philosophers is described. Must read! \$\endgroup\$ Commented Dec 26, 2022 at 16:30

1 Answer 1

2
\$\begingroup\$

Your code does not have any deadlocks. The only operations that can block are the lock statements and they are always locked in the same order. Which by the way means that there is no point having two locks at all, since all access is synchronized by the outer lock anyway.

However, your code has race conditions and as such is not correct.

Consider two neighbouring philosophers in a situation when noone is eating and all the forks are available. The first one checks the forks here

if (!_forks[leftFork] || !_forks[rightFork]) continue;

and sees that they are available. Just after that, the second one does the same thing and gets the same result. After that your lock is irrelevant: the philosophers will execute the code in order, but since there are no checks inside the lock, both philosophers will take the same fork.

To solve this problem, you will need to check the conditions again inside the lock. But if this check fails, what is the philosopher to do? Here is where the semaphore comes in, to enable the philosopher to wait until the forks are available. But this is not the only possible solution.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.