Vor einiger Zeit verbreitete sich ein Link zum Artikel "Moderne Speisephilosophen " über Ressourcen wie Reddit und HackerNews. Der Artikel ist interessant und zeigt verschiedene Lösungen für diese bekannte Aufgabe, die in modernem C ++ mithilfe eines aufgabenbasierten Ansatzes implementiert wurden. Wenn jemand diesen Artikel noch nicht gelesen hat, ist es sinnvoll, Zeit zu verbringen und ihn zu lesen.
Ich kann jedoch nicht sagen, dass mir die im Artikel vorgestellten Lösungen einfach und verständlich erschienen. Dies ist wahrscheinlich auf die Verwendung von Aufgaben zurückzuführen. Zu viele von ihnen werden über eine Vielzahl von Dispatchern / Serialisierern erstellt und versendet. Es ist also nicht immer klar, wo, wann und welche Aufgaben ausgeführt werden.
Darüber hinaus ist der aufgabenbasierte Ansatz nicht der einzige, der zur Lösung solcher Probleme möglich ist. Warum nicht sehen, wie die Aufgabe der "Essensphilosophen" durch die Modelle von Schauspielern und CSP gelöst wird?
Daher habe ich versucht, verschiedene Lösungen für dieses Problem sowohl mit Actors als auch mit CSP zu suchen und zu implementieren. Der Code für diese Lösungen befindet sich im Repository auf GitHub . Und unter dem Schneider, Erklärungen und Erklärungen, so dass jeder, der interessiert ist, unter Schnitt willkommen ist.
Ein paar gebräuchliche Worte
Ich hatte nicht das Ziel, die im Artikel "Moderne Speisephilosophen" gezeigten Entscheidungen genau zu wiederholen, zumal ich eine wichtige Sache grundsätzlich nicht mag: Tatsächlich unternimmt der Philosoph bei diesen Entscheidungen nichts. Er sagt nur "Ich will essen" und dann gibt ihm entweder jemand magisch Gabeln oder er sagt "Jetzt wird es nicht funktionieren."
Es ist klar, warum der Autor auf ein solches Verhalten zurückgegriffen hat: Es ermöglicht die Verwendung derselben Implementierung des „Philosophen“ in Verbindung mit verschiedenen Implementierungen der „Protokolle“. Es scheint mir jedoch persönlich interessanter zu sein, wenn der „Philosoph“ versucht, zuerst einen Stecker und dann einen anderen zu ziehen. Und wenn der "Philosoph" gezwungen ist, erfolglose Versuche zu unternehmen, die Gabeln zu fangen.
Genau diese Erkenntnisse der Aufgabe der „Essensphilosophen“ habe ich versucht zu machen. Gleichzeitig verwendeten einige Lösungen dieselben Ansätze wie im genannten Artikel (z. B. implementiert durch die Protokolle ForkLevelPhilosopherProtocol und WaiterFair).
Ich habe meine Entscheidungen auf der Grundlage von SObjectizer getroffen , was diejenigen, die meine Artikel bereits gelesen haben, wahrscheinlich nicht überraschen wird. Wenn jemand noch nichts von SObjectizer gehört hat, kurz gesagt: Dies ist eines der wenigen Live- und sich entwickelnden OpenSource "Actor Frameworks" für C ++ ( CAF und QP / C ++ können unter anderem auch erwähnt werden). Ich hoffe, dass die obigen Beispiele mit meinen Kommentaren auch für diejenigen klar genug sind, die mit SObjectizer nicht vertraut sind. Wenn nicht, beantworte ich gerne Fragen in den Kommentaren.
Schauspieler Lösungen
Wir werden die Diskussion der implementierten Lösungen mit denen beginnen, die auf den Akteuren basieren. Betrachten Sie zunächst die Implementierung der Edsger Dijkstra-Lösung, fahren Sie dann mit mehreren anderen Lösungen fort und sehen Sie, wie sich das Verhalten der einzelnen Lösungen unterscheidet.
Dijkstras Entscheidung
Edsger Dijkstra formulierte nicht nur die Aufgabe des „Essens von Phylophos“ (die Formulierung mit „Gabeln“ und „Spaghetti“ wurde von Tony Hoar geäußert), sondern schlug auch eine sehr einfache und schöne Lösung vor. Nämlich: Philosophen sollten nur die Gabeln greifen, um die Anzahl der Gabeln zu erhöhen, und wenn der Philosoph es geschafft hat, die erste Gabel zu nehmen, wird er sie nicht loslassen, bis er die zweite Gabel erhält.
Wenn ein Philosoph beispielsweise Gabeln mit den Nummern 5 und 6 verwenden muss, muss ein Philosoph zuerst eine Gabel mit der Nummer 5 nehmen. Nur dann kann er eine Gabel mit der Nummer 6 nehmen. Wenn sich also die Gabeln mit den niedrigeren Nummern links von den Philosophen befinden, sollte der Philosoph dies tun Nehmen Sie zuerst die linke Gabel und erst dann kann er die rechte Gabel nehmen.
Der letzte Philosoph auf der Liste, der sich mit Gabeln bei den Nummern (N-1) und 0 befassen muss, macht das Gegenteil: Er nimmt zuerst die rechte Gabel mit der Nummer 0 und dann die linke Gabel mit der Nummer (N-1).
Um diesen Ansatz umzusetzen, werden zwei Arten von Akteuren benötigt: eine für Gabeln und eine für Philosophen. Wenn der Philosoph essen möchte, sendet er eine Nachricht an den entsprechenden Gabelschauspieler, um die Gabel zu erfassen, und der Gabelschauspieler antwortet mit einer Antwortnachricht.
Der Code zur Implementierung dieses Ansatzes ist hier zu sehen.
Nachrichten
Bevor Sie über Schauspieler sprechen, müssen Sie sich die Botschaften ansehen, die die Schauspieler austauschen:
struct take_t { const so_5::mbox_t m_who; std::size_t m_philosopher_index; }; struct taken_t : public so_5::signal_t {}; struct put_t : public so_5::signal_t {};
Wenn der Schauspieler-Philosoph den Stecker nehmen möchte, sendet er die Nachricht take_t an den Gabelschauspieler, und der Gabelschauspieler antwortet mit der Nachricht taken_t . Wenn der Schauspieler-Philosoph mit dem Essen fertig ist und die Gabeln wieder auf den Tisch legen möchte, sendet er put_t-Nachrichten an die put_t Gabeln.
In der take_t Nachricht bezeichnet das Feld take_t die Mailbox (auch bekannt als mbox) des Philosophenschauspielers. Eine taken_t sollte an diese taken_t gesendet werden. Das zweite Feld von take_t wird in diesem Beispiel nicht verwendet. Wir benötigen es, wenn wir zu den Implementierungen von waiter_with_queue und waiter_with_timestamps gelangen.
Schauspieler Gabel
Jetzt können wir uns ansehen, was ein Gabelschauspieler ist. Hier ist sein Code:
class fork_t final : public so_5::agent_t { public : fork_t( context_t ctx ) : so_5::agent_t{ std::move(ctx) } {} void so_define_agent() override {
Jeder Akteur in SObjectizer muss von der Basisklasse agent_t . Was wir hier für den Typ fork_t .
Die Methode so_define_agent() wird in der Klasse so_define_agent() überschrieben. Dies ist eine spezielle Methode, die vom SObjectizer automatisch aufgerufen wird, wenn ein neuer Agent registriert wird. In der Methode so_define_agent() ist der so_define_agent() für die Arbeit in SObjectizer "konfiguriert": Der Startstatus ändert sich, die erforderlichen Nachrichten werden abonniert.
Jeder Akteur in SObjectizer ist eine Zustandsmaschine mit Zuständen (auch wenn ein Akteur nur einen Standardzustand verwendet). Der fork_t Akteur hat zwei Zustände: frei und genommen . Wenn sich ein Schauspieler in einem freien Zustand befindet, kann der Philosoph den Stecker „einfangen“. Und nach dem Erfassen der "Gabel" sollte der fork_t Darsteller in den aufgenommenen Zustand fork_t . Innerhalb der fork_t Klasse fork_t Zustände durch Instanzen von st_free und st_taken speziellen state_t Typ dargestellt.
Mit den Status können Sie eingehende Nachrichten auf verschiedene Arten verarbeiten. Im freien Zustand antwortet der Agent beispielsweise nur auf take_t und diese Reaktion ist sehr einfach: Der Zustand des Akteurs ändert sich und die Antwort taken_t :
st_free .event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } );
Alle anderen Nachrichten, einschließlich put_t im freien Zustand, werden einfach ignoriert.
Im Status " take_t verarbeitet der Akteur zwei Nachrichten, und selbst die Nachricht " take_t wird unterschiedlich verarbeitet:
st_taken .event( [this]( mhood_t<take_t> cmd ) { m_queue.push( cmd->m_who ); } ) .event( [this]( mhood_t<put_t> ) { if( m_queue.empty() ) this >>= st_free; else { const auto who = m_queue.front(); m_queue.pop(); so_5::send< taken_t >( who ); } } );
Der Handler für put_t am interessantesten: Wenn die Warteschlange der wartenden Philosophen leer ist, können wir zu free zurückkehren , aber wenn sie nicht leer ist, muss der erste von ihnen taken_t .
Philosoph Schauspieler
Der Code des Schauspieler-Philosophen ist viel umfangreicher, deshalb werde ich ihn hier nicht vollständig wiedergeben. Wir werden nur die wichtigsten Fragmente diskutieren.
Ein Schauspieler-Philosoph hat ein bisschen mehr Zustände:
state_t st_thinking{ this, "thinking.normal" }; state_t st_wait_left{ this, "wait_left" }; state_t st_wait_right{ this, "wait_right" }; state_t st_eating{ this, "eating" }; state_t st_done{ this, "done" };
Der Schauspieler beginnt seine Arbeit in einem denkenden Zustand und wechselt dann zu wait_left , dann zu wait_right und dann zu eat . Vom Essen kann ein Schauspieler zum Denken zurückkehren oder zum Handeln übergehen, wenn der Philosoph alles gegessen hat, was er haben sollte.
Das Zustandsdiagramm für einen Schauspieler-Philosophen kann wie folgt dargestellt werden:
Die Logik des Verhaltens des Schauspielers wird in der Implementierung seiner Methode so_define_agent() :
void so_define_agent() override {
Vielleicht ist der einzige Punkt, der besonders hervorgehoben werden sollte, der Ansatz, die Prozesse des „Denkens“ und „Essens“ nachzuahmen. Es gibt kein this_thread::sleep_for im Code des Schauspielers oder eine andere Möglichkeit, den aktuellen Arbeitsthread zu blockieren. Stattdessen werden ausstehende Nachrichten verwendet. Wenn ein Schauspieler beispielsweise in den stop_eating_t , sendet er sich eine ausstehende stop_eating_t Nachricht. Diese Nachricht wird an den SObjectizer-Timer gesendet und der Timer übermittelt die Nachricht an den Akteur, wenn die Zeit gekommen ist.
Durch die Verwendung von verzögerten Nachrichten können Sie alle Akteure im Kontext eines einzelnen Arbeitsthreads ausführen. Grob gesagt liest ein Thread Nachrichten aus einer Warteschlange und zieht den nächsten Nachrichtenhandler vom entsprechenden Empfängerakteur. Weitere Informationen zu Arbeitskontexten für Akteure werden nachstehend erörtert.
Ergebnisse
Die Ergebnisse dieser Implementierung können wie folgt aussehen (ein kleines Fragment):
Socrates: tttttttttttLRRRRRRRRRRRRRREEEEEEEttttttttLRRRRRRRRRRRRRREEEEEEEEEEEEE Plato: ttttttttttEEEEEEEEEEEEEEEEttttttttttRRRRRREEEEEEEEEEEEEEttttttttttLLL Aristotle: ttttEEEEEtttttttttttLLLLLLRRRREEEEEEEEEEEEttttttttttttLLEEEEEEEEEEEEE Descartes: tttttLLLLRRRRRRRREEEEEEEEEEEEEtttLLLLLLLLLRRRRREEEEEEttttttttttLLLLLL Spinoza: ttttEEEEEEEEEEEEEttttttttttLLLRRRREEEEEEEEEEEEEttttttttttRRRREEEEEEtt Kant: ttttttttttLLLLLLLRREEEEEEEEEEEEEEEttttttttttLLLEEEEEEEEEEEEEEtttttttt Schopenhauer: ttttttEEEEEEEEEEEEEttttttLLLLLLLLLEEEEEEEEEttttttttLLLLLLLLLLRRRRRRRR Nietzsche: tttttttttLLLLLLLLLLEEEEEEEEEEEEEttttttttLLLEEEEEEEEEttttttttRRRRRRRRE Wittgenstein: ttttEEEEEEEEEEtttttLLLLLLLLLLLLLEEEEEEEEEttttttttttttRRRREEEEEEEEEEEt Heidegger: tttttttttttLLLEEEEEEEEEEEEEEtttttttLLLLLLREEEEEEEEEEEEEEEtttLLLLLLLLR Sartre: tttEEEEEEEEEttttLLLLLLLLLLLLRRRRREEEEEEEEEtttttttLLLLLLLLRRRRRRRRRRRR
Lesen Sie dies wie folgt:
t bedeutet, dass der Philosoph "denkt";L bedeutet, dass der Philosoph erwartet, die linke Gabel zu erfassen (befindet sich im Zustand wait_left );R bedeutet, dass der Philosoph erwartet, die richtige Gabel zu erfassen (befindet sich im Status wait_right );E bedeutet, dass der Philosoph "isst".
Wir können sehen, dass Sokrates die Gabelung links erst nehmen kann, nachdem Sartre sie verschenkt hat. Danach wartet Sokrates, bis Platon die richtige Gabel loslässt. Erst danach kann Sokrates essen.
Eine einfache Entscheidung ohne Schiedsrichter (Kellner)
Wenn wir das Ergebnis von Dijkstras Entscheidung analysieren, werden wir sehen, dass Philosophen viel Zeit damit verbringen, auf die Erfassung von Gabeln zu warten. Was ist nicht gut, weil Diese Zeit kann auch zum Nachdenken verwendet werden. Nicht umsonst gibt es die Meinung, dass man mit leerem Magen viel interessantere und unerwartetere Ergebnisse erzielen kann;)
Schauen wir uns die einfachste Lösung an, bei der der Philosoph die erste erfasste Gabel zurückgibt, wenn er die zweite nicht erfassen kann (in dem oben erwähnten Artikel "Moderne Speisephilosophen" wird diese Lösung von ForkLevelPhilosopherProtocol implementiert).
Der Quellcode für diese Implementierung ist hier zu sehen, und der Code für den entsprechenden Philosophenakteur hier .
Nachrichten
Diese Lösung verwendet fast die gleichen Nachrichten:
struct take_t { const so_5::mbox_t m_who; std::size_t m_philosopher_index; }; struct busy_t : public so_5::signal_t {}; struct taken_t : public so_5::signal_t {}; struct put_t : public so_5::signal_t {};
Der einzige Unterschied ist das Vorhandensein des busy_t Signals. Die Schauspielergabel sendet dieses Signal als Antwort an den Philosophen-Schauspieler, wenn die Gabel bereits von einem anderen Philosophen erfasst wurde.
Schauspieler Gabel
Der Gabelschauspieler in dieser Lösung ist noch einfacher als in der Dijkstra-Lösung:
class fork_t final : public so_5::agent_t { public : fork_t( context_t ctx ) : so_5::agent_t( ctx ) { this >>= st_free; st_free.event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } ); st_taken.event( []( mhood_t<take_t> cmd ) { so_5::send< busy_t >( cmd->m_who ); } ) .just_switch_to< put_t >( st_free ); } private : const state_t st_free{ this }; const state_t st_taken{ this }; };
Hier müssen wir nicht einmal die Warteschlange wartender Philosophen halten.
Philosoph Schauspieler
Der Philosoph-Akteur in dieser Implementierung ähnelt dem der Dijkstra-Lösung, aber auch hier muss der Philosoph-Akteur busy_t verarbeiten, sodass das Zustandsdiagramm folgendermaßen aussieht:
Ebenso ist die gesamte Logik eines Schauspieler-Philosophen in so_define_agent() :
void so_define_agent() override { st_thinking .event< stop_thinking_t >( [=] { this >>= st_wait_left; so_5::send< take_t >( m_left_fork, so_direct_mbox(), m_index ); } ); st_wait_left .event< taken_t >( [=] { this >>= st_wait_right; so_5::send< take_t >( m_right_fork, so_direct_mbox(), m_index ); } ) .event< busy_t >( [=] { think( st_hungry_thinking ); } ); st_wait_right .event< taken_t >( [=] { this >>= st_eating; } ) .event< busy_t >( [=] { so_5::send< put_t >( m_left_fork ); think( st_hungry_thinking ); } ); st_eating .on_enter( [=] { so_5::send_delayed< stop_eating_t >( *this, eat_pause() ); } ) .event< stop_eating_t >( [=] { so_5::send< put_t >( m_right_fork ); so_5::send< put_t >( m_left_fork ); ++m_meals_eaten; if( m_meals_count == m_meals_eaten ) this >>= st_done; else think( st_normal_thinking ); } ); st_done .on_enter( [=] { completion_watcher_t::done( so_environment(), m_index ); } ); }
Im Allgemeinen ist dies fast derselbe Code wie in der Dijkstra-Lösung, mit Ausnahme busy_t Handler für busy_t .
Ergebnisse
Die Ergebnisse der Arbeit sehen anders aus:
Socrates: tttttttttL..R.....EEEEEEEEEEEEttttttttttR...LL..EEEEEEEttEEEEEE Plato: ttttEEEEEEEEEEEttttttL.....L..EEEEEEEEEEEEEEEttttttttttL....L.... Aristotle: ttttttttttttL..LR.EEEEEEtttttttttttL..L....L....R.....EEEEEEEEE Descartes: ttttttttttEEEEEEEEttttttttttttEEEEEEEEttttEEEEEEEEEEEttttttL..L.. Spinoza: ttttttttttL.....L...EEEEEEtttttttttL.L......L....L..L...R...R...E Kant: tttttttEEEEEEEttttttttL.L.....EEEEEEEEttttttttR...R..R..EEEEEtttt Schopenhauer: tttR..R..L.....EEEEEEEttttttR.....L...EEEEEEEEEEEEEEEEttttttttttt Nietzsche: tttEEEEEEEEEEtttttttttEEEEEEEEEEEEEEEttttL....L...L..L....EEEEEEE Wittgenstein: tttttL.L..L.....RR....L.....L....L...EEEEEEEEEEEEEEEtttttttttL. Heidegger: ttttR..R......EEEEEEEEEEEEEttttttttttR..L...L...L..L...EEEEtttttt Sartre: tttEEEEEEEtttttttL..L...L....R.EEEEEEEtttttEEEEtttttttR.....R..R.
Hier sehen wir ein neues Symbol, was bedeutet, dass der Schauspieler-Philosoph in "hungrigen Gedanken" ist.
Selbst in diesem kurzen Fragment kann man sehen, dass es lange Zeiträume gibt, in denen der Philosoph nicht essen kann. Dies liegt daran, dass diese Lösung vor dem Deadlock-Problem geschützt ist, jedoch keinen Schutz vor Hunger bietet.
Die Entscheidung mit dem Kellner und der Warteschlange
Die einfachste oben gezeigte Lösung ohne Schiedsrichter schützt nicht vor Hunger. Der oben erwähnte Artikel "Moderne Speisephilosophen" enthält eine Lösung für das Problem des Fastens in Form eines WaiterFair-Protokolls. Das Fazit ist, dass es einen Schiedsrichter gibt, an den sich Philosophen wenden, wenn sie essen wollen. Und der Kellner hat eine Reihe von Bewerbungen von Philosophen. Und der Philosoph bekommt die Gabeln nur, wenn beide Gabeln jetzt frei sind und es keinen der Nachbarn des Philosophen gibt, der sich an den Kellner in der Warteschlange gewandt hat.
Lassen Sie uns einen Blick darauf werfen, wie dieselbe Lösung für die Schauspieler aussehen könnte.
Den Quellcode für diese Implementierung finden Sie hier .
Trick
Am einfachsten wäre es, eine neue Reihe von Botschaften einzuführen, über die Philosophen mit dem Kellner kommunizieren könnten. Ich wollte aber nicht nur die bereits vorhandenen Nachrichten take_t (d. H. take_t , taken_t , busy_t , put_t ). Ich wollte auch, dass der gleiche Schauspieler-Philosoph wie in der vorherigen Lösung verwendet wird. Deshalb musste ich ein kniffliges Problem lösen: wie man den Schauspieler-Philosophen mit dem einzigen Schauspieler-Kellner kommunizieren lässt, dachte aber gleichzeitig, dass er direkt mit Schauspieler-Gabeln interagiert (die bereits verschwunden sind).
Dieses Problem wurde mit einem einfachen Trick gelöst: Ein Schauspieler-Kellner erstellt eine Reihe von mbox-s, auf die Philosophen-Schauspieler als Links zu mbox-Akteuren von Steckern verweisen. Gleichzeitig abonniert der Schauspieler-Kellner Nachrichten aus all diesen Mboxen (was in SObjectizer einfach zu implementieren ist, da SObjectizer nicht nur / so viele Modelle von Akteuren implementiert, sondern auch Pub / Sub sofort unterstützt wird). .
Im Code sieht es ungefähr so aus:
class waiter_t final : public so_5::agent_t { public : waiter_t( context_t ctx, std::size_t forks_count ) : so_5::agent_t{ std::move(ctx) } , m_fork_states( forks_count, fork_state_t::free ) {
Das heißt, Erstellen Sie zuerst einen Vektor von mbox-s für nicht vorhandene "Gabeln" und abonnieren Sie dann jede von ihnen. Ja, wir abonnieren, um zu wissen, auf welchen bestimmten Stecker sich die Anfrage bezieht.
Der eigentliche Handler für die eingehende Anforderung on_take_fork() ist die Methode on_take_fork() :
void on_take_fork( mhood_t<take_t> cmd, std::size_t fork_index ) {
Hier brauchten wir übrigens das zweite Feld aus der Nachricht take_t .
In on_take_fork() wir also die ursprüngliche Anforderung und den Index der Gabel, auf die sich die Anforderung bezieht. Daher können wir feststellen, ob der Philosoph nach einer linken oder einer rechten Gabel fragt. Und dementsprechend können wir sie anders verarbeiten (und wir müssen sie anders verarbeiten).
Da der Philosoph immer zuerst nach der linken Gabel fragt, müssen wir in diesem Moment alle notwendigen Überprüfungen durchführen. Und wir befinden uns möglicherweise in einer der folgenden Situationen:
- Beide Gabeln sind kostenlos und können dem Philosophen übergeben werden, der die Anfrage gesendet hat. In diesem Fall
taken_t wir taken_t Philosophen und markieren die rechte Gabel als reserviert, damit niemand anderes sie nehmen kann. - Gabeln können dem Philosophen nicht gegeben werden. Egal warum. Vielleicht sind einige von ihnen gerade beschäftigt. Oder in der Schlange steht einer der Nachbarn des Philosophen. Wie auch immer, wir stellen den Philosophen, der die Anfrage gesendet hat, in die Warteschlange, wonach wir
busy_t ihn busy_t .
Dank dieser Arbeitslogik kann der Philosoph, der taken_t für die linke Gabel erhalten hat, sicher eine take_t Anfrage für die rechte Gabel senden. Diese Anfrage wird sofort erfüllt, da Die Gabel ist bereits diesem Philosophen vorbehalten.
Ergebnisse
Wenn Sie die resultierende Lösung ausführen, sehen Sie Folgendes:
Socrates: tttttttttttL....EEEEEEEEEEEEEEttttttttttL...L...EEEEEEEEEEEEEtttttL. Plato: tttttttttttL....L..L..L...L...EEEEEEEEEEEEEtttttL.....L....L.....EEE Aristotle: tttttttttL.....EEEEEEEEEttttttttttL.....L.....EEEEEEEEEEEtttL....LL Descartes: ttEEEEEEEEEEtttttttL.L..EEEEEEEEEEEEtttL..L....L....L.....EEEEEEEEEE Spinoza: tttttttttL.....EEEEEEEEEttttttttttL.....L.....EEEEEEEEEEEtttL....LL Kant: ttEEEEEEEEEEEEEtttttttL...L.....L.....EEEEEttttL....L...L..L...EEEEE Schopenhauer: ttttL...L.....L.EEEEEEEEEEEEEEEEEtttttttttttL..L...L..EEEEEEEttttttt Nietzsche: tttttttttttL....L..L..L...L...L.....L....EEEEEEEEEEEEttL.....L...L.. Wittgenstein: tttttttttL....L...L....L....L...EEEEEEEttttL......L.....L.....EEEEEE Heidegger: ttttttL..L...L.....EEEEEEEEEEEEtttttL...L..L.....EEEEEEEEEEEttttttL. Sartre: ttEEEEEEEEEEEEEttttttttL.....L...EEEEEEEEEEEEttttttttttttL.....EEEEE
Sie können auf das Fehlen von Zeichen R achten R Dies liegt daran, dass bei einer richtigen Gabelanforderung keine Fehler oder Erwartungen auftreten können.
Eine weitere Entscheidung mit einem Schiedsrichter (Kellner)
In einigen Fällen zeigt die vorherige Lösung "waiter_with_queue" möglicherweise ähnliche Ergebnisse:
Socrates: tttttEEEEEEEEEEEEEEtttL.....LL...L....EEEEEEEEEttttttttttL....L.....EE Plato: tttttL..L..L....LL...EEEEEEEEEEEEEEEttttttttttttL.....EEEEEEEEEttttttt Aristotle: tttttttttttL..L...L.....L.....L....L.....EEEEEEEEEEEEtttttttttttL....L.. Descartes: ttttttttttEEEEEEEEEEttttttL.....L....L..L.....L.....L..L...L..EEEEEEEEtt Spinoza: tttttttttttL..L...L.....L.....L....L.....L..L..L....EEEEEEEEEEtttttttttt Kant: tttttttttL....L....L...L...L....L..L...EEEEEEEEEEEttttttttttL...L......E Schopenhauer: ttttttL....L..L...L...LL...L...EEEEEtttttL....L...L.....EEEEEEEEEttttt Nietzsche: tttttL..L..L....EEEEEEEEEEEEEttttttttttttEEEEEEEEEEEEEEEttttttttttttL... Wittgenstein: tttEEEEEEEEEEEEtttL....L....L..EEEEEEEEEtttttL..L..L....EEEEEEEEEEEEEEEE Heidegger: tttttttttL...L..EEEEEEEEttttL..L.....L...EEEEEEEEEtttL.L..L...L....L...L Sartre: ttttttttttL..L....L...L.EEEEEEEEEEEtttttL...L..L....EEEEEEEEEEtttttttttt
Sie können das Vorhandensein ausreichend langer Zeiträume erkennen, in denen Philosophen trotz freier Gabeln nicht essen können. Zum Beispiel sind die linken und rechten Gabeln für Kant lange Zeit frei, aber Kant kann sie nicht nehmen, weil Seine Nachbarn warten bereits in der Schlange. Welche warten auf ihre Nachbarn. Die auf ihre Nachbarn warten, etc.
Daher schützt die oben diskutierte Implementierung von waiter_with_queue vor Hunger in dem Sinne, dass der Philosoph früher oder später essen wird. Dies ist ihm garantiert. Aber Fastenperioden können ziemlich lang sein. Und die Ressourcennutzung ist manchmal möglicherweise nicht optimal.
Um dieses Problem zu lösen, habe ich eine andere Lösung implementiert, waiter_with_timestamp (den Code finden Sie hier ). Anstatt sich anzustellen, priorisieren sie Anfragen von Philosophen unter Berücksichtigung der Zeit ihres Fastens. Je länger der Philosoph hungert, desto mehr Priorität hat seine Bitte.
Wir werden den Code für diese Lösung nicht berücksichtigen, weil Im Großen und Ganzen ist die Hauptsache der gleiche Trick mit einer Reihe von mboxen für nicht vorhandene "Gabeln", die wir bereits im Gespräch über die Implementierung von waiter_with_queue besprochen haben.
Einige Implementierungsdetails, auf die ich aufmerksam machen möchte
Es gibt einige Details in den Implementierungen, die auf den Akteuren basieren, auf die ich achten möchte, weil Diese Details zeigen interessante Funktionen von SObjectizer.
Arbeitskontext für Schauspieler
In den betrachteten Implementierungen arbeiteten alle Hauptakteure ( fork_t , philosopher_t , waiter_t ) am Kontext eines gemeinsamen Arbeitsthreads. Das bedeutet überhaupt nicht, dass in SObjectizer alle Akteure nur an einem einzigen Thread arbeiten. In SObjectizer können Sie Akteure an verschiedene Kontexte binden, was beispielsweise im Funktionscode run_simulation() in der Lösung no_waiter_simple zu sehen ist.
Run_simulation-Code von no_waiter_simple void run_simulation( so_5::environment_t & env, const names_holder_t & names ) { env.introduce_coop( [&]( so_5::coop_t & coop ) { coop.make_agent_with_binder< trace_maker_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names, random_pause_generator_t::trace_step() ); coop.make_agent_with_binder< completion_watcher_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names ); const auto count = names.size(); std::vector< so_5::agent_t * > forks( count, nullptr ); for( std::size_t i{}; i != count; ++i ) forks[ i ] = coop.make_agent< fork_t >(); for( std::size_t i{}; i != count; ++i ) coop.make_agent< philosopher_t >( i, forks[ i ]->so_direct_mbox(), forks[ (i + 1) % count ]->so_direct_mbox(), default_meals_count ); }); }
In dieser Funktion werden zusätzliche Akteure der Typen trace_maker_t und trace_maker_t completion_watcher_t . Sie werden an individuellen Arbeitskontexten arbeiten. Dazu werden zwei Instanzen des Dispatchers vom Typ one_thread und die Akteure an diese Instanzen von Dispatchern gebunden. Dies bedeutet, dass diese Akteure als aktive Objekte arbeiten : Jeder besitzt seinen eigenen Arbeitsthread.
SObjectizer bietet eine Reihe verschiedener Dispatcher, die sofort verwendet werden können. In diesem Fall kann der Entwickler in seiner Anwendung so viele Instanzen von Dispatchern erstellen, wie der Entwickler benötigt.
Das Wichtigste ist jedoch, dass am Schauspieler nichts geändert werden muss, damit er an einem anderen Manager arbeitet. , fork_t , philosopher_t .
run_simulation no_waiter_simple_tp void run_simulation( so_5::environment_t & env, const names_holder_t & names ) { env.introduce_coop( [&]( so_5::coop_t & coop ) { coop.make_agent_with_binder< trace_maker_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names, random_pause_generator_t::trace_step() ); coop.make_agent_with_binder< completion_watcher_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names ); const auto count = names.size();
fork_t philosopher_t .
Modern dining philosophers , , :
void doEat() { eventLog_.startActivity(ActivityType::eat); wait(randBetween(10, 50)); eventLog_.endActivity(ActivityType::eat);
SObjectizer . , , . Aufgrund was?
, SObjectizer- : . agent_state_listener_t . , SObjectizer .
greedy_philosopher_t philosopher_t :
philosopher_t(...) ... { so_add_destroyable_listener( state_watcher_t::make( so_environment(), index ) ); }
state_watcher_t — .
state_watcher_t class state_watcher_t final : public so_5::agent_state_listener_t { const so_5::mbox_t m_mbox; const std::size_t m_index; state_watcher_t( so_5::mbox_t mbox, std::size_t index ); public : static auto make( so_5::environment_t & env, std::size_t index ) { return so_5::agent_state_listener_unique_ptr_t{ new state_watcher_t{ trace_maker_t::make_mbox(env), index } }; } void changed( so_5::agent_t &, const so_5::state_t & state ) override; };
state_watcher_t SObjectizer changed() . state_watcher_t::changed -.
state_watcher_t::changed void state_watcher_t::changed( so_5::agent_t &, const so_5::state_t & state ) { const auto detect_label = []( const std::string & name ) {...}; const char state_label = detect_label( state.query_name() ); if( '?' == state_label ) return; so_5::send< trace::state_changed_t >( m_mbox, m_index, state_label ); }
CSP
, . (no_waiter_dijkstra, no_waiter_simple, waiter_with_timestamps) std::thread SObjectizer- mchain- (, , CSP- ). , , CSP- ( take_t , taken_t , busy_t , put_t ).
CSP- "" . , std::thread .
.
: + take_t put_t . fork_process :
void fork_process( so_5::mchain_t fork_ch ) {
fork_process : , - .
fork_process — "" , . receive() :
so_5::receive( so_5::from( fork_ch ), [&]( so_5::mhood_t<take_t> cmd ) {...}, [&]( so_5::mhood_t<put_t> ) {...} );
SObjectizer- receive() . . . , . , .
-. fork_t . , , .
philosopher_process . , .
philosopher_process oid philosopher_process( trace_maker_t & tracer, so_5::mchain_t control_ch, std::size_t philosopher_index, so_5::mbox_t left_fork, so_5::mbox_t right_fork, int meals_count ) { int meals_eaten{ 0 }; random_pause_generator_t pause_generator;
:
void philosopher_process( trace_maker_t & tracer, so_5::mchain_t control_ch, std::size_t philosopher_index, so_5::mbox_t left_fork, so_5::mbox_t right_fork, int meals_count )
.
SObjectizer- , , Actor-. :
tracer.thinking_started( philosopher_index, thinking_type_t::normal );
tracer , .
control_ch , philosopher_done_t , , . .
left_fork right_fork . take_t put_t . , mbox_t mchain_t ?
! , . , mchain — - mbox-, mchain- mbox_t .
, :
int meals_eaten{ 0 }; random_pause_generator_t pause_generator; auto self_ch = so_5::create_mchain( control_ch->environment() );
— self_ch . , .
. Das heißt, , .
, , this_thread::sleep_for .
, :
so_5::send< take_t >( left_fork, self_ch->as_mbox(), philosopher_index );
take_t . mbox_t , self_ch mchain_t . as_mbox() .
receive() :
so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) {...} );
taken_t . . , .
- , philosopher_process . receive() :
so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) { ... so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) {...} ); ... } );
- .
run_simulation() , . CSP- run_simulation() . , , ( ).
run_simulation void run_simulation( so_5::environment_t & env, const names_holder_t & names ) noexcept { const auto table_size = names.size(); const auto join_all = []( std::vector<std::thread> & threads ) { for( auto & t : threads ) t.join(); }; trace_maker_t tracer{ env, names, random_pause_generator_t::trace_step() };
, run_simulation() - . .
. :
std::vector< so_5::mchain_t > fork_chains; std::vector< std::thread > fork_threads( table_size ); for( std::size_t i{}; i != table_size; ++i ) { fork_chains.emplace_back( so_5::create_mchain(env) ); fork_threads[ i ] = std::thread{ fork_process, fork_chains.back() }; }
, , . . , join .
, .. join :
std::vector< std::thread > philosopher_threads( table_size ); for( std::size_t i{}; i != table_size - 1u; ++i ) { philosopher_threads[ i ] = philosopher_maker( i, i, i+1u ); } philosopher_threads[ table_size - 1u ] = philosopher_maker( table_size - 1u, table_size - 1u, 0u );
. :
so_5::receive( so_5::from( control_ch ).handle_n( table_size ), [&names]( so_5::mhood_t<philosopher_done_t> cmd ) { fmt::print( "{}: done\n", names[ cmd->m_philosopher_index ] ); } );
receive() table_size philosopher_done_t .
philosopher_done_t .
join :
join_all( philosopher_threads );
join . join , .. . receive() . join :
for( auto & ch : fork_chains ) so_5::close_drop_content( ch ); join_all( fork_threads );
.
noexcept
, run_simulation , noexcept . , exception-safety . — .
run_simulation ?
, . - exception-safety , . - , :
try { for( std::size_t i{}; i != table_size; ++i ) { fork_chains.emplace_back( so_5::create_mchain(env) ); fork_threads[ i ] = std::thread{ fork_process, fork_chains.back() }; } } catch( ... ) { for( std::size_t i{}; i != fork_chains.size(); ++i ) { so_5::close_drop_content( fork_chains[ i ] ); if( fork_threads[ i ].joinable() ) fork_threads[ i ].join(); } throw; }
, . Weil , . - :
struct fork_threads_stuff_t { std::vector< so_5::mchain_t > m_fork_chains; std::vector< std::thread > m_fork_threads; fork_threads_stuff_t( std::size_t table_size ) : m_fork_threads( table_size ) {} ~fork_threads_stuff_t() { for( std::size_t i{}; i != m_fork_chains.size(); ++i ) { so_5::close_drop_content( m_fork_chains[ i ] ); if( m_fork_threads[ i ].joinable() ) m_fork_threads[ i ].join(); } } void run() { for( std::size_t i{}; i != m_fork_threads.size(); ++i ) { m_fork_chains.emplace_back( so_5::create_mchain(env) ); m_fork_threads[ i ] = std::thread{ fork_process, m_fork_chains.back() }; } } } fork_threads_stuff{ table_size };
, (, Boost- ScopeExit-, GSL- finally() ).
. .
, exception-safety run_simulation() , run_simulation() , . , -. exception-safety run_simulation() noexcept , std::terminate . , .
, , , , . , join , join . .
()
, CSP- , .
.
fork_process , :
void fork_process( so_5::mchain_t fork_ch ) {
, fork_process , ( , ).
philosopher_process , , .
philosopher_process void philosopher_process( trace_maker_t & tracer, so_5::mchain_t control_ch, std::size_t philosopher_index, so_5::mbox_t left_fork, so_5::mbox_t right_fork, int meals_count ) { int meals_eaten{ 0 };
- philosopher_process philosopher_process . .
-, thinking_type . , , , "" .
-, busy_t . receive() :
so_5::receive( so_5::from( self_ch ).handle_n( 1u ), []( so_5::mhood_t<busy_t> ) { }, [&]( so_5::mhood_t<taken_t> ) { ... so_5::receive( so_5::from( self_ch ).handle_n( 1u ), []( so_5::mhood_t<busy_t> ) { }, [&]( so_5::mhood_t<taken_t> ) {...} );
, busy_t , , receive() , receive() . busy_t . , .. receive() busy_t . receive() busy_t .
CSP- , . (): waiter_with_queue, , waiter_with_timestamps. : mbox- , mbox- , mbox- .
CSP- , philosopher_process no_waiter_simple. mchain- , ?
, .
mchain- . , mchain-.
SObjectizer- select() , , , :
so_5::select( so_5::from_all(), case_(ch1, one_handler_1, one_handler_2, one_handler_3, ...), case_(ch2, two_handler_1, two_handler_2, two_handler_3, ...), ...);
select() , -. " " . CSP- .
.
, , take_t put_t . - . take_t put_t , :
struct extended_take_t final : public so_5::message_t { const so_5::mbox_t m_who; const std::size_t m_philosopher_index; const std::size_t m_fork_index; extended_take_t( so_5::mbox_t who, std::size_t philosopher_index, std::size_t fork_index ) : m_who{ std::move(who) } , m_philosopher_index{ philosopher_index } , m_fork_index{ fork_index } {} }; struct extended_put_t final : public so_5::message_t { const std::size_t m_fork_index; extended_put_t( std::size_t fork_index ) : m_fork_index{ fork_index } {} };
, so_5::message_t , ( ). , SObjectizer- .
, . take_t put_t , extended_take_t extended_put_t , .
mbox. :)
mbox- class wrapping_mbox_t final : public so_5::extra::mboxes::proxy::simple_t { using base_type_t = so_5::extra::mboxes::proxy::simple_t;
mbox-: so_5_extra , . so_5::abstract_message_box_t .
, wrapping_mbox_t . , . wrapping_mbox, mchain . waiter_process , , :
void waiter_process( so_5::mchain_t waiter_ch, details::waiter_logic_t & logic ) {
, , . waiter_with_timestamps .
: " philosopher_process mbox-?" , waiter_with_timestamps mbox, mchain.
, mchain. , .. so_5_extra mchain- ( ). mbox- mchain-.
Fazit
, , , CSP . , . , , . , - .
, SObjectizer-. , "" SObjectizer — 5.6, 5.5. , ( ). - , SO-5.6 ( ).
, !
PS. "" , . C++14.