Algoritmo do banqueiro

O algoritmo foi desenvolvido por Edsger Dijkstra em 1965. É um algoritmo de alocação de recursos com prevenção de impasses 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, logo 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.

Algoritmo do banqueiro com múltiplos recursos

O algoritmo do banqueiro pode ser generalizado para tratar múltiplos recursos. A figura abaixo mostra como ele funciona.

Na figura 1 vemos duas matrizes. A primeira, do lado esquerdo, mostra quanto de cada recurso atualmente está alocado para cada um dos cinco processos. A matriz do lado direito mostra de quantos recursos cada processo ainda precisa para completar sua execução.

Os três vetores à direita da figura mostram:

·         E recursos existentes.

·         P recursos alocados.

·         A recursos disponíveis.

 E revela que o sistema tem seis unidades de fita, três Plotters, quatro impressoras e duas unidades de CD-ROM. Desses recursos, cinco acionadores de fita, três plotters, duas impressoras e duas unidades de CD-ROM se encontram alocados. Esse fato pode ser observado se somando-se as quatro colunas de recursos na matros do lado esquerdo. O vetor de recursos disponíveis é simplesmente a diferença entre aquilo que o sistema tem e aquilo que atualmente está em uso pelos processos.

O algoritmo que verifica se um estado é seguro é descrito a seguir:

1. Procure uma linha, R cujas necessidades de recursos sejam todas inferiores ou iguais a A. Se não existir nenhuma linha com essas características, o sistema acabará por entrar em situação de impasse, visto que nenhum processo pode ser executado até sua conclusão isso presumindo que os processos mantêm todos os recursos ate que terminem.
2. Considere que o processo da linha escolhida requisita todos os recursos de que precisa (o que se garante ser possível) e termina. Marque esse processo como terminado e adicione ao vetor A todos os recursos que lhe pertenciam.
3.  Repita os passos 1 e 2 até que todos os processos sejam marcados como terminados, que é o caso seguro, ou até ocorrer um impasse, que é o caso inseguro.

Se vários processos são elegíveis para serem escolhidos no passo 1, não importa qual deles é selecionado: o pool de recursos disponíveis pode ficar maior ou, na pior das hipóteses, permanecer o mesmo, em função da ordem de atendimento aos processos.

Ainda analisando a figura 1. O estado atual é seguro. Suponha que o processo B agora requisite uma impressora. Essa requisição pode ser atendida porque o estado resultante ainda é seguro (o processo D pode terminar e, depois, os processos A ou E, seguidos dos demais).

Imagine então que, após alocar para B uma das duas impressoras restantes, E queira a ultima impressora. O atendimento dessa requisição reduziria o vetor de recursos disponíveis a (1 0 0 0), o que levaria a um impasse assim fica muito claro que a requisição de E deve ser negada por enquanto.

Embora que a teoria do algoritmo do banqueiro seja maravilhosa, na pratica ela é inútil, porque os processos raramente sabem com antecipação o máximo de recursos de que vão precisar. Além disso, o número de processos não é fixo, mas varia dinamicamente à medida que novos usuários entram e saem. E, também, recursos que aparentemente estavam disponíveis poderão desaparecer repentinamente. Assim na prática, poucos são os sistemas que usam o algoritmo do banqueiro para evitar impasses ou talvez nenhum use.