“INTERBLOQUEOS” · Un interbloqueo supone un bloqueo permanente de un conjunto de procesos o hilos que compiten por recursos o bien se comunican o sincronizan entre sí. (Carretero

UNIVERSIDAD CENTROCCIDENTAL

“LISANDRO ALVARADO”

DECANATO DE CIENCIAS Y TECNOLOGÍA

DEPARTAMENTO DE SISTEMAS

Unidad III:

“INTERBLOQUEOS”

II PARTE

“Aunque no podemos ir hacia atrás y tener un nuevo comienzo, todos podemos empezar desde ahora y conseguir un nuevo final.”

Karl Barth

1Sistemas Operativos Unidad III - Abril 2015

Contenido1. Introducción:

• Concepto

• Caracterización

• Tipos de recursos

2. Interbloqueo (Deadlock) • Modelaje

• Condiciones necesarias para que ocurra un interbloqueo.

• Tratamiento para interbloqueos.

3. Métodos de tratamiento de interbloqueo:• Prevención

• Evitación

• Detección y recuperación

• Ignorar el problema

Sistemas Operativos. Unidad I - Aimará Vargas- Niriaska Perozo

Interbloqueos

Las necesidades de algunos procesos pueden entrar enconflicto entre sí, causando que éstos se bloqueen.

Ejemplos:

Carretera de 2 sentidos con puente donde sólo cabe unautomóvil.

Dos personas llamándose por teléfono mutuamente.

Palillos en la cena de los filósofos.

Introducción.

Un interbloqueo supone un bloqueo permanente de un conjunto deprocesos o hilos que compiten por recursos o bien se comunican osincronizan entre sí. (Carretero y otros)

Los sucesos tienen que ver con la adquisición y liberación de los recursos.Estos recursos pueden ser físicos (Impresoras, unidades de cinta, espaciosen memoria, ciclos de CPU, entre otros) o lógicos (archivos, semáforos,monitores, entre otros).

En los bloqueos mutuos, pueden involucrarse uno o varios tipos derecursos.

Interbloqueos. Definición

Interbloqueo se caracteriza por la existencia de un conjunto deentidades activas que usan un conjunto de recursos:

Entidades activas Procesos y threads

Recursos Físicos:

CPU, memoria, dispositivos.

Lógicos:

archivos, semáforos, mutex, mensajes, señales, etc.

Caracterización

Tipos de recursos

Un sistema se compone de un numero finito de recursos que se distribuyen

entre varios procesos que compiten por ellos:

Recursos

Modos de operación

- Solicitud

- Utilización

- Liberación

-Físicos-Lógicos

-Expropiables.-No expropiables.

Llamadas al sistema

Modelaje de Bloqueo mutuo

Recurso A

Recurso T

Proceso P2Proceso P1

El recurso a está asignado al Proceso P1

El proceso P2 pide el recurso A.

El proceso P1pide el recurso T

El recurso T está asignado al Proceso P2.

Este sistema está bloqueado porque cada proceso tiene un recurso solicitado por el otro proceso y ninguno de ellos está dispuesto a liberar el recurso que tiene.

Bloqueo mutuo

EXCLUSIÓN MUTUA: los procesos reclaman control exclusivo de losrecursos que piden.

RETENCIÓN Y ESPERA: los procesos mantienen los recursos que ya leshan sido asignados mientras esperan por recursos adicionales.

NO APROPIACIÓN: los recursos no pueden ser extraídos de los procesosque los tienen hasta su completa utilización

ESPERA CIRCULAR: existe una cadena circular de procesos en la cual cadauno de ellos mantiene a uno o más recursos que son requeridos por elsiguiente proceso de la cadena.

El interbloqueo ocurre por: (Según Coffman)

Ignorar el problema: Utilizada por la mayoría de los S.O.

Dada la baja probabilidad de que ocurra y el costo que conlleva evitarlo(infrautilización y/o coste de algoritmos).

Prevención. Asegura que no ocurre fijando reglas para pedir recursos

- Infrautilización de recursos: se deben pedir antes de necesitarlos

Predicción o evitación. Asegura que no ocurre basándose en conocimiento denecesidades futuras de los procesos

- Dificultad de conocer el futuro

Detección y recuperación. Dejar que se produzca, detectarlo y recuperarse delmismo.

- Coste de algoritmo + pérdida del trabajo realizado

- Coste de algoritmo + Infrautilización de recursos

Tratamiento del interbloqueo

Tratamiento del interbloqueo: prevención.

Supresión de exclusión mutua:

Un proceso no puede tener acceso exclusivo a un recurso. No siemprees posible, y puede que lo único que haga sea cambiar el problema desitio. Es una solución drástica, inviable. Por ejemplo, permitir que dosprocesos usaran a la vez una impresora sería caótico.

La condición de EXCLUSIÓN MUTUA debe conservarse para aquellosrecursos que por naturaleza propia o función no pueden compartirse.

Tratamiento del interbloqueo: prevención

Suprimir la retención y espera:

La retención y espera es cuando no se puede satisfacer la petición deun proceso, éste se bloquea manteniendo los recursos que teníapreviamente asignados.

Para suprimirla cada proceso deberá pedir TODOS sus recursos almismo tiempo y no podrá comenzar su ejecución hasta haberlosrecibido por completo.

(Principio de Todo o Nada).

NEGACIÓN DE LA CONDICIÓN DE RETENCIÓN Y ESPERA.


No apropiación:

La no aprociación es cuando los recursos no se pueden quitar, es decir,un recurso sólo puede ser liberado voluntariamente por el proceso quelo retiene, después que haya cumplido su tarea.

Para eliminar la no apropiacion si un proceso que retiene algún recursosolicita otro recurso que no se le puede asignar de inmediato, entoncestodos los recursos que retiene se le expropian.

NEGACIÓN DE LA CONDICIÓN DE NO APROPIACIÓN


Espera circular:

Ocurre cuando existe una cadena circular de procesos tal que cada procesoen la lista esté esperando por uno o más recursos que tiene asignado elsiguiente proceso.

Para evitarla se debe:

Imponer una ordenación total de todos los tipos de recursos y

Requerir que cada proceso solicite los recursos siguiendo un orden denumeración ascendente. (Método de las peticiones ordenadas).

NEGACIÓN DE LA CONDICIÓN DE ESPERA CIRCULAR.


Utilizar el Método de las

Peticiones Ordenadas.

• Establece orden de recursos del

sistema :

Según forma de uso más frecuente

• Restricción:

Proceso sólo puede pedir en orden

LISTA DE RECURSOS

NIVEL RECURSO1 Terminal2 Impresora3 Plotter4 Unidad CD5 Disco Duro


Tratamiento de interbloqueo: Predicción y evitación.

Predicción

Si se presentan las condiciones necesarias paraun bloqueo mutuo, todavía es posible predecir suocurrencia mediante una cuidadosa asignaciónde recursos.

ALGORITMO DEL BANQUERO

(Habermann, 1969).

Tratamiento de interbloqueo: Predicción y evitación.

ALGORITMO DEL BANQUERO. (Condiciones Iníciales)

1. El sistema operativo administra un número fijo de unidades porrecurso entre un número fijo de usuarios (procesos).

2. Cada usuario (proceso) especifica por adelantado el número máximode unidades de los recursos que necesitará durante la ejecución de lostrabajos.

3. El sistema operativo aceptará la petición de un usuario (proceso) si lanecesidad máxima de ese usuario no es mayor al número fijo deunidades del recurso.

Predicción del interbloqueo (algoritmo banquero).

4- Un usuario (proceso) puede obtener o liberar unidades del recurso una a una. Los recursos asignados no podrán ser mayores a las necesidades máximas declaradas por dicho usuario.

5- Si el sistema operativo es capaz de satisfacer la necesidad máxima del usuario (proceso), entonces este proceso debe garantizar al sistema operativo que las unidades del recurso serán utilizadas y liberadas en un tiempo finito.

6- Determinar la situación del sistema : “SISTEMA EN ESTADO SEGURO" y “SISTEMA EN ESTADO INSEGURO".


Se dice que el sistema se encuentra en estado SEGURO, si el sistemaoperativo puede permitir que todos los procesos actuales terminen sustrabajos en un tiempo finito. En otro caso, el estado del sistema esINSEGURO.

Ejemplo: Préstamo Necesidad

Procesos Actual Máxima

Proceso 1 1 4

Proceso 2 4 6

Proceso 3 5 8

Unidades disponibles:2

La clave para que un sistema sea seguro es que exista al menos una formaadecuada de que terminen todos los procesos.


Ejemplo: Préstamo Necesidad

Procesos Actual Máxima

Proceso 1 8 10

Proceso 2 2 5

Proceso 3 1 3

Unidades disponibles:1

Un sistema inseguro indica que alguna secuencia desafortunada en la asignación de recursos podría llevar al bloqueo mutuo.


Estructura de datos para el algoritmo:

n: número de procesos, m:tipos de recursos

• Disponible: Un vector de longitud m que indica el número de recursosdisponibles de cada tipo. Si Disponible[j]=k, entonces hay k ejemplaresdisponibles del tipo de recurso Rj.

• Máx. Una matriz de n*m que define la demanda máxima de cada proceso porcada clase de recurso. Si máx[i,j]=k, entonces el proceso Pi puede solicitarcomo máximo k ejemplares del tipo de recurso Rj.

• Asignación: Una matriz de n*m que define el número de recursos de cada tipoasignados en ese momento a cada proceso. Si asignación[i,j]=k, entonces elproceso pi tiene actualmente asignados k ejemplares del tipo de recurso Rj.

• Necesidad: Una matriz de n*m que indica los recursos que le hacen falta acada proceso. Si necesidad[i,j]=k, entonces el proceso pi puede necesitar kejemplares más del tipo de recurso Rj para completar su tarea. Observe queNecesidad[i,j]=Máx[i,j]-Asignacion[i,j].


Estructura de datos para el algoritmo:

n: número de procesos, m:tipos de recursos

Disponible[m] Máx[n][m]

Asignación[n][m] Necesidad[n][m]


R1 R2 … Rm

3 2 … 2

R1 R2 … Rm

P1 7 2 … 3

P2 0 3 … 5

… … … … …

Pn 1 1 … 2

R1 R2 … Rm

P1 3 2 … 2

P2 0 3 … 4

… … … … …

Pn 0 1 … 1

R1 R2 … Rm

P1 4 0 … 1

P2 0 0 … 1

… … … … …

Pn 1 0 … 1

Implementación del algoritmo.

Sea Solicitudi el vector de solicitudes para el proceso Pi. Si Solicitudi[j]=k, entoncesel proceso Pi quiere k ejemplares del tipo de recurso Rj. Cuando el proceso Pi

efectúa una solicitud de recursos, se emprenden las siguientes acciones:

1- Si solicitudi<=Necesidadi , continuar en el paso 2. De lo contrario, presentar unacondición de error, ya que el proceso se ha excedido de su demanda máxima.

2- Si Solicitudi<=Disponiblei , continuar en el paso 3. De lo contrario, Pi deberáesperar, pues los recursos no están disponibles.

3- El sistema simula haber asignado todos los recursos solicitados al proceso pi

modificando el estado de la manera siguiente:

Disponible := Disponible - Solicitudi;

Asignacioni: = Asignacion + Solicitudi;

Necesidadi := Necesidad - Solicitudi;


Implementación del algoritmo.

4. Se ejecuta el ALGORITMO PARA DETERMINAR EL ESTADO DE UN SISTEMA.

5. Si el estado de asignación de recursos resultante es seguro, entonces se efectúa la transacción y los recursos se asignan al proceso pi. Sin embargo, si el nuevo estado no es seguro, entonces Pi, deberá esperar y se restablece el anterior estado de asignación de recursos.



PASO 1Sean Trabajo y Fin vectores de longitud m y n, respectivamente. AsígneseTrabajo:=Disponible y Fin[i]:=falso para toda i=1,2,...,n.

PASO 2Encontrar una i (proceso) tal que se cumplan ambas proposiciones:

a) Fin[i]=falsob) Necesidadi <=Trabajo.Si no existe tal i, continuar en el paso 4.

PASO 3Trabajo:=Trabajo + Asignacióni

Fin[i]:=verdaderoContinuar en el paso 2.

PASO 4Si Fin[i]=verdadero para toda i, entonces el sistema está en un estado SEGURO.En caso contrario, el sistema se encuentra en estado INSEGURO.

Predicción del interbloqueo (algoritmo estado de un sistema).



Si un sistema no emplea un algoritmo de prevención opredicción de bloqueo mutuo, entonces deberá:

1. Determinar si ha ocurrido un bloqueo mutuo.

(FASE DE DETECCIÓN)

1. Recuperarse del bloqueo mutuo.

(FASE DE RECUPERACIÓN)

Detección y recuperación.

1. FASE DE DETECCIÓN:

Debe ejecutarse unalgoritmo que determinesi el estado actual delsistema esté libre debloqueo y que, en caso deque no lo esté,identifique qué procesosestán implicados en elinterbloqueo.

2.FASE DE RECUPERACIÓN:

Una vez detectado elbloqueo mutuo, se debeaplicar una acción que loelimine

Detección y recuperación.

Se realiza mediante la aplicación del concepto dereducción a partir de una representación del sistema(procesos y recursos) mediante un grafo.

Se basa en el siguiente principio: “Se dice que el estadodel sistema se puede reducir por un proceso P si sepueden satisfacer las necesidades del proceso con losrecursos disponibles “. Esto significa que el proceso seencuentra desbloqueado.

Detección.

Sea N = Conjunto que contiene los nodos del grafo

( formado por los recurso y los procesos)

Sea A= Conjunto de las aristas que conectan a los nodos del grafo

Estado inicial

S= Ø (Conjunto de la secuencia de reducción )

D= Conjunto de procesos desbloqueados que NO están en el conjunto S.

Mientras D ≠ Ø, se puede reducir cualquier proceso del conjunto D y añadirlo a S

Si D = Ø y S = P, Donde P es el conjunto de todos los procesos

Entonces No existe INTERBLOQUEO

Sino los procesos del conjunto resultante P-S están en INTERBLOQUEO

Algoritmo de Detección. (Basado en grafos)

Permitir al sistema operativo recuperarse después de laocurrencia de un deadlock, sin intervención directa deloperador.

Alternativas:

i) Abortar uno o más procesos.

ii) Arrebatar recursos a uno o más procesos que seencuentran en deadlock.

Recuperación.

Abortar

Métodos:

- Abortar todos los procesos en deadlock:

• Costo alto.

• Pérdida total del trabajo realizado.

- Abortar un proceso a la vez, hasta que el deadlock haya sido eliminado:

FACTORES PARA LA ESCOGENCIA DEL PROCESO.

1- Prioridad de los procesos.

2- Cuántos y qué tipos de recursos tiene asignado el proceso.

3-Cuántos recursos más necesita el proceso para culminar.

4-Tiempo que lleva ejecutado cada proceso.

• Overhead (Sobretiempo).

• Algoritmo de detección.

Recuperación (1. Abortar recursos).

Quitar recursos a los procesos en forma sucesiva y otorgar éstos recursos aotros procesos.

Aspectos a considerar:

SELECCIÓN DE UN PROCESO “VICTIMA".

Determinar a cuáles procesos y cuáles recursos les serán

arrebatados.

Parámetros:

• Número de recursos que tiene asignado un procesos en deadlock.

• Cantidad de tiempo consumida por el proceso en su ejecución.

Hay que tener presente el que no ocurra el fenómeno de

STARVATION (APLAZAMIENTO INDEFINIDO):

Garantizar que los recursos no siempre sean arrebatados a los mismos procesos “Víctimas“, ya que esto aplazaría su culminación.

Recuperación (1. Arrebatar recursos).

Documents

“INTERBLOQUEOS” · Un interbloqueo supone un bloqueo permanente de un conjunto de procesos o hilos que compiten por recursos o bien se comunican o sincronizan entre sí. (Carretero