Lassen Sie uns anschauen, wie konkurrierendes und paralleles Programmieren in .NET funktioniert, am Beispiel des Problems der speisenden Philosophen. Der Plan ist folgender: von der Synchronisation von Threads/Prozessen bis zum Aktormodell (in den nächsten Teilen). Der Artikel kann nützlich sein, um ein erstes Verständnis zu erlangen oder um sein Wissen aufzufrischen.
Warum sollte man das überhaupt können? Transistoren erreichen ihre minimale Größe, das Moore'sche Gesetz stößt an die Lichtgeschwindigkeit und daher zeigt sich das Wachstum in der Anzahl, man kann mehr Transistoren herstellen. Gleichzeitig wächst die Datenmenge und die Benutzer erwarten sofortige Reaktionen von Systemen. In einer solchen Situation ist das "gewöhnliche" Programmieren, bei dem wir einen ausführenden Thread haben, nicht mehr effizient. Man muss irgendwie das Problem der gleichzeitigen oder konkurrierenden Ausführung lösen. Und das Problem existiert auf verschiedenen Ebenen: auf der Ebene von Threads, auf der Ebene von Prozessen, auf der Ebene von Maschinen im Netzwerk (verteilte Systeme). In .NET gibt es qualitativ hochwertige, bewährte Technologien zur schnellen und effektiven Lösung solcher Aufgaben.
Aufgabe
Edsger Dijkstra stellte dieses Problem seinen Schülern bereits 1965. Die etablierte Formulierung lautet wie folgt. Es gibt eine gewisse (gewöhnlich fünf) Anzahl von Philosophen und ebenso viele Gabeln. Sie sitzen an einem runden Tisch, die Gabeln zwischen ihnen. Die Philosophen können aus ihren Tellern mit unendlichem Essen essen, nachdenken oder warten. Um zu essen, muss ein Philosoph zwei Gabeln nehmen (der letzte teilt eine Gabel mit dem ersten). Gabel nehmen und ablegen sind zwei getrennte Aktionen. Alle Philosophen sind still. Die Aufgabe besteht darin, einen Algorithmus zu finden, sodass sie alle nachdenken und in den nächsten 54 Jahren satt sind.
Zuerst versuchen wir, dieses Problem durch die Nutzung eines gemeinsamen Raums zu lösen. Die Gabeln liegen auf dem gemeinsamen Tisch und die Philosophen nehmen sie einfach, wenn sie da sind, und legen sie wieder zurück. Hier entstehen Synchronisationsprobleme: wann genau sollen die Gabeln genommen werden? Was tun, wenn keine Gabeln vorhanden sind? und andere. Aber zuerst lassen Sie uns die Philosophen starten.
Um die Threads zu starten, verwenden wir den Thread-Pool über Task.Run Methode:
var cancelTokenSource = new CancellationTokenSource();
Action<int> create = (i) => RunPhilosopher(i, cancelTokenSource.Token);
for (int i = 0; i < philosophersAmount; i++)
{
int icopy = i;
// Die Aufgabe in die Warteschlange des Threadpools einfügen. Die Methode RunDeadlock wird nicht sofort gestartet,
// sondern wartet auf ihren Thread. Asynchrone Ausführung.
philosophers[i] = Task.Run(() => create(icopy), cancelTokenSource.Token);
}Der Threadpool wurde zur Optimierung der Erstellung und Löschung von Threads erstellt. Dieser Pool hat eine Warteschlange mit Aufgaben, und der CLR erstellt oder entfernt Threads abhängig von der Anzahl dieser Aufgaben. Ein Pool für alle AppDomainen. Man sollte diesen Pool fast immer verwenden, da man sich nicht mit der Erstellung, dem Löschen von Threads, ihren Warteschlangen usw. beschäftigen muss. Man kann auch ohne Pool arbeiten, aber dann muss man direkt verwenden Thread, was sinnvoll ist, wenn man die Priorität eines Threads ändern muss, wenn wir eine lange Operation für den Vordergrund-Thread haben usw.
Anders ausgedrückt, System.Threading.Tasks.Task Klasse ist dasselbe Thread, aber mit verschiedenen Annehmlichkeiten: die Möglichkeit, den Task nach einem Block anderer Tasks zu starten, sie aus Funktionen zurückzugeben, sie bequem abzubrechen usw. Sie sind erforderlich, um async/await-Konstruktionen (Task-based Asynchronous Pattern, syntaktischer Zucker zum Warten auf IO-Operationen) zu unterstützen. Darüber werden wir später sprechen.
CancelationTokenSource wird hier benötigt, damit der Thread selbst nach dem Signal des aufrufenden Threads beendet werden kann.
Synchronisationsprobleme
Blockierte Philosophen
Gut, wir können Threads erstellen, lass uns versuchen, zu Abend zu essen:
// Кто какие вилки взял. К примеру: 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();
}
}Hier versuchen wir zuerst, die linke und dann die rechte Gabel zu nehmen und wenn es klappt, essen wir und legen sie zurück. Das Nehmen einer Gabel ist atomar, d.h. zwei Threads können nicht gleichzeitig eine nehmen (falsch: der erste liest, dass die Gabel frei ist, der zweite auch, der erste nimmt, der zweite nimmt). Dafür Interlocked.CompareExchange, das mit einer Prozessoranweisung implementiert werden muss (TSL, XCHG), die einen Speicherbereich für atomare sequentielle Lese- und Schreibvorgänge sperrt. Ein SpinWait entspricht der Konstruktion while(true) nur mit ein wenig "Magie" — der Thread beansprucht die CPU (Thread.SpinWait), übergibt aber manchmal die Kontrolle an einen anderen Thread (Thread.Yield) oder schläft ein (Thread.Sleep).
Aber diese Lösung funktioniert nicht, da die Threads bald (bei mir innerhalb einer Sekunde) blockiert werden: Alle Philosophen nehmen ihre linke Gabel, aber nicht die rechte. Das Array forks hat dann die Werte: 1 2 3 4 5.
Auf der Abbildung ist die Blockierung von Threads (Deadlock) dargestellt. Grün bedeutet Ausführung, Rot Synchronisation, Grau bedeutet, dass der Thread schläft. Die Rauten kennzeichnen die Startzeit der Tasks.
Das Hungrige Philosophenproblem
Obwohl man zum Denken nicht besonders viel Essen braucht, kann Hunger jeden dazu bringen, die Philosophie aufzugeben. Versuchen wir, eine Situation des Hungernt in unserem Problem zu simulieren. Hunger ist, wenn ein Thread arbeitet, aber ohne wesentliche Arbeit, mit anderen Worten, es ist dasselbe wie ein Deadlock, nur dass der Thread jetzt nicht schläft, sondern aktiv nach Möglichkeiten sucht, etwas zu essen, aber es gibt kein Essen. Um häufige Blockierungen zu vermeiden, legen wir die Gabel zurück, wenn wir nicht in der Lage sind, eine andere zu nehmen.
// То же что и в 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 diesem Code ist es wichtig, dass zwei von vier Philosophen vergessen, ihre linke Gabel zurückzulegen. Dabei essen sie mehr und die anderen beginnen zu hungern, obwohl die Threads die gleiche Priorität haben. Hier hungern sie nicht ganz, da die schlechten Philosophen manchmal ihre Gabeln zurücklegen. Bei mir scheint es, dass gute Philosophen etwa fünfmal weniger essen als schlechte. Ein kleiner Fehler im Code führt dazu, dass die Leistung leidet. Es sollte auch erwähnt werden, dass es eine seltene Situation geben kann, in der alle Philosophen die linke Gabel nehmen, die rechte nicht, sie legen die linke ab, warten und nehmen die linke erneut usw. Diese Situation ist auch Hunger, die mehr wie ein gegenseitiger Deadlock aussieht. Mir ist es nicht gelungen, sie zu reproduzieren. Unten ist ein Bild für die Situation, als zwei schlechte Philosophen beide Gabeln genommen haben und zwei gute hungern.
Hier ist zu sehen, dass die Threads manchmal aufwachen und versuchen, eine Ressource zu erhalten. Zwei von vier Kernen tun nichts (grüner Graph oben).
Der Tod eines Philosophen
Und ein weiteres Problem, das das feierliche Essen der Philosophen unterbrechen kann, ist, wenn einer von ihnen plötzlich mit Gabeln in den Händen stirbt (und so auch beerdigt wird). Dann bleiben die Nachbarn ohne Mittagessen. Ein Beispielcode für diesen Fall können Sie selbst erfinden, zum Beispiel wird NullReferenceException ausgelöst, nachdem der Philosoph die Gabeln genommen hat. Übrigens wird die Ausnahme nicht behandelt und der aufrufende Code wird sie einfach nicht abfangen (dafür AppDomain.CurrentDomain.UnhandledException usw.). Daher sind Fehlerbehandler in den Threads selbst notwendig und müssen korrekt beendet werden.
Der Kellner
Wie können wir das Problem mit den gegenseitigen Sperren, dem Hunger und den Toden lösen? Lassen wir immer nur einen Philosophen zu den Gabeln, fügen wir eine gegenseitige Exklusivität (mutual exclusion) für diesen Ort hinzu. Wie macht man das? Nehmen wir an, dass neben den Philosophen ein Kellner steht, der einem einzelnen Philosophen erlaubt, die Gabeln zu nehmen. Wie gestalten wir diesen Kellner und wie werden die Philosophen ihn bitten? Interessante Fragen.
Der einfachste Weg ist, dass die Philosophen einfach ständig den Kellner bitten, Zugang zu den Gabeln zu bekommen. Das heißt, jetzt werden die Philosophen nicht neben der Gabel warten, sondern warten oder den Kellner bitten. Zunächst verwenden wir dafür nur den User Space, in dem wir keine Unterbrechungen verwenden, um irgendetwas aus dem Kernel aufzurufen (darüber später mehr).
Lösungen im Benutzerraum
Hier machen wir das gleiche wie zuvor mit einer Gabel und zwei Philosophen: Wir werden uns im Zyklus drehen und warten. Aber jetzt sind das alle Philosophen und es wird sozusagen nur eine Gabel geben, das heißt, man kann sagen, es wird nur der Philosoph essen, der diese "goldene Gabel" vom Kellner genommen hat. Dafür verwenden wir SpinLock.
private static SpinLock spinLock = new SpinLock(); // Unser "Kellner"
private void RunSpinLock(int i, CancellationToken token)
{
while (true)
{
// Gegenseitige Sperre durch busy waiting. Wir rufen bis try auf, um
// eine Ausnahme im Falle eines Fehlers im SpinLock zu werfen.
bool hasLock = false;
spinLock.Enter(ref hasLock);
try
{
// Hier kann nur ein Thread sein (mutual exclusion).
forks[Left(i)] = i + 1; // Wir nehmen die Gabel sofort, ohne zu warten.
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(); // Wir vermeiden das Problem mit dem Tod des Philosophen.
}
Think(i);
if (token.IsCancellationRequested)
break;
}
}SpinLock ist ein Sperrmechanismus, ganz grob gesagt, mit demselben while(true) { if (!lock) break; }, aber mit noch mehr "Magie" als in SpinWait (der dort verwendet wird). Jetzt kann er die Wartenden zählen, sie ein wenig beruhigen und vieles mehr. Kurz gesagt, er tut alles Mögliche zur Optimierung. Aber man muss bedenken, dass es sich immer noch um denselben aktiven Zyklus handelt, der Ressourcen des Prozessors verbraucht und einen Fluss aufrechterhält, der zu Hunger führen kann, wenn einer der Philosophen priorisiert wird, aber keine goldene Gabel hat (Priority Inversion Problem). Deshalb verwenden wir ihn nur für sehr, sehr kurze Änderungen im gemeinsamen Speicher, ohne irgendwelche externen Aufrufe, eingebettete Sperrungen und andere Überraschungen.
Abbildung für SpinLock. Die Threads „kämpfen“ ständig um die goldene Gabel. Es entstehen Ausfälle – im Bild hervorgehobener Bereich. Die Kerne werden nicht vollständig genutzt: Nur etwa 2/3 dieser vier Threads.
Eine andere Lösung wäre es hier, nur Interlocked.CompareExchange mit demselben aktiven Warten zu verwenden, wie im obigen Code dargestellt (in den hungernden Philosophen), aber das könnte, wie bereits erwähnt, theoretisch zu einer Blockierung führen.
Über Interlocked es sollte gesagt werden, dass dort nicht nur CompareExchange, sondern auch andere Methoden zum atomaren Lesen und Schreiben existieren. Und durch wiederholtes Ändern, falls ein anderer Thread seine Änderungen rechtzeitig eingeben kann (lesen 1, lesen 2, schreiben 2, schreiben 1 schlecht), kann es für komplexe Änderungen eines Wertes verwendet werden (Interlocked Anything Muster).
Lösungen im Kernmodus
Um den Ressourcenverbrauch im Zyklus zu vermeiden, schauen wir uns an, wie man einen Thread blockieren kann. Mit anderen Worten, setzen wir unser Beispiel fort und schauen, wie der Kellner den Philosophen beruhigt und ihn nur dann weckt, wenn es nötig ist. Zunächst betrachten wir, wie dies durch den Kernmodus des Betriebssystems gemacht werden kann. Alle Strukturen dort stellen sich oft als langsamer heraus als die im Benutzermodus. Mehrere Male langsamer, beispielsweise AutoResetEvent kann bis zu 53-mal langsamer sein SpinLock [Richter]. Aber damit können Prozesse über das gesamte System synchronisiert werden, unabhängig davon, ob sie verwaltet werden oder nicht.
Die Grundkonstruktion hier ist ein Semaphore, der von Dijkstra vor über einem halben Jahrhundert vorgeschlagen wurde. Ein Semaphore ist, vereinfacht gesagt, eine positive ganze Zahl, die von einem System verwaltet wird, sowie zwei Operationen darauf – erhöhen und verringern. Wenn das Verringern nicht möglich ist, also null, wird der aufrufende Thread blockiert. Wenn die Zahl von einem anderen aktiven Thread/Prozess erhöht wird, werden die Threads durchgelassen und der Semaphore wird um die durchgelassenen Zahlen verringert. Man kann sich Züge an einem engen Ort mit einem Semaphore vorstellen. .NET bietet mehrere Konstruktionen mit ähnlichen Funktionen an: AutoResetEvent, ManualResetEvent, Mutex und es selbst Semaphore. Wir werden AutoResetEvent, dies ist die einfachste dieser Konstruktionen: nur zwei Werte 0 und 1 (false, true). Ihre Methode WaitOne() blockiert den aufrufenden Thread, wenn der Wert 0 war, und wenn er 1 war, wird er auf 0 verringert und der Thread wird durchgelassen. Die Methode Set() erhöht auf 1 und lässt einen wartenden Thread durch, der dann wieder auf 0 verringert. Funktioniert wie ein Drehkreuz in der U-Bahn.
Wir machen die Lösung komplizierter und verwenden eine Sperre für jeden Philosophen, nicht für alle gleichzeitig. Das heißt, jetzt können mehrere Philosophen gleichzeitig da sein, nicht nur einer. Aber wir blockieren wieder den Zugang zum Tisch, um korrekt und vermeiden von Rennen (race conditions) die Gabeln zu nehmen.
// Для блокирования отдельного философа.
// Инициализируется: 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();
}Um zu verstehen, was hier passiert, betrachten wir den Fall, dass es dem Philosophen nicht gelungen ist, die Gabeln zu nehmen. Seine Handlungen werden dann so aussehen: Er wartet auf den Zugang zum Tisch. Nach Erhalt versucht er, die Gabeln zu nehmen. Es klappt nicht. Er gibt den Zugang zum Tisch zurück (gegenseitiger Ausschluss). Und passiert sein "Drehkreuz" (AutoResetEvent) (zu Beginn sind sie offen). Er gelangt wieder in eine Schleife, da er keine Gabeln hat. Er versucht, sie zu nehmen und bleibt an seinem "Drehkreuz" stehen. Ein glücklicherer Nachbar rechts oder links, der mit dem Essen fertig ist, entsperrt unseren Philosophen, "öffnet sein Drehkreuz". Unser Philosoph passiert es (und es schließt sich hinter ihm) zum zweiten Mal. Er versucht ein drittes Mal, die Gabeln zu nehmen. Erfolgreich. Und passiert sein Drehkreuz, um zu Mittag zu essen.
Wenn in solchem Code zufällige Fehler auftreten (die gibt es immer), zum Beispiel wenn der Nachbar falsch angegeben wird oder dass dasselbe Objekt AutoResetEvent für alle erstellt wird (Enumerable.Repeat), dann werden die Philosophen bereits auf die Entwickler warten, da die Fehlersuche in solchem Code ziemlich schwierig ist. Ein weiteres Problem mit dieser Lösung ist, dass sie nicht garantiert, dass irgendein Philosoph nicht anfängt zu hungern.
Hybride Lösungen
Wir haben zwei Ansätze zur Synchronisation betrachtet: den Benutzer-Modus, in dem wir in einer Schleife bleiben, und den Ansatz, bei dem wir den Thread über den Kernel blockieren. Die erste Methode eignet sich gut für kurze Sperren, die zweite für längere. Oft ist es notwendig, zunächst kurz auf eine Änderung der Variable in der Schleife zu warten und dann den Thread zu blockieren, wenn das Warten lange dauert. Dieser Ansatz wird in den sogenannten hybriden Konstruktionen realisiert. Hier gibt es die gleichen Konstruktionen wie im Kernel-Modus, jedoch jetzt mit einer Schleife im Benutzer-Modus: SemaphoreSlim, ManualResetEventSlim u.a. Die bekannteste Konstruktion hier ist Monitor, da es in C# ein allgemein bekanntes lock Syntax gibt. Monitor Es handelt sich um dasselbe Semaphore mit einem Maximalwert von 1 (Mutex), jedoch mit Unterstützung für das Warten in einer Schleife, Rekursion, das Condition-Variable-Muster (darüber später) und weitere Funktionen. Lassen Sie uns die Lösung damit betrachten.
// Спрячем объект для Монитора от всех, чтобы без дедлоков.
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);
}
}Hier blockieren wir erneut den gesamten Tisch für den Zugriff auf die Gabeln, aber jetzt entblockieren wir alle Threads auf einmal und nicht nur die Nachbarn, wenn jemand mit dem Essen fertig ist. Das heißt, zunächst isst jemand und blockiert die Nachbarn, und wenn dieser jemand fertig ist und sofort wieder essen möchte, geht er in die Blockierung und weckt seine Nachbarn, da seine Wartezeit kürzer ist.
So vermeiden wir Deadlocks und das Verhungern eines Philosophen. Wir verwenden eine Schleife für kurzes Warten und blockieren den Thread für längeres Warten. Das sofortige Entblockieren aller funktioniert langsamer, als wenn nur der Nachbar entblockiert wird, wie in der Lösung mit AutoResetEvent, aber der Unterschied sollte nicht groß sein, da die Threads zunächst im Benutzer-Modus bleiben sollten.
Der lock Syntax hat unangenehme Überraschungen. Es wird empfohlen, Monitor direkt [Richter] [Eric Lippert] zu verwenden. Eine davon ist, dass lock immer aus Monitor, selbst wenn eine Ausnahme aufgetreten ist, und dann kann ein anderer Thread den Zustand des gemeinsamen Speichers ändern. In solchen Fällen ist es oft besser, in einen Deadlock zu gehen oder das Programm auf sichere Weise zu beenden. Eine weitere Überraschung ist, dass Monitor Synchronisationsblöcke (SyncBlock), die in allen Objekten vorhanden sind, verwendet. Daher kann, wenn ein ungeeignetes Objekt ausgewählt wird, leicht ein Deadlock entstehen (zum Beispiel, wenn man ein Lock auf einen internierten String macht). Wir verwenden immer ein verstecktes Objekt dafür.
Das Condition Variable-Muster ermöglicht eine kürzere Implementierung des Wartens auf eine komplexe Bedingung. In .NET ist es meiner Meinung nach unvollständig, da es mehrere Warteschlangen für mehrere Variablen haben sollte (wie in Posix Threads) und nicht nur für ein Lock. So könnte man sie für alle Philosophen erstellen. Aber selbst in dieser Form ermöglicht es, den Code zu kürzen.
Viele Philosophen oder async / await
Gut, jetzt können wir Threads effektiv blockieren. Aber was ist, wenn wir viele Philosophen haben? 100? 10000? Zum Beispiel haben wir 100000 Anfragen an den Webserver erhalten. Für jede Anfrage einen Thread zu erstellen, wäre aufwendig, da so viele Threads nicht parallel ausgeführt werden können. Es werden nur so viele ausgeführt, wie es logische Kerne gibt (ich habe 4). Alle anderen würden einfach Ressourcen verbrauchen. Eine Lösung für dieses Problem ist das async / await-Muster. Die Idee ist, dass die Funktion keinen Thread blockiert, wenn sie auf etwas warten muss, um fortzufahren. Wenn das Warten abgeschlossen ist, wird die Ausführung wieder aufgenommen (aber nicht unbedingt im selben Thread!). In unserem Fall warten wir auf die Gabel.
SemaphoreSlim hat dafür WaitAsync() Methode. Hier ist die Implementierung mit Verwendung dieses Musters.
// Запуск такой же, как раньше. Где-нибудь в программе:
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();
}Die Methode wird async / await in einen raffinierten Endzustandsautomaten übersetzt, der sofort seinen internen Task. Über ihn kann man das Ende der Methode abwarten, sie abbrechen und alles andere tun, was man mit Task machen kann. Innerhalb der Methode kontrolliert der endliche Automat die Ausführung. Der Kern ist, dass die Ausführung synchron ist, wenn es keine Verzögerung gibt, und wenn es eine Verzögerung gibt, wird der Thread freigegeben. Um dies besser zu verstehen, sollte man sich diesen endlichen Automaten ansehen. Man kann Ketten aus diesen async / await Methoden erstellen.
Lass uns testen. Der Betrieb von 100 Philosophen auf einer Maschine mit 4 logischen Kernen, 8 Sekunden. Die vorherige Lösung mit Monitor führte nur die ersten 4 Threads aus, während die anderen überhaupt nicht ausgeführt wurden. Jeder dieser 4 Threads war etwa 2 ms untätig. Die Lösung mit async / await führte alle 100 aus, wobei jeder im Durchschnitt 6,8 Sekunden wartete. Natürlich ist eine Wartezeit von 6 Sekunden in realen Systemen inakzeptabel, und es ist besser, nicht so viele Anfragen so zu verarbeiten. Die Lösung mit dem Monitor stellte sich als überhaupt nicht skalierbar heraus.
Fazit
Wie aus diesen kleinen Beispielen ersichtlich ist, unterstützt .NET viele Synchronisationskonstrukte. Es ist jedoch nicht immer offensichtlich, wie man sie verwendet. Ich hoffe, dieser Artikel war hilfreich. Damit schließen wir für jetzt, aber es bleibt noch viel Interessantes zu besprechen, wie z.B. threadsichere Sammlungen, TPL Dataflow, reaktive Programmierung, Software-Transaktionsmodelle und vieles mehr.
Quellen
- Visualisierung von Threads:
- MSDN: , und vieles mehr.
- [Richter] — CLR via C#, Jeffrey Richter
- [Eric Lippert] —
- Bild — „Tanz zwischen den Schwertern“, G. Semiradsky
Quelle: habr.com
