Wohlgenährte Philosophen oder wettbewerbsfähige .NET-Programmierung

Sehen wir uns am Beispiel des Philosophers Dining Problem an, wie gleichzeitiges und paralleles Programmieren in .Net funktioniert. Der Plan ist dieser, von der Synchronisation der Threads/Prozesse bis hin zum Akteurmodell (in den folgenden Teilen). Der Artikel kann für das erste Kennenlernen oder zum Auffrischen Ihres Wissens nützlich sein.

Warum überhaupt? Transistoren erreichen ihre Mindestgröße, das Mooresche Gesetz beruht auf der Begrenzung der Lichtgeschwindigkeit und daher ist eine Zunahme der Anzahl zu beobachten, es können mehr Transistoren hergestellt werden. Gleichzeitig wächst die Datenmenge und die Nutzer erwarten eine sofortige Reaktion der Systeme. In einer solchen Situation ist die „normale“ Programmierung, wenn wir einen ausführenden Thread haben, nicht mehr effektiv. Sie müssen das Problem der gleichzeitigen oder gleichzeitigen Ausführung irgendwie lösen. Darüber hinaus besteht dieses Problem auf verschiedenen Ebenen: auf der Ebene der Threads, auf der Ebene der Prozesse, auf der Ebene der Maschinen im Netzwerk (verteilte Systeme). .NET verfügt über hochwertige und bewährte Technologien zur schnellen und effizienten Lösung solcher Probleme.

Aufgabe

Edsger Dijkstra stellte dieses Problem bereits 1965 seinen Studenten. Die etablierte Formulierung lautet wie folgt. Es gibt eine bestimmte (normalerweise fünf) Anzahl von Philosophen und die gleiche Anzahl von Gabeln. Sie sitzen an einem runden Tisch, Gabeln dazwischen. Philosophen können von ihren endlosen Tellern essen, nachdenken oder warten. Um einen Philosophen zu essen, muss man zwei Gabeln nehmen (die letzte teilt sich die Gabel mit der ersten). Das Aufheben und Ablegen einer Gabel sind zwei getrennte Aktionen. Alle Philosophen schweigen. Die Aufgabe besteht darin, einen solchen Algorithmus zu finden, dass auch nach 54 Jahren noch alle denken und satt sind.

Versuchen wir zunächst, dieses Problem durch die Nutzung eines gemeinsam genutzten Bereichs zu lösen. Die Gabeln liegen auf dem gemeinsamen Tisch und die Philosophen nehmen sie einfach, wenn sie da sind, und legen sie zurück. Hier gibt es Probleme mit der Synchronisierung. Wann genau sollten Surebets angenommen werden? Was ist, wenn es keine Gabel gibt? usw. Aber zuerst beginnen wir mit den Philosophen.

Um Threads zu starten, verwenden wir einen Thread-Pool 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;
    // Поместить задачу в очередь пула потоков. Метод RunDeadlock не запускаеться 
    // сразу, а ждет своего потока. Асинхронный запуск.
    philosophers[i] = Task.Run(() => create(icopy), cancelTokenSource.Token);
}

Der Thread-Pool ist darauf ausgelegt, das Erstellen und Löschen von Threads zu optimieren. Dieser Pool verfügt über eine Warteschlange mit Aufgaben und die CLR erstellt oder entfernt Threads abhängig von der Anzahl dieser Aufgaben. Ein Pool für alle AppDomains. Dieser Pool sollte fast immer genutzt werden, denn. Sie müssen sich nicht um das Erstellen, Löschen von Threads, deren Warteschlangen usw. kümmern. Es ist auch ohne Pool möglich, aber dann müssen Sie ihn direkt verwenden Thread, dies ist nützlich für Fälle, in denen Sie die Priorität eines Threads ändern müssen, wenn wir einen langen Vorgang haben, für einen Vordergrund-Thread usw.

Mit anderen Worten, System.Threading.Tasks.Task Klasse ist gleich Thread, aber mit allen möglichen Annehmlichkeiten: die Möglichkeit, eine Aufgabe nach einem Block anderer Aufgaben auszuführen, sie von Funktionen zurückzugeben, sie bequem zu unterbrechen und mehr. usw. Sie werden benötigt, um Async/Await-Konstruktionen zu unterstützen (Task-based Asynchronous Pattern, syntaktischer Zucker zum Warten auf IO-Operationen). Wir werden später darüber sprechen.

CancelationTokenSource hier wird es benötigt, damit sich der Thread auf das Signal des aufrufenden Threads selbst beenden kann.

Synchronisationsprobleme

Blockierte Philosophen

Okay, wir wissen, wie man Threads erstellt. Versuchen wir, zu Mittag 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 Gabel zu nehmen, dann die rechte Gabel, und wenn es klappt, dann essen wir und legen sie zurück. Eine Gabel zu nehmen ist atomar, d.h. Zwei Threads können nicht gleichzeitig einen übernehmen (falsch: Der erste liest, dass die Verzweigung frei ist, der zweite - auch, der erste nimmt, der zweite nimmt). Dafür Interlocked.CompareExchange, die mit einer Prozessoranweisung implementiert werden muss (TSL, XCHG), wodurch ein Teil des Speichers für atomares sequentielles Lesen und Schreiben gesperrt wird. Und SpinWait entspricht dem Konstrukt while(true) nur mit ein wenig „Magie“ – der Thread übernimmt den Prozessor (Thread.SpinWait), überträgt aber manchmal die Kontrolle an einen anderen Thread (Thread.Yeild) oder schläft ein (Thread.Sleep).

Aber diese Lösung funktioniert nicht, weil Die Flüsse sind bald (bei mir innerhalb einer Sekunde) blockiert: Alle Philosophen nehmen ihre linke Abzweigung, aber nicht die rechte. Das Forks-Array hat dann die Werte: 1 2 3 4 5.

In der Abbildung blockierende Threads (Deadlock). Grün – Ausführung, Rot – Synchronisierung, Grau – der Thread schläft. Die Rauten geben die Startzeit von Aufgaben an.

Der Hunger der Philosophen

Obwohl es nicht notwendig ist, besonders viel Essen zu denken, bringt der Hunger jeden dazu, die Philosophie aufzugeben. Versuchen wir, die Situation des Thread-Mangels in unserem Problem zu simulieren. Hunger liegt vor, wenn ein Thread läuft, aber ohne nennenswerte Arbeit, mit anderen Worten, es ist derselbe Deadlock, nur dass der Thread jetzt nicht schläft, sondern aktiv nach etwas zu essen sucht, aber es gibt kein Essen. Um häufiges Blockieren zu vermeiden, werden wir die Gabel zurücksetzen, wenn wir keine andere nehmen konnten.

// То же что и в 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)
    );
}

Das Wichtige an diesem Code ist, dass zwei von vier Philosophen vergessen, ihre linke Gabel abzulegen. Und es stellt sich heraus, dass sie mehr essen, während andere anfangen zu verhungern, obwohl die Fäden die gleiche Priorität haben. Hier hungern sie nicht völlig, denn. Schlechte Philosophen legen manchmal ihre Gabeln zurück. Es stellt sich heraus, dass gute Menschen etwa fünfmal weniger essen als schlechte. Ein kleiner Fehler im Code führt also zu einem Leistungsabfall. Es ist hier auch erwähnenswert, dass eine seltene Situation möglich ist, wenn alle Philosophen die linke Abzweigung nehmen, es keine rechte gibt, sie die linke setzen, warten, wieder die linke nehmen usw. Auch diese Situation ist eine Hungersnot, eher eine Sackgasse. Ich habe es nicht geschafft, es zu wiederholen. Unten ist ein Bild für eine Situation, in der zwei schlechte Philosophen beide Gabeln genommen haben und zwei gute verhungern.

Hier können Sie sehen, dass die Threads manchmal aufwachen und versuchen, die Ressource abzurufen. Zwei der vier Kerne tun nichts (grüne Grafik oben).

Tod eines Philosophen

Nun, ein weiteres Problem, das ein herrliches Abendessen unter Philosophen stören kann, ist, wenn einer von ihnen plötzlich mit Gabeln in der Hand stirbt (und sie ihn so begraben). Dann bleiben die Nachbarn ohne Abendessen. Sie können sich für diesen Fall selbst einen Beispielcode ausdenken, der beispielsweise verworfen wird NullReferenceException nachdem der Philosoph die Gabeln genommen hat. Übrigens wird die Ausnahme nicht behandelt und der aufrufende Code fängt sie nicht einfach ab (aus diesem Grund). AppDomain.CurrentDomain.UnhandledException usw.). Daher sind Fehlerhandler in den Threads selbst und mit ordnungsgemäßer Beendigung erforderlich.

Kellner

Okay, wie lösen wir dieses Stillstands-, Hunger- und Todesproblem? Wir erlauben nur einem Philosophen, die Gabeln zu erreichen, und fügen für diesen Ort einen gegenseitigen Ausschluss von Threads hinzu. Wie kann man das machen? Angenommen, ein Kellner steht neben den Philosophen und gibt jedem Philosophen die Erlaubnis, die Gabeln zu nehmen. Wie wir diesen Kellner machen und wie Philosophen ihn stellen werden, die Fragen sind interessant.

Der einfachste Weg ist, wenn die Philosophen den Kellner einfach ständig um Zugang zu den Gabeln bitten. Diese. Jetzt warten Philosophen nicht mehr auf eine Gabel in der Nähe, sondern warten oder fragen den Kellner. Zunächst nutzen wir dafür nur User Space, dabei verwenden wir keine Interrupts, um Prozeduren aus dem Kernel aufzurufen (dazu weiter unten).

Lösungen im Userspace

Hier machen wir das Gleiche wie früher mit einer Gabel und zwei Philosophen, wir drehen uns im Kreis und warten. Aber jetzt werden es alle Philosophen sein und sozusagen nur eine Abzweigung, d.h. Man kann sagen, dass nur der Philosoph essen wird, der dem Kellner diese „goldene Gabel“ abgenommen hat. Hierfür verwenden wir SpinLock.

private static SpinLock spinLock = new SpinLock();  // Наш "официант"
private void RunSpinLock(int i, CancellationToken token)
{
    while (true)
    {
        // Взаимная блокировка через busy waiting. Вызываем до try, чтобы
        // выбрасить исключение в случае ошибки в самом SpinLock.
        bool hasLock = false;
        spinLock.Enter(ref hasLock);
        try
        {
            // Здесь может быть только один поток (mutual exclusion).
            forks[Left(i)] = i + 1;  // Берем вилку сразу, без ожидания.
            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();  // Избегаем проблемы со смертью философа.
        }

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

SpinLock Dies ist ein Blocker, der grob gesagt das Gleiche hat while(true) { if (!lock) break; }, aber mit noch mehr „Magie“ als in SpinWait (was dort verwendet wird). Jetzt weiß er, wie man die Wartenden zählt, sie ein wenig einschläfert und vieles mehr. usw. Im Allgemeinen wird alles getan, um zu optimieren. Wir müssen uns jedoch daran erinnern, dass dies immer noch derselbe aktive Zyklus ist, der Prozessorressourcen verbraucht und den Fluss aufrechterhält, was zu einer Hungersnot führen kann, wenn einer der Philosophen höhere Priorität erhält als andere, aber keine goldene Abzweigung hat (Prioritätsumkehrproblem). . Daher verwenden wir es nur für sehr, sehr kurze Änderungen im gemeinsam genutzten Speicher, ohne Aufrufe Dritter, verschachtelte Sperren und andere Überraschungen.

Zeichnen für SpinLock. Die Streams „kämpfen“ ständig um die goldene Gabel. Es liegen Fehler vor – in der Abbildung der ausgewählte Bereich. Die Kerne werden nicht vollständig ausgelastet: nur etwa 2/3 durch diese vier Threads.

Eine andere Lösung wäre hier die Verwendung von only Interlocked.CompareExchange mit dem gleichen aktiven Warten wie im obigen Code (in den hungernden Philosophen), aber dies könnte, wie bereits gesagt, theoretisch zu einer Blockierung führen.

Про Interlocked Es sollte beachtet werden, dass es nicht nur gibt CompareExchange, aber auch andere Methoden zum atomaren Lesen UND Schreiben. Und wenn ein anderer Thread Zeit hat, seine Änderungen vorzunehmen (Lesen 1, Lesen 2, Schreiben 2, Schreiben 1 ist fehlerhaft), kann die Änderungswiederholung für komplexe Änderungen an einem einzelnen Wert verwendet werden (Interlocked Anything-Muster).

Kernel-Modus-Lösungen

Um die Verschwendung von Ressourcen in einer Schleife zu vermeiden, sehen wir uns an, wie wir einen Thread blockieren können. Mit anderen Worten: Lassen Sie uns in Fortsetzung unseres Beispiels sehen, wie der Kellner den Philosophen einschläfert und ihn nur dann aufweckt, wenn es nötig ist. Schauen wir uns zunächst an, wie dies über den Kernelmodus des Betriebssystems durchgeführt wird. Alle Strukturen dort sind oft langsamer als die im Userspace. Zum Beispiel um ein Vielfaches langsamer AutoResetEvent vielleicht 53-mal langsamer SpinLock [Richter]. Aber mit ihrer Hilfe können Sie Prozesse im gesamten System synchronisieren, ob verwaltet oder nicht.

Das grundlegende Konstrukt hier ist das von Dijkstra vor über einem halben Jahrhundert vorgeschlagene Semaphor. Ein Semaphor ist, einfach ausgedrückt, eine vom System verwaltete positive Ganzzahl und zwei Operationen darauf, Inkrementieren und Dekrementieren. Wenn es nicht gelingt, auf Null zu sinken, wird der aufrufende Thread blockiert. Wenn die Zahl durch einen anderen aktiven Thread/Prozess erhöht wird, werden die Threads übersprungen und das Semaphor erneut um die übergebene Zahl dekrementiert. Man kann sich Züge in einem Stau mit einem Semaphor vorstellen. .NET bietet mehrere Konstrukte mit ähnlicher Funktionalität: AutoResetEvent, ManualResetEvent, Mutex und ich Semaphore. Wir werden verwenden AutoResetEventDies ist die einfachste dieser Konstruktionen: nur zwei Werte 0 und 1 (falsch, wahr). Ihre Methode WaitOne() Blockiert den aufrufenden Thread, wenn der Wert 0 war, und wenn er 1 ist, senkt er ihn auf 0 und überspringt ihn. Eine Methode Set() Erhöht sich auf 1 und lässt einen Kellner durch, der wiederum auf 0 sinkt. Funktioniert wie ein U-Bahn-Drehkreuz.

Lassen Sie uns die Lösung verkomplizieren und die Sperre für jeden Philosophen verwenden und nicht für alle auf einmal. Diese. Jetzt kann es mehrere Philosophen gleichzeitig geben und nicht einen. Wir blockieren jedoch erneut den Zugriff auf den Tisch, um unter Vermeidung von Rennen (Rennbedingungen) korrekt Surebets anzunehmen.

// Для блокирования отдельного философа.
// Инициализируется: 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, stellen Sie sich den Fall vor, dass der Philosoph es nicht geschafft hat, die Gabeln zu nehmen, dann werden seine Handlungen wie folgt sein. Er wartet auf Zugang zum Tisch. Nachdem er es erhalten hat, versucht er, die Gabeln zu nehmen. Hat nicht funktioniert. Es gewährt Zugriff auf die Tabelle (gegenseitiger Ausschluss). Und passiert sein „Drehkreuz“ (AutoResetEvent) (sie sind zunächst geöffnet). Es kommt wieder in den Kreislauf, denn er hat keine Gabeln. Er versucht sie mitzunehmen und bleibt an seinem „Drehkreuz“ stehen. Ein glücklicherer Nachbar rechts oder links, der mit dem Essen fertig ist, schließt unseren Philosophen auf und „öffnet sein Drehkreuz“. Unser Philosoph besteht es (und es schließt sich dahinter) zum zweiten Mal. Er versucht zum dritten Mal, die Gabeln zu ergreifen. Viel Glück. Und er geht an seinem Drehkreuz vorbei, um zu speisen.

Wenn in einem solchen Code zufällige Fehler auftreten (sie sind immer vorhanden), wird beispielsweise ein Nachbar falsch angegeben oder dasselbe Objekt erstellt AutoResetEvent für alle (Enumerable.Repeat), dann werden die Philosophen auf die Entwickler warten, denn Fehler in einem solchen Code zu finden ist eine ziemlich schwierige Aufgabe. Ein weiteres Problem dieser Lösung besteht darin, dass sie nicht garantiert, dass nicht irgendein Philosoph verhungert.

Hybridlösungen

Wir haben uns zwei Timing-Ansätze angesehen: Wenn wir im Benutzermodus bleiben und in einer Schleife bleiben und wenn wir den Thread durch den Kernel blockieren. Die erste Methode eignet sich für kurze Schlösser, die zweite für lange. Oft ist es notwendig, zunächst kurz darauf zu warten, dass sich eine Variable in einer Schleife ändert, und dann den Thread zu blockieren, wenn die Wartezeit lang ist. Dieser Ansatz wird im sogenannten umgesetzt. Hybridstrukturen. Hier sind die gleichen Konstrukte wie für den Kernel-Modus, aber jetzt mit einer Benutzermodus-Schleife: SemaphorSlim, ManualResetEventSlim usw. Das beliebteste Design hier ist Monitor, Weil In C# gibt es ein bekanntes lock Syntax. Monitor Dies ist das gleiche Semaphor mit einem Maximalwert von 1 (Mutex), aber mit Unterstützung für das Warten in einer Schleife, Rekursion, das Bedingungsvariablenmuster (mehr dazu weiter unten) usw. Schauen wir uns eine Lösung damit an.

// Спрячем объект для Монитора от всех, чтобы без дедлоков.
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 wieder die gesamte Tabelle für den Zugriff auf die Forks, aber jetzt entsperren wir alle Threads auf einmal und nicht die Nachbarn, wenn jemand mit dem Essen fertig ist. Diese. Zuerst isst jemand und blockiert die Nachbarn, und wenn dieser jemand fertig ist, aber sofort wieder essen möchte, geht er ins Blockieren und weckt seine Nachbarn, weil. die Wartezeit ist kürzer.

So vermeiden wir Blockaden und das Verhungern mancher Philosophen. Wir verwenden eine Schleife für eine kurze Wartezeit und blockieren den Thread für eine lange Wartezeit. Das Entsperren aller auf einmal ist langsamer, als wenn nur der Nachbar entsperrt würde, wie bei der Lösung mit AutoResetEvent, aber der Unterschied sollte nicht groß sein, weil Threads müssen zunächst im Benutzermodus bleiben.

У lock Die Syntax birgt böse Überraschungen. Empfehlen Sie die Verwendung Monitor direkt [Richter] [Eric Lippert]. Einer davon ist dieser lock immer raus Monitor, selbst wenn es eine Ausnahme gab, in diesem Fall könnte ein anderer Thread den Status des gemeinsam genutzten Speichers ändern. In solchen Fällen ist es oft besser, in einen Deadlock zu gehen oder das Programm auf irgendeine sichere Weise zu beenden. Eine weitere Überraschung ist, dass Monitor Synchronisierungsblöcke verwendet (SyncBlock), die in allen Objekten vorhanden sind. Wenn daher ein ungeeignetes Objekt ausgewählt wird, kann es leicht zu einem Deadlock kommen (z. B. wenn Sie eine internierte Zeichenfolge sperren). Wir verwenden hierfür das immer versteckte Objekt.

Mit dem Muster „Bedingungsvariable“ können Sie die Erwartung einer komplexen Bedingung prägnanter umsetzen. 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 einen Lok. Dann könnte man sie für alle Philosophen machen. Aber auch in dieser Form können Sie den Code reduzieren.

viele Philosophen bzw async / await

Okay, jetzt können wir Threads effektiv blockieren. Aber was ist, wenn wir viele Philosophen haben? 100? 10000? Beispielsweise haben wir 100000 Anfragen an den Webserver erhalten. Es wird einen Aufwand verursachen, für jede Anfrage einen Thread zu erstellen, weil so viele Threads werden nicht parallel laufen. Es werden nur so viele ausgeführt, wie es logische Kerne gibt (ich habe 4). Und alle anderen werden nur Ressourcen wegnehmen. Eine Lösung für dieses Problem ist das Async/Await-Muster. Die Idee dahinter ist, dass die Funktion den Thread nicht hält, wenn sie darauf warten muss, dass etwas fortgesetzt wird. Und wenn es etwas tut, setzt es seine Ausführung fort (aber nicht unbedingt im selben Thread!). In unserem Fall werden wir auf die Abzweigung warten.

SemaphoreSlim hat dafür WaitAsync() Methode. Hier ist eine Implementierung, die dieses Muster verwendet.

// Запуск такой же, как раньше. Где-нибудь в программе:
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();
}

Methode mit async / await wird in eine knifflige Zustandsmaschine übersetzt, die ihr Inneres sofort zurückgibt Task. Dadurch können Sie auf den Abschluss der Methode warten, sie abbrechen und alles andere tun, was Sie mit Task tun können. Innerhalb der Methode steuert die Zustandsmaschine die Ausführung. Das Fazit lautet: Wenn es keine Verzögerung gibt, ist die Ausführung synchron, und wenn ja, wird der Thread freigegeben. Um dies besser zu verstehen, ist es besser, sich diese Zustandsmaschine anzusehen. Daraus können Sie Ketten erstellen async / await Methoden.

Lasst uns testen. Arbeit von 100 Philosophen an einer Maschine mit 4 logischen Kernen, 8 Sekunden. Die vorherige Lösung mit Monitor führte nur die ersten 4 Threads aus und der Rest lief überhaupt nicht. Jeder dieser 4 Threads war etwa 2 ms lang im Leerlauf. Und die Async/Await-Lösung hat alle 100 ausgeführt, mit einer durchschnittlichen Wartezeit von jeweils 6.8 Sekunden. Natürlich ist in realen Systemen ein Leerlauf von 6 Sekunden inakzeptabel und es ist besser, nicht so viele Anfragen wie diese zu bearbeiten. Die Lösung mit Monitor erwies sich als überhaupt nicht skalierbar.

Abschluss

Wie Sie anhand dieser kleinen Beispiele sehen können, unterstützt .NET viele Synchronisationskonstrukte. Es ist jedoch nicht immer klar, wie man sie verwendet. Ich hoffe, dieser Artikel war hilfreich. Dies ist vorerst das Ende, aber es bleiben noch viele interessante Dinge übrig, zum Beispiel threadsichere Sammlungen, TPL-Datenfluss, reaktive Programmierung, Software-Transaktionsmodell usw.

Quellen

• Strömungsvisualisierung: Parallelitätsvisualisierer
• MSDN: Threading, Asynchrone Programmiermuster und viele andere andere
• [Richter] – CLR über C#, Jeffrey Richter
• [Eric Lippert] - Über Schloss
• Quellcode
• Bild - „Tanz zwischen Schwertern“, G. Semiradsky

Source: habr.com