Computación concurrente

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

Esta es una propiedad de un sistema, ya sea un programa, una computadora o una red, donde hay un punto de ejecución separado o "hilo de control" para cada proceso. Un sistema concurrente es aquel en el que un cálculo puede avanzar sin esperar a que se completen todos los demás cálculos.

La computación concurrente es una forma de programación modular. En su paradigma, un cómputo general se factoriza en subcálculos que pueden ejecutarse simultáneamente. Los pioneros en el campo de la computación concurrente incluyen a Edsger Dijkstra, Per Brinch Hansen y CAR Hoare.

Introducción

El concepto de computación concurrente se confunde con frecuencia con el concepto relacionado pero distinto de computación paralela, 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 núcleo), ya que solo uno el cálculo puede ocurrir en cualquier instante (durante cualquier ciclo de reloj). Por el contrario, la computación concurrente consiste en la vida útil de los procesossuperpuestos, pero la ejecución no tiene por qué ocurrir en el mismo instante. El objetivo aquí es modelar procesos en el mundo exterior que ocurren simultáneamente, como múltiples clientes que acceden a un servidor al mismo tiempo. La estructuración de sistemas de software como compuestos de múltiples partes simultáneas que se comunican puede ser útil para abordar la complejidad, independientemente de si las partes se pueden ejecutar en paralelo.

Por ejemplo, los procesos simultáneos se pueden ejecutar en un núcleo intercalando los pasos de ejecución de cada proceso a través de segmentos de tiempo compartido: solo se ejecuta un proceso a la vez, y si no se completa durante su segmento de tiempo, se pausa, otro proceso comienza o se reanuda, y luego se reanuda el proceso original. De esta forma, múltiples procesos están a medio camino de la ejecución en un solo instante, pero solo un proceso se está ejecutando en ese instante.

Los cálculos concurrentes se pueden ejecutar en paralelo, por ejemplo, asignando cada proceso a un procesador o núcleo de procesador independiente, o distribuyendo un cálculo a través de una red. Sin embargo, en general, los lenguajes, las herramientas y las técnicas para la programación paralela pueden no ser adecuados para la programación concurrente y viceversa.

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

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

La palabra "secuencial" se utiliza como antónimo tanto de "concurrente" como de "paralelo"; cuando estos se distinguen explícitamente, concurrente/secuencial y paralelo/serie se utilizan como pares opuestos. Un cronograma en el que las tareas se ejecutan una a la vez (en serie, sin paralelismo), sin intercalar (secuencialmente, sin concurrencia: ninguna tarea comienza hasta que finaliza la tarea anterior) se denomina cronograma en serie. Un conjunto de tareas que se pueden programar en serie es serializable, lo que simplifica el control de concurrencia.

Coordinar el acceso a los recursos compartidos

El principal desafío en el diseño de programas concurrentes es el control de concurrencia: garantizar la secuencia correcta de las interacciones o comunicaciones entre diferentes ejecuciones computacionales y coordinar el acceso a los recursos que se comparten entre las ejecuciones. Los problemas potenciales incluyen condiciones de carrera, interbloqueos y escasez de recursos. Por ejemplo, considere el siguiente algoritmo para realizar retiros de una cuenta corriente representada por el recurso compartido balance:

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

Supongamos que dos subprocesosbalance = 500 simultáneos realizan las llamadas y. Si la línea 3 en ambas operaciones se ejecuta antes que la línea 5, ambas operaciones encontrarán que se evalúa como, y la ejecución procederá a restar el monto del retiro. Sin embargo, dado que ambos procesos realizan sus retiros, el monto total retirado terminará siendo mayor que el saldo original. Este tipo de problemas con recursos compartidos se benefician del uso de algoritmos de control de concurrencia o de no bloqueo. withdraw(300)withdraw(350)balance >= withdrawaltrue

Ventajas

Las ventajas de la computación concurrente incluyen:

• Mayor rendimiento del programa: la ejecución paralela de un programa concurrente permite que la cantidad de tareas completadas en un tiempo determinado aumente proporcionalmente a la cantidad de procesadores de acuerdo con la ley de Gustafson
• Alta capacidad de respuesta para entrada/salida: los programas intensivos en entrada/salida en su mayoría esperan a que se completen las operaciones de entrada o salida. La programación concurrente permite que el tiempo que se pasaría esperando se use para otra tarea.
• Estructura de programa más apropiada: algunos problemas y dominios de problemas se adaptan bien a la representación como tareas o procesos concurrentes.

Modelos

Introducidas en 1962, las redes de Petri fueron un primer intento de codificar las reglas de ejecución concurrente. Más tarde, la teoría del flujo de datos se basó en estos, y se crearon arquitecturas de flujo de datos para implementar físicamente las ideas de la teoría del flujo de datos. A partir de fines de la década de 1970, se desarrollaron cálculos de procesos como Cálculo de sistemas de comunicación (CCS) y Procesos secuenciales de comunicación (CSP) para permitir el razonamiento algebraico sobre sistemas compuestos por componentes que interactúan. El cálculo π agregó 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 TLA+ de Lamport y modelos matemáticos como trazas y diagramas de eventos Actor para describir el comportamiento de sistemas concurrentes.

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

Modelos de consistencia

Los lenguajes de programación concurrentes y los programas multiprocesador deben tener un modelo de consistencia (también conocido como modelo de memoria). El modelo de consistencia define reglas sobre cómo ocurren las operaciones en la memoria de la computadora y cómo se producen los resultados.

Uno de los primeros modelos de consistencia fue el modelo de consistencia secuencial de Leslie Lamport. La consistencia secuencial es la propiedad de un programa de que su ejecución produce los mismos resultados que un programa secuencial. Específicamente, un programa es secuencialmente consistente si "los resultados de cualquier ejecución son los mismos que si las operaciones de todos los procesadores se ejecutaran en algún orden secuencial, y las operaciones de cada procesador individual aparecen en esta secuencia en el orden especificado por su programa". ".

Implementación

Se pueden usar varios métodos diferentes para implementar programas concurrentes, como implementar cada ejecución computacional como un proceso del sistema operativo o implementar los procesos computacionales como un conjunto de subprocesos dentro de un solo proceso del sistema operativo.

Interacción y comunicación

En algunos sistemas informáticos concurrentes, la comunicación entre los componentes concurrentes está oculta para el programador (por ejemplo, mediante el uso de futuros), mientras que en otros debe manejarse explícitamente. La comunicación explícita se puede dividir en dos clases:comunicación de memoria compartidaLos componentes simultáneos se comunican alterando el contenido de las ubicaciones de memoria compartida (ejemplificado por Java y C#). Este estilo de programación concurrente generalmente necesita el uso de alguna forma de bloqueo (por ejemplo, mutexes, semáforos o monitores) para coordinar entre hilos. Se dice que un programa que implementa correctamente cualquiera de estos es seguro para subprocesos.Comunicación de paso de mensajesLos componentes concurrentes se comunican intercambiando mensajes (ejemplificados por MPI, Go, Scala, Erlang y occam). El intercambio de mensajes puede llevarse a cabo de forma asincrónica, o puede utilizar un estilo de "cita" sincrónica en el que el remitente bloquea hasta que se recibe el mensaje. El paso de mensajes asincrónicos puede ser confiable o no confiable (a veces denominado "enviar y rezar"). La concurrencia de paso de mensajes tiende a ser mucho más fácil de razonar que la concurrencia de memoria compartida y, por lo general, se considera una forma más robusta de programación concurrente. Se encuentra disponible una amplia variedad de teorías matemáticas para comprender y analizar los sistemas de paso de mensajes, incluido el modelo de actor y varios cálculos de procesos. El paso de mensajes se puede implementar de manera eficiente a través del multiprocesamiento simétrico,

La memoria compartida y la concurrencia de paso de mensajes tienen diferentes características de rendimiento. Por lo general (aunque no siempre), la sobrecarga de memoria por proceso y la sobrecarga de cambio de tareas es menor en un sistema de paso de mensajes, pero la sobrecarga de paso de mensajes es mayor que para una llamada a procedimiento. Estas diferencias a menudo se ven superadas por otros factores de rendimiento.

Historia

La computación concurrente se desarrolló a partir de trabajos anteriores sobre ferrocarriles y telegrafía, del siglo XIX y principios del XX, y algunos términos datan de este período, como semáforos. Estos surgieron para abordar la cuestión de cómo manejar múltiples trenes en el mismo sistema ferroviario (evitando colisiones y maximizando la eficiencia) y cómo manejar múltiples transmisiones a través de un conjunto determinado de cables (mejorando la eficiencia), como a través de 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, con Dijkstra (1965) acreditado como el primer artículo en este campo, identificando y resolviendo la exclusión mutua.

Predominio

La simultaneidad es omnipresente en la informática y se produce desde hardware de bajo nivel en un solo chip hasta redes mundiales. Los ejemplos siguen.

A nivel de lenguaje de programación:

• Canal
• Corrutina
• Futuros y promesas

A nivel de sistema operativo:

• Multitarea informática, incluida la multitarea cooperativa y la multitarea preventiva
  • Tiempo compartido, que reemplazó el procesamiento secuencial por lotes de trabajos con el uso simultáneo de un sistema
• Proceso
• Hilo

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

Lenguajes que soportan la programación concurrente

Los lenguajes de programación concurrentes son lenguajes de programación que usan construcciones de lenguaje para la concurrencia. Estas construcciones pueden implicar subprocesos múltiples, 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).

Hoy en día, los lenguajes de programación más utilizados que tienen construcciones específicas para la concurrencia son Java y C#. Ambos lenguajes utilizan fundamentalmente un modelo de concurrencia de memoria compartida, con bloqueo proporcionado por monitores (aunque los modelos de paso de mensajes pueden implementarse y se han implementado sobre el modelo de memoria compartida subyacente). De los lenguajes que utilizan un modelo de concurrencia de paso de mensajes, Erlang es probablemente el más utilizado en la industria en la actualidad.

Muchos lenguajes de programación concurrentes 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 han tenido un uso industrial en varios momentos en los últimos 20 años. Una lista no exhaustiva de lenguajes que utilizan o proporcionan servicios de programación concurrentes:

• Ada: propósito general, con soporte nativo para paso de mensajes y concurrencia basada en monitor
• Alef: concurrente, con subprocesos y paso de mensajes, para la programación del sistema en versiones anteriores de Plan 9 de Bell Labs
• Alice: extensión a Standard ML, agrega soporte para concurrencia a través de futuros
• Ateji PX: extensión a Java con primitivas paralelas inspiradas en el cálculo π
• Axum: específico del dominio, concurrente, basado en el modelo de actor y.NET Common Language Runtime usando una sintaxis similar a C
• BMDFM—Máquina de flujo de datos modular binario
• C++—estándar::hilo
• Cω (C omega): para investigación, amplía C#, utiliza comunicación asíncrona
• C#: admite computación concurrente usando lock, yield, también desde la versión 5.0 asíncrono y palabras clave en espera introducidas
• Clojure: dialecto moderno y funcional de Lisp en la plataforma Java
• Limpieza concurrente: programación funcional, similar a Haskell
• Recopilaciones simultáneas (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 la memoria compartida
• Aprendizaje automático concurrente: extensión simultánea del aprendizaje automático estándar
• Pascal concurrente—por Per Brinch Hansen
• Curry
• D: lenguaje de programación de sistemas de múltiples paradigmas con soporte explícito para programación concurrente (modelo de actor)
• E: utiliza promesas para evitar puntos muertos
• ECMAScript: utiliza promesas para operaciones asincrónicas
• Eiffel—a través de su mecanismo SCOOP basado en los conceptos de Design by Contract
• Elixir: lenguaje consciente de metaprogramación dinámico y funcional que se ejecuta en la máquina virtual Erlang.
• Erlang: utiliza el paso de mensajes asíncronos sin compartir nada
• FAUST: funcional en tiempo real, para el procesamiento de señales, el compilador proporciona paralelización automática a través de OpenMP o un programador de robo de trabajo específico
• Fortran: coarrays y do concurrent son parte del estándar Fortran 2008
• Go: para la programación del sistema, con un modelo de programación concurrente basado en CSP
• Haskell: lenguaje de programación funcional concurrente y paralelo
• Hume: funcional, concurrente, para entornos de espacio y tiempo limitados donde los procesos de autómatas se describen mediante patrones de canales sincrónicos y paso de mensajes.
• Io: simultaneidad basada en actores
• Janus: cuenta con personas que preguntan y cuentan distintas variables lógicas , canales de bolsa; es puramente declarativo
• Java: clase de subproceso o interfaz ejecutable
• Julia: "primitivas de programación concurrentes: tareas, espera asíncrona, canales".
• JavaScript: a través de trabajadores web, en un entorno de navegador, promesas y devoluciones de llamada.
• JoCaml: basado en canales simultáneos y distribuidos, extensión de OCaml, implementa el cálculo conjunto de procesos
• Únase a Java: simultáneo, basado en el lenguaje Java
• Joule: basado en el flujo de datos, se comunica mediante el paso de mensajes
• Joyce: concurrente, didáctico, basado en Concurrent Pascal con funciones de CSP de 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: relativo a Alef, para la programación del sistema en Inferno (sistema operativo)
• MultiLisp: variante del esquema ampliada para admitir el paralelismo
• Modula-2: para programación de sistemas, por N. Wirth como sucesor de Pascal con soporte nativo para rutinas
• Modula-3: miembro moderno de la familia Algol con amplio soporte para subprocesos, mutexes, variables de condición
• Newsqueak: para investigación, con canales como valores de primera clase; antecesor de Alef
• occam: fuertemente influenciado por la comunicación de procesos secuenciales (CSP)
  • occam-π: una variante moderna de occam, que incorpora ideas del cálculo π de Milner
• Orco: muy concurrente, no determinista, basado en el álgebra de Kleene
• Oz-Mozart: multiparadigma, admite concurrencia de estado compartido y paso de mensajes, y futuros
• ParaSail—orientado a objetos, paralelo, libre de punteros, condiciones de carrera
• Pict: esencialmente una implementación ejecutable del cálculo π de Milner
• Raku incluye clases para hilos, promesas y canales por defecto
• Python: utiliza paralelismo basado en subprocesos y paralelismo basado en procesos
• Reia: utiliza el paso de mensajes asincrónicos entre objetos que no comparten nada
• Rojo/Sistema: para la programación del sistema, basado en Rebol
• Rust: para la programación del sistema, utilizando el paso de mensajes con semántica de movimiento, memoria inmutable compartida y memoria mutable compartida.
• Scala: propósito general, diseñado para expresar patrones de programación comunes de una manera concisa, elegante y con seguridad de tipos
• SequenceL: funcional de propósito general, los principales objetivos de diseño son la facilidad de programación, la claridad y la legibilidad del código y la paralelización automática para el rendimiento en hardware multinúcleo y demostrablemente libre de condiciones de carrera.
• SR—para investigación
• SuperPascal: concurrente, para la enseñanza, basado en Concurrent Pascal y Joyce por Per Brinch Hansen
• Unicon: para la investigación
• TNSDL: para desarrollar intercambios de telecomunicaciones, utiliza el paso de mensajes asíncronos
• Lenguaje de descripción de hardware VHSIC (VHDL): IEEE STD-1076
• XC: subconjunto extendido de concurrencia del lenguaje C desarrollado por XMOS, basado en la comunicación de procesos secuenciales, construcciones integradas para E/S programables

Muchos otros lenguajes brindan soporte para la concurrencia en forma de bibliotecas, a niveles más o menos comparables con la lista anterior.