Sincronización Entre Procesos (aka: Semáforos)

Transcript

Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Sincronizaci´on entre procesos (aka: sem´aforos) Mat´ıas Barbeito DC - FCEyN - UBA Sistemas Operativos, 1c-2016 Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Race condition Sem´ aforos ¿D´onde estamos? ¿De d´ onde venimos? Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Race condition Sem´ aforos Primero repasemos brevemente lo que vieron en la te´orica. ¿Qu´e es una race condition? Defecto en un proceso, donde el resultado del mismo depende inesperadamente del orden en que se ejecuten ciertos eventos. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Race condition Sem´ aforos ¿Cu´al es el output de los siguientes procesos A y B corriendo simult´aneamente y con memoria compartida? x comienza inicializado en 0. B x = x + 1; A x = x + 1; print(x); Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Race condition Sem´ aforos ¿Qu´e es un sem´aforo? Es una variable (o tipo abstracto de datos) que permite controlar el acceso de m´ ultiples procesos a un recurso com´ un en un ambiente de programaci´ on paralela. ¿Es lo mismo que usar un entero y fijarme qu´e valor tiene? No, es escencial que las primitivas sobre sem´aforos sean at´omicas. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Race condition Sem´ aforos Recordemos cu´ales son las primitivas: Primitivas sem_create(int value): Devuelve un nuevo sem´aforo inicializado en value. (Otras formas: Semaphore(value), new Semaphore(value), etc.) sem_wait(semaphore sem): Mientras el valor sea menor o igual a 0 se bloquea esperando un signal. Luego decrementa el valor de sem. (Otras formas: wait(sem), P(sem), sem.wait(), etc.) sem_signal(semaphore sem, [int n = 1]): Incrementa en uno el valor del sem´aforo sem y despierta a alguno1 de los procesos que est´an esperando en ese sem´aforo. (Otras formas: signal(sem, [n]), V(sem), sem.signal([n]), etc.) 1 En general las bibliotecas de sem´ aforos no garantizan en qu´e orden se despertar´ a a los procesos que est´ an esperando en un sem´ aforo. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Ejercicio Se tienen 3 procesos A, B y C. Construya el c´ odigo con sem´aforos de manera tal que la secuencia sea ABC,ABC,ABC,. . . Soluci´ on: Uso 3 sem´aforos, sem A, sem B y sem C. Sus valores de inicializaci´on son: sem A = 1, sem B = 0, sem C = 0 while(true): sem A.wait() // Secci´ on cr´ıtica A() // Fin secci´ on cr´ıtica sem B.signal() while(true): sem B.wait() // Secci´ on cr´ıtica B() // Fin secci´ on cr´ıtica sem C.signal() Mat´ıas Barbeito while(true): sem C.wait() // Secci´on cr´ıtica C() // Fin secci´on cr´ıtica sem A.signal() Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Ejercicio ¿Y si quiero que la secuencia sea BCA,BCA,BCA,. . .? Soluci´ on: Cambio los valores de inicializaci´ on de los sem´aforos por sem A = 0, sem B = 1, sem C = 0 Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Ejercicio ¿Y si quiero que la secuencia sea BBCA,BBCA,BBCA,. . .? Soluci´ on: Uso 3 sem´aforos, sem A, sem B y sem C. Sus valores de inicializaci´on son: sem A = 0, sem B = 2, sem C = 0 while(true): sem A.wait() // Secci´ on cr´ıtica A() // Fin secci´ on cr´ıtica sem B.signal() sem B.signal() while(true): sem B.wait() // Secci´ on cr´ıtica B() // Fin secci´ on cr´ıtica sem C.signal() Mat´ıas Barbeito while(true): sem C.wait() sem C.wait() // Secci´on cr´ıtica C() // Fin secci´on cr´ıtica sem A.signal() Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Ejercicio Se tienen N procesos, P0 , P1 , ..., PN−1 (donde N es un par´ametro). Se los quiere sincronizar de manera que la secuencia de ejecuci´on sea Pi , Pi+1 , ..., PN−1 , P0 , ..., Pi−1 con i tambi´en un par´ametro. Soluci´ on: Global Semaphore semaforos[N]; for(int j = 0; j < N; j++) semaforos[j] = Semaphore(0); semaforos[i] = Semaphore(1); En cada Pj semaforos[j].wait() // Algo semaforos[(j + 1) % n].signal() Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Ejercicio Suponga que se tienen N procesos Pi , cada uno de los cuales ejecuta un conjunto de sentencias ai y bi . Se los quiere sincronizar de manera tal que los bi se ejecuten despu´es de que se hayan ejecutado todos los ai Soluci´ on: Global mutex = Semaphore(1); cuantosLlegaron = 0; barrera = Semaphore(0); y en cada Pi ... ai (); mutex.wait(); cuantosLlegaron++; if (cuantosLlegaron == N) barrera.signal(N); mutex.signal(); barrera.wait(); bi (); Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Ejercicio En un sistema, para determinado recurso exclusivo se ha definido una pol´ıtica de acceso FIFO. Se tienen una serie de procesos que desean acceder a ese recurso. Escribir el c´ odigo de sincronizaci´on de cada uno de los procesos para asegurar que el acceso respeta la pol´ıtica adoptada. Tip para la soluci´ on Usar una cola :) Tip para la soluci´ on 2 Hay que garantizar acceso exclusivo a la cola. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Cantidad de procesos est´ atica Cantidad de procesos din´ amica Soluci´ on: Global Cola c = crearCola() Semaphore mutex = Semaphore(1) Mat´ıas Barbeito Pi Semaphore yo = Semaphore(0) mutex.wait() n = long(c) c.push(yo) mutex.signal() if (n == 0) yo.signal() yo.wait() f() // Usar el recurso mutex.wait() c.pop() if (!c.empty()): c.top().signal() mutex.signal() Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso ¿Cu´ando est´a en deadlock un conjunto de procesos? Deadlock Situaci´on en la que dos o m´as acciones en competencia est´an esperando mutuamente que la otra concluya, y entonces ninguna lo hace. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Condiciones (Coffman) Exclusi´on mutua. Hold & Wait. No preemption. Espera circular. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejemplos Visuales Exclusi´on mutua: Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejemplos Visuales Hold & Wait: Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejemplos Visuales No Preemption: Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejemplos Visuales Espera circular: Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Deadlock So it begins, the great battle of our time. Un ejemplo t´ıpico de deadlock es P1 sem1.wait(); sem2.wait(); // Secci´ on cr´ ıtica sem2.signal(); sem1.signal(); P2 sem2.wait(); sem1.wait(); // Secci´ on cr´ ıtica sem1.signal(); sem2.signal(); Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejercicio En un sistema conviven 3 procesos y 2 recursos (R1 y R2) de uso exclusivo. Los 3 procesos necesitan tener los recursos a la vez para completar su ejecuci´on. ¿Puede haber deadlock? Soluci´ on: S´ı. Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejercicio ¿Y si ahora R1 puede ser compartido por hasta tres procesos? Soluci´ on: No. Ejercicio ¿Cu´al o cu´ales de las condiciones de Coffman no se cumple? Recordemos las condiciones de Coffman 1 Exclusi´ on mutua 2 Hold & Wait 3 Sin desalojo 4 Espera circular Mat´ıas Barbeito Soluci´ on: No hay exclusi´on mutua, porque a los efectos del problema R1 puede ser usado por todos los procesos al mismo tiempo. Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso Ejercicio En un sistema hay tres procesos (P1, P2 y P3) y tres recursos (R1, R2, R3). Los tres recursos son de uso exclusivo. Se sabe que P1 requiere los tres recursos, P2 requiere de R1 y R2 y P3 s´olo require R3. 1 ¿El sistema est´a libre de deadlock? 2 ¿P3 influye en que el sistema est´a o no libre de deadlock? 3 Si me aseguro que P2 no podr´a pedir ning´ un recurso hasta que P1 haya liberado todos sus recursos ¿El sistema est´a libre de deadlock? ¿Por qu´e? Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos) Repaso Sincronizaci´ on (Ej. introductorios) Deadlock Repaso La pr´oxima clase: M´as ejercicios de sincronizaci´ on dif´ıciles Mat´ıas Barbeito Sincronizaci´ on entre procesos (aka: sem´ aforos)