Algoritmo del banquero

El algoritmo del banquero es un algoritmo de asignación de recursos y prevención de bloqueos desarrollado por Edsger Dijkstra que prueba la seguridad simulando la asignación de cantidades máximas posibles predeterminadas de todos los recursos y luego realiza una verificación de "estado" para probar posibles condiciones de bloqueo para todas las demás actividades pendientes, antes de decidir si se debe permitir que continúe la asignación.

El algoritmo fue desarrollado en el proceso de diseño del sistema operativo THE y descrito originalmente (en holandés) en EWD108. Cuando un nuevo proceso ingresa a un sistema, debe declarar la cantidad máxima de instancias de cada tipo de recurso que puede reclamar; claramente, esa cantidad no puede exceder la cantidad total de recursos en el sistema. Además, cuando un proceso obtiene todos los recursos solicitados, debe devolverlos en una cantidad finita de tiempo.

Para que el algoritmo del banquero funcione, necesita saber tres cosas:

• ¿Cuánto de cada recurso podría solicitar cada proceso ("MAX")
• Cuánta cantidad de cada recurso se mantiene actualmente cada proceso ("ALLOCATED")
• ¿Cuánto de cada recurso que el sistema tiene actualmente disponible ("AVAILABLE")

Los recursos se pueden asignar a un proceso sólo si la cantidad de recursos solicitados es menor o igual a la cantidad disponible; de lo contrario, el proceso espera hasta que haya recursos disponibles.

Algunos de los recursos que se rastrean en los sistemas reales son la memoria, los semáforos y el acceso a la interfaz.

El algoritmo del banquero debe su nombre al hecho de que este algoritmo podría utilizarse en un sistema bancario para garantizar que el banco no se quede sin recursos, ya que el banco nunca asignaría su dinero de tal manera que ya no pudiera satisfacer las necesidades de todos sus clientes. Al utilizar el algoritmo del banquero, el banco garantiza que cuando los clientes soliciten dinero, el banco nunca abandone un estado seguro. Si la solicitud del cliente no hace que el banco abandone un estado seguro, se asignará el efectivo; de lo contrario, el cliente deberá esperar hasta que otro cliente deposite lo suficiente.

Estructuras de datos básicas que se deben mantener para implementar el algoritmo del Banker:

Sea n el número de procesos en el sistema y m el número de tipos de recursos. Entonces necesitamos las siguientes estructuras de datos:

• Disponible: Un vector de longitud m indica el número de recursos disponibles de cada tipo. Si está disponible[j] = k, hay k casos de tipo de recurso R_j disponible.
• Max: An n × m matriz define la demanda máxima de cada proceso. Si Max[i,j] = k, entonces P_i puede solicitar a la mayoría de k casos de tipo de recurso R_j.
• Asignación: Una n × m matriz define el número de recursos de cada tipo asignados actualmente a cada proceso. Si Asignación[i,j] = k, entonces proceso P_i k casos de tipo de recurso R_j.
• Necesidad: Una n × m matriz indica la necesidad de recursos restantes de cada proceso. Si necesita [i,j] = k, entonces P_i puede necesitar k más casos de tipo de recurso R_j para completar la tarea.

Nota: Necesidad[i,j] = Máx[i,j] - Asignación[i,j]. n=m-a.

Los recursos totales del sistema son:
A B C D
6 5 7 6

Los recursos disponibles del sistema son:
A B C D
3 1 1 2

Procesos (recursos asignados actualmente):
A B C D
P1 1 2 1
P2 1 0 3
P3 1 2 1 0

Procesos (recursos máximos):
A B C D
P1 3 3 2
P2 1 2 3 4
P3 1 3 5 0

Necesidad = recursos máximos - recursos asignados actualmente
Procesos (posiblemente necesarios recursos):
A B C D
P1 2 1 0
P2 0 2 0 1
P3 0 1 4 0

Un estado (como en el ejemplo anterior) se considera seguro si es posible que todos los procesos terminen de ejecutarse (finalicen). Dado que el sistema no puede saber cuándo finalizará un proceso ni cuántos recursos habrá solicitado para entonces, el sistema supone que todos los procesos intentarán adquirir sus recursos máximos establecidos y finalizarán poco después. Esta es una suposición razonable en la mayoría de los casos, ya que al sistema no le preocupa especialmente cuánto tiempo se ejecuta cada proceso (al menos no desde la perspectiva de evitar bloqueos). Además, si un proceso finaliza sin adquirir su recurso máximo, solo se lo hace más fácil al sistema. Se considera que un estado seguro es el que toma la decisión de si va a procesarse en la cola de procesos listos.

Dada esa suposición, el algoritmo determina si un estado es seguro al intentar encontrar un conjunto hipotético de solicitudes de los procesos que permitirían a cada uno adquirir su máximo de recursos y luego terminar (devolviendo sus recursos al sistema). Cualquier estado en el que no exista dicho conjunto es un estado inseguro.

Podemos demostrar que el estado dado en el ejemplo anterior es un estado seguro al demostrar que es posible que cada proceso adquiera sus recursos máximos y luego finalice.

1. P1 necesidades 2 A, 1 B y 1 D más recursos, alcanzando su máximo
   • [recurso disponible: 1 2 − 1 0 1 = ♫ 0 1 ♫]
   • El sistema todavía tiene 1 A, no B, 1 C y 1 D recursos disponibles
2. P1 termina, devolviendo 3 A, 3 B, 2 C y 2 D recursos al sistema
   • [recurso disponible: ♫ 0 1 ♫ + # 3 2 2 # = 3 3 3]
   • El sistema cuenta ahora con 4 A, 3 B, 3 C y 3 D recursos disponibles
3. P2 adquiere 2 B y 1 D recursos extra, luego termina, devolviendo todos sus recursos
   • [recurso disponible: 3 3 3 − # 2 0 1 # + 2 3 4 = 3 6 6]
   • El sistema cuenta ahora con 5 recursos A, 3 B, 6 C y 6 D
4. P3 adquiere 1 B y 4 C recursos y termina.
   • [recurso disponible: 3 6 6 − # 4 0 # + 3 5 0 = 5 7 6]
   • El sistema tiene ahora todos los recursos: 6 A, 5 B, 7 C y 6 D
5. Debido a que todos los procesos pudieron terminar, este estado es seguro

Para un ejemplo de un estado inseguro, considere qué sucedería si el proceso 2 tuviera 1 unidad del recurso B al comienzo.

Cuando el sistema recibe una solicitud de recursos, ejecuta el algoritmo del banquero para determinar si es seguro conceder la solicitud. El algoritmo es bastante sencillo una vez que se comprende la distinción entre estados seguros e inseguros.

1. ¿Se puede conceder la solicitud?
   • Si no, la solicitud es imposible y debe ser negada o puesta en una lista de espera
2. Supongamos que se concede la solicitud
3. ¿Está seguro el nuevo estado?
   • En caso afirmativo la solicitud
   • Si no, niegue la solicitud o la ponga en una lista de espera

El hecho de que el sistema rechace o posponga una solicitud imposible o insegura es una decisión específica del sistema operativo.

 Ejemplo

Comenzando en el mismo estado en el que se inició el ejemplo anterior, supongamos que el proceso 1 solicita 2 unidades del recurso C.

1. No hay suficiente recurso C disponible para conceder la solicitud
2. Se niega la solicitud.

Por otra parte, supongamos que el proceso 3 solicita 1 unidad del recurso C.

1. Hay suficientes recursos para conceder la solicitud
2. Supongamos que se concede la solicitud
   • El nuevo estado del sistema sería:

 Recursos disponibles del sistema
A B C D
Gratis 3 1 0 2

 Procesos (recursos asignados actualmente):
A B C D
P1 1 2 1
P2 1 0 3
P3 1 2 2 0

 Procesos (recursos máximos):
A B C D
P1 3 3 2
P2 1 2 3 4
P3 1 3 5 0

1. Determinar si este nuevo estado es seguro
   1. P1 puede adquirir 2 recursos A, 1 B y 1 D y terminar
   2. Luego, P2 puede adquirir 2 recursos B y 1 D y terminar
   3. Por último, P3 puede adquirir 1 B y 3 C recursos y terminar
   4. Por lo tanto, este nuevo estado es seguro
2. Puesto que el nuevo estado es seguro, otorgar la solicitud

Ejemplo final: a partir del estado en el que comenzamos, supongamos que el proceso 2 solicita 1 unidad del recurso B.

1. Hay suficientes recursos
2. Asumiendo que se conceda la solicitud, el nuevo estado sería:

 Recursos disponibles del sistema:
A B C D
Gratis 3 0 1 2

 Procesos (recursos asignados actualmente):
A B C D
1 2 5 1
P2 1 3 3
P3 1 2 1 0

 Procesos (recursos máximos):
A B C D
P1 3 3 2
P2 1 2 3 4
P3 1 3 5 0

1. ¿Este estado es seguro? Asumiendo que P1, P2, y P3 soliciten más recursos B y C.
   • P1 no puede adquirir suficientes recursos B
   • P2 no puede adquirir suficientes recursos B
   • P3 es incapaz de adquirir suficientes recursos B
   • Ningún proceso puede adquirir suficientes recursos para terminar, por lo que este estado no es seguro
2. Puesto que el estado es inseguro, niegue la solicitud

importación numposo como npn_procesos = int()entrada()¿Número de procesos?)n_resources = int()entrada()"¿Número de recursos? ")disponibles_resources = [int()x) para x dentro entrada()"Claim vector? ").división()")actualmente_allocated = np.array([2] [int()x) para x dentro entrada()f"Actualmente asignado para el proceso {}i + 1}? ").división()") para i dentro rango()n_procesos)])max_demand = np.array([2] [int()x) para x dentro entrada()f"La demanda máxima del proceso {}i + 1}? ").división()") para i dentro rango()n_procesos)])total_disponible = disponibles_resources - np.suma()actualmente_allocated, axis=0)corriendo = np.uno()n_procesos) # Un array con n_processes 1's para indicar si el proceso aún está por ejecutarmientras np.Conde_nonzero()corriendo) ■ 0: at_least_one_allocated = Falso para p dentro rango()n_procesos): si corriendo[p]: si Todos()i >= 0 para i dentro total_disponible - ()max_demand[p] - actualmente_allocated[p]) at_least_one_allocated = Cierto. impresión()f"{}p} está corriendo") corriendo[p] = 0 total_disponible += actualmente_allocated[p] si no at_least_one_allocated: impresión()"Inseguro") descanso # Salida # más: impresión()"Safe")

Al igual que los demás algoritmos, el algoritmo del banquero tiene algunas limitaciones a la hora de implementarlo. En concreto, necesita saber qué cantidad de cada recurso podría solicitar un proceso. En la mayoría de los sistemas, esta información no está disponible, lo que hace imposible implementar el algoritmo del banquero. Además, no es realista suponer que el número de procesos es estático, ya que en la mayoría de los sistemas el número de procesos varía dinámicamente. Además, el requisito de que un proceso libere finalmente todos sus recursos (cuando el proceso termina) es suficiente para la corrección del algoritmo, pero no es suficiente para un sistema práctico. Esperar horas (o incluso días) para que se liberen los recursos no suele ser aceptable.

• "Operating System Concepts" de Silberschatz, Galvin y Gagne (páginas 259-261 de la séptima edición)
• "Operating System Concepts" de Silberschatz, Galvin y Gagne (páginas 298-300 de la 8a edición)
• Dijkstra, Edsger W. Las matemáticas detrás del Algorithm del Banker (EWD-623) (PDF). E.W. Dijkstra Archive. Centro de Historia Americana, Universidad de Texas en Austin. (transcripción) (1977), publicado como páginas 308 a 312 de Edsger W. Dijkstra, Escritos seleccionados sobre Computación: Una Perspectiva Personal, Springer-Verlag, 1982.