Peterson Lock dans un arbre binaire

Question

J'ai des doutes sur l'algorithme de Peterson dans un arbre binaire.

Je fais quelques exercices du livre « The Art of multiprocesseur Programmation » et je suis coincé dans le chapitre 2, ex 13:

« Une autre façon de généraliser le verrou Peterson à deux fils est d'organiser un nombre de verrous Peterson à 2 fils dans un arbre binaire Supposons que n soit une puissance de 2. Chaque verrou est affecté à un thread qu'il partage avec un autre thread Chaque verrou traite un thread comme thread 0 et l'autre thread 1."

OK, mais quoi? Si Peterson ne traite que 2 threads, comment sera cet arbre? Un arbre avec UNE seule feuille? (parce que si j'ai 2 threads, et chaque feuille traite 2 threads ... le résultat sera un arbre avec une seule feuille?)

"Dans la méthode d'acquisition de l'arbre-serrure, le fil acquiert tous les deux fils Le verrou de Peterson à partir de la feuille de ce thread à la racine.L'élément de verrouillage de l'arbre pour le verrou arborescence déverrouille chacun des verrous Peterson à 2 fils que le fil a acquis, de la racine vers sa feuille. "

Que voulait-il dire par là? Comment une feuille peut-elle passer par le nœud racine? Très confus!! : S

Merci les gars!

Answer 1

La généralisation à utiliser n deux fils serrures Peterson et les disposer dans un arbre binaire fonctionne comme suit:

Pour acquérir le verrou:

1. Supposons qu'il existe n threads qui veulent pour accéder à une région critique.
2. La première étape utilise des verrous Peterson n/2 à deux fils. Ensuite, deux threads sont affectés à chaque verrou Peterson à deux threads. A la fin de cette étape, seulement n/2 threads acquis le verrou. Ces n/2 verrous Peterson à deux fils sont les feuilles de l'arbre binaire
3. Similaire à la première étape, la deuxième étape utilise n/4 deux threads Peterson verrous et deux threads sont affectés pour chaque verrou Peterson (ces fils sont les "gagnants" dans la première étape). Ces n/4 verrous Peterson sont les nouveaux nœuds de l'arbre
4. Cette procédure se poursuit jusqu'à atteindre la racine, où un seul verrou Peterson est nécessaire. Le thread qui acquiert le dernier verrou Peterson peut entrer dans la région critique.

Pour libérer le verrou

Le fil qui a acquis le verrou doit libérer chaque verrou Peterson dans le chemin qu'il a suivi de la feuille correspondant à la racine.

J'espère que cette explication vous servira.