BUENO PRIMERO UNA PEQUEÑA INTRODUCCION MEDIANTE VIDEOS PARA ADENTRARNOS AL TEMA
aqui otro video como apoyo y referencias sobre nuestro tema
y empezamos con nuestro desarollo
INTERBLOQUEOS
Un Interbloqueo
supone un bloqueo permanente de un conjunto de procesos que compiten por recursos
o bien se comunican o sincronizan si. Los procesos de los sistemas no solo son
independientes, sino que compiten en el uso exclusivo de recursos, se comunican
y se sincronizan entre si. El sistema operativo debe encargarse de asegurar que
estas interacciones se llevan a cabo aproximadamente proporcionando la
exclusión mutua requerida por las mismas. La necesidad de los algunos procesos
pueden entrar en conflicto entre si causando que estos se bloqueen
indefinidamente. El Interbloqueo surge debido a que produce un conflicto entre
las necesidades de los procesos y el recurso que necesita cada proceso lo posee
el otro. Se caracteriza por la existencia de un conjunto de entidades activas
que utilizan un conjunto de recursos para llevar a cabo su labor.
Un ejemplo fácil para entender este contexto es
imaginar que existen dos procesos que compiten por dos recursos que necesitan
para funcionar, que solo pueden ser usados por un proceso a la vez. El
primer proceso obtiene el permiso de utilizar uno de los recursos. El segundo
proceso toma el otro recurso, y luego intenta utilizar el recurso ya utilizado
por el primer proceso, por lo tanto queda en espera.
Cuando el primer proceso a su vez intenta utilizar el otro recurso, se
produce un interbloqueo, donde los dos procesos esperan la liberación del
recurso que utiliza el otro proceso.
Los interbloqueos
pueden ocurrir en una variedad de situaciones, además de solicitar dispositivos
de E/S dedicados. Por ejemplo, en un sistema de bases de datos, un programa
puede tener que
Bloquear varios
registros que esté utilizando para evitar condiciones de competencia. Si el
proceso A bloquea el registro R1y el proceso 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.
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). Por lo general, una computadora tendrá muchos
recursos que se pueden adquirir. Para algunos recursos puede haber disponibles
varias instancias idénticas, como tres unidades de cinta. Cuando hay
disponibles varias copias de un recurso, se puede utilizar sólo una de ellas
para satisfacer cualquier petición de ese
recurso
Recursos existentes en el sistema: son utilizados por los
procesos para llevar a cabo su valor. Tipos de recursos:
1-Recursos reutilizables o consumibles: Se caracteriza por
que el recurso existiendo después de que un proceso lo use queda disponible
para otros procesos. El recurso es independiente de su utilización.
2-Recursos consumibles: Estos se caracterizan por que dejan
de existir una vez que los usa.
3-Recursos compartidos o exclusivos: Estos recursos no se
ven afectados por Interbloqueos ya que los procesos que quieran usarlos pueden
hacerlo inmediatamente sin posibilidad de quedarse bloqueados.
4-Recursos con un único ejemplar o con múltiples: Una
solicitud de este recurso por parte de un proceso podría satisfacerse con
cualquier ejemplar del mismo.
-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. Por ejemplo, considere un sistema con 256 MB de memoria de
usuario, una impresora y dos procesos de 256 MB, cada uno de los cuales quiere
imprimir algo. El proceso A
Solicita y obtiene la impresora, y después empieza a
calcular los valores a imprimir. Antes de terminar con el cálculo, excede su
quantum de tiempo y se intercambia por el otro proceso.
Ahora el proceso B se ejecuta y trata (sin éxito) de
adquirir la impresora: se crea una situación
Potencial de interbloqueo, ya que Atiene la impresora y B
tiene la memoria, y ninguno puede proceder sin el recurso que el otro posee.
Por fortuna, es posible apropiarse (quitar) de la memoria de B al
intercambiarlo y colocar el proceso A de vuelta. Ahora Ase puede ejecutar,
realizar su impresión y después liberar la impresora. Así no ocurre ningún
interbloqueo.
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.
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.
Si el recurso no está disponible cuando se le solicita,
el proceso solicitante se ve obligado a esperar. En algunos sistemas
operativos, el proceso se bloquea de manera automática cuando falla la
solicitud de un recurso, y se despierta cuando el recurso está disponible. En
otros sistemas, la solicitud falla con un código de error y depende del proceso
que hizo la llamada decidir si va a esperar un poco e intentar de nuevo.
Un proceso al que se le ha negado la petición de un
recurso por lo general permanece en un ciclo estrecho solicitando el recurso, después
pasa al estado inactivo y después intenta de nuevo.
Aunque este proceso no está bloqueado, para toda
intención y propósito es como si lo estuviera, debido a que no puede realizar
ningún trabajo útil. En nuestro siguiente análisis vamos a suponer que cuando a
un proceso se le niega un recurso solicitado pasa al estado inactivo.
La naturaleza exacta de solicitar un recurso es en gran
medida dependiente del sistema. En algunos sistemas se proporciona una llamada
al sistema request para permitir que los procesos pidan los recursos en forma
explícita. En otros, los únicos recursos que conoce el sistema operativo son
los archivos especiales que sólo un proceso puede tener abiertos en un momento
dado. Éstos se abren mediante la llamada al sistema open ordinaria. Si el
archivo ya está en uso, el proceso que llama es bloqueado hasta que su
propietario actual lo cierra
-Adquisición de
recursos
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
downen el semáforo para adquirir el recurso, usarlo y
finalmente realizar una operación upen el
recurso para liberarlo. Estos pasos se muestran en la figura (a).
typedef int semaforo; typedef int semaforo;
semaforo recurso_1; semaforo recurso_1;
semaforo recurso_2;
void proceso_A(void) { void proceso_A(void) {
down(&recurso_1); down(&recurso_1);
usar_recurso_1(); down(&recurso_2);
up(&recurso_1); usar_ambos_recursos();
} up(&recurso_2);
up(&recurso_1);
}
(a) (b)
Figura. Uso de un semáforo para proteger los recursos.
(a) Un recurso. (b) Dos recursos.
Algunas veces los procesos necesitan dos o más recursos.
Se pueden adquirir de manera secuencial, como se muestra en la figura (b). Si
se necesitan más de dos recursos, sólo se adquieren uno después del otro.
Hasta ahora todo está bien. Mientras sólo haya un proceso
involucrado, todo funciona sin problemas. Desde luego que con sólo un proceso,
no hay necesidad de adquirir formalmente los recursos, ya que no hay
competencia por ellos.
Ahora consideremos una situación con dos procesos, Ay B,
y dos recursos. En la figura se ilustran dos escenarios. En la figura 6-2(a),
ambos procesos piden los recursos en el mismo orden.
En la figura (b), los piden en un orden distinto. Esta
diferencia puede parecer insignificante, pero no lo es.
En la figura (a), uno de los procesos adquirirá el primer
recurso antes del otro. Después ese proceso adquirirá con éxito el segundo
recurso y realizará su trabajo. Si el otro proceso intenta adquirir el recurso
1 antes de que sea liberado, el otro proceso simplemente se bloqueará hasta que
esté disponible.
En la figura (b), la situación es distinta. Podría
ocurrir que uno de los procesos adquiera ambos recursos y en efecto bloquee al
otro proceso hasta que termine. Sin embargo, también podría ocurrir que el
proceso A adquiera el recurso 1 y el proceso B adquiera el recurso 2. Ahora
cada uno se bloqueará al tratar de adquirir el otro. Ninguno de los procesos se
volverá a ejecutar. Esa situación es un interbloqueo.
Aquí podemos ver cómo lo que parece ser una diferencia
insignificante en el estilo de codificación (cuál recurso adquirir primero)
constituye la diferencia entre un programa funcional y uno que falle de una
manera difícil de detectar. Como los interbloqueos pueden ocurrir con tanta
facilidad, gran parte de la investigación se ha enfocado en las formas de
lidiar con ellos. En este capítulo analizaremos los interbloqueos con detalle y
lo que se puede hacer con ellos.
typedef int semaforo;
semaforo recurso_1; semaforo recurso_1;
semaforo recurso_2; semaforo recurso_2;
void proceso_A(void) { void proceso_A(void) {
down(&recurso_1); down(&recurso_1);
down(&recurso_2); down(&recurso_2);
usar_ambos_recursos(); usar_ambos_recursos();
up(&recurso_2); up(&recurso_2);
up(&recurso_1); up(&recurso_1);
}} void proceso_B(void) { void proceso_B(void) {
down(&recurso_1); down(&recurso_2);
down(&recurso_2); down(&recurso_1);
usar_ambos_recursos(); usar_ambos_recursos();
up(&recurso_2); up(&recurso_1);
up(&recurso_1); up(&recurso_2);
}}(a) (b)
Figura (a) Código
libre de interbloqueos. (b) Código con potencial de interbloqueo.
INTRODUCCIÓN A LOS INTERBLOQUEOS
Como introducción a los interbloqueos daremos nueva mente
una definición de este.
La administración de los recursos es una de las principales
tareas del sistema operativo.
Los sistemas operativos tienen que ofrecer mecanismos que
permitan a los procesos acceder de forma exclusiva a este tipo de recursos.
Cuando un proceso solicita ciertos recursos y éstos no
están disponibles en ese momento, entra en un estado de espera.
Requerir el acceso exclusivo no sólo a un recurso, sino a
varios.
Se dice
que dos o más procesos están bloqueados, cuando están suspendidos en espera de
un evento que sólo puede ser activado por uno de los procesos bloqueados, y por
lo tanto dicho evento nunca sucederá. Para este problema no existe solución
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.
En la mayoría de los casos, 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. En otras palabras, cada miembro del conjunto de
procesos en interbloqueo está esperando un recurso que posee un proceso en
interbloqueo.
Ninguno de los procesos se puede ejecutar, ninguno de
ellos puede liberar recursos y ninguno puede ser despertado. 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
También tenemos
condiciones necesarias para un interbloqueo las cuales serian
•
Inapropiatividad: Los recursos asignados a un proceso, sólo pueden ser liberados por el
proceso mismo y no pueden ser desasignados por el sistema, cuando otro proceso
los necesite.
•
Espera circular: Dependencia: Si un proceso P1 está suspendido en espera de un recurso
exclusivo que está asignado a otro proceso P2, entonces decimos que P1 depende
de P2 (P1 <= P2).
•
interbloqueo
•
Puede
surgir si y sólo si en un sistema se
•
presentan simultáneamente las condiciones:
•
– Exclusión mutua.
•
– Retención y espera
•
– No expropiación
•
– Espera circular
•
No son
completamente independientes
Modelado de los interbloqueos
ALGORITMO DEL AVESTRUZ
El algoritmo del avestruz es uno de los métodos más
simples e inservibles el cual es el siguiente
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 al sistema 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
Detección y recuperación: En esta
política, el sistema deja que suceda el interbloqueo, pero se implementan
procesos encargados de revisar el estado de asignación de los procesos, para
detectar los interbloqueo. Una vez detectado, se pueden implementar políticas
de recuperación de interbloqueo, que básicamente consisten en matar procesos.
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. En esta sección
analizaremos algunas de las formas en que se pueden detectar los interbloqueos,
y ciertas maneras en que se puede llevar a cabo una recuperación de los mismos.
Formas de enfrentar los interbloqueos
Existen varias políticas y estrategias que el sistema operativo puede tomas,
para tratar con los interbloqueos: Indiferencia: Problema del usuario y del
programador, lograr que no se dé el interbloqueo. Prevención: Consisten en
condicionar el sistema con una serie de restricciones a los programadores, para
que no se den al menos una de las condiciones del interbloqueo, por lo que éste
nunca sucederá. Evitación o predicción: Esta estrategia consiste en dejar que
las condiciones para el interbloqueo se puedan dar, pero en el momento de
asignar recursos, y se detecte que puede ocurrir un interbloqueo, deniega la
asignación del recurso que puede desencadenar el interbloqueo
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.
Por ejemplo, para quitar una impresora láser a su
propietario, el operador puede recolectar todas las hojas ya impresas y
colocarlas en una pila. Después se puede suspender el proceso (se marca como no
ejecutable). En este punto, la impresora se puede asignar a otro proceso.
Cuando ese proceso termina, la pila de hojas impresas se puede colocar de
vuelta en la bandeja de salida de la impresora y se puede reiniciar el proceso
original.
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.
Recuperación a
través del retroceso
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. 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 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.
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. Se pierde todo el trabajo realizado desde el punto de comprobación
(por ejemplo, la salida impresa desde el punto de comprobación se debe
descartar, ya que se volverá a imprimir). En efecto, el proceso se restablece a
un momento anterior en el que no tenía el recurso, que ahora se asigna a uno de
los procesos en interbloqueo. Si el proceso reiniciado trata de adquirir el
recurso de nuevo, tendrá que esperar hasta que vuelva a estar disponible.
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. Con un poco de suerte, los demás procesos podrán continuar. Si
esto no ayuda, se puede repetir hasta que se rompa el ciclo.
De manera alternativa, se puede elegir como víctima a un
proceso que no esté en el ciclo, para poder liberar sus recursos. 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. Por ejemplo, un
proceso podría contener una impresora y querer un trazador, en donde otro
proceso podría contener un trazador y querer una impresora. Estos dos procesos
están en interbloqueo. Un tercer proceso podría contener otra impresora idéntica
y otro trazador idéntico, y estar felizmente en ejecución. Al eliminar el
tercer proceso se liberarán estos recursos y se romperá el interbloqueo que
involucra a los primeros dos.
Donde sea posible, es mejor eliminar un proceso que se
pueda volver a ejecutar desde el principio sin efectos dañinos. Por ejemplo,
una compilación siempre podrá volver a ejecutarse, ya que todo lo que hace es
leer un archivo de código fuente y producir un archivo de código objeto. Si se
elimina a mitad del proceso, la primera ejecución no tiene influencia sobre la
segunda.
Por otra parte, 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.
Como evitar interbloqueos
Evitación o predicción: Esta estrategia consiste en
dejar que las condiciones para el interbloqueo se puedan dar, pero en el
momento de asignar recursos, y se detecte que puede ocurrir un
interbloqueo, deniega la asignación del recurso que puede desencadenar el
interbloqueo.
Detección y recuperación: En esta política, el sistema
deja que suceda el interbloqueo, pero se implementan procesos encargados de
revisar el estado de asignación de los procesos, para detectar los
interbloqueo. Una vez detectado, se pueden implementar políticas de
recuperación de interbloqueo, que básicamente consisten en matar procesos.
Evitación o
Predicción ( Estrategias de Dijkstra, Habermann)
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.
Conceptos
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.
Algoritmo del
banquero (Dijkstra, Habermann)
En este algoritmo,
de evitación en general procede así:
Necesita que cada
proceso declare el máximo número de recursos a utilizar
En cada
requerimiento, determina si el asignar los recursos pedidos deja un estado
inseguro de asignación de recursos, entonces se pospone el requerimiento.
De lo contrario se asignan los recursos solicitados.
Procedimiento
de asignación
Cuando un proceso
solicita recursos, el sistema operativo procede así:
Determinar si hay
disponibles
Determinar que no
exceda su máximo declarado
Determinar que, si
se concede la petición, el sistema quede en estado seguro
Si no se cumple
cualquiera de estas condiciones, el proceso queda suspendido hasta que exista
una liberación de recursos.
Estructuras de
datos:
sea m el número
de tipos de recursos y n el número de procesos
int disponible [m] ; unidades de R j disponibles
int max[n][m]; máximo número de requerimientos del proceso Pi del recurso Rj
int asignado [n][m]; asignación actual del proceso P i del recurso Rj
int necesario [n][m]; necesario [i][j] = max [i][j] - asignados[i][j]
int requerimiento[m]; vector de requerimiento de cada petición de recursos//
int disponible [m] ; unidades de R j disponibles
int max[n][m]; máximo número de requerimientos del proceso Pi del recurso Rj
int asignado [n][m]; asignación actual del proceso P i del recurso Rj
int necesario [n][m]; necesario [i][j] = max [i][j] - asignados[i][j]
int requerimiento[m]; vector de requerimiento de cada petición de recursos//
Relación <=
entre vectores
si x in N m , y in
N m : x <= y ssi para todo i = 0,...,m-1 : x[i] <= y[i]
Por ejemplo:
<1,1,1> <= <2,5,7>
<1,1,1> NO <= <2,0,7>
Por ejemplo:
<1,1,1> <= <2,5,7>
<1,1,1> NO <= <2,0,7>
Algoritmo
void
requerimiento_de_recursos (int requerimiento[], idProceso i) {
if (requerimiento >= necesario[i] )
error () ; máximo de recursos estimados agotados
i f (requerimiento >= disponible)
suspender () ; recursos no disponibles
disponible -= requerimiento;
asignado [i] += requerimiento;
necesario[i] -= requerimiento;
if (! estado_seguro ()) {
regresamos al estado anterior
disponible += requerimiento;
asignado[i] -= requerimiento;
necesario[i] += requerimiento;
suspender () ;
}
}
int estado_seguro() {
int disp_temp = disponible;
bool terminado[n] = (FALSE,...,FALSE);
int i;
encontrar un p[i] tal que terminado[i] = FALSE y necesario[i] <= disponible
while (terminado!=(TRUE,...TRUE)){
for (i=0; (i < n && terminado[i]) || necesario[i] > disp_temp); i++) {
if (i == n-1) {
return FALSE;
}else
if (!terminado[i]){
disp_temp += asignados[i] ;
terminado[i] = TRUE;
} if
} for
} while
return TRUE ;
}estado_seguro
if (requerimiento >= necesario[i] )
error () ; máximo de recursos estimados agotados
i f (requerimiento >= disponible)
suspender () ; recursos no disponibles
disponible -= requerimiento;
asignado [i] += requerimiento;
necesario[i] -= requerimiento;
if (! estado_seguro ()) {
regresamos al estado anterior
disponible += requerimiento;
asignado[i] -= requerimiento;
necesario[i] += requerimiento;
suspender () ;
}
}
int estado_seguro() {
int disp_temp = disponible;
bool terminado[n] = (FALSE,...,FALSE);
int i;
encontrar un p[i] tal que terminado[i] = FALSE y necesario[i] <= disponible
while (terminado!=(TRUE,...TRUE)){
for (i=0; (i < n && terminado[i]) || necesario[i] > disp_temp); i++) {
if (i == n-1) {
return FALSE;
}else
if (!terminado[i]){
disp_temp += asignados[i] ;
terminado[i] = TRUE;
} if
} for
} while
return TRUE ;
}estado_seguro
Ejemplo
proceso\recurso
|
R1 (7)
|
R2(7)
|
R3(7)
|
|
Maximos
|
P1
|
5
|
3
|
1
|
P2
|
3
|
2
|
3
|
|
P3
|
2
|
3
|
1
|
|
P4
|
5
|
0
|
3
|
|
Asignados
|
P1
|
3
|
3
|
1
|
P2
|
2
|
2
|
2
|
|
P3
|
0
|
1
|
1
|
|
P4
|
0
|
0
|
1
|
|
Necesarios
|
P1
|
2
|
0
|
0
|
P2
|
1
|
0
|
1
|
|
P3
|
2
|
2
|
0
|
|
P4
|
5
|
0
|
2
|
|
Disponibles
|
2
|
1
|
2
|
|
Sobre este estado
de asignación de recursos (qué es estable ¿?) supongamos las siguientes
peticiones de recursos:
P2[1,0,1]:El
sistema queda en un estado seguro
P3[2,0,0]:El
sistema queda en un estado inseguro
Necesita el
conocimiento del máximo por recurso que usará cada proceso implica un retardo
en cada asignación de recursos, lo que puede degradar el sistema si se manejan
muchos recursos y/o procesos
Se requiere una
garantía de devolución: c/proceso liberará los recursos asignados. (Suponga que
después de hacer la primera asignación de recursos, el proceso P2 no termina, entonces
ninguno de los procesos podría terminar, sin necesidad de que haya interbloqueo
Como prevenir interbloqueos
Prevención del interbloqueo
Se trata de eliminar la aparición de alguna de las cuatro condiciones necesarias para el
interbloqueo.
Exclusión mutua. Depende de la naturaleza del recurso,
así que esta condición no se puede eliminar.
Prevención del interbloqueo
Retención y espera. Hay que garantizar que un proceso no
pueda quedar bloqueado si retiene algún recurso. ¿Cómo conseguirlo?
el proceso tiene que pedir todos sus recursos de una vez,
p.ej. antes de empezar a ejecutarse efecto negativo: muchos recursos retenidos
pero no usados, un proceso sólo puede solicitar recursos cuando no tiene
ninguno asignado
Efecto negativo: puede ocurrir que tengamos que liberar
un recurso y volver a pedirlo para poder solicitar otros recursos
En ambos caso puede que un proceso nunca se ejecute
(inanición)
Prevención del interbloqueo
No expropiación. Permitir que el S.O. desasigne recursos
a un proceso bloqueado.
Si un proceso se bloquea por un recurso, los recursos
retenidos quedan a disposición de los procesos activos
El proceso bloqueado tiene ahora que esperar por todos
los recursos penaliza a los procesos que necesitan muchos recursos
Es posible seguir este protocolo en recursos cuyo estado
se puede guardar fácilmente y después restaurarse (registros de CPU, espacio de
memoria, ...). Generalmente no puede aplicarse a
Prevención del interbloqueo
Espera circular. Se puede evitar forzando un orden en la
petición de los recursos.
Cada recurso tiene asignado un número de orden Los recursos se deben pedir en orden
ascendente
Aconsejable: el orden de petición de los recursos se
establezca según el orden de uso normal de los recursos de un sistema Efectos
negativo se limita la libertad de escritura de código se puede inducir a una
mala utilización de los recursos
Prevención (Estrategias de
Havender/Prevención estática)
Se pueden adoptar ¿4? posibles
estrategias de prevención del interbloqueo, una para cada condición. Ya que
para se dé un interbloqueo son necesarias las cuatro, con negar una de ellas,
se niega la posibilidad del interbloqueo:
Negación de la exclusividad
Sólo se aplica a recursos compartidos, es muy
difícil poder aplicarlo a todos los recursos, dado que hay recursos que son
inherentemente de uso no compartido.
Uso de spoolers: dar un API concurrente
(compartido) a los procesos para accesar recursos. La estrategia básica es que
un servicio del sistema (daemon) proporciona un API, y ese servicio es el único
que accesa el recurso compartido, exclusivo. Ej: una impresa es un recurso
exclusivo e inapropiativo, pero con el uso de un spooler se convierte en un
recurso compartido.
Test & Get: un API especial que permite revisar
primero si el recurso está disponible, y pedirlo, o retornar un código de error
que indica que no está disponible. Requiere que los procesos hagan uso de este
API.
Negación de la contención
Estrategia 1: El proceso pide al sistema TODOS los
recursos a necesitar antes de iniciar su proceso (todo o nada). No siempre se
sabe cuántos recursos se utilizarán.
Estrategia 2: También puede establecerse que un
procesos puede pedir recursos cuando no tiene recursos asignados
No siempre se conoce la cantidad de recursos que se
necesitará, por lo que lo que el operador debe configurar, por prueba y error,
lograr que los procesos funcionen adecuadamente
Obliga a optimizar los programas por medio de
división. El programador de modularizar extremadamente bien los procesos para
utilizar los recursos por fases, de forma que para cada fase, se piden los
recursos y se liberan, antes de la siguiente fase
La utilización de recursos resulta muy pobre
Puede resultar una postergación indefinida de un
proceso que requiera muchos recursos
Negación de la inapropiatividad
Si un proceso que tiene recursos asignados, pide un
nuevo recurso que no está disponible, deberá liberar los recursos asignados y
pedirlos posteriormente.
Sólo se aplica a recursos apropiativos y recursos
que se pueden almacenar su estado para reasignarlo, o que puedan hacerles
rollback
puede llevar a que la ejecución de un proceso se
prolongue indefinidamente, debido a que nadie puede garantizar que termine en
un tiempo determinado.
Pobre utilización del tiempo de procesamiento
Se impone un orden a los recursos
Para que haya una dependencia de Pi A Pj, significa que Pi tiene asignados recursos <= k, y está pidiendo un Rk+1, el cual está asignado a Pj, lo que significa que Pj tiene asignados recursos >= k+1, por lo tanto Pn ¡=> P0
En general las técnicas de prevención, aunque logran su objetivo de eliminar los interbloqueos, provocan una pobre utilización de los recursos, incluyendo el procesador. También el algunos casos, provocan postergación indefinida
bloqueos de dos faces, interbloqueos de comunicaciones bloqueo activo e inanición
TÉCNICAS DE BLOQUEO Protocolo de bloqueo en dos fases
En él, todas las operaciones de bloqueo preceden a la primera operación de desbloqueo de la transacción. El proceso se puede así dividir en dos fases; la fase de bloqueo y de desbloqueo. Si se permite la conversión entre bloqueos, las conversiones de bloqueos de lectura a bloqueos de escritura son en la primera fase y las de bloqueos de escritura a lectura en la segunda.
Cualquier transacción que después de liberar un bloqueo adquiere otro siempre corre el riesgo de producir resultados incorrectos. Esto es, siempre es posible definir una segunda transacción que pueda ejecutarse concurrentemente con la primera de manera tal que la ejecución intercalada o concurrente de ambas no sea serializable y por ende no correcta. Se define el siguiente teorema:
Teorema: Si todas las transacciones obedecen las siguientes reglas:
a) Antes de operar sobre cualquier objeto la transacción debe adquirir primero un bloqueo sobre ese objeto; y
b) Después de liberar un bloqueo la transacción no adquiere ningún otro bloqueo Entonces, todas las ejecuciones intercaladas de esas transacciones son serializables.
Una transacción que obedece las reglas a) y b) se dice que satisface el protocolo de bloqueo en dos fases. Las dos fases son una fase creciente durante la cual los bloqueos son adquiridos, y una fase decreciente durante la cual los bloqueos son liberados.
Su principal ventaja es que garantiza la seriabilidad, lo que no se consigue usando simplemente bloqueos.
Como inconvenientes podemos citar varios:
• Bloquea los elementos que podrían ser desbloqueados tras su uso ocupados hasta la segunda fase, impidiendo que otras transacciones que los necesiten los utilicen. Esto hace que el rendimiento de este protocolo se degrade conforme aumenta el grado de concurrencia;
• No permite todos los planes serializables posibles.
• La implementación de este este bloqueo depende del programador, que puede no realizar su tarea convenientemente.
Bloqueo en dos fases básico, conservador, estricto y riguroso
Son variaciones del bloqueo en dos fases. Se detallan a continuación:
Conservador o estático
Requiere que una transacción bloquee todos los elementos a los que tendrá acceso antes decomenzar a ejecutarse. Una vez bloqueados, no habrá conversión de bloqueos de lectura a escritura.
Si no es posible bloquearlos todos, la transacción no bloqueará nada y esperará a poder bloquear todos los elementos necesarios en su totalidad.
Su principal ventaja es que no sólo garantiza la seriabilidad, sino que evita el interbloqueo de transacciones.
Como principal inconveniente, en la práctica, es muy difícil saber quéelementos serán necesarios durante la transacción antes de que esta comience, si no imposible. es interesante destacar que, al tener que esperar a poder bloquear todos los elementos que la transacción necesite, este protocolo reduce la concurrencia.
Estricto
La transacción no libera ninguno de sus bloqueos de escritura antes de confirmarse o abortar.
Este tipo de bloqueo garantiza planes estrictos en cuanto a recuperabilidad (recuperable es un plan que, una vez confirmada la transacción, no será necesaria deshacerla). Sin embargo, puede sufrir interbloqueos.
Riguroso
Es una versión más restrictiva del estricto. Similar al anterior, pero además tampoco libera los bloqueos de lectura. Es más fácil de implementar
Inanición (informática)
En informática, inanición (starvation en inglés) es un problema relacionado con los sistemas multitarea, donde a un proceso o un hilo de ejecución se le deniega siempre el acceso a un recurso compartido. Sin este recurso, la tarea a ejecutar no puede ser nunca finalizada.
La inanición no es sinónimo de interbloqueo, aunque el interbloqueo produce la inanición de los procesos involucrados1 . La inanición puede (aunque no tiene porqué) acabar, mientras que un interbloqueo no puede finalizar sin una acción del exterior.
Un caso de inanición la ilustra perfectamente la paradoja conocida como la cena de los filósofos de Edsger Dijkstra cuando se da el caso de que todos los filósofos cogen el tenedor a la vez.
La utilización de prioridades en muchos sistemas operativos multitarea podría causar que procesos de alta prioridad estuvieran ejecutándose siempre y no permitieran la ejecución de procesos de baja prioridad, causando inanición en estos. Es más, si un proceso de alta prioridad está pendiente del resultado de un proceso de baja prioridad que no se ejecuta nunca, entonces este proceso de alta prioridad también experimenta inanición (esta situación se conoce como inversión de prioridades). Para evitar estas situaciones los planificadores modernos incorporan algoritmos para asegurar que todos los procesos reciben un mínimo de tiempo de CPU para ejecutarse
referencias y bibliografias
libro pdf sistemas operativos modernos
tema 6
http://www.powershow.com/view/286685-ZTdlZ/INTERBLOQUEO_E_INANICION_powerpoint_ppt_presentation
No hay comentarios:
Publicar un comentario