Modelo de actor y cálculo de procesos

Un canal síncrono puede modelarse mediante un Actor que recibe puty getcomunica. A continuación se describe el comportamiento de un Actor para un canal síncrono simple:

• Cada putcomunicación tiene un mensaje y una dirección a la que se envía un acuse de recibo cuando se recibe el mensaje.
• Cada get comunicación tiene una dirección a la que se envía el mensaje recibido.
• Al recibir una getcomunicación, el Actor elige una putcomunicación en orden FIFO y envía el mensaje y la confirmación a las direcciones especificadas.

Sin embargo, los canales síncronos simples no son suficientes para cálculos de procesos como los Procesos Secuenciales Comunicantes (CSP) [Hoare 1978 y 1985] debido al uso del comando de elección protegida (siguiendo a Dijkstra) (llamado comando alternativo en CSP). En un comando de elección protegida, se pueden realizar múltiples ofertas (llamadas protecciones) simultáneamente en múltiples canales para putlos getmensajes; sin embargo, como máximo se puede elegir una protección para cada ejecución del comando. Dado que solo se puede elegir una protección, un comando de elección protegida generalmente requiere efectivamente un tipo de protocolo de confirmación de dos fases o quizás incluso un protocolo de confirmación de tres fases si se permiten tiempos de espera en las protecciones (como en Occam 3 [1992]).

Considere el siguiente programa escrito en CSP [Hoare 1978]:

[X :: Z!stop() || Y :: guard: boolean; guard := true; *[guard  →  Z!go(); Z?guard] || Z :: n: entero; n:= 0; *[X?stop()  →  Y!false; print!n; [] Y?go()  →  n := n+1; Y!true] ]

Según Clinger [1981], este programa ilustra el no determinismo global, ya que el no determinismo surge de la especificación incompleta de la sincronización de las señales entre los tres procesos X, Y, y Z. El comando repetitivo protegido en la definición de Ztiene dos alternativas:

1. El stopmensaje es aceptado desde X, en cuyo caso Yse envía el valor falso y printse envía el valorn
2. goSe acepta un mensaje de Y, en cuyo caso nse incrementa y Yse envía el valor verdadero .

Si Zalguna vez acepta el stopmensaje de X, entonces Xtermina. Aceptar stopprovoca Yque se envíe falso, lo que cuando se introduce como valor de su guardia hará Yque termine. Cuando tanto Xcomo Yhan terminado, Ztermina porque ya no tiene procesos activos que proporcionen entrada.

En el programa anterior, hay canales síncronos de Xa Z, Ya Z, y Za Y.

Según Knabe [1992], Chandy y Misra [1988] caracterizaron esto como análogo al problema de coordinación del comité:

En una universidad, los profesores son asignados a diversos comités. Ocasionalmente, un profesor decide asistir a una reunión de alguno de sus comités y espera hasta que le sea posible. Las reuniones solo pueden comenzar si todos los miembros están presentes. La tarea consiste en asegurar que, si todos los miembros de un comité están esperando, al menos uno de ellos asista a alguna reunión.

El meollo del problema reside en que dos o más comités podrían compartir un profesor. Cuando ese profesor esté disponible, solo podrá elegir una de las reuniones, mientras que los demás seguirán esperando.

Esta sección presenta un protocolo distribuido sencillo para canales en cálculos de procesos síncronos. El protocolo presenta algunos problemas que se abordan en las secciones siguientes.

El comportamiento de un comando de elección protegida es el siguiente:

• El comando envía un mensaje a cada uno de sus guardias para prepare.
• Cuando recibe la primera respuesta de uno de sus guardias de que está preparado, entonces envía un mensaje a ese guardia prepare to commity envía mensajes a todos los demás guardias abort.
  • Cuando recibe un mensaje del guardia que indica que es prepared to commit, entonces le envía un commitmensaje al guardia. Sin embargo, si el guardia lanza una excepción que indica que no puede prepare to commit, entonces el comando de elección protegida reinicia todo el proceso.
• Si todos sus guardias responden que no pueden prepare, entonces la orden custodiada no hace nada.

El comportamiento de un guardia es el siguiente:

• Cuando se recibe un mensaje prepare, el guardia envía un preparemensaje a cada uno de los canales con los que ofrece comunicarse. Si el guardia tiene valores booleanos que indican que no puede prepareo si alguno de los canales responde que no puede prepare, entonces envía abortmensajes a los otros canales y luego responde que no puede prepare.
  • Cuando se recibe un mensaje prepare to commit, el guardia envía un prepare to commitmensaje a cada uno de los canales. Si alguno de los canales responde que no puede prepare to commit, entonces envía abortmensajes a los otros canales y luego lanza una excepción que indica que no puede prepare to commit.
  • Cuando se recibe un mensaje commit, el guardia envía un commitmensaje a cada uno de los canales.
  • Cuando se recibe un mensaje abort, el guardia envía un abortmensaje a cada uno de los canales.

El comportamiento de un canal es el siguiente:

• Cuando prepare to putse recibe una comunicación, entonces responde que está preparada si hay una prepare to getcomunicación pendiente a menos que terminatese haya recibido una comunicación, en cuyo caso lanza una excepción que indica que no puede prepare to put.
• Cuando prepare to getse recibe una comunicación, entonces responde que está preparada si hay una prepare to putcomunicación pendiente a menos que terminatese haya recibido una comunicación, en cuyo caso lanza una excepción que indica que no puede prepare to get.
  • Cuando prepare to commit to putse recibe una comunicación, entonces responde que está preparada si hay una prepare to commit to getcomunicación pendiente a menos que terminatese haya recibido una comunicación, en cuyo caso lanza una excepción que indica que no puede prepare to commit to put.
  • Cuando prepare to commit to getse recibe una comunicación, entonces responde que está preparada si hay una prepare to commit to putcomunicación pendiente a menos que terminatese haya recibido una comunicación, en cuyo caso lanza una excepción que indica que no puede prepare to commit to get.
    • Cuando commit putse recibe una comunicación, entonces, dependiendo de cuál de los siguientes elementos se reciba:
      • Cuando se recibe una commit getcomunicación, si no se ha hecho ya, realice los preparativos puty getlimpie.
      • Cuando se reciba una abort getcomunicación, cancele los preparativos.
    • Cuando commit getse recibe una comunicación, entonces, dependiendo de cuál de los siguientes elementos se reciba:
      • Cuando se recibe una commit putcomunicación, si no se ha hecho ya, realice los preparativos gety putlimpie.
      • Cuando se reciba una abort putcomunicación, cancele los preparativos.
    • Cuando se reciba una abort putcomunicación, cancele los preparativos.
    • Cuando se reciba una abort getcomunicación, cancele los preparativos.

Consideremos nuevamente el programa escrito en CSP (discutido en Canales síncronos en cálculos de procesos más arriba):

[X :: Z!stop() || Y :: guard: boolean; guard := true; *[guard  →  Z!go(); Z?guard] || Z :: n: entero; n:= 0; *[X?stop()  →  Y!false; print!n; [] Y?go()  →  n := n+1; Y!true] ]

Como se señala en Knabe [1992], un problema con el protocolo anterior ( un protocolo distribuido simple ) es que el proceso Zpodría no aceptar nunca el stopmensaje X(un fenómeno llamado inanición ) y, en consecuencia, el programa anterior podría no imprimir nunca nada.

En contraste, considere un sistema de actores simple que consta de los actores X , Y , Z , y imprima donde

• El Actor X se crea con el siguiente comportamiento:
  • Si "start"se recibe el mensaje, entonces envíe el mensaje a Z."stop"
• El actor Y se crea con el siguiente comportamiento:
  • Si "start"se recibe el mensaje, entonces envíe el mensaje a Z."go"
  • Si se recibe el mensaje verdadero , entonces envíe el mensaje a Z."go"
  • Si se recibe el mensaje falso , entonces no haga nada.
• El actor Z se crea con el siguiente comportamiento que tiene un contador nque inicialmente es 0 :
  • Si "start"se recibe el mensaje, no haga nada.
  • "stop"Si se recibe el mensaje , entonces envíe a Y el mensaje falso y envíe imprimir el mensaje el contador n.
  • "go"Si se recibe el mensaje , entonces envíe a Y el mensaje verdadero y procese el siguiente mensaje recibido con un contador nde n+1.

Según las leyes de la semántica de los actores, el sistema de actores anterior siempre se detendrá cuando a los actores X , Y y Z se les envíe un "start"mensaje, lo que dará como resultado el envío de un número que puede ser ilimitadamente grande.

La diferencia entre el programa CSP y el sistema Actor radica en que el Actor Z no recibe mensajes mediante un comando de elección controlada desde múltiples canales. En cambio, procesa los mensajes según el orden de llegada, y, según las leyes de los sistemas Actor, stopse garantiza la llegada del mensaje.

Considere el siguiente programa escrito en CSP [Hoare 1978]:

[Postor1 :: b: oferta; *[Bids1?b  →  process1!b; [] Ofertas2?b  →  proceso1!b;] || Postor2 :: b: oferta; *[Bids1?b  →  process2!b; [] Ofertas2?b  →  proceso2!b;] ]

Como se señala en Knabe [1992], un problema con el protocolo anterior ( un protocolo distribuido simple ) es que el proceso Bidder2podría no aceptar nunca una oferta de Bid1o Bid2(un fenómeno llamado bloqueo mutuo ) y, por lo tanto, process2podría no recibir nunca nada. En cada intento de aceptar un mensaje, Bidder2se ve frustrado porque la oferta que fue ofrecida por Bids1o Bids2es arrebatada por Bidder1porque resulta que Bidder1tiene un acceso mucho más rápido que Bidder2a Bids1y Bids2. Por lo tanto, Bidder1puede aceptar una oferta, procesarla y aceptar otra oferta antes de que Bidder2pueda comprometerse a aceptar una oferta.

Como se señala en Knabe [1992], un problema con el protocolo anterior ( Un protocolo distribuido simple ) es la gran cantidad de comunicaciones que deben enviarse para realizar el intercambio de claves y enviar un mensaje a través de un canal síncrono. De hecho, como se muestra en la sección anterior ( Bloqueo mutuo ), la cantidad de comunicaciones puede ser ilimitada.

Las subsecciones anteriores han articulado los siguientes tres problemas relacionados con el uso de canales síncronos para cálculos de procesos:

1. Inanición. El uso de canales síncronos puede provocar inanición cuando un proceso intenta obtener mensajes de múltiples canales en un comando de elección protegida.
2. Bloqueo mutuo. El uso de canales síncronos puede provocar que un proceso quede atrapado en un bloqueo mutuo cuando intenta obtener mensajes de múltiples canales en un comando de elección protegida.
3. Eficiencia. El uso de canales síncronos puede requerir una gran cantidad de comunicaciones para obtener mensajes de múltiples canales en un comando de elección controlada.

Cabe destacar que en todos los casos mencionados, surgen problemas derivados del uso de un comando de selección controlada para obtener mensajes de múltiples canales.

Un canal asíncrono puede modelarse mediante un Actor que recibe puty getcomunica. A continuación se describe el comportamiento de un Actor para un canal asíncrono simple:

• Cada putcomunicación tiene un mensaje y una dirección a la que se envía un acuse de recibo inmediatamente (sin esperar a que el mensaje sea recibido por otra getcomunicación).
• Cada get comunicación tiene una dirección a la que se envía el mensaje recibido.

El lenguaje de programación Join-calculus (publicado en 1996) implementaba cálculos concurrentes locales y distribuidos. Incorporaba canales asíncronos, así como un tipo de canal síncrono que se utiliza para llamadas a procedimientos. El cálculo Aπ Actor de Agha ( Agha y Thati, 2004 ) se basa en una versión tipada del cálculo π asíncrono .