Algorithme de Dijkstra banquiers

Question

Quelqu'un pourrait-il s'il vous plaît fournir une approche progressive par la résolution du problème suivant à l'aide de l'algorithme de banquier? Comment puis-je déterminer si un « Safe State » existe? Qu'est-ce que l'on entend quand un processus peut « exécuter jusqu'à la fin »?

Dans cet exemple, j'ai quatre processus et 10 instances de la même ressource.

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

Answer 1

Par Wikipedia ,

  

Un état (comme dans l'exemple ci-dessus) est considéré comme sûr s'il est possible pour tous les processus de fin d'exécution (fin). Étant donné que le système ne peut pas savoir quand un processus prendra fin, ou combien de ressources il aura demandé alors, le système suppose que tous les processus finiront par tenter d'acquérir leurs ressources maximales et la fin peu après. Cette hypothèse est raisonnable dans la plupart des cas étant donné que le système est particulièrement préoccupé par la durée de chaque processus se déroule (au moins pas d'un point de vue d'évitement de blocage). En outre, si un processus se termine sans acquérir ses maximum de ressources, il ne fait que rendre plus facile sur le système.

Un processus peut fonctionner jusqu'à la fin lorsque le nombre de chaque type de ressource dont elle a besoin sont disponibles, entre lui-même et le système. Si un processus a besoin de 8 unités d'une ressource donnée, et a alloué 5 unités, alors il peut courir jusqu'à la fin s'il y a au moins 3 autres unités disponibles qu'il peut allouer.

Étant donné votre exemple, le système gère une seule ressource, avec 10 unités disponibles. Les procédés de fonctionnement ont déjà alloué 8 (1 + 1 + 2 + 4) unités, donc il y a 2 unités restantes. La quantité que tout processus doit achever son maximum est moins ce qu'il a déjà alloué, de sorte que, au début, un besoin de plus de 5 (6-1), B a besoin de plus quatre (5-1), C 2 a besoin de plus (4- 2), et a besoin D 3 plus (7-4). Il existe deux disponibles, le procédé C est autorisé à exécuter à la fin, libérant ainsi 2 unités (4 laissant disponible). À ce stade, B ou D peuvent être exécutés (nous supposerons D). Une fois que D est terminée, il y aura 8 unités disponibles, après quoi A ou B peuvent être exécutés (nous supposerons A). Une fois que A a terminé, il y aura 9 unités disponibles, puis B peut être exécuté, ce qui laissera les 10 unités restantes pour d'autres travaux. Étant donné que nous pouvons choisir un ordre des processus qui permettront à tous les processus à exécuter, l'état est considéré comme « sûr ».

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

Le total des ressources allouées est 8 D'où 2 ressources sont encore à affecter par conséquent, qui est alloué pour le traitement C et le procédé c après la fin de reliefs 4 les ressources qui peuvent être données à traiter B, Procédé B après avoir terminé revit 5 ressources, qui sont alloués pour traiter un processus de n A après finition alloue 2 ressources pour traiter D