Algoritmo del banquero

El Algoritmo del banquero, en sistemas operativos es una forma de evitar el interbloqueo, propuesta por primera vez por Edsger Dijkstra. Es un acercamiento teórico para evitar los interbloqueos en la planificación de recursos. Requiere conocer con anticipación los recursos que serán utilizados por todos los procesos. Esto último generalmente no puede ser satisfecho en la práctica.

Este algoritmo usualmente es explicado usando la analogía con el funcionamiento de un banco. Los clientes representan a los procesos, que tienen un crédito límite, y el dinero representa a los recursos. El banquero es el sistema operativo.

El banco confía en que no tendrá que permitir a todos sus clientes la utilización de todo su crédito a la vez. El banco también asume que si un cliente maximiza su crédito será capaz de terminar sus negocios y devolver el dinero a la entidad, permitiendo servir a otros clientes.

El algoritmo mantiene al sistema en un estado seguro. Un sistema se encuentra en un estado seguro si existe un orden en que pueden concederse las peticiones de recursos a todos los procesos, previniendo el interbloqueo. El algoritmo del banquero funciona encontrando estados de este tipo.

Los procesos piden recursos, y son complacidos siempre y cuando el sistema se mantenga en un estado seguro después de la concesión. De lo contrario, el proceso es suspendido hasta que otro proceso libere recursos suficientes.

En términos más formales, un sistema se encuentra en un estado seguro si existe una secuencia segura. Una secuencia segura es una sucesión de procesos, ${\displaystyle <P_{1}}$,..., ${\displaystyle P_{n}>}$, donde para un proceso ${\displaystyle P_{i}}$, el pedido de recursos puede ser satisfecho con los recursos disponibles sumados los recursos que están siendo utilizados por ${\displaystyle P_{j}}$, donde j < i. Si no hay suficientes recursos para el proceso ${\displaystyle P_{i}}$, debe esperar hasta que algún proceso ${\displaystyle P_{j}}$ termine su ejecución y libere sus recursos. Entonces podrá ${\displaystyle P_{i}}$ tomar los recursos necesarios, utilizarlos y terminar su ejecución. Al suceder esto, el proceso ${\displaystyle P}$_i+1 puede tomar los recursos que necesite, y así sucesivamente. Si una secuencia de este tipo no existe, el sistema se dice que está en un estado inseguro, aunque esto no implica que esté bloqueado.

Así, el uso de este tipo de algoritmo permite impedir el interbloqueo, pero supone una serie de restricciones:

• Se debe conocer la máxima demanda de recursos por anticipado.
• Los procesos deben ser independientes, es decir que puedan ser ejecutados en cualquier orden. Por lo tanto su ejecución no debe estar forzada por condiciones de sincronización.
• Debe haber un número fijo de recursos a utilizar y un número fijo de procesos.
• Los procesos no pueden finalizar mientras retengan recursos.

Estructuras y complejidad

Se deben utilizar cuatro estructuras de datos para implementar el algoritmo del banquero. Estas codifican el estado del sistema de asignación de recursos. Sea n, el número de procesos del sistema, m el número de tipos de recursos. Se necesita:

• Recursos (Available, disponible): Un vector de longitud m que mantiene la cantidad total de recursos, de cada tipo, que pueden ser utilizados por los procesos. De esta forma, Recursos[i] = k significa que hay una cantidad total k de recursos tipo ${\displaystyle R_{i}}$ disponibles.
• Demanda (Max): Esta matriz, ${\displaystyle n\times m}$, guarda las cantidades máximas de recursos de cada tipo que pueden ser demandadas por cada proceso. Si Max[i][j]=k, el proceso i, puede solicitar, como máximo k instancias del recurso j.
• Asignación (allocation): En esta matriz, n x m, número de recursos de cada tipo actualmente asignados a cada proceso. Asignación[i][j] = k significa que el proceso i tiene asignado k unidades del recurso j.
• Necesidad (need): Una matriz, n x m, que indica la necesidad restante de recursos de cada proceso. Si Necesidad[i][j] = k, entonces el proceso i puede necesitar k instancias del tipo de recurso j. Observe que Necesidad[i][j] = Max[i][j] - Asignación[i][j].

En términos de complejidad, el algoritmo del banquero es de orden O(n² × m), donde n es el número de procesos y m la cantidad de recursos.

Ejemplo

Recursos iniciales
R1	R2	R3
18	6	12

Recursos máximos					Recursos en uso					Recursos necesarios para finalizar
	R1	R2	R3			R1	R2	R3			R1	R2	R3
P1	6	4	4		P1	2	0	0		P1	4	4	4
P2	12	2	6		P2	10	2	2		P2	2	0	4
P3	6	2	8		P3	4	2	6		P3	2	0	2

Recursos disponibles=total recursos iniciales - total recursos en uso

Recursos disponibles
R1	R2	R3
2	2	4

Si, por ejemplo, P2 está solicitando (2,0,2): las matrices de recursos en uso y recursos necesarios para finalizar son las siguientes:

Recursos máximos					Recursos en uso					Recursos necesarios para finalizar
	R1	R2	R3			R1	R2	R3			R1	R2	R3
P1	6	4	4		P1	2	0	0		P1	4	4	4
P2	12	2	6		P2	12	2	4		P2	0	0	2
P3	6	2	8		P3	4	2	6		P3	2	0	2

Recursos disponibles
R1	R2	R3
0	2	2

• En primer lugar, miramos si el proceso 2 puede acabar su ejecución:

Recursos necesarios para finalizar					Recursos disponibles
	R1	R2	R3		R1	R2	R3
P1	4	4	4		0	2	0
P2	0	0	0
P3	2	0	2

• En segundo lugar, agregamos a la matriz de recursos disponibles los recursos que tenía en uso el proceso dos y miramos si el resto de procesos podrían acabar sin caer en un estado inseguro (insuficientes recursos disponibles):

Recursos en uso					Recursos necesarios					Recursos disponibles
	R1	R2	R3			R1	R2	R3		R1	R2	R3
P1	2	0	0		P1	4	4	4		12	4	4
P2	0	0	0		P2	0	0	0
P3	4	2	6		P3	2	0	2

• Como podemos comprobar, todo los procesos tienen recursos disponibles para finalizar, por lo que la solicitud de P2 habría que aceptarla.

Algoritmo de comprobación de estado seguro

Es un algoritmo que determina si el sistema está en un estado seguro y sin que haya que molestar a un recurso .2-xc tmlp .r3l-4t-cx1

Algoritmo de asignación de recursos

Este algoritmo determina si un pedido de recursos puede ser satisfecho de forma segura. Es ejecutado por el sistema cada vez que llega una petición de recursos por parte de un proceso.

Ejemplos

• https://web.archive.org/web/20160305125244/http://www.mcs.csueastbay.edu/~billard/os/cs6560.compact.pdf (en inglés), a partir de la transparencia 81.

Bibliografía

• Silberschatz, Abraham (2006). Sistemas Operativos. McGrawHill. pp. 229-230. ISBN 0-471-69466-5.

• Datos: Q386678