En informática , la concurrencia es la capacidad de diferentes partes o unidades de un programa , algoritmo o problema de ejecutarse desordenadamente o en orden parcial , sin afectar el resultado. Esto permite la ejecución paralela de las unidades concurrentes, lo que puede mejorar significativamente la velocidad general de ejecución en sistemas multiprocesador y multinúcleo . 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]
Según Rob Pike , la concurrencia es la composición de cálculos que se ejecutan de forma independiente, [2] y la concurrencia no es paralelismo: la concurrencia se trata de lidiar con muchas cosas a la vez, pero el paralelismo se trata de hacer muchas cosas a la vez. La concurrencia tiene que ver con la estructura, el paralelismo tiene que ver con la ejecución, la concurrencia proporciona una manera de estructurar una solución para resolver un problema que puede (pero no necesariamente) ser paralelizable. [3]
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 .
Como señala Leslie Lamport (2015): "Si bien la ejecución concurrente de programas se había considerado durante años, la informática de la concurrencia comenzó con el artículo fundamental de Edsger Dijkstra de 1965 que introdujo el problema de la exclusión mutua ... Las décadas siguientes han visto un enorme crecimiento del interés en la concurrencia, particularmente en sistemas distribuidos . Mirando hacia atrás en los orígenes del campo, lo que destaca es el papel fundamental desempeñado por Edsger Dijkstra". [4]
Debido a que los cálculos en un sistema concurrente pueden interactuar entre sí mientras se ejecutan, la cantidad de rutas de ejecución posibles 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 lleve a problemas como estancamientos y escasez de recursos . [5]
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 . [6]
La teoría de la concurrencia ha sido un campo activo de investigación en 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 los años sesenta. En los años posteriores, se ha desarrollado una amplia variedad de formalismos para modelar y razonar sobre la concurrencia.
Se han desarrollado una serie de formalismos para modelar y comprender sistemas concurrentes, que incluyen: [7]
Algunos de estos modelos de concurrencia están destinados principalmente a respaldar el razonamiento y la especificación, mientras que otros pueden usarse durante 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 ellos se basan en el paso de mensajes , mientras que otros tienen diferentes mecanismos de concurrencia.
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 se puede utilizar el llamado modelo de "señal etiquetada" para proporcionar un marco común para definir la semántica denotacional de una variedad de modelos diferentes de concurrencia, [9] 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. [10]
El teorema de representación de concurrencia en el modelo de actor proporciona una forma bastante general de representar sistemas concurrentes que son cerrados en el sentido de que no reciben comunicaciones del exterior. (Otros sistemas de concurrencia, por ejemplo, cálculos de procesos, se pueden modelar en el modelo de actor usando un protocolo de confirmación de dos fases . [11] ) La denotación matemática denotada por un sistema cerrado S se construye con 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 (es decir, ) para S de la siguiente manera: [12]
De esta manera, S puede caracterizarse matemáticamente en términos de todos sus comportamientos posibles.
Se pueden utilizar varios tipos de lógica temporal [13] para ayudar a razonar sobre sistemas concurrentes. Algunas de estas lógicas, como la lógica temporal lineal y la lógica de á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 del árbol computacional de acción, la lógica de Hennessy-Milner y la lógica temporal de acciones de Lamport , construyen sus afirmaciones a partir de secuencias de acciones (cambios de estado). La aplicación principal de estas lógicas es escribir especificaciones para sistemas concurrentes. [5]
La programación concurrente abarca lenguajes de programación y algoritmos utilizados para implementar sistemas concurrentes. Generalmente se considera la programación concurrente [ ¿por quién? ] es más general que la programación paralela porque puede implicar patrones arbitrarios y dinámicos de comunicación e interacción, mientras que los sistemas paralelos generalmente [ ¿ según quién? ] tener un patrón de comunicación predefinido y bien estructurado. Los objetivos básicos de la programación concurrente incluyen corrección , rendimiento y solidez . Los sistemas concurrentes, como los sistemas operativos y los sistemas de gestión de bases de datos , generalmente están diseñados [ ¿ por quién? ] para operar indefinidamente, incluida la recuperación automática en caso de falla, y no finalizar inesperadamente (consulte Control de concurrencia ). Algunos sistemas concurrentes [ ejemplo necesario ] implementan una forma de concurrencia transparente, en la que entidades computacionales concurrentes pueden competir y compartir un único recurso, pero las complejidades de esta competencia y el intercambio están protegidas del programador.
Porque utilizan recursos compartidos, sistemas concurrentes en general [ ¿ según quién? ] requieren la inclusión de algún [ ejemplo necesario ] 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 de modelos porque provoca 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 sus intervalos de tiempo, ya sea al sistema o a otro proceso.
{{cite journal}}: Citar diario requiere |journal=( ayuda )