Algoritmo del banquero

Llamado: (Algoritmo de Dijkstra)

Este algoritmo se usa para evitar interbloqueos en el sistema, básicamente procede de la

siguiente manera: cada proceso declara el máximo de recursos a utilizar y cada vez que
se hace una solicitud de asignación de recursos, se determina si al asignar los recursos
se deja en un estado inseguro y de ser así se pospone la asignación, de lo contrario, se
asignan los recursos solicitados.

Asignación
1. Se determina si hay disponiboles
2. Se valida que no exceda su máximo declarado
3. Se verifica 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.

Desventajas

 Se necesita saber desde un principio el máximo de recursos que usará cada

proceso
 Este 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
Ejemplo

proceso\recurso R1 (7) R2(7) R3(7)

P1 5 3 1
P2 3 2 3
Maximos
P3 2 3 1
P4 5 0 3
P1 3 3 1
P2 2 2 2
Asignados
P3 0 1 1
P4 0 0 1
P1 2 0 0
P2 1 0 1
Necesarios
P3 2 2 0
P4 5 0 2
Disponibles 2 1 2
Supongamos las siguiente 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

Algoritmo del Banquero

En principio, estudiaremos este algoritmo suponiendo que todos los

recursos del mismo tipo. Considérese la asignación de una
cantidad t, de unidades de cintas idénticas.

Un sistema operativo comparte un número fijo, t, de unidades de

cinta entre un número fijo de, p, de procesos. Cada proceso
especifica por adelantado el número máximo de unidades de cinta
que necesitará durante su ejecución. El sistema operativo aceptará la
petición de un usuario si la necesidad máxima de ese proceso no es
mayor que t. Un proceso puede obtener o liberar unidades de cinta
una a una. Algunas veces un usuario puede verse obligado a esperar
para obtener una unidad adicional, pero el sistema operativo
garantiza una espera finita. El número real de unidades asignadas a
un proceso nunca será superior a la necesidad máxima declarada por
ese usuario. Si el sistema operativo es capaz de satisfacer la
necesidad máxima del proceso, entonces éste debe garantizar al
sistema operativo que las unidades de cinta serán utilizadas y
liberadas en un tiempo finito.

Se dice que el estado del sistema es seguro si el sistema operativo

puede garantizar que todos los procesos terminan en un tiempo
finito. En otro caso, el sistema está en un estado inseguro.

Sea préstamo (i) la representación del préstamo actual de unidades

de cinta para el proceso i. Sea máx(i) la necesidad máxima de cintas
de un proceso y, por último, sea petición (i) la petición actual del
usuario, que es igual a su necesidad máxima menos el préstamo
actual. Por ejemplo, el proceso 7 tiene una necesidad máxima de 6
unidades y un préstamo actual de 5, entonces tiene

petición(7) = máx(7) - préstamo(7) = 6 - 5 = 2

 El sistema operativo controla t unidades de cinta. Sea a el número
de unidades de cinta todavía disponibles para asignar. Entonces a es
igual a t menos la suma de los préstamos de los usuarios.

El algoritmo del banquero permite la asignación de unidades de

cinta a los usuarios solamente cuando la asignación conduzca a
estados seguros, y no a estados inseguros. Un estado seguro es una
situación tal en la que todos los procesos son capaces de terminar en
algún momento. Un estado inseguro es aquel en el cual puede
presentarse un bloqueo mutuo.

Ejemplo de estado seguro

Supóngase que un sistema tiene doce unidades de cinta y tres

procesos que las comparten.

La tabla anterior representa un estado seguro porque el proceso 2

tiene un préstamo de 4 unidades y necesita como máximo 6, o sea, 2
más. El sistema tiene 12 de las cuales 10 están en uso y mantiene 2
disponibles. Si las que están disponible se asignan al proceso 2,
cubriendo su demanda máxima, este proceso podrá terminar. Al
acabar, devolverá todos los recursos, 6 unidades de cinta, y el
sistema podrá asignarlas al proceso 1 y al 3. De esta forma, la clave
de un estado seguro es que exista al menos una forma en la que
terminen todos los procesos.

Ejemplo de estado inseguro

 Ahora 11 de las 12 unidades de cinta están asignadas y solamente
hay una disponible. En este momento, no se puede garantizar que
terminen los tres procesos. Si el proceso 1 pide y obtiene la última
unidad de cinta y los tres vuelven a solicitar una unidad de cinta
más se produciría un bloqueo triple.

Es importante señalar, que un estado inseguro no implica la

existencia, ni siquiera eventual, de un interbloqueo. Lo que sí
implica un estado inseguro es la posibilidad de que ocurra por una
desafortunada secuencia de eventos.

Ejemplo de transición de estado seguro a estado inseguro

Saber que un estado es seguro no implica que serán seguros todos

los estados futuros. La política de asignación de recursos debe
considerar cuidadosamente todas las peticiones antes de
satisfacerlas. Por ejemplo supongamos la situación que se muestra
en la siguiente tabla.

Ahora supóngase que el proceso 3 pide un recurso más. Si el

sistema satisface esta petición, el nuevo estado será el que se
muestra en la tabla de abajo.
 Según vemos, aunque, en principio el sistema no estaba bloqueado,
ha pasado de un estado seguro a uno inseguro. La última de las
tablas caracteriza un sistema en el cual no puede garantizarse la
terminación de todos los procesos. Solamente hay un recurso
disponible, pero deben estarlo al menos dos para asegurar que el
proceso 2 o el 3 puedan terminar, devolver sus recursos al sistema y
permitir que los otros procesos acaben.

Defectos del algoritmo del banquero

El algoritmo del banquero es interesante porque ofrece una forma

de asignar los recursos que evita el interbloqueo. Permite ejecutar
procesos que tendrían que esperar seguramente con alguna de las
estrategias de prevención. Sin embargo, tiene varios defectos
importantes :

El algoritmo requiere un número fijo

de recursos asignables. Como los recursos a menudo
requieren servicio, ya sea por algún fallo o por
mantenimiento preventivo, no se puede contar con que
será siempre constante.

El algoritmo requiere una población de usuarios

constantes. En los sistemas multiprogramables y más
en los de tiempo compartido, la población de usuarios
cambia constantemente, incluso en cuestión de
segundos.

El algoritmo requiere que el banquero satisfaga

todas las peticiones en un tiempo finito. Es evidente
que en los sistemas reales esto no es una garantía
suficiente.

De manera similar, el algoritmo requiere que los

procesos salden sus préstamos (es decir, devuelvan sus
recursos) en un tiempo finito. Una vez más, esto es
insuficiente para un sistema de tiempo real.

El algoritmo requiere que los usuarios declaren por

anticipado sus necesidades máximas. A medida que la
 asignación de recursos se hace más dinámica, conocer
las necesidades máximas de un usuario presenta mayor
dificultad. De hecho, ahora que los sistemas
ofrecen interfaces gráficas, cada vez es más común
que los usuarios no tengan la menor idea de los
recursos que necesitan.

En resumen, los métodos descritos anteriormente en el apartado de

prevención son demasiado restrictivos, mientras que los de
evitación que acabas de estudiar requieren información de la que,
generalmente, no se dispone.