stringtranslate.com

Concurrencia (informática)

Los "filósofos del comedor" , un problema clásico que involucra concurrencia y recursos compartidos

En informática , la concurrencia es la capacidad de diferentes partes o unidades de un programa , algoritmo o problema de ejecutarse fuera de orden 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 capacidad de descomposición de un programa, algoritmo o problema en componentes o unidades de computación independientes del orden o parcialmente ordenados. [1]

Paralelismo vs concurrencia

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 , cada uno de los cuales realiza una tarea de forma independiente. Por otro lado, la concurrencia permite que un programa se ocupe de múltiples tareas incluso en un solo núcleo de CPU; el núcleo cambia entre tareas (es decir, subprocesos ) sin completar necesariamente cada una de ellas. Un programa puede tener ambas, ninguna o una combinación de características de paralelismo y concurrencia. [2]

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 .

Asuntos

Debido a que los cálculos en un sistema concurrente pueden interactuar entre sí mientras se ejecutan, la cantidad de posibles rutas de ejecución en el sistema puede ser extremadamente grande y el resultado puede ser indeterminado . El uso concurrente de recursos compartidos puede ser una fuente de indeterminación que genere problemas como bloqueos y escasez de recursos . [3]

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 . [4]

Teoría

La teoría de la concurrencia ha sido un campo de investigación activo en la informática teórica . Una de las primeras propuestas fue el trabajo seminal de Carl Adam Petri sobre las redes de Petri a principios de los años 1960. 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: [5]

Algunos de estos modelos de concurrencia están pensados ​​principalmente para respaldar el razonamiento y la especificación, mientras que otros pueden utilizarse durante todo el ciclo de desarrollo, incluidos 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 un modelo denominado "tagged-signal" para proporcionar un marco común para definir la semántica denotacional de una variedad de diferentes modelos de concurrencia, [7] 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. [8]

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, los cálculos de procesos se pueden modelar en el modelo de actor utilizando un protocolo de confirmación de dos fases . [9] ) 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 utilizando una progresión de función de aproximación de comportamiento S para construir una denotación (que significa ) para S de la siguiente manera: [10]

Denotamos S ≡ ⊔ i∈ω progresión S i (⊥ 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 [11] 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 realizar afirmaciones sobre las secuencias de estados por las que puede pasar un sistema concurrente. Otras, como la lógica de árbol de cálculo de acciones, 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 principal aplicación de estas lógicas es la redacción de especificaciones para sistemas concurrentes. [3]

Práctica

La programación concurrente abarca lenguajes de programación y algoritmos utilizados para implementar sistemas concurrentes. La programación concurrente suele considerarse [ ¿por quién? ] como 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? ] tienen un patrón de comunicaciones predefinido y bien estructurado. Los objetivos básicos de la programación concurrente incluyen la corrección , el rendimiento y la robustez . 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 funcionar indefinidamente, incluida la recuperación automática de fallas, y no terminar inesperadamente (ver Control de concurrencia ). Algunos [ ejemplo necesario ] sistemas concurrentes implementan una forma de concurrencia transparente, en la que las entidades computacionales concurrentes pueden competir y compartir un solo recurso, pero las complejidades de esta competencia y compartición están protegidas del programador.

Debido a que utilizan recursos compartidos, los sistemas concurrentes en general [ ¿según quién? ] requieren la inclusión de algún tipo de [ ejemplo necesario ] á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 causa 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 porciones de tiempo, ya sea al sistema o a otro proceso.

Véase también

Referencias

  1. ^ Lamport, Leslie (julio de 1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" (PDF) . Comunicaciones de la ACM . 21 (7): 558–565. doi :10.1145/359545.359563. S2CID  215822405 . Consultado el 4 de febrero de 2016 .
  2. ^ Programación paralela y concurrente en Haskell . O'Reilly Media. 2013. ISBN 9781449335922.
  3. ^ ab Cleaveland, Rance; Scott Smolka (diciembre de 1996). "Direcciones estratégicas en la investigación de concurrencia". Encuestas de computación de ACM . 28 (4): 607. doi : 10.1145/242223.242252 . S2CID  : 13264261.
  4. ^ Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (agosto de 2010). Programación paralela con Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3.
  5. ^ Filman, Robert; Daniel Friedman (1984). Computación coordinada: herramientas y técnicas para software distribuido . McGraw-Hill. ISBN 978-0-07-022439-1.
  6. ^ Keller, Jörg; Christoph Keßler; Jesper Traff (2001). Programación práctica de PRAM . John Wiley e hijos.
  7. ^ Lee, Edward; Alberto Sangiovanni-Vincentelli (diciembre de 1998). "Un marco para comparar modelos de computación" (PDF) . IEEE Transactions on CAD . 17 (12): 1217–1229. doi :10.1109/43.736561.
  8. ^ Mogens Nielsen; Vladimiro Sassone; Glynn Winskel (1993). "Relaciones entre modelos de concurrencia". Escuela/Simposio REX .
  9. ^ Frederick Knabe. Un protocolo distribuido para comunicación basada en canales con elección PARLE 1992.
  10. ^ William Clinger (junio de 1981). "Fundamentos de la semántica de actores". Tesis doctoral en matemáticas. MIT. hdl :1721.1/6935. {{cite journal}}: Requiere citar revista |journal=( ayuda )
  11. ^ Roscoe, Colin (2001). Propiedades modales y temporales de los procesos . Springer. ISBN 978-0-387-98717-0.

Lectura adicional

Enlaces externos