stringtranslate.com

Algoritmo bancario

El algoritmo bancario es un algoritmo de asignación de recursos y evitación de interbloqueos 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 interbloqueo para todos los demás. actividades pendientes, antes de decidir si se debe permitir que continúe la asignación.

El algoritmo se desarrolló en el proceso de diseño del sistema operativo THE y se describió originalmente (en holandés ) en EWD108. [1] Cuando un nuevo proceso ingresa a un sistema, debe declarar el número máximo de instancias de cada tipo de recurso que puede reclamar; Claramente, ese número no puede exceder el número total de recursos del sistema. Además, cuando un proceso obtiene todos los recursos solicitados, debe devolverlos en un tiempo finito.

Recursos

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

Se podrán asignar recursos 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 deriva su nombre del hecho de que este algoritmo podría usarse 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 pueda satisfacer las necesidades. 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 salga de 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 mantendrán para implementar el algoritmo del banquero:

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:

Nota: Necesidad[i,j] = Max[i,j] - Asignación[i,j]. n=ma.

Ejemplo

Los recursos totales del sistema son:A B C D6 5 7 6
Los recursos disponibles del sistema son:A B C D3 1 1 2
Procesos (recursos actualmente asignados): 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 actualmente asignadosProcesos (posiblemente recursos necesarios): A B C DP1 2 1 0 1P2 0 2 0 1P3 0 1 4 0

Estados seguros e inseguros

Un estado (como en el ejemplo anterior) se considera seguro si es posible que todos los procesos terminen de ejecutarse (terminar). Dado que el sistema no puede saber cuándo terminará un proceso, o cuántos recursos habrá solicitado para entonces, el sistema supone que todos los procesos eventualmente intentarán adquirir sus recursos máximos establecidos y terminará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 interbloqueos). Además, si un proceso finaliza sin adquirir su recurso máximo, solo lo hace más fácil para el sistema. Se considera que un estado seguro es quien toma las decisiones si va a procesar la cola lista.

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

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

  1. P1 necesita 2 A, 1 B y 1 D más recursos, logrando su máximo
    • [recurso disponible: ⟨3 1 1 2⟩ − ⟨2 1 0 1⟩ = ⟨1 0 1 1⟩ ]
    • El sistema ahora todavía tiene 1 recurso A, ningún recurso B, 1 C y 1 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 recursos 4 A, 3 B, 3 C y 3 D
  3. P2 adquiere 2 recursos B y 1 D adicionales, luego finaliza y devuelve 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 recursos 1 B y 4 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 terminar, este estado es seguro

Como ejemplo de un estado inseguro, considere lo que sucedería si el proceso 2 tuviera 1 unidad del recurso B al principio.

Peticiones

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

  1. ¿Se puede acceder a la solicitud?
    • De lo 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?
    • Si es así concede la solicitud
    • En caso contrario, rechazar la solicitud o ponerla en 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, suponga 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 otro lado, supongamos que el proceso 3 solicita 1 unidad del recurso C.

  1. Hay recursos suficientes 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 actualmente asignados): 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 terminar
    2. Entonces, P2 puede adquirir 2 recursos B y 1 D y terminar
    3. Finalmente, P3 puede adquirir recursos 1 B y 3 C y terminar
    4. Por 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 disponibles del sistema: A B C DGratis 3 0 1 2
 Procesos (recursos actualmente asignados): 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 este estado seguro? 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 terminar, por lo que este estado no es seguro
  2. Dado que el estado es inseguro, rechace la solicitud.
importar  numpy  como  npn_processes  =  int ( input ( "¿Número de procesos? " )) n_resources  =  int ( input ( "¿Número de recursos? " ))recursos_disponibles  =  [ int ( x )  para  x  en  entrada ( "¿Vector de reclamo?" ) . dividir ( " " )]actualmente_asignado  =  np . matriz ([  [ int ( x )  para  x  en  entrada ( f "Actualmente asignado para el proceso { i + 1 } ? " ) . split ( " " )] para i en rango ( n_procesos ) ])      demanda_max  =  np . matriz ([  [ int ( x )  para  x  en  entrada ( f "Demanda máxima del proceso { i + 1 } ? " ) . split ( " " )] para i en rango ( n_procesos ) ])      total_disponible  =  recursos_disponibles  -  np . suma ( actualmente asignada ,  eje = 0 ) en ejecución  =  np . ones ( n_processes )  # Una matriz con n_processes unos para indicar si el proceso aún no se ha ejecutadomientras  np . count_nonzero ( en ejecución )  >  0 :  al menos_uno_allocado  =  Falso  para  p  en el  rango ( n_procesos ):  si  se está ejecutando [ p ]:  si  todo ( i  >=  0  para  i  en  total_disponible  -  ( max_demand [ p ]  -  actualmente_allocado [ p ])):  al menos_uno_allocado  =  Verdadero  imprimir ( f " { p } se está ejecutando" )  ejecutando [ p ]  =  0  total_disponible  +=  actualmente_asignado [ p ]  si  no  al_menos_uno_asignado :  imprimir ( "Inseguro" )  romper  # salir  más :  imprimir ( "Seguro" )

Limitaciones

Al igual que los otros algoritmos, el algoritmo del banquero tiene algunas limitaciones cuando se implementa. Específicamente, 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 bancario. 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 eventualmente todos sus recursos (cuando finalice el proceso) es suficiente para la corrección del algoritmo, pero no es suficiente para un sistema práctico. Por lo general, no es aceptable esperar horas (o incluso días) para que se liberen los recursos.

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. pag. 330.ISBN​ 978-1-118-06333-0.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )

Otras lecturas