stringtranslate.com

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 s" para probar posibles condiciones de bloqueo para todas las demás actividades pendientes, antes de decidir si se debe permitir que la asignación continúe.

El algoritmo fue desarrollado en el proceso de diseño del sistema operativo THE y originalmente descrito (en holandés ) en EWD108. [1] 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.

Recursos

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

Se pueden asignar recursos a un proceso sólo si la cantidad de recursos solicitada es menor o igual a la cantidad disponible; de ​​lo contrario, el proceso espera hasta que los recursos estén disponibles.

Algunos de los recursos que se rastrean en 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, porque el banco nunca asignaría su dinero de tal manera que ya no pudiera satisfacer las necesidades de todos sus clientes. [2] 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 debe esperar hasta que otro cliente deposite lo suficiente.

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

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

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

Ejemplo

Los recursos totales del sistema son:A B C D6 5 7 6
Los recursos del sistema disponibles son:A B C D3 1 1 2
Procesos (recursos asignados actualmente): A B C DP1 1 2 2 1P2 1 0 3 3P3 1 2 1 0
Procesos (recursos máximos): A B C DP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
Necesidad = recursos máximos - recursos asignados actualmenteProcesos (posiblemente recursos necesarios): A B C DP1 2 1 0 1P2 0 2 0 1P3 0 1 4 0

Estados seguros y no seguros

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 si va a procesarse en la cola de procesos listos.

Teniendo en cuenta 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 mostrar que es posible que cada proceso adquiera sus recursos máximos y luego finalice.

  1. P1 necesita 2 A, 1 B y 1 D recursos más, logrando su máximo
    • [recurso disponible: ⟨3 1 1 2⟩ − ⟨2 1 0 1⟩ = ⟨1 0 1 1⟩ ]
    • El sistema todavía tiene 1 recurso A, ningún recurso B, 1 recurso C y 1 recurso D disponibles
  2. P1 termina, devolviendo 3 recursos A, 3 B, 2 C y 2 D al sistema
    • [recurso disponible: ⟨1 0 1 1⟩ + ⟨3 3 2 2⟩ = ⟨4 3 3 3⟩ ]
    • El sistema ahora tiene disponibles 4 recursos A, 3 B, 3 C y 3 D
  3. P2 adquiere 2 recursos B y 1 D adicionales, luego finaliza, devolviendo todos sus recursos
    • [recurso disponible: ⟨4 3 3 3⟩ − ⟨0 2 0 1⟩ + ⟨1 2 3 4⟩ = ⟨5 3 6 6⟩ ]
    • El sistema ahora cuenta con 5 recursos A, 3 B, 6 C y 6 D
  4. P3 adquiere 1 recurso B y 4 recursos C y termina.
    • [recurso disponible: ⟨5 3 6 6⟩ − ⟨0 1 4 0⟩ + ⟨1 3 5 0⟩ = ⟨6 5 7 6⟩ ]
    • El sistema ahora tiene todos los recursos: 6 A, 5 B, 7 C y 6 D
  5. Debido a que todos los procesos pudieron finalizar, este estado es seguro.

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

Solicitudes

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. ¿Puede concederse la solicitud?
    • En caso contrario, la solicitud es imposible y debe ser rechazada o puesta en lista de espera.
  2. Supongamos que se concede la solicitud
  3. ¿Es seguro el nuevo estado?
    • En caso afirmativo, conceda la solicitud.
    • En caso contrario, rechace la solicitud o póngala en una lista de espera.

Si el sistema rechaza o pospone una solicitud imposible o insegura es una decisión específica del sistema operativo.

 Ejemplo

Comenzando en el mismo estado en el que comenzó 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. La solicitud es denegada


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 del sistema disponibles A B C DGratis 3 1 0 2
 Procesos (recursos asignados actualmente): A B C DP1 1 2 2 1P2 1 0 3 3P3 1 2 2 0
 Procesos (recursos máximos): A B C DP1 3 3 2 2P2 1 2 3 4P3 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 terminarlos
    2. Luego, P2 puede adquirir 2 recursos B y 1 D y terminar
    3. Finalmente, P3 puede adquirir 1 recurso B y 3 recursos C y terminarlos.
    4. Por lo tanto, este nuevo estado es seguro.
  2. Dado que el nuevo estado es seguro, conceda la solicitud.


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

  1. Hay suficientes recursos
  2. Suponiendo que se conceda la solicitud, el nuevo estado sería:
 Recursos del sistema disponibles: A B C DGratis 3 0 1 2
 Procesos (recursos asignados actualmente): A B C DP1 1 2 5 1P2 1 1 3 3P3 1 2 1 0
 Procesos (recursos máximos): A B C DP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
  1. ¿Es seguro este estado? Suponiendo que P1, P2 y P3 solicitan más recursos B y C.
    • P1 no puede adquirir suficientes recursos B
    • P2 no puede adquirir suficientes recursos B
    • P3 no puede adquirir suficientes recursos B
    • Ningún proceso puede adquirir suficientes recursos para finalizar, por lo que este estado no es seguro.
  2. Dado que el estado no es seguro, deniegue la solicitud.
importar  numpy  como  npn_procesos  =  int ( input ( "¿Número de procesos? " )) n_recursos  =  int ( input ( "¿Número de recursos? " ))recursos_disponibles  =  [ int ( x )  para  x  en  entrada ( "¿Reclamar vector? " ) . split ( " " )]actualmente_asignado  =  np . array ([  [ int ( x )  para  x  en  entrada ( f "Actualmente asignado para el proceso { i + 1 } ? " ) . split ( " " )] para i en rango ( n_procesos ) ])      max_demand  =  np . array ([  [ int ( x )  para  x  en  entrada ( f "Demanda máxima del proceso { i + 1 } ? " ) . split ( " " )] para i en rango ( n_procesos ) ])      total_available  =  available_resources  -  np . sum ( currently_allocated ,  axis = 0 ) running  =  np . ones ( n_processes )  # Una matriz con n_processes 1 para indicar si el proceso aún no se ha ejecutadomientras  np . count_nonzero ( en ejecución )  >  0 :  al_menos_uno_asignado  =  False  para  p  en  rango ( n_procesos ):  si  se está ejecutando [ p ]:  si  todos ( i  >=  0  para  i  en  total_disponible  -  ( demanda_máxima [ p ]  -  actualmente_asignado [ p ])):  al_menos_uno_asignado  =  True  print ( f " { p } se está ejecutando" )  en ejecución [ p ]  =  0  total_disponible  +=  actualmente_asignado [ p ]  si  no está  al_menos_uno_asignado :  print ( "Inseguro" )  break  # salir  de lo contrario :  print ( "Seguro" )

Limitaciones

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 de forma dinámica. 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.

Referencias

  1. ^ Dijkstra, Edsger W. Un algoritmo para voorkoming van de dodelijke omarming (EWD-108) (PDF) . Archivo EW Dijkstra. Centro de Historia Estadounidense, Universidad de Texas en Austin .(transcripción) (en holandés; Un algoritmo para la prevención del abrazo mortal )
  2. ^ Silberschatz, Galvin y Gagne (2013). Conceptos de sistemas operativos, novena edición . Wiley. pág. 330. ISBN 978-1-118-06333-0.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )

Lectura adicional