testas

Tema 2: El problema de la exclusion mutua

1

Introducci´n hist´rica al problema
o
o

Aunque siempre han existido soluciones de bajo nivel para resolver este problema, p.e. los
cerrojos; sin embargo, se han venido estudiando desde 1965 una serie de soluciones-software para
resolverlo. Dichas soluciones pretenden ser independientes de las instrucciones de una m´quina
a
concreta ypermiten asegurar que los procesos cumplen todas las propiedades exigidas a un
programa concurrente. Se intenta conseguir, fundamentalmente, soluciones que proporcionen
un acceso equitativo de los procesos a la secci´n cr´
o
ıtica. S´lo vamos a considerar soluciones al
o
problema de la exclusi´n mutua que utilicen las instrucciones b´sicas de lectura o escritura del
o
a
valor de una variable.Los algoritmos que se van a introducir a continucai´n representan una muestra cronol´gica
o
o
de las propuestas de soluci´n del problema de la exclusi´n mutua y tienen un indudable valor
o
o
pedag´gico para la comprensi´n de conceptos b´sicos de la Programaci´n Concurrente.
o
o
a
o
En la actualidad vuelve a tener inter´s la investigaci´n de estos algoritmos, ya que con
e
o
lasnuevas arquitecturas distribuidas es necesario encontrar versiones descentralizadas de los
algoritmos cl´sicos que necesitan de un sistema con memoria com´n para su programaci´n.
a
u
o
Los algoritmos para resolver el problema de la exclusi´n mutua se dividen en:
o
1. Centralizados: utilizan variables compartidas entre los procesos que expresan el estado de
los procesos ( se suele acceder aestas variables en los protocolos de adquisici´n y restio
tuci´n, que ejecutan los procesos antes y despu´s de la secci´n cr´
o
e
o
ıtica, respectivamente)
2. Distribuidos: no utilizan variables compartidas entre los procesos. Suelen utilizar instrucciones de paso de mensajes.

2

Soluci´n al problema con espera ocupada
o

La espera activa consiste en que los procesos esperan a la entradade la secci´n cr´
o
ıtica hasta
que su continuaci´n sea segura.
o
Este tipo de implementaci´n utiliza recursos (tiempo del procesador en sistemas monoo
procesador y ciclos de memoria en sistemas multiprocesador) sin realizar ning´n avance en el
u
1

2
proceso que espera. Se puede considerar una soluci´n aceptable, siempre que el sistema no
o
tenga muchos procesos.
Se podr´ pensaren una soluci´n al problema de la exclusi´n mutua que utiliza una variable
ıa
o
o
l´gica mutex que cambia al valor cierto cuando un proceso est´ en la secci´n cr´
o
a
o
ıtica y a falso
cuando no hay ning´n proceso en secci´n cr´
u
o
ıtica:
var mutex: boolean:= false;
procedure ProtocoloAdquisicion;
begin
while mutex do
nothing;
enddo;
mutex:= true;
end;
procedureProtocoloRestitucion;
begin
mutex:= false;
end;
P1
P2
---------------ProtocoloAdquisicion;
ProtocoloAdquisicion;
S.C.
S.C.
ProtocoloRestitucion;
ProtocoloRestitucion;

La soluci´n anterior no cumple la propiedad de seguridad. Ya que los 2 procesos pueden
o
entrar a ejecutar simult´neamente el protocolo de adquisici´n, pasar ambos la condici´n del
a
o
o
bucle y entrar en secci´n cr´
o
ıtica.3

El Algoritmo de Dekker

3

Condiciones que ha de verificar una soluci´n correcta
o
al problema

El problema de la exclusi´n mutua para 2 procesos fue definitivamente resuelto por Dekker
o
en 1965. Como al principio es un algoritmo dif´ de entender, Dijkstra estableci´ un m´todo
ıcil
o
e
para obtenerlo y las condiciones que cualquier otra soluci´n al problema de la exclusi´nmutua
o
o
deber´ cumplir para ser aceptada como tal. Las condiciones de Dijkstra son:
ıa
1. No hacer ninguna suposici´n acerca de las instrucciones o n´mero de procesos soportados
o
u
por la m´quina. S´lo podemos utilizar las instrucciones b´sicas, tales como leer, escribir
a
o
a
o comprobar una posici´n de memoria para resolver el problema. Adem´s, supondremos
o
a
que son...