Sistemas Concurrentes:Sistemas Concurrentes:programación concurrenteprogramación concurrente

I.T. Informática de SistemasCurso 2002-2003

SistemasConcurrentes

Cómo implementar la concurrencia

• El propio hardware multiprocesadores (máqs. de memoria

compartida) sistemas distribuidos

• Multiprogramación No hay paralelismo. Los procesos se reparten

el procesador: entrelazado (interleaving) ¿Quién planifica los procesos?

el sistema operativoel propio ejecutable (gracias al compilador) ->

runtime scheduler (RTSS)

SistemasConcurrentes

Planificadores

• Nuestro programa se ejecutará de manera diferente según la política de planificación empleada.

• Algunos programas funcionarán adecuadamente con un planificador, pero con otros pueden fracasar.

SistemasConcurrentes

“Granularidad” del paralelismo

• ¿cuáles son las acciones que se pueden ejecutar en paralelo? instrucciones de máquina sentencias de un lenguaje de programación objetos concurrentes dentro de un programa programas ejecutables completos

• Grano fino --> grano grueso• Cada ‘grano’ propicia unas herramientas y

técnicas de programación diferentes

La abstracción de la programación concurrente

SistemasConcurrentes

Abstracción 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. serán responsables de ejecutar nuestros procesos como consideren más 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 programación secuencial define un orden total de las instrucciones

• Un programa concurrente define un orden parcial de ejecución

• 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, según el orden de ejecución de los procesos.

SistemasConcurrentes

No determinismo

• El no determinismo es una propiedad inherente a la concurrencia.

• Por culpa del no determinismo, es más difícil analizar y verificar un algoritmo concurrente.

• Ojo, que existan varias posibilidades de salida NO significa necesariamente que un programa concurrente sea incorrecto.

SistemasConcurrentes

Acciones atómicas

• Por culpa del no determinismo, la ejecución del programa puede ser incorrecta e inesperada.

• Surge la conveniencia de imponer que ciertas piezas de código se ejecuten de forma atómica.

cobegin x := 2; x := 65536;coend;

¡¡el resultado podría ser x=65538!!

SistemasConcurrentes

Acciones atómicas (2)

• En el análisis de algoritmos concurrentes, se permite declarar que una sentencia se ejecuta de forma atómica.

cobegin <x:=x+1> <x:=x+2> coend

• Así se facilita el análisis y verificación de estos algoritmos.

• No nos incumbe (por ahora) cómo se consigue la ejecución atómica.

SistemasConcurrentes

Historias / secuencias de ejecución

• Una historia o la secuencia de ejecución es una secuencia temporal de acciones que ocurren durante la ejecución de un programa.

• Un programa concurrente puede tener múltiples secuencias de ejecución (y todas ellas pueden ser correctas) a -> b -> c c -> a -> b ...

SistemasConcurrentes

Verificación de programas

• ¿Cuándo 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 múltiples secuencias de ejecución.

• Cuando se dice que un pr.c. es correcto, se entiende que se refiere a todas sus posibles secuencias de ejecución.

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. exclusión mutua, no interbloqueo

• Propiedades de progreso (liveness) una propiedad que se cumplirá con toda

seguridad en algún momento de la ejecución ejs. propiedades de justicia (fairness),

evitación de inanición

SistemasConcurrentes

Ejemplos de justicia (fairness)

• Justicia débil. Si un proceso realiza continuamente una petición, terminará siendo atendido.

• Justicia fuerte. Si un proceso realiza una petición con frecuencia infinita, terminará siendo atendido.

• Espera lineal. Si un proceso realiza una petición, ningún otro proceso puede ser atendido dos veces antes que él.

• Espera FIFO. Si un proceso realiza una petición, será atendido antes que cualquier otra solicitud posterior.

SistemasConcurrentes

Análisis de algoritmos concurrentes

• Usar invariantes y lógica proposicional• Usar métodos inductivos• Usar historias de ejecución (a->b)• Usar predicados posicionales: at(I), in(I),

after(I)• Usar lógica temporal• ...