En informática , la concurrencia es la capacidad de que diferentes partes o unidades de un programa , algoritmo o problema se ejecuten de forma desordenada o parcial , sin afectar el resultado final. Esto permite paralelo ejecución de las unidades concurrentes, que pueden mejorar significativamente la velocidad global de la ejecución en múltiples procesadores y multi-núcleo sistemas. En términos más técnicos, la concurrencia se refiere a la descomponibilidad de un programa, algoritmo o problema en componentes o unidades de cálculo independientes del orden o parcialmente ordenados.[1]
Se han desarrollado varios modelos matemáticos para el cálculo concurrente general, incluidas las redes de Petri , los cálculos de procesos , el modelo de máquina de acceso aleatorio paralelo , el modelo de actor y el lenguaje de coordinación Reo .
Historia [ editar ]
Como señala Leslie Lamport (2015), "Si bien durante años se había considerado la ejecución concurrente de programas , la informática de la concurrencia comenzó con el artículo seminal de 1965 de Edsger Dijkstra que introdujo el problema de la exclusión mutua ... crecimiento del interés en la concurrencia, particularmente en los sistemas distribuidos . Mirando hacia atrás en los orígenes del campo, lo que se destaca es el papel fundamental desempeñado por Edsger Dijkstra ". [2]
Problemas [ editar ]
Debido a que los cálculos en un sistema concurrente pueden interactuar entre sí mientras se ejecutan, el número de posibles rutas de ejecución en el sistema puede ser extremadamente grande y el resultado resultante puede ser indeterminado . El uso simultáneo de recursos compartidos puede ser una fuente de indeterminación que conduce a problemas como puntos muertos y falta de recursos . [3]
El diseño de sistemas concurrentes a menudo implica encontrar técnicas confiables para coordinar su ejecución, intercambio de datos, asignación de memoria y programación de ejecución para minimizar el tiempo de respuesta y maximizar el rendimiento . [4]
Teoría [ editar ]
La teoría de la concurrencia ha sido un campo activo de investigación en la informática teórica . Una de las primeras propuestas fue el trabajo fundamental de Carl Adam Petri sobre las redes de Petri a principios de la década de 1960. En los años transcurridos desde entonces, se ha desarrollado una amplia variedad de formalismos para modelar y razonar sobre la concurrencia.
Modelos [ editar ]
Se han desarrollado varios formalismos para modelar y comprender sistemas concurrentes, que incluyen: [5]
- La máquina paralela de acceso aleatorio [6]
- El modelo de actor
- Modelos de puente computacional como el modelo paralelo síncrono masivo (BSP)
- Redes de Petri
- Cálculos de proceso
- Cálculo de sistemas de comunicación (CCS)
- Modelo de comunicación de procesos secuenciales (CSP)
- π-cálculo
- Espacios de tupla , p. Ej., Linda
- Programación simple concurrente orientada a objetos (SCOOP)
- Lenguaje de coordinación Reo
Algunos de estos modelos de concurrencia están destinados principalmente a respaldar el razonamiento y la especificación, mientras que otros se pueden utilizar a lo largo de todo el ciclo de desarrollo, incluido el diseño, la implementación, la prueba, las pruebas y la simulación de sistemas concurrentes. Algunos de estos se basan en el paso de mensajes , mientras que otros tienen diferentes mecanismos de simultaneidad.
La proliferación de diferentes modelos de concurrencia ha motivado a algunos investigadores a desarrollar formas de unificar estos diferentes modelos teóricos. Por ejemplo, Lee y Sangiovanni-Vincentelli han demostrado que un modelo llamado "señal etiquetada" se puede utilizar para proporcionar un marco común para definir la semántica denotacional de una variedad de diferentes modelos de concurrencia, [7] mientras que Nielsen, Sassone , y Winskel han demostrado que la teoría de categorías se puede utilizar para proporcionar una comprensión unificada similar de diferentes modelos. [8]
El teorema de representación de concurrencia en el modelo de actor proporciona una forma bastante general de representar sistemas concurrentes que están cerrados en el sentido de que no reciben comunicaciones del exterior. (Otros sistemas de concurrencia, por ejemplo, los cálculos de procesos se pueden modelar en el modelo de actor usando un protocolo de compromiso de dos fases . [9] ) La denotación matemática denotada por un sistema cerrado S se construye aproximaciones cada vez mejores a partir de un comportamiento inicial llamado ⊥ S usando un comportamiento que se aproxima a la progresión de la función S para construir una denotación (significado) para S de la siguiente manera: [10]
- Denote S ≡ ⊔ i∈ω progresión S i (⊥ S )
De esta manera, S se puede caracterizar matemáticamente en términos de todos sus posibles comportamientos.
Lógicas [ editar ]
Se pueden utilizar varios tipos de lógica temporal [11] para ayudar a razonar sobre sistemas concurrentes. Algunas de estas lógicas, como la lógica temporal lineal y la lógica del árbol de cálculo , permiten hacer afirmaciones sobre las secuencias de estados por las que puede pasar un sistema concurrente. Otros, como la lógica computacional acción de árbol , la lógica Hennessy-Milner , y de Lamport lógica temporal de las acciones , construyen sus afirmaciones a partir de secuencias de acciones (cambios en el estado). La principal aplicación de estas lógicas es escribir especificaciones para sistemas concurrentes. [3]
Practica [ editar ]
Esta sección no cita ninguna fuente . ( Abril de 2007 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) |
La programación concurrente abarca lenguajes de programación y algoritmos utilizados para implementar sistemas concurrentes. La programación concurrente generalmente se considera más general que la programación paralela porque puede involucrar patrones arbitrarios y dinámicos de comunicación e interacción, mientras que los sistemas paralelos generalmente tienen un patrón de comunicaciones predefinido y bien estructurado. Los objetivos básicos de la programación concurrente incluyen la corrección , el rendimiento y la solidez . Sistemas concurrentes como sistemas operativos y sistemas de gestión de bases de datosPor lo general, están diseñados para funcionar de manera indefinida, incluida la recuperación automática de fallas, y no terminan inesperadamente (consulte Control de concurrencia ). Algunos sistemas concurrentes implementan una forma de concurrencia transparente, en la que las entidades computacionales concurrentes pueden competir por un solo recurso y compartirlo, pero las complejidades de esta competencia e intercambio están protegidas del programador.
Debido a que usan recursos compartidos, los sistemas concurrentes en general requieren la inclusión de algún tipo de árbitro en algún lugar de su implementación (a menudo en el hardware subyacente), para controlar el acceso a esos recursos. El uso de árbitros introduce la posibilidad de indeterminación en el cálculo concurrente, lo que tiene importantes implicaciones para la práctica, incluida la corrección y el rendimiento. Por ejemplo, el arbitraje introduce un no determinismo ilimitado que plantea problemas con la verificación del modelo porque causa una explosión en el espacio de estados e incluso puede hacer que los modelos tengan un número infinito de estados.
Algunos modelos de programación concurrente incluyen coprocesos y concurrencia determinista . En estos modelos, los hilos de control ceden explícitamente su tiempo, ya sea al sistema oa otro proceso.
Ver también [ editar ]
- Chu espacio
- Nodos de red cliente-servidor
- Clojure
- Nodos de clúster
- Control de concurrencia
- Computación concurrente
- Programación concurrente orientada a objetos
- Patrón de concurrencia
- Construcción y análisis de procesos distribuidos (CADP)
- D (lenguaje de programación)
- Nodos de sistema distribuidos
- Elixir (lenguaje de programación)
- Erlang (lenguaje de programación)
- Go (lenguaje de programación)
- Gordon Pask
- Congreso Internacional de Teoría de la Concurrencia (CONCUR)
- OpenMP
- Computación paralela
- Espacio de direcciones global particionado
- Procesos
- Proyecto Ptolomeo
- Rust (lenguaje de programación)
- Gavilla (matemáticas)
- Hilos
- X10 (lenguaje de programación)
Referencias [ editar ]
- ^ Lamport, Leslie (julio de 1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" (PDF) . Comunicaciones de la ACM . 21 (7): 558–565. doi : 10.1145 / 359545.359563 . Consultado el 4 de febrero de 2016 .
- ^ Lamport, Leslie . "Conferencia de Turing: La informática de la concurrencia: los primeros años (Comunicaciones de la ACM, Vol. 58 No. 6, junio de 2015)" . ACM . Consultado el 22 de marzo de 2017 .
- ^ a b Cleaveland, Rance; Scott Smolka (diciembre de 1996). "Direcciones estratégicas en la investigación de la concurrencia". Encuestas de computación ACM . 28 (4): 607. doi : 10.1145 / 242223.242252 .
- ^ Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (agosto de 2010). Programación paralela con Microsoft .NET . Microsoft Press. ISBN 978-0-7356-5159-3.
- ^ Filman, Robert; Daniel Friedman (1984). Computación coordinada: herramientas y técnicas para software distribuido . McGraw-Hill. ISBN 978-0-07-022439-1.
- ^ Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Programación práctica de PRAM . John Wiley e hijos.
- ^ Lee, Edward; Alberto Sangiovanni-Vincentelli (diciembre de 1998). "Un marco para comparar modelos de computación" (PDF) . Transacciones IEEE en CAD . 17 (12): 1217-1229. doi : 10.1109 / 43.736561 .
- ^ Mogens Nielsen; Vladimiro Sassone; Glynn Winskel (1993). "Relaciones entre modelos de concurrencia" . Escuela REX / Simposio .
- ^ Frederick Knabe. Un protocolo distribuido para la comunicación basada en canales con Choice PARLE 1992.
- ^ William Clinger (junio de 1981). "Fundamentos de la semántica del actor". Tesis de Doctorado en Matemáticas. MIT. hdl : 1721,1 / 6935 . Cite journal requiere
|journal=( ayuda ) - ^ Roscoe, Colin (2001). Propiedades modales y temporales de los procesos . Saltador. ISBN 978-0-387-98717-0.
Lectura adicional [ editar ]
- Lynch, Nancy A. (1996). Algoritmos distribuidos . Morgan Kaufmann. ISBN 978-1-55860-348-6.
- Tanenbaum, Andrew S .; Van Steen, Maarten (2002). Sistemas distribuidos: principios y paradigmas . Prentice Hall. ISBN 978-0-13-088893-8.
- Kurki-Suonio, Reino (2005). Una teoría práctica de los sistemas reactivos . Saltador. ISBN 978-3-540-23342-8.
- Garg, Vijay K. (2002). Elementos de la Computación Distribuida . Prensa de Wiley-IEEE. ISBN 978-0-471-03600-5.
- Magee, Jeff; Kramer, Jeff (2006). Simultaneidad: modelos de estado y programación Java . Wiley. ISBN 978-0-470-09355-9.
- Distefano, S. y Bruneo, D. (2015). Evaluaciones cuantitativas de sistemas distribuidos: Metodologías y técnicas (1ª ed.). Somerset: John Wiley & Sons Inc. ISBN 9781119131144
- Bhattacharyya, SS (2013; 2014;). Manual de sistemas de procesamiento de señales (segundo; 2; segundo 2013; ed.). Nueva York, NY: Springer.10.1007 / 978-1-4614-6859-2 ISBN 9781461468592
- Wolter, K. (2012; 2014;). Evaluación de la resiliencia y evaluación de los sistemas informáticos (1. Aufl.; 1; ed.). Londres; Berlín ;: Springer. ISBN 9783642290329
Enlaces externos [ editar ]
- Sistemas concurrentes en la biblioteca virtual WWW
- Presentación de patrones de concurrencia dada en scaleconf
