Concurrencia (informática)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de julio de 2022; las comprobaciones requieren 2 ediciones .

En informática , el paralelismo es una propiedad de los sistemas en los que varios cálculos se realizan simultáneamente y, al hacerlo, posiblemente interactúen entre sí. Los cálculos pueden ejecutarse en múltiples núcleos en el mismo chip con subprocesos de tiempo compartido preventivo en el mismo procesador, o ejecutarse en procesadores separados físicamente . Se han desarrollado varios modelos matemáticos para realizar cálculos paralelos, incluidas las redes de Petri , el cálculo de procesos , los modelos de cálculo de acceso aleatorio paralelo y los modelos de actores .

Nota  : en la literatura en idioma ruso, los términos "paralelismo" y "competitividad" a menudo se confunden. . Ambas cosas los términos significan simultaneidad de procesos, pero el primero es a nivel físico (ejecución paralela de varios procesos, con el único objetivo de aumentar la velocidad de ejecución mediante el uso de soporte de hardware adecuado), y el segundo uno está en el nivel lógico ( paradigma de diseño de sistemas que identifica los procesos como independientes, lo que , entre otras cosas, permite que se ejecuten físicamente en paralelo, pero tiene como objetivo principal simplificar la escritura de programas multiproceso y aumentar su estabilidad).

Problemas

Dado que los cálculos en sistemas paralelos interactúan entre sí, la cantidad de rutas de ejecución posibles puede ser extremadamente grande y el resultado resultante puede volverse no determinista (indeterminado). El uso simultáneo de recursos compartidos puede ser una fuente de no determinismo, lo que lleva a problemas como estancamiento o escasez de recursos. [una]

La construcción de sistemas paralelos requiere encontrar métodos confiables para coordinar procesos en ejecución, comunicarse, asignar memoria y programar para minimizar el tiempo de respuesta y aumentar el rendimiento.

Teoría

La teoría de la computación paralela es un área activa de investigación en informática teórica . Una de las primeras propuestas en esta dirección fue el trabajo seminal de Carl Adam Petri sobre las redes de Petri a principios de la década de 1960. En los años siguientes, se desarrolló una amplia gama de formalismos para modelar y describir sistemas paralelos.

Modelos

Ya se ha desarrollado una gran cantidad de métodos formales para modelar y comprender el funcionamiento de sistemas paralelos, entre ellos: [2]

Algunos de estos modelos de concurrencia son principalmente para descripciones de especificaciones e inferencias, mientras que otros se pueden usar a lo largo del ciclo de desarrollo, incluido el diseño, la implementación, la prueba de resultados, las pruebas y la simulación de sistemas paralelos.

La proliferación de diferentes modelos de concurrencia ha llevado a algunos investigadores a desarrollar formas de combinar estos modelos teóricos. Por ejemplo, Lee y Sangiovanni-Vincentelli han demostrado que el llamado modelo de "señales etiquetadas" se puede utilizar para proporcionar un marco común para describir la semántica denotacional de varios modelos de concurrencia, [4] y Nielsen, Sassoon y Winskle han demostrado que la teoría de categorías se puede utilizar para proporcionar una comprensión común de los diversos modelos. [5]

El teorema de representación de concurrencia del modelo de actor proporciona una forma bastante general de describir sistemas concurrentes que son cerrados en el sentido de que no reciben mensajes del exterior. Otros métodos para describir la concurrencia, como el cálculo de procesos , se pueden describir en términos del modelo de actor mediante el protocolo de compromiso de dos fases. [6] La notación matemática utilizada para describir un sistema cerrado S proporciona una mejor aproximación si se construye a partir de un comportamiento inicial, denotado por ⊥ S , utilizando una progresión S de función de comportamiento de aproximación . [7] Entonces la notación para S se construye de la siguiente manera:

Denotar S ≡ ⊔ i∈ω progresión S i (⊥ S )

Por lo tanto, S puede expresarse matemáticamente en términos de todos sus comportamientos posibles.

Lógica

Para proporcionar un razonamiento lógico sobre los sistemas paralelos, se pueden utilizar varios tipos de lógicas temporales [8] . Algunas de ellas, como la lógica temporal lineal o la lógica de árbol computacional, permiten realizar afirmaciones sobre la secuencia de estados por los que puede pasar un sistema paralelo. Otros, como la lógica de acción de árbol computacional, la lógica de Hennessy-Milner o la lógica de acción temporal de Lamport, construyen sus declaraciones a partir de una secuencia de acciones (cambios de estado). El uso principal de estas lógicas es escribir especificaciones para sistemas paralelos. [una]

Practica

En esta sección, usaremos dos nociones de paralelismo que son comunes en la literatura inglesa, ya que hablaremos de compararlas entre sí. El término Concurrencia se traducirá como "simultaneidad", y el término Paralelismo se traducirá como "paralelismo".

La programación simultánea incluye lenguajes de programación y algoritmos utilizados para implementar sistemas simultáneos. La programación simultánea generalmente se considera más general que la programación paralela porque puede involucrar patrones de comunicación e interacción dinámicos arbitrarios, mientras que los sistemas paralelos a menudo implementan patrones de comunicación predefinidos y bien estructurados. Los principales objetivos de la programación concurrente son la corrección , la eficiencia y la estabilidad . Los sistemas concurrentes, como los sistemas operativos y los sistemas de administración de bases de datos, están diseñados principalmente para operar en condiciones inciertas, incluida la recuperación automática después de una falla, no deben dejar de funcionar inesperadamente. Algunos sistemas concurrentes operan en una forma de simultaneidad transparente, en la que las entidades computacionales concurrentes pueden competir por el uso del mismo recurso, pero la esencia de esta competencia está oculta para el programador.

Debido a que los sistemas concurrentes comparten recursos, normalmente requieren algún tipo de árbitro integrado en su implementación (a menudo el hardware subyacente) para controlar el acceso a esos recursos. El uso de árbitros crea la posibilidad de incertidumbre en los cálculos simultáneos, lo cual es de gran importancia para la práctica, incluso para garantizar la corrección y la eficiencia. Por ejemplo, el arbitraje no descarta el indeterminismo ilimitado, que está asociado con el problema de verificación del modelo , que es la causa de la naturaleza explosiva del espacio de estados y puede incluso conducir a la formación de un modelo con un número infinito de estados.

Algunos modelos de programación concurrente incluyen la creación de coprocesos y simultaneidad determinista . En estos modelos, los subprocesos de control de procesos otorgan explícitamente sus intervalos de tiempo al sistema o a otro proceso.

Véase también

Notas

  1. ↑ 1 2 Cleaveland, Rance; Scott Smolka. Direcciones estratégicas en la investigación de concurrencia  // Encuestas informáticas de  ACM : diario. - 1996. - Diciembre ( vol. 28 , no. 4 ). — Pág. 607 . -doi : 10.1145/ 242223.242252 .
  2. ↑ Filman, Robert; Daniel Friedman. Computación Coordinada - Herramientas y Técnicas para  Software Distribuido . - Educación McGraw-Hill , 1984. - ISBN 0-07-022439-0 . Copia archivada (enlace no disponible) . Consultado el 5 de octubre de 2011. Archivado desde el original el 16 de mayo de 2007. 
  3. ↑ Keller, Jorge; Christoph Kessler, Jesper Träff. Programación PRAM Práctica  (neopr.) . — John Wiley e Hijos , 2001.
  4. ↑ Lee, Eduardo; Alberto Sangiovanni-Vincentelli. Un marco para comparar modelos de computación  // Transacciones IEEE en  CAD : diario. - 1998. - Diciembre ( vol. 17 , no. 12 ). - P. 1217-1229 . -doi : 10.1109/ 43.736561 .
  5. ↑ Mogens Nielsen; Vladimiro Sassone y Glynn Winskel (1993). "Relaciones entre modelos de concurrencia" . Escuela/Simposio REX . Archivado desde el original el 26 de febrero de 2009 . Consultado el 5 de octubre de 2011 . Parámetro obsoleto utilizado |deadlink=( ayuda )
  6. ↑ Federico Knabe. Un protocolo distribuido para comunicación basada en canales con Choice PARLE 1992.
  7. ↑ Guillermo Clinger. Fundamentos de la semántica  actoral (neopr.) . - MIT, 1981. - Junio ​​( vol. Tesis Doctoral en Matemáticas ).
  8. ↑ Roscoe, Colin. Propiedades modales y temporales de los  procesos . - Springer, 2001. - ISBN 0-387-98717-7 .

Enlaces

  Ir al elemento de Wikidata  diccionarios y enciclopedias