? En la mayoría de las aplicaciones es necesario regular el acceso y uso de las variables compartidas
? Se necesitan accesos atómicos de tipo RMW
(2) Sincronización de proc.
(Gp:) …
LD R1,CONT
ADDI R1,R1,#1
ST CONT,R1
…
(Gp:) Pi
(Gp:) …
LD R1,CONT
ADDI R1,R1,#1
ST CONT,R1
…
(Gp:) Pj
LD..ADDI…….ST
LD….ADDI…..ST
CONT = 1!!!
? Dos tipos básicos:
– control de acceso a secciones críticas
trozos de código que se ejecutan en estricta exclusión mutua (sólo un procesador cada vez)
– sincronización entre procesos
modelo productor / consumidor:
1 a 1 ? eventos
global ? barreras
Sincronización
? Variables “cerrojo” (abierto/cerrado) para asegurar el acceso secuencial a la sección crítica.
? Dos funciones para controlar el acceso a la sección crítica:
(Gp:) …
k := k + 1;
…
(Gp:) sección crítica
(Gp:) LOCK(A);
(Gp:) UNLOCK(A);
(Gp:) A: cerrojo
Secciones críticas
? Operaciones atómicas de lectura/escritura sobre el cerrojo.
Ejemplo: Test&Set R1,A ? R1 := M(A); A := 1;
? En un entorno SMP, limitar el tráfico es crucial.
La instrucción Test&Set efectúa siempre una escritura, esté el cerrojo abierto o cerrado, y por tanto invalida el bloque en todas las caches ? genera mucho tráfico.
Secciones críticas
lock: T&S R1,A
BNZ R1,lock
RET
unlock: ST A,R0
RET
Soluciones para reducir el tráfico:
? Test-and-Test&Set
primero mirar y luego intentar entrar
? Temporizaciones entre intentos de entrada
Secciones críticas
lock: LD R1,A
BNZ R1,lock
T&S R1,A
BNZ R1,lock
RET
Soluciones para reducir el tráfico:
? Load Linked / Store Conditional
Dividir la operación atómica R(M)W en dos operaciones especiales, una de lectura (LL) y una de escritura (SC), que operan junto con un flag hardware.
Secciones críticas
lock: ADDI R2,R0,#1
l1: LL R1,A
BNZ R1,l1
…
SC A,R2
BZ R2,lock
RET
unlock: ST A,R0
RET
Soluciones para reducir el tráfico:
? Tickets
Una variable global ordena la entrada a la sección crítica
? Vector de eventos
La entrada a la sección crítica se ordena mediante un vector. Cada proceso va dando paso al siguiente.
Secciones críticas
? Eventos: Sincronización habitual entre productor y consumidor.
Sincronización: eventos
P1 (productor) P2 (consumidor)
X = F1(Z);
Y = F2(X);
post(A); wait(A);
(Gp:) while (A == 0) {};
(Gp:) A = 1;
post(A,i); wait(A,i);
? Sincronización global en base a barreras:
flag + contador
BARRERA (BAR, P)
{ bit_sal = !(bit_sal);
LOCK (BAR.lock);
BAR.cont++;
mi_cont = BAR.cont;
UNLOCK (BAR.lock)
if (mi_cont==P) {
BAR.cont = 0;
BAR.flag = bit_sal;
}
else
while (BAR.flag != bit_sal) {};
}
Sincronización: barreras
? Orden de ejecución de las instrucciones (mem.)
? El problema del orden de ejecución de las instruccio-nes de memoria se conoce como consistencia (visión global del sistema de memoria).
? N procesadores ? no se sabe en qué orden se ejecuta el programa global
? 1 procesador ? el hardware (desorden/desorden) pero sólo hay una unidad de control (se “sabe” lo que se hace).
(3) Consistencia de la mem.
? La coherencia de los datos también hace referencia al “orden”, pero de una manera más limitada. Indica que los cambios en una determinada variable se reflejarán, en algún momento, en todos los procesadores en el mismo orden.
? Pero nada indica sobre el orden relativo de cambios en variables diferentes!
Consistencia de la mem.
? La semántica de un programa paralelo está íntimamente ligada al orden local y al orden global.
? Ejemplo (A=B=0):
P1 P2
A = 1; (wr) print B; (rd)
B = 2; (wr) print A; (rd)
Resultados posibles
B,A ? 0,0 / 0,1 / 2,1 2,0 ??
? 2,0 es un resultado posible si P2 decide desordenar sus dos instrucciones, que para él son totalmente independientes!
Consistencia: orden de ej.
? La semántica del programa paralelo se suele asegurar mediante operaciones de sincronización.
? Ejemplo (A=flag=0):
P1 P2
A = 1; while (flag==0);
flag = 1; print A;
(Gp:) dependencias
wr1 rd1
wr2 rd2
? Pero P2 puede decidir ejecutar primero rd2, porque para él no hay dependencia alguna con la instrucción anterior:
el procesador local no “entiende” la sincronización del programa global!
(Gp:) ¿debería escribir P2 A=1?
Consistencia: orden de ej.
? La semántica del programa paralelo se suele asegurar mediante operaciones de sincronización.
? Ejemplo (A=flag=0):
P1 P2
A = 1; while (flag==0);
flag = 1; print A;
(Gp:) dependencias
wr1 rd1
wr2 rd2
(Gp:) ¿debería escribir P2 A=1?
? Sólo se respeta la dependencia wr1 ? rd2 (A) si se respeta el orden local:
wr1 >> wr2 y rd1 >> rd2 +
wr2 ? rd1
entonces wr1 ? rd2
Consistencia: orden de ej.
? Incluso manteniendo el orden local, la no atomicidad de las operaciones de actualización da lugar a problemas.
? Ejemplo (A=flag=0):
P1 P2
A = 1; while (flag==0);
flag = 1; print A;
(Gp:) El mantenimiento de la coherencia indica que los cambios sobre una variable se ven en el mismo orden en todos los procesadores, pero no indica nada sobre el orden de los cambios en diferentes variables.
Puede imprimir A = 0 si P2 ve el cambio en flag antes que el cambio en A.
Consistencia: atomicidad
? Otro ejemplo (A = B = 0)
P1 P2 P3
A = 1; while (A==0);
B = 1; while (B==0);
C = A;
(Gp:) finalmente, obtenemos C = 0
Consistencia: atomicidad
? El programador de sistemas paralelos necesita saber cuál es el modelo de consistencia que se aplica, es decir, qué tipo de restricciones existen sobre el orden de ejecución de las instrucciones en cada procesador y sobre la atomicidad global de las operaciones de escritura/lectura sobre variables compartidas.
Veamos los modelos principales.
Consistencia: modelos
? Extensión del modelo de orden estricto en un solo procesador.
? Un multiprocesador mantiene consistencia secuen-cial si mantiene el orden local de las instrucciones en cada procesador y si el orden global de las instrucciones corresponde a un determinado entrelazado de las instrucciones de cada procesador.
Consistencia secuencial
? Mantener orden global implica no poder ejecutar ninguna operación de memoria en ningún procesador hasta que no termine completamente la anterior operación iniciada en cualquier procesador y todas sus consecuencias.
Se necesita, además, que las operaciones de memoria sean todas atómicas.
Consistencia secuencial
? El conjunto de restricciones de la CS es un conjunto suficiente, pero no necesario, por lo que es posible relajar alguna de las condiciones anteriores:
+ orden: rd >> rd rd >> wr wr >> rd wr >> wr
+ atomicidad
? Pero tiene que ser posible imponer en ciertos casos el orden estricto, instrucciones tipo fence.
Consistencia relajada
Consistencia: resumen
Consistencia: resumen
(Gp:) orden
 Página anterior | Volver al principio del trabajo | Página siguiente  |