Ejecutar varios cálculos durante períodos de tiempo superpuestos
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, 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. [1]
La computación concurrente es una forma de programación modular . En su paradigma, un cálculo general se descompone en subcómputos 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]
Introducción
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 núcleo ), ya que solo hay un El cálculo puede ocurrir en cualquier instante (durante cualquier ciclo de reloj). [a] Por el contrario, la computación concurrente consiste en la superposición de la duración de los procesos , pero no es necesario que la ejecución ocurra en el mismo instante. El objetivo aquí es modelar procesos en el mundo exterior que ocurren simultáneamente, como que varios clientes accedan a un servidor al mismo tiempo. Estructurar sistemas de software como si estuvieran compuestos por múltiples partes comunicantes simultáneas puede ser útil para abordar la complejidad, independientemente de si las partes se pueden ejecutar en paralelo. [5] : 1
Por ejemplo, los procesos concurrentes se pueden ejecutar en un núcleo intercalando los pasos de ejecución de cada proceso a través de intervalos de tiempo compartido : solo se ejecuta un proceso a la vez, y si no se completa durante su intervalo de tiempo, se pausa , otro proceso comienza o se reanuda, y luego se reanuda el proceso original. De esta manera, varios procesos se encuentran en la mitad de la ejecución en un solo instante, pero solo se está ejecutando un proceso en ese instante. [ cita necesaria ]
Los cálculos concurrentes se pueden ejecutar 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 programación , y no siempre es necesario que las tareas se ejecuten al mismo tiempo. Por ejemplo, dadas dos tareas, T1 y T2: [ cita necesaria ]
- T1 puede ejecutarse y finalizarse antes que T2 o viceversa (serial y secuencial)
- T1 y T2 pueden ejecutarse alternativamente (en 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 se distinguen explícitamente, se utilizan concurrente/secuencial y paralelo/serial 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 llama cronograma en serie . Un conjunto de tareas que se pueden programar en serie es serializable , lo que simplifica el control de concurrencia . [ cita necesaria ]
Coordinar el acceso a recursos compartidos
El principal desafío al diseñar programas concurrentes es el control de la concurrencia : garantizar la secuenciación correcta de las interacciones o comunicaciones entre diferentes ejecuciones computacionales y coordinar el acceso a los recursos que se comparten entre las ejecuciones. [6] Los problemas potenciales incluyen condiciones de carrera , estancamientos y escasez de recursos . Por ejemplo, considere el siguiente algoritmo para realizar retiros de una cuenta corriente representada por el recurso compartido balance
:
bool retirar ( int retiro ) { si ( saldo >= retiro ) { saldo -= retiro ; devolver verdadero ; } falso retorno ; }
Supongamos que dos subprocesosbalance = 500
simultáneos realizan las llamadas y . Si la línea 3 en ambas operaciones se ejecuta antes de 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 control de concurrencia o algoritmos sin bloqueo .withdraw(300)
withdraw(350)
balance >= withdrawal
true
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 dedicaría a esperar se utilice para otra tarea. [ cita necesaria ]
- Estructura de programa más apropiada: algunos problemas y dominios de problemas se adaptan bien a la representación como tareas o procesos concurrentes. [ cita necesaria ]
Modelos
Introducidas en 1962, las redes de Petri fueron un primer intento de codificar las reglas de ejecución concurrente. Posteriormente, 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 finales de la década de 1970, se desarrollaron cálculos de procesos como el cálculo de sistemas en comunicación (CCS) y los procesos de comunicación secuencial (CSP) para permitir el razonamiento algebraico sobre sistemas compuestos por componentes que interactúan. 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 TLA+ de Lamport y modelos matemáticos como trazas y diagramas de eventos de 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 lo 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 coherencia (también conocido como modelo de memoria). El modelo de coherencia 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 coherencia 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". ". [8]
Implementación
Se pueden utilizar 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 único proceso del sistema operativo.
Interacción y comunicación.
En algunos sistemas informáticos concurrentes, la comunicación entre los componentes concurrentes está oculta al 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 compartida
- Los componentes concurrentes se comunican alterando el contenido de las ubicaciones de memoria compartida (ejemplificados por Java y C# ). Este estilo de programación concurrente generalmente necesita el uso de algún tipo de bloqueo (por ejemplo, mutex , semáforos o monitores ) para coordinar entre subprocesos. Se dice que un programa que implementa adecuadamente cualquiera de estos es seguro para subprocesos .
- Comunicación de paso de mensajes.
- Los componentes concurrentes se comunican mediante el intercambio de mensajes (ejemplificados por MPI , Go , Scala , Erlang y occam ). El intercambio de mensajes puede realizarse de forma asincrónica o puede utilizar un estilo de "encuentro" sincrónico en el que el remitente se bloquea hasta que se recibe el mensaje. El paso de mensajes asincrónicos puede ser confiable o no confiable (a veces denominado "enviar y orar"). La simultaneidad de paso de mensajes tiende a ser mucho más fácil de razonar que la simultaneidad de memoria compartida y, por lo general, se considera una forma más sólida de programación concurrente. [ cita necesaria ] Se encuentra disponible una amplia variedad de teorías matemáticas para comprender y analizar los sistemas de transmisión de mensajes, incluido el modelo de actor y varios cálculos de procesos . El paso de mensajes se puede implementar eficientemente mediante multiprocesamiento simétrico , con o sin coherencia de caché de memoria compartida .
La memoria compartida y la concurrencia de paso de mensajes tienen diferentes características de rendimiento. Normalmente (aunque no siempre), la sobrecarga de memoria por proceso y la sobrecarga de conmutación de tareas es menor en un sistema de paso de mensajes, pero la sobrecarga del 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 los 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 por ejemplo mediante 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 a Dijkstra (1965) se le atribuye ser el primer artículo en este campo, identificando y resolviendo la exclusión mutua . [9]
Predominio
La concurrencia es omnipresente en la informática y ocurre desde hardware de bajo nivel en un solo chip hasta redes mundiales. Siguen ejemplos.
A nivel de lenguaje de programación:
A nivel del sistema operativo:
A nivel de red, los sistemas en red son generalmente concurrentes por su naturaleza, ya que constan de dispositivos separados.
Lenguajes que soportan programación concurrente
Los lenguajes de programación concurrentes son lenguajes de programación que utilizan 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 . Estos lenguajes a veces se describen como lenguajes orientados a la concurrencia o lenguajes de programación orientados a la concurrencia (COPL). [10]
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. [ cita necesaria ]
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, idiomas como Erlang , Limbo y occam han tenido uso industrial en varios momentos de los últimos 20 años. Una lista no exhaustiva de lenguajes que utilizan o proporcionan funciones de programación concurrentes:
- Ada : propósito general, con soporte nativo para paso de mensajes y simultaneidad basada en monitoreo
- Alef : concurrente, con subprocesos y paso de mensajes, para la programación del sistema en las primeras versiones del Plan 9 de Bell Labs
- Alice : extensión de 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 de 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++: bibliotecas de soporte de subprocesos y rutinas [11] [12]
- Cω (C omega): para investigación, extiende C# y utiliza comunicación asincrónica
- C# : admite computación concurrente usando lock, yield, también desde la versión 5.0 se introdujeron las palabras clave async y await
- Clojure : dialecto moderno y funcional de Lisp en la plataforma Java
- Limpieza concurrente : 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
- ML concurrente : extensión concurrente de ML 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 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 Diseño por Contrato
- Elixir : lenguaje dinámico y funcional compatible con metaprogramación que se ejecuta en Erlang VM.
- Erlang : utiliza el paso de mensajes sincrónico o asincrónico sin memoria compartida
- FAUST : funcional en tiempo real, para 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 : los coarrays y do concurrentes son parte del estándar Fortran 2008
- Go : para programación de sistemas, con un modelo de programación concurrente basado en CSP
- Haskell : lenguaje de programación funcional concurrente y paralelo [13]
- 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 : presenta distintos preguntadores y contadores de variables lógicas, canales de bolsas; es puramente declarativo
- Java : clase de subproceso o interfaz ejecutable
- Julia : "primitivas de programación concurrente: tareas, espera asíncrona, canales". [14]
- JavaScript : a través de trabajadores web , en un entorno de navegador, promesas y devoluciones de llamada .
- JoCaml : extensión de OCaml basada en canales concurrentes y distribuidos , implementa el cálculo de unión de procesos
- Unirse a Java : simultáneo, basado en el lenguaje Java
- Joule : basado en flujo de datos, se comunica mediante el paso de mensajes
- Joyce : enseñanza concurrente, basada en Pascal concurrente con características de CSP de Per Brinch Hansen
- LabVIEW : gráficos, 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 Amstrad de BASIC contiene comandos EVERY y DESPUÉS para subrutinas concurrentes
- MultiLisp : variante de esquema ampliada para admitir el paralelismo
- Modula-2 : para programación de sistemas, de N. Wirth como sucesor de Pascal con soporte nativo para corrutinas
- Modula-3 : miembro moderno de la familia Algol con amplio soporte para subprocesos, mutex y variables de condición.
- Newsqueak —para investigación, con canales como valores de primer nivel; predecesor de Alef
- occam : fuertemente influenciado por la comunicación de procesos secuenciales (CSP)
- Orco : muy concurrente, no determinista, basado en el álgebra de Kleene
- Oz-Mozart : multiparadigma, admite simultaneidad de estado compartido y transmisión de mensajes, y futuros
- ParaSail : orientado a objetos, paralelo, sin punteros, condiciones de carrera
- Pict : esencialmente una implementación ejecutable del cálculo π de Milner
- Raku incluye clases para hilos, promesas y canales de forma predeterminada [15]
- Python : utiliza paralelismo basado en subprocesos y paralelismo basado en procesos [16]
- Reia : utiliza el paso de mensajes asincrónicos entre objetos que no comparten nada
- Rojo/Sistema —para programación del sistema, basado en Rebol
- Rust : para la programación de sistemas, utilizando el paso de mensajes con semántica de movimiento, memoria inmutable compartida y memoria mutable compartida. [17]
- Scala : propósito general, diseñado para expresar patrones de programación comunes de una manera concisa, elegante y con seguridad de escritura.
- SequenceL : funcional de propósito general, los 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 el rendimiento en hardware multinúcleo y demostrablemente libre de condiciones de carrera.
- SR —para investigación
- SuperPascal : concurrente, para enseñanza, basado en Concurrent Pascal y Joyce por Per Brinch Hansen
- Swift : soporte integrado para escribir código asincrónico y paralelo de forma estructurada [18]
- Unicon : para investigación
- TNSDL : para desarrollar intercambios de telecomunicaciones, utiliza el paso de mensajes asíncrono.
- Lenguaje de descripción de hardware VHSIC ( VHDL ): IEEE STD-1076
- XC: subconjunto extendido de simultaneidad 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, en niveles aproximadamente comparables con la lista anterior.
Ver también
Notas
- ^ Esto descarta el paralelismo interno de un núcleo de procesador, como canalización o instrucciones vectorizadas. Una máquina de un núcleo y un procesador puede ser capaz de establecer cierto paralelismo, como por ejemplo con un coprocesador , pero el procesador por sí solo no lo es.
Referencias
- ^ Conceptos de sistemas operativos, novena edición, Abraham Silberschatz. "Capítulo 4: Hilos"
- ^ Hansen, Por Brinch, ed. (2002). El origen de la programación concurrente. doi :10.1007/978-1-4757-3472-0. ISBN 978-1-4419-2986-0. S2CID 44909506.
- ^ ab Pike, Rob (11 de enero de 2012). "La concurrencia no es paralelismo". Conferencia de Waza , 11 de enero de 2012. Obtenido de http://talks.golang.org/2012/waza.slide (diapositivas) y http://vimeo.com/49718712 (vídeo).
- ^ "Paralelismo versus concurrencia". Wiki Haskell .
- ^ Schneider, Fred B. (6 de mayo de 1997). Sobre programación concurrente . Saltador. ISBN 9780387949420.
- ^ ab Ben-Ari, Mordejai (2006). Principios de programación concurrente y distribuida (2ª ed.). Addison-Wesley. ISBN 978-0-321-31283-9.
- ^ Lamport, Leslie (1 de septiembre de 1979). "Cómo hacer una computadora multiprocesador que ejecute correctamente programas multiproceso". Transacciones IEEE en computadoras . C-28 (9): 690–691. doi :10.1109/TC.1979.1675439. S2CID 5679366.
- ^ "Premio PODC al artículo influyente: 2002", Simposio ACM sobre principios de informática distribuida , consultado el 24 de agosto de 2009
- ^ Armstrong, Joe (2003). "Realizar sistemas distribuidos confiables ante la presencia de errores de software" (PDF) .
- ^ https://en.cppreference.com/w/cpp/header/thread
- ^ https://en.cppreference.com/w/cpp/header/coroutine
- ^ Marlow, Simon (2013) Programación paralela y concurrente en Haskell: técnicas para programación multinúcleo y multiproceso ISBN 9781449335946
- ^ https://juliacon.talkfunnel.com/2015/21-concurrent-and-parallel-programming-in-julia Programación concurrente y paralela en Julia
- ^ "Simultaneidad". docs.perl6.org . Consultado el 24 de diciembre de 2017 .
- ^ Documentación » Biblioteca estándar de Python » Ejecución concurrente
- ^ Blum, Ben (2012). "Estado mutable compartido Typesafe" . Consultado el 14 de noviembre de 2012 .
- ^ "Simultaneidad". 2022 . Consultado el 15 de diciembre de 2022 .
Fuentes
- Patterson, David A.; Hennessy, John L. (2013). Organización y diseño de computadoras: la interfaz hardware/software . La serie Morgan Kaufmann sobre arquitectura y diseño de computadoras (5 ed.). Morgan Kaufman. ISBN 978-0-12407886-4.
Otras lecturas
- Dijkstra, EW (1965). "Solución de un problema en el control de programación concurrente". Comunicaciones de la ACM . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID 19357737.
- Herlihy, Maurice (2008) [2008]. El arte de la programación multiprocesador . Morgan Kaufman. ISBN 978-0123705914.
- Downey, Allen B. (2005) [2005]. El librito de los semáforos (PDF) . Prensa de té verde. ISBN 978-1-4414-1868-5. Archivado desde el original (PDF) el 4 de marzo de 2016 . Consultado el 21 de noviembre de 2009 .
- Filman, Robert E.; Daniel P. Friedman (1984). Computación coordinada: herramientas y técnicas para software distribuido. Nueva York: McGraw-Hill. pag. 370.ISBN 978-0-07-022439-1.
- Leppäjärvi, Jouni (2008). Un estudio pragmático y de orientación histórica sobre la universalidad de las primitivas de sincronización (PDF) . Universidad de Oulu.
- Taubenfeld, Gadi (2006). Algoritmos de sincronización y programación concurrente. Pearson/Prentice Hall. pag. 433.ISBN 978-0-13-197259-9.
enlaces externos
- Medios relacionados con la programación concurrente en Wikimedia Commons
- Biblioteca virtual de sistemas concurrentes