Computación concurrente

La computación concurrente es una forma de computación en la que se ejecutan varios cálculos simultáneamente —durante períodos de tiempo superpuestos— en lugar de secuencialmente , de manera que uno finaliza antes de que comience el siguiente.

Esta es una propiedad de un sistema —ya sea un programa , una computadora o una red— donde existe un punto de ejecución independiente o "hilo de control" para cada proceso. Un sistema concurrente es aquel en el que un cálculo puede avanzar sin esperar a que todos los demás cálculos finalicen. ^{[ 1 ]}

La computación concurrente es una forma de programación modular . En su paradigma, un cálculo global se divide en subcálculos que pueden ejecutarse simultáneamente. Entre los pioneros en el campo de la computación concurrente se encuentran Edsger Dijkstra , Per Brinch Hansen y CAR Hoare . ^{[ 2 ]}

El concepto de computación concurrente se confunde frecuentemente con el concepto relacionado pero distinto de computación paralela , ^{[ 3 ] [ 4 ]} aunque ambos pueden describirse como "múltiples procesos que se ejecutan durante el mismo período de tiempo ". En la computación paralela, la ejecución ocurre en el mismo instante físico: por ejemplo, en procesadores separados de una máquina multiprocesador , con el objetivo de acelerar los cálculos; la computación paralela es imposible en un solo procesador ( de un solo núcleo ), ya que solo puede ocurrir un cálculo en cualquier instante (durante cualquier ciclo de reloj). ^{[ a ]} Por el contrario, la computación concurrente consiste en vidas útiles de procesos que se superponen, pero la ejecución no ocurre en el mismo instante. El objetivo aquí es modelar procesos que ocurren concurrentemente, como múltiples clientes que acceden a un servidor al mismo tiempo. Estructurar los sistemas de software como compuestos de múltiples partes concurrentes y comunicantes puede ser útil para abordar la complejidad, independientemente de si las partes pueden ejecutarse en paralelo. ^{[ 5 ] : 1}

Por ejemplo, se pueden ejecutar procesos concurrentes en un mismo núcleo intercalando las etapas de ejecución de cada proceso mediante segmentos de tiempo compartido : solo se ejecuta un proceso a la vez, y si no finaliza durante su segmento, se pausa , otro proceso comienza o se reanuda, y posteriormente se reanuda el proceso original. De esta forma, varios procesos se encuentran en ejecución en un mismo instante, pero solo uno se está ejecutando en ese momento.

Los cálculos concurrentes pueden ejecutarse en paralelo, ^{[ 3 ] [ 6 ]} por ejemplo, asignando cada proceso a un procesador o núcleo de procesador separado, o distribuyendo un cálculo a través de una red.

El momento exacto en que se ejecutan las tareas en un sistema concurrente depende de la planificación , y las tareas no siempre tienen que ejecutarse simultáneamente. Por ejemplo, dadas dos tareas, T1 y T2:

• T1 puede ejecutarse y finalizarse antes que T2 o viceversa (en serie y secuencial).
• T1 y T2 pueden ejecutarse alternativamente (en serie y simultáneamente).
• T1 y T2 pueden ejecutarse simultáneamente en el mismo instante (en paralelo y concurrente).

La palabra "secuencial" se usa como antónimo tanto de "concurrente" como de "paralelo"; cuando se distinguen explícitamente, concurrente/secuencial y paralelo/serie se usan como pares opuestos. ^{[ 7 ]} Una planificación en la que las tareas se ejecutan una a la vez (serie, sin paralelismo), sin intercalación (secuencialmente, sin concurrencia: ninguna tarea comienza hasta que la anterior termina) se llama planificación serial . Un conjunto de tareas que se pueden planificar serialmente es serializable , lo que simplifica el control de concurrencia .

bool retirar ( int retirar ){si ( saldo >= retiro ){saldo -= retiro ;devolver verdadero ;}devolver falso ;}

Introducidas en 1962, las redes de Petri fueron un primer intento de codificar las reglas de la ejecución concurrente. La teoría del flujo de datos se basó posteriormente en estas, y se crearon arquitecturas de flujo de datos para implementar físicamente las ideas de dicha teoría. A partir de finales de la década de 1970, se desarrollaron cálculos de procesos como el Cálculo de Sistemas Comunicantes (CCS) y los Procesos Secuenciales Comunicantes (CSP) para permitir el razonamiento algebraico sobre sistemas compuestos por componentes que interactúan entre sí. El cálculo π añadió la capacidad de razonar sobre topologías dinámicas.

Los autómatas de entrada/salida se introdujeron en 1987.

También se han desarrollado lógicas como la TLA+ de Lamport y modelos matemáticos como los diagramas de trazas y los diagramas de eventos de actores para describir el comportamiento de los sistemas concurrentes.

La memoria transaccional de software toma prestado de la teoría de bases de datos el concepto de transacciones atómicas y lo aplica a los accesos a la memoria.

Para implementar programas concurrentes se pueden utilizar diversos métodos, como implementar cada ejecución computacional como un proceso del sistema operativo o implementar los procesos computacionales como un conjunto de hilos dentro de un único proceso del sistema operativo.

La computación concurrente se desarrolló a partir de trabajos previos sobre ferrocarriles y telegrafía , de los siglos XIX y principios del XX, y algunos términos datan de este período, como los semáforos. Estos surgieron para abordar la cuestión de cómo gestionar múltiples trenes en el mismo sistema ferroviario (evitando colisiones y maximizando la eficiencia) y cómo gestionar múltiples transmisiones a través de un conjunto determinado de cables (mejorando la eficiencia), por ejemplo, mediante la multiplexación por división de tiempo (década de 1870).

El estudio académico de los algoritmos concurrentes comenzó en la década de 1960, y se le atribuye a Dijkstra (1965) el primer artículo en este campo, en el que identificó y resolvió la exclusión mutua . ^{[ 12 ]}

La concurrencia es omnipresente en la informática, y se da desde el hardware de bajo nivel en un solo chip hasta las redes mundiales. A continuación se muestran algunos ejemplos.

A nivel de lenguaje de programación:

• Canal
• Corutina
• Futuros y promesas

A nivel del sistema operativo:

• Multitarea informática , que incluye tanto la multitarea cooperativa como la multitarea preventiva.
  • El tiempo compartido , que reemplazó el procesamiento secuencial por lotes de trabajos con el uso concurrente de un sistema.
• Proceso
• Hilo

A nivel de red, los sistemas en red son generalmente concurrentes por naturaleza, ya que constan de dispositivos separados.

Los lenguajes de programación concurrentes son lenguajes de programación que utilizan construcciones del lenguaje para la concurrencia . Estas construcciones pueden incluir multihilo , soporte para computación distribuida , paso de mensajes , recursos compartidos (incluida la memoria compartida ) o futuros y promesas . Dichos lenguajes a veces se describen como lenguajes orientados a la concurrencia o lenguajes de programación orientados a la concurrencia (COPL). ^{[ 13 ]}

Actualmente, los lenguajes de programación más utilizados que cuentan con estructuras específicas para la concurrencia son Java y C# . Ambos lenguajes emplean fundamentalmente un modelo de concurrencia de memoria compartida, con bloqueo proporcionado por monitores (aunque se pueden implementar, y de hecho se han implementado, modelos de paso de mensajes sobre el modelo subyacente de memoria compartida). De los lenguajes que utilizan un modelo de concurrencia de paso de mensajes, Erlang era probablemente el más utilizado en la industria en 2010.

Muchos lenguajes de programación concurrente se han desarrollado más como lenguajes de investigación (por ejemplo, Pict ) que como lenguajes para uso en producción. Sin embargo, lenguajes como Erlang , Limbo y occam se han utilizado industrialmente en diversos momentos durante los últimos 20 años. A continuación, se presenta una lista no exhaustiva de lenguajes que utilizan o proporcionan funcionalidades de programación concurrente:

• Ada : de propósito general, con soporte nativo para el paso de mensajes y la concurrencia basada en monitores.
• Alef : concurrente, con subprocesos y paso de mensajes, para la programación de sistemas en las primeras versiones de Plan 9 de Bell Labs.
• Alice : extensión de Standard ML , añade soporte para concurrencia mediante futuros.
• Ateji PX : extensión para Java con primitivas paralelas inspiradas en el cálculo π.
• Axum : específico del dominio, concurrente, basado en el modelo de actores y .NET Common Language Runtime, utilizando una sintaxis similar a la de C.
• Máquina de flujo de datos modular binaria (BMDFM)
• C++ – bibliotecas de soporte para hilos y corrutinas ^{[ 14 ] [ 15 ]}
• Cω (C omega) – para investigación, extiende C#, utiliza comunicación asíncrona
• C# – admite computación concurrente mediante lock , yield , y desde la versión 5.0 se introdujeron las palabras clave async y await.
• Clojure : dialecto de programación funcional y moderno de Lisp en la plataforma Java .
• Concurrent Clean : programación funcional, similar a Haskell.
• Colecciones concurrentes (CnC): logra un paralelismo implícito independiente del modelo de memoria al definir explícitamente el flujo de datos y el control.
• Haskell concurrente : lenguaje funcional puro y perezoso que opera procesos concurrentes en memoria compartida.
• Aprendizaje automático concurrente : extensión concurrente del aprendizaje automático estándar.
• Pascal concurrente – por Per Brinch Hansen
• Curry
• D – lenguaje de programación de sistemas multiparadigma con soporte explícito para programación concurrente ( modelo de actores )
• E – utiliza promesas para evitar interbloqueos
• ECMAScript : utiliza promesas para operaciones asíncronas.
• Eiffel , a través de su mecanismo SCOOP basado en los conceptos de Diseño por Contrato
• Elixir : lenguaje dinámico y funcional que admite metaprogramación y se ejecuta en la máquina virtual de Erlang, que utiliza paso de mensajes asíncrono sin memoria compartida.
• Erlang : lenguaje dinámico y funcional que se ejecuta en la máquina virtual de Erlang, que utiliza paso de mensajes asíncrono sin memoria compartida.
• FAUST – compilador funcional en tiempo real para procesamiento de señales, que proporciona paralelización automática a través de OpenMP o un planificador de robo de trabajo específico .
• Fortran : los coarrays y la ejecución concurrente forman parte del estándar Fortran 2008.
• Go – para programación de sistemas, con un modelo de programación concurrente basado en procesos secuenciales comunicantes (CSP)
• Haskell – lenguaje de programación funcional concurrente y paralelo ^{[ 16 ]}
• Hume : funcional, concurrente, para entornos de espacio y tiempo limitados donde los procesos de autómatas se describen mediante patrones de canales síncronos y paso de mensajes.
• Io – concurrencia basada en actores
• Janus : presenta distintos emisores y emisores de variables lógicas, canales de bolsa; es puramente declarativo.
• Java – clase de hilo o interfaz Runnable
• Julia – primitivas de programación concurrente: tareas, espera asíncrona, canales ^{[ 17 ]}
• JavaScript : mediante web workers , en un entorno de navegador, promesas y funciones de devolución de llamada.
• JoCaml , una extensión de OCaml basada en canales concurrentes y distribuidos , implementa el cálculo de unión de procesos.
• Únete a Java : concurrente, basado en el lenguaje Java .
• Joule – basado en flujo de datos, se comunica mediante paso de mensajes
• Joyce – concurrente, para la enseñanza, basado en Concurrent Pascal con características de CSP por Per Brinch Hansen
• LabVIEW : gráfico, flujo de datos, las funciones son nodos en un gráfico, los datos son cables entre los nodos; incluye lenguaje orientado a objetos.
• Limbo – pariente de Alef , para programación de sistemas en Inferno (sistema operativo)
• Locomotive BASIC – La variante de BASIC para Amstrad contiene los comandos EVERY y AFTER para subrutinas concurrentes.
• MultiLisp : variante de Scheme extendida para admitir paralelismo.
• Modula-2 – para programación de sistemas, por Niklaus Wirth como sucesor de Pascal con soporte nativo para corrutinas
• Modula-3 : miembro moderno de la familia ALGOL con amplio soporte para hilos, mutexes y variables de condición.
• Newsqueak – para investigación, con los canales como valores de primera clase; predecesor de Alef
• occam – fuertemente influenciado por los procesos secuenciales comunicantes (CSP)
  • occam-π – variante moderna de occam , incluye ideas del cálculo π de Milner.
• Object REXX (ooRexx): intercambio de mensajes basado en objetos para la comunicación y la sincronización.
• Orc : altamente concurrente, no determinista, basado en el álgebra de Kleene.
• Oz-Mozart : multiparadigma, admite estado compartido y concurrencia por paso de mensajes, y futuros.
• ParaSail : orientado a objetos, paralelo, sin punteros, condiciones de carrera.
• PHP – soporte para multihilo con extensión paralela que implementa el paso de mensajes inspirado en Go ^{[ 18 ]}
• Pict : básicamente una implementación ejecutable del cálculo π de Milner.
• Python – utiliza paralelismo basado en hilos y paralelismo basado en procesos ^{[ 19 ]}
• Raku : incluye clases para hilos, promesas y canales por defecto ^{[ 20 ].}
• Reia : utiliza el paso de mensajes asíncrono entre objetos sin recursos compartidos.
• Rojo/Sistema : para programación de sistemas, basada en Rebol.
• Rust – para programación de sistemas, utilizando paso de mensajes con semántica de movimiento y memoria compartida (inmutable y mutable) ^{[ 21 ]}
• Scala : lenguaje de propósito general, diseñado para expresar patrones de programación comunes de forma concisa, elegante y con seguridad de tipos.
• SequenceL es una biblioteca funcional de propósito general cuyos principales objetivos de diseño son la facilidad de programación, la claridad y legibilidad del código, y la paralelización automática para un buen rendimiento en hardware multinúcleo, además de estar demostrablemente libre de condiciones de carrera.
• SR – para investigación
• SuperPascal – versión concurrente, para la enseñanza, basada en Concurrent Pascal y Joyce de Per Brinch Hansen.
• Swift : soporte integrado para escribir código asíncrono y paralelo de forma estructurada ^{[ 22 ].}
• Unicon – para investigación
• Lenguaje de especificación y descripción de TeleNokia ( TNSDL ): para el desarrollo de centrales de telecomunicaciones, utiliza paso de mensajes asíncrono.
• Lenguaje de descripción de hardware VHSIC ( VHDL ) – IEEE STD-1076
• XC – subconjunto del lenguaje C con extensión de concurrencia desarrollado por XMOS , basado en procesos secuenciales comunicantes , construcciones integradas para E/S programable

Muchos otros lenguajes ofrecen soporte para la concurrencia en forma de bibliotecas , a niveles aproximadamente comparables con la lista anterior.

• E/S asíncrona
• Espacio Chu
• Programación basada en flujo
• Mapa concurrente de Java
• Proyecto Ptolomeo
• Condición de carrera §  Informática
• Concurrencia estructurada
• Procesamiento de transacciones

• Dijkstra, EW (1965). "Solución de un problema en el control de programación concurrente" . Communications of the ACM . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID 19357737 . 
• Herlihy, Maurice (2008) [2008]. El arte de la programación multiprocesador . Morgan Kaufmann. ISBN 978-0123705914.
• Downey, Allen B. (2005) [2005]. El pequeño libro de los semáforos (PDF) . Green Tea Press. ISBN 978-1-4414-1868-5. Archivado del original (PDF) el 04-03-2016 . Consultado el 21-11-2009 .
• Filman, Robert E.; Daniel P. Friedman (1984). Computación coordinada: herramientas y técnicas para software distribuido . Nueva York: McGraw-Hill. pág . 370. ISBN  978-0-07-022439-1.
• Leppäjärvi, Jouni (2008). Un estudio pragmático e históricamente orientado sobre la universalidad de los primitivos de sincronización (PDF) . Universidad de Oulu. Archivado del original (PDF) el 30 de agosto de 2017. Recuperado el 13 de septiembre de 2012 .
• Taubenfeld, Gadi (2006). Algoritmos de sincronización y programación concurrente . Pearson / Prentice Hall. pág.  433. ISBN 978-0-13-197259-9.

• Contenido multimedia relacionado con la programación simultánea en Wikimedia Commons.
• Biblioteca virtual de sistemas concurrentes