Was ist der Unterschied zwischen Deadlock und Livelock?

Entnommen http://en.wikipedia.org/wiki/Deadlock:

In concurrent computing, ein deadlock ist ein Zustand, in dem jedes Mitglied einer Gruppe von Aktionen, ist warten, für einen anderen Mitglied eine Sperre freizugeben

Einen livelock ist ähnlich zu einem deadlock,
außer, dass die Staaten der
Prozesse, die bei der livelock
ständig ändern sich mit Bezug auf eine
ein anderer, keine Fortschritte. Livelock ist
ein besonderer Fall von Ressourcen-Hunger;
die Allgemeine definition besagt lediglich
dass ein bestimmter Prozess nicht
voran.

Ein real-world Beispiel von
livelock tritt auf, wenn sich zwei Menschen treffen
in einem schmalen Korridor, und jeder versucht
höflich zu sein, durch verschieben beiseite zu lassen
den anderen pass, aber Sie am Ende
schwankend von Seite zu Seite, ohne
macht keine Fortschritte, weil Sie beide
immer wieder bewegen die gleiche Weise an der
gleichen Zeit.

Livelock ist ein Risiko mit
einige algorithmen, die erkennen und
wiederherstellen von deadlock. Wenn mehr als
ein Prozess greift, der deadlock
Erkennung Algorithmus kann wiederholt werden
ausgelöst. Dies kann vermieden werden, indem
sicherstellen, dass nur ein Prozess (gewählt
nach dem Zufallsprinzip oder nach Priorität) tritt in Aktion.

InformationsquelleAutor der Antwort mah

Alle den Inhalt und die Beispiele hier sind aus

Operating Systems: Internals and Design Principles

William Aufschübe

8º Edition

Deadlock: Eine situation, in der zwei oder mehr Prozesse nicht fortfahren, weil jeder wartet, dass einer den anderen etwas zu tun.

Beispiel: betrachten wir zwei Prozesse P1 und P2 und zwei Ressourcen R1 und R2. Angenommen, dass jeder Prozess braucht Zugang zu beiden Ressourcen zur Durchführung von Teil seine Funktion. Dann ist es möglich, sich folgende situation vor: das OS weist R1, P2, R2 P1. Jeder Prozess wartet für eine der beiden Ressourcen. Weder wird die Ressource freigeben, die es bereits besitzt, bis es erworben hat
die andere Ressource und führte die Funktion, die sowohl Ressourcen. Die beiden
Prozesse festgefahren sind

Livelock: Eine situation, in der zwei oder mehr Prozesse, die ständig Ihren Status ändern in Reaktion auf änderungen in den anderen Prozess(en) ohne sinnvolle Arbeit:

Hunger: Eine situation, in der ein ausführbarer Prozess wird übersehen, auf unbestimmte Zeit durch den scheduler; es ist zwar in der Lage zu gehen, es ist nie gewählt.

Angenommen, dass die drei Prozesse (P1, P2, P3), jede erfordert eine regelmäßige Zugriff auf die Ressource R. Betrachten Sie die situation, in der P1 ist im Besitz der Ressource ist, und sowohl P2 und P3 sind verzögert, wartet auf die Ressource. Wenn P1 beendet seinen kritischen Abschnitt, entweder P2 oder P3 sollte gestattet werden, Zugang zu R. davon Ausgehen, dass das OS Zugriff auf P3 und P1 wieder zugreifen muss, bevor P3 schließt seine kritischen Abschnitt. Wenn das OS den Zugang zu P1 nach P3 beendet hat, und anschließend abwechselnd Zugriff gewährt, P1 und P3, dann P2 können auf unbestimmte Zeit keinen Zugriff auf die Ressource, auch wenn es keine deadlock-situation.

ANHANG A - THEMEN IN PARALLELITÄT

Beispiel Deadlock

Wenn beide Prozesse Ihre flags auf true, bevor Sie entweder ausgeführt hat, die der while-Anweisung, dann wird jeder denken, dass der andere eingegeben hat, seinen kritischen Abschnitt, wodurch deadlock.

/* 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;

Livelock Beispiel

/* 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;

[...] betrachten Sie die folgende Sequenz von Ereignissen:

• P0 setzt flag[0] auf true.
• P1 setzt flag[1] auf true.
• P0 überprüft flag[1].
• P1 prüft flag[0].
• P0 setzt flag[0] auf false.
• P1 setzt flag[1] auf false.
• P0 setzt flag[0] auf true.
• P1 setzt flag[1] auf true.

Diese Reihenfolge könnte endlos erweitert werden, und weder der Prozess konnte Sie, seinen kritischen Abschnitt. Streng genommen ist das nicht deadlock, weil jede änderung in der relativen Geschwindigkeit der beiden Prozesse brechen dieses Zyklus und erlauben es, geben Sie den kritischen Abschnitt. Diese Bedingung wird als bezeichnet livelock. Daran erinnern, dass deadlock tritt auf, wenn eine Reihe von Prozessen, die Wünsche zu geben, mit Ihren kritischen Abschnitten, aber kein Prozess gelingen kann. Mit livelock, ist es möglich, Sequenzen von Hinrichtungen, die erfolgreich sind, aber es ist auch möglich, beschreiben Sie eine oder mehrere der Ausführung von Sequenzen, in denen kein Prozess, der jemals in seinen kritischen Abschnitt.

InformationsquelleAutor der Antwort Daniel Frederico Lins Leite

Vielleicht diese zwei Beispiele veranschaulichen Ihnen den Unterschied zwischen einem deadlock und einem livelock:

Java-Beispiel für ein deadlock:

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");
        }
    }
}

Beispiel-Ausgabe:

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-Beispiel für einen 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
        }
    }
}

Beispiel-Ausgabe:

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

Beide Beispiele Kraft, die threads zu erwerben, die sperren in unterschiedlicher Reihenfolge.
Während der deadlock wartet, bis die andere Sperre,
der livelock nicht wirklich warten - es versucht verzweifelt, die Sperre ohne die chance zu bekommen, es. Jeder Versuch verbraucht CPU-Zyklen.

InformationsquelleAutor der Antwort mmirwaldt