Concurrencia (informática)

En informática, 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.

Tenga en cuenta que en informática, el paralelismo y la concurrencia son dos cosas diferentes: un programa paralelo utiliza múltiples núcleos de CPU y cada núcleo realiza una tarea de forma independiente. Por otro lado, la concurrencia permite que un programa se ocupe de múltiples tareas incluso en un único núcleo de CPU; el núcleo cambia entre tareas (es decir, subprocesos) sin completar necesariamente cada una. Un programa puede tener ambas características, ninguna o una combinación de paralelismo y concurrencia.

Se han desarrollado varios modelos matemáticos para el cálculo concurrente general, incluidas redes de Petri, cálculos de procesos, el modelo de máquina de acceso aleatorio paralelo, el modelo de actor y el lenguaje de coordinación Reo.

Problemas

Debido a que los cálculos en un sistema concurrente pueden interactuar entre sí mientras se ejecutan, el número 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 genere problemas como estancamientos y escasez de recursos.

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.

Teoría

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 los años sesenta. En los años posteriores, se ha desarrollado una amplia variedad de formalismos para modelar y razonar sobre la concurrencia.

Modelos

Se han desarrollado varios formalismos para modelar y comprender sistemas concurrentes, entre ellos:

• La máquina de acceso al azar paralelo
• El modelo actor
• Modelos de brida computacional como el modelo paralelo sincrónico (BSP)
• Redes Petri
• Calculi de proceso
  • Cálculo de sistemas de comunicación (CCS)
  • Modelo de comunicación de procesos secuenciales
  • π-calculus
• Espacios de tuple, por ejemplo, Linda
• Programación simple orientada hacia objetos (SCOOP)
• Reo Coordination Language
• Trace monoids

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 un modelo llamado "tagged-signal" puede utilizarse para proporcionar un marco común para definir la semántica denotacional de una variedad de modelos diferentes de concurrencia, mientras que Nielsen, Sassone y Winskel han demostrado que la teoría de la categoría puede ser utilizada para proporcionar una comprensión unificada similar de diferentes modelos.

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, cálculos de procesos, se pueden modelar en el modelo de actor utilizando un protocolo de confirmación de dos fases). La denotación matemática denotada por un sistema cerrado S se construye cada vez mejor. aproximaciones a partir de un comportamiento inicial llamado ⊥_S usando una función de aproximación de comportamiento progresión_S para construir una denotación (significado) para S de la siguiente manera:

Denote_S ≡_i progresión_Sⁱ(⊥_S)

De esta manera, S puede caracterizarse matemáticamente en términos de todos sus posibles comportamientos.

Lógica

Se pueden utilizar varios tipos de lógica temporal 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 de á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.

Práctica

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 comunicación predefinido y bien estructurado. Los objetivos básicos de la programación concurrente incluyen corrección, rendimiento y robustez. Los sistemas concurrentes, como los sistemas operativos y los sistemas de administración de bases de datos, generalmente están diseñados para funcionar indefinidamente, incluida la recuperación automática en caso de falla, y no finalizar inesperadamente (consulte Control de concurrencia). Algunos sistemas concurrentes 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 ocultas al programador.

Debido a que utilizan 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 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.