En informática , el modelo Actor y los cálculos de procesos son dos enfoques estrechamente relacionados con el modelado de la computación digital concurrente . Consulte Modelo de actor e historial de cálculos de procesos .
Hay muchas similitudes entre los dos enfoques, pero también varias diferencias (algunas filosóficas, otras técnicas):
- Existe un solo modelo de Actor (aunque tiene numerosos sistemas formales de diseño, análisis, verificación, modelado, etc. ); Existen numerosos cálculos de procesos , desarrollados para razonar sobre una variedad de diferentes tipos de sistemas concurrentes en varios niveles de detalle (incluidos los cálculos que incorporan tiempo, transiciones estocásticas o construcciones específicas para áreas de aplicación como el análisis de seguridad).
- El modelo Actor se inspiró en las leyes de la física y depende de ellas para sus axiomas fundamentales, es decir , las leyes físicas (véase la teoría del modelo Actor ); los cálculos de proceso se inspiraron originalmente en el álgebra ( Milner 1993 ).
- Los procesos en los cálculos de procesos son anónimos y se comunican mediante el envío de mensajes a través de canales con nombre (sincrónicos o asincrónicos) o mediante ambientes (que también se pueden utilizar para modelar comunicaciones similares a canales ( Cardelli y Gordon 1998 )). En contraste, los actores en el modelo Actor poseen una identidad y se comunican enviando mensajes a las direcciones de correo de otros actores (este estilo de comunicación también se puede usar para modelar comunicaciones tipo canal, ver más abajo).
Las publicaciones sobre el modelo Actor y sobre cálculos de procesos tienen un buen número de referencias cruzadas, reconocimientos y citas recíprocas (ver Modelo de actor e historial de cálculos de procesos ).
Cómo funcionan los canales
La comunicación indirecta mediante canales ( por ejemplo, Gilles Kahn y David MacQueen [1977]) ha sido un tema importante para la comunicación en computación paralela y concurrente que afecta tanto a la semántica como al rendimiento. Algunos cálculos de procesos difieren del modelo Actor en el uso de canales en oposición a la comunicación directa.
Canales sincrónicos
Los canales síncronos tienen la propiedad de que un remitente que coloca un mensaje en el canal debe esperar a que un receptor saque el mensaje del canal antes de que el remitente pueda continuar.
Canales síncronos simples
Un canal sincrónico puede ser modelado por un actor que recibe put
y get
comunica. El siguiente es el comportamiento de un actor para un canal sincrónico simple:
- Cada
put
comunicación tiene un mensaje y una dirección a la que se envía un acuse de recibo cuando el mensaje es recibido por unaget
comunicación del canal en orden FIFO . - Cada
get
comunicación tiene una dirección a la que se envía el mensaje recibido.
Canales síncronos en cálculos de proceso
Sin embargo, los canales síncronos simples no son suficientes para cálculos de procesos como Comunicar Procesos Secuenciales (CSP) [Hoare 1978 y 1985] debido al uso del comando de elección protegida (después de Dijkstra) (llamado comando alternativo en CSP). En un comando de elección cautelosa, se pueden realizar múltiples ofertas (llamadas guardias) simultáneamente en múltiples canales put
y get
mensajes; sin embargo, como máximo, se puede elegir uno de los guardias para cada ejecución del comando de elección guardada. Debido a que solo se puede elegir un guardia, un comando de elección cautelosa en general requiere efectivamente una especie de protocolo de compromiso de dos fases o quizás incluso un protocolo de compromiso de tres fases si se permiten tiempos de espera en los guardias (como en Occam 3 [1992]) .
Considere el siguiente programa escrito en CSP [Hoare 1978]:
[X :: Z! Stop () || Y :: guard: boolean; guardia: = verdadero; * [guardia → Z! go (); Z? Guardia] || Z :: n: entero; n: = 0; * [X? Stop () → Y! False; imprimir! n; [] Y? Go () → n: = n + 1; Y! Cierto]]
Según Clinger [1981], este programa ilustra no determinismo global, ya que el no determinismo surge de especificación incompleta de la sincronización de las señales entre los tres procesos X
, Y
, y Z
. El comando guardado repetitivo en la definición de Z
tiene dos alternativas:
- desde el
stop
que se acepta el mensajeX
, en cuyo casoY
se envía el valor falso yprint
se envía el valorn
go
se acepta un mensaje deY
, en cuyo cason
se incrementa yY
se envía el valor verdadero .
Si Z
alguna vez acepta el stop
mensaje de X
, entonces X
termina. Aceptando las stop
causas Y
para que se envíe falso que al ingresar como valor de su guarda provocará Y
su terminación. Cuando ambos X
y Y
han terminado, Z
termina porque ya no tiene procesos activos que proporcionen información.
En el programa anterior, hay canales síncronos desde X
hacia Z
, Y
hacia Z
y Z
hasta Y
.
Analogía con el problema de coordinación del comité
Según Knabe [1992], Chandy y Misra [1988] caracterizaron esto como análogo al problema de coordinación del comité:
- Los profesores de una universidad están asignados a varios comités. Ocasionalmente, una profesora decidirá asistir a una reunión de cualquiera de sus comités y esperará hasta que sea posible. Las reuniones pueden comenzar solo si hay una asistencia completa. La tarea es asegurarse de que si todos los miembros de un comité están esperando, al menos uno de ellos asistirá a alguna reunión.
- El meollo de este problema es que dos o más comités pueden compartir un profesor. Cuando ese profesor esté disponible, solo podrá elegir una de las reuniones, mientras los demás continúan esperando.
Un protocolo distribuido simple
Esta sección presenta un protocolo distribuido simple para canales en cálculos de procesos síncronos. El protocolo tiene algunos problemas que se tratan en las secciones siguientes.
El comportamiento de un comando de elección cautelosa es el siguiente:
- El comando envía un mensaje a cada uno de sus guardias a
prepare
. - Cuando recibe la primera respuesta de uno de sus guardias que está preparado, envía un mensaje a ese guardia
prepare to commit
y envía mensajes a todos los demás guardias aabort
.- Cuando recibe un mensaje del guardia que lo es
prepared to commit
, envía uncommit
mensaje al guardia . Sin embargo, si el guardia lanza una excepción que no puedeprepare to commit
, entonces el comando de elección protegida comienza todo el proceso nuevamente.
- Cuando recibe un mensaje del guardia que lo es
- Si todos sus guardias responden que no pueden
prepare
, entonces el comando vigilado no hace nada.
El comportamiento de un guardia es el siguiente:
- Cuando
prepare
se recibe un mensaje a , el guardia envía unprepare
mensaje a cada uno de los canales con los que se ofrece a comunicarse. Si el guardia tiene valores booleanos de modo que no puedeprepare
o si alguno de los canales responde que no puedeprepare
, envíaabort
mensajes a los otros canales y luego responde que no puedeprepare
.- Cuando
prepare to commit
se recibe un mensaje a , el guardia envía unprepare to commit
mensaje a cada uno de los canales. Si alguno de los canales responde que no puedeprepare to commit
, envíaabort
mensajes a los otros canales y luego lanza una excepción que no puedeprepare to commit
. - Cuando
commit
se recibe un mensaje a , el guardia envía uncommit
mensaje a cada uno de los canales. - Cuando
abort
se recibe un mensaje a , el guardia envía unabort
mensaje a cada uno de los canales.
- Cuando
El comportamiento de un canal es el siguiente:
- Cuando
prepare to put
se reciba una comunicación, entonces responda que está preparada si hay unaprepare to get
comunicación pendiente a menos queterminate
se haya recibido una comunicación, en cuyo caso arroje una excepción que no puedeprepare to put
. - Cuando
prepare to get
se reciba una comunicación, entonces responda que está preparada si hay unaprepare to put
comunicación pendiente a menos queterminate
se haya recibido una comunicación, en cuyo caso arroje una excepción que no puedeprepare to get
.- Cuando
prepare to commit to put
se reciba una comunicación, entonces responda que está preparada si hay unaprepare to commit to get
comunicación pendiente a menos queterminate
se haya recibido una comunicación, en cuyo caso arroje una excepción que no puedeprepare to commit to put
. - Cuando
prepare to commit to get
se reciba una comunicación, entonces responda que está preparada si hay unaprepare to commit to put
comunicación pendiente a menos queterminate
se haya recibido una comunicación, en cuyo caso arroje una excepción que no puedeprepare to commit to get
.- Cuando
commit put
se recibe una comunicación, dependiendo de cuál de las siguientes opciones se reciba:- Cuando una
commit get
se recibe la comunicación, a continuación, si no se ha hecho lo realiceput
yget
y limpiar los preparativos. - Cuando
abort get
se recibe una comunicación, cancele los preparativos
- Cuando una
- Cuando
commit get
se recibe una comunicación, dependiendo de cuál de las siguientes opciones se reciba:- Cuando una
commit put
se recibe la comunicación, a continuación, si no se ha hecho lo realiceget
yput
y limpiar los preparativos. - Cuando
abort put
se reciba una comunicación, cancele los preparativos.
- Cuando una
- Cuando
abort put
se reciba una comunicación, cancele los preparativos. - Cuando
abort get
se reciba una comunicación, cancele los preparativos.
- Cuando
- Cuando
Hambruna al obtener de múltiples canales
Considere nuevamente el programa escrito en CSP (discutido en Canales síncronos en cálculos de proceso arriba):
[X :: Z! Stop () || Y :: guard: boolean; guardia: = verdadero; * [guardia → Z! go (); Z? Guardia] || Z :: n: entero; n: = 0; * [X? Stop () → Y! False; imprimir! n; [] Y? Go () → n: = n + 1; Y! Cierto]]
Como se señala en Knabe [1992], un problema con el protocolo anterior ( un protocolo distribuido simple ) es que el proceso Z
nunca podría aceptar el stop
mensaje de X
(un fenómeno llamado inanición ) y, en consecuencia, el programa anterior nunca podría imprimir nada.
Por el contrario, considere un sistema de actor simple que consta de los actores X , Y , Z e imprimir donde
- el Actor X se crea con el siguiente comportamiento:
- Si
"start"
se recibe el mensaje , envíe Z el mensaje"stop"
- Si
- el Actor Y se crea con el siguiente comportamiento:
- Si
"start"
se recibe el mensaje , envíe Z el mensaje"go"
- Si se recibe el mensaje verdadero , envíe Z el mensaje
"go"
- Si se recibe el mensaje falso , no haga nada
- Si
- el Actor Z se crea con el siguiente comportamiento que tiene un recuento
n
que inicialmente es 0 :- Si
"start"
se recibe el mensaje , no haga nada. - Si
"stop"
se recibe el mensaje , envíe Y el mensaje falso y envíe el mensaje a imprimir el recuenton
. - Si
"go"
se recibe el mensaje , envíe Y el mensaje verdadero y procese el siguiente mensaje recibido con la cuentan
siendon+1
.
- Si
Según las leyes de la semántica de Actor, el sistema de Actor anterior siempre se detendrá cuando los Actores X , Y y Z reciben cada uno un "start"
mensaje que da como resultado el envío de un número impreso que puede ser ilimitado.
La diferencia entre el programa CSP y el sistema Actor es que el Actor Z no recibe mensajes usando un comando de elección cautelosa de múltiples canales. En su lugar, procesa los mensajes en el orden de llegada y, según las leyes de los sistemas Actor, stop
se garantiza la llegada del mensaje.
Livelock al obtener de múltiples canales
Considere el siguiente programa escrito en CSP [Hoare 1978]:
[Licitador1 :: b: oferta; * [Bids1? B → process1! B; [] Ofertas2? B → proceso1! B;] || Licitante2 :: 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 Bidder2
nunca podría aceptar una oferta de Bid1
o Bid2
(un fenómeno llamado livelock ) y, en consecuencia process2
, nunca podría enviarse nada. En cada intento de aceptar un mensaje, Bidder2
se frustra porque la oferta que se le ofreció por Bids1
o Bids2
está arrebatado por Bidder1
porque resulta que Bidder1
tiene acceso mucho más rápido de lo Bidder2
que Bids1
y Bids2
. En consecuencia, Bidder1
puede aceptar una oferta, procesarla y aceptar otra oferta antes de Bidder2
comprometerse a aceptar una oferta.
Eficiencia
Como se señala en Knabe [1992], un problema con el protocolo anterior ( un protocolo distribuido simple ) es la gran cantidad de comunicaciones que se deben enviar para realizar el protocolo de enlace para enviar un mensaje a través de un canal síncrono. De hecho, como se muestra en la sección anterior ( Livelock ), el número de comunicaciones puede ser ilimitado.
Resumen de problemas
Las subsecciones anteriores han articulado los siguientes tres temas relacionados con el uso de canales síncronos para cálculos de procesos:
- Inanición. El uso de canales síncronos puede causar inanición cuando un proceso intenta obtener mensajes de múltiples canales en un comando de elección cautelosa.
- Livelock. El uso de canales síncronos puede hacer que un proceso quede bloqueado cuando intenta obtener mensajes de varios canales en un comando de elección protegida.
- 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 cautelosa.
Es notable que en todo lo anterior, los problemas surgen del uso de un comando de elección cautelosa para obtener mensajes de múltiples canales.
Canales asincrónicos
Los canales asincrónicos tienen la propiedad de que un remitente que coloca un mensaje en el canal no necesita esperar a que un receptor saque el mensaje del canal.
Canales asincrónicos simples
Un canal asincrónico puede ser modelado por un actor que recibe put
y get
comunica. El siguiente es el comportamiento de un actor para un canal asincrónico simple:
- Cada
put
comunicación tiene un mensaje y una dirección a la que se envía un acuse de recibo inmediatamente (sin esperar a que la comunicación reciba el mensajeget
). - Cada
get
comunicación tiene una dirección a la que se envía el mensaje recibido.
Canales asincrónicos en cálculos de proceso
El lenguaje de programación Join-calculus (publicado en 1996) implementó cálculos concurrentes locales y distribuidos. Incorporaba canales asíncronos así como una especie 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 mecanografiada del cálculo π asincrónico .
Álgebras
El uso de técnicas algebraicas fue pionero en el proceso de cálculo. Posteriormente, se han desarrollado varios cálculos de procesos diferentes destinados a proporcionar un razonamiento algebraico sobre los sistemas Actor en ( Gaspari y Zavattaro 1997 ), ( Gaspari y Zavattaro 1999 ), ( Agha y Thati 2004 ).
Semántica denotacional
Will Clinger (basándose en el trabajo de Irene Greif [1975], Gordon Plotkin [1976], Henry Baker [1978], Michael Smyth [1978] y Francez, Hoare , Lehmann y de Roever [1979]) publicó la primera publicación satisfactoria teoría matemática denotacional del modelo Actor usando la teoría del dominio en su disertación en 1981. Su semántica contrastó el no determinismo ilimitado del modelo Actor con el no determinismo acotado de CSP [Hoare 1978] y Concurrent Processes [Milne y Milner 1979] (ver semántica denotacional ) . Roscoe [2005] ha desarrollado una semántica denotacional con no determinismo ilimitado para una versión posterior de Communicating Sequential Processes Hoare [1985]. Más recientemente, Carl Hewitt [2006b] desarrolló una semántica denotacional para Actores basada en diagramas cronometrados .
Ugo Montanari y Carolyn Talcott [1998] han contribuido a intentar reconciliar a los actores con los cálculos de procesos.
Referencias
- Carl Hewitt, Peter Bishop y Richard Steiger. Un formalismo universal de actor modular para la inteligencia artificial IJCAI 1973.
- Robin Milner. Procesos: un modelo matemático de agentes informáticos en el coloquio de lógica 1973.
- Irene Greif y Carl Hewitt. Semántica de actor de PLANNER-73 Conferencia Record del Simposio ACM sobre principios de lenguajes de programación. Enero de 1975.
- Irene Greif. Semántica de la comunicación de profesiones paralelas Tesis doctoral EECS del MIT. Agosto de 1975.
- Gordon Plotkin. Una construcción de dominio de potencia SIAM Journal on Computing, septiembre de 1976.
- Carl Hewitt y Henry Baker Actores y Actas de Funcionalidad Continua de la Conferencia de Trabajo de IFIP sobre Descripción Formal de Conceptos de Programación. 1-5 de agosto de 1977.
- Gilles Kahn y David MacQueen. Corutinas y redes de procesos paralelos IFIP. 1977
- Aki Yonezawa Especificaciones y técnicas de verificación para programas paralelos basadas en la semántica de aprobación de mensajes MIT EECS Tesis doctoral. Diciembre de 1977.
- Michael Smyth. Power domains Journal of Computer and System Sciences. 1978.
- George Milne y Robin Milner . Procesos concurrentes y su sintaxis JACM. Abril de 1979.
- COCHE Hoare . Comunicación de procesos secuenciales CACM. Agosto de 1978.
- Nissim Francez, CAR Hoare , Daniel Lehmann y Willem de Roever. Semántica del no determinismo, concurrencia y comunicación Journal of Computer and System Sciences. Diciembre de 1979.
- Mathew Hennessy y Robin Milner. Sobre la observación del no determinismo y la concurrencia LNCS 85. 1980.
- Will Clinger. Fundamentos de la semántica del actor MIT Matemáticas Tesis doctoral. Junio de 1981.
- Mathew Hennessy. Un modelo de término para procesos síncronos Departamento de Ciencias de la Computación de la Universidad de Edimburgo. CSR-77-81. 1981.
- JA Bergstra y JW Klop. Álgebra de procesos para información y control de comunicación síncrona . 1984.
- Luca Cardelli. Un modelo de implementación del seminario de comunicación de encuentro sobre concurrencia. Apuntes de conferencias en informática 197. Springer-Verlag. 1985
- Robert van Glabbeek. No determinismo acotado y el principio de inducción de aproximación en el simposio de álgebra de procesos sobre aspectos teóricos de las ciencias de la computación en STACS 1987.
- K. Mani Chandy y Jayadev Misra. Diseño de programas paralelos: una fundación Addison-Wesley 1988.
- Robin Milner, Joachim Parrow y David Walker. Cálculo de procesos móviles Departamento de Ciencias de la Computación de Edimburgo. Informes ECS-LFCS-89-85 y ECS-LFCS-89-86. Junio de 1989. Revisado en septiembre de 1990 y octubre de 1990, respectivamente.
- Robin Milner. The Polyadic pi-Calculus: A Tutorial de la Universidad de Edimburgo. Informe LFCS ECS-LFCS-91-180. 1991.
- Kohei Honda y Mario Tokoro. Un cálculo de objetos para la comunicación asincrónica ECOOP 91.
- José Meseguer. La lógica de reescritura condicional como modelo unificado de concurrencia en artículos seleccionados del Segundo Taller sobre concurrencia y composicionalidad. 1992.
- Frederick Knabe. Un protocolo distribuido para la comunicación basada en canales con Choice PARLE 1992.
- Geoff Barrett. Manual de referencia de Occam 3 INMOS. 1992.
- Benjamin Pierce, Didier Rémy y David Turner. Lenguaje de programación mecanografiado de orden superior basado en el taller pi-calculus sobre teoría de tipos y su aplicación a sistemas informáticos. Universidad de Kyoto. Julio de 1993.
- Milner, Robin (enero de 1993), "Elementos de interacción: conferencia del premio Turing", Comunicaciones del ACM , CACM, 36 : 78–89, doi : 10.1145 / 151233.151240.
- R. Amadio y S. Prasad. Ubicaciones y fallas Conferencia de Fundamentos de Tecnología de Software y Computación Teórica. 1994.
- Cédric Fournet y Georges Gonthier. La máquina abstracta química reflexiva y el cálculo combinado POPL 1996.
- Cédric Fournet, Georges Gonthier, Jean-Jacques Lévy, Luc Maranget y Didier Rémy. Un cálculo de agentes móviles CONCUR 1996.
- Tatsurou Sekiguchi y Akinori Yonezawa . Un cálculo con movilidad de código FMOODS 1997.
- Gaspari, Mauro; Zavattaro, Gianluigi (mayo de 1997), An Algebra of Actors (Informe técnico), Universidad de Bolonia
- Luca Cardelli y Andrew Gordon (1998), Maurice Nivat (ed.), "Ambientes móviles", Fundamentos de la ciencia del software y estructuras computacionales , Lecture Notes in Computer Science, Springer, 1378
- Ugo Montanari y Carolyn Talcott. ¿Pueden los actores y los agentes pi vivir juntos? Notas electrónicas en informática teórica. 1998.
- Robin Milner. Sistemas móviles y de comunicación: Pi-Calculus Cambridge University Press. 1999.
- M. Gaspari y G. Zavattaro (1999), "An Algebra of Actors", Métodos formales para sistemas abiertos basados en objetos : 3–18, doi : 10.1007 / 978-0-387-35562-7_2 , ISBN 978-1-4757-5266-3
- Davide Sangiorgi y David Walker. El Pi-Cálculo: una teoría de los procesos móviles Cambridge University Press. 2001.
- P. Thati, R. Ziaei y G. Agha. Una teoría de las pruebas de mayo para cálculos asincrónicos con localidad y sin nombre que coincida con la metodología algebraica y la tecnología de software. Springer Verlag. Septiembre de 2002. LNCS 2422.
- Gul Agha y Prasanna Thati (2004), "Una teoría algebraica de los actores y su aplicación a un lenguaje simple basado en objetos" (PDF) , OO to FM (Dahl Festschrift) LNCS , Springer-Verlag, 2635 , archivado del original ( PDF) el 2004-04-20 , consultado el 2005-12-15
- JCM Baeten, T. Basten y MA Reniers. Álgebra de los procesos de comunicación Cambridge University Press. 2005.
- He Jifeng y CAR Hoare. Vinculación de las teorías de la concurrencia Instituto Internacional de Tecnología de Software de la Universidad de las Naciones Unidas Informe UNU-IIST No. 328. Julio de 2005.
- Luca Aceto y Andrew D. Gordon (editores). Cálculos de procesos algebraicos: los primeros veinticinco años y más allá del álgebra de procesos. Bertinoro, Forl`ı, Italia, 1 al 5 de agosto de 2005.
- Roscoe, AW (2005), Teoría y práctica de la concurrencia , Prentice Hall , ISBN 978-0-13-674409-2CS1 maint: ref duplica el valor predeterminado ( enlace )
- Carl Hewitt (2006b) ¿Qué es el compromiso? COIN @ AAMAS Físico, Organizacional y Social . 2006.