Sistemas Concurrentes: programacin concurrente
I.T. Informtica de Sistemas Curso 2002-2003
Cmo implementar la concurrencia
El propio hardware
multiprocesadores (mqs. de memoria compartida) sistemas distribuidos
Multiprogramacin
No hay paralelismo. Los procesos se reparten el procesador: entrelazado (interleaving) Quin planifica los procesos?
el sistema operativo el propio ejecutable (gracias al compilador) -> runtime
scheduler (RTSS)
SistemasConcurrentes
Planificadores
Nuestro programa se ejecutar de manera diferente segn la poltica de planificacin empleada. Algunos programas funcionarn adecuadamente con un planificador, pero con otros pueden fracasar.
SistemasConcurrentes
Granularidad del paralelismo
cules son las acciones que se pueden ejecutar en paralelo?
instrucciones de mquina sentencias de un lenguaje de programacin objetos concurrentes dentro de un programa programas ejecutables completos
Grano fino --> grano grueso Cada grano propicia unas herramientas y tcnicas de programacin diferentes
SistemasConcurrentes
La abstraccin de la programacin concurrente
Abstraccin de la concurrencia
Nuestro programa expresa acciones concurrentes (procesos o hilos), pero stas no tienen por qu ejecutarse en paralelo. Cada proceso concurrente se ejecuta sobre un procesador virtual. El compilador y el s.o. sern responsables de ejecutar nuestros procesos como consideren ms oportuno.
SistemasConcurrentes
Procesadores virtuales
Supondremos que nuestro programa concurrente consiste en un conjunto de procesos secuenciales que se ejecutan en paralelo, cada uno de ellos corriendo sobre un procesador virtual. Nos deben dar igual las velocidades relativas de los procesadores virtuales.
SistemasConcurrentes
Orden parcial -> no determinismo
La programacin secuencial define un orden total de las instrucciones Un programa concurrente define un orden parcial de ejecucin El orden parcial implica el no determinismo de los programas concurrentes
SistemasConcurrentes
No determinismo
Un programa secuencial es determinista:
si se le presenta el mismo conjunto de datos de entrada, siempre producir la misma salida.
Un programa concurrente es no determinista:
un mismo conjunto de datos de entrada puede producir diferentes datos de salida, segn el orden de ejecucin de los procesos.
SistemasConcurrentes
No determinismo
El no determinismo es una propiedad inherente a la concurrencia. Por culpa del no determinismo, es ms difcil analizar y verificar un algoritmo concurrente. Ojo, que existan varias posibilidades de salida NO significa necesariamente que un programa concurrente sea incorrecto.
SistemasConcurrentes
Acciones atmicas
Por culpa del no determinismo, la ejecucin del programa puede ser incorrecta e inesperada.
cobegin x := 2; x := 65536; coend;
el resultado podra ser x=65538!!
Surge la conveniencia de imponer que ciertas piezas de cdigo se ejecuten de forma atmica.
SistemasConcurrentes
Acciones atmicas (2)
En el anlisis de algoritmos concurrentes, se permite declarar que una sentencia se ejecuta de forma atmica.
cobegin <x:=x+1> <x:=x+2> coend
As se facilita el anlisis y verificacin de estos algoritmos. No nos incumbe (por ahora) cmo se consigue la ejecucin atmica.
SistemasConcurrentes
Historias / secuencias de ejecucin
Una historia o la secuencia de ejecucin es una secuencia temporal de acciones que ocurren durante la ejecucin de un programa. Un programa concurrente puede tener mltiples secuencias de ejecucin (y todas ellas pueden ser correctas)
a -> b -> c c -> a -> b ...
SistemasConcurrentes
Verificacin de programas
Cundo un programa (secuencial) se considera correcto?
Parcialmente correcto. Dadas unas precondiciones correctas, si el programa termina se cumplen las postcondiciones previstas. Totalmente correcto. Dadas unas precondiciones correctas, el programa termina y se cumplen las postcondiciones.
SistemasConcurrentes
Peculiaridades de los programas concurrentes
Los programas concurrentes pueden no terminar nunca y al mismo tiempo ser correctos. Un pr.c. puede tener mltiples secuencias de ejecucin. Cuando se dice que un pr.c. es correcto, se entiende que se refiere a todas sus posibles secuencias de ejecucin.
SistemasConcurrentes
Seguridad y progreso (safety and liveness)
Dos tipos de propiedades tiles en los sistemas concurrentes Propiedades de seguridad (safety)
una propiedad que debe ser cierta siempre ejs. exclusin mutua, no interbloqueo
Propiedades de progreso (liveness)
una propiedad que se cumplir con toda seguridad en algn momento de la ejecucin ejs. propiedades de justicia (fairness), evitacin de inanicin
SistemasConcurrentes
Ejemplos de justicia (fairness)
Justicia dbil. Si un proceso realiza continuamente una peticin, terminar siendo atendido. Justicia fuerte. Si un proceso realiza una peticin con frecuencia infinita, terminar siendo atendido. Espera lineal. Si un proceso realiza una peticin, ningn otro proceso puede ser atendido dos veces antes que l. Espera FIFO. Si un proceso realiza una peticin, ser atendido antes que cualquier otra solicitud posterior.
SistemasConcurrentes
Anlisis de algoritmos concurrentes
Usar invariantes y lgica proposicional Usar mtodos inductivos Usar historias de ejecucin (a->b) Usar predicados posicionales: at(I), in(I), after(I) Usar lgica temporal ...
SistemasConcurrentes
