Il y a quelque temps, un lien vers l'article "Les philosophes de la restauration moderne" s'est répandu sur des ressources comme Reddit et HackerNews. L'article est intéressant, il montre plusieurs solutions à cette tâche bien connue, implémentée en C ++ moderne en utilisant une approche basée sur les tâches. Si quelqu'un n'a pas encore lu cet article, alors il est logique de passer du temps et de le lire.
Cependant, je ne peux pas dire que les solutions présentées dans l'article me paraissent simples et compréhensibles. Cela est probablement dû à l'utilisation de tâches. Un trop grand nombre d'entre eux sont créés et distribués par le biais de divers répartiteurs / sérialiseurs. Il n'est donc pas toujours clair où, quand et quelles tâches sont effectuées.
De plus, l'approche basée sur les tâches n'est pas la seule possible pour résoudre de tels problèmes. Pourquoi ne pas voir comment la tâche des «philosophes de la restauration» est résolue à travers les modèles des acteurs et du CSP?
Par conséquent, j'ai essayé de rechercher et de mettre en œuvre plusieurs solutions à ce problème en utilisant à la fois Acteurs et CSP. Le code de ces solutions se trouve dans le référentiel sur GitHub . Et sous le cutter, des explications et des explications, donc toute personne intéressée, bienvenue sous le cut.
Quelques mots courants
Je n'avais pas pour objectif de répéter exactement les décisions présentées dans l'article même "Les philosophes de la restauration moderne" , d'autant plus que je déteste fondamentalement une chose importante: en fait, le philosophe ne fait rien sur ces décisions. Il dit seulement "je veux manger", puis soit quelqu'un lui donne des fourchettes comme par magie, soit il dit "maintenant ça ne marchera pas".
Il est clair pourquoi l'auteur a eu recours à un tel comportement: il permet d'utiliser la même implémentation du «philosophe» en conjonction avec différentes implémentations des «protocoles». Cependant, il me semble personnellement que c'est plus intéressant lorsque le «philosophe» essaie de prendre une prise d'abord, puis une autre. Et lorsque le "philosophe" est contraint de gérer les tentatives infructueuses de capture des fourches.
Ce sont précisément ces réalisations de la tâche des «philosophes culinaires» que j'ai tenté de réaliser. Dans le même temps, certaines solutions ont utilisé les mêmes approches que dans l'article mentionné (par exemple, implémentées par les protocoles ForkLevelPhilosopherProtocol et WaiterFair).
J'ai construit mes décisions sur la base de SObjectizer , ce qui ne surprendra probablement pas ceux qui ont lu mes articles auparavant. Si quelqu'un n'a pas encore entendu parler de SObjectizer, en bref: c'est l'un des rares "frameworks d'acteurs" OpenSource en développement pour C ++ ( CAF et QP / C ++ peuvent également être mentionnés entre autres). J'espère que les exemples ci-dessus avec mes commentaires seront suffisamment clairs même pour ceux qui ne connaissent pas SObjectizer. Sinon, je serai heureux de répondre aux questions dans les commentaires.
Solutions d'acteurs
Nous allons commencer la discussion des solutions mises en œuvre avec celles basées sur les Acteurs. Tout d'abord, considérez la mise en œuvre de la solution Edsger Dijkstra, puis passez à plusieurs autres solutions et voyez comment le comportement de chacune des solutions diffère.
Décision de Dijkstra
Edsger Dijkstra, non seulement a-t-il formulé la tâche de "manger du phylophos" (la formulation de celui-ci en utilisant des "fourchettes" et des "spaghettis" a été exprimée par Tony Hoar), il a également proposé une solution très simple et très belle. A savoir: les philosophes ne devraient saisir les fourchettes que dans le but d'augmenter le nombre de fourchettes, et si le philosophe a réussi à prendre la première fourchette, il ne la lâchera pas avant d'avoir reçu la deuxième fourchette.
Par exemple, si un philosophe a besoin d'utiliser des fourchettes avec les nombres 5 et 6, alors le philosophe doit d'abord prendre une fourchette du nombre 5. Ce n'est qu'après cela qu'il peut prendre une fourchette du nombre 6. Ainsi, si les fourchettes avec des nombres inférieurs sont à la gauche des philosophes, alors le philosophe devrait prenez d'abord la fourche gauche et alors seulement il peut prendre la fourche droite.
Le dernier philosophe de la liste, qui doit gérer les fourches aux numéros (N-1) et 0, fait le contraire: il prend d'abord la fourche droite avec le numéro 0, puis la fourche gauche avec le numéro (N-1).
Pour mettre en œuvre cette approche, deux types d'acteurs seront nécessaires: un pour les fourches et un pour les philosophes. Si le philosophe veut manger, il envoie un message à l'acteur fork correspondant pour capturer la fork, et l'acteur fork répond avec un message de réponse.
Le code pour implémenter cette approche peut être vu ici .
Des messages
Avant de parler des acteurs, vous devez regarder les messages que les acteurs échangeront:
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 {};
Lorsque l'acteur-philosophe veut prendre la prise, il envoie le message take_t à l' take_t fork, et l'acteur fork répond avec le message taken_t . Lorsque l'acteur-philosophe a fini de manger et veut remettre les fourchettes sur la table, il envoie des messages put_t à l' put_t fourches.
Dans le message take_t , le champ take_t désigne la boîte aux lettres (aka mbox) de l'acteur philosophe. Un message de réponse taken_t doit être envoyé à cette taken_t . Le deuxième champ de take_t n'est pas utilisé dans cet exemple, nous en aurons besoin lorsque nous arriverons aux implémentations de waiter_with_queue et waiter_with_timestamps.
Fourchette d'acteur
Maintenant, nous pouvons voir ce qu'est un acteur fork. Voici son 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 {
Chaque acteur dans SObjectizer doit être dérivé de la classe de base agent_t . Ce que nous voyons ici pour le type fork_t .
La méthode so_define_agent() est remplacée dans la classe so_define_agent() . Il s'agit d'une méthode spéciale, elle est automatiquement appelée par le SObjectizer lors de l'enregistrement d'un nouvel agent. Dans la méthode so_define_agent() , l' so_define_agent() est "configuré" pour fonctionner dans SObjectizer: l'état de démarrage change, les messages nécessaires sont souscrits.
Chaque acteur dans SObjectizer est une machine à états avec des états (même si un acteur n'utilise qu'un seul état par défaut). L'acteur fork_t a deux états: libre et pris . Lorsqu'un acteur est libre , la prise peut être «capturée» par le philosophe. Et après avoir capturé le "fork", l'acteur fork_t devrait passer dans l'état pris . Dans la classe fork_t états sont représentés par des instances de st_free et st_taken type spécial state_t .
Les états vous permettent de traiter les messages entrants de différentes manières. Par exemple, à l'état libre , l'agent ne répond qu'à take_t et cette réaction est très simple: l'état de l'acteur change et la réponse taken_t :
st_free .event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } );
Alors que tous les autres messages, y compris put_t à l'état libre , sont simplement ignorés.
À l'état pris , l'acteur traite deux messages, et même le message take_t il traite différemment:
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 ); } } );
Le gestionnaire de put_t plus intéressant put_t : si la file d'attente des philosophes en attente est vide, alors nous pouvons revenir à free , mais si elle n'est pas vide, alors le premier d'entre eux doit être envoyé à taken_t .
Acteur philosophe
Le code de l'acteur-philosophe est beaucoup plus volumineux, donc je ne le donnerai pas ici en entier. Nous ne discuterons que des fragments les plus significatifs.
Un acteur-philosophe a un peu plus d'états:
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" };
L'acteur commence son travail dans un état de réflexion , puis passe à wait_left , puis à wait_right , puis à manger . En mangeant, un acteur peut revenir à la pensée ou aller à l'action si le philosophe a mangé tout ce qu'il devrait avoir.
Le diagramme d'état d'un acteur-philosophe peut être représenté comme suit:
La logique du comportement de l'acteur est décrite dans l'implémentation de sa méthode so_define_agent() :
void so_define_agent() override {
Le seul point qui devrait être particulièrement souligné est peut-être l'approche consistant à imiter les processus de «penser» et de «manger». Il n'y a pas this_thread::sleep_for dans le code de l'acteur ou de toute autre manière pour bloquer le thread de travail actuel. À la place, les messages en attente sont utilisés. Par exemple, lorsqu'un acteur entre en état de manger , il s'envoie un message stop_eating_t attente. Ce message est transmis au temporisateur SObjectizer et le temporisateur remet le message à l'acteur le moment venu.
L'utilisation de messages différés vous permet d'exécuter tous les acteurs dans le contexte d'un seul thread de travail. En gros, un thread lit les messages d'une file d'attente et tire le gestionnaire de messages suivant de l'acteur destinataire correspondant. Plus d'informations sur les contextes de travail des acteurs seront discutées ci-dessous.
Résultats
Les résultats de cette implémentation peuvent ressembler à ceci (un petit fragment):
Socrates: tttttttttttLRRRRRRRRRRRRRREEEEEEEttttttttLRRRRRRRRRRRRRREEEEEEEEEEEEE Plato: ttttttttttEEEEEEEEEEEEEEEEttttttttttRRRRRREEEEEEEEEEEEEEttttttttttLLL Aristotle: ttttEEEEEtttttttttttLLLLLLRRRREEEEEEEEEEEEttttttttttttLLEEEEEEEEEEEEE Descartes: tttttLLLLRRRRRRRREEEEEEEEEEEEEtttLLLLLLLLLRRRRREEEEEEttttttttttLLLLLL Spinoza: ttttEEEEEEEEEEEEEttttttttttLLLRRRREEEEEEEEEEEEEttttttttttRRRREEEEEEtt Kant: ttttttttttLLLLLLLRREEEEEEEEEEEEEEEttttttttttLLLEEEEEEEEEEEEEEtttttttt Schopenhauer: ttttttEEEEEEEEEEEEEttttttLLLLLLLLLEEEEEEEEEttttttttLLLLLLLLLLRRRRRRRR Nietzsche: tttttttttLLLLLLLLLLEEEEEEEEEEEEEttttttttLLLEEEEEEEEEttttttttRRRRRRRRE Wittgenstein: ttttEEEEEEEEEEtttttLLLLLLLLLLLLLEEEEEEEEEttttttttttttRRRREEEEEEEEEEEt Heidegger: tttttttttttLLLEEEEEEEEEEEEEEtttttttLLLLLLREEEEEEEEEEEEEEEtttLLLLLLLLR Sartre: tttEEEEEEEEEttttLLLLLLLLLLLLRRRRREEEEEEEEEtttttttLLLLLLLLRRRRRRRRRRRR
Lisez ceci comme suit:
t indique que le philosophe "pense";L signifie que le philosophe s'attend à capturer la fourche gauche (est dans l'état wait_left );R signifie que le philosophe s'attend à capturer la fourche droite (est dans l'état wait_right );E signifie que le philosophe "mange".
On voit que Socrate ne peut prendre la fourche à gauche qu'après que Sartre l'ait cédée. Après quoi, Socrate attendra que Platon libère la bonne fourche. Ce n'est qu'après que Socrate pourra manger.
Une décision simple sans arbitre (serveur)
Si nous analysons le résultat de la décision de Dijkstra, nous verrons que les philosophes passent beaucoup de temps à attendre la capture des fourches. Ce qui n'est pas bon, car ce temps peut également être consacré à la réflexion. Ce n'est pas pour rien qu'il y a une opinion que si vous pensez à jeun, vous pouvez obtenir des résultats beaucoup plus intéressants et inattendus;)
Examinons la solution la plus simple dans laquelle le philosophe retourne la première fourchette capturée s'il ne peut pas capturer la seconde (dans l'article "Modern Dining philosophers" mentionné ci-dessus, cette solution est implémentée par ForkLevelPhilosopherProtocol).
Le code source de cette implémentation peut être vu ici , et le code de l'acteur philosophe correspondant ici .
Des messages
Cette solution utilise presque le même ensemble de messages:
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 {};
La seule différence est la présence du signal busy_t . L'acteur-fork envoie ce signal en réponse au philosophe-acteur si le fork est déjà capté par un autre philosophe.
Fourchette d'acteur
L'acteur fork de cette solution est encore plus simple que dans la solution de Dijkstra:
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 }; };
Ici, nous n'avons même pas besoin de garder la file d'attente des philosophes en attente.
Acteur philosophe
Le philosophe-acteur dans cette implémentation est similaire à celui de la solution de Dijkstra, mais ici le philosophe-acteur doit également traiter busy_t , donc le diagramme d'état ressemble à ceci:
De même, toute la logique d'un acteur-philosophe est définie dans 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 ); } ); }
En général, c'est presque le même code que dans la solution de Dijkstra, à l'exception de quelques gestionnaires pour busy_t .
Résultats
Les résultats du travail sont différents:
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.
Nous voyons ici un nouveau symbole, ce qui signifie que l'acteur-philosophe est dans «des pensées affamées».
Même dans ce court fragment, on peut voir qu'il y a de longues périodes de temps pendant lesquelles le philosophe ne peut pas manger. En effet, cette solution est protégée contre le problème de blocage, mais n'a pas de protection contre la famine.
La décision avec le serveur et la file d'attente
La solution la plus simple présentée ci-dessus sans arbitre ne protège pas contre la famine. L'article "Modern Dining Philosophers" mentionné ci-dessus contient une solution au problème du jeûne sous la forme d'un protocole WaiterFair. L'essentiel, c'est qu'il y a un arbitre (serveur), auquel les philosophes se tournent quand ils veulent manger. Et le serveur a une file d'attente d'applications de philosophes. Et le philosophe n'obtient les fourches que si les deux fourchettes sont libres maintenant, et qu'aucun des voisins du philosophe ne s'est tourné vers le serveur dans la file d'attente.
Voyons à quoi pourrait ressembler cette même solution pour les acteurs.
Le code source de cette implémentation peut être trouvé ici .
Trick
Le moyen le plus simple serait d'introduire un nouvel ensemble de messages à travers lequel les philosophes pourraient communiquer avec le serveur. Mais je voulais enregistrer non seulement l'ensemble de messages déjà existant (c'est-à-dire take_t , taken_t , busy_t , put_t ). Je voulais aussi que le même acteur-philosophe soit utilisé comme dans la solution précédente. Par conséquent, j'ai dû résoudre un problème délicat: comment faire communiquer l'acteur-philosophe avec le seul acteur-serveur, mais en même temps, j'ai pensé qu'il interagissait directement avec les acteurs-fourches (qui ont déjà disparu).
Ce problème a été résolu à l'aide d'une astuce simple: un acteur-serveur crée un ensemble de mbox-s, dont les liens sont donnés à des philosophe-acteurs sous forme de liens vers des mbox-s d'acteurs fork. Dans le même temps, l'acteur-serveur s'abonne aux messages de toutes ces mbox (ce qui est facilement implémenté dans SObjectizer, car SObjectizer est une implémentation non seulement / autant de modèles d'acteurs, mais aussi Pub / Sub est pris en charge hors de la boîte) .
Dans le code, cela ressemble à ceci:
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 ) {
C'est-à-dire Créez d'abord un vecteur de mbox-s pour les "fourches" inexistantes, puis abonnez-vous à chacune d'elles. Oui, nous nous abonnons pour savoir à quelle fiche particulière se rapporte la demande.
Le véritable gestionnaire de la demande entrante on_take_fork() est la méthode on_take_fork() :
void on_take_fork( mhood_t<take_t> cmd, std::size_t fork_index ) {
Au fait, c'est ici que nous avions besoin du deuxième champ du message take_t .
Ainsi, dans on_take_fork() nous avons la requête d'origine et l'index du fork auquel se rapporte la requête. Par conséquent, nous pouvons déterminer si le philosophe demande une fourche gauche ou une droite. Et, en conséquence, nous pouvons les traiter différemment (et nous devons les traiter différemment).
Puisque le philosophe demande toujours d'abord la fourche gauche, nous devons alors faire toutes les vérifications nécessaires en ce moment même. Et nous pouvons nous retrouver dans l'une des situations suivantes:
- Les deux fourchettes sont gratuites et peuvent être remises au philosophe qui a envoyé la demande. Dans ce cas, nous
taken_t philosophe et marquons la fourche droite comme réservée pour que personne d'autre ne puisse la prendre. - On ne peut pas donner de fourchettes au philosophe. Peu importe pourquoi. Peut-être que certains d'entre eux sont occupés en ce moment. Ou en ligne est l'un des voisins du philosophe. Quoi qu'il en soit, nous mettons le philosophe qui a envoyé la demande dans la file d'attente, après quoi nous lui
busy_t .
Grâce à cette logique de travail, le philosophe qui a reçu taken_t pour la fourche gauche peut en toute sécurité envoyer une demande take_t pour la fourche droite. Cette demande sera immédiatement satisfaite, la fourchette est déjà réservée à ce philosophe.
Résultats
Si vous exécutez la solution résultante, vous pouvez voir quelque chose comme:
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
Vous pouvez faire attention au manque de caractères R En effet, les échecs ou les attentes ne peuvent pas se produire sur une demande de fourche droite.
Une autre décision en utilisant un arbitre (serveur)
Dans certains cas, la solution waiter_with_queue précédente peut afficher des résultats similaires à celui-ci:
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
Vous pouvez voir la présence de périodes suffisamment longues où les philosophes ne peuvent pas manger, même en présence de fourchettes gratuites. Par exemple, les fourches gauche et droite pour Kant sont libres pendant longtemps, mais Kant ne peut pas les prendre, car ses voisins attendent déjà en ligne. Qui attendent leurs voisins. Qui attendent leurs voisins, etc.
Par conséquent, la mise en œuvre de waiter_with_queue discutée ci-dessus protège contre la famine dans le sens où tôt ou tard le philosophe mangera. Cela lui est garanti. Mais les périodes de jeûne peuvent être assez longues. Et l'utilisation des ressources peut parfois ne pas être optimale.
Afin de résoudre ce problème, j'ai implémenté une autre solution, waiter_with_timestamp (son code peut être trouvé ici ). Au lieu de faire la queue, ils priorisent les demandes des philosophes en tenant compte de l'heure de leur jeûne. Plus le philosophe a faim, plus sa demande est prioritaire.
Nous ne considérerons pas le code de cette solution, car dans l'ensemble, l'essentiel est la même astuce avec un ensemble de mbox pour les "fourches" inexistantes, dont nous avons déjà discuté dans la conversation sur la mise en œuvre de waiter_with_queue.
Quelques détails de mise en œuvre sur lesquels je voudrais attirer l'attention
Il y a plusieurs détails dans les implémentations basées sur les acteurs que je voudrais faire attention, car ces détails présentent des fonctionnalités intéressantes de SObjectizer.
Contexte de travail des acteurs
Dans les implémentations considérées, tous les principaux acteurs ( fork_t , philosopher_t , waiter_t ) ont travaillé sur le contexte d'un thread de travail commun. Ce qui ne signifie pas du tout que dans SObjectizer tous les acteurs travaillent sur un seul thread. Dans SObjectizer, vous pouvez lier des acteurs à différents contextes, ce qui peut être vu, par exemple, dans le code de la fonction run_simulation() dans la solution no_waiter_simple.
Run_simulation code de 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 ); }); }
Dans cette fonction, des acteurs supplémentaires des types trace_maker_t et completion_watcher_t . Ils travailleront sur des contextes de travail individuels. Pour ce faire, deux instances du répartiteur de type one_thread sont one_thread et les acteurs sont liés à ces instances de répartiteurs. Ce qui signifie que ces acteurs fonctionneront comme des objets actifs : chacun possédera son propre fil de travail.
SObjectizer fournit un ensemble de plusieurs répartiteurs différents qui peuvent être utilisés dès la sortie de la boîte. Dans ce cas, le développeur peut créer dans son application autant d'instances de répartiteurs que le développeur en a besoin.
, , . , 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 . , , . À cause de quoi?
, 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 . , .
. C'est-à-dire , .
, , 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; }
, . Parce que , . - :
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-.
Conclusion
, , , CSP . , . , , . , - .
, SObjectizer-. , "" SObjectizer — 5.6, 5.5. , ( ). - , SO-5.6 ( ).
, !
PS. "" , . C++14.