PDF de programación - Sistemas Operativos II - Tema 2

Imágen de pdf Sistemas Operativos II - Tema 2

Sistemas Operativos II - Tema 2gráfica de visualizaciones

Publicado el 14 de Enero del 2017
872 visualizaciones desde el 14 de Enero del 2017
67,5 KB
14 paginas
Creado hace 24a (09/03/2000)
Sistemas Operativos II

T EM A 2

El Interbloqueo

Contenido

2.1. Introducción
2.2. Recursos
2.3. Condiciones para que se produzca Interbloqueo
2.4. Modelado del Interbloqueo
2.5. Métodos para el tratamiento del interbloqueo
2.6. Prevención del interbloqueo

2.6.1. Exclusión mutua
2.6.2. Retención y espera
2.6.3. No expropiación
2.6.4. Espera circular

2.7. Evitación del interbloqueo

2.7.1. Trayectorias de recursos
2.7.2. Estados seguros e inseguros
2.7.3. Algoritmo del banquero

2.7.3.1. Algoritmo del banquero
2.7.3.2. Algoritmo de seguridad

2.7.4. Resumen

2.8. Detección del interbloqueo

2.8.1. Algoritmo de detección
2.8.2. Utilización de los algoritmos de detección

2.9. Recuperación del interbloqueo

2.9.1. Terminación de procesos
2.9.2. Expropiación de recursos
2.9.3. Resumen

2.10. Estrategia combinada para el manejo de interbloqueos
2.11. Referencias

Sistemas Operativos II

2.1. Introducción
La administración de los recursos es una de las principales tareas del sistema operativo. Muchos de los
recursos únicamente pueden ser usados por un solo proceso a la vez, como es el caso de las impresoras,
dispositivos de cinta, etc. Como consecuencia, todos los sistemas operativos tienen que ofrecer
mecanismos que permitan a los procesos acceder de forma exclusiva a determinados recuros. Como
consecuencia, cuando un proceso solicita recursos y éstos no están disponibles en ese momento, entra en
un estado de espera.

En muchas aplicaciones, un proceso puede requir acceso exclusivo no sólo a un recurso, sino a
varios. En sistemas operativos en los que únicamente se ejecuta un proceso a la vez, el proceso
simplemente toma todos los recursos que necesita. Sin embargo, en un sistema con multiprogramación,
puede suceder que procesos que están en espera de recursos ocupados por otros procesos no cambien
nunca de estado, porque los recursos que solicitan están en poder de otros procesos también en espera. A

interbloqueo (deadlock. También abrazo mortal o bloqueo mutuo).

El interbloqueo se puede definir como sigue:

Un conjunto de procesos se encuentra en estado de interbloqueo cuando cada uno
de ellos espera un suceso que sólo puede originar otro proceso del mismo
conjunto.

2.2. Recursos
Un sistema se compone de un número finito de recursos que se distribuyen entre varios procesos que
compiten por ellos. Los recursos se dividen en varios tipos, de cada uno de los cuales pueden existir
varios ejemplares idénticos:

q físicos: ciclos de CPU, espacio en memoria, dispositivos de E/S (impresoras, unidades de cinta,

etc.).

q lógicos: ficheros, tablas del sistema, semáforos.

Un proceso debe solicitar un recurso antes de usarlo y liberarlo al terminar su uso. Además, un

proceso puede solicitar cuantos recursos necesite.

Existen dos clases de recursos: expropiables y no expropiables. Un recurso expropiable
(preemptable resource) es aquél que se le puede quitar a un proceso sin que se produzca ningún tipo de
malfuncionamiento. Ejemplos son la memoria y la CPU. Un recurso no expropiable (non preemptable
resource), por el contrario, no puede ser quitado a un proceso sin provocar un fallo en el mismo. Un
ejemplo es la impresora. Los interbloqueos se suelen producir, en parte, debido al uso de recursos no
expropiables. Sin embargo, existen otros sucesos que pueden originar un interbloqueo, como pueden ser
los mecanismos de comunicación entre procesos.

En el modo de operación normal, un proceso utiliza un recurso de acuerdo con la siguiente

secuencia:

q Solicitud. Si la solicitud no puede atenderse de inmediato, entonces el proceso solicitante debe

esperar hasta que pueda adquirir el recurso.

q Utilización. El proceso puede trabajar con el recurso.
q Liberación. El proceso libera el recurso.

La solicitud y liberación de recursos son llamadas al sistema. Algunos ejemplos son las parejas de
llamadas Abrir/Cerrar archivo y Asignar/Liberar memoria. De igual forma, la utilización de recursos sólo
puede conseguirse mediante llamadas al sistema, de modo que para cada utilización el sistema operativo
comprueba que el proceso que usa el recurso lo había solicitado previamente y ya lo tiene asignado.

Una tabla del sistema registra si cada uno de los recursos está libre o asignado y, de estar
asignado, a qué proceso. Si un proceso solicita un recurso que ya se encuentra asignado a otro, puede
añadirse a la cola de procesos que esperan tal recurso.

_________________________________________________________________________________
___
TEMA 2. El Interbloqueo

Pág. 1

Sistemas Operativos II

2.3. Condiciones para que se produzca Interbloqueo
Un interbloqueo puede surgir si y solo si en un sistema se presentan simultáneamente las siguientes
cuatro condiciones:

1. Exclusión mutua. Los recursos compartidos son adquiridos y utilizados de modo mútuamente

exclusivo, es decir, por un proceso como máximo en cada momento.

2. Retención y espera. Cada proceso retiene los recursos que ya le han sido asignados mientras

espera para adquirir el resto de recursos.

3. No expropiación. Los recursos no se pueden quitar a los procesos. Un recurso sólo puede ser

liberado voluntariamente por el proceso que lo retiene.

4. Espera circular. Debe existir una cadena circular de dos o más procesos, cada uno de los cuales

espera por uno o más recursos en poder del siguiente miembro de la cadena.

La condición de espera circular implica la condición de retención y espera, por lo que las cuatro

condiciones no son completamente independientes.

2.4. Modelado del Interbloqueo
Los interbloqueos pueden describirse utilizando un grafo dirigido y bipartito G(N,A) llamado grafo de
asignación de recursos, que consta en un conjunto de N nodos (vértices) y E arcos.

El conjunto de nodos N se divide en dos tipos:

• P = {P1, P2, ..., Pn}, conjunto formado por todos los procesos del sistema.
• R = {R1, R2, ..., Rn}, conjunto formado por todos los tipos de recursos.

Los arcos también son de dos tipos:

• Arco de solicitud. Es un arco que parte de un proceso Pi hacia un tipo de recurso Rj y se representa
por Pi fi Rj (o (Pi, Rj)). Significa que el proceso Pi solicitó una instancia del recurso Rj y se
encuentra esperándolo.

• Arco de asignación. Es un arco que sale de un tipo de recurso Rj y se dirige a un proceso Pi
(representado por Rj fi Pi o (Rj, Pi)). Significa que se ha asignado un ejemplar del tipo de recurso Rj
al proceso Pi.

Gráficamente se representa cada proceso con un círculo y cada tipo de recurso con un
rectángulo. Si de algún tipo de recurso existe más de un ejemplar, se representa cada ejemplar con un
punto dentro del rectángulo. Un arco de solicitud parte entonces de un círculo y apunta a un rectángulo;
en cambio un arco de asignación parte desde un punto dentro del rectángulo y señala hacia un círculo.

El efecto de las operaciones sobre recursos (solicitud, asignación y liberación) en el grafo de

Pi solicita un ejemplar del tipo Rj
Una instancia del recurso Rj se asigna al
proceso Pi
El proceso Pi libera el recurso Rj

Se inserta un arco de solicitud Pi fi Rj
El arco de solicitud Pi fi Rj se transforma
instantáneamente en arco de asignación Rj fi Pi
Se elimina el arco de asignación Rj fi Pi

Efecto en el grafo

Un ejemplo de grafo de asignación de recursos se muestra en la Figura 1.

_________________________________________________________________________________
___
TEMA 2. El Interbloqueo

Pág. 2

Sistemas Operativos II

R1


R3


P1

P2

P3




R2




R4

Figura 1.- Gráfico de asignación de recursos.

Este grafo de asignación de recursos muestra la siguiente situación:

• Los conjuntos P, R y E son:
- P = {P1, P2, P3}
- R = {R1, R2, R3, R4}
- E = {P1 fi R1, P2 fi R3, R1 fi P2, R2 fi P2, R2 fi P1, R3 fi P3}

• Los recursos existentes son:

- Un recurso del tipo R1.
- Dos recursos del tipo R2.
- Un recurso del tipo R3.
- Tres recursos del tipo R4.

• Estados de los procesos:

- El proceso P1 tiene asignado un recurso de tipo R2, y espera un recurso de tipo R1.
- El proceso P2 tiene asignado un recurso de tipo R1 y otro de tipo R2, y espera un recurso de tipo

R3.

- El proceso P3 tiene asignado un recurso de tipo R3.

Si el grafo de asignación de recursos no contiene ciclos, entonce

encuentra en interbloqueo. Por otra parte, si existe un ciclo, puede haber interbloqueo. Es decir, la
presencia de un ciclo es condición necesaria para la existencia de interbloqueo.

Si de cada tipo de recurso existe un único ejemplar, entonces la presencia de un ciclo determina
que existe interbloqueo. En este caso la existencia de un ciclo es condición necesaria y suficiente para la
existencia de interbloqueo.

En la Figura 2 se muestran un ejemplo de grafo de asignación con interbloqueo.

R1


R3


P1

P2

P3




R2




R4

Figura 2.- Gráfico de asignación de recursos con un interbloqueo.

_________________________________________________________________________________
___
TEMA 2. El Interbloqueo

Pág. 3

Sistemas Operativos II

2.5. Métodos para el tratamiento del interbloqueo

Existen varias estrategias para enfrentar el problema de los interbloqueos:

q Ignorar el problema
q Detección y Recuperación
q Evitación
q Prevención

La estrategia más sencilla es simplemente ignorar el problema. A esta estrategia se la denomina
algoritmo del avestruz (Ostrich): esconder la cabeza en la tierra y pretender que no existe problema
alguno. La justificación de este método es que si el interbloqueo se presenta con una frecuencia baja en
comparación con los fallos del sistema por otras razones (errores en el sistema operativo, fallos en el
hardware, etc.), no tiene sentido tomar
  • Links de descarga
http://lwp-l.com/pdf1240

Comentarios de: Sistemas Operativos II - Tema 2 (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad