Serna_Jose_SO - Jose SernaS

Vista previa del material en texto

Tarea 11: Concurrencia: Interbloqueo e inanición
Sistemas Operativos
Sección D02
Jose Luis Serna Serna
Código: 218292327
1. FUNDAMENTOS DEL INTERBLOQUEO
El interbloqueo es el bloqueo permanente de 
un conjunto de procesos o hilos de 
ejecución en un sistema concurrente que compiten 
por recursos del sistema o bien se
comunican entre ellos. Ejemplo: los recursos de
estos procesos no pueden satisfacerse porque se
bloquean entre si pidiendo un recurso asignado.
El interbloqueo ocurre cuando cada proceso del 
conjunto está bloqueado esperando un evento (normalmente 
la liberación del recurso requerido) que sólo
puede generar otro proceso bloqueado del conjunto. 
El interbloqueo es permanente porque no puede 
producirse ninguno de los eventos mencionados.
Ejemplo de interbloqueo del tráfico:
•	El coche 1, viaja hacia el norte, 
	necesita de los cuadrantes a y b.
•	El 2 necesita cuadrantes b y c.
•	El 3 necesita cuadrantes c y d.
•	El 4 necesita cuadrantes d y a.
Hay dos categorías de recursos; reutilizables, consumibles.
Un recurso reutilizable es aquél que sólo 
lo puede utilizar de forma segura un 
proceso en cada momento y que no 
se destruye después de su uso. Ejemplos:
Procesadores, canales de E/S, memoria principal y 
secundaria, ficheros, bases de datos y semáforos.
Un recurso consumible es aquél que puede 
crearse (producirse) y destruirse (consumirse).
Un proceso productor puede crear un número 
ilimitado de estos recursos, cuando un proceso 
consumidor adquiere un recurso, el recurso desaparece. 
Ejemplo: Las interrupciones, las señales, los mensajes 
y la información en buffers de E/S.
CONDICIONES PARA EL INTERBLOQUEO
Exclusión mutua. Ningún proceso puede acceder 
a un recurso asignado a otro proceso.
Retención y espera. Un proceso mantiene recursos 
asignados mientras espera asignación de otros recursos.
Sin expropiación. No se fuerza la expropiación 
de un recurso al proceso poseedor.
Si se cumplen las tres condiciones anteriores 
puede producirse un interbloqueo, pero aún cumpliéndose
puede no haberlo. Para que realmente se 
produzca interbloqueo, se requiere una cuarta condición:
Espera circular. Hay una lista de procesos, 
de manera que cada proceso posee mínimo
un recurso necesitado por el siguiente proceso.
2. Prevención de interbloqueo.
Esta estrategia consiste en diseñar un sistema 
que pueda prevenir un posible interbloqueo. Un
método indirecto es impedir la aparición de 
cualquiera de las tres condiciones listadas anteriormente. 
Un método directo preventivo es impedir que 
se produzca una espera circular (cuarta condición). 
PREVENCIÓN DE EXCLUSIÓN MUTUA. 
Generalmente, esta condición no puede eliminarse. 
Si el acceso a un recurso requiere 
exclusión mutua, el sistema operativo debe proporcionarlo. 
Recursos como los ficheros, pueden permitir múltiples 
accesos de lectura, pero acceso exclusivo sólo 
para escrituras. Aún así puede ocurrir interbloqueo 
si muchos procesos requiere permiso de escritura.
PREVENCIÓN DE RETENCIÓN Y ESPERA
Esta condición puede eliminarse estableciendo que un 
proceso debe solicitar al mismo tiempo todos 
sus recursos requeridos, bloqueándolo hasta que se 
le puedan conceder simultáneamente todas las peticiones.
Desventajas; Tiempo prolongado de inutilización de recursos, 
de espera para satisfacer las peticiones, el 
proceso puede desconocer los recursos que requerirá.
PREVENCIÓN DE CONDICIÓN SIN EXPROPIACIÓN
Si a un proceso que mantiene varios 
recursos se le deniega una petición posterior, 
ese proceso deberá liberar sus recursos originales.
También si otro proceso solicita dichos recursos.
Esta estrategia es sólo práctica cuando se 
aplica a recursos cuyo estado se puede 
restaurar más tarde, como en un procesador.
PREVENCIÓN DE ESPERA CIRCULAR
Esta condición puede impedirse definiendo un orden 
lineal entre los tipos de recursos, si 
a un proceso le asignan recursos de 
tipo R, posteriormente puede pedir sólo recursos 
de un orden posterior a R.
Esta estrategia puede ser ineficiente, ralentizar los 
procesos y denegar innecesariamente acceso a recursos.
3. PREDICCIÓN DEL INTERBLOQUEO
A diferencia de la prevención, la predicción 
permite las tres condiciones necesarias pero toma 
decisiones razonables para asegurarse de que nunca 
se alcanza el punto del interbloqueo, de 
esta manera, la predicción permite más concurrencia.
Decide dinámicamente si la petición actual de 
reserva de recursos, podría potencialmente causar interbloqueo.
Técnicas principales para predecir el interbloqueo:
•	Denegación del inicio de un proceso 
	si sus demandas podrían llevar al interbloqueo.
•	Denegación de una petición adicional de un 
	recurso por parte de un proceso si 
	esta asignación podría provocar un interbloqueo.
La predicción tiene varias restricciones de uso:
•	Deben establecerse por anticipado los requisitos máximos 
	de recursos de cada proceso.
•	Los procesos involucrados deben ser independientes.
•	Debe haber un número fijo de recursos 
	que asignar.
•	Ningún proceso puede terminar mientras mantenga recursos.
4. Tratamiento del interbloqueo
[HOWA73] sugiere usar la siguiente técnica:
•	Agrupar recursos en clases de recursos diferentes.
•	Utilizar la estrategia del orden lineal definida 
previamente previniendo la espera circular impidiendo interbloqueos.
•	Dentro de una clase de recursos, usar 
	el algoritmo que sea más apropiado para esa clase. 
Clases de recursos considerados en dicha técnica:
•	Espacio de intercambio. Bloques de memoria en 
almacenamiento secundario utilizados al expulsar los procesos.
•	Recursos del proceso. Dispositivos asignables; cinta, ficheros.
•	Memoria principal. Asignable a los procesos en 
	páginas o segmentos.
•	Recursos internos. Como canales de E/S.
Estrategias dentro de cada clase:
Espacio de intercambio. Prevención de los interbloqueos, 
	asignar obligatoriamente al mismo tiempo todos los 
	recursos necesitados, como en prevención de retención 
	y espera, estrategia razonable si se conocen 
	los requisitos máximos de almacenamiento.
 	La predicción también es una posibilidad factible.
Recursos del proceso. La predicción es regularmente 
	efectiva para esta categoría, porque es razonable 
	esperar que los procesos declaren anticipadamente los 
	recursos de esta clase que requerirán. 
	La prevención mediante ordenamiento de recursos es 
	también posible y razonable para esta clase.
Memoria principal. Prevención por expropiación parece la 
	estrategia más apropiada para la memoria principal.
	Cuando se expropia a un proceso es 
	expulsado a memoria secundaria, liberando el espacio 
	para resolver el interbloqueo.
Recursos internos. Puede utilizarse la prevención mediante 
	el ordenamiento de recursos.
5. Los filósofos comensales.
Problema de sincronización planteado por Dijkstra (1965). 
Cinco filósofos están sentados alrededor de una 
mesa circular; cada filósofo tiene un plato 
de espagueti y necesita dos tenedores para 
comer; entre cada par de platos hay 
un tenedor. 
Cada filosofo requiere periodos alternantes de comer 
y pensar, cuando siente hambre, necesita tenedor
 izquierdo y derecho, uno a la vez 
en cualquier orden, comerá un rato y 
luego dejara los tenedores y seguirá pensando. 
La solución consiste en que cada filósofo 
haga lo suyo sin que se bloqueen.
SOLUCIÓN UTILIZANDO SEMÁFOROS.
Cada filósofo toma primero el tenedor de 
la izquierda y después el de la 
derecha. Cuando el filósofo termina de comer, 
Coloca nuevamente los tenedores en la mesa. 
Esta solución, lamentablemente, genera interbloqueo cuando todos 
los filósofos están hambrientos al mismo tiempo.
Ejemplo del libro: William Stallings. (2005). Sistemas Operativos , Aspectos internos y principios de diseño.
Para solucionar el riesgo de interbloqueo; se 
podrían comprar cinco tenedores adicionales o enseñar 
a los filósofos a comer espaguetis con 
un solo tenedor. Alternativamente se podríaincorporar 
un asistente que sólo permitiera que haya 
cuatro filósofos simultáneamente en el comedor. 
Ejemplo de solución utilizando un monitor.
Ejemplo del libro: William Stallings. (2005). Sistemas Operativos , Aspectos internos y principios de diseño.
Bibliografía.
Stallings, W. (2011), Operating Systems: Internals and Design Principles. Prentice Hall. 7th Edition.
William Stallings. (2005). Sistemas Operativos, Aspectos internos y principios de diseño. Madrid: Pearson Educación S.A.
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}