Linda (lenguaje de coordinación)

En ciencias de la computación , Linda es un modelo de coordinación y comunicación entre varios procesos paralelos que operan sobre objetos almacenados y recuperados de la memoria asociativa virtual compartida. ^[1] Fue desarrollado por Sudhir Ahuja en AT&T Bell Laboratories en colaboración con David Gelernter y Nicholas Carriero en la Universidad de Yale en 1986. ^{[1] [2]}

Modelo

Este modelo se implementa como un "lenguaje de coordinación" en el que varias primitivas que operan en una secuencia ordenada de objetos de datos con tipo, "tuplas", se agregan a un lenguaje secuencial, como C, y una memoria asociativa lógicamente global , llamada tuplespace , en qué procesos almacenan y recuperan tuplas.

El modelo de Linda original requiere cuatro operaciones que los trabajadores individuales realizan en las tuplas y el espacio de tuplas:

• en atómicamente lee y elimina (consume) una tupla de tuplespace
• rd lee de forma no destructiva un tuplespace
• out produce una tupla, escribiéndola en tuplespace (la tupla puede estar duplicada en tuplespace)
• eval crea nuevos procesos para evaluar tuplas, escribiendo el resultado en tuplespace

Linda-cálculo

El cálculo de Linda es una formalización del modelo anterior con la diferencia de que en el siguiente subsume las operaciones out y eval . La presentación del cálculo se basa en Cridlig et al. ^[3]${\displaystyle \mathrm {outeval} }$

Sintaxis

Abstraemos la representación concreta de tuplas. Simplemente asumimos que tenemos un conjunto de tuplas y se nos permite formar y aplicar una función de sustitución en tuplas sustituyendo variables por términos que produzcan una tupla. Por ejemplo, dado que tenemos una tupla , luego aplicamos una sustitución en los rendimientos${\displaystyle t\in {\mathcal {T}}}$${\displaystyle \sigma }$${\displaystyle t=({\mathit {hello}},x)}$${\displaystyle \sigma =\{{\mathit {world}}/x\}}$${\displaystyle t}$${\displaystyle ({\mathit {hello}},{\mathit {world}})}$

Los procesos de cálculo de Linda se definen mediante la siguiente gramática.

${\displaystyle P,Q::=t\;|\;\mathrm {outeval} (P).Q\;|\;\mathrm {rd} (t).P\;|\;\mathrm {in} (t).P\;|\;P+Q\;|\;\mathbf {rec} X.P\;|\;X}$

La sintaxis incluye las operaciones de Linda antes mencionadas, la elección no determinista y la recursividad. La función de sustitución se extiende a los procesos de forma recursiva.

Semántica

Un espacio de tupla se representa como un conjunto múltiple de procesos. Escribimos para donde es un multiset, un singleton multiset y es la operación de unión de multiset. La semántica se define entonces como una relación de reducción en un multiset de la siguiente manera.${\displaystyle M\,|\,P}$${\displaystyle M\uplus \{P\}}$${\displaystyle M}$${\displaystyle \{P\}}$${\displaystyle \uplus }$${\displaystyle M\rightarrow M'}$

${\displaystyle {\begin{array}{lrcll}{\text{(outeval)}}&M\,|\,\mathrm {outeval} (P).Q&\rightarrow &M\,|\,P\,|\,Q&\\{\text{(read)}}&M\,|\,\mathrm {rd} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma \,|\,t'&{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(input)}}&M\,|\,\mathrm {in} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma &{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(left choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,P&\\{\text{(right choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,Q&\\{\text{(recursion)}}&M\,|\,\mathbf {rec} X.P&\rightarrow &M\,|\,P\{\mathbf {rec} X.P/X\}&\\\end{array}}}$

Tenga en cuenta que (entrada) consume la tupla del espacio de tupla, mientras que (lectura) solo la lee. La semántica operativa resultante es sincrónica.${\displaystyle t'}$

Evaluación

En comparación con otros modelos de procesamiento paralelo, Linda es más ortogonal al tratar la coordinación de procesos como una actividad separada de la computación, y es más general al poder subsumir varios niveles de concurrencia (monoprocesador, multiprocesador de múltiples subprocesos o en red) bajo una modelo único. Su ortogonalidad permite que los procesos de computación en diferentes lenguajes y plataformas interoperen utilizando las mismas primitivas. Su generalidad permite que un sistema Linda de subprocesos múltiples se distribuya en varias computadoras sin cambios.

Mientras que los modelos de paso de mensajes requieren procesos estrechamente acoplados que se envían mensajes entre sí en alguna secuencia o protocolo, los procesos de Linda están desacoplados de otros procesos, comunicándose solo a través del tuplespace; un proceso no necesita tener noción de otros procesos, excepto los tipos de tuplas consumidas o producidas (acoplamiento de datos).

Los investigadores han propuesto más primitivas para soportar diferentes tipos de comunicación y coordinación entre sistemas informáticos (distribuidos abiertos) y para resolver problemas particulares que surgen de varios usos del modelo. ^{[ cita requerida ] Los} investigadores también han experimentado con varios medios para implementar la memoria compartida virtual para este modelo. ^{[ cita requerida ]} Muchos de estos investigadores propusieron modificaciones más grandes al modelo original de Linda, desarrollando una familia de sistemas conocidos como sistemas tipo Linda e implementados como tecnología ortogonal (a diferencia de la versión original). Un ejemplo de esto es el lenguaje Ease diseñado por Steven Ericsson-Zenith.

Implementaciones

Linda se implementó originalmente en C y Fortran , pero desde entonces se ha implementado en muchos lenguajes de programación, que incluyen:

• C : C-Linda , TCP-Linda , LinuxTuples
• C ++ : CppLinda , Boreas
• C # : pSpaces
• Erlang : Erlinda
• Ir : pSpaces
• Java : JavaSpaces , jRESP , TSpaces , LightTS , LIME , pSpaces
• JavaScript : pSpaces
• Ceceo
• Lua : LuaTS Lua Lanes
• Prólogo : SICStus Prolog Linda
• Python : PyLinda
• Rubí : Rinda
• Swift : pSpaces

Algunas de las implementaciones de Linda más notables incluyen:

• C-Linda o TCP-Linda: el primer comercial y una implementación generalizada de memoria virtual compartida para supercomputadoras y sistemas agrupados de Scientific Computing Associates, fundada por Martin Schultz.
• JavaSpaces : una implementación de tuplespace basada en Java que ayudó a popularizar la computación distribuida.
• TSpaces : una plataforma tuplespace basada en Java de IBM. ^{[ peso indebido? - discutir ]}

Críticas

Las críticas a Linda por parte de la comunidad de multiprocesamiento tienden a centrarse en la disminución de la velocidad de las operaciones en los sistemas Linda en comparación con los sistemas de interfaz de paso de mensajes (MPI). ^{[ cita requerida ]} Aunque no sin justificación, estas afirmaciones fueron refutadas en gran medida por una clase importante de problemas. ^[4] También se pueden encontrar críticas detalladas del modelo de Linda en el libro Process Interaction Models de Steven Ericsson-Zenith . ^[5]

Nombre

Linda lleva el nombre de Linda Lovelace , actriz en la película pornográfica Garganta profunda , un juego de palabras con Ada homenaje 's de Ada Lovelace . ^[6]

Publicaciones

• Gelernter, David; Carriero, Nicolás (1992). "Idiomas de coordinación y su significado". Comunicaciones de la ACM . 35 (2): 97–107. doi : 10.1145 / 129630.129635 . S2CID  7748555 .
• Carriero, Nicolás; Gelernter, David; Mattson, Timothy; Sherman, Andrew (1994). "La alternativa de Linda a los sistemas de paso de mensajes". Computación paralela . 20 (4): 633–655. doi : 10.1016 / 0167-8191 (94) 90032-9 .
• Wells, George. "Idiomas de coordinación: Regreso al futuro con Linda" (PDF) . Universidad de Rhodes. Archivado desde el original (PDF) el 19 de diciembre de 2009.
• Sluga, Thomas Arkadius. "Implementación C ++ moderna del lenguaje de coordinación LINDA". Universidad de Hannover.

Ver también

• Flujo de datos
• Diagrama de flujo de datos
• Programación de flujo de datos
• Programación basada en flujo

Referencias

1. Ahuja, Sudhir (Laboratorios Bell de AT&T); Carriero, Nicolás; Gelernter, David (agosto de 1986), "Linda and Friends", Computer , IEEE, 19b (8): 26–34, doi : 10.1109 / mc.1986.1663305 , S2CID 5155678 
2. Carriero, Nicholas; Gelernter, David (1 de enero de 1985). "Linda Kernel de S / Net (resumen extendido)". Actas del Décimo Simposio ACM sobre Principios de Sistemas Operativos . SOSP '85. Nueva York, NY, EE.UU .: ACM: 160–. doi : 10.1145 / 323647.323643 . ISBN 978-0897911740. S2CID  6922183 .
3. Cridlig, Régis; Goubault, Eric (1993). "Semántica y análisis de lenguajes basados ​​en linda". Lecture Notes in Computer Science, vol 724 . Springer, Berlín, Heidelberg. doi : 10.1007 / 3-540-57264-3_30 . ISBN 978-3-540-57264-0.
4. Carriero; et al. (1 de abril de 1994). "La alternativa de Linda a los sistemas de transmisión de mensajes". Computación paralela . 2 (4): 633–655. doi : 10.1016 / 0167-8191 (94) 90032-9 .
5. Ericsson-Zenith (1992). Modelos de interacción de procesos . Universidad de Paris.
6. Markoff, John (19 de enero de 1992). "Romance de David Gelernter con Linda" . The New York Times .

Enlaces externos

• Lenguaje de coordinación : una pequeña discusión sobre las diferencias entre el enfoque de Linda y el de la programación basada en Flow.
• Linda para C ++
• Linda para C
• Erlinda (por Erlang)
• PyLinda (para Python)
• Rinda (por Ruby)
• Linda en un entorno móvil (LIME) (para nesC)