Quelle est la différence entre deadlock et livelock?

Absence de cycle non productif

Un thread agit souvent en réponse à l'action d'un autre thread. Si l'autre fil de l'action est aussi une réponse à l'action de l'autre thread, puis livelock peut en résulter.

Comme avec deadlock, les threads animés sont incapables de progresser . Cependant, les threads ne sont pas bloqués - ils sont simplement trop occupés à répondre les uns aux autres pour reprendre le travail . Ceci est comparable à deux personnes qui tentent de passer L'un l'autre 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 encore, Alphonse se déplace à sa droite, tandis que Gaston se déplace à sa gauche. Ils se bloquent encore, et ainsi de suite...

La principale différence entre livelock et impasse est - ce que les threads ne vont pas être bloqués, au lieu de cela, ils vont essayer de répondre les uns aux autres continuellement.

Dans cette image, les deux cercles (threads ou processus) vont essayer de donner de l'espace à l'autre en se déplaçant à gauche et à droite. Mais ils ne peuvent pas aller plus loin.

Tout le contenu et les exemples ici proviennent de

Systèmes D'exploitation: internes et principes de conception
William Stallings
8ème Édition

Deadlock : une situation dans laquelle deux processus ou plus sont incapables de procéder parce que chacun attend que l'un 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. Ensuite, il est possible d'avoir la situation suivante: le système d'exploitation attribue R1 à P2, et R2 à P1. Chaque processus attend l'une des deux ressources. Ni ne libérera la ressource qu'il possède déjà jusqu'à ce qu'il ait acquis l'autre ressource et a effectué la fonction nécessitant les deux ressources. Les deux les processus sont bloqués

Livelock : une situation dans laquelle deux processus ou plus changent continuellement leurs états en réponse à des changements dans l'autre processus(s) sans faire tout travail utile:

La Famine: une situation dans laquelle Un processus exécutable est négligé indéfiniment par le planificateur, bien qu'il soit en mesure de 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 devrait être autorisé à accéder à R. Supposons que le système d'exploitation accorde l'accès à P3 et que P1 nécessite à nouveau l'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, et accorde ensuite 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 DANS LA CONCURRENCE

Exemple De Blocage

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

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

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

Absence De Cycle Non Productif Exemple

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

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

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

• P0 définit flag[0] sur true.
• P1 définit flag[1] sur true.
• P0 vérifie l'indicateur[1].
• P1 vérifie l'indicateur[0].
• P0 définit flag[0] sur false.
• P1 définit flag[1] sur false.
• P0 définit l'indicateur[0] sur vrai.
• P1 définit flag[1] sur true.

Cette séquence pourrait être prolongée indéfiniment, et aucun processus ne pourrait entrer dans sa section critique. Strictement parlant, ce n'est pas une impasse , car toute modification de la vitesse relative des deux processus va rompre ce cycle et permettre à l'un d'entrer dans la section critique. Cette condition est appelée livelock . Rappelons que l'impasse se produit lorsqu'un ensemble de processus souhaite entrer dans leurs sections critiques mais non le processus peut réussir. Avec livelock , Il existe des séquences d'exécutions possibles 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.

Blocage L'impasse est une condition dans laquelle une tâche attend indéfiniment pour des conditions qui ne peuvent jamais être satisfaire - tâche revendique le contrôle exclusif sur partagé ressources - tâche détient des ressources en attendant d'autres ressources pour être publié - les tâches ne peuvent pas être obligées de relinguer des ressources - une condition d'attente circulaire existe

Absence de cycle non productif Les conditions de Livelock peuvent survenir lorsque deux ou plus de tâches dépendent et utilisent certains ressource provoquant une circulaire dépendance condition dans laquelle ces tâches se poursuivent en cours d'exécution pour toujours, bloquant ainsi tous les plus bas tâches de niveau de priorité de l'exécution (ces les tâches de priorité inférieure éprouvent une condition appelé famine)

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

Java-exemple de 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

Java-exemple 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 la serrure sans la chance de l'obtenir. Chaque essai consomme des cycles CPU.

Avec référence: http://operatingsystemgeeks.blogspot.in/ Exemple de blocage : Une condition d'exclusion mutuelle s'applique, car un seul véhicule peut être sur une section de la rue à la fois. La condition de maintien et d'attente s'applique, puisque chaque véhicule occupe une section de la rue et attend de passer à la section suivante de la rue. Aucune condition préventive ne s'applique, car une section de la rue qui est une section de la rue occupée par un véhicule ne peut être enlevée à partir d'elle. La condition d'attente circulaire s'applique, puisque chaque véhicule attend le prochain véhicule pour se déplacer. Autrement dit, chaque véhicule dans la circulation attend une section de rue tenue par le véhicule suivant dans la circulation.