Hispanopedia Wiki
Articulo de referencia

Algoritmo del banquero

El algoritmo del banquero es un algoritmo de asignación de recursos y prevención de interbloqueos desarrollado por Edsger Dijkstra que comprueba la seguridad simulando la asigna...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo del banquero es un algoritmo de asignación de recursos y prevención de interbloqueos desarrollado por Edsger Dijkstra que comprueba la seguridad simulando la asignación de cantidades máximas predeterminadas de todos los recursos y, a continuación, realiza una comprobación de "estado s" para detectar posibles condiciones de interbloqueo en todas las demás actividades pendientes, antes de decidir si se debe permitir que la asignación continúe.

El algoritmo se desarrolló durante el proceso de diseño del sistema operativo THE y se describió originalmente (en neerlandé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; obviamente, ese número no puede exceder el número total de recursos en el sistema. Además, cuando un proceso obtiene todos los recursos que solicitó, debe devolverlos en un tiempo finito.

Recursos

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

  • ¿Cuánto de cada recurso podría solicitar cada proceso ("MÁX")?
  • Cuánto de cada recurso está utilizando actualmente cada proceso ("ASIGNADO").
  • Cantidad de cada recurso que el sistema tiene disponible actualmente ("DISPONIBLE")

Los recursos solo se pueden asignar a un proceso 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 monitorizan 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 podría utilizarse en un sistema bancario para garantizar que el banco no se quede sin recursos, ya que nunca asignaría su dinero de forma que dejara de poder satisfacer las necesidades de todos sus clientes. [ 2 ] Mediante el algoritmo del banquero, el banco se asegura de que, cuando los clientes solicitan dinero, nunca abandone un estado seguro. Si la solicitud del cliente no provoca que el banco abandone dicho estado, se le asignará el efectivo; de lo contrario, el cliente deberá esperar hasta que otro cliente deposite la cantidad suficiente.

Estructuras de datos básicas que deben mantenerse 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:

  • Disponible: Un vector de longitud m indica la cantidad de recursos disponibles de cada tipo. Si Available[j] = k, hay k instancias del tipo de recurso R j disponibles.
  • Max: Una matriz n × m define la demanda máxima de cada proceso. Si Max[i,j] = k, entonces P i puede solicitar como máximo k instancias del tipo de recurso R j .
  • Asignación: Una matriz n × m define el número de recursos de cada tipo asignados actualmente a cada proceso. Si Asignación[i,j] = k, entonces al proceso P i se le asignan actualmente k instancias del tipo de recurso R j .
  • Necesidad: Una matriz n × m indica la necesidad de recursos restantes de cada proceso. Si Need[i,j] = k, entonces P i puede necesitar k instancias más del tipo de recurso R j para completar la tarea.

Nota: Need[i,j] = Max[i,j] - Allocation[i,j]. n=ma.

Ejemplo

Necesidad = recursos máximos - recursos actualmente asignados

Estados seguros e inseguros

Un estado (como en el ejemplo anterior) se considera seguro si todos los procesos pueden finalizar su ejecución. Dado que el sistema no puede saber cuándo terminará un proceso ni cuántos recursos habrá solicitado para entonces, asume que todos los procesos intentarán adquirir sus recursos máximos y finalizar 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 sus recursos máximos, facilita la tarea del sistema. Un estado seguro se considera el que toma la decisión de procesar la cola de procesos listos.

Partiendo de esa premisa, el algoritmo determina si un estado es seguro intentando encontrar un conjunto hipotético de solicitudes de los procesos que les permita adquirir sus recursos máximos y luego finalizar (devolviendo sus recursos al sistema). Cualquier estado en el que no exista tal conjunto es un estado inseguro .

Podemos demostrar que el estado dado en el ejemplo anterior es un estado seguro demostrando 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, alcanzando 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 recurso C y 1 recurso D disponibles.
  2. P1 finaliza, 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 4 recursos A, 3 B, 3 C y 3 D disponibles.
  3. P2 adquiere 2 recursos B y 1 recurso D adicionales, luego termina, 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 tiene 5 recursos A, 3 B, 6 C y 6 D.
  4. P3 adquiere 1 recurso B y 4 recursos C y finaliza.
    • [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. Dado 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 principio.

Solicitudes

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

  1. ¿Puede concederse la solicitud?
    • De lo contrario, la solicitud es imposible y debe ser denegada o puesta en lista de espera.
  2. Supongamos que la solicitud es concedida.
  3. ¿Es seguro el nuevo estado?
    • Si es así, conceder la solicitud.
    • De lo contrario, rechace la solicitud o agréguela a una lista de espera.

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

Ejemplo

Partiendo del mismo estado en el que comenzó el ejemplo anterior, supongamos que el proceso 1 solicita 2 unidades del recurso C.

  1. No hay suficientes recursos C disponibles para conceder la solicitud.
  2. La solicitud es denegada.

Por otro lado, supongamos que el proceso 3 solicita 1 unidad del recurso C.

  1. Existen recursos suficientes para conceder la solicitud.
  2. Supongamos que la solicitud es concedida.
    • El nuevo estado del sistema sería:
 Recursos del sistema disponibles ABCD Gratis 3 1 0 2
 Procesos (recursos asignados actualmente): ABCD P1 1 2 2 1 P2 1 0 3 3 P3 1 2 2 0
 Procesos (recursos máximos): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. Determina 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 recurso D y terminar
    3. Finalmente, P3 puede adquirir 1 recurso B y 3 recursos C y terminar
    4. Por lo tanto, este nuevo estado es seguro.
  2. Dado que el nuevo estado es seguro, concede la solicitud.

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

  1. Hay recursos suficientes
  2. Suponiendo que se apruebe la solicitud, el nuevo estado sería:
 Recursos del sistema disponibles: ABCD Gratis 3 0 1 2
 Procesos (recursos asignados actualmente): ABCD P1 1 2 5 1 P2 1 1 3 3 P3 1 2 1 0
 Procesos (recursos máximos): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. ¿Es seguro este estado? Suponiendo que P1, P2 y P3 solicitan más de los 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 no es seguro, deniegue la solicitud.
import numpy as npn_procesos = int ( input ( "Número de procesos? " )) n_recursos = int ( input ( "Número de recursos? " ))recursos_disponibles = [ int ( x ) para x en entrada ( "Vector de reclamación? " ) . split ( " " )]currently_allocated = np . array ([ [ int ( x ) for x in input ( f "Actualmente asignado para el proceso { i + 1 } ? " ) . split ( " " )] for i in range ( n_processes ) ])max_demanda = np . array ([ [ int ( x ) for x in input ( f "Demanda máxima del proceso { i + 1 } ? " ) . split ( " " )] for i in range ( n_processes ) ])total_disponible = available_resources - np.sum ( currently_allocated , axis = 0 ) running = np.ones ( n_processes ) # Un array con n_processes de 1 para indicar si el proceso aún no se ha ejecutadowhile np . count_nonzero ( running ) > 0 : at_least_one_allocated = False for p in range ( n_processes ): if running [ p ]: if all ( i >= 0 for i in total_available - ( max_demand [ p ] - currently_allocated [ p ])): at_least_one_allocated = True print ( f " { p } está en ejecución" ) running [ p ] = 0 total_available += currently_allocated [ p ] if not at_least_one_allocated : print ( "Inseguro" ) break # salir else : print ( "Seguro" )

Limitaciones

Al igual que otros algoritmos, el algoritmo del banquero presenta algunas limitaciones en su implementación. En concreto, requiere conocer la cantidad de cada recurso que un proceso podría solicitar. En la mayoría de los sistemas, esta información no está disponible, lo que imposibilita la implementación del algoritmo del banquero. Además, no es realista suponer que el número de procesos sea estático, ya que en la mayoría de los sistemas varía dinámicamente. Asimismo, si bien el requisito de que un proceso libere finalmente todos sus recursos (al finalizar) es suficiente para la corrección del algoritmo, no lo es para un sistema práctico. Esperar horas (o incluso días) a 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 neerlandés; Un algoritmo para la prevención del abrazo mortal )
  2. ↑ Silberschatz, Galvin y Gagne (2013). Conceptos de sistemas operativos, 9.ª edición . Wiley. pág. 330. ISBN  978-1-118-06333-0.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )

Lecturas adicionales

  • " Conceptos de sistemas operativos " de Silberschatz, Galvin y Gagne (páginas 259-261 de la 7ª edición)
  • " Conceptos de sistemas operativos " de Silberschatz, Galvin y Gagne (páginas 298-300 de la 8.ª edición)
  • Dijkstra, Edsger W. Las matemáticas detrás del algoritmo del banquero (EWD-623) (PDF) . Archivo EW Dijkstra. Centro de Historia Americana, Universidad de Texas en Austin .( transcripción ) (1977), publicada como páginas 308-312 de Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective , Springer-Verlag, 1982. ISBN 0-387-90652-5
  • Implementación del algoritmo del banquero en Java
  • Implementación del algoritmo del banquero en C
  • Implementación del algoritmo del banquero en C++

Obtenido de " https://en.wikipedia.org/w/index.php?title=Banker%27s_algorithm&oldid=1319231528 "
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...Asignación de recursosAsignación de recursosEn economía , la asignación de recursos es la asignación de los recursos disponibles a diversos usos. En el contexto de una economía en su conjunto...Punto muerto (informática)Punto muerto (informática)En la computación concurrente , el interbloqueo es cualquier situación en la que ningún miembro de un grupo de entidades puede continuar porque cad...Edsger W. DijkstraEdsger W. DijkstraEdsger Wybe Dijkstra ( / ˈ d aɪ k s t r ə / DYKE -strə ; holandés: [ ˈɛtsxər ˈʋibə ˈdɛikstraː ]ⓘ ; 11 de mayo de 1930 – 6 de agosto de 2002) fue un...Recurso del sistemaRecurso del sistemaEn informática , un recurso del sistema , o simplemente recurso , es cualquier componente físico o virtual de disponibilidad limitada al que puede ...Idioma holandésIdioma holandésUn hablante de holandés Holandés ( endónimo : Nederlands [ˈneːdərlɑnts]) ⓘ ) es una lengua germánica occidental , hablada por unos 25 millones de p...