Apuntes Concurrente

PConcurrente.md

Programación Concurrente 2015

Apuntes de Programación Concurrente, Facultad de Informatica, UNLP. Promoción teorica 2015 - febrero.

Teoria 1

##Qué es la concurrencia?

Concurrencia es la capacidad de ejecutar múltiples actividades en paralelo o simultáneamente (o intercalando la ejecucion de distintos programas secuencias). Permite a distintos objetos actuar al mismo tiempo.

CONCURRENCIA: Concepto de software no restringido a una arquitectura particular de hardware ni a un número determinado de procesadores.

Un programa concurrente especifica dos o más procesos que cooperan para realizar una tarea. Cada proceso es un programa secuencial que ejecuta una secuencia de sentencias. Los procesos cooperan por comunicación: se comunican usando variables compartidas o pasaje de mensajes. Cuando se usan variables compartidas, un proceso escribe en una variable que es leída por otra. Cuando se usa pasaje de mensajes, un proceso envía un mensaje que es recibido por el otro.

Los sistemas operativos fueron los primeros ejemplos de programas concurrentes. Hay muchos ejemplo de programas concurrente como por ejemplo:

• Sistemas de ventanas en computadoras personales o workstations.
• Procesamiento de transacciones en sistemas de BD multiusuario.
• File servers en una red.
• Computacion cientifica que manipulan grandes arreglos de datos.

Los sistemas concurrentes icrementar la performance (ej: mejora la utilización de la CPU), mejorando los tiempos de respuesta de los sistemas de procesamiento de datos, a través de un enfoque diferente de la arquitectura física y lógica de las soluciones.

##Secuencialidad y concurrencia

Programa secuencial: es un solo flujo de control que ejecuta una instruccion y cuando esta finaliza ejecuta la siguiente. Totalmente ordenado. determinístico: para los mismos datos de entrada, ejecuta siempre la misma secuencia de instrucciones y obtiene la misma salida. La Programación Secuencial estructurada puede expresarse con 3 clases de instrucciones básicas: asignación, alternativa (decisión) e iteración (repetición con condición).

Los programas concurrentes pueden ser no-determinísticos: pueden dar distintos resultados al ejecutarse sobre los mismos datos de entrada.

Concurrencia "interleaved": Procesamiento simultáneo lógicamente. Ejecución intercalada en un único procesador "Seudo-paralelismo".
Concurrencia simultánea: Procesamiento simultáneo físicamente. Requiere un sistema multiprocesador o multicore. Paralelismo "full".

Medir el incremento de performance

El procesamiento paralelo lleva a los conceptos de speedup y eficiencia.

• Speedup:

Speedup = Tiempo Secuencial / Tiempo Paralelo 

• Eficiencia:

Eficiencia = Speedup / cantidad de procesadores 

Que es un proceso?

Un proceso es un programa secuencial. Comportamiento de los procesos:

• Cooperación: Los procesos se combinan para resolver una tarea común, para esto deben sicronizarse.
• Competencia: Los procesos compiten por el acceso a un recurso. Tipico en SO y redes, debido a recursos compartidos.
• Procesos independientes: relativamente raros y poco interesantes.

Clases de aplicaciones concurrentes

Hay 3 grandes clases (superpuestas) de aplicaciones:

• Sistemas multithread: Un sistema de software de "multithreading" maneja simultáneamente tareas independientes, asignando los procesadores de acuerdo a alguna política (ej, por tiempos). Ejemplo: Sistemas de ventanas en PCs o WS. Sistemas Operativos time-shared y multiprocesador. Sistemas de tiempo real (x ej, en plantas industriales o medicina).

• Sistemas de cómputo distribuido: Una red de comunicaciones vincula procesadores diferentes sobre los que se ejecutan procesos que se comunican esencialmente por mensajes. Cada componente del sistema distribuido puede hacer a su vez multithreading. Ejemplos: Servidores de archivos en una red. Sistemas de BD en bancos y aerolíneas (acceso a datos remotos). Servidores Web distribuidos (acceso a datos remotos).

• Sistemas de cómputo paralelo: arq. multiprocesador en la que se pueda distribuir la tarea global en tareas que puedan ejecutarse en distintos procesadores.Paralelismo de datos y paralelismo de procesos. Ejemplo: Cálculo cientifico. Gráficos, procesamiento de imagenes, problemas combinatorios, etc.

Comunicación y Sincronizacion

Comunicación:

La comunicación indica el modo en que se organiza y trasmiten datos entre tareas concurrentes. Esta organización requiere especificar protocolos para controlar el progreso y la corrección de la comunicación. Hay dos tipos de comunicacion:

• Memoria compartida: Los procesos intercambian información sobre la memoria compartida o actúan coordinadamente sobre datos residentes en ella. Lógicamente no pueden operar simultáneamente sobre la MC, lo que obliga a bloquear y liberar el acceso a la memoria (ej: semáforos).

• Pasaje de mensajes: Es necesario establecer un canal (lógico o físico) para transmitir información entre procesos. También el lenguaje debe proveer un protocolo adecuado. Para que la comunicación sea efectiva los procesos deben "saber" cuándo tienen mensajes para leer y cuando deben trasmitir mensajes.

Sincronización

Los procesos en un programa concurrente se comunican usando variables compartidas o mensajes. La comunicación provoca la necesidad de sincronización.
La sincronización es la información que tiene un proceso sobre el estado de otro proceso que es utilizada con el fin de coordinar tareas o acciones entre estos procesos. El objetivo de la sincronización es restringir las historias de un programa concurrente sólo a las permitidas.

Historia (o trace) de un programa concurrente: es una ejecución dada por un intercalado (interleaving) particular de acciones individuales de los procesos. Algunas historias de un programa son válidas y otras no, ya que se debe asegurar un orden temporal entre las acciones que ejecuntan los procesos.

Un programa concurrente con n procesos, donde c/u ejecuta m acciones atómicas tiene una cantidad de historias posibles dada por (n*m)! / (m!)^n.

En los programas concurrentes se dan dos formas de sincronización:

• Exclusión mutua: Consiste en asegurar que las secciones críticas de sentencias que acceden a objetos compartidos no se ejecuntan al mismo tiempo, En otras palabras, asegurar que sólo un proceso tenga acceso a un recurso compartido en un instante de tiempo.

Evita que dos o más procesos puedan encontrarse en la misma sección crítica al mismo tiempo.

• Sincronización por condición: asegura que un proceso se demora si es necesario hasta que sea verdadera una condición dada. En otras palabras, permite bloquear la ejecución de un proceso hasta que se cumpla una condición.

Ejemplo de los dos mecanismos de sincronización en un problema de utilización de un área de memoria compartida (buffer limitado con productores y consumidores).

Conceptos relacionados con la Prog Concurrente

Propiedad fairness

Es una propiedad (de vida), la cual trata de garantizar que los procesos tengan chance de avanzar, sin importar lo que hagan los otros procesos.

Inanición

Es una situacion no deseable en los programas concurrentes que se da cunado un proceso no logra acceder a los recursos compartidos.

Deadlock

Dos (o más procesos) pueden entrar en deadlock, si por error de programación ambos se quedan esperando que el otro libere un recurso compartido. La ausencia de deadlock es una propiedad necesaria en los procesos concurrentes. Hay 4 propiedades necesarias y suficientes para que exista deadlock:

• Recursos reusables serialmente: Los procesos comparten recursos que pueden usar con Exclusión mutua.
• Adquisicion incremental: Los procesos mantienen los recursos que poseen mientras esperan adquirir recursos adicionales.
• No-preemtion: Una vez que los recursos son adquiridos por un proceso, los recursos no pueden quitarse de manera forzada sino que sólo son liberados voluntariamente.
• Espera cíclica: Existe una cadena cirucular (ciclo) de procesos tal que cada uno tiene un recurso que su sucesor en el ciclo está esperando adquirir.

Acción átomica

es una sentencia de ejecución que no tiene estado intermedios, es decir, que su ejecución tiene estados intermedios invisibles para otros procesos). Son implementadas por Hardware.

• Si una expresión e en un proceso no referencia una variable alterada por otro proceso, la evaluación será atómica, aunque requiera ejecutar varias acciones atómicas de grano fino.

• Si una asignación x = e en un proceso no referencia ninguna variable alterada por otro proceso, la ejecución de la asignación será atómica.

Una acción atómica en un proceso es elegible si es la próxima acción atómica en el procesos que será ejecutado. Cuando hay varios procesos, hay varias acciones atómicas elegibles. Una política de scheduling determina cuál será la próxima en ejecutarse.

Interferencia

un proceso toma/ejecuta una acción que invalida las suposiciones hechas por otro proceso.

Referencia crítica

se da en una expresión cuando referencia a una variable que es modificada por otro proceso. Asumamos que toda referencia crítica se da en variable simple leída y escrita atómicamente.

Teoria 2

Paradigmas y patrones de resolución de programas concurrentes

1. Paralelismo iterativo: un programa consta de un conjunto de procesos (posiblemente idénticos), cada uno de los cuales es un programa iterativo (tiene uno o mas loop). Estos cooperan para resolver una única tarea. ejemplo: calculo de matrices.
2. Paralelismo recursivo: el problema general se descompone en procesos recursivos que trabajan sobre partes del conjunto total de datos (Dividir y conquistar). ejemplo: sorting by merging, aproximacion de la integral de una función.
3. Productores y consumidores. (pipelines o workflows): proceso que se comunican. En general, los procesos se organizan en pipes a través de los cuales fluye la infomación.

Cada proceso en el pipe es un filtro que consume la salida de su proceso predecesor y produce una salida para el proceso siguiente.

4. Clientes y servidores: esquema dominante en las aplicaciones de procesamiento distribuido. Los servidores son procesos que esperan pedidos de servicios de múltiples clientes. Unos y otros pueden ejecutarse en procesadores diferentes. Comunicación bidireccional. Mecanismos de invocación variados (rendezvous y RPC x ej en MD, monitores x ej en MC).
5. Pares que interactúan. (interacting peers): los procesos (que forman parte de un programa distribuido) resuelven partes del problema (normalmente mediante código idéntico) e intercambian mensajes para avanzar en la tarea y completar el objetivo.

Clasificación del Hardware

Por la organizacion del espacio de direcciones

• Multiprocesadores de memoria compartida:

  • Interacción modificando datos en la memoria compartida.
  • (problemas de consistencia).

• Multiprocesadores de memoria distribuida:

  • Memoria local (no hay problemas de consistencia).
  • Interacción es sólo por pasaje de mensajes.

Por mecanismo de control

Se basa en la manera en que las instrucciones son ejecutadas sobre los datos, hay 4 clases:

1. SISD (Single Instruction Single Data)
2. SIMD (Single Instruction Multiple Data)
3. MISD (Multiple Instruction Single Data)
4. MIMD (Multiple Instruction Multiple Data)

Por la granularidad de los procesadores

Puede verse también como la relación entre cómputo y comunicación. Es importante el matching entre la arquitectura y la aplicación.

• De grano grueso: (coarse-grained) pocos procesadores muy poderosos. Puede usarse eficientemente cuando se tiene concurrencia limitada.
• De grano fino: (fine-grained) gran número de procesadores menos potentes. es efectiva para aplicaciones con alta concurrencia.
• De grano medio (medium-grained).

Relación de la granularidad con la sincronización: Combinar acciones atómicas de grano fino (fine-grained) en acciones (compuestas) de grano grueso (coarse grained) que den la exclusión mutua.

Una acción atómica de grano grueso (coarse grained) es como secuencia de acciones atómicas de grano fino (fine grained) que aparecen como indivisibles pero se logra utilizando mecanismo de sincronización.

Por la red de interconexión:

• Estáticas: Las redes estáticas constan de links punto a punto. Típicamente se usan para máquinas de pasaje de mensajes.

• Dinámicas:Las redes dinámicas están construidas usando switches y enlaces de comunicación. Normalmente para máquinas de Memoria compartida.

Propiedad de "A lo sumo una vez".

Una sentencia de asignación x = e satisface la propiedad de A lo sumo una vez si:

1. e contiene a lo sumo una referencia crítica y x no es referenciada por otro proceso, o
2. e no contiene referencias críticas, en cuyo caso x puede ser leída por otro proceso.

EFECTO: Si una sentencia de asignación cumple la propiedad ASV, entonces su ejecución parece atómica, pues la variable compartida será leída o escrita sólo una vez. Si una expresión o asignación no satisface ASV con frecuencia es necesario ejecutarla atómicamente.

Ejemplo:

• Sin refencias criticas: (ambas cumplen ASV)

int x=0, y=0;
co x=x+1 // y=y+1 oc;

• Con refencias criticas: En este caso y cumple con ASV porque no tiene ninguna referencia crítica, x cumple porque tiene una referencia critica pero no es leida por otro proceso.

int x=0, y=0;
co x=y+1 // y=y+1 oc;

• Con referencia criticas pero no cumple ASV: Ninguna de las 2 variables cumple con ASV

int x=0, y=0;
co x=y+1 // y=x+1 oc;

Seguridad y vida:

Una propiedad de seguridad asegura que el programa nunca entra en un estado malo, asegura un estado consistente (es decir uno en el que algunas variables tienen valores indeseables).Ej: ausencia de deadlock y ausencia de interferencia (exclusión mutua) entre procesos.
Una propiedad de vida asegura que el programa eventualmente entra en un estado bueno (es decir, uno en el cual todas las variables tiene valores deseables). Ej: terminación, asegurar que un pedido de servicio será atendido, que un mensaje llega a destino.

Prueba de propiedades

1. Testing o debugging: "tome el programa y vea qué sucede". No demuestra la ausencia de historias "malas".
2. Razonamiento operacional: análisis exhaustivo de casos.
3. Razonamiento asercional: análisis abstracto. para este analisis se usa la logica de predicados (logica proposicional).

Fairness y políticas de scheduling

Fairness Incondicional. Una política de scheduling es incondicionalmente fair si toda acción atómica incondicional que es elegible eventualmente es ejecutada.

Fairness Débil. Una política de scheduling es débilmente fair si es incondicionalmente fair y toda acción atómica condicional que se vuelve elegible eventualmente es ejecutada si su guarda se convierte en true y de allí en adelante permanece true.

Fairness Fuerte. Una política de scheduling es fuertemente fair si es incondicionalmente fair y toda acción atómica condicional que se vuelve elegible eventualmente es ejecutada si su guarda es true con infinita frecuencia.

####### Clase 3

Herramientas para la concurrencia

• Memoria compartida
  • Variables compartidas
  • Semáforos
  • Regiones Críticas Condicionales
  • Monitores
• Memoria distribuida (pasaje de mensajes)
  • Mensajes asincrónicos
  • Mensajes sincrónicos
  • Remote Procedure Call (RPC)
  • Rendezvous

Sincronización por variables compartidas.

###Problema de la SC:

Propiedades que de de la Seccion Critica

• Exclusión mutua: A lo sumo un proceso a la vez está ejecutando su sección crítica
• Ausencia de Deadlock: Si dos o más procesos tratan de entrar a sus secciones críticas, al menos uno tendrá éxito.
• Ausencia de Demora Innecesaria: Si un proceso está tratando de entrar a su SC y los otros están ejecutando sus SNC o terminaron, el primero no está impedido de entrar a su SC.
• Eventual Entrada: Un proceso que está intentando entrar a su SC eventualmente lo hará.

Busy Waiting

En la técnica de busy waiting un proceso chequea repetidamente una condición hasta que sea verdadera, es decir, está ocupado haciendo nada más que un chequeo de la guarda. Ventaja: implementación con instrucciones de cualquier procesador.
Ineficiente en multiprogramación (cuando varios procesos comparten el procesador y la ejecución es interleaved). Aceptable si cada proceso ejecuta en su procesador.

Defectos de busy waiting

Complejos y sin clara separación entre variables de sincronización y las usadas para computar resultados. Es difícil diseñar para probar corrección. Incluso la verificación. Es compleja cuando se incrementa el número de procesos. Es una técnica ineficiente si se la utiliza en multiprogramación. Un procesador ejecutando un proceso spinning puede ser usado de manera más productiva por otro proceso.

Solución grano fino: "Spin Locks"

Esta solución tiene como objetivo hacer átomico el await de grano grueso, para esto se usa alguna instrucción especial que casi todas las máquinas tienen, que puede usarse para implementar las acciones atómicas condicionales de este programa (test-and-set, fetch-and-add, compare-and-swap). Por ahora definimos y usamos Test-and-Set (TS)

La instrucción TS toma dos argumentos booleanos: un lock compartido y un código de condición local cc. Como una acción atómica, TS setea cc al valor de lock, luego setea lock a true:

TS(lock,cc): 〈 cc := lock; lock := true 〉

Cuando se usa una variable de lockeo de este modo, se lo llama spin lock pues los procesos “dan vueltas” (spin) mientras esperan que se libere el lock.
Esta solución cumple las 4 propiedades si el scheduling es fuertemente fair. Una política débilmente fair es aceptable (rara vez todos los procesos están simultáneamente tratando de entrar a su SC).
Aunque la última solución es correcta, se demostró que en multiprocesadores puede llevar a baja performance si varios procesos están compitiendo por el acceso a una SC. Esto es porque lock es una variable compartida y todo proceso demorado continuamente la referencia. Esto causa “memory contention”, lo que degrada la performance de las unidades de memoria y las redes de interconexión procesador-memoria. Además, la instrucción TS escribe en lock cada vez que es ejecutada, aún cuando el valor de lock no cambie.
Spin locks no controla el orden de los procesos demorados entonces es posible que alguno no entre nunca si el scheduling no es fuertemente fair (race conditions).

Algoritmo TIE-BREAKER

El algoritmo tie-breaker (o algoritmo de Peterson) es un protocolo de SC (Sección Crítica) que requiere solo scheduling incondicionalmente fair para satisfacer la propiedad de eventual entrada. Además no requiere instrucciones especiales del tipo Test-and-Set. Sin embargo, el algoritmo es mucho más complejo que la solución spin lock. Usa una variable adicional para romper empates, indicando qué proceso fue el último en comenzar a ejecutar su protocolo de entrada a la SC. Si hay n procesos, el entry protocol en cada proceso consiste de un loop que itera a través de n-1 etapas. En cada etapa, usamos instancias del algoritmo tie-breaker para dos procesos paradeterminar cuales procesos avanzan a la siguiente etapa. El algoritmo tie-breaker n-proceso es costoso en tiempo ybastante complejo y difícil de entender. Esto es en parte porque no es obvio cómo generalizar el algoritmo de 2 procesos a n.

Algoritmo Ticket

Es una solución para N-procesos mas facil de entender que la solucion de N procesos del algoritmo Tie-Breaker. La solución también ilustra cómo pueden usarse contadores enteros para ordenar procesos. En esta solución se reparten números y se espera turno: Los clientes toman un número mayor que el de cualquier otro que espera ser atendido; luego esperan hasta que todos los clientes con un número más chico sean atendidos. La ausencia de deadlock y de demora innecesaria resultan de que los valores de turno son únicos. Con scheduling débilmente fair se asegura eventual entrada. El algoritmo ticket tiene un problema potencial que es común en algoritmos que emplean incrementos en contadores: los valores de number y next son ilimitados. Si el algoritmo corre un tiempo largo, se puede alcanzar un overflow. Para este algoritmo podemos resolver el problema reseteando los contadores a un valor chico (digamos 1) cada vez que sean demasiado grandes. Si el valor más grande es al menos tan grande como n, entonces los valores de turn[i] se garantiza que son únicos.

var number := 1, next := 1, turn[1:n] : int := ( [n] 0 )
P[i: 1..n] :: 
	do true →
		turn[i] := FA(number,1)
		do turn[i] ≠ next → skip od
		critical section
		next := next + 1
		non-critical section
	od

Fetch-and-Add es una instrucción con el siguiente efecto:

FA(var,incr): 〈 temp := var; var := var + incr; return(temp) 〉

La mayor fuente de demora en el algoritmo ticket es esperar a que turn[i] sea igual a next.

Algoritmo Bakery

El algoritmo ticket puede ser implementado directamente en máquinas que tienen una instrucción como Fetch-and-Add. Si solo tenemos disponibles instrucciones menos poderosas, podemos simular la parte de obtención del número del algoritmo ticket usando algun algoritmo SC con busy waiting (como Spin lock). Pero eso requiere usar otro protocolo de SC, y la solución podría no ser fair. bakery algorithm es un algoritmo del tipo de ticket que es fair y no requiere instrucciones de máquina especiales. El algoritmo es más complejo que el ticket, pero ilustra una manera de romper empates cuando dos procesos obtienen el mismo número. No requiere un contador global proximo que se “entrega” a cada proceso al llegar a la SC. Cada proceso que trata de ingresar recorre los números de los demás y se autoasigna uno mayor. Luego espera a que su número sea el menor de los que esperan. Los procesos se chequean entre ellos y no contra un global.

El algoritmo asegura entrada eventual si el scheduling es débilmente fair pues una vez que una condición de demora se convierte en true, permanece true.

Sincronización Barrier

Barrier synchronization es un protocolo de sincronización donde se demoran al final de cada iteración a todos los procesos representando una barrera a la que todos los procesos deben arribar antes de que se les permita pasar. En general manipulan un arreglo, y cada iteración realiza la misma computación sobre todos los elementos del arreglo. Generalmente son múltiples procesos para computar partes disjuntas de la solución en paralelo. En la mayoría de los algoritmos iterativos paralelos cada iteración depende de los resultados de la iteración previa.

Contador compartido

La manera más simple de especificar los requerimientos para una barrera es emplear una variable entera compartida, count, el cual es inicialmente 0. Asumimos que hay N procesos worker que necesitan encontrarse en una barrera. Cuando un proceso llega a la barrera, incrementa count. Por lo tanto, cuando count es N, todos los procesos pueden continuar.

La dificultad es que count debe ser 0 al comienzo de cada iteración. Por lo tanto, count necesita ser reseteada a 0 cada vez que todos los procesos han pasado la barrera. Más aún, tiene que ser reseteada antes de que cualquier proceso trate nuevamente de incrementar count. Es posible resolver este problema de "reset" empleando dos contadores, uno que cuenta hasta N y otro que cuenta hacia abajo hasta 0, con los roles de los contadores switcheados después de cada etapa. Sin embargo, hay problemas adicionales, con el uso de contadores compartidos. Primero, tienen que ser incrementados y/o decrementados como acciones atómicas. Segundo, cuando un proceso es demorado, está examinando continuamente count. En el peor caso, N-1 procesos podrían estar demorados esperando que el n-ésimo proceso llegue a la barrera. Esto podría llevar a memory contention.

Flags y Coordinadores

Una manera de evitar el problema de contención de memoria es distribuir la implementación de count usando n variables que sumen el mismo valor. En lugar de que cada Worker testear el valor de count, hacemos que cada Worker espere que un único valor se convierta en true. Hay un proceso coordinador que espera a que todos los elementos de llegada(que es un arreglo con la cantidad de procesos worker, una posición para cada worker) se vuelvan 1, luego setea todos los elementos de continue(es un arreglo, una posición para cada worker) en 1. Reintroduce memory contention y es ineficiente.

Arboles

Combinar las acciones de workers y coordinador, haciendo que cada worker sea también coordinador. Por ejemplo, workers en forma de árbol: las señales de arribo van hacia arriba en el árbol, y las de continuar hacia abajo. Problemas: Requiere un proceso (y procesador) extra. El tiempo de ejecución del coordinador es proporcional a n.

Barrera Simetrica / Butterfly Barrier

Una barrera simétrica para n procesos se construye a partir de pares de barreras simples para dos procesos. Para construir una barrera de dos procesos, podríamos usar la técnica coordinador/worker. Sin embargo, las acciones de los dos procesos serían diferentes. En lugar de esto, podemos construir una barrera completamente simétrica como sigue. (@) Sea que cada proceso tiene un flag que setea cuando arriba a la barrera. Luego espera a que el otro proceso setee su flag y finalmente limpia la bandera del otro.

Sean Worker[1:n] los n procesos. Si n es potencia de 2, podemos usar butterfly barrier. Una butterfly barrier tiene log2 n etapas. Cada Worker sincroniza con un Worker distinto en cada etapa. En particular, en la etapa s un Worker sincroniza con un Worker a distancia 2^(s-1) etapas. Cada worker se puede implementar como en (@). Cuando cada Worker pasó a través de log 2 n etapas, todos los Workers deben haber arribado a la barrera y por lo tanto todos pueden seguir. Esto es porque cada Worker ha sincronizado directa o indirectamente con cada uno de los otros.