Dining philosophers problem using just lock without semaphore in C#

Question

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

• Peter Csala: Why don't you use one of the built-in Concurrent collections for states and forks?
• Alexander Petrov: 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!

Answer 1

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.