1. No category

Programación Concurrente y
Tiempo Real
Tema 2. Semáforos y Memoria Compartida
D. Vallejo, M.A. Redondo, C. Villarrubia,
X. Peña, C. González, J. Ruiz
Escuela Superior de Informática
Universidad de Castilla-La Mancha
Curso 2014/2015
Grado en Ingeniería Informática
Tema 2. Semáforos y Memoria Compartida
Tema 2. Semáforos y Memoria Compartida
1. Conceptos básicos [Silber 6.5]
1. Conceptos básicos [Silber 6.5]
2. Problemas clásicos de sincronización
2. Problemas clásicos de sincronización
[Downey 4, 5]
[Downey 4, 5]
3. Patrones de sincronización básicos
3. Patrones de sincronización básicos
[Downey 3]
[Downey 3]
Curso 2014/2015
Grado en Ingeniería Informática
Curso 2014/2015
Grado en Ingeniería Informática
Conceptos | Problemas | Patrones
Semáforos. ¿Qué, cómo y por qué?
p1: proceso
p1: proceso
1
5
3
cr eación
[inicialización]
wait
[p1 bloqueado]
sem (1)
sem (0)
2
wa it
[decremento]
p2: proceso
Conceptos | Problemas | Patrones
Ejemplo de sincronización
p1: proceso
P1
r1
[p1 desbloqueado]
r2
sem (-1)
sem (0)
r3
4
sig nal
[incremento]
p2: proceso
a
P2
P3
P1
s1
t1
s2
b
s3
c
d
t2
t3
r4
s4
t4
r5
s5
t5
P2
P3
r1
s1
t1
r2
S(a)
t2
W(a)
s2
S(c)
r3
W(c)
t3
S(b)
s3
S(d)
r4
W(b)
t4
r5
W(d)
t5
s4
s5
T2 – Semáforos y Memoria Compartida
Trp 4
T2 – Semáforos y Memoria Compartida
Trp 5
Conceptos | Problemas | Patrones
Tema 2. Semáforos y Memoria Compartida
1. Conceptos básicos [Silber 6.5]
El buffer limitado
while (1) {
// Produce en nextP.
wait (empty);
wait (mutex);
// Guarda nextP en buffer.
signal (mutex);
signal (full);
while (1) {
}
wait (full);
2. Problemas clásicos de sincronización
[Downey 4, 5]
3. Patrones de sincronización básicos
[Downey 3]
wait (mutex);
// Rellenar nextC.
signal (mutex);
signal (empty);
// Consume nextC.
}
Curso 2014/2015
Grado en Ingeniería Informática
T2 – Semáforos y Memoria Compartida
Trp 7
Conceptos | Problemas | Patrones
Lectores y escritores
Conceptos | Problemas | Patrones
El puente de un solo carril
Proceso lector
Proceso escritor
wait(mutex);
num_lectores++;
if num_lectores == 1 then
wait(acceso_esc);
signal(mutex);
// SC: Lectura
// ...
wait(mutex);
num_lectores--;
if num_lectores == 0 then
signal(acceso_esc);
signal(mutex);
wait(acceso_esc);
// SC: Escritura
// ...
signal(acceso_esc);
Norte
Sur
T2 – Semáforos y Memoria Compartida
Trp 8
T2 – Semáforos y Memoria Compartida
Trp 9
Conceptos | Problemas | Patrones
Filósofos comensales
Conceptos | Problemas | Patrones
Filósofos comensales (sin deadlock)
Proceso filósofo i
#define N 5
#define IZQ (i-1) % 5
#define DER (i+1) % 5
Proceso filósofo
while (1) {
// Pensar...
wait(palillos[i]);
wait(palillos[(i+1) % 5]);
// Comer...
signal(palillos[i]);
signal(palillos[(i+1) % 5]);
}
T2 – Semáforos y Memoria Compartida
void coger_palillos (int i) {
wait(mutex);
estado[i] = HAMBRIENTO;
prueba(i);
signal(mutex);
wait(sem[i]);
}
int estado[N];
sem_t mutex;
sem_t sem[N];
void filosofo (int i) {
while (1) {
pensar();
coger_palillos(i);
comer();
dejar_palillos(i);
}
}
Trp 10
void dejar_palillos (int i) {
wait(mutex);
estado[i] = PENSANDO;
prueba(i - 1);
prueba(i + 1);
signal(mutex)
}
T2 – Semáforos y Memoria Compartida
Trp 11
Conceptos | Problemas | Patrones
El barbero dormilón
Consejos útiles
Proceso cliente
Proceso barbero
1. si
1.1
2. si
2.1
2.2
2.3
2.4
2.5
2.6
2.7
1.
2.
3.
4.
5.
no sillas libres,
marcharse
hay sillas libres,
sentarse
esperar sillón
levantarse silla
ocupar sillón
despertar barbero
esperar fin
levantarse sillón
T2 – Semáforos y Memoria Compartida
Conceptos | Problemas | Patrones
dormir
despertar
cortar
notificar fin
volver a 1
1
Identificación
de procesos
2
Identificación
de clases
3
Identificación de
recursos compartidos
4
Identificación de
eventos de sincronización
Trp 12
T2 – Semáforos y Memoria Compartida
5
Implementación
Trp 13
Conceptos | Problemas | Patrones
El problema de los caníbales
?
Conceptos | Problemas | Patrones
La Navidad y Santa Claus
?
?
?
?
T2 – Semáforos y Memoria Compartida
Trp 14
T2 – Semáforos y Memoria Compartida
Trp 15
Conceptos | Problemas | Patrones
Tema 2. Semáforos y Memoria Compartida
1. Conceptos básicos [Silber 6.5]
Reutilizando conocimiento...
Señalización (signaling)
2. Problemas clásicos de sincronización
[Downey 4, 5]
Proceso A
Proceso B
sentencia a1
signal(sem);
wait(sem);
sentencia b1;
3. Patrones de sincronización básicos
[Downey 3]
Rendezvous
Curso 2014/2015
Grado en Ingeniería Informática
Proceso A
Proceso B
sentencia a1
sentencia a2
sentencia b1;
sentencia b2;
T2 – Semáforos y Memoria Compartida
Conceptos | Problemas | Patrones
Reutilizando conocimiento...
Trp 17
Conceptos | Problemas | Patrones
Reutilizando conocimiento...
Mutex
Exclusión mutua categórica
Proceso A
Proceso B
wait(mutex);
// Sección crítica
cont = cont + 1;
signal(mutex);
wait(mutex);
// Sección crítica
cont = cont + 1;
signal(mutex);
Marcador (scoreboard)
Interruptor (lightswicht)
Barrera (barrier)
Cola FIFO (FIFO queue)
Multiplex
wait(multiplex);
// Sección crítica
signal(multiplex);
T2 – Semáforos y Memoria Compartida
Trp 18
T2 – Semáforos y Memoria Compartida
Trp 19