Let’s take a look at how concurrent and parallel programming works in .NET, using the problem of the dining philosophers as an example. The plan is to cover everything from thread/process synchronization to the actor model (in later parts). This article can be useful for a first introduction or to refresh your knowledge.
Why is this skill important? Transistors are reaching their minimum size, Moore's Law is hitting the limit of the speed of light, and thus growth is observed in quantity; more transistors can be made. At the same time, the amount of data is increasing, and users expect instantaneous system responses. In such a situation, 'traditional' programming, where there is only one executing thread, is no longer efficient. We need to address the problem of simultaneous or concurrent execution. This problem exists at various levels: at the thread level, at the process level, and at the machine level in networks (distributed systems). .NET offers reliable, proven technologies for quickly and effectively solving such tasks.
Task
Edsger Dijkstra posed this problem to his students back in 1965. The established formulation is as follows. There is a certain (usually five) number of philosophers and the same number of forks. They sit around a circular table with forks between them. Philosophers can eat from their plates filled with infinite food, think, or wait. To eat, a philosopher needs to take two forks (the last philosopher shares a fork with the first). Picking up and placing down a fork are two separate actions. All philosophers are silent. The task is to find an algorithm that allows them all to think and be satisfied even after 54 years.
First, let’s try to solve this problem using shared space. The forks are placed on a common table, and philosophers simply take them when they are available and put them back. Here, synchronization problems arise: when exactly should forks be taken? What to do if a fork is not available? And so on. But first, let’s get the philosophers started.
To launch the threads, we use a thread pool via Task.Run method:
var cancelTokenSource = new CancellationTokenSource();
Action create = (i) => RunPhilosopher(i, cancelTokenSource.Token);
for (int i = 0; i create(icopy), cancelTokenSource.Token);
}The thread pool is created to optimize the creation and deletion of threads. This pool has a queue with tasks and the CLR creates or removes threads depending on the number of those tasks. There is one pool for all AppDomains. This pool should be used almost all the time since it removes the hassle of creating, deleting threads, their queues, etc. It is possible to go without a pool, but then one would have to use it directly. Thread, this is reasonable for cases when you need to change the thread priority, when we have a long operation, for a Foreground thread, etc.
In other words, System.Threading.Tasks.Task class is essentially the same Thread, but with various conveniences: the ability to start a task after a block of other tasks, to return them from functions, to interrupt them conveniently, and many others. They are needed to support async/await constructs (Task-based Asynchronous Pattern, syntactic sugar for waiting for an IO operation). We will discuss this further.
CancelationTokenSource is needed here so that the thread can finish by itself at the signal of the calling thread.
Synchronization issues
Blocked philosophers
Well, we can create threads, let’s try to have lunch:
// Кто какие вилки взял. К примеру: 1 1 3 3 - 1й и 3й взяли первые две пары.
private int[] forks = Enumerable.Repeat(0, philosophersAmount).ToArray();
// То же, что RunPhilosopher()
private void RunDeadlock(int i, CancellationToken token)
{
// Ждать вилку, взять её. Эквивалентно:
// while(true)
// if forks[fork] == 0
// forks[fork] = i+1
// break
// Thread.Sleep() или Yield() или SpinWait()
void TakeFork(int fork) =>
SpinWait.SpinUntil(() =>
Interlocked.CompareExchange(ref forks[fork], i+1, 0) == 0);
// Для простоты, но можно с Interlocked.Exchange:
void PutFork(int fork) => forks[fork] = 0;
while (true)
{
TakeFork(Left(i));
TakeFork(Right(i));
eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
PutFork(Left(i));
PutFork(Right(i));
Think(i);
// Завершить работу по-хорошему.
token.ThrowIfCancellationRequested();
}
}Here we first try to take the left fork and then the right one, and if we succeed, we eat and put them back. The taking of one fork is atomic, i.e., two threads cannot take one at the same time (incorrect: the first reads that the fork is free, the second does too, the first takes it, the second takes it). For this, Interlocked.CompareExchange, which should be implemented using a processor instruction (TSL, XCHG), which locks a memory area for atomic sequential reading and writing. And SpinWait is equivalent to the construct while(true) but with a little 'magic' — the thread occupies the CPU (Thread.SpinWait), but sometimes yields control to another thread (Thread.Yeild) or sleeps (Thread.Sleep).
But this solution does not work, as the threads soon (for me within a second) get blocked: all philosophers take their left fork, but not their right. The forks array then has the values: 1 2 3 4 5.
In the diagram, blocking threads (deadlock). Green indicates execution, red indicates synchronization, and gray indicates the thread is sleeping. Diamonds represent the start time of tasks.
The Dining Philosophers
While you don't need much food to think, hunger can make anyone abandon philosophy. Let's simulate a situation of thread starvation in our task. Starvation occurs when a thread is active but not making significant progress; in other words, it's similar to deadlock, but now the thread is not sleeping—it is actively seeking to eat, but there's no food. To avoid frequent blocking, we will put the fork back if we cannot take another one.
// То же что и в RunDeadlock, но теперь кладем вилку назад и добавляем плохих философов.
private void RunStarvation(int i, CancellationToken token)
{
while (true)
{
bool hasTwoForks = false;
var waitTime = TimeSpan.FromMilliseconds(50);
// Плохой философов может уже иметь вилку:
bool hasLeft = forks[Left(i)] == i + 1;
if (hasLeft || TakeFork(Left(i), i + 1, waitTime))
{
if (TakeFork(Right(i), i + 1, TimeSpan.Zero))
hasTwoForks = true;
else
PutFork(Left(i)); // Иногда плохой философ отдает вилку назад.
}
if (!hasTwoForks)
{
if (token.IsCancellationRequested) break;
continue;
}
eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
bool goodPhilosopher = i % 2 == 0;
// А плохой философ забывает положить свою вилку обратно:
if (goodPhilosopher)
PutFork(Left(i));
// А если и правую не положит, то хорошие будут вообще без еды.
PutFork(Right(i));
Think(i);
if (token.IsCancellationRequested)
break;
}
}
// Теперь можно ждать определенное время.
bool TakeFork(int fork, int philosopher, TimeSpan? waitTime = null)
{
return SpinWait.SpinUntil(
() => Interlocked.CompareExchange(ref forks[fork], philosopher, 0) == 0,
waitTime ?? TimeSpan.FromMilliseconds(-1)
);
}In this code, it is important that two out of four philosophers forget to put their left fork down. As a result, they eat more food while others start starving, even though all threads have the same priority. Here, they are not completely starving, since the bad philosophers occasionally put their forks down. I find that the good philosophers eat about five times less than the bad ones. Thus, a small error in the code leads to decreased performance. It's also worth noting that there is a rare situation where all philosophers grab their left fork, leaving the right one. They put the left one down, wait, grab the left one again, and so on. This situation is also starvation, resembling deadlock more closely. I couldn't reproduce it. Below is an illustration of the situation when two bad philosophers take both forks, while two good ones starve.
Here, it can be seen that the threads wake up occasionally and try to acquire the resource. Two out of four cores are doing nothing (the green graph at the top).
The Death of a Philosopher
And yet another problem that can interrupt the philosophers' delightful meal is if one of them suddenly dies with forks in hand (and he gets buried just like that). Then the neighbors will be left without lunch. You can come up with a sample code for this case, for example, throwing a NullReferenceException after the philosopher takes the forks. By the way, the exception will be unhandled, and the calling code won’t catch it just like that (for this, AppDomain.CurrentDomain.UnhandledException etc.). Therefore, error handlers are necessary within the threads with proper termination.
Waiter
Well, how do we solve this problem of deadlocks, starvation, and deaths? We'll allow only one philosopher to access the forks at a time and add mutual exclusion to this area. How do we do that? Let's assume there's a waiter next to the philosophers who grants permission to one philosopher to take the forks. How do we make this waiter, and how will the philosophers ask him? These are interesting questions.
The simplest way is for the philosophers to constantly ask the waiter for access to the forks. That is, now the philosophers will not wait for a fork but will wait or ask the waiter. Initially, we will only use User Space for this, where we do not use interrupts for calling any kernel procedures (more on that below).
User Space Solutions
Here we will do the same as we did before with one fork and two philosophers, we will loop and wait. But now it will be all philosophers and, in a way, only one fork, meaning only the philosopher who takes this 'golden fork' from the waiter can eat. For this, we will use SpinLock.
private static SpinLock spinLock = new SpinLock(); // Our "waiter"
private void RunSpinLock(int i, CancellationToken token)
{
while (true)
{
// Mutual blocking through busy waiting. We call before try to
// throw an exception in case of an error in the SpinLock.
bool hasLock = false;
spinLock.Enter(ref hasLock);
try
{
// Only one thread can be here (mutual exclusion).
forks[Left(i)] = i + 1; // Take the fork immediately, without waiting.
forks[Right(i)] = i + 1;
eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
forks[Left(i)] = 0;
forks[Right(i)] = 0;
}
finally
{
if(hasLock) spinLock.Exit(); // Avoid philosopher's death problem.
}
Think(i);
if (token.IsCancellationRequested)
break;
}
}SpinLock it's a lock that, roughly speaking, has the same while(true) { if (!lock) break; }, but with even more "magic" than in SpinWait (which is used there). Now it can count waiters, put them to sleep a bit, and much more. In general, it does everything possible for optimization. But it should be noted that this is still the same active loop, which consumes CPU resources and holds a thread that can lead to starvation if one of the philosophers becomes a higher priority than the others but does not have a golden fork (Priority Inversion problem). Therefore, we use it only for very very short changes in shared memory, without any external calls, nested locks, and other surprises.
Figure for SpinLock. The threads are constantly "fighting" for the golden fork. There are failures — the highlighted area in the figure. The cores are not fully utilized: only about 2/3 by these four threads.
Another solution here would be to use only Interlocked.CompareExchange with the same active waiting as shown in the code above (in the starving philosophers), but as mentioned earlier, this could theoretically lead to a deadlock.
About Interlocked It is worth mentioning that it not only has CompareExchange, but also other methods for atomic reading and writing. And through repeat modifications in case another thread gets a chance to make changes (read 1, read 2, write 2, write 1 is bad), it can be used for complex changes of a single value (Interlocked Anything pattern).
Kernel mode solutions
To avoid resource loss in the loop, let’s see how to block a thread. In other words, continuing our example, let’s see how the waiter puts the philosopher to sleep and wakes him only when needed. First, let's look at how to do this through the operating system's kernel mode. All structures there often turn out to be slower than those in user space. Slower by several times, for example, AutoResetEvent can be up to 53 times slower SpinLock [Richter]. But with their help, it is possible to synchronize processes across the system, whether managed or not.
The main construct here is the semaphore introduced by Dijkstra over half a century ago. A semaphore is, to simplify, a positive integer controlled by a system, with two operations on it: increment and decrement. If it cannot be decremented to zero, the calling thread is blocked. When the number is increased by some other active thread/process, the threads are allowed to proceed, and the semaphore decreases by the number of threads that passed. You can think of it as trains in a narrow space with a semaphore. .NET offers several constructs with similar functions: AutoResetEvent, ManualResetEvent, Mutex and itself Semaphore. We will use AutoResetEvent, which is the simplest of these constructs: it has only two values, 0 and 1 (false, true). Its method WaitOne() blocks the calling thread if the value was 0, and if 1, it decrements it to 0 and allows it to proceed. The method Set() increments it to 1 and allows one waiting thread to proceed, which then decrements back to 0. It acts like a turnstile in a metro.
Let's complicate the solution and use a lock for each philosopher, rather than for all at once. This means that multiple philosophers can now sit down simultaneously instead of just one. However, we still lock access to the table to correctly take the forks, avoiding race conditions.
// Для блокирования отдельного философа.
// Инициализируется: new AutoResetEvent(true) для каждого.
private AutoResetEvent[] philosopherEvents;
// Для доступа к вилкам / доступ к столу.
private AutoResetEvent tableEvent = new AutoResetEvent(true);
// Рождение философа.
public void Run(int i, CancellationToken token)
{
while (true)
{
TakeForks(i); // Ждет вилки.
// Обед. Может быть и дольше.
eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
PutForks(i); // Отдать вилки и разблокировать соседей.
Think(i);
if (token.IsCancellationRequested) break;
}
}
// Ожидать вилки в блокировке.
void TakeForks(int i)
{
bool hasForks = false;
while (!hasForks) // Попробовать еще раз (блокировка не здесь).
{
// Исключающий доступ к столу, без гонок за вилками.
tableEvent.WaitOne();
if (forks[Left(i)] == 0 && forks[Right(i)] == 0)
forks[Left(i)] = forks[Right(i)] = i + 1;
hasForks = forks[Left(i)] == i + 1 && forks[Right(i)] == i + 1;
if (hasForks)
// Теперь философ поест, выйдет из цикла. Если Set
// вызван дважды, то значение true.
philosopherEvents[i].Set();
// Разблокировать одного ожидающего. После него значение tableEvent в false.
tableEvent.Set();
// Если имеет true, не блокируется, а если false, то будет ждать Set от соседа.
philosopherEvents[i].WaitOne();
}
}
// Отдать вилки и разблокировать соседей.
void PutForks(int i)
{
tableEvent.WaitOne(); // Без гонок за вилками.
forks[Left(i)] = 0;
// Пробудить левого, а потом и правого соседа, либо AutoResetEvent в true.
philosopherEvents[LeftPhilosopher(i)].Set();
forks[Right(i)] = 0;
philosopherEvents[RightPhilosopher(i)].Set();
tableEvent.Set();
}To understand what is going on, let's consider the situation when a philosopher fails to take the forks; their actions will be as follows. They wait for access to the table. Upon receiving it, they attempt to take the forks. If unsuccessful, they give up access to the table (mutual exclusion). And they go through their 'turnstile' (AutoResetEvent) (initially, they are open). They loop back since they do not have the forks. They try to take them and stop at their 'turnstile'. Some luckier neighbor to the right or left, having finished eating, releases our philosopher by 'opening their turnstile'. Our philosopher passes through (and it closes behind them) for the second time. They try to take the forks a third time. Successfully. And they go through their turnstile to have lunch.
When there are occasional errors in such code (there always are), for instance, if a neighbor is incorrectly specified or if the same object is created AutoResetEvent for everyone (Enumerable.Repeat), then the philosophers will be waiting for developers, as debugging such code is quite a challenging task. Another issue with this solution is that it does not guarantee that any philosopher won't start starving.
Hybrid Solutions
We examined two approaches to synchronization: one where we stay in user mode and spin in a loop, and the other where we block the thread through the kernel. The first method is good for brief locks, while the second is suitable for long ones. Often, it's required to briefly wait for a variable change in a loop, and then block the thread when the wait is prolonged. This approach is implemented in so-called hybrid constructs. Here, we have the same constructs as in kernel mode, but now with a user-mode loop: SemaphoreSlim, ManualResetEventSlim and others. The most popular construct here is Monitor, as there is a well-known lock syntax in C#. Monitor It's the same semaphore with a maximum value of 1 (mutex), but with support for waiting in a loop, recursion, the Condition Variable pattern (which will be discussed below), and more. Let's look at a solution using it.
// Спрячем объект для Монитора от всех, чтобы без дедлоков.
private readonly object _lock = new object();
// Время ожидания потока.
private DateTime?[] _waitTimes = new DateTime?[philosophersAmount];
public void Run(int i, CancellationToken token)
{
while (true)
{
TakeForks(i);
eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
PutForks(i);
Think(i);
if (token.IsCancellationRequested) break;
}
}
// Наше сложное условие для Condition Variable паттерна.
bool CanIEat(int i)
{
// Если есть вилки:
if (forks[Left(i)] != 0 && forks[Right(i)] != 0)
return false;
var now = DateTime.Now;
// Может, если соседи не более голодные, чем текущий.
foreach(var p in new int[] {LeftPhilosopher(i), RightPhilosopher(i)})
if (_waitTimes[p] != null && now - _waitTimes[p] > now - _waitTimes[i])
return false;
return true;
}
void TakeForks(int i)
{
// Зайти в Монитор. То же самое: lock(_lock) {..}.
// Вызываем вне try, чтобы возможное исключение выбрасывалось выше.
bool lockTaken = false;
Monitor.Enter(_lock, ref lockTaken);
try
{
_waitTimes[i] = DateTime.Now;
// Condition Variable паттерн. Освобождаем лок, если не выполненно
// сложное условие. И ждем пока кто-нибудь сделает Pulse / PulseAll.
while (!CanIEat(i))
Monitor.Wait(_lock);
forks[Left(i)] = i + 1;
forks[Right(i)] = i + 1;
_waitTimes[i] = null;
}
finally
{
if (lockTaken) Monitor.Exit(_lock);
}
}
void PutForks(int i)
{
// То же самое: lock (_lock) {..}.
bool lockTaken = false;
Monitor.Enter(_lock, ref lockTaken);
try
{
forks[Left(i)] = 0;
forks[Right(i)] = 0;
// Освободить все потоки в очереди ПОСЛЕ вызова Monitor.Exit.
Monitor.PulseAll(_lock);
}
finally
{
if (lockTaken) Monitor.Exit(_lock);
}
}Here we are blocking the whole table for access to the forks again, but now we unlock all threads at once instead of just the neighbors when someone finishes eating. That is, first, someone eats and blocks the neighbors, and when this person finishes but wants to eat again right away, they go into blocking mode and wake their neighbors since their wait time is shorter.
This way, we avoid deadlocks and starvation of any philosopher. We use a loop for brief waiting and block the thread for longer waits. Unlocking everyone at once works slower than if only the neighbor were unlocked, as in the solution with AutoResetEvent, but the difference shouldn't be significant since threads should remain in user mode at first.
The lock syntax has some unpleasant surprises. It is recommended to use Monitor directly [Richter] [Eric Lippert]. One of them is that lock always exits from Monitor, even if there was an exception, and then another thread can change the state of the shared memory. In such cases, it is often better to enter a deadlock or safely terminate the program. Another surprise is that Monitor uses synchronization blocks (SyncBlock), which are present in all objects. Therefore, if an unsuitable object is chosen, it can easily lead to a deadlock (for example, if a lock is made on an interned string). Always use a hidden object for this.
The Condition Variable pattern allows for a more concise implementation of waiting for some complex condition. In .NET, it is incomplete in my opinion, as there should ideally be multiple queues on several variables (like in Posix Threads), not just one lock. This way, it could be applied to all philosophers. However, even in its current form, it helps reduce code.
Many philosophers or async / await
Alright, now we can effectively block threads. But what if we have many philosophers? 100? 10,000? For example, we received 100,000 requests to the web server. Creating a thread for each request would be costly, as so many threads won't run concurrently. Only as many as there are logical cores (I have 4) will be executed. All the others will just consume resources. One solution to this problem is the async / await pattern. The idea is that the function does not hold the thread if it needs to wait for something to continue. When that something happens, it resumes execution (but not necessarily in the same thread!). In our case, we will be waiting for forks.
SemaphoreSlim provides this with WaitAsync() method. Here’s the implementation using this pattern.
// Запуск такой же, как раньше. Где-нибудь в программе:
Task.Run(() => Run(i, cancelTokenSource.Token));
// Запуск философа.
// Ключевое слово async -- компилятор транслирует этот метот в асинхронный.
public async Task Run(int i, CancellationToken token)
{
while (true)
{
// await -- будем ожидать какого-то события.
await TakeForks(i);
// После await, продолжение возможно в другом потоке.
eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
// Может быть несколько событий для ожидания.
await PutForks(i);
Think(i);
if (token.IsCancellationRequested) break;
}
}
async Task TakeForks(int i)
{
bool hasForks = false;
while (!hasForks)
{
// Взаимоисключающий доступ к столу:
await _tableSemaphore.WaitAsync();
if (forks[Left(i)] == 0 && forks[Right(i)] == 0)
{
forks[Left(i)] = i+1;
forks[Right(i)] = i+1;
hasForks = true;
}
_tableSemaphore.Release();
// Будем ожидать, чтобы сосед положил вилки:
if (!hasForks)
await _philosopherSemaphores[i].WaitAsync();
}
}
// Ждем доступа к столу и кладем вилки.
async Task PutForks(int i)
{
await _tableSemaphore.WaitAsync();
forks[Left(i)] = 0;
// "Пробудить" соседей, если они "спали".
_philosopherSemaphores[LeftPhilosopher(i)].Release();
forks[Right(i)] = 0;
_philosopherSemaphores[RightPhilosopher(i)].Release();
_tableSemaphore.Release();
}The method is async / await transformed into a clever finite state machine that immediately returns its internal Task. Through it, you can wait for the completion of the method, cancel it, and perform all other operations that can be done with Task. Inside the method, the finite state machine controls execution. The essence is that if there is no delay, execution is synchronous; if there is, the thread is freed. For a better understanding of this, it’s best to look at this finite state machine. You can create chains of these async / await methods.
Let's test it. Working with 100 philosophers on a machine with 4 logical cores took 8 seconds. The previous solution with Monitor executed only the first 4 threads, while the rest didn't run at all. Each of these 4 threads was idle for about 2ms. The solution with async / await ran all 100, with each averaging a wait of 6.8 seconds. Of course, in real systems, a 6-second idle time is unacceptable, and it’s better not to handle that many requests this way. The Monitor solution turned out to be completely non-scalable.
Conclusion
As these small examples show, .NET supports many synchronization constructs. However, it is not always obvious how to use them. I hope this article has been helpful. For now, we will conclude, but there is still much more interesting content to cover, such as thread-safe collections, TPL Dataflow, Reactive programming, Software Transaction model, and more.
file — continuous reading of events from one or more local files;
- Flow Visualization:
- MSDN: , and more.
- [Richter] — CLR via C#, Jeffrey Richter
- [Eric Lippert] —
- Image — "Dance Among Swords," G. Semiradsky
Source: habr.com
