Algoritmo do banqueiro - Banker's algorithm

O algoritmo do Banker , às vezes referido como o algoritmo de detecção , é uma alocação de recursos e algoritmo de prevenção de deadlock desenvolvido por Edsger Dijkstra que testa a segurança simulando a alocação de quantidades máximas possíveis predeterminadas de todos os recursos e, em seguida, cria um "estado s" verifique para testar possíveis condições de impasse para todas as outras atividades pendentes, antes de decidir se a alocação deve continuar.

O algoritmo foi desenvolvido no processo de design para o sistema operacional THE e originalmente descrito (em holandês ) em EWD108. Quando um novo processo entra em um sistema, ele deve declarar o número máximo de instâncias de cada tipo de recurso que pode reivindicar; claramente, esse número não pode exceder o número total de recursos no sistema. Além disso, quando um processo obtém todos os recursos solicitados, ele deve devolvê-los em um período de tempo finito.

Recursos

Para que o algoritmo do banqueiro funcione, ele precisa saber três coisas:

  • Quanto de cada recurso cada processo poderia solicitar [MAX]
  • Quanto de cada recurso cada processo está mantendo atualmente [ALLOCATED]
  • Quanto de cada recurso o sistema tem atualmente disponível [DISPONÍVEL]

Os recursos podem ser alocados a um processo apenas se a quantidade de recursos solicitados for menor ou igual ao valor disponível; caso contrário, o processo espera até que os recursos estejam disponíveis.

Alguns dos recursos rastreados em sistemas reais são memória , semáforos e acesso à interface .

O algoritmo do banqueiro deriva seu nome do fato de que este algoritmo poderia ser usado em um sistema bancário para garantir que o banco não ficasse sem recursos, porque o banco nunca alocaria seu dinheiro de tal forma que não pudesse mais satisfazer o necessidades de todos os seus clientes. Ao usar o algoritmo do banqueiro, o banco garante que, quando os clientes solicitam dinheiro, o banco nunca saia de um estado seguro. Se a solicitação do cliente não fizer com que o banco saia de um estado seguro, o dinheiro será alocado, caso contrário, o cliente deve esperar até que outro cliente deposite o suficiente.

Estruturas de dados básicas a serem mantidas para implementar o Algoritmo do Banqueiro:

Let Ser o número de processos no sistema e ser o número de tipos de recursos. Então, precisamos das seguintes estruturas de dados:

  • Disponível: um vetor de comprimento m indica o número de recursos disponíveis de cada tipo. Se Disponível [j] = k, existem k instâncias do tipo de recurso R j disponíveis.
  • Máx: Uma matriz × define a demanda máxima de cada processo. Se Max [i, j] = k, então P i pode solicitar no máximo k instâncias do tipo de recurso R j .
  • Alocação: Uma matriz × define o número de recursos de cada tipo atualmente alocado para cada processo. Se Allocation [i, j] = k, então o processo P i é atualmente alocado k instâncias do tipo de recurso R j .
  • Necessidade: uma matriz × indica a necessidade de recursos restantes de cada processo. Se Need [i, j] = k, então P i pode precisar de mais k instâncias do tipo de recurso R j para completar a tarefa.

Nota: Necessidade [i, j] = Máx [i, j] - Alocação [i, j]. n = ma.

Exemplo 

Total system resources are:
A B C D
6 5 7 6

Available system resources are:
A B C D
3 1 1 2

Processes (currently allocated resources):
   A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

Processes (maximum resources):
   A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Need = maximum resources - currently allocated resources
Processes (possibly needed resources):
   A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

Estados seguros e inseguros

Um estado (como no exemplo acima) é considerado seguro se for possível que todos os processos concluam a execução (terminem). Como o sistema não pode saber quando um processo será encerrado, ou quantos recursos ele terá solicitado até então, o sistema assume que todos os processos tentarão adquirir seus recursos máximos declarados e encerrarão logo em seguida. Essa é uma suposição razoável na maioria dos casos, uma vez que o sistema não está particularmente preocupado com quanto tempo cada processo é executado (pelo menos não de uma perspectiva de prevenção de deadlock). Além disso, se um processo termina sem adquirir seu recurso máximo, isso apenas torna mais fácil para o sistema. Um estado seguro é considerado o tomador de decisão se for processar a fila pronta.

Dada essa suposição, o algoritmo determina se um estado é seguro tentando encontrar um conjunto hipotético de solicitações pelos processos que permitiria a cada um adquirir seus recursos máximos e, em seguida, terminar (retornando seus recursos ao sistema). Qualquer estado onde não exista tal conjunto é um estado inseguro .


Podemos mostrar que o estado dado no exemplo anterior é um estado seguro, mostrando que é possível para cada processo adquirir seus recursos máximos e, em seguida, terminar.

  1. P1 precisa de mais 2 A, 1 B e 1 D de recursos, atingindo seu máximo
    • [recurso disponível: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
    • O sistema agora ainda tem 1 recurso A, nenhum B, 1 C e 1 D disponíveis
  2. P1 termina, retornando recursos 3 A, 3 B, 2 C e 2 D para o sistema
    • [recurso disponível: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
    • O sistema agora tem 4 recursos A, 3 B, 3 C e 3 D disponíveis
  3. P2 adquire 2 B e 1 D recursos extras, então termina, retornando todos os seus recursos
    • [recurso disponível: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
    • O sistema agora tem recursos 5 A, 3 B, 6 C e 6 D
  4. P3 adquire recursos 1 B e 4 C e termina.
    • [recurso disponível: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
    • O sistema agora tem todos os recursos: 6 A, 5 B, 7 C e 6 D
  5. Como todos os processos foram encerrados, este estado é seguro

Para obter um exemplo de um estado inseguro, considere o que aconteceria se o processo 2 contivesse 2 unidades do recurso B no início.

solicitações de

Quando o sistema recebe uma solicitação de recursos, ele executa o algoritmo do banqueiro para determinar se é seguro atender à solicitação. O algoritmo é bastante simples, uma vez que a distinção entre estados seguros e inseguros é compreendida.

  1. O pedido pode ser atendido?
    • Caso contrário, o pedido é impossível e deve ser negado ou colocado na lista de espera
  2. Suponha que a solicitação seja concedida
  3. O novo estado é seguro?
    • Se assim for, conceda o pedido
    • Caso contrário, negue o pedido ou coloque-o na lista de espera

Se o sistema nega ou adia uma solicitação impossível ou insegura é uma decisão específica do sistema operacional.

Exemplo

Começando no mesmo estado em que o exemplo anterior começou, suponha que o processo 1 solicite 2 unidades do recurso C.

  1. Não há recurso C suficiente disponível para atender a solicitação
  2. O pedido é negado


Por outro lado, suponha que o processo 3 solicite 1 unidade do recurso C.

  1. Existem recursos suficientes para atender o pedido
  2. Suponha que a solicitação seja concedida
    • O novo estado do sistema seria: 
    Available system resources
     A B C D
Free 3 1 0 2

    Processes (currently allocated resources):
     A B C D
P1   1 2 2 1
P2   1 0 3 3
P3   1 2 2 0

    Processes (maximum resources):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0
  1. Determine se este novo estado é seguro
    1. P1 pode adquirir recursos 2 A, 1 B e 1 D e encerrar
    2. Então, P2 pode adquirir recursos 2 B e 1 D e encerrar
    3. Finalmente, P3 pode adquirir recursos 1 B e 3 C e encerrar
    4. Portanto, este novo estado é seguro
  2. Como o novo estado é seguro, conceda a solicitação


Exemplo final: do estado em que começamos, suponha que o processo 2 solicite 1 unidade do recurso B.

  1. Existem recursos suficientes
  2. Supondo que a solicitação seja concedida, o novo estado seria: 
    Available system resources:
     A B C D
Free 3 0 1 2

    Processes (currently allocated resources):
     A B C D
P1   1 2 5 1
P2   1 1 3 3
P3   1 2 1 0

    Processes (maximum resources):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0
  1. Este estado é seguro? Supondo que P1, P2 e P3 solicitem mais do recurso B e C.
    • P1 não consegue adquirir recursos B suficientes
    • P2 não consegue adquirir recursos B suficientes
    • P3 não consegue adquirir recursos B suficientes
    • Nenhum processo pode adquirir recursos suficientes para encerrar, portanto, este estado não é seguro
  2. Como o estado não é seguro, negue a solicitação 
import numpy as np

n_processes = int(input('Number of processes? '))
n_resources = int(input('Number of resources? '))

available_resources = [int(x) for x in input('Claim vector? ').split(' ')]

currently_allocated = np.array([[int(x) for x in input('Currently allocated for process ' + str(i + 1) + '? ').split(' ')] for i in range(n_processes)])
max_demand = np.array([[int(x) for x in input('Maximum demand from process ' + str(i + 1) + '? ').split(' ')] for i in range(n_processes)])

total_available = available_resources - np.sum(currently_allocated, axis=0)

running = np.ones(n_processes)  # An array with n_processes 1's to indicate if process is yet to run

while 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(str(p) + ' is running')
                running[p] = 0
                total_available += currently_allocated[p]
    if not at_least_one_allocated:
        print('Unsafe')
        exit()
                
print('Safe')

Limitações

Como os outros algoritmos, o algoritmo do banqueiro tem algumas limitações quando implementado. Especificamente, ele precisa saber quanto de cada recurso um processo pode solicitar. Na maioria dos sistemas, essas informações não estão disponíveis, impossibilitando a implementação do algoritmo do banqueiro. Além disso, não é realista supor que o número de processos seja estático, pois na maioria dos sistemas o número de processos varia dinamicamente. Além disso, o requisito de que um processo irá eventualmente liberar todos os seus recursos (quando o processo termina) é suficiente para a correção do algoritmo, porém não é suficiente para um sistema prático. Esperar horas (ou mesmo dias) para que os recursos sejam liberados geralmente não é aceitável.

Referências

Leitura adicional