Capitulo 6 - Resumen Sistemas operativos PDF

Preview

Summary

INTERBLOQUEOS6.1 Recursos apropiativos y no apropiativosUn 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).Un recurso apropiativo es uno que se puede quitar al proceso que lo posee sin efecto...

Description

INTERBLOQUEOS 6.1.1 Recursos apropiativos y no apropiativos

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). Un recurso apropiativo es uno que se puede quitar al proceso que lo posee sin efectos dañinos. Por el contrario, 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. Los grabadores de CD no son apropiativos en un momento arbitrario. 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. 6.1.2 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.

6.2 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. 6.2.1 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.

6.2.2 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 y recursos. En general, se utilizan cuatro estrategias para lidiar con los interbloqueos. 1. Sólo ignorar el problema. Tal vez si usted lo ignora, él lo ignorará a usted.

2. Detección y recuperación. Dejar que ocurran los interbloqueos, detectarlos y tomar acción. 3. Evitarlos en forma dinámica mediante la asignación cuidadosa de los recursos. 4. Prevención, al evitar estructuralmente una de las cuatro condiciones requeridas. 6.3 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. Los matemáticos la encuentran totalmente inaceptable y dicen que los interbloqueos se deben prevenir a toda costa Los ingenieros no están dispuestos a reducir considerablemente el rendimiento por la conveniencia de eliminar los interbloqueos.

6.4.1 Detección de interbloqueos con un recurso de cada tipo

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 6. 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. 6.4.2 Detección del interbloqueo con varios recursos de cada tipo El algoritmo de detección de interbloqueos se basa en la comparación de vectores. 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. Cuando el algoritmo termina, todos los procesos desmarcados (si los hay) están en interbloqueo. 6.4.3 Recuperación de un interbloqueo 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. La habilidad de quitar un recurso a un proceso, hacer que otro proceso lo utilice y después regresarlo sin que el proceso lo note, depende en gran parte de la naturaleza del recurso. 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. 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.

6.5.1 Trayectorias de los recursos

Los principales algoritmos para evitar interbloqueos se basan en el concepto de los estados seguros. 6.5.2 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. 6.5.3 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. 6.5.4 El algoritmo del banquero para varios recursos

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). Si hay varios procesos que pueden elegirse en el paso 1, no importa cuál esté seleccionado: la reserva de recursos disponibles aumentará, o en el peor caso, permanecerá igual. 6.6.1 Cómo atacar la condición de exclusión mutua Evite asignar un recurso cuando no sea absolutamente necesario, y trate de asegurarse que la menor cantidad posible de procesos reclamen ese recurso. 6.6.2 Cómo atacar la condición de contención y espera

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 todo está disponible, 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á.

6.6.3 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. No obstante, con los discos grandes es muy improbable quedarse sin espacio. 6.6.4 Cómo atacar la condición de espera circular

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....