Algoritmo Del Banquero

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.

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,

...