Algoritmo do banqueiro

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde janeiro de 2014).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

O Algoritmo do banqueiro é um algoritmo de alocação de recursos com prevenção de impasses desenvolvido por Edsger Dijkstra que testa a segurança pela simulação da alocação do máximo pré-determinado possível de montantes de todos os recursos computacionais, e em seguida faz uma verificação de estados-seguros para testar a possibilidade de condições de impasse para todas as outras atividades pendentes, antes de decidir se a alocação deve prosseguir.

O algoritmo foi desenvolvido durante o projeto do sistema operacional THE e originalmente descrito (em Holandês) em EWD108.[1] O nome é por analogia a maneira com que os banqueiros respondem por constrangimentos de liquidez.

Algoritmo[editar | editar código-fonte]

O algoritmo do banqueiro é executado pelo sistema operacional quando um processo de computação requisita recursos..[2]

O algoritmo impede o impasse, ao negar ou adiar o pedido se ele determinar que aceitar o pedido pode colocar o sistema em um estado inseguro (onde um impasse poderia ocorrer). 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 não pode exceder o número total de recursos no sistema.

Recursos[editar | editar código-fonte]

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

  • Quanto de cada recurso cada processo poderia solicitar
  • Quanto de cada recurso cada processo atualmente detém
  • Quanto de cada recurso o sistema tem disponível

Recursos podem ser atribuídos a um processo somente se forem preenchidas as seguintes condições: 1.Pedido <= máximo, senão ajuste a condição de erro definida como o processo ultrapassou a quantidade máxima feita por ele. 2.Pedido <= disponível, senão o processo tem que esperar até que mais recursos estejam disponíveis.

Alguns dos recursos que são controlados em sistemas reais são memória, semáforos e interfaces de acesso.

Exemplo[editar | editar código-fonte]

Supondo que o sistema distingue quatro tipos de recursos, (A, B, C e D), o seguinte é um exemplo de como esses recursos poderiam ser distribuídos. Note que este exemplo mostra o sistema em um instante antes de um novo pedido de recursos chegar. Além disso, os tipos e número de recursos são abstraídos. Sistemas reais, por exemplo, lidariam com quantidades muito maiores de cada recurso.

Recursos do sistema disponíveis são: 
A B C D
3 1 1 2
Processos (recursos atualmente alocados):
   A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 1 1 0
Processos (máximo de recursos):
   A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 1 5 0

Estados seguros e inseguros[editar | editar código-fonte]

Um estado (como no exemplo acima) é considerada seguro se é possível para todos os processos concluir sua execução (terminar). Desde que o sistema não pode saber quando o processo será encerrado, ou quantos recursos ele terá solicitado até então, o sistema assume que todos os processos acabarão por tentar adquirir o máximo de seus recursos previstos e encerrar logo depois. Esta é uma suposição razoável na maioria dos casos uma vez que o sistema não está particularmente preocupado com o tempo que cada processo é executado (pelo menos não numa perspectiva de prevenção de deadlocks). Além disso, se um processo termina sem adquirir o seu máximo de recursos, isto só torna mais fácil para o sistema.

Dada esta premissa, o algoritmo determina se um estado é seguro, tentando encontrar um conjunto hipotético de pedidos pelos processos que permitiriam a cada, a aquisição de seus recursos máximos e depois o seu término (retornando os seus recursos para o sistema). Qualquer estado onde tal conjunto não existe é definido como um estado inseguro.

Pseudocódigo[editar | editar código-fonte]

function algoritmo_do_banqueiro(conjunto de processos P, recursos atualmente disponíveis A) {

    while (P não vazio) {
        boolean achou = false
        for each (processo p in P) {
            Cp = atual alocação de recursos para o processo(p)
            Mp = requisito máximo de recursos para o processo(p)
            if (Mp − Cp ≤ A) {
                // p pode obter tudo de que necessita.
                // Suponha que ele faz isso, termina, e libera o que ele já tem.
                A = A + Cp
                remove_elemento_do_conjunto(p, P)
                achou = true
            }
        }
        if (not achou) {
            return INSEGURO
        }
    }
    return SEGURO
}

[3]

Exemplo[editar | editar código-fonte]

Podemos mostrar que o estado dado no exemplo anterior é um estado de segurança, mostrando que é possível para cada processo adquirir o máximo de seus recursos e, em seguida, finalizar.

  1. P1 adquire os recursos 2 A, 1 B e 1 D, atingindo o seu máximo
    • O sistema agora ainda tem 1 A, nenhum B, 1 C e 1 D como recursos disponíveis
  2. P1 termina, retornando os recursos 3 A, 3 B, 2 C e 2 D para o sistema
    • O sistema tem agora os recursos disponíveis 4 A, 3 B, 3 C e 3 D
  3. P2 adquire 2 B e 1 D recursos extras, então termina, retornando todos os seus recursos
    • O sistema tem agora os recursos 5 A, 3 B, 6 C e 6 D
  4. P3 adquire os recursos 4 C e termina
    • O sistema tem agora todos os recursos: 6 A, 4 B, 7 C e 6 D
  5. Porque todos os processos foram capazes de terminar, esse estado é seguro

Note-se que estes pedidos e aquisições são hipotéticos. O algoritmo gera eles para verificar a segurança do estado, mas nenhum recurso é efectivamente dado e nenhum processo realmente termina. Observe também que a ordem em que esses pedidos são gerados - se vários possam ser satisfeitos - não importa, porque todos os pedidos hipótéticos deixam o processo terminar, aumentando assim os recursos livres do sistema.

Para um exemplo de um estado inseguro, considere o que aconteceria se o processo 2 estavesse segurando mais 1 unidade do recurso B no início.

Pedidos[editar | editar código-fonte]

Quando o sistema recebe um pedido de recursos, é executado o algoritmo do banqueiro para determinar se ele é seguro com o propósito de se deferir o pedido. O algoritmo é bastante simples uma vez a distinção entre os Estados seguros e inseguros ter sido compreendida.

  1. Pode o pedido ser concedido?
  2. * Se não, o pedido é impossível e deve ser negado ou colocado em lista de espera
  3. Suponha que o pedido é concedido
  4. O novo estado é seguro?
  5. * Sendo assim deferir o pedido
  6. * Se não, negar o pedido, ou colocá-lo em uma lista de espera

Se o sistema nega ou adiar um pedido impossível ou inseguro é uma decisão específica do sistema operacional.

Exemplo[editar | editar código-fonte]

Continuando o exemplo anterior, suponha que o processo 3 solicite 2 unidades de recursos C.

  1. Não há o suficiente de recursos de C disponíveis para deferir o pedido
  2. O pedido é negado


Por outro lado, assuma-se que o processo 3 pedidos solicite 1 unidade do recurso C.

  1. Existem recursos suficientes para deferir o pedido
  2. Suponha que o pedido for deferido
  3. * O novo estado do sistema seria:
Recursos do sistema disponíveis são: 
       A B C D
Livres 3 1 0 2
Processos (recursos atualmente alocados):
     A B C D
P1   1 2 2 1
P2   1 0 3 3
P3   1 1 2 0
Processos (recursos máximos):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 1 5 0
  1. Determinar se este novo estado é seguro
    1. P1 pode adquirir os recursos 2 A, 1 B e 1 D e finalizar
    2. Então, P2 pode adquirir os recursos 2 B e 1 D e finalizar
    3. Finalmente, P3 pode adquirir os recursos 3 C e terminar
    4. Assim, este novo estado é seguro
  2. Uma vez que o novo estado é seguro, deferir o pedido


Finalmente, suponha que o processo 2 requisite 1 unidade de recursos B.

  1. Existem recursos suficientes
  2. Supondo que o pedido seja deferido, o novo estado seria:
Recursos do sistema disponíveis são: 
       A B C D
Livres 3 0 1 2
Processos (recursos atualmente alocados):
     A B C D
P1   1 2 2 1
P2   1 1 3 3
P3   1 1 1 0
Processos (recursos máximos):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 1 5 0
  1. Este estado é seguro? Assumindo que P1, P2 e P3 requisitem mais dos recursos B e C.
    • P1 é incapaz de adquirir recursos suficientes de B
    • P2 é incapaz de adquirir recursos suficientes de B
    • P3 é incapaz de adquirir recursos suficientes de C
    • Nenhum processo pode adquirir recursos suficientes para finalizar, assim que este estado não é seguro
  2. Uma vez que o estado é inseguro, negar o pedido

Note que neste exemplo, nenhum processo foi capaz de terminar. É possível que alguns processos estejam aptos a terminar, mas não todos eles. Isso ainda seria um estado inseguro.

Trade-offs[editar | editar código-fonte]

Como a maioria dos algoritmos, o algoritmo do banqueiro envolve alguns dilemas (trade-offs). Especificamente, ele precisa saber o quanto de cada recurso de um processo poderia ser requerido. Na maioria dos sistemas, esta informação não está disponível, fazendo com que o algoritmo do banqueiro seja inútil. Além disso, é irrealista supor que o número de processos seja estático. Na maioria dos sistemas o número de processos varia dinamicamente. Além disso, a exigência de que um processo acabará por 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 por horas (ou até mesmo dias) que os recursos sejam liberados normalmente não é aceitável.

Leitura complementar[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Referências

  1. E. W. Dijkstra "EWD108: Een ter algorithme voorkoming van de omarming dodelijke" (em holandês; Um algoritmo para a prevenção do abraço mortal)
  2. Bic, Lubomir F.; Shaw, Alan C.. Operating System Principles. 2ª ed. [S.l.]: Prentice Hall, 2003. ISBN 0-13-026611-6
  3. Concurrency