Bonjour,
Je cherche à retrouver les 4 conditions de Coffman pour un deadlock dans l'illustration de wikipedia ci-dessous:
Tiré de cet article: Deadlock#Necessary_conditions
Je ne suis pas trop sûr de moi. Est-ce que vous pouvez me dire ce que vous en pensez? Est-ce que j'ai une bonne formulation, non ambiguë?
Il faut séparer le problème en deux. Si il y a 4 boules ou plus sur chacune des 4 directions et si il y a 3 boules ou moins. Commençons par le cas 4 boules. Je montre que toutes les conditions du deadlock sont remplies:
- exclusion mutuelle: Oui, en particulier quand il y a 4 boules
- retiens et attends: une boule retiens toujours le verrou de la boule à sa gauche et attends la libération du verrou à sa droite
- Non préemptif: les threads gardent le contrôle sur leur verrou
- attente circulaire: la première boule est bloquée par la boule à sa droite, qui est bloquée par la boule à sa droite, et ainsi de suite jusqu'à fermer la boucle.
Les conditions étant suffisantes (d'après wikipedia), on aura un deadlock.
Si il n'y a que trois boules, deux conditions ne sont plus remplies. L'exclusion mutuelle car il y a une boule qui n'est exclue par aucune autre et l'attente circulaire. Les conditions étant nécessaires, un deadlock est donc impossible.
Autre question: Ces 4 conditions sont-elles aussi suffisantes comme cela est suggéré dans l'article? Il faut faire des hypothèses supplémentaire sur le scheduling, j'imagine. J'ai bien l'impression que je pourrais créer un scheduler qui ne va jamais autoriser un deadlock même avec 4 boules.
# Mon interprétation
Posté par NicolasP . Évalué à 2. Dernière modification le 25 août 2019 à 23:35.
L'exclusion mutuelle c'est l'existence d'une ressource qui ne peut pas être partagée. Un seul process à la fois peut y avoir accès. Le fait d'avoir 3 boules ne change rien à l'existence ou non de cette ressource. Il y a toujours l'exclusion mutuelle.
A noter que la légende du schéma indique que la ressource c'est la zone grise, mais l'animation ainsi que la "right-before-left policy" suggèrent plutôt 4 ressources partagées qui sont les intersections des lignes bleues.
Effectivement, elle n'existe plus et donc il n'y a plus le deadlock.
J'aurais dû mal à démontrer que c'est suffisant, je ne vois même pas dans quel formalisme se placer. Mais intuitivement, oui ça l'est.
Supposons que les 4 conditions (C1, C2, C3, C4) soient vérifiées. Pour qu'il n'y ait pas de deadlock, il faut au moins 1 process qui puisse faire évoluer son état. Disons que c'est P1. C4 implique que P1 soit en attente d'une ressource (disons R1) détenue par un autre process (disons P2). C1 implique que P1 doive attendre la libération de R1. C3 implique que seul P2 puisse libérer R1. Donc P1 ne peut faire évoluer son état avant P2. De même P2, ne peut pas faire évoluer son état avant P3, … jusqu'à Pn qui ne peut pas faire évoluer son état avant P1.
La seule possibilité qu'il n'y ait pas de deadlock est donc que tous les process fassent évoluer leurs états simultanément. Hors chaque process a besoin d'une ressource non partageable (C1) qui est aussi nécessité par un autre process. Du coup, la simultanéité est elle aussi interdite.
Dans le raisonnement ci-dessus, je ne me sers pas de C2, mais j'ai l'impression que c'est une forme affaiblie de C4. J'ai peut-être raté quelque chose.
Le scheduler pourrait peut-être éviter d'arriver dans la situation où les conditions sont vérifiées et donc éviter le deadlock. Mais si tu te places dans une situation où les conditions sont déjà vérifiées, aucun process ne peut tourner. Du coup le scheduler n'a aucune marge de manœuvre (autre que killer un process).
[^] # Re: Mon interprétation
Posté par j_m . Évalué à 3.
Je crois que je vois ce que tu veux dire.
Mais c'est un cas un peu bizarre ici, non? Il n'y a pas d'exclusion mutuelle pour deux boules en parallèles.
Oh je crois que j'étais passé à côté du truc…
Je voyais ça comme: s'il est possible que C1, C2, C3, C4 alors il y aura deadlock un jour.
J'avais mal interprété le simultané.
Oui du coup peu importe le scheduler. Si on entre dans un états où les 3 conditions sont remplies alors on n'en sortira jamais.
Merci pour les explications. Ta démonstration m'a bien aidée.
[^] # Re: Mon interprétation
Posté par NicolasP . Évalué à 2.
Je suppose que tu te places dans mon interprétation, c'est à dire que les ressources sont les intersections.
Dans cet article, l'exclusion mutuelle, c'est juste l'existence d'une ressource non partageable, c'est à dire qui ne peut pas être utilisée par 2 process en même temps. Avec 2 boules en parallèles, chacune a ses ressources non partageables. Mais ce n'est pas un problème car on ne veut pas les partager. Les conditions C2 et C4 ne seront jamais vérifiées.
[^] # Re: Mon interprétation
Posté par j_m . Évalué à 3.
J'ai trouvé un document qui formalise ces conditions. C'est intéressant: l'auteur arrive à extraire l'essentiel de ce qu'est un verrou, l'exclusion mutuelle ou une barrière. Mais ça devient un peu ardu lorsqu'on tourne les pages:
https://www.r2labs.org/pubs/algebra_ijnc.pdf
Pour lui les conditions ne sont pas nécessaires. On peut avoir un interblockage et les 4 conditions ne sont pas remplies; parce que le processus qui a le lock est dans un état zombie par exemple:
# Le nombre de boule n'est pas important
Posté par moi1392 . Évalué à 2.
Je ne vois pas pourquoi tu as besoin de séparer le cas >= 4 boules et les autres ?
Je suis allé voir la page wikipedia pour voir si cela parlait d'un cas particulier, mais, sauf si j'ai raté un truc, c'est bien une page sur les deadlock en général. (je ne sais pas s'il y a un terme dédié en français, j'utilise "interblocage" que j'ai lu à plusieurs endroits).
Et dans le cas général, un seul process est suffisant pour avoir un interblocage, exemple avec un pseudo code C :
RESSOURCE resource;
lock(resource);
lock(resource); // oups, to process est bloqué sans possibilité de se débloquer !
Donc, une boule suffit.
Après, si on exclu ce cas un peu particulier (qui peut tout de même arriver dans un programme complexe si on ne fais pas un minimum attention), ton exemple avec l'animation et les boules fonctionne très bien (ou très mal, selon le point de vue) avec 2 boules.
[^] # Re: Le nombre de boule n'est pas important
Posté par j_m . Évalué à 3. Dernière modification le 27 août 2019 à 21:15.
C'est à cause la priorité de droite. Si tu as trois boules, il y en a une qui n'a personne à sa droite et elle peut passer.
J'ai l'impression que tu n'en tiens pas compte dans ton commentaire. Je me trompe?
[^] # Re: Le nombre de boule n'est pas important
Posté par moi1392 . Évalué à 2. Dernière modification le 28 août 2019 à 00:11.
Ça dépends de ce que tu appelles la droite. Dans ton exemple, c'est juste utiliser pour trouver l'élément suivant de la liste des processus, parce qu'ils sont représentés sur un graphe planaire pour aider à la compréhension.
Mais dans le cas général, il n'y a pas de processus "à droite" d'un autre.
Si on reprends le formalisme de la page wikipédia, et en particulier le quatrième point :
"Circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, …, PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1"
Il fonctionne avec n=1, comme dans le cas que j'ai explicité dans mon poste précédent :
Le premier process P1 detiens une resource, et est en attente d'une resource (la même en l'occurence) détenue par le process suivant, mais comme P1=PN car il n'y a qu'un process, le process suivant se trouve être P1 lui même ("PN is waiting for a resource held by P1").
La boucle est bouclé, sans faire intervenir de notion de droite.
[^] # Re: Le nombre de boule n'est pas important
Posté par NeoX . Évalué à 2.
priorité à droite dans le cas de 4 voies
mais quid s'il n'y a qu'une seule ressource, avec 3 voies seulements,
alors c'est nombre de voies -1 (2 boules) qu'il faut appliquer,
et ca reste un cas tres particulier (le carrefour routier ou un seul vehicule peut passer à son tour) et c'est utiliser en algoritmie pour faire comprendre l'interblocage (deadlock) aux etudiants.
[^] # Re: Le nombre de boule n'est pas important
Posté par j_m . Évalué à 3.
A, oui. C'est intéressant. C'est pour éviter cette situation qu'on fait des verrous réentrant, non?
Y aurait-il une raison de faire un verrou non réentrant? C'est plus rapide?
[^] # Re: Le nombre de boule n'est pas important
Posté par moi1392 . Évalué à 3.
oui, c'est plus performant, tu n'as pas besoin de vérifier s'il a déjà été pris par le même thread, si tu prends les std::lock, il ne sont pas ré-entrant.
après tu peux ajouter une couche par dessus pour vérifier cela, et c'est certainement les vérrous dont tu parles.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.