Quelle est la différence entre l'impasse et le livelock?

Réponses:

398

Tiré de http://en.wikipedia.org/wiki/Deadlock :

Dans le calcul simultané, un blocage est un état dans lequel chaque membre d'un groupe d'actions attend qu'un autre membre libère un verrou

Un livelock est similaire à une impasse, sauf que les états des processus impliqués dans le livelock changent constamment les uns par rapport aux autres, aucun ne progressant. Livelock est un cas particulier de famine liée aux ressources; la définition générale indique seulement qu'un processus spécifique ne progresse pas.

Un exemple réel de livelock se produit lorsque deux personnes se rencontrent dans un couloir étroit, et chacune essaie d'être polie en s'écartant pour laisser passer l'autre, mais elles finissent par se balancer d'un côté à l'autre sans faire de progrès car elles se déplacent toutes les deux à plusieurs reprises de la même manière en même temps.

Livelock est un risque avec certains algorithmes qui détectent et récupèrent des blocages. Si plusieurs processus prennent des mesures, l'algorithme de détection de blocage peut être déclenché à plusieurs reprises. Cela peut être évité en s'assurant qu'un seul processus (choisi au hasard ou par priorité) prend des mesures.

mah
la source
8
Je l'ai déjà trouvé, mais ils n'ont pas d'exemples comme vous pouvez le voir, merci quand même
macindows
61
Je ne fournirai pas d'exemple de code, mais considérons deux processus en attente chacun d'une ressource que l'autre a mais en attente de manière non bloquante. Lorsque chacun apprend qu'il ne peut pas continuer, il libère sa ressource suspendue et s'endort pendant 30 secondes, puis récupère sa ressource d'origine, puis essaie la ressource que l'autre processus a détenue, puis a quitté, puis a été ré-acquise. Étant donné que les deux processus essaient de faire face (juste mal), c'est un vivelock.
mah
4
pouvez-vous me donner le même exemple mais avec une impasse, merci d'avance
macindows
32
Un exemple de blocage est beaucoup plus facile ... supposons deux processus A et B, et chacun veut la ressource r1 et la ressource r2. Supposons que A reçoit (ou a déjà) r1, et B reçoit (ou a déjà) r2. Maintenant, chacun essaie d'obtenir la ressource dont dispose l'autre, sans aucun délai. A est bloqué parce que B détient r2, et B est bloqué parce que A détient r1. Chaque processus est bloqué et ne peut donc pas libérer la ressource que l'autre veut, ce qui provoque un blocage.
mah
2
Dans le contexte de la mémoire transactionnelle, il y a une excellente vidéo montrant l'impasse et le livelock: youtube.com/watch?v=_IxsOEEzf-c
BlackVegetable
78

Livelock

Un thread agit souvent en réponse à l'action d'un autre thread. Si l'action de l'autre thread est également une réponse à l'action d'un autre thread, alors Livelock peut en résulter.

Comme pour l'impasse, les threads verrouillés ne sont pas en mesure de progresser davantage . Cependant, les threads ne sont pas bloqués - ils sont simplement trop occupés à se répondre pour reprendre le travail . C'est comparable à deux personnes tentant de se croiser dans un couloir: Alphonse se déplace à sa gauche pour laisser passer Gaston, tandis que Gaston se déplace à sa droite pour laisser passer Alphonse. Voyant qu'ils se bloquent toujours, Alphonse se déplace vers sa droite, tandis que Gaston se déplace vers sa gauche. Ils se bloquent toujours, et ainsi de suite ...

La principale différence entre livelock et deadlock est que les threads ne seront pas bloqués, ils essaieront plutôt de se répondre en continu.

Dans cette image, les deux cercles (fils ou processus) essaieront de donner de l'espace à l'autre en se déplaçant à gauche et à droite. Mais ils ne peuvent plus avancer.

entrez la description de l'image ici

Buru
la source
Exemples de code pour livelocks stackoverflow.com/questions/1036364/good-example-of-livelock
Yauhen Yakimovich
1
Cette chose a un nom. Un mot d'argot peut-être, mais quand même: schlumperdink : P
John Red
64

Tout le contenu et les exemples ici proviennent de

Systèmes d'exploitation: internes et principes de conception
William Stallings
8º Edition

Blocage : situation dans laquelle deux processus ou plus sont incapables de se poursuivre car chacun attend que les autres fassent quelque chose.

Par exemple, considérons deux processus, P1 et P2, et deux ressources, R1 et R2. Supposons que chaque processus ait besoin d'accéder aux deux ressources pour exécuter une partie de sa fonction. Il est alors possible d'avoir la situation suivante: le système d'exploitation affecte R1 à P2 et R2 à P1. Chaque processus attend l'une des deux ressources. Aucun ne libérera la ressource qu'il possède déjà tant qu'il n'aura pas acquis l'autre ressource et exécuté la fonction nécessitant les deux ressources. Les deux processus sont bloqués

Livelock : Une situation dans laquelle deux processus ou plus changent continuellement leurs états en réponse aux changements des autres processus sans effectuer aucun travail utile:

Famine : situation dans laquelle un processus exécutable est ignoré indéfiniment par le planificateur; bien qu'il puisse procéder, il n'est jamais choisi.

Supposons que trois processus (P1, P2, P3) nécessitent chacun un accès périodique à la ressource R. Considérez la situation dans laquelle P1 est en possession de la ressource, et P2 et P3 sont retardés, en attendant cette ressource. Lorsque P1 quitte sa section critique, P2 ou P3 doivent être autorisés à accéder à R. Supposons que le système d'exploitation accorde l'accès à P3 et que P1 nécessite à nouveau un accès avant que P3 ne termine sa section critique. Si le système d'exploitation accorde l'accès à P1 après la fin de P3, puis accorde alternativement l'accès à P1 et P3, P2 peut se voir refuser indéfiniment l'accès à la ressource, même s'il n'y a pas de situation de blocage.

ANNEXE A - SUJETS CONCURRENTS

Exemple de blocage

Si les deux processus définissent leurs indicateurs sur true avant que l'un n'ait exécuté l'instruction while, alors chacun pensera que l'autre est entré dans sa section critique, provoquant un blocage.

/* PROCESS 0 */
flag[0] = true;            // <- get lock 0
while (flag[1])            // <- is lock 1 free?
    /* do nothing */;      // <- no? so I wait 1 second, for example
                           // and test again.
                           // on more sophisticated setups we can ask
                           // to be woken when lock 1 is freed
/* critical section*/;     // <- do what we need (this will never happen)
flag[0] = false;           // <- releasing our lock

 /* PROCESS 1 */
flag[1] = true;
while (flag[0])
    /* do nothing */;
/* critical section*/;
flag[1] = false;

Exemple Livelock

/* PROCESS 0 */
flag[0] = true;          // <- get lock 0
while (flag[1]){         
    flag[0] = false;     // <- instead of sleeping, we do useless work
                         //    needed by the lock mechanism
    /*delay */;          // <- wait for a second
    flag[0] = true;      // <- and restart useless work again.
}
/*critical section*/;    // <- do what we need (this will never happen)
flag[0] = false; 

/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
    flag[1] = false;
    /*delay */;
    flag[1] = true;
}
/* critical section*/;
flag[1] = false;

[...] considérer la séquence d'événements suivante:

  • P0 définit le drapeau [0] sur true.
  • P1 définit le drapeau [1] sur true.
  • P0 vérifie l'indicateur [1].
  • P1 vérifie l'indicateur [0].
  • P0 définit le drapeau [0] sur faux.
  • P1 définit le drapeau [1] sur faux.
  • P0 définit le drapeau [0] sur true.
  • P1 définit le drapeau [1] sur true.

Cette séquence pourrait être prolongée indéfiniment et aucun des deux processus ne pourrait entrer dans sa section critique. À proprement parler, ce n'est pas une impasse , car toute modification de la vitesse relative des deux processus rompra ce cycle et permettra à l'un d'entrer dans la section critique. Cette condition est appelée livelock . Rappelez-vous qu'un blocage se produit lorsqu'un ensemble de processus souhaite entrer dans leurs sections critiques mais qu'aucun processus ne peut réussir. Avec livelock , il existe des séquences possibles d'exécutions qui réussissent, mais il est également possible de décrire une ou plusieurs séquences d'exécution dans lesquelles aucun processus n'entre jamais dans sa section critique.

Plus de contenu du livre.

Et les verrous tournants?

Spinlock est une technique pour éviter le coût du mécanisme de verrouillage du système d'exploitation. En règle générale, vous feriez:

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

Un problème commence à apparaître quand beginLock()coûte beaucoup plus cher doSomething(). En termes très exagérés, imaginez ce qui se passe lorsque le beginLockcoût 1 seconde, mais ne doSomethingcoûte que 1 milliseconde.

Dans ce cas, si vous attendez 1 milliseconde, vous éviterez d'être gêné pendant 1 seconde.

Pourquoi beginLockcela coûterait-il si cher? Si le verrou est gratuit, cela ne coûte pas cher (voir https://stackoverflow.com/a/49712993/5397116 ), mais si le verrou n'est pas gratuit, le système d'exploitation "gèlera" votre thread, configurez un mécanisme pour vous réveiller lorsque le verrou est libéré, puis vous réveiller à nouveau à l'avenir.

Tout cela est beaucoup plus cher que certaines boucles vérifiant la serrure. C'est pourquoi il vaut parfois mieux faire un "spinlock".

Par exemple:

void beginSpinLock(lock)
{
   if(lock) loopFor(1 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   if(lock) loopFor(2 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   // important is that the part above never 
   // cause the thread to sleep.
   // It is "burning" the time slice of this thread.
   // Hopefully for good.

   // some implementations fallback to OS lock mechanism
   // after a few tries
   if(lock) return beginLock(lock);
   else 
   {
     lock = true;
     return;
   }
}

Si votre implémentation ne fait pas attention, vous pouvez tomber sur livelock, dépensant tout le CPU sur le mécanisme de verrouillage.

Regarde aussi:

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Mon implémentation de verrouillage de rotation est-elle correcte et optimale?

Résumé :

Impasse : situation où personne ne progresse, ne fait rien (dormir, attendre etc.). L'utilisation du processeur sera faible;

Livelock : situation où personne ne progresse, mais le CPU est dépensé sur le mécanisme de verrouillage et non sur votre calcul;

Famine: situation où un procureur n'a jamais la chance de courir; par pure malchance ou par une partie de ses biens (faible priorité, par exemple);

Spinlock : technique pour éviter le coût en attendant que le verrou soit libéré.

Daniel Frederico Lins Leite
la source
Monsieur, l'exemple que vous avez donné pour Deadlock est en fait un exemple de Spinlock. Un blocage se produit lorsqu'un ensemble de processus sont bloqués qui ne sont pas prêts ou en cours d'exécution et en attente de certaines ressources. Mais dans notre exemple, chacun effectue une tâche, c'est-à-dire qu'il vérifie la condition encore et encore. Corrigez-moi si je me trompe.
Vinay Yadav
L'exemple est si minime qu'il laisse une chance à cette interprétation, alors je l'ai amélioré pour être un peu plus explicite sur leur différence. J'espère que cela pourra aider.
Daniel Frederico Lins Leite
Merci d'avoir ajouté sur les verrous tournants, selon vous les verrous tournants sont une technique et vous la justifiez aussi et j'ai compris. Mais qu'en est-il de ce problème d'inversion de priorité lorsqu'un processus P1 est dans la section critique et qu'un autre processus de haute priorité P2 est planifié en préemptant P1, alors dans ce cas, le processeur est avec P2 et notre mécanisme de synchronisation est avec P1. Cela s'appelle Spinlock car P1 est à l' état prêt et P2 est à l' état d' exécution . Ici, le verrou tournant est un problème. Suis-je en train de bien faire les choses? Je ne suis pas en mesure de comprendre les subtilités. S'il vous plaît aider
Vinay Yadav
Ma suggestion est de créer une autre question en exposant plus clairement votre problème. Maintenant, si vous êtes dans "l'espace utilisateur", et P1 est à l'intérieur d'une session critique protégée avec un SpinLock implémenté avec une boucle infinie et son préempté; alors P2 essaiera d'y entrer, échouera et brûlera toute sa tranche de temps. Vous avez créé un livelock (un processeur sera à 100%). (une mauvaise utilisation serait de protéger un IO de synchronisation avec spinlock. Vous pouvez facilement essayer cet exemple) Sur "l'espace du noyau", cette note peut peut-être vous aider: lxr.linux.no/linux+v3.6.6/Documentation/…
Daniel Frederico Lins Leite
Merci beaucoup pour la clarification. Quoi qu'il en soit, votre réponse était assez descriptive et utile contrairement aux autres
Vinay Yadav
13

DEADLOCK Deadlock est une condition dans laquelle une tâche attend indéfiniment des conditions qui ne peuvent jamais être satisfaites - la tâche revendique un contrôle exclusif sur les ressources partagées - la tâche détient les ressources en attendant que d'autres ressources soient libérées - les tâches ne peuvent pas être forcées d'éteindre les ressources - une attente circulaire la condition existe

LIVELOCK Les conditions Livelock peuvent survenir lorsque deux tâches ou plus dépendent et utilisent certaines ressources, provoquant une condition de dépendance circulaire où ces tâches continuent de s'exécuter indéfiniment, bloquant ainsi l'exécution de toutes les tâches de niveau de priorité inférieur (ces tâches de priorité inférieure subissent une condition appelée famine)

Deepak Lamichhane
la source
Si les tâches `` verrouillées '' suivent des protocoles d'arbitrage de ressources qui incluent des retards de `` coupure '' et passent la plupart de leur temps en état de sommeil, alors d'autres tâches ne seront pas affamées.
greggo
8

Peut-être que ces deux exemples vous illustrent la différence entre une impasse et un livelock:


Exemple Java pour un blocage:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
        Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
        lock1.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 1");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
            lock2.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } finally {
            lock1.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
        }
    }

    public static void doB() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
        lock2.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 2");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
            lock1.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } finally {
            lock2.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
        }
    }
}

Exemple de sortie:

Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2

Exemple Java pour un livelock:


import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LivelockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(LivelockSample::doA, "Thread A");
        Thread threadB = new Thread(LivelockSample::doB, "Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        try {
            while (!lock1.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                while (!lock2.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 2");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
                } finally {
                    lock2.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
                }
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }

    public static void doB() {
        try {
            while (!lock2.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                while (!lock1.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 1");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
                } finally {
                    lock1.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
                }
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }
}

Exemple de sortie:

Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...

Les deux exemples forcent les threads à acquérir les verrous dans des ordres différents. Pendant que l'impasse attend l'autre verrou, le livelock n'attend pas vraiment - il essaie désespérément d'acquérir le verrou sans avoir la chance de l'obtenir. Chaque essai consomme des cycles CPU.

mmirwaldt
la source
Le code est sympa. Mais l'exemple de verrouillage en direct n'est pas bon. Qu'un thread soit bloqué sur une valeur ou qu'il recherche une modification de valeur n'est pas conceptuellement différent. Un changement facile pour mieux illustrer un verrouillage en direct consiste à demander aux threads A et B de libérer les verrous dont ils disposent lorsqu'ils se rendent compte qu'ils ne peuvent pas obtenir le deuxième verrou dont ils ont besoin. Ensuite, ils dorment pendant une seconde chacun, acquièrent à nouveau le verrou qu'ils avaient à l'origine, puis dorment pendant une autre seconde et tentent d'acquérir à nouveau l'autre verrou. Ainsi, le cycle pour chacun serait: 1) acquérir le mien, 2) dormir, 3) essayer d'acquérir un autre et échouer, 4) libérer le mien, 5) dormir, 6) répéter.
CognizantApe
1
Je doute que les verrous vivants auxquels vous pensez existent vraiment depuis assez longtemps pour qu'ils causent des problèmes. Lorsque vous abandonnez toujours tous les verrous que vous détenez lorsque vous ne pouvez pas attribuer le verrou suivant, la condition de blocage (et de verrouillage en direct) "Hold and Wait" est manquante car il n'y a plus d'attente. ( en.wikipedia.org/wiki/Deadlock )
mmirwaldt
en effet, la condition de verrouillage mort est manquante car ce sont des verrous actifs dont nous discutons. L'exemple que j'ai donné est similaire à l'exemple de couloir standard donné: geeksforgeeks.org/deadlock-starvation-and-livelock , en.wikibooks.org/wiki/Operating_System_Design/Concurrency/… , docs.oracle.com/javase/tutorial/essential / simultané /…
CognizantApe
0

Imaginez que vous avez le thread A et le thread B. Ils sont tous synchronisedles deux sur le même objet et à l'intérieur de ce bloc, il y a une variable globale qu'ils mettent à jour tous les deux;

static boolean commonVar = false;
Object lock = new Object;

...

void threadAMethod(){
    ...
    while(commonVar == false){
         synchornized(lock){
              ...
              commonVar = true
         }
    }
}

void threadBMethod(){
    ...
    while(commonVar == true){
         synchornized(lock){
              ...
              commonVar = false
         }
    }
}

Ainsi, lorsque le fil A entre dans la whileboucle et maintient le verrou, il fait ce qu'il doit faire et mettre l' commonVarà true. Puis enfilez B arrive, entre dans la whileboucle et depuis commonVarest truemaintenant, il est en mesure de tenir le verrou. Il le fait, exécute le synchronisedbloc et commonVarrevient à false. Maintenant, le thread A obtient à nouveau sa nouvelle fenêtre CPU, il était sur le point de quitter la whileboucle mais le thread B vient de le remettre àfalse , donc le cycle se répète à nouveau. Les threads font quelque chose (donc ils ne sont pas bloqués au sens traditionnel) mais pour à peu près rien.

Il est peut-être également agréable de mentionner que Livelock ne doit pas nécessairement apparaître ici. Je suppose que le planificateur favorise l'autre thread une fois l' synchronisedexécution du bloc terminée. La plupart du temps, je pense que c'est une attente difficile à atteindre et dépend de beaucoup de choses qui se passent sous le capot.

stdout
la source
Bel exemple. Il illustre également pourquoi vous devez toujours lire et écrire de manière atomique dans un contexte simultané. Si les boucles while étaient à l'intérieur des blocs de synchronisation, alors ce qui précède ne serait pas un problème.
CognizantApe