Algoritmo del Banquero

Llamado también negativa de asignación de recursos, el algoritmo resuelve un problema planteado por Edsger Dijkstra.

Existe un banco que tiene una reserva limitada de dinero a prestar y clientes con línea de crédito. Un cliente pide dinero y no hay garantía de que haga reposiciones hasta que saque la cantidad máxima. El banco puede rechazar el préstamo si hay riesgo de que no tenga fondos para prestar a otros clientes

Viéndolo como Sistema Operativo, los clientes serían los procesos, el dinero a prestar los recursos y el banquero el S.O.

Para este algoritmo es importante considerar los siguientes puntos:

• Estado. Es la asignación actual de los recursos a los procesos.
• Matriz demanda (o máximo necesario). Son las exigencias máximas de recursos para cada proceso.
• Matriz asignación. Son las asignaciones actuales de recursos para cada proceso.
• Vector disponible. Cantidad total de recursos sin asignar a los procesos.
• Estado seguro. Es un estado en el que existe al menos un orden en el que todos los procesos pueden ejecutar hasta el final sin generar interbloqueo.

Cuando un proceso realiza una solicitud de recursos, se supone que se concede, se actualiza el estado y se toma una decisión. Si se llega a un estado seguro, se concede la petición. Si se llega a uno inseguro, se rechaza y el proceso es bloqueado.

A continuación se presenta un ejemplo:

Utilizando el algoritmo del banquero resuelva el siguiente problema, indicando el orden en que los procesos pasan a ser estados seguros evitando el problema del interbloqueo.


Lista de procesos: P₁-P₃-P₄-P₀ ó P₂

A la derecha se tienen 5 procesos, cada uno tiene recursos de tipo A, B y C. En la primer columna de asignados está la cantidad de recursos que el proceso ha obtenido a lo largo de un tiempo; en la segunda columna de Máximo Necesario, están los recursos que tiene que obtener de cada tipo para comenzar a ser ejecutado. Por ejemplo, el P0 no ha obtenido ningún recurso del tipo A, sólo 1 del tipo B y ninguno del tipo C, y necesita para ejecutarse haber conseguido 7 del A, 5 del B y 3 del C.

En la última columna se tienen los recursos disponibles que da el sistema, los que se pueden utilizar con todos los procesos. Hay 3 del A, 3 del B y 2 del C.
El algoritmo del banquero trata de asegurar qué proceso tiene un “estado seguro” es decir, se requiere alcanzar el máximo requerido entre los que estén en Asignados y los que se encuentren en Disponibles.
Ejemplo: El proceso 0 no está en estado seguro. Si se suman Asignados + Disponibles para cada uno de los recursos A, B y C, realmente no se alcanzan los Máximos Requeridos.

Entonces se va al proceso 1 y se trata de hacer lo mismo, sumar Asignados + Disponibles. Allí sí se tiene un ESTADO SEGURO, A con 5, B con 3 y C con 2, y como se alcanza a llenar los Máximos, ese proceso se ejecuta.

Una vez que el proceso se ejecutó, entonces se procede a SUMAR los recursos asignados del proceso anterior a los disponibles. Hay que recordar que el proceso al terminar de ejecutarse libera todos sus recursos, por lo tanto pasan tanto los de tipo A, B y C a sumarse con los disponibles 3-3-2 y se tendrán nuevos DISPONIBLES que repartir, siendo ahora éstos 5-3-2.
Con estos se pasa al proceso P₂ y así sucesivamente.
Y el algoritmo es como sigue:

(El algoritmo principal es el de asignación de recursos)

Ventajas del algoritmo del banquero:

• No es necesario expulsar y hacer retroceder procesos como en la detección del interbloqueo.
• Es menos restrictivo que la prevención.

Desventajas:

• Se debe conocer la máxima demanda de recursos por anticipado.
• La ejecución de los recursos no debe estar forzada por la sincronización.
• Se tiene un número fijo de procesos y recursos.
• Los procesos no finalizan mientras retengan recursos.
• Requiere que los procesos salden sus préstamos en un tiempo finito.