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

Quelqu'un peut-il expliquer avec des exemples (de code) quelle est la différence entre l' impasse et le livelock ?

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.

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.

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é.

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)

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.

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.