Lassen Sie uns anhand des Problems der Speisephilosophen sehen, wie die gleichzeitige und parallele Programmierung in .Net funktioniert. Ein solcher Plan, von der Synchronisation von Threads / Prozessen bis zum Modell der Akteure (in den folgenden Teilen). Der Artikel kann für eine erste Bekanntschaft oder zur Auffrischung Ihres Wissens nützlich sein.
Warum das können? Transistoren erreichen ihre minimale Größe, Moores Gesetz beruht auf der Begrenzung der Lichtgeschwindigkeit, und daher wird ein Wachstum in der Menge beobachtet, mehr Transistoren können durchgeführt werden. Gleichzeitig wächst die Datenmenge und die Benutzer erwarten eine sofortige Reaktion der Systeme. In einer solchen Situation ist die „normale“ Programmierung, wenn wir einen ausführenden Thread haben, nicht mehr effektiv. Es ist notwendig, das Problem der gleichzeitigen oder wettbewerbsorientierten Ausführung irgendwie zu lösen. Darüber hinaus besteht dieses Problem auf verschiedenen Ebenen: auf der Ebene der Flüsse, auf der Ebene der Prozesse, auf der Ebene der Maschinen im Netzwerk (verteilte Systeme). .NET verfügt über hochwertige, bewährte Technologien zur schnellen und effektiven Lösung solcher Probleme.
Herausforderung
Edsger Dijkstra stellte seinen Schülern dieses Problem bereits 1965 vor. Der etablierte Wortlaut lautet wie folgt. Es gibt einige (normalerweise fünf) Philosophen und ebenso viele Gabeln. Sie sitzen am runden Tisch, Gabeln dazwischen. Philosophen können mit endlosem Essen von ihren Tellern essen, nachdenken oder warten. Um den Philosophen zu essen, müssen Sie zwei Gabeln nehmen (die letztere teilt die Gabel mit der ersten). Eine Gabel nehmen und setzen - zwei getrennte Aktionen. Alle Philosophen schweigen. Die Aufgabe besteht darin, einen solchen Algorithmus zu finden, den alle denken und auch nach 54 Jahren satt haben.
Versuchen wir zunächst, dieses Problem mithilfe des gemeinsam genutzten Speicherplatzes zu lösen. Die Gabeln liegen auf dem Tisch und die Philosophen nehmen sie einfach, wenn sie sind, und legen sie zurück. Es gibt Probleme mit der Synchronisation, wann genau die Stecker zu nehmen? Was tun, wenn kein Stecker vorhanden ist? und andere. Aber zuerst wollen wir die Philosophen starten.
Verwenden Sie zum Starten von Threads den Thread-Pool über die 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;
Thread-Pool erstellt, um die Erstellung und Löschung von Threads zu optimieren. Dieser Pool verfügt über eine Aufgabenwarteschlange, und die CLR erstellt oder löscht Threads abhängig von der Anzahl dieser Aufgaben. Ein Pool für alle AppDomains. Dieser Pool sollte fast immer benutzt werden, weil Sie müssen sich nicht um das Erstellen, Löschen von Threads, deren Warteschlangen usw. kümmern. Es ist ohne Pool möglich, aber dann müssen Sie Thread direkt verwenden. Dies ist ratsam, wenn Sie die Priorität eines Threads ändern müssen, wenn wir eine lange Operation haben, für den Vordergrund eines Threads usw.
Und die System.Threading.Tasks.Task Klasse macht es einfach, mit diesem Thread-Pool zu arbeiten (oder sogar darauf zu verzichten). Es ist eine asynchrone Operation. Grob gesagt ist dies der gleiche Thread , aber mit allen möglichen Annehmlichkeiten: Die Möglichkeit, Aufgaben nach einem Block anderer Aufgaben zu starten, sie von Funktionen zurückzugeben, sie bequem zu unterbrechen und vieles mehr. usw. Sie werden benötigt, um asynchrone / wartende Konstrukte zu unterstützen (aufgabenbasiertes asynchrones Muster, syntaktischer Zucker zum Warten auf den E / A-Betrieb). Wir werden noch einmal darüber sprechen.
CancelationTokenSource wird hier benötigt, damit der Thread selbst durch das Signal des aufrufenden Threads beendet werden kann.
Synchronisierungsprobleme
Blockierte Philosophen
Ok, wir können Threads erstellen. Versuchen wir, zu Mittag zu essen:
Hier versuchen wir zuerst, die linken und dann die rechten Gabeln zu nehmen, und wenn es funktioniert, dann essen wir und legen sie zurück. Das Nehmen einer Gabel ist atomar, d.h. Zwei Streams können nicht gleichzeitig einen nehmen (falsch: Der erste liest, dass der Stecker frei ist, der zweite auch, der erste nimmt, der zweite nimmt). Zu diesem XCHG Interlocked.CompareExchange , das mithilfe eines Prozessorbefehls ( TSL , XCHG ) implementiert werden muss, der ein Stück Speicher für atomares sequentielles Lesen und Schreiben blockiert. Und SpinWait entspricht einem while(true) -Konstrukt mit nur wenig "Magie" - der Thread nimmt den Prozessor auf ( Thread.SpinWait ), überträgt aber manchmal die Kontrolle auf einen anderen Thread ( Thread.Yeild ) oder schläft ein ( Thread.Sleep ).
Aber diese Lösung funktioniert nicht, weil Flüsse werden bald blockiert sein (für mich innerhalb einer Sekunde): Alle Philosophen nehmen ihre linke Gabel, aber nicht die rechte. Das Forks-Array hat dann folgende Werte: 1 2 3 4 5.
In der Abbildung blockierende Threads (Deadlock). Grün zeigt die Ausführung an, Rot zeigt die Synchronisation an und Grau zeigt den Ruhezustand an. Diamanten geben die Startzeit der Aufgabe an.
Der Hunger der Philosophen
Es ist zwar nicht notwendig, besonders viel über Essen nachzudenken, aber man muss jeden zwingen, die Philosophie aufzugeben. Versuchen wir, die Situation der Fastenströme in unserem Problem zu simulieren. Hunger ist, wenn der Strom funktioniert, aber ohne nennenswerte Arbeit, mit anderen Worten, es ist der gleiche Stillstand, nur jetzt schläft der Strom nicht, sondern sucht aktiv nach etwas zu essen, aber es gibt kein Essen. Um häufiges Blockieren zu vermeiden, setzen wir den Stecker wieder ein, wenn wir keinen anderen nehmen könnten.
In diesem Code ist es wichtig, dass zwei von vier Philosophen vergessen, ihre linke Gabel zu setzen. Und es stellt sich heraus, dass sie mehr essen, während andere anfangen zu verhungern, obwohl die Ströme die gleiche Priorität haben. Hier verhungern sie nicht wirklich, weil schlechte Philosophen legen manchmal ihre Gabeln zurück. Es stellt sich heraus, dass die Guten etwa fünfmal weniger essen als die Schlechten. Ein kleiner Fehler im Code führt also zu einem Leistungsabfall. Hier ist anzumerken, dass eine seltene Situation möglich ist, wenn alle Philosophen die linke Gabel nehmen, es gibt keine rechte, sie setzen die linke, warten, nehmen die linke wieder usw. Diese Situation ist auch Hunger, eher wie ein Stillstand. Ich konnte es nicht wiederholen. Unten sehen Sie ein Bild für eine Situation, in der zwei schlechte Philosophen beide Gabeln genommen haben und zwei gute Philosophen verhungern.
Hier können Sie sehen, dass Threads manchmal aufwachen und versuchen, eine Ressource zu erhalten. Zwei der vier Kerne tun nichts (die grüne Grafik oben).
Der Tod des Philosophen
Nun, ein weiteres Problem, das das herrliche Abendessen der Philosophen unterbrechen kann, ist, wenn einer von ihnen plötzlich mit Gabeln in den Händen stirbt (und sie werden ihn so begraben). Dann bleiben die Nachbarn ohne Mittagessen. Sie können selbst NullReferenceException Beispielcode für diesen Fall NullReferenceException Beispielsweise wird eine NullReferenceException ausgelöst, nachdem der Philosoph die Gabeln genommen hat. AppDomain.CurrentDomain.UnhandledException wird die Ausnahme nicht verarbeitet und der aufrufende Code fängt sie einfach nicht ab (dafür AppDomain.CurrentDomain.UnhandledException usw.). Daher sind Fehlerbehandlungsroutinen in den Threads selbst und mit der richtigen Beendigung erforderlich.
Kellner
Wie lösen wir dieses Problem mit Deadlocks, Hunger und Tod? Wir werden nur einem Philosophen erlauben, sich zu gabeln und den gegenseitigen Ausschluss von Flüssen für diesen Ort hinzuzufügen. Wie kann man das machen? Angenommen, ein Kellner steht neben den Philosophen, der einem Philosophen die Erlaubnis gibt, Gabeln zu nehmen. Wie machen wir diesen Kellner und wie stellen ihm Philosophen interessante Fragen?
Der einfachste Weg ist, wenn die Philosophen den Kellner einfach ständig um Zugang zu den Gabeln bitten. Das heißt, Jetzt warten Philosophen nicht auf einen Stecker in der Nähe, sondern warten oder fragen einen Kellner. Erstens verwenden wir hierfür nur User Space. Dabei verwenden wir keine Interrupts, um Prozeduren aus dem Kernel aufzurufen (dazu weiter unten).
User Space-Lösungen
Hier werden wir das Gleiche tun wie früher mit einer Gabel und zwei Philosophen, wir werden uns in einem Zyklus drehen und warten. Aber jetzt werden es alle Philosophen sein und als ob nur eine Gabel, d.h. Wir können sagen, dass es nur diesen Philosophen geben wird, der diese "goldene Gabel" vom Kellner genommen hat. Dafür verwenden wir SpinLock.
private static SpinLock spinLock = new SpinLock();
SpinLock ist ein Blocker, der grob gesagt dasselbe ist, while(true) { if (!lock) break; } while(true) { if (!lock) break; } , aber mit noch mehr "Magie" als in SpinWait (das dort verwendet wird). Jetzt weiß er, wie man diejenigen zählt, die warten, sie ein wenig einschläfert und vieles mehr. etc. Im Allgemeinen tut alles möglich, um zu optimieren. Wir müssen uns jedoch daran erinnern, dass dies immer noch derselbe aktive Zyklus ist, der Prozessorressourcen verbraucht und einen Thread beibehält, der zum Hunger führen kann, wenn einer der Philosophen Vorrang vor anderen hat, aber keine goldene Gabel hat (Priority Inversion-Problem). Daher verwenden wir es nur für sehr sehr kurze Änderungen im gemeinsam genutzten Speicher, ohne dass Aufrufe von Drittanbietern, verschachtelte Sperren usw. Überraschungen verursachen.
Abbildung für SpinLock . Bäche "kämpfen" ständig um die goldene Gabel. Fehler treten auf - in der Abbildung der ausgewählte Bereich. Die Kerne sind nicht voll ausgelastet: nur etwa 2/3 dieser vier Fäden.
Eine andere Lösung wäre, nur Interlocked.CompareExchange mit der gleichen aktiven Erwartung zu verwenden, wie im obigen Code gezeigt (bei hungernden Philosophen), aber dies könnte, wie bereits erwähnt, theoretisch zum Blockieren führen.
Über Interlocked Es ist erwähnenswert, dass es nicht nur CompareExchange , sondern auch andere Methoden zum atomaren Lesen UND Schreiben. Durch Wiederholen der Änderungen für den Fall, dass ein anderer Thread seine Änderungen vornehmen kann (Lesen 1, Lesen 2, Schreiben 2, Schreiben 1 ist schlecht), kann er für komplexe Änderungen eines Werts verwendet werden (Interlocked Anything-Muster).
Kernel-Modus-Lösungen
Um zu vermeiden, dass Ressourcen in einer Schleife verloren gehen, sehen wir uns an, wie Sie einen Stream blockieren können. Mit anderen Worten, wenn wir unser Beispiel fortsetzen, werden wir sehen, wie der Kellner den Philosophen einschläfert und ihn nur dann weckt, wenn es nötig ist. Lassen Sie uns zunächst sehen, wie dies im Kernel-Modus des Betriebssystems erfolgt. Alle Strukturen dort erweisen sich häufig als langsamer als die im Benutzerbereich. Mehrfach langsamer, zum Beispiel kann AutoResetEvent 53-mal langsamer sein als SpinLock [Richter]. Mit ihrer Hilfe können Sie Prozesse im gesamten System synchronisieren, ob verwaltet oder nicht.
Die Hauptkonstruktion hier ist das Semaphor, das Dijkstroy vor mehr als einem halben Jahrhundert vorgeschlagen hat. Ein Semaphor ist in einfachen Worten eine positive ganze Zahl, die von einem System gesteuert wird, und zwei Operationen daran - Erhöhen und Verringern. Wenn die Reduzierung nicht funktioniert, Null, wird der aufrufende Thread blockiert. Wenn die Anzahl durch einen anderen aktiven Thread / Prozess erhöht wird, werden die Threads übersprungen und das Semaphor verringert sich erneut um die Anzahl der übergebenen Threads. Sie können sich Züge in einem Engpass mit einem Semaphor vorstellen. .NET bietet verschiedene Designs mit ähnlichen Funktionen: AutoResetEvent , ManualResetEvent , Mutex und Semaphore . Wir werden AutoResetEvent , dies ist die einfachste dieser Konstruktionen: Nur zwei Werte sind 0 und 1 (false, true). Die WaitOne() -Methode blockiert den aufrufenden Thread, wenn der Wert 0 war, und wenn 1, wird er auf 0 gesenkt und übersprungen. Und die Set() -Methode erhöht sich auf 1 und überspringt eine Wartezeit, die sich wieder auf 0 senkt. Sie wirkt wie ein Drehkreuz in der U-Bahn.
Wir werden die Lösung komplizieren und das Schloss für jeden Philosophen und nicht für alle gleichzeitig verwenden. Das heißt, Jetzt kann es mehrere Philosophen gleichzeitig geben und nicht einen. Aber wieder blockieren wir den Zugang zum Tisch, um Gabeln richtig zu nehmen und Rennen zu vermeiden (Rennbedingungen).
Um zu verstehen, was hier passiert, betrachten Sie den Fall, in dem der Philosoph die Gabeln nicht genommen hat, dann werden seine Handlungen so sein. Er wartet auf den Zugang zum Tisch. Nachdem er es erhalten hat, versucht er die Gabeln zu nehmen. Hat nicht funktioniert. Er gewährt Zugang zum Tisch (gegenseitiger Ausschluss). Und es passiert sein "Drehkreuz" ( AutoResetEvent ) (zuerst sind sie geöffnet). Es tritt wieder in den Zyklus ein, weil Er hat keine Gabeln. Versucht sie zu nehmen und bleibt an seinem Drehkreuz stehen. Ein glücklicherer Nachbar rechts oder links, der mit dem Essen fertig ist, öffnet unseren Philosophen und "öffnet sein Drehkreuz". Unser Philosoph gibt es zum zweiten Mal (und er schließt sich dahinter). Versucht zum dritten Mal, die Gabeln zu nehmen. Viel Glück. Und geht an seinem Drehkreuz vorbei, um zu speisen.
Wenn ein solcher Code zufällige Fehler enthält (sie sind immer vorhanden), beispielsweise ein Nachbar falsch angegeben ist oder für alle das gleiche AutoResetEvent Objekt AutoResetEvent wird ( Enumerable.Repeat ), warten Philosophen auf die Entwickler, weil Fehler in einem solchen Code zu finden, ist eine ziemlich schwierige Aufgabe. Ein weiteres Problem bei dieser Lösung ist, dass sie nicht garantiert, dass ein Philosoph nicht verhungert.
Hybridlösungen
Wir haben zwei Ansätze zur Synchronisation untersucht, wenn wir im Benutzermodus bleiben und uns in einer Schleife drehen und wenn wir einen Thread durch den Kernel blockieren. Die erste Methode eignet sich für kurze Schlösser, die zweite für lange. Oft müssen Sie zuerst kurz warten, bis sich eine Variable in der Schleife ändert, und dann den Thread blockieren, wenn die Wartezeit lang ist. Dieser Ansatz wird in der sogenannten implementiert Hybrid-Designs. Es gibt die gleichen Konstrukte wie für den Kernel-Modus, aber jetzt mit einer Schleife im Benutzermodus: SemaphorSlim , ManualResetEventSlim usw. Die beliebteste Konstruktion hier ist Monitor , weil C # hat eine bekannte Sperrsyntax. Monitor ist das gleiche Semaphor mit einem Maximalwert von 1 (Mutex), aber mit Unterstützung für das Warten in einer Schleife, Rekursion, Muster der Bedingungsvariablen (siehe unten) usw. Schauen wir uns eine Lösung damit an.
Hier sperren wir wieder den gesamten Tisch für den Zugang zu den Gabeln, aber jetzt entsperren wir alle Bäche auf einmal und nicht die Nachbarn, wenn jemand mit dem Essen fertig ist. Das heißt, Zuerst isst und blockiert jemand die Nachbarn, und wenn dieser fertig ist, aber sofort wieder essen will, geht er ins Schloss und weckt seine Nachbarn, weil seine Wartezeit ist kürzer.
So vermeiden wir die Blockaden und den Hunger eines Philosophen. Wir verwenden eine Schleife für eine kurze Wartezeit und blockieren den Fluss für eine lange Wartezeit. Das Entsperren auf einmal funktioniert langsamer als wenn nur der Nachbar entsperrt würde, wie in der Lösung mit AutoResetEvent , aber der Unterschied sollte nicht groß sein, weil Threads sollten zuerst im Benutzermodus bleiben.
Die Syntaxsperre hält unangenehme Überraschungen bereit. Sie empfehlen die direkte Verwendung von Monitor [Richter] [Eric Lippert]. Eine davon ist, dass die lock Monitor immer beendet, auch wenn es eine Ausnahme gab, und dann kann ein anderer Thread den Status des gemeinsam genutzten Speichers ändern. In solchen Fällen ist es oft besser, zum Deadlock zu gehen oder das Programm irgendwie sicher abzuschließen. Eine weitere Überraschung ist, dass Monitor Synchronisationsblöcke ( SyncBlock ) verwendet, die sich in allen Objekten befinden. Wenn Sie also das falsche Objekt auswählen, können Sie leicht einen Deadlock erhalten (z. B. wenn Sie die internierte Zeichenfolge sperren). Wir verwenden dafür immer ein verstecktes Objekt.
Bedingungsvariables Muster ermöglicht es Ihnen, die Erwartung einer komplexen Bedingung präziser umzusetzen. In .NET ist es meiner Meinung nach unvollständig, weil Theoretisch sollte es mehrere Warteschlangen für mehrere Variablen geben (wie in Posix-Threads) und nicht für eine Sperre. Dann könnte man sie für alle Philosophen machen. Aber auch in dieser Form können Sie den Code reduzieren.
Viele Philosophen oder async / await
Ok, jetzt können wir Threads effektiv blockieren. Aber was ist, wenn wir viele Philosophen haben? 100? 10000? Zum Beispiel haben wir 100.000 Anfragen an einen Webserver erhalten. Das Erstellen eines Streams für jede Anforderung ist weil So viele Threads werden nicht parallel ausgeführt. Es werden nur so viele logische Kerne ausgeführt (ich habe 4). Und alle anderen werden einfach Ressourcen in Anspruch nehmen. Eine Lösung für dieses Problem ist das Async / Wait-Muster. Die Idee ist, dass eine Funktion keinen Stream enthält, wenn Sie warten müssen, bis er fortgesetzt wird. Und wenn sie dies tut, passiert etwas, sie setzt ihre Hinrichtung fort (aber nicht unbedingt im selben Thread!). In unserem Fall warten wir auf den Stecker.
SemaphoreSlim verfügt WaitAsync() über eine WaitAsync() -Methode. Hier ist eine Implementierung mit diesem Muster.
async / await , Task . , , Task. , , . , , , , . . async / await .
. 100 4 , 8 . Monitor 4 , . 4 2. async / await 100, 6.8 . , 6 . Monitor .
Fazit
, .NET . , , , . . , , , TPL Dataflow, Reactive , Software Transaction .
Quellen