miércoles, 28 de noviembre de 2012

2.4.3.2 Detección.

Detectar y actuar

Se implementa un proceso adicional que vigila si los demás forman una cadena circular.
Más preciso, se define el grafo de asignación de recursos:
  • Los procesos y los recursos representan los nodos de un grafo.
  • Se añade cada vez una arista entre un nodo tipo recurso y un nodo tipo proceso cuando el proceso ha obtenido acceso exclusivo al recurso.
  • Se añade cada vez una arista entre un nodo tipo recurso y un nodo tipo proceso cuando el proceso está pidiendo acceso exclusivo al recurso.
  • Se eliminan las aristas entre proceso y recurso y al revés cuando el proceso ya no usa el recurso.
Cuando se detecta en el grafo resultante un ciclo, es decir, cuando ya no forma un grafo acíclico, se ha producido una posible situación de un bloqueo.
Se puede reaccionar de dos maneras si se ha encontrado un ciclo:
  • No se da permiso al último proceso de obtener el recurso.
  • Sí se da permiso, pero una vez detectado el ciclo se aborta todos o algunos de los procesos involucrados.
Sin embargo, las técnicas pueden dar como resultado que el programa no avance, incluso, el programa se puede quedar atrapado haciendo trabajo inútil: crear situaciones de bloqueo y abortar procesos continuamente.


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

Detección de deadlock

  • La evitacíon de deadlock tiene un costo porque todos los estados inseguros no son estados de deadlock. Esto implica que hay tiempos cuando algunos procesos tienen que esperar y recursos están desocupados sin que es necesario.
  • El sistema operativo puede chequear de vez en cuando si hay un deadlock. ¿Cuán frecuentemente debieramos chequear si hay deadlock?
    • El costo de algoritmo vs. el número de procesos en deadlock.
    • Saber quien creó el deadlock.
    • ¶ Cuando la utilización de la CPU es baja.
  • Tenemos que eliminar los deadlocks que encontramos. Posibilidades:
    • Abortar todos los procesos en deadlock. ¡Esto es un método común!
    • Abortar procesos uno a la vez hasta que no haya deadlock.
    • Retroceder los procesos a algún punto y reiniciar. El deadlock puede reocurrir.
    • Expropiar recursos de procesos hasta que no haya deadlock. Retrocedemos los procesos expropiados.
  •  
  • Tenemos que seleccionar un proceso para abortar o retroceder. Factores:
    • La prioridad
    • El tiempo que el proceso ha corrido
    • El número y tipo de los recursos adquiridos
    • La clase de proceso (batch o interactiva)
  • La starvation es un problema.

Detección y Recuperación.

            Es el hecho de determinar si existe o no un Dead Lock, e identificar cuales son los procesos y recursos implicados en él. El uso de algoritmos de detección de interbloqueo implica una sobrecarga en el tiempo de ejecución. Para ser correcto, un algoritmo de detección de interbloqueo debe de cumplir dos criterios:

            1) Debe detectar todos los dead lock´s   existentes en un tiempo finito.

            2) No debe reportar "falsos" Dead Lock's.

Grafo de asignación de recursos.
            Los Dead Lock pueden describirse con mayor precisión en función de un grafo dirigido llamado grafo de asignación de recursos, que consiste en un conjunto de vértices V y aristas A. El conjunto de vértices V se divide en dos tipos, P = {P1,P2, ... , Pn}, el conjunto formado por  todos los procesos del sistema,  y   R ={R1,R2, ... ,Rn}, el conjunto integrado por todos los tipos de recursos del sistema.


Representación mediante grafos del estado del sistema.

            El estado de un sistema es dinámico; esto es,  los procesos del sistema toman y liberan recursos continuamente.  La  representación del dead lock requiere la representación del estado  de la interacción  procesos - recursos, la representación se hace mediante un grafo dirigido que se conoce como gráfica de asignación de recursos .

En los sistemas de bases de datos distribuidos (DDBS) está representación se conoce como gráfica de espera de transacción (Transaction Wait-For TWF).

            Los dead lock`s pueden describirse con mayor precisión en función de un grafo dirigido llamado grafo de asignación de recursos.
La simbologia es la siguiente .  a, b, c y d.

  Gráfica de asignación y petición de recursos  

La técnica para la reducción de gráficas implica las consideraciones siguientes:

*          Si las peticiones de recursos de un proceso piden ser concedidas, entonces la gráfica puede
            ser reducida.
*          La reducción de una gráfica consiste en retirar las flechas que van de los recursos a los procesos y retirar las flechas que van del proceso al recurso.
*          Si una gráfica puede ser reducida para todos sus procesos entonces no hay dead lock.
*          Si una gráfica no puede ser reducida para todos sus procesos, entonces los procesos
irreducibles constituyen la serie de procesos interbloqueados de la gráfica.
*          Detección de interbloqueo mediante grafos.

Un grafo G consiste de un conjunto finito no vacío.

V = C(G)   de:     P puntos (vértices) conjunto X de q parejas desordenadas de puntos de V(aristas).
           
            cada par X = {U,V} de puntos en X y una línea de G  por lo tanto X = UV.
            Un grafo de p puntos y q líneas se denomina un grafo (p,q), el grafo (1,0) es trivial.

            Petición  =   Proceso - Recurso
                                            Pi

            Rx             Ry            El proceso Pi tiene el recurso Rx y solicita el recurso Ry.

            Para determinar si existe un ciclo en un grafo se puede usar la representación matricial del grafo dirigido. Dado que se tienen parejas ordenadas {Rx, Ry}, la matriz se construye colocando un 1 en la diagonal en (x,x) y (y,y) y un 1 en la posición (x,y) de la matriz.  .  
  Reducción de la matriz del grafo.

Reducción de la matriz de un grafo correspondiente. No existen vértices terminales; los vértices 1 y 2 son iniciales y pueden ser eliminados; existe un Inter bloqueo.



    



  Representación vectorial
Un vértice terminal sólo aparece en la columna requiere y un vértice inicial sólo aparece en la columna Tiene. Para reducir esta representación se recorren de arriba a abajo los vectores y se buscan los vértices terminales e iniciales y se elimina su renglón.
            El proceso se repite hasta:
            1) No existen renglones o
            2) No se pueden eliminar renglones.
           
            Si no se pueden eliminar renglones las transiciones producen un Dead Lock.

            Para el grafo de la  en el primer paso se eliminan los procesos P1 (vértice inicial), P2 y P3 (vértice terminal). En el segundo paso se elimina el proceso P4 (vértice terminal),  inicial.

            Para el grafo de la el primero se eliminan los procesos P1,P2,P3 (vértices iniciales), P4(vértice inicial al eliminar el proceso P1), Los procesos restantes no pueden ser eliminados, por lo tanto existe un dead lock. El resultado de la reducción

  Reducción del vector del grafo.

No hay comentarios:

Publicar un comentario