Manejo de Bloqueos Mútuos
-
Upload
natalia-ludena -
Category
Documents
-
view
4.525 -
download
1
description
Transcript of Manejo de Bloqueos Mútuos
Sistemas Operativos
MANEJO DE BLOQUEOS MUTUOS
Integrantes Natalia LudeñaAndrea Novillo Keyner Abarca
Prevención De Bloqueos MutuosTodos los recursos del sistema se les asigna un número único i sólo si no está reteniendo un recurso con un número único mayor que i. De manera similar, podemos utilizar el algoritmo de evitación de bloqueos mutuos.Para controlar la apropiación, se asigna un número de prioridad único a cada proceso
Se utiliza los números si un proceso Pi deberá esperar a un proceso Pj Ejemplo podemos hacer que Pi espere a Pj si tiene una prioridad mayor que la de PJ en caso contrario se retrocede a Pi .Una dificulta con este esquema es la posibilidad de inanición
El esquema espera – morir
Se basa en una técnica no apropiativa.Cuando el proceso Pi solicita un recursos que actualmente está retenido por Pj a Pi se le permite esperar sólo si tiene una marca de tiempo menor que Pj. En caso contrario Pi retrocede
El esquema herir – esperar
Se basa en un técnica apropiativa es una contraparte del método anterior. Cuando el proceso Pi solicita un recursoque actualmente esta retenido por Pj a Pi, se permite esperar sólo si tiene una marca de tiempo mas grande que Pj. En caso contrario Pj retrocede
Diferencias
En el esquema espera-morir, un proceso más antiguo debe esperar a que un proceso mas joven libere su recurso. Entre mas viejo se hace el proceso, más tiende a esperar
En el esquema herir-esperar, un proceso mas viejo, nunca espera a un mas joven
Impide apropiación de recursos innecesarios. Mediante un algoritmo de detección de bloqueos
mutuos. Construye una gráfica de espera que describa el
estado de la asignación de recursos. Un algoritmo para detectar un ciclo en una
gráfica requiere de n2 operaciones, donde n es el número de vértices en la gráfica.
¿Cómo mantener la gráfica en un sistema distribuido?
Cuando un proceso Pi en el sitio A necesita un recurso retenido por el proceso Pj en el sitio B, Pi envía un mensaje de solicitud al sitio B.
La arista Pi->Pj se inserta entonces en la gráfica de espera local del sitio B.
Si cualquier gráfica de espera local tiene un ciclo, ha ocurrido un bloqueo mutuo.
El hecho de que no haya ciclos en cualquiera de las gráficas de espera locales no significa que no haya bloqueos mutuos.
Para probar un bloqueo mutuo, debemos demostrar que la unión de las gráficas locales es acíclica.
Existen diversos métodos para organizar la gráfica de espera en un sistema distribuido.
Se construye una gráfica de espera global: unión de las locales.
Se mantiene en un proceso único: el coordinador de detección de bloqueos mutuos.
Gráficas de espera: real y construida.
Para construir la gráfica de espera:
Siempre que se inserte o remueva una nueva arista en una de las gráficas locales.
Periódicamente, cuando hayan ocurrido varios cambios en una gráfica.
Siempre que el coordinador necesite invocar al algoritmo de detección de ciclos.
Cuando se invoca al algoritmo de detección de bloqueos mutuos, el coordinador busca en su gráfica global. Si encuentra un ciclo, se selecciona una víctima para su retroceso. El coordinador debe notificar a todos los sitios que se ha seleccionado un proceso particular como víctima.
Pueden ocurrir retrocesos innecesarios, como resultado de 2 situaciones:
1. Ciclos falsos2. Ocurre Bloqueo mutuo y se ha escogido víctima, pero al
mismo tiempo unos de los procesos fue abortado por otras razones.
Algoritmo centralizado para detección de bloqueos mutuos
Para evitar el reporte de bloqueos falsos, requerimos que las solicitudes de diferentes sitios se anexen con identificadores únicos o marcas de tiempo
1. El controlador envía un mensaje de inicio a cada sitio en el sistema.
2. Al recibir este mensaje, un sitio envía su gráfica de espera local al coordinador.
3. Cuando el controlador ha recibido una respuesta de cada sitio construye una gráfica:
1. Vértice para cada proceso2. Arista-etiqueta TS