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.
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:
- 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.
- 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.
- 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.
Nenhum comentário:
Postar um comentário