Los sistemas
computacionales están llenos de recursos que pueden ser utilizados por sólo un
proceso a la vez. Algunos ejemplos comunes son las impresoras, las unidades de
cinta y las ranuras en los tableros internos del sistema.
El proceso A pide
permiso para utilizar el escáner y se le otorga.
El proceso B se programa de manera
distinta y solicita primero el grabador de CDs, y también se le otorga. Ahora A
pide el grabador de CDs, pero la petición se rechaza hasta que B lo
libere. Por desgracia, en vez de liberar el grabador de CD, B pide el
escáner.
En este punto ambos procesos están bloqueados
y permanecerán así para siempre. A esta situación se le conoce como interbloqueo.
Los interbloqueos
también pueden ocurrir entre máquinas A menudo, los dispositivos como escáneres,
grabadores de CD, impresoras y unidades de cinta se conectan a la red como
recursos compartidos, disponibles para cualquier usuario en cualquier equipo.
Si estos dispositivos se pueden reservar de manera remota (es decir, desde el
equipo doméstico del usuario), pueden ocurrir los mismos tipos de interbloqueos
antes descritos. Las situaciones más complicadas pueden ocasionar interbloqueos
que involucren a tres, cuatro o más dispositivos y usuarios.
Los interbloqueos
pueden ocurrir en una variedad de situaciones, además de solicitar dispositivos
de E/S dedicados.
Si el proceso A bloquea
el registro R1 y el proceso B bloquea el registro R2, y
después cada proceso trata de bloquear el registro del otro, también tenemos un
interbloqueo. Por ende, los interbloqueos pueden ocurrir en los recursos de
hardware o de software.
Se ha escrito mucho
sobre los interbloqueos.
Dos bibliografías sobre
el tema han aparecido en Operating Systems Review y deben consultarse en
busca de referencias (Newton, 1979; y Zobel, 1983). Aunque estas bibliografías
son antiguas, la mayor parte del trabajo sobre los interbloqueos se hizo mucho
antes de 1980, por lo que aún son de utilidad.
Recursos
Una clase principal de
interbloqueos involucra a los recursos, Los interbloqueos pueden ocurrir cuando
a los procesos se les otorga acceso exclusivo a los dispositivos, registros de
datos, archivos, etcétera. Para que el análisis sobre los interbloqueos sea lo
más general posible, nos referiremos a los objetos otorgados como recursos Un recurso puede ser un
dispositivo de hardware (por ejemplo, una unidad de cinta) o una pieza de
información (como un registro bloqueado en una base de datos). En resumen, un
recurso es cualquier cosa que se debe adquirir, utilizar y liberar con el
transcurso del tiempo.
Recursos apropiativos y no apropiativos
Los recursos son de dos
tipos: apropiativos y no apropiativos. Un recurso apropiativo es uno que se puede quitar al proceso que lo
posee sin efectos dañinos. La memoria es un ejemplo de un recurso apropiativo.
Un recurso no apropiativo es uno que no
se puede quitar a su propietario actual sin hacer que el cómputo falle. Si un
proceso ha empezado a quemar un CD-ROM y tratamos de quitarle de manera
repentina el grabador de CD y otorgarlo a otro proceso, se obtendrá un CD con
basura.
En general, los
interbloqueos involucran a los recursos no apropiativos. Los interbloqueos
potenciales que pueden involucrar a los recursos apropiativos por lo general se
pueden resolver mediante la reasignación de los recursos de un proceso a otro.
Por ende, nuestro análisis se enfocará en los recursos no apropiativos.
La secuencia de eventos
requerida para utilizar un recurso se proporciona a continuación, en un formato
abstracto.
1. Solicitar el
recurso.
2. Utilizar el recurso.
3. Liberar el recurso.
Adquisición de recursos
Para ciertos tipos de
recursos, como los registros de una base de datos, es responsabilidad de los
procesos de usuario administrar su uso. Una manera de permitir que los usuarios
administren los recursos es asociar un semáforo con cada recurso. Estos
semáforos se inicializan con 1. Se pueden utilizar mutexes de igual forma. Los
tres pasos antes listados se implementan como una operación down en el semáforo
para adquirir el recurso, usarlo y finalmente realizar una operación up en el
recurso para liberarlo.
Algunas veces los
procesos necesitan dos o más recursos. Se pueden adquirir de manera secuencial.
Si se necesitan más de dos recursos, sólo se adquieren uno después del otro.
Mientras sólo haya un proceso involucrado, todo funciona sin problemas.
INTRODUCCIÓN A LOS INTERBLOQUEOS
El interbloqueo se
puede definir formalmente de la siguiente manera:
Un conjunto de procesos
se encuentra en un interbloqueo si cada proceso en el conjunto está esperando
un evento que sólo puede ser ocasionado por otro proceso en el conjunto
Debido a que todos los
procesos están en espera, ninguno de ellos producirá alguno de los eventos que
podrían despertar a cualquiera de los otros miembros del conjunto, y todos los
procesos seguirán esperando para siempre.
El evento por el que
cada proceso espera es la liberación de algún recurso que actualmente es
poseído por otro miembro del conjunto.
El número de procesos y
el número de cualquier tipo de recursos poseídos y solicitados es irrelevante.
Este resultado se aplica a cualquier tipo de recurso, tanto de hardware como de
software. A este tipo de interbloqueo se le conoce como interbloqueo de recursos.
Condiciones para los interbloqueos de recursos
Coffman y colaboradores
(1971) mostraron que deben aplicarse cuatro condiciones para un interbloqueo
(De recursos):
|1. Condición de
exclusión mutua. Cada recurso se asigna en un momento dado a sólo un proceso, o
está disponible.
2. Condición de
contención y espera. Los procesos que actualmente contienen recursos que se les
otorgaron antes pueden solicitar nuevos recursos.
3. Condición no
apropiativa. Los recursos otorgados previamente no se pueden quitar a un
proceso por la fuerza. Deben ser liberados de manera explícita por el proceso
que los contiene.
4. Condición de espera
circular. Debe haber una cadena circular de dos o más procesos, cada uno de los
cuales espera un recurso contenido por el siguiente miembro de la cadena.
Las cuatro condiciones
deben estar presentes para que ocurra un interbloqueo.
Modelado de interbloqueos
Holt (1972) mostró cómo
se pueden modelar estas cuatro condiciones mediante el uso de gráficos
dirigidos.
Los gráficos tienen dos
tipos de nodos: procesos, que se muestran como círculos, y recursos, que se
muestran como cuadros. Un arco dirigido de un nodo de recurso (cuadro) a un
nodo de proceso (círculo) significa que el recurso fue solicitado previamente
por, y asignado a, y actualmente es contenido por ese proceso.
EL
ALGORITMO DE LA AVESTRUZ
El método más simple es
el algoritmo de la avestruz: meta su cabeza en la arena y pretenda que no hay
ningún problema.† Las personas reaccionan a esta estrategia de diversas formas.
Los matemáticos la encuentran totalmente inaceptable y dicen que los
interbloqueos se deben prevenir a toda costa; los ingenieros preguntan con qué
frecuencia se espera el problema, con qué frecuencia falla el sistema por otras
razones y qué tan grave es un interbloqueo. Si ocurren interbloqueos en
promedio de una vez cada cinco años, pero los fallos del sistema debido al
hardware, errores del compilador y errores en el sistema operativo ocurren una
vez por semana, la mayoría de los ingenieros no estarán dispuestos a reducir
considerablemente el rendimiento por la conveniencia de eliminar los interbloqueos.
Para que este contraste
sea más específico, considere un sistema operativo que bloquea al proceso llamador
cuando no se puede llevar a cabo una llamada a los sistemas open en un
dispositivo físico, como una unidad de CD-ROM o una impresora, debido a que el
dispositivo está muy ocupado.
Por lo general es
responsabilidad del driver (controlador) de dispositivos decidir qué acción
tomar bajo tales circunstancias. Bloquear o devolver una clave de error son dos
posibilidades obvias. Si un proceso abre exitosamente la unidad de CD-ROM y
otro la impresora, y después cada proceso trata de abrir el otro recurso y se
bloquea en el intento, tenemos un interbloqueo. Pocos sistemas actuales detectarán
esto.
DETECCIÓN Y RECUPERACIÓN DE UN
INTERBLOQUEO
Una segunda técnica es
la detección y recuperación. Cuando se utiliza esta técnica, el sistema no trata
de evitar los interbloqueos. En vez de ello, intenta detectarlos cuando ocurran
y luego realiza cierta acción para recuperarse después del hecho
Detección de interbloqueos con un recurso de cada
tipo sólo
existe un recurso de cada tipo. Dicho sistema podría tener un escáner, un
grabador de CD, un trazador (plotter) y una unidad de cinta, pero no más que un recurso de cada clase.
Para un sistema así,
podemos construir un gráfico de recursos.
Si este gráfico
contiene uno o más ciclos, existe un interbloqueo. Cualquier proceso que forme parte de un ciclo está en
interbloqueo. Si no existen ciclos, el sistema no está en interbloqueo.
Como ejemplo de un
sistema más complejo que los que hemos analizado hasta ahora, considere un
sistema con siete procesos, A a G, y seis recursos, R a W.
El estado de cuáles recursos están contenidos por algún proceso y cuáles están
siendo solicitados es el siguiente:
1. El proceso A contiene
a R y quiere a S.
2. El proceso B no
contiene ningún recurso pero quiere a T.
3. El proceso C no
contiene ningún recurso pero quiere a S.
4. El proceso D contiene
a U y quiere a S y a T.
5. El proceso E contiene
a T y quiere a V.
6. El proceso F contiene
a W y quiere a S.
7. El
proceso G contiene a V y quiere a U.
Es relativamente fácil
distinguir los procesos en interbloqueo a simple vista a partir de un sencillo
gráfico, para usar este método en sistemas reales necesitamos un algoritmo
formal para la detección de interbloqueos. Hay muchos algoritmos conocidos para
detectar ciclos en gráficos dirigidos. A continuación veremos un algoritmo
simple que inspecciona un gráfico y termina al haber encontrado un ciclo, o
cuando ha demostrado que no existe ninguno. Utiliza cierta estructura dinámica
de datos: L, una lista de nodos, así como la lista de arcos. Durante el
algoritmo, los arcos se marcarán para indicar que ya han sido inspeccionados,
para evitar repetir inspecciones.
El algoritmo opera al
llevar a cabo los siguientes pasos, según lo especificado:
1. Para cada nodo N en
el gráfico, realizar los siguientes cinco pasos con N como el nodo
inicial.
2. Inicializar L con
la lista vacía y designar todos los arcos como desmarcados.
3. Agregar el nodo
actual al final de L y comprobar si el nodo ahora aparece dos veces en L.
Si lo hace, el gráfico
contiene un ciclo (listado en L) y el algoritmo termina.
4. Del nodo dado, ver
si hay arcos salientes desmarcados. De ser así, ir al paso 5; en caso
contrario, ir al paso
5. Elegir un arco
saliente desmarcado al azar y marcarlo. Después seguirlo hasta el nuevo nodo actual
e ir al paso 3.
6. Si este nodo es el
inicial, el gráfico no contiene ciclos y el algoritmo termina. En caso
contrario, ahora hemos llegado a un punto muerto. Eliminarlo y regresar al nodo
anterior; es decir, el que estaba justo antes de éste, hacerlo el nodo actual e
ir al paso 3.
Lo que hace este
algoritmo es tomar cada nodo en turno, como la raíz de lo que espera sea un árbol,
y realiza una búsqueda de un nivel de profundidad en él. Si alguna vez regresa
a un nodo que ya se haya encontrado, entonces ha encontrado un ciclo. Si agota
todos los arcos desde cualquier nodo dado, regresa al nodo anterior. Si regresa
hasta la raíz y no puede avanzar más, el subgráfico que se puede alcanzar desde
el nodo actual no contiene ciclos. Si esta propiedad se aplica para todos los
nodos, el gráfico completo está libre de ciclos, por lo que el sistema no está
en interbloqueo.
Detección del interbloqueo con varios recursos de cada tipo
Cuando existen varias
copias de algunos de los recursos, se necesita un método distinto para detectar
interbloqueos. Ahora presentaremos un algoritmo basado en matrices para
detectar interbloqueos entre n procesos, de P1 a Pn.
Hagamos que el número de clases de recursos sea m, con E1 recursos
de la clase 1, E2 recursos de la clase 2 y en general, Ei recursos
de la clase i (1 ≤i ≤m). E es el vector de recursos existentes. Este
vector proporciona el número total de instancias de cada recurso en existencia.
Por ejemplo, si la clase 1 son las unidades de cinta, entonces E1 _ 2
significa que el sistema tiene dos unidades de cinta.
En cualquier instante,
algunos de los recursos están asignados y no están disponibles. Hagamos que A
sea el vector de recursos
disponibles, donde Ai proporciona el número de instancias del
recurso i que están disponibles en un momento dado (es decir, sin
asignar). Si ambas de nuestras unidades de cinta están asignadas, A1 será
0.
Ahora necesitamos dos
arreglos: C, la matriz de
asignaciones actuales y R, la matriz de peticiones.
La i-ésima fila
de C nos indica cuántas instancias de cada clase de recurso contiene Pi
en un momento dado. Así Cij es el número de instancias del recurso j
que están contenidas por el proceso i. De manera similar, Rij es
el número de instancias del recurso j que desea Pi. Estas cuatro
estructuras de datos
El algoritmo de
detección de interbloqueos se muestra a continuación.
1. Buscar un proceso
desmarcado, Pi, para el que la i-ésima fila de R sea menor
o igual que A.
2. Si se encuentra
dicho proceso, agregar la i-ésima fila de C a A, marcar el
proceso y regresar al paso 1.
3. Si no existe dicho
proceso, el algoritmo termina.
RECUPERACION DE
INTERBLOQUEOS
Un sistema que pretenda
recuperarse del interbloqueo, debe invocar a un algoritmo de detección cuando
lo considere oportuno.
Formas de intentar la recuperación:
Terminación de procesos
Expropiación de recursos
Terminación de procesos
Matando a todos los procesos implicados
(drástico)
Matando a uno de los procesos ¿cuál?
El que más recursos libere
El que menos tiempo lleve en ejecución...
Retrocediendo la ejecución de algún proceso (rollback)
Muy complicado de implementar y necesita que
el programa esté diseñado para que pueda retroceder
Expropiación de
recursos
Selección de la víctima
¿Qué recursos y de que procesos se expropian?
Retroceso
Si expropiamos un recurso de un proceso, ¿qué
hacemos con ese proceso?
En ambos casos (terminación de procesos o expropiación
de recursos) hay que tener cuidado de no provocar la inanición de procesos
Recuperación por medio de apropiación
En algunos casos puede
ser posible quitar temporalmente un recurso a su propietario actual y otorgarlo
a otro proceso. En muchos casos se puede requerir intervención manual, en
especial en los sistemas operativos de procesamiento por lotes que se ejecutan en
mainframes.
Recuperación a través del retroceso
Realizar puntos de
comprobación en un proceso significa que su estado se escribe en un archivo
para poder reiniciarlo más tarde. El punto de comprobación no sólo contiene la
imagen de la memoria, sino también el estado del recurso; en otras palabras,
qué recursos están asignados al proceso en un momento dado.
Para realizar la
recuperación, un proceso que posee un recurso necesario se revierte a un punto
en el tiempo antes de que haya adquirido ese recurso, para lo cual se inicia
uno de sus puntos de comprobación anteriores.
Recuperación a través de la eliminación
de procesos
La forma más cruda y
simple de romper un interbloqueo es eliminar uno o más procesos. Una
posibilidad es eliminar a uno de los procesos en el ciclo.
En este método, el
proceso a eliminar se elige con cuidado, debido a que está conteniendo recursos
que necesita cierto proceso en el ciclo.
Donde sea posible, es
mejor eliminar un proceso que se pueda volver a ejecutar desde el principio sin
efectos dañinos.
Un proceso que
actualiza una base de datos no siempre se puede ejecutar una segunda vez en
forma segura. Si el proceso agrega 1 a algún campo de una tabla en la base de
datos, al ejecutarlo una vez, después eliminarlo y volverlo a ejecutar de nuevo,
se agregará 2 al campo, lo cual es incorrecto.
CÓMO EVITAR INTERBLOQUEOS
Con la evitación no se tienen
reglas estáticas a los procesos, sino que el sistema operativo analiza cada
petición de recursos y determina si el sistema quedará en un estado estable o inestable,
en este último caso, se deniega la petición, posponiéndola temporalmente.
La evitación se basa en los
siguientes conceptos:
Estado de asignación de
recursos: Número de recursos asignados, disponibles y máximo de recursos
posibles por proceso.
Secuencia segura: Secuencia de
finalización de procesos, tal que todos los procesos puedan finalizar exitosamente,
iniciando en un determinado estado de asignación de recursos
Estado seguro de asignación de
recursos: Estado de asignación de recursos, donde existe al menos una secuencia
segura.
Estado inseguro de asignación
de recursos: No existe ninguna secuencia segura. Obsérvese, que aunque un
estado inseguro no implica que exista interbloqueo, talvez una secuencia
determinada de eventos lleve a uno.
Estados seguros e inseguros
Se dice que un estado
es seguro si hay cierto
orden de programación en el que se puede ejecutar cada proceso hasta
completarse, incluso aunque todos ellos solicitaran de manera repentina su
número máximo de recursos de inmediato.
Un estado inseguro no
es un estado en interbloqueo, la diferencia entre un estado seguro y uno inseguro
es que, desde un estado seguro, el sistema puede garantizar que todos
los procesos terminarán; desde un estado inseguro, no se puede dar esa
garantía.
El algoritmo del banquero para un solo
recurso
Dijkstra (1965) ideó un
algoritmo de programación que puede evitar interbloqueos; este algoritmo se
conoce como el algoritmo del banquero
y es una extensión del algoritmo de detección de interbloqueos.
Se modela de la forma
en que un banquero de una pequeña ciudad podría tratar con un grupo de clientes
a los que ha otorgado líneas de crédito. Lo que hace el algoritmo es comprobar
si al otorgar la petición se produce un estado inseguro. Si es así, la petición
se rechaza. Si al otorgar la petición se produce un estado seguro, se lleva a
cabo.
En la imagen (a)
podemos ver cuatro clientes, A, B, C y D, cada uno
de los cuales ha recibido un cierto número de unidades de crédito (por ejemplo,
1 unidad es 1K dólares). El banquero sabe que no todos los clientes necesitan
su crédito máximo de inmediato, por lo que ha reservado sólo 10 unidades en vez
de 22 para darles servicio (en esta analogía, los clientes son procesos, las
unidades son, por ejemplo, unidades de cinta, y el banquero es el sistema
operativo).
Los clientes hacen sus
respectivas labores, pidiendo préstamos de vez en cuando (es decir, solicitando
recursos).
Este estado es seguro
debido a que, con dos unidades restantes, el banquero puede retrasar cualquier
petición excepto la de C, con lo cual deja que C termine y libere
todos sus cuatro recursos. Con cuatro unidades a la mano, el banquero puede
dejar que D o B tengan las unidades necesarias, y así en lo
sucesivo. Considere lo que ocurriría si se otorgara una petición de B por
una o más unidades en la (b). Tendríamos la situación de la (c), que es
insegura. Si todos los clientes pidieran de manera repentina sus préstamos
máximos, el banquero no podría satisfacer a ninguno de ellos, y tendríamos un
interbloqueo.
El algoritmo del
banquero considera cada petición a medida que va ocurriendo, y analiza si al otorgarla
se produce un estado seguro. Si es así, se otorga la petición; en caso
contrario, se pospone hasta más tarde. Para ver si un estado es seguro, el
banquero comprueba si tiene los suficientes recursos para satisfacer a algún
cliente.
El algoritmo del banquero para varios
recursos
El algoritmo del
banquero se puede generalizar para manejar varios recursos. La figura muestra cómo
funciona.
En la figura se
muestran dos matrices. La de la izquierda muestra cuántas instancias de cada
recurso están asignadas en un momento dado a cada uno de los cinco procesos. La
matriz de la derecha muestra cuántos recursos sigue necesitando cada proceso
para poder completarse.
Al igual que en el caso
con un solo recurso, los procesos deben declarar sus necesidades totales de
recursos antes de ejecutarse, por lo que el sistema puede calcular la matriz
derecha en cada instante.
Los tres vectores a la
derecha de la figura muestran los recursos existentes (E), los recursos
poseídos
(P) y los
recursos disponibles (A), respectivamente. De E podemos ver que
el sistema tiene seis unidades de cinta, tres trazadores, cuatro impresoras y
dos unidades de CD-ROM. De éstos, ya hay asignados cinco unidades de cinta,
tres trazadores, dos impresoras y dos unidades de CD-ROM.
Ahora se puede declarar
el algoritmo para comprobar si un estado es seguro.
1. Buscar una fila R,
cuyas necesidades de recursos no satisfechas sean menores o iguales que A.
Si no existe dicha fila, el sistema entrará en interbloqueo en un momento dado,
debido a que ningún proceso se podrá ejecutar hasta completarse (suponiendo que
los procesos mantienen todos los recursos hasta que terminan).
2. Suponer que el
proceso seleccionado de la fila solicita todos los recursos que necesita (lo que
se garantiza que es posible) y termina. Marcar ese proceso como terminado y
agregar todos sus recursos al vector A.
3. Repetir los pasos 1
y 2 hasta que todos los procesos se marquen como terminados (en cuyo caso el
estado inicial era seguro) o hasta que no haya ningún proceso cuyas necesidades
de recursos se puedan satisfacer (en cuyo caso hay un interbloqueo).
CÓMO PREVENIR INTERBLOQUEOS
Habiendo visto que
evitar los interbloqueos es algo en esencia imposible, debido a que se requiere
información sobre las peticiones futuras, que no se conocen, ¿cómo evitan los
sistemas reales el interbloqueo?
La respuesta es volver
a las cuatro condiciones establecidas por Coffman y colaboradores
(1971) para ver si
pueden proporcionarnos una pista.
Cómo atacar la condición de exclusión
mutua
Concepto de exclusión mutua:
Consiste en que un solo proceso excluye temporalmente a todos los demás para
usar un recurso compartido de forma que garantice la integridad del sistema.
Concepto de sección critica:
Es la parte del programa con un
comienzo y un final claramente marcados que generalmente contiene la
actualización de una o más variables compartidas.
Para que una solución al
problema de la exclusión mutua sea válida, se tienen que cumplir una serie de
condiciones:
Hay que garantizar la exclusión
mutua entre los diferentes procesos a la hora de acceder al recurso compartido.
No puede haber en ningún momento dos procesos dentro de sus respectivas
secciones críticas.
No se deben hacer suposiciones
en cuanto a la velocidad relativa de los procesos en conflicto.
Ningún proceso que esté fuera de
su sección crítica debe interrumpir a otro para el acceso a la sección crítica.
Cuando más de un proceso desee
entrar en su sección crítica, se le debe conceder la entrada en un tiempo
finito, es decir, que nunca se le tendrá esperando en un bucle que no tenga
final.
REQUISITOS PARA LA EXCLUSIÓN MUTUA
Sólo un proceso, de
todos los que poseen secciones críticas por el mismo recurso compartido, debe
tener permiso para entrar en ella en un momento dado.Un proceso que se interrumpe en una sección no
crítica debe hacerlo sin interferir con los otros procesos.
Un proceso no debe poder solicitar acceso a una
sección crítica para después ser demorado indefinidamente, no puede permitirse
el interbloqueo o la inanición.
Si ningún proceso está en su sección crítica,
cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora.
No se debe suponer sobre la velocidad relativa de
los procesos o el número de procesadores.
6 Un proceso permanece en su sección crítica por un
tiempo finito.
Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.
Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.
Si podemos evitar que
los procesos que contienen recursos esperen por más recursos, podemos eliminar los
interbloqueos. Una forma de lograr esta meta es requerir que todos los procesos
soliciten todos sus recursos antes de empezar su ejecución. Si completa al
proceso se le asignará lo que necesite y podrá ejecutarse hasta completarse. Si
uno o más recursos están ocupados, no se asignará nada y el proceso sólo
esperará.
Un problema inmediato
con este método es que muchos procesos no saben cuántos recursos necesitarán
hasta que hayan empezado a ejecutarse. Otro problema es que los recursos no se
utilizarán de una manera óptima con este método.
Sin embargo, algunos
sistemas de procesamiento por lotes de mainframes requieren que el usuario
liste todos los recursos en la primera línea de cada trabajo.
Una manera ligeramente
distinta de romper la condición de contención y espera es requerir que un
proceso que solicita un recurso libere temporalmente todos los recursos que
contiene en un momento dado. Después puede tratar de obtener todo lo que
necesite a la vez.
Cómo atacar la condición no apropiativa
Si a un proceso se le
ha asignado la impresora y está a la mitad de imprimir su salida, quitarle la
impresora a la fuerza debido a que el trazador que necesita no está disponible
es algo engañoso como máximo, e imposible en el peor caso. Sin embargo, ciertos
recursos se pueden virtualizar para evitar esta situación. Al colocar en una
cola de impresión en el disco la salida de la impresora y permitir que sólo el
demonio de impresión tenga acceso a la impresora real, se eliminan los
interbloqueos que involucran a la impresora, aunque se crea uno para el espacio
en disco.
Cómo atacar la condición de espera
circular
La espera circular se
puede eliminar de varias formas. Una de ellas es simplemente tener una regla
que diga que un proceso tiene derecho sólo a un recurso en cualquier momento.
Si necesita un segundo recurso, debe liberar el primero.
Con esta regla, el
gráfico de asignación de recursos nunca puede tener ciclos. Veamos por qué es
esto cierto para el caso de dos procesos, en la figura (b). Podemos obtener un
interbloqueo sólo si A solicita el recurso j y B solicita
el recurso i. Suponiendo que i y j sean recursos
distintos, tendrán diferentes números. Si i > j, entonces A
no puede solicitar a j debido a que es menor de lo que ya tiene. Si i
< j, entonces B no puede solicitar a i debido a que
es menor de lo que ya tiene. De cualquier forma, el interbloqueo es imposible.
Con más de dos procesos
se aplica la misma lógica.
Una variación menor de
este algoritmo es retirar el requerimiento de que los recursos se adquieran en
una secuencia cada vez más estricta, y simplemente insistir que ningún proceso
puede solicitar un recurso menor del que ya contiene.
Los diversos métodos
para evitar el interbloqueo se definen en la siguiente imagen:
Bloqueo de dos fases
Aunque los métodos para
evitar y prevenir los interbloqueos no son muy prometedores en el caso general,
para aplicaciones específicas se conocen muchos algoritmos excelentes de
propósito especial. Como ejemplo, en muchos sistemas de bases de datos, una
operación que ocurre con frecuencia es solicitar bloqueos sobre varios
registros y después actualizar todos los registros bloqueados. Cuando hay
varios procesos en ejecución al mismo tiempo, hay un peligro real de
interbloqueo.
Este método se le
conoce como bloqueo de dos fases.
El proceso trata de bloquear todos los registros que necesita, uno a la vez.
Si tiene éxito pasa a
la segunda fase, realizando sus actualizaciones y liberando los bloqueos. No se
realiza ningún trabajo real en la primera fase.
Si durante la primera
fase se necesita cierto registro que ya esté bloqueado, el proceso sólo libera todos
sus bloqueos e inicia la primera fase desde el principio.
Interbloqueos de comunicaciones
Otro tipo de
interbloqueo puede ocurrir en los sistemas de comunicaciones (como las redes),
en donde dos o más procesos se comunican mediante el envío de mensajes.
Un arreglo común es que
el proceso A envía un mensaje de petición al proceso B, y después
se bloquea hasta que B envía de vuelta un mensaje de respuesta. Suponga
que el mensaje de petición se pierde. A se bloquea en espera de la
respuesta. B se bloquea en espera de una petición para que haga algo.
Tenemos un interbloqueo.
Los interbloqueos de
comunicación no se pueden evitar mediante el ordenamiento de recursos (ya que
no hay ninguno), ni se puede evitar mediante una programación cuidadosa (ya que
no hay momentos en los que se puede posponer una petición). Por fortuna hay
otra técnica que por lo general se puede utilizar para romper los interbloqueos
de comunicación: los tiempos de espera. En la mayoría de los sistemas de
comunicación de red, cada vez que se envía un mensaje del que se espera una
respuesta, también se inicia un temporizador. Si el temporizador termina su
conteo antes de que llegue la respuesta, el emisor del mensaje asume que éste
se ha perdido y lo envía de nuevo (una y otra vez, si es necesario). De esta
forma se evita el interbloqueo.
Bloqueo activo
Esta estrategia se
utiliza a menudo cuando se va a usar la exclusión mutua por un tiempo muy
corto, y la sobrecarga de la suspensión es grande en comparación con realizar
el trabajo. Considere una primitiva atómica en la que el proceso que llama
prueba un mutex y lo sostiene o devuelve una falla.
El bloqueo activo puede
ocurrir en formas sorprendentes. En algunos sistemas, el número total de
procesos permitidos se determina con base en el número de entradas en la tabla
de procesos.
Así, las entradas de la
tabla de procesos son recursos finitos. Si una operación fork falla debido a que
la tabla está llena, un método razonable para el programa que realiza la
operación fork es esperar un tiempo aleatorio y probar de nuevo.
Inanición
Un problema muy
relacionado con el interbloqueo y el bloqueo activo es la inanición. En un sistema dinámico, las
peticiones de recursos ocurren todo el tiempo. Se necesita cierta política para
decidir acerca de quién obtiene qué recurso y cuándo. Esta política, aunque
parece razonable, puede ocasionar que ciertos procesos nunca reciban atención,
aun cuando no estén en interbloqueo.
Un posible algoritmo de
asignación es otorgar la impresora al proceso con el archivo más pequeño a
imprimir
Este método maximiza el
número de clientes satisfechos y parece razonable. Ahora considere lo que
ocurre en un sistema ocupado, cuando un proceso tiene que imprimir un archivo
enorme. Cada vez que la impresora esté libre, el sistema buscará y elegirá el
proceso con el archivo más pequeño.
La inanición se puede
evitar mediante el uso de una política de asignación de recursos del tipo “primero
en llegar, primero en ser atendido”. Con este método, el proceso que espere más
tiempo será el que se atienda primero. A su debido tiempo, cualquier proceso
dado se convertirá en el más antiguo y, por ende, obtendrá el recurso que
necesita.
