Filósofos gastronómicos "modernos" en C ++ a través de actores y CSP

Hace alg√ļn tiempo, un enlace al art√≠culo "Fil√≥sofos de la comida moderna" se extendi√≥ sobre recursos como Reddit y HackerNews. El art√≠culo es interesante, muestra varias soluciones a esta tarea conocida, implementada en C ++ moderno utilizando un enfoque basado en tareas. Si alguien a√ļn no ha le√≠do este art√≠culo, entonces tiene sentido pasar tiempo y leerlo.


Sin embargo, no puedo decir que las soluciones presentadas en el artículo me parecieron simples y comprensibles. Esto probablemente se deba al uso de tareas. Demasiados de ellos son creados y enviados a través de una variedad de despachadores / serializadores. Por lo tanto, no siempre está claro dónde, cuándo y qué tareas se realizan.


Adem√°s, el enfoque basado en tareas no es el √ļnico posible para resolver tales problemas. ¬ŅPor qu√© no ver c√≥mo se resuelve la tarea de los "fil√≥sofos gastron√≥micos" a trav√©s de los modelos de actores y CSP?


Por lo tanto, traté de buscar e implementar varias soluciones a este problema usando Actors y CSP. El código para estas soluciones se puede encontrar en el repositorio en GitHub . Y debajo del cortador, explicaciones y explicaciones, para que cualquiera que esté interesado, sea bienvenido.


Algunas palabras comunes


No ten√≠a el objetivo de repetir exactamente las decisiones que se muestran en el mismo art√≠culo "Fil√≥sofos de la cocina moderna" , especialmente porque fundamentalmente no me gusta una cosa importante: de hecho, el fil√≥sofo no hace nada en esas decisiones. √Čl solo dice "Quiero comer", y luego alguien le da tenedores m√°gicamente o dice "ahora no funcionar√°".


Está claro por qué el autor recurrió a tal comportamiento: permite el uso de la misma implementación del "filósofo" junto con diferentes implementaciones de los "protocolos". Sin embargo, me parece personalmente que es más interesante cuando el "filósofo" trata de tomar un tapón primero, luego otro. Y cuando el "filósofo" se ve obligado a manejar intentos fallidos de capturar los tenedores.


Precisamente estas realizaciones de la tarea de los "filósofos gastronómicos" fueron las que intenté hacer. Al mismo tiempo, algunas soluciones utilizaron los mismos enfoques que en el artículo mencionado (por ejemplo, implementado por los protocolos ForkLevelPhilosopherProtocol y WaiterFair).


Constru√≠ mis decisiones sobre la base de SObjectizer , que es poco probable que sorprenda a quienes leyeron mis art√≠culos antes. Si alguien a√ļn no ha o√≠do hablar de SObjectizer, en pocas palabras: este es uno de los pocos "marcos de actores" de OpenSource en vivo y en desarrollo para C ++ ( CAF y QP / C ++ tambi√©n se pueden mencionar entre otros). Espero que los ejemplos anteriores con mis comentarios sean lo suficientemente claros incluso para aquellos que no est√°n familiarizados con SObjectizer. Si no, estar√© encantado de responder preguntas en los comentarios.


Soluciones de actores


Comenzaremos la discusión de las soluciones implementadas con aquellas basadas en los actores. Primero, considere la implementación de la solución Edsger Dijkstra, luego pase a otras soluciones y vea cómo difiere el comportamiento de cada una de ellas.


La decisión de Dijkstra


Edsger Dijkstra, no solo formul√≥ la tarea de "comer phylophos" (Tony Hoar expres√≥ su formulaci√≥n utilizando "tenedores" y "spaghetti"), sino que tambi√©n propuso una soluci√≥n muy simple y hermosa. A saber: los fil√≥sofos solo deben agarrar los tenedores para aumentar el n√ļmero de tenedores, y si el fil√≥sofo logr√≥ tomar el primer tenedor, entonces no lo soltar√° hasta que reciba el segundo tenedor.


Por ejemplo, si un fil√≥sofo necesita usar tenedores con los n√ļmeros 5 y 6, entonces un fil√≥sofo primero debe tomar un tenedor del n√ļmero 5. Solo entonces puede tomar un tenedor del n√ļmero 6. Por lo tanto, si los tenedores con n√ļmeros m√°s bajos est√°n a la izquierda de los fil√≥sofos, entonces el fil√≥sofo debe primero tome el tenedor izquierdo y solo entonces puede tomar el tenedor derecho.


El √ļltimo fil√≥sofo de la lista, que tiene que lidiar con los tenedores en los n√ļmeros (N-1) y 0, hace lo contrario: primero toma el tenedor derecho con el n√ļmero 0, y luego el tenedor izquierdo con el n√ļmero (N-1).


Para implementar este enfoque, se requerirán dos tipos de actores: uno para los tenedores y otro para los filósofos. Si el filósofo quiere comer, envía un mensaje al actor tenedor correspondiente para capturar el tenedor, y el actor tenedor responde con un mensaje de respuesta.


El código para implementar este enfoque se puede ver aquí .


Mensajes


Antes de hablar sobre actores, debe mirar los mensajes que los actores intercambiar√°n:


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 {}; 

Cuando el actor-filósofo quiere desconectarse, envía el mensaje take_t al take_t fork, y el actor fork responde con el mensaje taken_t . Cuando el actor-filósofo termina de comer y quiere volver a poner los tenedores sobre la mesa, envía mensajes put_t a los tenedores put_t .


En el mensaje take_t , el campo take_t denota el buzón (también conocido como mbox) del actor filósofo. Se debe enviar un mensaje de respuesta taken_t a este taken_t . El segundo campo de take_t no se usa en este ejemplo, lo necesitaremos cuando lleguemos a las implementaciones de waiter_with_queue y waiter_with_timestamps.


Tenedor actor


Ahora podemos ver qué es un actor tenedor. Aquí está su código:


 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 { //     'free'. this >>= st_free; //   'free'    . st_free .event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } ); //   'taken'   . 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 ); } } ); } private : //    . const state_t st_free{ this, "free" }; const state_t st_taken{ this, "taken" }; //   . std::queue< so_5::mbox_t > m_queue; }; 

Cada actor en SObjectizer debe derivarse de la clase base agent_t . Lo que vemos aquí para el tipo fork_t .


El método so_define_agent() se reemplaza en la clase so_define_agent() . Este es un método especial, el SObjectizer lo llama automáticamente al registrar un nuevo agente. En el método so_define_agent() , el so_define_agent() está "configurado" para trabajar en SObjectizer: el estado de inicio cambia, los mensajes necesarios se suscriben.


Cada actor en SObjectizer es una máquina de estados con estados (incluso si un actor usa solo un estado predeterminado). El actor fork_t tiene dos estados: libre y tomado . Cuando un actor está en estado libre , el filósofo puede "capturar" el tapón. Y después de capturar el "tenedor", el actor fork_t debería pasar al estado tomado . Dentro de la clase fork_t estados están representados por instancias de st_free y st_taken tipo especial state_t .


Los estados le permiten procesar los mensajes entrantes de diferentes maneras. Por ejemplo, en el estado libre , el agente responde solo a take_t y esta reacción es muy simple: el estado del actor cambia y la respuesta taken_t :


 st_free .event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } ); 

Mientras que todos los dem√°s mensajes, incluido put_t en estado libre , simplemente se ignoran.


En el estado tomado , el actor procesa dos mensajes, e incluso el mensaje take_t procesa de manera diferente:


 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 ); } } ); 

El controlador para put_t más interesante put_t : si la cola de los filósofos en espera está vacía, entonces podemos volver a liberar , pero si no está vacía, entonces el primero de ellos debe enviarse taken_t .


Actor filósofo


El código del actor-filósofo es mucho más voluminoso, por lo que no lo daré aquí por completo. Discutiremos solo los fragmentos más significativos.


Un actor-filósofo tiene un poco más de estados:


 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" }; 

El actor comienza su trabajo en un estado de pensamiento , luego cambia a wait_left , luego a wait_right , luego a comer . De comer, un actor puede volver a pensar o puede hacerlo si el filósofo ha comido todo lo que debería haber comido.


El diagrama de estado para un actor-filósofo se puede representar de la siguiente manera:


imagen


La lógica del comportamiento del actor se describe en la implementación de su método so_define_agent() :


 void so_define_agent() override { //   thinking     stop_thinking. st_thinking .event( [=]( mhood_t<stop_thinking_t> ) { //    . this >>= st_wait_left; so_5::send< take_t >( m_left_fork, so_direct_mbox(), m_index ); } ); //        taken. st_wait_left .event( [=]( mhood_t<taken_t> ) { //     .   . this >>= st_wait_right; so_5::send< take_t >( m_right_fork, so_direct_mbox(), m_index ); } ); //    ,    taken. st_wait_right .event( [=]( mhood_t<taken_t> ) { //    ,  . this >>= st_eating; } ); //      stop_eating. st_eating // 'stop_eating'        'eating'. .on_enter( [=] { so_5::send_delayed< stop_eating_t >( *this, eat_pause() ); } ) .event( [=]( mhood_t<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_done .on_enter( [=] { //   ,   . completion_watcher_t::done( so_environment(), m_index ); } ); } 

Quiz√°s el √ļnico punto que debe enfatizarse particularmente es el enfoque para imitar los procesos de "pensar" y "comer". No hay this_thread::sleep_for en el c√≥digo del actor ni ninguna otra forma de bloquear el hilo de trabajo actual. En cambio, se utilizan mensajes pendientes. Por ejemplo, cuando un actor entra en el estado de comer , se env√≠a un mensaje de stop_eating_t pendiente. Este mensaje se entrega al temporizador SObjectizer y el temporizador entrega el mensaje al actor cuando llega el momento.


El uso de mensajes retrasados ‚Äč‚Äčle permite ejecutar a todos los actores en el contexto de un solo hilo de trabajo. En t√©rminos generales, un hilo lee los mensajes de alguna cola y tira del siguiente manejador de mensajes del actor receptor correspondiente. M√°s adelante se discutir√° m√°s sobre los contextos de trabajo para los actores.


Resultados


Los resultados de esta implementaci√≥n pueden verse de la siguiente manera (un peque√Īo fragmento):


  Socrates: tttttttttttLRRRRRRRRRRRRRREEEEEEEttttttttLRRRRRRRRRRRRRREEEEEEEEEEEEE Plato: ttttttttttEEEEEEEEEEEEEEEEttttttttttRRRRRREEEEEEEEEEEEEEttttttttttLLL Aristotle: ttttEEEEEtttttttttttLLLLLLRRRREEEEEEEEEEEEttttttttttttLLEEEEEEEEEEEEE Descartes: tttttLLLLRRRRRRRREEEEEEEEEEEEEtttLLLLLLLLLRRRRREEEEEEttttttttttLLLLLL Spinoza: ttttEEEEEEEEEEEEEttttttttttLLLRRRREEEEEEEEEEEEEttttttttttRRRREEEEEEtt Kant: ttttttttttLLLLLLLRREEEEEEEEEEEEEEEttttttttttLLLEEEEEEEEEEEEEEtttttttt Schopenhauer: ttttttEEEEEEEEEEEEEttttttLLLLLLLLLEEEEEEEEEttttttttLLLLLLLLLLRRRRRRRR Nietzsche: tttttttttLLLLLLLLLLEEEEEEEEEEEEEttttttttLLLEEEEEEEEEttttttttRRRRRRRRE Wittgenstein: ttttEEEEEEEEEEtttttLLLLLLLLLLLLLEEEEEEEEEttttttttttttRRRREEEEEEEEEEEt Heidegger: tttttttttttLLLEEEEEEEEEEEEEEtttttttLLLLLLREEEEEEEEEEEEEEEtttLLLLLLLLR Sartre: tttEEEEEEEEEttttLLLLLLLLLLLLRRRRREEEEEEEEEtttttttLLLLLLLLRRRRRRRRRRRR 

Lea esto de la siguiente manera:


  • t denota que el fil√≥sofo est√° "pensando";
  • L significa que el fil√≥sofo espera capturar la bifurcaci√≥n izquierda (est√° en el estado wait_left );
  • R significa que el fil√≥sofo espera capturar la bifurcaci√≥n correcta (est√° en el estado wait_right );
  • E significa que el fil√≥sofo "come".

Podemos ver que Sócrates puede tomar el tenedor a la izquierda solo después de que Sartre lo regala. Después de lo cual Sócrates esperará hasta que Platón libere el tenedor correcto. Solo después de esto, Sócrates podrá comer.


Una decisión simple sin un árbitro (camarero)


Si analizamos el resultado de la decisión de Dijkstra, veremos que los filósofos pasan mucho tiempo esperando la captura de tenedores. Lo que no es bueno, porque Este tiempo también se puede dedicar a la reflexión. No es por nada que hay una opinión de que si piensas con el estómago vacío, puedes obtener resultados mucho más interesantes e inesperados;)


Veamos la solución más simple en la que el filósofo devuelve el primer tenedor capturado si no puede capturar el segundo (en el artículo "Filósofos de la gastronomía moderna" mencionado anteriormente, esta solución es implementada por ForkLevelPhilosopherProtocol).


El código fuente de esta implementación se puede ver aquí , y el código del actor filósofo correspondiente aquí .


Mensajes


Esta solución utiliza casi el mismo conjunto de mensajes:


 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 √ļnica diferencia es la presencia de la se√Īal busy_t . El tenedor-actor env√≠a esta se√Īal en respuesta al fil√≥sofo-actor si el tenedor ya est√° capturado por otro fil√≥sofo.


Tenedor actor


El actor tenedor en esta soluci√≥n es a√ļn m√°s simple que en la soluci√≥n 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 }; }; 

Aquí ni siquiera necesitamos mantener la cola de los filósofos que esperan.


Actor filósofo


El filósofo-actor en esta implementación es similar al de la solución de Dijkstra, pero aquí el filósofo-actor también tiene que procesar busy_t , por lo que el diagrama de estado se ve así:


imagen


Del mismo modo, toda la lógica de un actor-filósofo se define en 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 general, este es casi el mismo código que en la solución de Dijkstra, a excepción de un par de controladores para busy_t .


Resultados


Los resultados del trabajo se ven diferentes:


  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. 

Aquí vemos un nuevo símbolo, lo que significa que el actor-filósofo está en "pensamientos hambrientos".


Incluso en este breve fragmento, uno puede ver que hay largos períodos de tiempo durante los cuales el filósofo no puede comer. Esto se debe a que esta solución está protegida del problema de punto muerto, pero no tiene protección contra el hambre.


La decisión con el camarero y la cola.


La solución más simple que se muestra arriba sin un árbitro no protege contra el hambre. El artículo "Filósofos gastronómicos modernos" mencionado anteriormente contiene una solución al problema del ayuno en forma de un protocolo WaiterFair. La conclusión es que hay un árbitro (camarero), al que recurren los filósofos cuando quieren comer. Y el camarero tiene una cola de solicitudes de filósofos. Y el filósofo obtiene los tenedores solo si ambos tenedores están libres ahora, y no hay ninguno de los vecinos del filósofo que recurrió al camarero en la cola.


Echemos un vistazo a cómo podría verse esta misma solución en los actores.


El código fuente de esta implementación se puede encontrar aquí .


Truco


La forma m√°s f√°cil ser√≠a introducir un nuevo conjunto de mensajes a trav√©s del cual los fil√≥sofos pudieran comunicarse con el camarero. Pero quer√≠a guardar no solo el conjunto de mensajes ya existente (es decir, taken_t , busy_t , put_t , put_t ). Tambi√©n quer√≠a que se utilizara el mismo actor-fil√≥sofo que en la soluci√≥n anterior. Por lo tanto, tuve que resolver un problema complicado: c√≥mo hacer que el actor-fil√≥sofo se comunique con el √ļnico actor-camarero, pero al mismo tiempo pens√© que interact√ļa directamente con los tenedores de actores (que ya no est√°n).


Este problema se resolvió mediante un simple truco: un actor-camarero crea un conjunto de mbox-s, enlaces a los filósofos-actores como enlaces a mbox-s de tenedores. Al mismo tiempo, el actor-camarero se suscribe a los mensajes de todos estos mboxes (que se implementa fácilmente en SObjectizer, porque SObjectizer es una implementación de no solo / tantos modelos de actores, sino que también Pub / Sub es compatible de fábrica) .


En código, se parece a esto:


 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 ) { //  mbox-   "" m_fork_mboxes.reserve( forks_count ); for( std::size_t i{}; i != forks_count; ++i ) m_fork_mboxes.push_back( so_environment().create_mbox() ); } ... void so_define_agent() override { //      "". for( std::size_t i{}; i != m_fork_mboxes.size(); ++i ) { //     .   . //          //    . so_subscribe( fork_mbox( i ) ) .event( [i, this]( mhood_t<take_t> cmd ) { on_take_fork( std::move(cmd), i ); } ) .event( [i, this]( mhood_t<put_t> cmd ) { on_put_fork( std::move(cmd), i ); } ); } } private : ... //     "". std::vector< so_5::mbox_t > m_fork_mboxes; 

Es decir Primero, cree un vector de mbox-s para "bifurcaciones" inexistentes, luego suscríbase a cada una de ellas. Sí, nos suscribimos para saber a qué enchufe en particular se refiere la solicitud.


El controlador real para la on_take_fork() entrante on_take_fork() es el método on_take_fork() :


 void on_take_fork( mhood_t<take_t> cmd, std::size_t fork_index ) { //   ,       //    . if( fork_index == cmd->m_philosopher_index ) handle_take_left_fork( std::move(cmd), fork_index ); else handle_take_right_fork( std::move(cmd), fork_index ); } 

Por cierto, fue aquí donde necesitábamos el segundo campo del mensaje take_t .


Entonces, en on_take_fork() tenemos la solicitud original y el índice de la bifurcación a la que se refiere la solicitud. Por lo tanto, podemos determinar si el filósofo pide un tenedor izquierdo o uno derecho. Y, en consecuencia, podemos procesarlos de manera diferente (y tenemos que procesarlos de manera diferente).


Dado que el filósofo siempre pregunta primero por la bifurcación izquierda, entonces necesitamos hacer todas las verificaciones necesarias en este mismo momento. Y podemos encontrarnos en una de las siguientes situaciones:


  1. Ambos tenedores son gratuitos y se pueden entregar al filósofo que envió la solicitud. En este caso, taken_t filósofo y marcamos la bifurcación derecha como reservada para que nadie más pueda tomarla.
  2. Los tenedores no se pueden dar al filósofo. No importa por qué Tal vez algunos de ellos están ocupados en este momento. O en línea es uno de los vecinos del filósofo. De todos modos, ponemos al filósofo que envió la solicitud en la cola, después de lo cual le busy_t .

Gracias a esta lógica de trabajo, el filósofo que recibió taken_t para la bifurcación izquierda puede enviar de forma segura una solicitud take_t para la bifurcación derecha. Esta solicitud será satisfecha de inmediato, ya que el tenedor ya está reservado para este filósofo.


Resultados


Si ejecuta la solución resultante, puede ver algo como:


  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 

Puedes prestar atención a la falta de caracteres R Esto se debe a que las fallas o expectativas no pueden ocurrir en una solicitud de bifurcación correcta.


Otra decisión usando un árbitro (camarero)


En algunos casos, la solución waiter_with_queue anterior puede mostrar resultados similares a este:


  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 

Puede ver la presencia de períodos de tiempo suficientemente largos cuando los filósofos no pueden comer, incluso a pesar de la presencia de tenedores gratuitos. Por ejemplo, las horquillas izquierda y derecha de Kant son gratuitas durante mucho tiempo, pero Kant no puede tomarlas, porque sus vecinos ya están esperando en la fila. Que están esperando a sus vecinos. Quienes esperan a sus vecinos, etc.


Por lo tanto, la implementación de waiter_with_queue discutida anteriormente protege contra la inanición en el sentido de que tarde o temprano el filósofo comerá. Esto está garantizado para él. Pero los períodos de ayuno pueden ser bastante largos. Y la utilización de recursos puede no ser óptima a veces.


Para resolver este problema, implementé otra solución, waiter_with_timestamp (su código se puede encontrar aquí ). En lugar de hacer cola, priorizan las solicitudes de los filósofos teniendo en cuenta el momento de su ayuno. Cuanto más tiempo pase el filósofo hambriento, más prioridad tendrá su solicitud.


No consideraremos el código para esta solución, porque en general, lo principal es el mismo truco con un conjunto de mboxes para "bifurcaciones" inexistentes, que ya discutimos en la conversación sobre la implementación de waiter_with_queue.


Algunos detalles de implementación a los que me gustaría llamar la atención


Hay varios detalles en las implementaciones basadas en los actores a los que me gustaría prestar atención, porque Estos detalles demuestran características interesantes de SObjectizer.


Contexto laboral para actores


En las implementaciones consideradas, todos los actores principales ( fork_t , philosopher_t , waiter_t ) trabajaron en el contexto de un hilo de trabajo com√ļn. Lo que no significa en absoluto que en SObjectizer todos los actores trabajen en un solo hilo. En SObjectizer, puede vincular actores a diferentes contextos, que se pueden ver, por ejemplo, en el c√≥digo de la funci√≥n run_simulation() en la soluci√≥n no_waiter_simple.


Código de simulación de ejecución 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 ); }); } 

En esta función, completion_watcher_t actores adicionales de los tipos trace_maker_t y completion_watcher_t . Trabajarán en contextos de trabajo individuales. Para hacer esto, se one_thread dos instancias del despachador del tipo one_thread y los actores están vinculados a estas instancias de despachadores. Lo que significa que estos actores trabajarán como objetos activos : cada uno tendrá su propio hilo de trabajo.


SObjectizer proporciona un conjunto de varios despachadores diferentes que se pueden usar directamente. En este caso, el desarrollador puede crear en su aplicación tantas instancias de despachadores como necesite el desarrollador.


, , . , 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(); //     thread_pool-. so_5::disp::thread_pool::bind_params_t bind_params; bind_params.fifo( so_5::disp::thread_pool::fifo_t::individual ); std::vector< so_5::agent_t * > forks( count, nullptr ); //     -. auto fork_disp = so_5::disp::thread_pool::create_private_disp( env, 3u //  . ); for( std::size_t i{}; i != count; ++i ) //      . forks[ i ] = coop.make_agent_with_binder< fork_t >( fork_disp->binder( bind_params ) ); //     -. auto philosopher_disp = so_5::disp::thread_pool::create_private_disp( env, 6u //  . ); for( std::size_t i{}; i != count; ++i ) coop.make_agent_with_binder< philosopher_t >( philosopher_disp->binder( bind_params ), i, forks[ i ]->so_direct_mbox(), forks[ (i + 1) % count ]->so_direct_mbox(), default_meals_count ); }); } 

fork_t philosopher_t .



Modern dining philosophers , , :


 void doEat() { eventLog_.startActivity(ActivityType::eat); wait(randBetween(10, 50)); eventLog_.endActivity(ActivityType::eat); 

SObjectizer . , , . ¬ŅPor qu√©?


, 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 ) { //  :   . bool taken = false; //   . std::queue< so_5::mbox_t > wait_queue; //        . so_5::receive( so_5::from( fork_ch ), [&]( so_5::mhood_t<take_t> cmd ) { if( taken ) //  ,     . wait_queue.push( cmd->m_who ); else { //    . taken = true; so_5::send< taken_t >( cmd->m_who ); } }, [&]( so_5::mhood_t<put_t> ) { if( wait_queue.empty() ) taken = false; //     . else { //       . const auto who = wait_queue.front(); wait_queue.pop(); so_5::send< taken_t >( who ); } } ); } 

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; //         . auto self_ch = so_5::create_mchain( control_ch->environment() ); while( meals_eaten < meals_count ) { tracer.thinking_started( philosopher_index, thinking_type_t::normal ); //    . std::this_thread::sleep_for( pause_generator.think_pause( thinking_type_t::normal ) ); //    . tracer.take_left_attempt( philosopher_index ); so_5::send< take_t >( left_fork, self_ch->as_mbox(), philosopher_index ); //  ,  . so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) { //   ,   . tracer.take_right_attempt( philosopher_index ); so_5::send< take_t >( right_fork, self_ch->as_mbox(), philosopher_index ); //  ,  . so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) { //    .  . tracer.eating_started( philosopher_index ); //     . std::this_thread::sleep_for( pause_generator.eat_pause() ); //     . ++meals_eaten; //     . so_5::send< put_t >( right_fork ); } ); //     . so_5::send< put_t >( left_fork ); } ); } //   ,   . tracer.philosopher_done( philosopher_index ); so_5::send< philosopher_done_t >( control_ch, philosopher_index ); } 

:


 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 . , .


. Es decir , .


, , 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() }; //  . 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() }; } //      . auto control_ch = so_5::create_mchain( env ); //  . const auto philosopher_maker = [&](auto index, auto left_fork_idx, auto right_fork_idx) { return std::thread{ philosopher_process, std::ref(tracer), control_ch, index, fork_chains[ left_fork_idx ]->as_mbox(), fork_chains[ right_fork_idx ]->as_mbox(), default_meals_count }; }; 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 ] ); } ); //     . join_all( philosopher_threads ); //     . for( auto & ch : fork_chains ) so_5::close_drop_content( ch ); //       . join_all( fork_threads ); //  . tracer.done(); //   SObjectizer. env.stop(); } 

, 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; } 

, . Porque , . - :


 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 }; //   . fork_threads_stuff.run(); //     . //       fork_threads_stuff. 

, (, 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 ) { //  :   . bool taken = false; //      . so_5::receive( so_5::from( fork_ch ), [&]( so_5::mhood_t<take_t> cmd ) { if( taken ) so_5::send< busy_t >( cmd->m_who ); else { taken = true; so_5::send< taken_t >( cmd->m_who ); } }, [&]( so_5::mhood_t<put_t> ) { if( taken ) taken = false; } ); } 

, 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 }; //       . thinking_type_t thinking_type{ thinking_type_t::normal }; random_pause_generator_t pause_generator; //      . auto self_ch = so_5::create_mchain( control_ch->environment() ); while( meals_eaten < meals_count ) { tracer.thinking_started( philosopher_index, thinking_type ); //    . std::this_thread::sleep_for( pause_generator.think_pause( thinking_type ) ); //  ,     . thinking_type = thinking_type_t::hungry; //    . tracer.take_left_attempt( philosopher_index ); so_5::send< take_t >( left_fork, self_ch->as_mbox(), philosopher_index ); //  ,  . so_5::receive( so_5::from( self_ch ).handle_n( 1u ), []( so_5::mhood_t<busy_t> ) { /*     */ }, [&]( so_5::mhood_t<taken_t> ) { //   ,   . tracer.take_right_attempt( philosopher_index ); so_5::send< take_t >( right_fork, self_ch->as_mbox(), philosopher_index ); //  ,  . so_5::receive( so_5::from( self_ch ).handle_n( 1u ), []( so_5::mhood_t<busy_t> ) { /*     */ }, [&]( so_5::mhood_t<taken_t> ) { //    ,  . tracer.eating_started( philosopher_index ); //     . std::this_thread::sleep_for( pause_generator.eat_pause() ); //     . ++meals_eaten; //      . so_5::send< put_t >( right_fork ); //        "normal". thinking_type = thinking_type_t::normal; } ); //       . so_5::send< put_t >( left_fork ); } ); } //    . tracer.philosopher_done( philosopher_index ); so_5::send< philosopher_done_t >( control_ch, philosopher_index ); } 

- 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; //    . const so_5::mbox_t m_target; //  ,      . const std::size_t m_fork_index; //    . static std::type_index original_take_type; static std::type_index original_put_type; public : wrapping_mbox_t( const so_5::mbox_t & target, std::size_t fork_index ) : base_type_t{ target } , m_target{ target } , m_fork_index{ fork_index } {} //    so_5::abstract_message_box_t   . //       . void do_deliver_message( const std::type_index & msg_type, const so_5::message_ref_t & message, unsigned int overlimit_reaction_deep ) const override { if( original_take_type == msg_type ) { //     . const auto & original_msg = so_5::message_payload_type<::take_t>:: payload_reference( *message ); //     . so_5::send< extended_take_t >( m_target, original_msg.m_who, original_msg.m_philosopher_index, m_fork_index ); } else if( original_put_type == msg_type ) { //     . so_5::send< extended_put_t >( m_target, m_fork_index ); } else base_type_t::do_deliver_message( msg_type, message, overlimit_reaction_deep ); } //       wrapping_mbox_t. static auto make( const so_5::mbox_t & target, std::size_t fork_index ) { return so_5::mbox_t{ new wrapping_mbox_t{ target, fork_index } }; } }; std::type_index wrapping_mbox_t::original_take_type{ typeid(::take_t) }; std::type_index wrapping_mbox_t::original_put_type{ typeid(::put_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 ) { //        . so_5::receive( so_5::from( waiter_ch ), [&]( so_5::mhood_t<details::extended_take_t> cmd ) { logic.on_take_fork( std::move(cmd) ); }, [&]( so_5::mhood_t<details::extended_put_t> cmd ) { logic.on_put_fork( std::move(cmd) ); } ); } 

, , . waiter_with_timestamps .


: " philosopher_process mbox-?" , waiter_with_timestamps mbox, mchain.


, mchain. , .. so_5_extra mchain- ( ). mbox- mchain-.


Conclusión


, , , CSP . , . , , . , - .


, SObjectizer-. , "" SObjectizer ‚ÄĒ 5.6, 5.5. , ( ). - , SO-5.6 ( ).


, !


PS. "" , . C++14.

Source: https://habr.com/ru/post/437998/


All Articles