Repaso
Sincronización (Ej. introductorios)
Deadlock
Sincronización entre procesos
(aka: semáforos)
Ignacio Vissani ) Pablo del Sel
DC - FCEyN - UBA
Sistemas Operativos, 1c-2011
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Primero repasemos un poco lo que vieron en la teórica.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Primero repasemos un poco lo que vieron en la teórica.
Qué es una race condition?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Primero repasemos un poco lo que vieron en la teórica.
Qué es una race condition?
Defecto en un proceso, donde el resultado del mismo depende
inesperadamente o crı́ticamente del orden en que se ejecuten
ciertos eventos.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Cuál es el output de los siguientes procesos A y B corriendo
simultáneamente y con memoria compartida?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Cuál es el output de los siguientes procesos A y B corriendo
simultáneamente y con memoria compartida?
A B
x = 1; x = 4;
print(x);
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Cuál es el output de los siguientes procesos A y B corriendo
simultáneamente y con memoria compartida?
x comienza inicializado en 0.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Cuál es el output de los siguientes procesos A y B corriendo
simultáneamente y con memoria compartida?
x comienza inicializado en 0.
A B
x = x + 1; x = x + 1;
print(x);
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Qué es un semáforo?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Qué es un semáforo?
Es una variable (o tipo abstracto de datos) que permite
controlar el acceso de múltiples procesos a un recurso común
en un ambiente de programación paralela.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Qué es un semáforo?
Es una variable (o tipo abstracto de datos) que permite
controlar el acceso de múltiples procesos a un recurso común
en un ambiente de programación paralela.
Es lo mismo que usar un entero y fijarme qué valor tiene?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Qué es un semáforo?
Es una variable (o tipo abstracto de datos) que permite
controlar el acceso de múltiples procesos a un recurso común
en un ambiente de programación paralela.
Es lo mismo que usar un entero y fijarme qué valor tiene?
No, es escencial que las primitivas sobre semáforos sean
atómicas.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Recordemos cuáles son las primitivas:
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Recordemos cuáles son las primitivas:
Primitivas
sem_create(int value): Devuelve un nuevo semáforo
inicializado en value. (Otras formas: Semaphore(value),
new Semaphore(value), etc.)
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Recordemos cuáles son las primitivas:
Primitivas
sem_create(int value): Devuelve un nuevo semáforo
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),
[Link](), etc.)
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Race condition
Sincronización (Ej. introductorios)
Semáforos
Deadlock
Recordemos cuáles son las primitivas:
Primitivas
sem_create(int value): Devuelve un nuevo semáforo
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),
[Link](), etc.)
sem_signal(semaphore sem, [int n = 1]): Incrementa
en uno el valor del semáforo sem y despierta a alguno1 de los
procesos que están esperando en ese semáforo. (Otras formas:
signal(sem, [n]), V(sem), [Link]([n]), etc.)
1
En general las bibliotecas de semáforos no garantizan en qué orden se
despertará a los procesos que están esperando en un semáforo.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
Se tienen 3 procesos A, B y C. Construya el código con semáforos de
manera tal que la secuencia sea ABC,ABC,ABC,. . .
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
Se tienen 3 procesos A, B y C. Construya el código con semáforos de
manera tal que la secuencia sea ABC,ABC,ABC,. . .
Solución:
Uso 3 semáforos, sem A, sem B y sem C. Sus valores de inicializacián
son:
sem A = 1, sem B = 0, sem C = 0
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
Se tienen 3 procesos A, B y C. Construya el código con semáforos de
manera tal que la secuencia sea ABC,ABC,ABC,. . .
Solución:
Uso 3 semáforos, sem A, sem B y sem C. Sus valores de inicializacián
son:
sem A = 1, sem B = 0, sem C = 0
P(sem A) P(sem B) P(sem C)
// Algo // Algo // Algo
V(sem B) V(sem C) V(sem A)
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
¿Y si quiero que la secuencia sea BCA,BCA,BCA,. . .?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
¿Y si quiero que la secuencia sea BCA,BCA,BCA,. . .?
Solución:
Cambio los valores de inicialización de los semáforos por
sem A = 0, sem B = 1, sem C = 0
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
¿Y si quiero que la secuencia sea BBCA,BBCA,BBCA,. . .?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
¿Y si quiero que la secuencia sea BBCA,BBCA,BBCA,. . .?
Solución:
Uso 3 semáforos, sem A, sem B y sem C. Sus valores de inicialización
son:
sem A = 0, sem B = 2, sem C = 0
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
¿Y si quiero que la secuencia sea BBCA,BBCA,BBCA,. . .?
Solución:
Uso 3 semáforos, sem A, sem B y sem C. Sus valores de inicialización
son:
sem A = 0, sem B = 2, sem C = 0
P(sem A) P(sem B) P(sem C)
// Algo // Algo P(sem C)
V(sem B) V(sem C) // Algo
V(sem B) V(sem A)
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
Se tienen N procesos, P0 , P1 , ..., PN 1 (donde N es un parámetro). Se los
quiere sincronizar de manera que la secuencia de ejecución sea
Pi , Pi+1 , ..., PN 1 , P0 , ..., Pi 1
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
Ejercicio
Se tienen N procesos, P0 , P1 , ..., PN 1 (donde N es un parámetro). Se los
quiere sincronizar de manera que la secuencia de ejecución sea
Pi , Pi+1 , ..., PN 1 , P0 , ..., Pi 1
Solución:
Global En cada Pi
Semaphore semaforos[N]; P(semaforos[i])
for(int j = 0; j < N; j++) // Algo
semaforos[j] = Semaphore(0); V(semaforos[i+1])
semaforos[i] = Semaphore(1);
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
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és de que se hayan ejecutado todos los ai
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
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és de que se hayan ejecutado todos los ai
Solución:
Global y en cada Pi ...
mutex = Semaphore(1); ai ();
cuantosLlegaron = 0; [Link]();
barrera = Semaphore(0); cuantosLlegaron++;
[Link]();
if (cuantosLlegaron == N)
[Link]();
[Link]();
bi ();
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
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és de que se hayan ejecutado todos los ai
Solución:
Global y en cada Pi ...
mutex = Semaphore(1); ai ();
cuantosLlegaron = 0; [Link]();
barrera = Semaphore(0); cuantosLlegaron++;
[Link]();
¿Esta solución es correcta? if (cuantosLlegaron == N)
[Link]();
[Link]();
bi ();
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
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és de que se hayan ejecutado todos los ai
Solución:
Global y en cada Pi ...
mutex = Semaphore(1); ai ();
cuantosLlegaron = 0; [Link]();
barrera = Semaphore(0); cuantosLlegaron++;
[Link]();
¿Esta solución es correcta? if (cuantosLlegaron == N)
La “solución” aquı́ presentada [Link]();
tiene deadlock2
[Link]();
bi ();
2
Más sobre deadlock en un ratito
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
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ódigo de sincronización de cada uno de
los procesos para asegurar que el acceso respeta la polı́tica adoptada.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Cantidad de procesos estática
Sincronización (Ej. introductorios)
Cantidad de procesos dinámica
Deadlock
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ódigo de sincronización de cada uno de
los procesos para asegurar que el acceso respeta la polı́tica adoptada.
Tip para la solución
Usar una cola :)
Tip para la solución 2
Hay que garantizar acceso exclusivo a la cola.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Deadlock
So it begins, the great battle of our time.
Un ejemplo tı́pico de deadlock es
P1 P2
[Link](); [Link]();
[Link](); [Link]();
// Sección crı́tica // Sección crı́tica
[Link](); [Link]();
[Link](); [Link]();
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Ejercicio
En un sistema conviven 3 procesos y 2 recursos. Uno de los
recursos (R2) es de uso exclusivo y el otro (R1) puede ser
compartido por hasta dos procesos. ¿Puede haber deadlock?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Ejercicio
En un sistema conviven 3 procesos y 2 recursos. Uno de los
recursos (R2) es de uso exclusivo y el otro (R1) puede ser
compartido por hasta dos procesos. ¿Puede haber deadlock?
Solución:
Sı́.
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Ejercicio
¿Y si ahora R1 puede ser compartido por hasta tres procesos?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Ejercicio
¿Y si ahora R1 puede ser compartido por hasta tres procesos?
Solución:
No.
Ejercicio
¿Cuál o cuáles de las condiciones de Co↵man no se cumple?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Ejercicio
¿Y si ahora R1 puede ser compartido por hasta tres procesos?
Solución:
No.
Ejercicio
¿Cuál o cuáles de las condiciones de Co↵man no se cumple?
Recordemos las condiciones de
Co↵man
1 Exclusión mutua
2 Hold & Wait
3 Sin desalojo
4 Espera circular
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
Ejercicio
¿Y si ahora R1 puede ser compartido por hasta tres procesos?
Solución:
No.
Ejercicio
¿Cuál o cuáles de las condiciones de Co↵man no se cumple?
Solución:
Recordemos las condiciones de Al no haber exclusión mutua
Co↵man en el recurso R1 no se puede
1 Exclusión mutua generar una espera circular.
2 Hold & Wait Solamente puede haber espera
3 Sin desalojo por el recurso R2.
4 Espera circular
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)
Repaso
Sincronización (Ej. introductorios)
Deadlock
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ólo require
R3.
1 ¿El sistema está libre de deadlock?
2 ¿P3 influye en que el sistema está o no libre de deadlock?
3 Si me aseguro que P2 no podrá pedir ningún recurso hasta
que P1 haya liberado todos sus recursos ¿El sistema está libre
de deadlock? ¿Por qué?
Ignacio Vissani ) Pablo del Sel Sincronización entre procesos (aka: semáforos)