Exclusion Mutua: Memoria Compartida. Ramiro De Santiago Lopez. 28/01/2014
Exclusion Mutua (ME) ●
●
Un proceso excluye temporalmente a todos los demás para usar un recurso compartido. Sección Crítica (CS).
Exclusion Mutua (ME) ME1. Exclusion Mutua
ME2. Libre de deadlock
ME3. Avance Algoritmo
Memoria Compartida ●
●
Puede ser accedida por múltiples procesos (Pi)
P2
P1
Memoria Compartida
Comunicacion entre Procesos
P5 P3 P4
Soluciones en el modelo Memoria Compartida ●
El matemático holandés Dekker fue el primero en proponer una solución a la exclusión mutua.
●
Operaciones atomicas de escritura-lectura.
●
Desarrollo 5 versiones de su algoritmo.
●
La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4
Primera Solucion Algoritmo para dos procesos bandera[0] = false bandera[1] = false p0: bandera[0] = true while( bandera[1]); //no hace nada; espera. // sección crítica // fin de la sección crítica bandera[0] = false
Presencia de interbloqueo.
p1: bandera[1] = true while( bandera[0] ); //no hace nada; espera. // sección crítica // fin de la sección crítica bandera[1] = false
PETERSON’S ALGORITHM
Preba de no deadlock (ME2) (por contradiccion). (flag[1] ∧ turn = 1) ∧ (flag[0] ∧ turn = 0) pero, (turn = 1) ∧ (turn = 0) = false Por lo tanto deadlock es imposible.
PETERSON’S ALGORITHM
Preba de Exclusion Mutua (ME1). Supongamos que p0 esta en la Seccion Critica. P1 tiene que esperar a que p0 termine la seccion critica
PETERSON’S ALGORITHM
Preba de Avance(ME3). Supongamos que p0 esta en la Seccion Critica. p1 esta en espera para entrar en la CS Eventualmente, p0 saldra de la CS y pondra flag[0] = false dando la oportunidad a p1 de entrar en la CS
EXCLUSION MUTUA USANDO INSTRUCCIONES ESPECIALES
TEST-AND-SET TS(r, x) ●
●
TS(r, x) es una operacion atomica definida como r := x; x := 1; Instrucciones de este tipo son conocidas como instrucciones read–modify–write (RMW).
TEST-AND-SET TS(r, x) ●
Using TS, the mutual exclusion problem can be solved for N processes (N > 1) as follows.
All TS operations are serialized, the first process that executes the TS instruction enters its CS
LOAD-LINKED AND STORECONDITIONAL ●
●
●
DEC Alpha introduced the special instructions LoadLinked (LL) and Storeconditional (SC) Unlike TS, LL and SC are not atomic RMW operations. x is a shared integer and r is a private integer local to a process
LOAD-LINKED AND STORECONDITIONAL ●
●
LL(r, x) is like a machine instruction load (i.e., r := x). x SC(r, x) is like a machine instruction store (i.e., x := r). r If SC succeeds, returning a value 1 into r, else r=0;
LOAD-LINKED AND STORECONDITIONAL
THE GROUP MUTUAL EXCLUSION PROBLEM ●
●
●
●
Instead of trying to enter their individual critical sections, processes opt to join distinct forums. In any time at most one forum should be in session. Any number of processes should be able to join the forum at a time. An example is that of a movie theater.
THE GROUP MUTUAL EXCLUSION PROBLEM ●
Is a combination of the classical mutual exclusion problem and the readers and writers problem.
Referencias ●
Distributed Systems: An Algorithmic Approach.Sukumar Ghos. Chapman & Hall/CRC, Taylor & Francis Group, LLC (2007). Ch7.
Gestión de Procesos. http://www.infor.uva.es/~fjgonzalez/apuntes_aso/Tema1.pdf. http://in.unsaac.edu.pe/~ecarrasco/sistOp/presentaciones/Cap05-Concurrencia.pdf.