sistemas distribuidos - cinvestavvjsosa/clases/sd/...sistemas distribuidos ramiro de santiago lopez....

Sistemas Distribuidos

Ramiro De Santiago Lopez.

Exclusion Mutua: Memoria Compartida.

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)

Algoritmo

ME1. Exclusion Mutua

ME2. Libre de deadlock

ME3. Avance

Memoria Compartida

● Puede ser accedida por múltiples procesos (Pi)

● Comunicacion entre Procesos

Memoria Compartida

P1 P2

P3

P5

P4

Soluciones en el modelo Memoria Soluciones en el modelo Memoria CompartidaCompartida

● 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 p1: bandera[1] = true

while( bandera[1]); while( bandera[0] ); //no hace nada; espera. //no hace nada; espera. // sección crítica // sección crítica // fin de la sección crítica // fin de la sección crítica bandera[0] = false bandera[1] = false

Presencia de interbloqueo.

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 TSinstruction enters its CS

LOAD-LINKED AND STORE-CONDITIONAL

● DEC Alpha introduced the special instructions Load-Linked (LL) and Store-conditional (SC)

● Unlike TS, LL and SC are not atomic RMW operations.

● xx is a shared integer and r is a private integer local to a process

LOAD-LINKED AND STORE-CONDITIONAL

● LL(r, x) is like a machine instruction load (i.e., r := xr := x).

● SC(r, x) is like a machine instruction store (i.e., x := rx := r). If SC succeeds, returning a value 1 into rr, else rr=0;

LOAD-LINKED AND STORE-CONDITIONAL

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.

● Peterson's algorithm. http://en.wikipedia.org/wiki/Peterson's_algorithm.

● EXCLUSION MUTUA. http://www.cs.buap.mx/~mceron/cap4_dis.pdf

● 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 .

● Exclusion Mutua. http://www.webprogramacion.com/44/sistemas-operativos/exclusion-mutua.aspx.

● Sistemas Operativos. Esclusion Mutua. http://sistemaoperativo.wikispaces.com/Exclusion+Mutua

● Bloqueo Mutuo. http://es.wikipedia.org/wiki/Bloqueo_mutuo.

● Sistemas Operativos. http://florysel.blogspot.mx/2012/11/243-interbloqueo-deadlock.html.

● Concepts of Concurrent Computation

● Concepts of Concurrent Computation http://se.inf.ethz.ch/courses/2013a_spring/ccc/lectures/03_synchronization_algorithms.pdf .

● Concepts of Concurrent Computation http://cs.uns.edu.ar/~pmd/sosd/downloads/Material%20Adicional/Slides/04-SincronizacionExtras.pdf .

● Test-and-set. http://en.wikipedia.org/wiki/Test-and-set

● Load-link/store-conditional. http://en.wikipedia.org/wiki/Load-link/store-conditional

● Memoria compartida. http://es.wikipedia.org/wiki/Memoria_compartida.