El algoritmo del banquero , a veces conocido como el algoritmo de detección , es una asignación de recursos y punto muerto evitación algoritmo desarrollado por Edsger Dijkstra que las pruebas para la seguridad mediante la simulación de la asignación de posibles cantidades máximas predeterminadas de todos los recursos , y luego hace una "s-estado" verifique para probar posibles condiciones de interbloqueo para todas las 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 en el sistema. Además, cuando un proceso obtiene todos los recursos solicitados, debe devolverlos en un período de tiempo finito.
Recursos
Para que el algoritmo del banquero funcione, necesita saber tres cosas:
- Cuánto de cada recurso podría solicitar cada proceso [MAX]
- Cuánto de cada recurso contiene cada proceso actualmente [ASIGNADO]
- Qué cantidad de cada recurso tiene disponible actualmente el sistema [DISPONIBLE]
Los recursos pueden asignarse a un proceso solo 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 sistemas reales son la memoria , los semáforos y el acceso a la interfaz .
El algoritmo bancario 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 de todos sus clientes. [2] Al utilizar el algoritmo bancario, el banco se asegura de 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 debe esperar hasta que otro cliente deposite lo suficiente.
Estructuras de datos básicas que se deben mantener para implementar el algoritmo bancario:
Dejar ser el número de procesos en el sistema y sea 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 Disponible [j] = k, hay k instancias del tipo de recurso R j disponibles.
- Max: An × La matriz 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: An × La matriz define el número de recursos de cada tipo asignados actualmente a cada proceso. Si Allocation [i, j] = k, entonces el proceso P i k casos se asigna actualmente de tipo de recurso R j .
- Necesidad: una × La matriz indica la necesidad de recursos restantes de cada proceso. Si Necesita [i, j] = k, entonces P i puede necesitar k más instancias del tipo de recurso R j para completar la tarea.
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 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 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 asume 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 el sistema no está particularmente preocupado por la duración de cada proceso (al menos no desde la perspectiva de evitar un punto muerto). Además, si un proceso termina sin adquirir su máximo recurso, solo lo hace más fácil para el sistema. Se considera que un estado seguro es el que toma las decisiones si va a procesar la cola lista.
Dado ese supuesto, el algoritmo determina si un estado es seguro al tratar de encontrar un conjunto hipotético de solicitudes por parte de los procesos que permitiría 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 termine.
- 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, no B, 1 C y 1 D disponible
- P1 termina y devuelve 3 A, 3 B, 2 C y 2 D recursos 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
- P2 adquiere 2 recursos adicionales B y 1 D, 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
- P3 adquiere recursos 1 B y 4 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
- Debido a que todos los procesos pudieron terminar, este estado es seguro
Para ver un ejemplo de un estado inseguro, considere lo que sucedería si el proceso 2 tuviera 2 unidades del recurso B al principio.
Peticiones
Cuando el sistema recibe una solicitud de recursos, ejecuta el algoritmo bancario 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.
- ¿Se puede conceder la solicitud?
- De lo contrario, la solicitud es imposible y debe ser denegada o puesta en una lista de espera.
- Suponga que se concede la solicitud
- ¿Es seguro el nuevo estado?
- Si es así, conceda la solicitud
- De lo contrario, rechace la solicitud o colóquela en una lista de espera.
Si el sistema niega 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.
- No hay suficiente recurso C disponible para conceder la solicitud
- La solicitud es denegada
Por otro lado, suponga que el proceso 3 solicita 1 unidad de recurso C.
- Hay suficientes recursos para conceder la solicitud.
- Suponga que se concede la solicitud
- El nuevo estado del sistema sería:
Recursos del sistema disponibles A B C DLibre 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
- Determine si este nuevo estado es seguro
- P1 puede adquirir 2 recursos A, 1 B y 1 D y terminar
- Entonces, P2 puede adquirir 2 recursos B y 1 D y terminar
- Finalmente, P3 puede adquirir 1 B y 3 C recursos y terminar
- Por lo tanto, este nuevo estado es seguro.
- Dado que el nuevo estado es seguro, conceda la solicitud
Ejemplo final: desde el estado en el que comenzamos, suponga que el proceso 2 solicita 1 unidad de recurso B.
- Hay suficientes recursos
- Suponiendo que se conceda la solicitud, el nuevo estado sería:
Recursos del sistema disponibles: A B C DLibre 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
- ¿Es este estado seguro? Suponiendo 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 no puede adquirir suficientes recursos B
- Ningún proceso puede adquirir suficientes recursos para finalizar, por lo que este estado no es seguro.
- Dado que el estado no es seguro, rechace la solicitud
importar numpy como npn_procesos = int ( input ( '¿Número de procesos?' )) n_resources = int ( input ( '¿Número de recursos?' ))available_resources = [ int ( x ) para x en la entrada ( '¿Reclamar vector?' ) . dividir ( '' )]actualmente_asignado = np . array ([[ int ( x ) para x en input ( 'Actualmente asignado para proceso' + str ( i + 1 ) + '?' ) . split ( '' )] para i en rango ( n_processes )]) max_demand = np . array ([[ int ( x ) para x en la entrada ( 'Demanda máxima del proceso' + str ( i + 1 ) + '?' ) . split ( '' )] para i en el rango ( n_procesos )])total_available = available_resources - np . suma ( actualmente_asignado , eje = 0 )corriendo = np . ones ( n_processes ) # Una matriz con n_processes 1's para indicar si el proceso aún no se ha ejecutadomientras que np . count_nonzero ( corriendo ) > 0 : at_least_one_allocated = False para p en la gama ( n_processes ): si se ejecuta [ p ]: si todos ( i > = 0 para i en total_available - ( max_demand [ p ] - currently_allocated [ p ])): at_least_one_allocated = Verdadero impresión ( str ( p ) + 'se está ejecutando' ) ejecuta [ p ] = 0 total_available + = currently_allocated [ p ] si no at_least_one_allocated : impresión ( 'inseguro' ) salida () imprimir ( 'Seguro' )
Limitaciones
Al igual que los otros algoritmos, el algoritmo de Banker 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, por lo que es 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 finalmente libere todos sus recursos (cuando el proceso termina) es suficiente para la corrección del algoritmo, sin embargo, 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
- ^ Dijkstra, Edsger W. Een algoritmo ter 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 )
- ^ Silberschatz, Galvin y Gagne (2013). Conceptos del sistema operativo, novena edición . Wiley. pag. 330. ISBN 978-1-118-06333-0.CS1 maint: varios nombres: lista de autores ( enlace )
Otras lecturas
- " Conceptos del sistema operativo " de Silberschatz, Galvin y Gagne (páginas 259-261 de la séptima edición)
- " Conceptos del sistema operativo " de Silberschatz, Galvin y Gagne (páginas 298-300 de la octava edición)
- Dijkstra, Edsger W. Las matemáticas detrás del algoritmo del banquero (EWD-623) (PDF) . Archivo EW Dijkstra. Centro de Historia Estadounidense, Universidad de Texas en Austin .( transcripción ) (1977), publicado como páginas 308–312 de Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective , Springer-Verlag, 1982. ISBN 0-387-90652-5