Programación Concurrente y Distribuida PDF

Programación Concurrente y Distribuida Tema 3. Conceptos básicos de programación concurrente Alfonso Antolínez García ® 1 Computación en Sistemas Distribuidos Conceptos básicos de programación concurrente Alfonso Antolín...

Programación Concurrente y Distribuida Tema 3. Conceptos básicos de programación concurrente Alfonso Antolínez García ® 1 Computación en Sistemas Distribuidos Conceptos básicos de programación concurrente Alfonso Antolínez García ® Programación Concurrente y Distribuida ¡PREGUNTA! ¿Cuáles son los conceptos básicos de programación concurrente? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Abstracción, Interfoliación (Intercalación, mezclado, etc.), Atomicidad, Corrección, Seguridad Vivacidad Equidad Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Abstracción/Abstraction Entendemos por abstracción la capacidad de aislar y encapsular la información del diseño y la ejecución. La principal abstracción, que nos permite desarrollar y describir sistemas complejos, es la que denominamos encapsulamiento. La abstracción en programación concurrente es el estudio de la ejecución interfoliada/interleaved de secuencias de instrucciones atómicas que pertenecen a procesos secuenciales (procesos secuenciales normales (con E/S) y ejecutados simultáneamente). Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Interfoliación/Intercalación Interfoliar equivale a mezclar. Un programa concurrente consta de un conjunto de procesos secuenciales que se ejecutan simultáneamente. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Interfoliación/Intercalación Suponemos: Dos procesos en la misma computadora, pero distintas CPU (abstracción), y dos tipos de interacciones entre procesos: - Contención: dos procesos o más compiten por el mismo recurso o deben acceder a la misma información. - Comunicación: dos procesos o más deben comunicarse entre sí para intercambiar algún tipo de información. Este paso de mensajes de un proceso a otro permite la sincronización. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Interfoliación Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Atomicidad En la definición de modelo de concurrencia aparece el concepto de instrucciones atómicas. Instrucciones atómicas son aquellas instrucciones cuya ejecución no puede ser interfoliada. Una definición más formal …→ Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Atomicidad Una operación atómica se refiere a un concepto fundamental en informática y programación, que representa una unidad de trabajo que es indivisible y que se garantiza que se ejecutará como una operación única, coherente e ininterrumpida. En esencia, una operación atómica es un conjunto de instrucciones que se ejecutan secuencialmente sin ninguna interrupción o interferencia de otros procesos o subprocesos concurrentes. Alfonso Antolínez García ® Programación Concurrente y Distribuida ¡PREGUNTA! ¿Por qué son importantes las operaciones atómicas? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Atomicidad La importancia de las operaciones atómicas radica en su capacidad para mantener la integridad y coherencia de los datos frente al acceso concurrente. Cuando varios procesos o subprocesos intentan modificar un recurso compartido simultáneamente, pueden ocurrir condiciones de carrera, lo que lleva a resultados impredecibles y erróneos. Las operaciones atómicas proporcionan un mecanismo para mitigar estos problemas al garantizar que se acceda al recurso compartido de manera mutuamente excluyente, evitando conflictos y asegurando que las operaciones se ejecuten de forma atómica. Alfonso Antolínez García ®  Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Atomicidad El resultado es el mismo independientemente de la interfoliación que se produzca. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Corrección Los programas concurrentes son una tarea compleja dado que la interfoliación nos lleva a una infinidad de trazas que pueden provocar la irrepetibilidad de una ejecución. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Corrección Analizando los distintos aspectos que intervienen en la corrección de los programas concurrentes. Cuando nos referimos a corrección, queremos indicar que las soluciones propuestas cumplen con los criterios de satisfacción del problema a resolver. En los algoritmos, deberemos comprobar si cumplen unas sentencias iniciales, denominadas invariantes. Estas sentencias deben de cumplirse antes de realizar el algoritmo, y al finalizar el mismo deben de permanecer sin cambios. En el caso de que se cumpla podremos indicar que el algoritmo es correcto. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Corrección Invariantes Una invariante es una condición o relación que siempre es verdadera. La definición se modifica un poco para la ejecución concurrente: una invariante es una condición o relación que es verdadera cuando se establece el bloqueo asociado. Una vez establecido el bloqueo, el invariante puede ser falso. Sin embargo, el código que sostiene el bloqueo debe restablecer la invariante antes de liberar el bloqueo. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Corrección Invariantes Una invariante también puede ser una condición o relación que es verdadera cuando se establece un bloqueo. Se puede considerar que las variables de condición tienen una invariante que es la condición. La declaración assert () está probando el invariante. La función cond_wait() no conserva el invariante, por lo que el invariante debe reevaluarse cuando finaliza el hilo. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Seguridad Características que se han de cumplir siempre para que podamos decir que un sistema es correcto: Exclusión mutua: imposibilidad de cohabitar en la misma zona. Podemos entender por exclusión mutua un cruce de carreteras, donde el propio cruce es la zona donde no pueden existir dos vehículos al mismo tiempo, ya que si no colisionarían. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Seguridad Características que se han de cumplir siempre para que podamos decir que un sistema es correcto: Interbloqueo: bloqueo permanente de (y debido a) un conjunto de procesos que compiten por algún recurso compartido o se comunican entre ellos. Podemos entender por interbloqueo cuando dos personas coinciden para pasar por una puerta y ninguna de las dos se pone de acuerdo para entrar. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Seguridad Características que se han de cumplir siempre para que podamos decir que un sistema es correcto: Interbloqueo (punto muerto, deadlock): Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Seguridad Características que se han de cumplir siempre para que podamos decir que un sistema es correcto: Inanición: podemos entender por inanición cuando de tres procesos, dos se alían para que el tercero no participe nunca, copando ellos el uso del recurso. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Vivacidad Las exigencias de vivacidad son exigencias que podríamos catalogar como exigencias finales. La característica de viveza indica que la ejecución de un programa con el tiempo llega a su estado deseable. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Vivacidad Propiedades de vivacidad ("liveness"): cada sentencia que se ejecute conduce en algún modo a un avance constructivo para alcanzar el objetivo funcional del programa. Son, en general, dependientes de la política de planificación que se utilice. Ejemplos de propiedades de vivacidad son: Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Vivacidad Ejemplos de propiedades de vivacidad son: No deben producirse bloqueos activos (livelock). Conjuntos de procesos que ejecutan de forma continuada sentencias que no conducen a un progreso constructivo. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Vivacidad Ejemplos de propiedades de vivacidad son: Aplazamiento indefinido (starvation): es el estado al que puede llegar un programa que aunque potencialmente puede avanzar de forma constructiva no consigue recursos para ello. Esto puede suceder, como consecuencia de que no se le asigna tiempo de procesador en la política de planificación; o porque en las condiciones de sincronización, hemos establecido criterios de prioridad que perjudican siempre al mismo proceso. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Vivacidad Ejemplos de propiedades de vivacidad son: Interbloqueo (deadlock): se produce cuando los procesos no pueden obtener, nunca, los recursos necesarios para finalizar su tarea. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Equidad Esta propiedad tiene que ver con el reparto de recursos: Débil: aquella forma de equidad que garantiza que si un proceso hace una petición continuada al final será satisfecha. Fuerte: aquella forma de equidad que garantiza que si un proceso realiza una petición infinitamente, al final será satisfecha. Lineal: aquella forma de equidad que garantiza que si un proceso realiza una petición, esta será satisfecha antes de que a otro proceso se le satisfagan dos veces. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Equidad Esta propiedad tiene que ver con el reparto de recursos. FIFO típica de cola: aquella forma de equidad que garantiza que el primer proceso en hacer la petición será el primero en ser servido. En orden de llegada. La FIFO es la más restrictiva y además solo es útil en el caso de sistemas centralizados Alfonso Antolínez García ® Computación en Sistemas Distribuidos Corrección de programas concurrentes Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Además de las especificaciones funcionales, un programa concurrente debe cumplir… Propiedades de seguridad: Son aquéllas que aseguran que nada malo va a pasar durante la ejecución del programa Propiedades de viveza: Son aquellas que aseguran que algo bueno pasará eventualmente durante la ejecución del programa Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Propiedades de seguridad: Exclusión mutua Condición de sincronización Interbloqueo: se produce cuando todos los procesos están esperando que ocurra un evento que nunca se producirá. Se le denomina también interbloqueo pasivo. (deadlock o abrazo mortal) Alfonso Antolínez García ® Computación en Sistemas Distribuidos Ejemplo ilustrativo de las propiedades (juego del pañuelo) Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente En el juego del pañuelo hay dos equipos A y B, y un juez con un pañuelo. Cada jugador de un equipo tiene un número del 1 al 3. No puede haber dos jugadores en el mismo equipo con el mismo número. El juez dice un número y entonces los dos rivales con el mismo número salen corriendo a coger el pañuelo. El jugador que lo coja ha de volver corriendo a su sitio sin que su rival logre tocarle la espalda. En este escenario plantearemos las propiedades de seguridad y viveza Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Propiedades de seguridad: Exclusión mutua Condición de sincronización Interbloqueo (punto muerto): se produce cuando todos los procesos están esperando que ocurra un evento que nunca se producirá. Se le denomina también interbloqueo pasivo. (deadlock o abrazo mortal) Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Propiedades de vivacidad: Interbloqueo activo: Se produce cuando un sistema ejecuta una serie de instrucciones sin hacer ningún progreso (livelock) Inanición: Existen un grupo de procesos que nunca progresan pues no se les otorga tiempo de procesador para avanzar Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Exclusion mutua: Hay recursos que deben ser accedidos en exclusión mutua y si otros procesos quieren acceder a este recurso tienen que esperar a que sea liberado. Ejemplo: basado en el ejemplo del pañuelo … ha de adquirirse por un jugador o por otro, en exclusion mutua, ya que si lo adquieren los dos puede llegar a romperse → mal funcionamiento del sistema. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Condición de sincronización: Hay situaciones, en las que un proceso debe esperar a que se produzca un determinado evento para poder avanzar y no debería de avanzar antes de que ese evento ocurra. Ejemplo: el jugador debe esperar a que digan su número para poder salir en busca del pañuelo. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Interbloqueo: En el juego del pañuelo, se daría si uno de los jugadores coge el pañuelo y se lo lleva fuera del juego. El juez debería esperar a que le devuelva el pañuelo y los jugadores a que el juez diga su número, pero esto puede nunca pasar. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Interbloqueo activo: En el ejemplo del pañuelo … si los jugadores que salen a por el pañuelo, simulan cogerlo, pero nunca llegan a cogerlo. Inanición: En nuestro ejemplo se produciría si el juez nunca dice el número de un jugador en concreto. Hay que garantizar equidad en el trato a los procesos a no ser que las especificaciones del sistema digan lo contrario. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Ejemplo: supongamos que la variable x se actualiza con dos funciones que se ejecutan concurrentemente, ¿qué valor tendría x al acabar el programa? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿De qué problema(s) de los nombrados adolece el programa? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿De qué problemas de los nombrados en esta sesión adolece el programa? Inanición, si incrementa_5_A() o incrementa_5_B() toman el control de x y no deja a la otra entra actualizar la variable Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿Por qué el programa podría ser considerado indeterminista? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿Por qué el programa podría ser considerado indeterminista? El resultado es indeterminado dependiendo del camino y velocidad de ejecución de los procesos. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿Es posible la programación concurrente en arquitecturas hardware monoprocesador? Respuesta: ¿... ? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿Es posible la programación concurrente en arquitecturas hardware monoprocesador? Respuesta: En arquitecturas hardware monoprocesador … También es posible tener ejecución concurrente de procesos No todos los procesos se ejecutan al mismo tiempo, sólo uno de ellos los estará haciendo en un momento dado, pero la sensación del usuario es de estar ejecutándose al mismo tiempo El sistema operativo irá alternando el tiempo de procesador entre los distintos procesos Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿En arquitecturas monoprocesador cuál es la forma de sincronizar los procesos? Respuesta: ¿…? Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Pregunta: ¿En arquitecturas monoprocesador cuál es la forma de sincronizar los procesos? Respuesta: En arquitecturas hardware monoprocesador todos los procesos comparten la misma memoria. La forma de sincronizar y comunicar es mediante el uso de variables compartidas. Alfonso Antolínez García ® Computación en Sistemas Distribuidos Tipos de arquitecturas (desde el punto de vista de procesos) Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Las arquitecturas las clasificamos en: Fuertemente acopladas : Se comunican mediante variables en memoria compartida, ya que los procesadores y otros dispositivos están conectados a un bus de datos. Débilmente acopladas : No existe memoria compartida por los procesadores, cada procesador tiene su memoria local. Se trata de un Procesamiento distribuido. El paso de mensajes, es el mecanismo de comunicación más habitual. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Ejercicio: ¿Cuál de las siguientes instrucciones se pueden ejecutar concurrentemente? a) x=x+1 b) y= 1 c) x=a+1 d) x=y+a Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Ejercicio: ¿Cuál de las siguientes instrucciones se pueden ejecutar concurrentemente? a) x=x+1 b) y= 1 c) x=a+1 d) x=y+a Teniendo en cuenta las Condiciones de Bernstein Para que se puedan ejecutar concurrentemente dos conjuntos de instrucciones Si y Sj se debe cumplir que ninguno escriba lo que el otro lee o escribe. Independencia en las entradas, independencia en las salidas y no conflicto en la escritura. Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Ejercicio: ¿Cuál de las siguientes instrucciones se pueden ejecutar concurrentemente? a) x=x+1 b) y= 1 c) x=a+1 d) x=y+a Teniendo en cuenta las Condiciones de Bernstein (a) y (b) pueden ejecutarse concurrentemente. (a) y (c) no pueden ejecutarse concurrentemente debido a la dependencia de la variable x. (a) y (d) no pueden ejecutarse concurrentemente debido a la dependencia de la variable x. … Alfonso Antolínez García ® Programación Concurrente y Distribuida Conceptos básicos de programación concurrente Ejercicio: ¿Cuál de las siguientes instrucciones se pueden ejecutar concurrentemente? a) x=x+1 a b c d b) y= 1 a Si No No c) x=a+1 d) x=y+a b Si Si c No Teniendo en cuenta las Condiciones de Bernstein d (a) y (b), (b) y (c), (b) y (d) pueden ejecutarse concurrentemente. Alfonso Antolínez García ® Computación en Sistemas Distribuidos ¡Muchas Gracias! ¿Preguntas? Alfonso Antolínez García ®