1. 5. Modelado de interbloqueos
1.1. Holt (1972) mostró cómo se pueden modelar estas cuatro condiciones mediante el uso de gráficos dirigidos.
1.1.1. Los gráficos tienen dos tipos de nodos: procesos, que se muestran como círculos, y recursos, que se muestran como cuadros
1.1.1.1. 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
1.1.1.2. Es decir: Un arco dirigido de un proceso a un recurso significa que el proceso está actualmente bloqueado, en espera de ese recurso.
2. 5.1. Algoritmo de la avestruz
2.1. Es llamado algoritmo de la avestruz
2.1.1. Es el proceso que ignora las situaciones de bloqueo escondiéndose de ellas como lo hace una avestruz al meter su cabeza en el suelo, los matemáticos lo encuentran imperdonable y dicen que los interbloqueos se deben prevenir a toda costa.
2.1.1.1. 5.1.1 El algoritmo de la avestruz
2.1.1.1.1. Aunque nuestro análisis de los gráficos de recursos ha sido para el caso de un solo recurso de cada tipo, los gráficos de recursos también se pueden generalizar para manejar varios recursos del mismo tipo (Holt, 1972). En general, se utilizan cuatro estrategias para lidiar con los interbloqueos.
3. 5.2 Deteccion y recuperación de un interbloqueo
3.1. 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
3.1.1. 5.2.1 Detección de interbloqueos con un recurso de cada tipo
3.1.1.1. Vamos a empezar con el caso más simple: 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. En otras palabras, estamos excluyendo los sistemas con dos impresoras por el momento.
3.1.1.2. Cualquier proceso que forme parte de un ciclo está en interbloqueo. Si no existen ciclos, el sistema no está en interbloqueo.
3.1.1.3. 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:
3.1.1.3.1. 1. El proceso A contiene a R y quiere a S.
3.1.1.3.2. 2. El proceso B no contiene ningún recurso pero quiere a T.
3.1.1.3.3. 3. El proceso C no contiene ningún recurso pero quiere a S.
3.1.1.3.4. 4. El proceso D contiene a U y quiere a S y a T.
3.1.1.3.5. 5. El proceso E contiene a T y quiere a V.
3.1.1.3.6. 6. El proceso F contiene a W y quiere a S.
3.1.1.3.7. 7. El proceso G contiene a V y quiere a U.
3.1.2. 5.2.2 Detección del interbloqueo con varios recursos de cada tipo
3.1.2.1. Cuando existen varias copias de algunos de los recursos, se necesita un método distinto para detectar interbloqueos.
3.1.2.2. 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.
4. 5.3 Recuperación de un interbloqueo
4.1. 5.3.1 Suponga que nuestro algoritmo de detección de interbloqueos ha tenido éxito y detectó un interbloqueo. ¿Qué debemos hacer ahora? Se necesita alguna forma de recuperarse y hacer funcionar el sistema otra vez.
4.1.1. Recuperación por medio de apropiación
4.1.1.1. 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.
4.1.1.2. 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. Con frecuencia es difícil o imposible recuperarse de esta manera. Elegir el proceso a suspender depende en gran parte de cuáles procesos tienen recursos que se pueden quitar con facilidad.
4.1.2. Recuperación a través del retroceso
4.1.2.1. Si los diseñadores de sistemas y operadores de máquinas saben que es probable que haya interbloqueos, pueden hacer que los procesos realicen puntos de comprobación en forma periódica. Realizar puntos de comprobación en un proceso significa que su estado se escribe en un archivo para poder reiniciarlo más tarde
4.1.2.2. 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.
4.1.2.3. Para que sean más efectivos, los nuevos puntos de comprobación no deben sobrescribir a los anteriores, sino que deben escribirse en nuevos archivos, para que se acumule una secuencia completa a medida que el proceso se ejecute.
4.1.2.4. Cuando se detecta un interbloqueo, es fácil ver cuáles recursos se necesitan. 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
4.1.3. Recuperación a través de la eliminación de procesos
4.1.3.1. 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
4.1.3.2. 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.
4.1.3.3. Donde sea posible, es mejor eliminar un proceso que se pueda volver a ejecutar desde el principio sin efectos dañinos.
5. 6. Como evitar los interbloqueos
5.1. Sin embargo, en la mayoría de los sistemas los recursos se solicitan uno a la vez. El sistema debe ser capaz de decidir si es seguro otorgar un recurso o si no lo es, y realizar la asignación sólo cuando sea seguro.
5.1.1. 6.1 Trayectorias de los recursos
5.1.1.1. Los principales algoritmos para evitar interbloqueos se basan en el concepto de los estados seguros.
5.1.1.2. Los principales algoritmos para evitar interbloqueos se basan en el concepto de los estados seguros.
5.1.1.3. Aunque el método gráfico no se traduce directamente en un algoritmo utilizable, ofrece una buena sensación intuitiva de la naturaleza del problema.
5.1.2. 6.2 Estados seguros e inseguros
5.1.2.1. 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
5.1.3. 6.3 El algoritmo del banquero para un solo recurso
5.1.3.1. 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.
5.1.3.2. 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.
5.1.3.3. De ser así, se asume que esos préstamos volverán a pagarse y ahora se comprueba el cliente más cercano al límite, etcétera. Si todos los préstamos se pueden volver a pagar en un momento dado, el estado es seguro y la petición inicial se puede otorgar.
5.1.4. 6.4 El algoritmo del banquero para varios recursos
5.1.4.1. El algoritmo del banquero se puede generalizar para manejar varios recursos.
6. Sistemas Operativos I
7. ING: JOSE ANTONIO VASQUEZ NOLASCO
8. Alumno Helmuth Adler Dominguez Alvarado
9. Asignación: "Resumen de Interbloqueos"
10. Nota: El tema principal es el mismo de la asignación cada uno de los sub- temas esta ordenado conforme a un numero provisto según el orden de los contenidos, dentro de cada sub-tema hay párrafos claves del mismo, los mismos están enumerados según su nomenclatura tomando como base el sub-tema: Ejemplo el sub-tema 6 el párrafo seria 6.1 el siguiente seria el 6.2 y así sucesivamente.
11. 1.Que es un interbloqueo en los sistemas operativos
11.1. Se dice que es un interbloqueo ciando dos o mas procesos están suspendidos, en espera de un evento que solo puede ser activado por uno de los procesos bloqueados, y por lo tanto dicho evento nunca sucederá. Para este problema no existe solución.
11.1.1. Ejemplo: Imaginémonos que existen dos procesos que compiten por dos recursos que necesitan para funcionar, que solo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos y el segundo obtiene el otro, cuando el primer proceso intenta utilizar el segundo recurso este ya a sido tomado por el segundo proceso entonces ambos procesos quedan en espera. Por ende los interbloqueos pueden ocurrir tanto en el hardware como en el software
12. 2.Recursos
12.1. 2.1 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. Los recursos en los interbloqueos pueden ser de dos tipos hardware y software. En el hardware puede ser: una unidad de cinta, y en el software puede ser: informacion como un registro bloqueado en la base de datos.
12.2. 2.2 Recursos apropiativos y no apropiativos.
12.2.1. Recursos 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.
12.2.2. 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.
12.3. Como se involucran los bloqueos en los recursos apropiativos y no apropiativos
12.3.1. 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.
12.4. La secuencia de eventos requerida para utilizar un recurso:
12.4.1. 1. Solicitar el recurso.
12.4.2. 2. Utilizar el recurso.
12.4.3. 3. Liberar el recurso.
12.5. 2.3 Adquisición de recursos:
12.5.1. 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.
13. 3. Introducción a los interbloqueos
13.1. Como ya lo hemos mencionado los interbloqueos se pueden definir como: 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.
13.2. 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. Es probablemente el tipo más común, pero no el único.
14. 4. Condiciones para los interbloqueos
14.1. Coffman y colaboradores (1971) mostraron que deben aplicarse cuatro condiciones para un interbloqueo de recursos estas condiciones son:
14.1.1. 1. Condición de exclusión mutua. Cada recurso se asigna en un momento dado a sólo un proceso, o está disponible.
14.1.2. 2. Condición de contención y espera. Los procesos que actualmente contienen recursos que seles otorgaron antes pueden solicitar nuevos recursos.
14.1.3. 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.
14.1.4. 4. Condición de espera circular. Debe haber una cadena circular de dos o más procesos, cadauno de los cuales espera un recurso contenido por el siguiente miembro de la cadena.
14.1.4.1. Las cuatro condiciones deben estar presentes para que ocurra un interbloqueo. Si una de ellas está ausente, no es posible el interbloqueo de recursos
15. 6. Como evitar los interbloqueos
15.1. Otras cuestiones
15.1.1. 6.5 Bloqueo de dos fases
15.1.1.1. 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.
15.1.1.2. A menudo, a este método se le conoce como bloqueo de dos fases. En la primera fase, 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.
15.1.1.3. 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. En cierto sentido este método es similar a solicitar todos los recursos que necesita de antemano, o al menos antes de realizar algo irreversible. En ciertas versiones del bloqueo de dos fases, no hay liberación y reinicio si se encuentra un registro bloqueado durante la primera fase. En estas versiones puede ocurrir un interbloqueo.