CONCURRENCIA INTERBLOQUEO E
INANICION
Este capítulo continúa el estudio de la
concurrencia, considerando dos problemas
que importunan todos los intentos de realizar
procesamiento concurrente: Interbloqueo e
Inanición.
Comienza con una exposición de los
principios básicos del interbloqueo y de un
problema afín, la inanición.
PRINCIPIOS DEL
INTERBLOQUEO
El Interbloqueo se
puede definir como el
bloque permanente
de un conjunto de
procesos que
compiten por los
recursos del sistema,
todos los
interbloqueos
suponen necesidades
contradictorias de
recursos, por parte
de dos o más
procesos.
Un ejemplo clásico de
interbloqueo es el
interbloqueo de
tráfico
Ahora se describe una situación de
interbloqueo, en la que intervienen
procesos y recursos informáticos, al
siguiente gráfico se le asigna la siguiente
forma:
Proceso P Proceso Q
Obtener A Obtener B
Obtener B Obtener A
Liberar A Liberar B
Liberar B Liberar A
El que se produzca
interbloqueo o no,
depende de la
dinámica de la
ejecución, por
ejemplo;
supóngase que p
no necesitara
Proceso P ambos recursos
en el mismo
Obtener A
instante y tuviera
Liberar A la siguiente forma:
Obtener B En este caso no se produce interbloqueo
Liberar B
Dos Categorías de Recursos:
*Reutilizable
*Consumible
◦ Que son los Recursos Reutilizables?
*Pueden ser usados con seguridad por un
proceso, no se agota con el uso.
*Obtienen unidades de recursos que liberan
posteriormente para que otros procesos lo
utilicen.
Ejemplos:
*Procesadores
*Canales de E/S
*MP, MS
*Archivos, Bases de Datos
◦ Ejemplo Ilustrativo:
• Dos procesos compiten por el acceso exclusivo a
un archivo D del disco y a una unidad de cinta C.
Guiarse por la tabla 6.4, el interbloqueo se
produce si un proceso pide un recurso y retiene
otro.
p0p1q0q1p2q2
Esta es la forma para que se produzca un
interbloqueo en un sistema multiprogramado
◦ Estrategias para resolver interbloqueos:
*Restricciones en el diseño del sistema
en el orden que se solicitan los recursos.
Que son los Recursos Reutilizables?
*Puede ser creado (producido)
*Puede ser destruido (consumido)
*No existe límite de recursos
consumibles
*Proceso Productor que no está
bloqueado libera cualquier número de
recursos consumidos
Ejemplos
*Interrupciones
*Señales
*Buffer de E/S
Elementos Claves
*Prevención y predicción→revisar
condiciones de interbloqueo.
Condiciones de interbloqueo
Deben darse tres condiciones para que
pueda producirse un interbloqueo, las
cuales son:
1.- Exclusión Mutua: solo un proceso
puede usar un recurso cada vez.
Hace falta para asegurar
consistencia de resultados y la
integridad de BD
2.- Retención y Espera: un proceso
puede retener unos recursos
asignados mientras espera que se le
asignen otros
3.- No Apropiación: ningún proceso
puede ser forzado a abandonar un
recurso que retenga; la apropiación
no puede aplicar arbitrariamente.
Puede existir interbloqueos con estas tres
condiciones pero puede haber una cuarta
que produzca un interbloqueo.
4.-Círculos Viciosos de Espera:
Cadena cerrada de procesos, retiene
al menos un recurso que necesita el
siguiente proceso de la cadena.
TABLA DE RECURSOS CONSUMIBLES
ELEMENTOS CLAVES
Tener en cuenta.
*Las tres primeras condiciones son
necesarias pero no suficientes para el
interbloqueo
*Consecuencia potencial de las tres
anteriores es la cuarta
*Se produce espera irresoluble. Un círculo
de espera irresoluble es la definición de
interbloqueo
La estrategia de prevención del interbloqueo
consiste a grandes rasgos en diseñar un
sistema de manera que este excluida la
posibilidad de interbloqueo, existen dos
métodos:
*Indirectos: Impiden la aparición de las
tres condiciones antes mencionadas.
*Directos: Evitan la aparición del círculo
vicioso de espera
La 1era de las condiciones no puede anularse.
Si el acceso a un recurso necesita exclusión
mutua, el S.O. debe soportarla. Se puede
producir interbloqueo si más de un proceso
necesita permiso de escritura
Puede prevenirse exigiendo que todos los
procesos soliciten todos los recursos que
necesiten a un mismo tiempo y
bloqueando el proceso hasta que todos
los recursos puedan concederse
simultáneamente. En primer lugar un
proceso puede estar suspendido durante
mucho tiempo, esperando que se
concedan todas las solicitudes de
recursos. En segundo lugar, los recursos
asignados a un proceso pueden
permanecer sin usarse durante mucho
tiempo.
Puede prevenirse de varias formas. Primero,
si un proceso que retiene ciertos recursos
se le deniega una nueva solicitud, deberá
liberar sus recursos anteriores y solicitarlos
de nuevo. Segundo, si un proceso solicita
un recurso que actualmente está retenido
por otro proceso, el S.O. Puede expulsar al
segundo proceso y exigirle que libere sus
recursos, y se evitará el interbloqueo solo si
no hay dos procesos que posean la misma
prioridad.
Puede prevenirse definiendo una ordenación
lineal de los tipos de recursos.
La prevención del círculo vicioso de espera
puede ser ineficiente, retardando procesos y
denegando accesos a recursos
innecesariamente.
Negar la asignación de recursos se
denomina algoritmo del banquero.
Comienza definiendo los conceptos de
estado y de estado seguro. En un sistema
con número fijo de procesos y un numero
fijo de sus recursos, un proceso tendrá cero
o más recursos asignados. El estado de
sistema es la asignación de recursos a los
procesos y estará formado por los dos
vectores; Recursos y Disponible y las dos
matrices Demanda y Asignación.
Con la predicción del interbloqueo se pueden
alcanzar las tres condiciones necesarias, pero
se realiza elecciones acertadas para asegurar
que nunca se llega al punto de interbloqueo.
La predicción permite más concurrencia que
la prevención
El control de interbloqueo se puede hacer
tantas veces como la solicitudes de
recursos.
Este algoritmo tiene dos ventajas: conduce
a una pronta detección y el algoritmo es
relativamente simple.
Las comprobaciones de este algoritmo
consumen un tiempo de procesador
considerable.
RECUPERACION
Detectado el interbloqueo, hace falta alguna
estrategia de recuperación. Las técnicas siguientes
son posibles enfoques, en orden creciente de
sofisticación:
1.-Abortar todos los procesos interbloqueados esto
es se crea o no una de las soluciones más comunes
2.-Retroceder cada proceso interbloqueado hasta
algún punto de control definido previamente y volver
a ejecutar todos los procesos. Es necesario que haya
disponibles unos mecanismos de retroceso y reinicio
del sistema.
3.-Abortar sucesivamente procesos interbloqueados
hasta que deje de haber interbloqueo
4.-Apropiarse de recurso sucesivamente hasta que
deje de haber interbloqueo
UNA ESTRATEGIA
INTEGRADA DE
INTERBLOQUEO
En lugar de intentar diseñar un servicio del
S.O. Que emplee solo una de las estrategias,
puede ser más eficiente usar diferentes
estrategias en diferentes situaciones.
Agrupar los recursos en un número de
clases diferentes.
Usar la estrategia de ordenación lineal
definida anteriormente para la prevención
de círculos viciosos de espera e impedir el
interbloqueo entre clases de recursos.
Dentro de cada clase de recursos, emplear el
algoritmo más apropiado para dicha clase.
Espacio intercambiable: Bloques de memoria en
almacenamiento secundario para el intercambio
de procesos.
Puede aplicarse la prevención de interbloqueos
pidiendo que todos los recursos sean asignados
de una vez como en la estrategia de prevención,
retención y espera.
Recursos de Procesos:dispositivos asignables,
como unidades de cinta y archivos.
Que los procesos declaren por anticipado los
recursos de esta clase que necesitarán.
Memoria Principal: Asignable a los procesos en
páginas o segmentos.
Cuando se expulsa un proceso,
simplemente este es trasladado a la
memoria secundaria,liberando espacio para
resolver el interbloqueo.
Recursos Internos: Como canales de
entrada y salida.
Puede usarse la prevención por ordenación
de recursos
*Tubos
*Mensajes
*Memoria compartida
*Semáforos
*Señales
*Contribuciones mas significativas de
UNIX.
*Connota de una cola de FIFO
*Se creas tamaño fijo de bytes
*Si un proceso intenta escribir en un tubo
se ejecuta si hay suficiente memoria,
caso contrario se bloquea.
TIPOS DE TUBOS:
-Con nombre: Procesos no afines
-Sin nombre: Solo procesos afines
*Bloqueo de texto con un tipo asociado
*Emisor específico, el tipo de mensaje en
cada envío.
*Ocupa el método FIFO.
*Suspende el proceso.
*Forma más rápida de comunicación entre
procesos.
*Bloque común de memoria virtual,
compartido por varios procesos.
*Permiso de procesos, solo lectura y
escritura.
*Varía, núcleo ejecuta todas las
operaciones solicitadas.
*No se puede acceder hasta que el otro
proceso se acabe.
Consta de lo siguiente:
*Valor actual
*ID del último proceso,
esperando que el valor del
semáforo sea cero.
*Número de procesos esperando
que el valor del semáforo
sea mayor que el actual
*Mecanismo de software que informa un
proceso del acontecimiento de un proceso
asíncrono.
*Los procesos pueden enviarse señales unos
a otros.
*El método puede enviar señales internas.
Dados los mecanismos de concurrencia en
UNIX SVR4, Solaris soporta 4 primitivas de
sincronización de hilo
*Cierre de exclusión mutua
*Semáforos
*Cierre de múltiples lectores, un escritorio
*Variables de Condición.
Solaris implementa estas primitivas para
los hilos de núcleo dentro del núcleo, la
primitiva crea una estructura de datos
que contiene parámetros especificados.
Una vez que está creado el objeto de
sincronización, hay dos operaciones
fundamentales que se pueden realizar:
Entrar (adquirir y bloquear) y Salir
(desbloquear)
Nota: Todas las primas de sincronización
necesitan de la existencia de una
instrucción Hardware que permite
comprobar y señalar el valor de un objeto
en una operación atómica
❑ Cierrede Exclusión Mutua
Un cierre mutex impide que ejecute más
de un hilo cuando el cierre está activo, el
hilo que bloquea el mutex debe ser el
que lo desbloquea.
Las primitivas asociadas a un cierre
mutex son:
*mutex_enter()→adquiere el cierre:
potencialmente se
bloque si ya está
adquirido
*mutex_exit()→libera el cierre:
potencialmente desbloquea
a uno que espera
*mutex_tryenter()→adquiere el cierre
si aun no está
Semáforos
Semáforos enteros clásicos con la
siguiente primitiva:
*sema_p()→disminuye el semáforo,
potencialmente bloquea el
hilo
*sema_v()→incrementa el semáforo,
potencialmente
desbloquea un hilo
que espera
*sema_tryp()→si no es necesario
bloquearse, disminuye el
semáforo
Cierre de Lectores/Escritores
Permite a múltiples hilos tener acceso a solo-
lectura simultáneamente o a un objeto
protegido por el cierre.
Las primas son:
*rw_enter()→intenta adquirir un cierre como
lector o escritor
*rw_exit()→Libera un cierre como lector o
escritor
*rw_tryenter() →si no es necesario bloquear
se adquiere el cierre
*rw_downgrade()→un hilo que ha adquirido
un cierre de escritura lo
convierte en cierre de lectura
*rw_tryupgrade()→intenta convertir un cierre
de lectura en uno de escritura
Variables de Condición
Se utiliza para esperar hasta que sea cierta
una determinada condición, las primitivas
son:
*cv_wait() →bloquea hasta que señalice la
condición
*cv_signal()→despierta un hilo bloqueado
en cv_wait()
*cv_broadeast()→despierta todos los hilos
bloqueados en cv_wait
Windows 2000 ofrece sincronización entre
los hilos como parte de la arquitectura de
objetos, está formado por los siguientes
pasos para sincronización de objetos
*Proceso
*Hilo
*Archivo
*Entrada de Consola
*Notificación de Cambio de Archivo
*Mutante
*Semáforo
*Suceso
*Temporizador
