LockTwo de "L'art de la programmation multiprocesseur".

Question

Voici l'implémentation de mutext pour deux fils de "The Art of Multiprocessor Programming".

private int victim;
// thread-local index, 0 or 1

public void lock() {
  int i = ThreadID.get();
  victim = i;                 // let the other go first
  while (victim == i) {}      // spin
}
public void unlock() {}

Ils déclarent que ce code se bloque si "un thread passe devant l'autre". Quelqu'un peut-il décrire un exemple d'exécution entrelacée où aucun blocage ne se produit ?

Answer 1

Il se peut que ma compréhension soit erronée, auquel cas quelqu'un pourra, je l'espère, la clarifier (cc @SonarJetLens).

Dans le cas où un thread est complètement en avance sur l'autre, nous avons, par exemple, que le thread A acquiert le verrou et attend, parce qu'il est la victime. Il attend indéfiniment jusqu'à ce que le thread B arrive et se pose en victime, laissant ainsi A passer à sa section critique. Dans ce cas, je ne vois pas d'impasse : par définition, une impasse, c'est lorsqu'aucun progrès n'est réalisé par tout fil.

Toutefois, considérons le cas où le fil A ne tente jamais de récupérer le verrou. Dans ce cas, le thread B attendra indéfiniment, sans jamais pouvoir atteindre sa section critique. Pour moi, cela ressemble plus à famine ce qui signifie que le fil B a été affamé et n'a jamais pu acquérir le fil.

Si le programme s'arrête là, alors le thread A a fait des "progrès" en exécutant sa section critique, et le thread B n'en a pas fait, donc il n'y a pas de blocage. Cependant, il y a famine, puisque le fil B a essayé d'acquérir le verrou et n'a jamais réussi, ce qui contredit la définition de la liberté de famine.

J'espère que tout cela a un sens et que je ne fais pas d'erreur de terminologie ou de définition, et j'espère vraiment que quelqu'un pourra m'éclairer :).

Answer 2

Après l'avoir relu aujourd'hui, je pense que j'ai compris l'idée derrière "La classe LockTwo est inadéquate parce qu'elle se bloque si un thread s'exécute". completely avant l'autre."

si les threads A et B sont sérialisés, ce qui signifie que le thread B attend que le thread A termine, alors le thread A n'obtiendra jamais le verrou par "LockTwo", c'est une impasse par définition : Freedom from Deadlock: If some thread attempts to acquire the lock, then some thread will succeed in acquiring the lock. .

C'est plus évident si l'auteur écrit "La classe LockTwo est inadéquate parce qu'elle se bloque s'il n'y a qu'un seul thread. (Bien qu'il n'y ait aucun besoin du verrou).

Answer 3

En fait, un thread sera bloqué dans la boucle while jusqu'à ce qu'un autre thread entre dans lock() et modifie la valeur du champ de la victime.

Si un thread est complètement en avance sur un autre, c'est-à-dire que

thread A writes victim = A -> 
thread A reads Victim != A -> 
thread A do Critical Section -> 
thread B writes victim = B -> 
thread B reads Victim != B -> 
thread B do Critical Section

Cela provoquera un blocage car l'événement thread B writes victim = B doit venir avant thread A reads Victim != A sinon le fil d'événement A lit Victim != A bloquera indéfiniment.

Les opérations entrelacées empêchent les blocages, car, par exemple, lorsque le fil B écrit victim = B permettant à A de terminer et de retourner sa section critique, le fil B attend maintenant dans la boucle while jusqu'à ce que victim != B . Le fil B reviendra de la boucle while lorsque soit le fil A entrera à nouveau dans le verrou et changera la victime, soit un autre fil C entrera dans le verrou et changera la victime, permettant à B de passer à sa section critique. etc.

Answer 4

Je vais moi aussi tenter de répondre à cette question, bien que je sois un novice dans ce domaine.

Considérons la situation suivante (A et B sont des fils) :

writeA(victim=A) -> readA(victim != A) -> CSA

De même,

writeB(victim=B) -> readB(victim != B) -> CSB

Considérons maintenant le cas suivant :

Case 1: Lorsqu'un thread est complètement en avance sur un autre, c'est-à-dire que A -> B

Comme thread A démarre en premier, il définit le victim=A et attend, pendant ce temps thread B ne peut pas démarrer car il attend que le thread A termine l'exécution de la section critique. Ainsi, thread A attend thread B pour modifier le victim mais B attend le thread A pour compléter son CSA . Il y aura donc un blocage car les deux threads attendent deux conditions différentes :

Thread A is waiting so that thread B sets victim=B whereas thread B is waiting so that thread A completes its critical section (CSA).

Case 2: Lorsque les threads ont une exécution entrelacée.

Dans cette situation, étant donné que les deux threads démarrent presque en même temps (et en supposant qu'ils s'exécutent encore et encore, probablement en boucle), ils définiront alternativement la victime, permettant ainsi à l'autre de s'exécuter en alternance.