|
Algoritmo del Banquero de Dijkstra Asigna peticiones de recursos siempre
que las mismas den como resultado estados seguros. Solicitudes que den como
resultado estados inseguros ser�n negadas hasta que puedan ser satisfechas.
Este algoritmos evita situaciones de Deadlock asignando los recursos en forma
correcta. Las debilidades del algoritmo son: que
requiere que la cantidad de recursos del sistema sea constante, requiere una
cantidad de procesos constante y requiere que los procesos garanticen que los
recursos van a ser devueltos en un intervalo finito de tiempo. Detecci�n y
Recuperaci�n de Deadlocks Algoritmos
de Detecci�n de Deadlock 1.
Cuando hay una �nica ocurrencia de cada recurso.
(variante del grafo de "wait for graph"). Consiste en reducir el
grafo, retirando las aristas que van de recursos a procesos y de procesos a
recursos, colocando nuevas aristas que reflejan la situaci�n de espera entre
procesos. Si el grafo reducido tiene ciclos el sistema esta en Deadlock. Orden de operaciones = n^2 , n = cantidad
de aristas. 2.
�Cuando hay
m�ltiples ocurrencias de cada recurso. Procedure
detecta_deadlock var Disponible:array[1..n] of integer //#
de recursos Usados:array[1..n]
of integer Solicitados:array[1..n]
of integer Finalizado:array[1..n]
of boolean Begin
Work:=Disponibles; For
i:=1..n do if(usados[i]?0) then finish[i]:=false Else
finish[i]:=true; While(encontrar_indice_i
= true) do { Work:=work + usados[i]; Finish[i]:=true;
} If ((finish[i] = false) para algun i), 1=i=n then � El sistema esta en
Deadlock. End
Function encontrar_indice_i : Boolean Begin
If (existe i tal que (Finish[i]=false && solicitados[i] = work) Then
-> true Else -> false End Recuperaci�n
ante Deadlocks 1.Cancelaci�n de procesos a.
Cancelaci�n de todos los procesos involucrados. Esto
resuelve la situaci�n de Deadlock pero tiene un costo muy alto de
reprocesamiento. b.
Cancelacion de un proceso por vez hasta resolver la
situaci�n de Deadlock. La ventaja de esto es que el costo de reprocesamiento
de la informaci�n es menor pero cada vez que se cancela un proceso debe
ejecutarse el algoritmo de detecci�n de deadlock. Los criterios para elegir el candidato
a ser cancelado son: por prioridad, por tiempo de uso de CPU, por cantidad de
recursos utilizados y por cuantos recursos adicionales habr� de utilizar. 2. Obtenci�n de recursos (resourse Preemption). El
sistema operativo selecciona un proceso y le quita los recursos otorgados.
Los criterios para seleccionar el candidato son los mismos que para la
cancelaci�n. El proceso seleccionado se le quitan los recursos y se le lleva
a un estado consistente (Rollback). Algoritmo
de Peterson (o Algoritmo de Dekker) Este algoritmo combina las dos ideas
anteriores. Se comparten una variable flag y una variable turno. Este
algoritmo soluciona el problema de la secci�n cr�tica y evite que un proceso
quede en espera mientras que otro proceso este en su secci�n no cr�tica. Para
n procesos la idea es un poco mas compleja: Flag::array[0..n-1]
Turn::0..n-1 El while se tornara en una evaluaci�n
de n condiciones. Sem�foros Son una herramienta de
sincronizaci�n. Es una variable protegida que solo puede ser modificada por
la rutina de inicializaci�n y por otras dos operaciones at�micas: P( ) <-
wait V( ) <- signal Las operaciones a las cuales se puede acceder son:
Inicializaci�n: Crea un nuevo sem�foro asign�ndole un valor inicial: P(s):
while (s=0) do no_op AT�MICA s:=s-1 V(s): s:=s+1 AT�MICA Existen b�sicamente dos tipos de
sem�foros: 1.
Sem�foros contadores: Toman valores positivos mayores o
iguales a 0. Se utilizan para sincronizaci�n de procesos. 2.
Sem�foros binarios: Toman los valores 0 � 1 y se
utilizan para exclusi�n mutua. A continuaci�n se presenta una soluci�n mediante sem�foros del problema productor/consumidor. #define
N 100 semaphore mutex = 1; semaphore
empty = N; semaphore
full = 0; void
productor(void) {int item; while(1){ produce_item(item); down(empty);
down(mutex);
enter_item(item);
up(mutex);
up(full);} } void
consumidor(void) { int item; while(1){
down(full); down(mutex);
remove_item(&item);
up(mutex);
up(empty);
consume_item(item);}
} En este caso tenemos la utilizaci�n de
3 sem�foros, uno destinado al control de la exclusi�n mutua y los otros dos
destinados a la sincronizaci�n de los procesos para el control de buffer
lleno y vac�o. Podr�amos utilizar sem�foros para un algoritmo de espera
ocupada con n procesos, pero los n procesos que est�n ejecutando el while de
la funci�n P(s) van a la cola de ready en un instante de tiempo reduciendo la
performance general del equipo. Para evitar la espera ocupada se crea un
sem�foro que sea un registro de un nuevo tipo: Sem�foro = Record Valor:Integer L:Lista_de_Procesos End P(s) { s.Valor:= s.valor - 1 if s.Valor < 0 then agregar este
proceso a s.L bloquear; end} V(s) {
s.Valor:=s.Valor + 1 if s.Valor � 0
then quitar un proceso y a s.L despertar(y) } CONCLUSIONES: Este trabajo nos describe
algoritmos como el de Dijkstra el cual evita situaciones de Deadlock asignando los recursos en forma
correcta. Tambien nos ense�a lo que son los sem�foros (una herramienta de
sincronizaci�n) y los tipos que hay de ellos. REFERENCIA: Copias de un
documento dado en clase. |
