Descarga la aplicación para disfrutar aún más
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; }
Compartir