Algoritmo de Dijkstra's Bankers

Question

Alguém poderia fornecer uma abordagem passo a passo para resolver o problema a seguir usando o algoritmo do banqueiro? Como determino se existe um "estado seguro"? O que se entende quando um processo pode "executar até a conclusão"?

Neste exemplo, tenho quatro processos e 10 instâncias do mesmo recurso.

          Resources Allocated | Resources Needed
Process A                   1                  6
Process B                   1                  5
Process C                   2                  4
Process D                   4                  7

Answer 1

Por Wikipedia,

Um estado (como no exemplo acima) é considerado seguro se for possível para que todos os processos terminem de executar (encerrar). Como o sistema não pode saber quando um processo será encerrado, ou quantos recursos solicitarão até então, o sistema pressupõe que todos os processos eventualmente tentarão adquirir seus recursos máximos declarados e encerrar logo depois. Essa é uma suposição razoável na maioria dos casos, pois o sistema não está particularmente preocupado com quanto tempo cada processo funciona (pelo menos não de uma perspectiva de evitação de impasse). Além disso, se um processo terminar sem adquirir seus recursos máximos, ele apenas facilita o sistema.

Um processo pode ser concluído quando o número de cada tipo de recurso que ele precisa estiver disponível, entre si e o sistema. Se um processo precisar de 8 unidades de um determinado recurso e alocar 5 unidades, ele poderá ser concluído se houver pelo menos mais 3 unidades disponíveis que poderão alocar.

Dado o seu exemplo, o sistema está gerenciando um único recurso, com 10 unidades disponíveis. Os processos de execução já alocaram 8 (1+1+2+4) unidades, portanto restam 2 unidades. A quantidade que qualquer processo precisa concluir é o máximo que já foi alocado, portanto, no início, precisa de mais 5 (6-1), B precisa de mais 4 (5-1), C precisa de mais 2 (4- 2) e D precisa de mais 3 (7-4). Existem 2 disponíveis, portanto, o processo C pode ser executado, liberando assim 2 unidades (deixando 4 disponíveis). Neste ponto, B ou D pode ser executado (assumiremos D). Depois que D estiver concluído, haverá 8 unidades disponíveis, após as quais A ou B podem ser executadas (assumiremos a). Depois que A estiver concluído, haverá 9 unidades disponíveis e B pode ser executado, o que deixará todas as 10 unidades restantes para mais trabalhos. Como podemos selecionar uma ordem de processos que permitirão que todos os processos sejam executados, o estado é considerado "seguro".

Answer 2

  Resources Allocated | Resources Needed    claim
  Process A      1                  6            5
  Process B      1                  5            4
  Process C      2                  4            2
  Process D      4                  7            3

Os recursos totais alocados são 8, portanto, 2 recursos ainda precisam ser alocados, portanto, que é alocado para processar C. e processar C após o término do alívio 4 recursos que podem ser dados ao processo B, Processar B após o término revive 5 recursos que são alocados para processar a O N Processo A após o término aloca 2 recursos para processar D