Programación Concurrente y Distribuida PDF

Programación Concurrente y Distribuida Tema 1. Introducción a la programación concurrente Computación en Sistemas Distribuidos Computación concurrente, computación paralela y computación distribuida Programación Concurrente y Distribuida ¡PREGUNTA! ¿Cuál es la diferencia entre computación...

Programación Concurrente y Distribuida Tema 1. Introducción a la programación concurrente Computación en Sistemas Distribuidos Computación concurrente, computación paralela y computación distribuida Programación Concurrente y Distribuida ¡PREGUNTA! ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Programación Concurrente y Distribuida ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Concurrente: Sucede en el mismo intervalo de tiempo. Cuando los computadores tenían una única CPU y todos los procesos que se ejecutaban en un momento dado recibían “porciones” de tiempo de procesador. Los procesos eran concurrentes pero no paralelos. No hay comunicación ni coordinación entre los avances de los procesos. Programación Concurrente y Distribuida ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Paralelismo: Se ejecuta al mismo tiempo. La computación paralela por definición requiere múltiples CPUs. En esta situación, más de un proceso concurrente puede ejecutarse simultáneamente. Al igual que con el procesamiento concurrente, no hay comunicación ni coordinación entre los avances de los procesos. Programación Concurrente y Distribuida ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Programación Concurrente y Distribuida ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Computación paralela Programación Concurrente y Distribuida ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Computación paralela Ejemplo: Cálculo de una nómina Programación Concurrente y Distribuida ¿Cuál es la diferencia entre computación concurrente y computación distribuida? Distribuido: Varios programas se ejecutan simultáneamente y se comunican entre sí para realizar un cómputo colectivamente. La esencia de la computación distribuida es que una computación general se “distribuye” en múltiples procesos (generalmente, casi siempre, pero no necesariamente, usando múltiples procesadores) que realizan la tarea computacional general mediante la comunicación entre los procesos. Programación Concurrente y Distribuida Concepto de concurrencia Programación Concurrente y Distribuida Computación concurrente y computación distribuida Programa secuencial nos referimos a un programa formado por instrucciones que se ejecutan una tras otra. Un proceso secuencial es un programa en ejecución. Un programa concurrente está formado por dos o más programas secuenciales que se ejecutan concurrentemente. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Ejecución paralela o concurrencia real, para que este caso se pueda dar necesitamos que existan tantos procesadores como procesos. Ejecución pseudo paralela o concurrente simulada, en este caso, tendremos más procesos que procesadores, por lo que los procesadores tendrán que repartirse el trabajo de ejecución de los procesos. Programación Concurrente y Distribuida ¡PREGUNTA! ¿Qué es la programación concurrente? Programación Concurrente y Distribuida Computación concurrente y computación distribuida Simplificando … , es cuando se realiza más de una cosa al mismo tiempo. No debe confundirse con el paralelismo, la programación concurrente o de concurrencia es cuando se ejecutan múltiples secuencias de operaciones en períodos de tiempo superpuestos. En el ámbito de la programación, la concurrencia es un tema bastante complejo. Tratar con estructuras como subprocesos (threads) y bloqueos (locks) y evitar problemas como “race conditions” (condiciones de carrera) y “deadlocks”puede ser bastante complicado, lo que dificulta la escritura de programas concurrentes. Programación Concurrente y Distribuida Computación concurrente y computación distribuida “race conditions” (condiciones de carrera) y “deadlocks” Una condición de carrera ocurre cuando dos o más subprocesos pueden acceder a datos compartidos e intentan cambiarlos al mismo tiempo. Debido a que el algoritmo de programación de subprocesos puede cambiar de subproceso en cualquier momento, no se sabe el orden en el que los subprocesos intentarán acceder a los datos compartidos. Por lo tanto, el resultado del cambio de datos depende del algoritmo de programación de subprocesos, es decir, ambos subprocesos están "compitiendo" para acceder a los datos o cambiarlos. Programación Concurrente y Distribuida Computación concurrente y computación distribuida “race conditions” (condiciones de carrera) y “deadlocks” Un bloqueo se produce cuando varios procesos intentan acceder al mismo recurso al mismo tiempo. Un proceso esperar a que el otro termine. Un “deadlocks” o punto muerto se produce cuando el proceso que está esperando todavía tiene otro recurso que el primero necesita antes de poder terminar. Programación Concurrente y Distribuida Computación concurrente y computación distribuida “race conditions” (condiciones de carrera) y “deadlocks” Un “deadlocks” o punto muerto, ejemplo: El proceso X y el proceso Y utilizan el recurso A y el recurso B X empieza a utilizar A. X e Y intentan empezar a utilizar B Y "gana" y obtiene B primero Ahora Y necesita utilizar A X bloquea A y espera a Y Programación Concurrente y Distribuida Arquitecturas en sistemas concurrentes Programación Concurrente y Distribuida Computación concurrente y computación distribuida El paralelismo se puede dar en tres sistemas físicos distintos: Sistemas multiprocesadores. Disponen de una memoria que es común a todos los procesos con independencia de que cada proceso pueda disponer de una memoria local. Sistemas distribuidos. No se disponen de memoria común, sino que cada proceso posee su propia memoria local. Sistemas de tiempo compartido. A los sistemas multiprocesadores y a los de tiempo compartido los podemos agrupar como entornos centralizados. Programación Concurrente y Distribuida Computación concurrente y computación distribuida El paralelismo se puede dar en tres sistemas físicos distintos: Sistemas multiprocesadores. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Sistemas distribuidos. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Sistemas de tiempo compartido. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Algunos sistemas distribuidos se permite que un proceso pueda acceder a la memoria de otro, pero solo para leer. Esto permite conocer el estado de los procesos un proceso no permitirá nunca que otro modifique sus variables. Programación Concurrente y Distribuida ¡PREGUNTA! ¿Ventajas de la Programación Concurrente? Programación Concurrente y Distribuida Computación concurrente y computación distribuida Velocidad de ejecución Existen aplicaciones donde la velocidad de respuesta es crítica. Tenemos un número de procesos > número de procesadores. No es aplicable la programación paralela. No coincide número de procesos y procesadores. La programación concurrente puede mejorar el tiempo de respuesta. Solución de problemas concurrentes Realizar cálculos de forma más rápida si existen varias CPU. Simulaciones físicas que no pueden realizarse de forma secuencial Todo tipo de servidores: atender varias peticiones a la vez. Aplicaciones con GUI. Sistemas empotrados donde se reacciona a diversos tipos de entrada en tiempo real. Programación Concurrente y Distribuida Condiciones de Bernstein en la Programación Concurrente Programación Concurrente y Distribuida ¡PREGUNTA! ¿Qué son las Condiciones de Bernstein? Programación Concurrente y Distribuida Computación concurrente y computación distribuida Las Condiciones de Bernstein sirven para poder determinar si dos conjuntos de instrucciones Si y Sj, pueden ser ejecutadas concurrentemente Sea Sk un conjunto de instrucciones Se definen los siguientes conjuntos sobre las sentencias El conjunto de lectura de una sentencia, son las variables cuyo valor es usado en la sentencia para la lectura, se denomina R(sentencia). El conjunto de escritura de una sentencia son las variables cuyo valor es modificado en la sentencia, a este conjunto se le denomina W(sentencia). Programación Concurrente y Distribuida Computación concurrente y computación distribuida Para que dos conjuntos de instrucciones se puedan ejecutar concurrentemente se tiene que cumplir las siguientes condiciones: 1. R(S1) ∩ W(S2) = {x, y} ∩ {b} = ∅ = { }. El conjunto de lectura de la sentencia S1 intersección con el conjunto de escritura de la sentencia S2 debe de resultar el conjunto vacío, es decir, el conjunto de lectura de S1 y de S2 no tienen variables en común. 2. W(S1) ∩ R(S2) = {a} ∩ {z} = ∅ = { } El conjunto de escritura de la sentencia S1 intersección con el conjunto de lectura de la sentencia S2 debe de resultar el conjunto vacío, es decir, el conjunto de escritura de S1 y el conjunto de lectura de S2 no tienen variables en común. 3. W(S1) ∩ W(S2) = {a} ∩ {b} = ∅ = { } El conjunto de escritura de la sentencia S1 intersección con el conjunto de escritura de la sentencia S2 debe de resultar el conjunto vacío, es decir, el conjunto de escritura de S1 y de S2 no tienen variables en común. También se podría representar como: Read set(Si) ∩ Write set(Sj) = ϕ Write set(Si) ∩ Read set(Sj) = ϕ Write set(Si) ∩ Write set(Sj) = ϕ Programación Concurrente y Distribuida Grafos de Precedencia en la Programación Concurrente Programación Concurrente y Distribuida Computación concurrente y computación distribuida Gráficos de precedencia begin Sentencias S1: par begin par begin - par end begin o S2; Co begin - Co end S6; end begin S3; Los programas con CoBegin/CoEnd S7; continuarán cuando se termine de ejecutar el código end que se encuentra entre las dos sentencias. S4; S5; par end S8; end (*) PARBEGIN/PAREND es también designado como COBEGIN/COEND. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Gráficos de precedencia Sentencias fork y join La sentencia fork hace que un proceso empiece a ejecutarse concurrentemente con las sentencias que se encuentran a continuación del fork en el programa. La sentencia join indica que el programa debe de detenerse hasta que el proceso invocado finalice su ejecución. Fork-join: estilo de paralelización donde el cómputo (task) es partido en sub-cómputos menores (subtasks). Los resultados de estos se unen (join) para construir la solución al cómputo inicial. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Gráficos de precedencia Sentencias fork y join Características principales: Los sub-cómputos son independientes para que el cómputo se pueda realizar en paralelo. Las sub-tareas se pueden crear en cualquier momento de la ejecución de la tarea. Las tareas no deben bloquearse, excepto para esperar el final de las subtareas. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Gráficos de precedencia Sentencias fork y join Programación Concurrente y Distribuida Características de los Sistemas Concurrentes Programación Concurrente y Distribuida Computación concurrente y computación distribuida Características de los sistemas concurrentes vs secuenciales En un programa secuencial se ejecutan las instrucciones en un orden predefinido. El resultado final no depende de la velocidad de ejecución del código, su comportamiento es reproducible, es decir, sabemos cómo se va a ejecutar. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Características de los sistemas concurrentes vs secuenciales En una programación concurrente El resultado depende de la velocidad del código. El comportamiento no es reproducible. Es no determinista, es decir, existe una incertidumbre acerca del orden en que se van a ejecutar las instrucciones. Hay que tomar medidas para no obtener distintos resultados con cada ejecución del programa concurrente. Se producen o no errores transitorios dependiendo de los caminos que se siga en la ejecución. Estos errores son difíciles de detectar. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Características de los sistemas concurrentes vs secuenciales Indeterminismo en la programación concurrente El orden parcial produce consecuentemente un comportamiento indeterminista. Es decir, repetidas ejecuciones sobre un mismo conjunto de datos resultan diferentes resultados. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Características de los sistemas concurrentes vs secuenciales En una programación concurrente Programación Concurrente y Distribuida Problemas en la Programación Concurrente Programación Concurrente y Distribuida Computación concurrente y computación distribuida Problemas en la programación concurrente Un programa secuencial es correcto cuando al terminar el programa produce el resultado esperado. Un programa concurrente no tiene por qué terminar (son varios procesos que se entrelazan) y además no produce siempre el resultado esperado, por tanto, diremos que es correcto si se verifican determinadas propiedades de seguridad y de vivacidad. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Problemas en la programación concurrente Propiedades de seguridad Las propiedades de seguridad que debe cumplir el sistema para no llegar a un estado incorrecto son: Exclusión mutua: todas las secciones críticas se ejecutan de forma indivisible. Sincronización: intercambio de información para coordinar actividades. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Problemas en la programación concurrente Propiedades de vivacidad Las propiedades de vivacidad que debe cumplir el sistema para que tenga un progreso constructivo son: No Deadlock: esta situación se conoce con el nombre de interbloqueo y se produce cuando los procesos quedan parados indefinidamente por falta de vivacidad total o falta de vivacidad parcial: Vivacidad total: aparece cuando todo el sistema se paraliza indefinidamente. Vivacidad parcial: aparece cuando parte del sistema se paraliza indefinidamente. No Livelock: Livelock es la situación que se caracteriza por que todo el sistema o parte de él se encuentra realizando operaciones inútiles o no constructivas indefinidamente. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Problemas en la programación concurrente Propiedades de vivacidad Las propiedades de vivacidad que debe cumplir el sistema para que tenga un progreso constructivo son: Equitatividad: también conocida como Starvation, que se da cuando hay procesos del sistema que son discriminados sistemáticamente. Diferencia entre Livelock y DeadLock: En Livelock el sistema se encuentra en ejecución, pero atrapado en un bucle infinito En Deadlock el proceso se encuentra parado y por tanto no consume tiempo de procesador. Programación Concurrente y Distribuida Computación concurrente y computación distribuida Problemas en la programación concurrente // Counting.java public class Counting { public static void main(String[] args) throws InterruptedException { class Counter { int counter = 0; public void increment() { counter++; } public int get() { return counter; } } final Counter counter = new Counter(); class CountingThread extends Thread { public void run() { for (int x = 0; x < 500000; x++) { counter.increment(); } En cada ejecución del programa obtenemos } diferentes resultados } CountingThread t1 = new CountingThread(); CountingThread t2 = new CountingThread(); t1.start(); t2.start(); t1.join(); t2.join(); System.out.println(counter.get()); } } Computación en Sistemas Distribuidos ¡Muchas Gracias! ¿Preguntas?