• Author / Uploaded
• Sherman Pérez

• Categories
• Proceso (Computación)
• Algoritmos
• Sistema operativo
• Ingeniería Informática
• Áreas de informática

Citation preview

1

UNIVERSIDAD NACIONAL TECNOLÓGICA DE LIMA SUR FACULTAD DE INGENIERÍA Y GESTIÓN Escuela Académico Profesional de Ingeniería de Sistemas

LOGO

SEGURIDAD INFORMÁTICA

Trabajo presentado en cumplimiento parcial de la materia de Sistemas de Tiempo Real

Por: Juan Perez Luna

Ciudad Universitaria 2018

2

DEDICATORIA

Trabajo de investigación dedicado a nuestros padres que supieron inculcarnos valores y principios, además por ser el motor que nos impulsa a siempre superarnos.

3

TABLA DE CONTENIDO

4

LISTA DE FIGURAS

5

LISTA DE TABLAS

6

INTRODUCION

7

Abrazo mortal o Interbloqueo mutuo Definición: Cuando un proceso de un sistema de multiprogramación espera en balde a que se presente un evento específico, se dice que se encuentra en un estado de interbloqueo o bloqueo mutuo. Los procesos que pueden encontrase en esta situación pueden ser uno o varios. En los sistemas de multiprogramación, compartir recursos es uno de los principales objetivos del sistema operativo. Cuando se comparten recursos entre una población de usuarios o procesos, cada uno de los cuales mantiene un control exclusivo sobre ciertos recursos asignados a él, es posible que se produzcan bloqueos mutuos que impedirán la terminación de algunos de los procesos del sistema. Todos los interbloqueos suponen demandas contradictorias de recursos por parte de dos o más procesos. La figura 5.1 ilustra este conflicto de forma abstracta en el caso de dos procesos y dos recursos. Los dos ejes del diagrama representan el avance de los dos procesos en términos de instrucciones ejecutadas. El avance conjunto de los dos procesos se representa entonces con una secuencia discreta de puntos en el espacio. Las líneas horizontales o

8

verticales representan el intervalo de tiempo en el que sólo uno de los procesos está ejecutándose (intercalado); una línea diagonal significa ejecución simultánea (solapamiento). Supóngase que existe un punto en la ejecución de cada proceso en el que se requiere el uso exclusivo de ambos recursos, R1 y R2, para continuar. En el ejemplo, llega un punto en el que el proceso P1 ha adquirido el recurso R1 y el proceso P2 ha adquirido el recurso R2, y cada proceso necesita el otro recurso. Este es el punto de interbloqueo. En este tema se analizará el problema del interbloqueo y las distintas alternativas de solución que se pueden adoptar clasificadas en las siguientes cuatro áreas : prevención, evitación, detección y recuperación del bloqueo mutuo. Para cada una de las estrategias adoptadas, se analizará el equilibrio entre la sobrecarga debida a los mecanismos de corrección del interbloqueo y los beneficios que reportan. En algunos casos es excesivo el precio (gasto extra) que hay que pagar para conseguir a toda costa que no se produzcan interbloqueos. Sin embargo, en algunos casos, como en los sistemas de tiempo real, no hay más alternativa que pagar el precio, ya que puede resultar catastrófico permitir la posibilidad de un bloqueo mutuo. Un problema afín : el aplazamiento indefinido

En cualquier sistema que mantenga los procesos en espera mientras se les asigna un recurso o se toman decisiones de planificación, la programación de un proceso puede postergarse indefinidamente mientras otro recibe la atención del sistema. Tal situación se conoce con varios nombres, entre los que se incluyen aplazamiento indefinido, bloqueo indefinido e inanición, y puede resultar tan peligrosa como el interbloqueo. El aplazamiento indefinido puede ocurrir debido a predisposiciones en las políticas de

planificación de recursos del sistema. Cuando los recursos se planifican por prioridad, es

9

posible que un proceso dado espere de forma indefinida un recurso porque siguen llegando otros procesos con mayor prioridad. Los sistemas deben diseñarse para administrar los procesos en espera de manera justa además de eficiente. En algunos sistemas, el aplazamiento indefinido se evita aumentando la prioridad del proceso mientras espera (técnica de envejecimiento). En algún momento la prioridad de ese proceso superará la prioridad de los entrantes y el proceso en espera será atendido. Casos de Interbloqueos El caso más simple de interbloqueo sería el de un sólo proceso que espera la ocurrencia de un evento y, sin embargo, el sistema no incluye la posibilidad de señalar dicha ocurrencia. Es muy difícil detectar los bloqueos mutuos de esta naturaleza. La mayor parte de los bloqueos mutuos implican una competencia entre varios procesos por varios recursos. Holt (1972) utilizó grafos dirigidos para representar situaciones de interbloqueo. Estos grafos tienen dos tipos de nodos : procesos, que se representan con círculos, y recursos, representados por cuadrados. Si in proceso está utilizando un recurso, previamente solicitado y concedido, se traza un arco desde el nodo del recurso (cuadrado) hasta el proceso (círculo). En la figura 2, el recurso R está en ese momento asignado al proceso A. En b), el proceso B está solicitando el recurso s. Por último en c) se representa un situación de interbloqueo : el proceso C está a la espera del recurso T, que está asignado al proceso D. El proceso D no ha dejado T, porque está esperando a que quede libre el recurso U, que, a su vez, está siendo utilizado por C. Ambos esperarán indefinidamente.

10

El siguiente ejemplo servirá para ilustrar el empleo de grafos de recursos. Supongamos que tenemos tres procesos, A, B y C, y tres recursos, R, S, y T. La figura 5.2 representa las secuencias de petición y liberación que realizan los tres procesos. El sistema operativo tiene en todo momento completa libertad para ejecutar cualquiera de los procesos que no estén bloqueados, así que, por ejemplo, podría decidirse a ejecutar A hasta que éste terminara su trabajo, después B hasta que acabe y, finalmente C. Este secuenciamiento no produce interbloqueo, ( ya que no se compite por los recursos), pero suprime completamente el paralelismo. Además de pedir y liberar recursos, los procesos también realizan E/S y procesamiento de datos. Si se ejecutan uno tras otro, se elimina completamente la posibilidad de que, mientras uno de ellos está esperando que acabe una E/S, otro pueda utilizar el procesador. Supongamos, sin embargo, que los procesos realizan tanto E/S como procesamiento de datos, de forma que la planificación por turno rotatorio es la más adecuada. En este caso, la secuencia de petición de recursos podría ser la representada en la figura 3 (d). Si las seis peticiones se llevan a cabo en ese orden, se producirían los seis grafos de los casos (e)-(j).

11

Después de la petición 4, A está bloqueado en espera de captar S, como se muestra en (h). Los procesos B y C se bloquean en las dos etapas siguientes, lo que conduce finalmente a un bucle cerrado y al correspondiente interbloqueo representado en (j).

Ejemplo de Interbloqueo y como evitarlo.

12

El sistema operativo no está obligado a ejecutar los procesos en ningún orden en particular. En concreto, si la concesión de un recurso a un proceso determinado puede provocar interbloqueo, el sistema operativo es muy libre de suspender al proceso y no atender su petición hasta que esté seguro de que esto no conduce a una situación problemática. En la figura 5.3, por ejemplo, si el sistema operativo supiera que se avecinaba un interbloqueo, podría decidir suspender al proceso B antes de concederle el recurso S. La ejecución sólo de los procesos A y C produciría las secuencias de petición y liberación de la figura 5.3 (k), en lugar de las de la figura 5.3 (d). Esta secuencia de ejecución produce los grafos de recursos (l)(q), y no produce interbloqueo. Después de la etapa (q), no hay ningún problema en conceder S a B, ya que A ha terminado y C tiene todo lo que necesita. Aunque B se bloqueara al solicitar T, no se produciría interbloqueo; B simplemente esperaría hasta que terminara C.

Condiciones Necesarias para Producir un Interbloqueo [DEIT93] [MILE94] [STAL95]

Coffman, Elphick y Shoshani (71) establecen que deben darse las siguientes cuatro condiciones necesarias para que ocurra un bloqueo mutuo. Condición de exclusión mutua : los procesos exigen un control exclusivo de los recursos que necesitan. Condición de espera : los procesos mantienen la posesión de los recursos ya asignados a ellos mientras esperan recursos adicionales.

13

Condición de no apropiación : los recursos no pueden arrebatarse a los procesos a los cuales están asignados hasta que termine su utilización. Condición de espera circular : existe una cadena circular de procesos en la que cada proceso tiene uno o más recursos que son requeridos por el siguiente proceso en la cadena. Como dichas condiciones son necesarias para que se presente un interbloqueo, la existencia de un bloqueo mutuo implica que se han dado todas y cada una de las cuatro condiciones. Como se verá más adelante, tener en mente semejante observación será de gran ayuda para desarrollar esquemas que eviten los interbloqueos. Estrategias para Resolver Interbloqueos [DEIT93] [STAL95] Los resultados de la investigación sobre el bloqueo mutuo han sido satisfactorios en cuanto a que se han encontrado métodos limpios y rápidos para manejar la mayoría de los problemas más comunes. Existen cuatro áreas de interés relacionadas con los interbloqueos que pueden resumirse como prevención, técnicas para evitarlos, detección y recuperación de los mismos. En la prevención del interbloqueo interesa ajustar el sistema para eliminar toda posibilidad de que ocurra un bloqueo mutuo. La prevención suele funcionar pero sus métodos ocasionan, en general, un aprovechamiento pobre de los recursos. No obstante, estos métodos se utilizan con frecuencia. Las técnicas que tienen como objetivo evitar el interbloqueo imponen condiciones menos atractivas que en la prevención, para tratar de obtener un aprovechamiento de los recursos. No elimina como las técnicas de prevención todas las posibilidades de que se produzca un bloqueo mutuo, pero se esquiva cuanto está a punto de suceder (algoritmo del banquero de Dijkstra).

14

Los métodos de detección del interbloqueo es utilizan en sistemas que permiten la ocurrencia de los mismos, ya sea de manera voluntaria o involuntaria. Su objetivo es determinar si ha ocurrido un bloqueo mutuo y saber exactamente cuáles son los procesos y recursos implicados en él. Los métodos de recuperación están íntimamente ligados a los de detección. Sirven para eliminar los interbloqueos detectados en un sistema para poder seguir trabajando y para que los procesos implicados puedan terminar su ejecución y liberen sus recursos. La recuperación es un problema complejo, en el mejor de los casos, los sistemas se recuperan de un bloqueo mutuo eliminando completamente uno o varios de los procesos implicados. Después, se inician de nuevo los procesos eliminados, perdiéndose la mayor parte o todo el trabajo previo realizado por el proceso. Desentenderse. El Algoritmo de la Avestruz [TANE93] La estrategia más sencilla es el algoritmo del avestruz : esconder la cabeza bajo tierra y pretender que el problema no existe. La gente reacciona a esta estrategia de distintos modos según su formación. Los matemáticos consideran que es inaceptable y argumentan que los interbloqueos se deben evitar a toda costa. Los ingenieros se interrogan sobre la frecuencia del problema, la frecuencia con el que el sistema se para por otras causas y la importancia de los interbloqueos. Si éstos se presentan de una vez cada cinco años, y los sistemas se paran una vez al mes por errores en el hardware, en el compilador o en el sistema operativo, a casi ningún ingeniero le gustaría tener que sufrir una degradación seria de las prestaciones del sistema para garantizar la eliminación de los interbloqueos. Por ejemplo, Unix pude sufrir interbloqueos que ni siquiera se detectan, y que, por supuesto, no se eliminan automáticamente. El número total de procesos en el sistema viene determinado por el número de posiciones de la tabla de procesos, que, en definitiva,

15

constituye un recurso limitado. Supongamos ahora que un sistema Unix con 100 posiciones en la tabla de procesos tiene ejecutándose diez programas, cada uno de los cuales ha de crear 12 subprocesos. Después de que cada proceso haya creado otros 9, los 10 procesos originales y los 90 nuevos llenarán por completo la tabla. Los 10 procesos originales se encontrarán ahora en un bucle infinito intentando crear un nuevo proceso sin poder : se ha producido un interbloqueo. Otros ejemplos de recursos que suelen ser limitados son : el número máximo de ficheros que pueden estar abiertos está limitado, el área en el disco para intercambio con

memoria principal. En realidad, casi todas las tablas del sistema operativo representan recursos limitados, ¿deberíamos, por tanto, limitar estos recursos para no producir un interbloqueo? La estrategia UNIX es simplemente desentenderse del problema, suponiendo que la mayoría de los usuarios preferirán un interbloqueo ocasional antes que la imposición de que cada usuario pueda crear un solo proceso, abrir un solo fichero y usar sólo una unidad de lo que sea. Veremos a continuación que se puede adoptar alguna estrategia adecuada que nos permitirá prevenir, evitar o detectar y recuperar situaciones de interbloqueo. Prevención de Interbloqueos La estrategia empleada con más frecuencia por los diseñadores para tratar el bloqueo mutuo es la prevención. En esta sección se examinan los métodos de prevención, junto con los efectos que tienen sobre los usuarios y los sistemas, sobre todo desde la perspectiva del rendimiento. Havender (68) llegó a la conclusión de que si falta alguna de las cuatro condiciones necesarias no puede haber un interbloqueo. Este autor sugiere las siguientes estrategias para negar varias de esas condiciones :

16

Cada proceso deberá pedir todos sus recursos al mismo tiempo y no podrá seguir la ejecución hasta haberlos recibido todos. Si a un proceso que tiene recursos se le niegan los demás, ese proceso deberá liberar sus recursos y, en caso necesario, pedirlos de nuevo junto con los recursos adicionales. Se impondrá un ordenamiento lineal de los tipos de recursos en todos los procesos ; es decir, si a un proceso le han sido asignados recursos de un tipo específico, en lo sucesivo sólo podrá pedir aquellos recursos que siguen en el ordenamiento. Como vemos Havender presenta tres estrategias y no cuatro. Cada una de ellas, está diseñada para negar una de las condiciones necesarias. La primera de estas condiciones, esto es, que los procesos exijan el uso exclusivo de los recursos que requieren, es una condición que no es deseable impedir, porque específicamente queremos permitir la existencia de recursos no compartibles o dedicados. Negación de la condición de espera La primera de las estrategias requiere que los recursos que necesita un proceso sean pedidos de una sola vez. El sistema debe proporcionarlos según el principio de todo o nada. Si está disponible el conjunto de los recursos que necesita un proceso, entonces el sistema puede asignarle todos los recursos y éste seguir su ejecución. Si no está disponible alguno de ellos, el proceso debe esperar. Mientras espera no puede tener ningún recurso. Con esto se elimina la condición de espera y no puede ocurrir un interbloqueo. Todo esto suena bien, pero puede llevar a un grave desperdicio de recursos. Supongamos que un proceso necesita diez unidades de un determinado recurso para su ejecución. Como debe solicitarlas todas antes de comenzar, los mantendrá en su poder durante toda su

17

ejecución. Pudiera suceder, que el programa únicamente utilice estos recursos al principio de su ejecución, por tanto, los recursos están ociosos el resto del tiempo. Dividir el programa en varios pasos que se ejecuten de manera relativamente independiente es una técnica empleada con frecuencia para conseguir una mejor utilización de los recursos en estas circunstancias. La asignación de recursos se controla por etapas. Esta solución reduce el desperdicio pero implica mucho trabajo extra tanto en el diseño de las aplicaciones como en al ejecución. Por otro lado, esta estrategia puede provocar un aplazamiento indefinido, pues los recursos requeridos pueden no estar disponibles todos al tiempo. El sistema podría, entonces, permitir que se fueran acumulando recursos hasta conseguir todos los que necesita un proceso. Pero mientras se acumulan no se pueden asignar a otros procesos y volvemos a infrautilizarlos. Negación de la condición de no apropiación La segunda estrategia de Havender consiste en liberar los recursos que un proceso tiene asignados cuando se le niegan peticiones de recursos adicionales. De esta forma, se anula la condición de no apropiación. Los recursos se pueden quitar al proceso que los tiene antes de que termine su ejecución. En este caso también existe un costo excesivo. Cuando un proceso libera recursos puede perder todo el trabajo realizado hasta ese momento. El costo puede parecer muy alto, pero la pregunta es : ¿con qué frecuencia ha de pagarse ese precio ? Si ocurre de tarde en tarde, entonces éste parece ser un buen método para prevenir el interbloqueo. Si, por el contrario, es muy frecuente, entonces el costo es sustancial y sus efectos demasiado perjudiciales (por ejemplo, para procesos de alta prioridad o plazo fijo).

18

Esta estrategia también adolece de aplazamiento indefinido. Un proceso puede aplazarse continuamente mientras pide y libera muchas veces los mismo recursos. Si esto ocurre, el sistema puede verse obligado a eliminar el proceso para que otros puedan ejecutarse. Negación de la condición de espera circular La tercera estrategia de Havender anula la posibilidad de un espera circular. Como todos los recursos tienen una numeración única y como los procesos deben pedir los recursos en un orden lineal ascendente, es imposible que se presente una espera circular (figura 5.4). Esta estrategia presenta las siguientes dificultades : Los recursos deben pedirse en un orden ascendente por número de recursos. El número de recurso es asignado por la instalación y debe tener un tiempo de vida largo (meses o años) . Si se agregan nuevos tipos de recursos, puede ser necesario reescribir los programas y los sistemas. Lógicamente, cuando se asignan los números de recursos, éstos deben reflejar el orden normal en que los usan la mayoría de las tareas. Pero los procesos que necesiten los recursos en un orden diferente que el previsto por el sistema, los deberán adquirir y conservar, quizá durante tiempo antes de utilizarlos realmente, lo que significa un desperdicio considerable. Una de las metas más importantes de los sistemas operativos actuales es crear ambientes amables con el usuario. Los usuarios deben ser capaces de desarrollar sus aplicaciones sin tener en cuenta molestas restricciones de hardware y software. El ordenamiento lineal impide al usuario escribir sus códigos libremente.

19

Evitación de Interbloqueos [TANE93] Aún presentándose las condiciones para un interbloqueo, todavía es posible evitarlo mediante una asignación cuidadosa de los recursos. Tal vez el algoritmo más famoso para evitar el interbloqueo sea el algoritmo del banquero de Dijkstra (73), cuyo interesante nombre se debe a que atañe a un banquero que otorga préstamos y recibe pagos a partir de una determinada fuente de capital. Algoritmo del Banquero En principio, estudiaremos este algoritmo suponiendo que todos los recursos del mismo tipo. Considérese la asignación de una cantidad t, de unidades de cintas idénticas.

20

Un sistema operativo comparte un número fijo, t, de unidades de cinta entre un número fijo de, p, de procesos. Cada proceso especifica por adelantado el número máximo de unidades de cinta que necesitará durante su ejecución. El sistema operativo aceptará la petición de un usuario si la necesidad máxima de ese proceso no es mayor que t. Un proceso puede obtener o liberar unidades de cinta una a una. Algunas veces un usuario puede verse obligado a esperar para obtener una unidad adicional, pero el sistema operativo garantiza una espera finita. El número real de unidades asignadas a un proceso nunca será superior a la necesidad máxima declarada por ese usuario. Si el sistema operativo es capaz de satisfacer la necesidad máxima del proceso, entonces éste debe garantizar al sistema operativo que las unidades de cinta serán utilizadas y liberadas en un tiempo finito. Se dice que el estado del sistema es seguro si el sistema operativo puede garantizar que todos los procesos terminan en un tiempo finito. En otro caso, el sistema está en un estado inseguro. Sea préstamo (i) la representación del préstamo actual de unidades de cinta para el proceso i. Sea máx(i) la necesidad máxima de cintas de un proceso y, por último, sea petición (i) la petición actual del usuario, que es igual a su necesidad máxima menos el préstamo actual. Por ejemplo, el proceso 7 tiene una necesidad máxima de 6 unidades y un préstamo actual de 5, entonces tiene petición(7) = máx(7) - préstamo(7) = 6 - 5 = 2 El sistema operativo controla t unidades de cinta. Sea a el número de unidades de cinta todavía disponibles para asignar. Entonces a es igual a t menos la suma de los préstamos de los usuarios. El algoritmo del banquero permite la asignación de unidades de cinta a los usuarios solamente cuando la asignación conduzca a estados seguros, y no a estados inseguros. Un

21

estado seguro es una situación tal en la que todos los procesos son capaces de terminar en algún momento. Un estado inseguro es aquel en el cual puede presentarse un bloqueo mutuo. Algoritmo del banquero para múltiples recursos

La figura 5.5 representa dos matrices. La de la izquierda muestra el número de recursos asignados en ese instante (préstamo actual) a cada uno de los cinco procesos. En la derecha aparece el número de recursos que todavía necesita cada proceso para llevar a cabo su función (petición). Al igual que el caso de un único recurso, los procesos deben comunicar sus necesidades máximas antes de empezar a ejecutarse, de forma que en todo momento el sistema pueda calcular la matriz de la derecha. Para describir los recursos existentes en el sistema, los que están en posesión y los que están disponibles, emplearemos tres vectores como los siguientes : E =(6342), P=(5322) y D=(1020). E indica que el sistema tiene 6 unidades de cinta, 3 trazadores, 4 impresoras y 2 cdrom. De ellos se están utilizando 5 unidades de cinta, tres trazadores gráficos, dos impresoras y dos cdrom. Esto se puede deducir sin más que sumar las cuatro columnas de recursos en préstamo de la matriz izquierda. El vector de recursos disponibles es simplemente la diferencia ente lo que el sistema tiene y lo que está usando en ese momento. Ahora estamos en condiciones de describir en qué consiste el algoritmo de comprobación de estado seguro :

22

1.-Buscar una fila, F, cuyas necesidades de recursos sean menores o iguales a D. Si no existe tal fila, el sistema puede interbloquearse, ya que ningún proceso puede ejecutarse hasta el final. 2.-Suponer que el proceso de la fila seleccionada solicita todos los recursos que necesita, y termina. Marcar el proceso como terminado y añadir sus recursos al vector D. 3.-Repetir las etapas 1 y 2 hasta que se vayan marcando todos los procesos como terminados (en cuyo caso el estado inicial era seguro) o hasta que se llegue a una situación de interbloqueo (en cuyo caso no lo era). En el caso de que se pueda seleccionar más de un proceso en el paso 1, la elección sería indiferente: en cualquier caso, el conjunto de recursos disponibles aumenta o, en el peor de los casos, se queda igual. Volviendo al ejemplo de la figura 5.5 . El estado actual es seguro. Supongamos que el proceso B solicita la impresora. Dado que el estado resultante es todavía seguro, esta petición puede concederse (el proceso D puede terminar, seguido por los procesos A o E y a continuación el resto). Imaginemos ahora que, después de que B obtiene una de las dos impresoras restantes, E solicita la última impresora. Si se le concede esta petición, el vector de recursos disponibles se reduciría a (1 0 0 0), situación que produce interbloqueo. Por lo tanto, la petición de E debe posponerse de momento. Ahora debe estar claro cómo opera el algoritmo del banquero de Dijkstra cuando asigna recursos. Están permitidas las condiciones de espera circular, espera y no apropiación, pero los procesos sí exigen el uso exclusivo de los recursos que requieren. Los procesos pueden conservar recursos mientras piden y esperan recursos adicionales y los recursos no pueden

23

arrebatarse a los procesos que los tienen. Los procesos facilitan el trabajo al sistema pidiendo un solo recurso a la vez. El sistema puede satisfacer o rechazar cada petición. Si una petición es rechazada, el proceso conserva los recursos que ya tiene asignados y espera un tiempo finito a que se satisfaga la petición. El sistema sólo satisface peticiones que llevan a estados seguros. Una petición que condujese a un estado inseguro se rechazaría repetidamente hasta que pueda quedar satisfecha. Como el sistema se mantiene en un estado seguro, tarde o temprano (en un tiempo finito) todas las peticiones podrán ser atendidas y los procesos terminarán. Defectos del algoritmo del banquero El algoritmo del banquero es interesante porque ofrece una forma de asignar los recursos que evita el interbloqueo. Permite ejecutar procesos que tendrían que esperar seguramente con alguna de las estrategias de prevención. Sin embargo, tiene varios defectos importantes : El algoritmo requiere un número fijo de recursos asignables. Como los recursos a menudo requieren servicio, ya sea por algún fallo o por mantenimiento preventivo, no se puede contar con que será siempre constante. El algoritmo requiere una población de usuarios constantes. En los sistemas multiprogramables y más en los de tiempo compartido, la población de usuarios cambia constantemente, incluso en cuestión de segundos. El algoritmo requiere que el banquero satisfaga todas las peticiones en un tiempo finito. Es evidente que en los sistemas reales esto no es una garantía suficiente. De manera similar, el algoritmo requiere que los procesos salden sus préstamos (es decir, devuelvan sus recursos) en un tiempo finito. Una vez más, esto es insuficiente para un sistema de tiempo real.

24

El algoritmo requiere que los usuarios declaren por anticipado sus necesidades máximas. A medida que la asignación de recursos se hace más dinámica, conocer las necesidades máximas de un usuario presenta mayor dificultad. De hecho, ahora que los sistemas ofrecen interfaces gráficas, cada vez es más común que los usuarios no tengan la menor idea de los recursos que necesitan. En resumen, los métodos descritos anteriormente en el apartado de prevención son demasiado restrictivos, mientras que los de evitación que acabas de estudiar requieren información de la que, generalmente, no se dispone. Detección y Recuperación de Interbloqueos La detección del bloqueo mutuo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos y recursos implicados en él. Los algoritmos de detección determinan por lo general si existe una espera circular. El empleo de algoritmos de detección del interbloqueo implica cierto gasto extra durante la ejecución. Así pues, se presenta de nuevo la cuestión de costeabilidad, tan habitual en los sistemas operativos, ¿el gasto extra debido a los algoritmos de detección del bloqueo mutuo se justifica con los ahorros potenciales debidos a la localización y solución de los interbloqueos? Para facilitar la detección de interbloqueos, se utilizará una notación en la que un grafo dirigido indica las asignaciones y peticiones de recursos. Los cuadrados representan procesos; los círculos grandes, clases de dispositivos idénticos; los círculos pequeños de color rojo en el interior de los grandes indican el número de dispositivos de cada clase. Por ejemplo, si un círculo grande etiquetado como R1 contiene tres círculos pequeños, significa que ya tres recursos del tipo R1 disponibles para asignación en este sistema.

25