Kann mir bitte jemand anhand von Beispielen (Code) erklären, was der Unterschied ist zwischen Deadlock y Livelock ?
Antworten
Zu viele Anzeigen?
Entnommen aus http://en.wikipedia.org/wiki/Deadlock :
Bei der gleichzeitigen Datenverarbeitung ist eine Deadlock ist ein Zustand, in dem jedes Mitglied einer Gruppe von Aktionen darauf wartet, dass ein anderes Mitglied eine Sperre freigibt
A Livelock ist vergleichbar mit einer Sackgasse, mit der Ausnahme, dass die Zustände der Prozesse, die an dem Livelock beteiligt sind beteiligten Prozesse ständig im Verhältnis zueinander ändern einander, ohne dass ein Fortschritt erzielt wird. Livelock ist ein Sonderfall der Ressourcenverknappung; die allgemeine Definition besagt nur dass ein bestimmter Prozess nicht fortschreitet.
Ein Beispiel aus der Praxis für Livelock tritt auf, wenn sich zwei Personen in einem engen Korridor treffen und jeder versucht höflich zu sein, indem sie zur Seite gehen, um den anderen vorbeizulassen, aber sie enden damit von einer Seite zur anderen schwanken, ohne ohne voranzukommen, weil sie beide immer wieder in die gleiche Richtung bewegen zur gleichen Zeit.
Livelock ist ein Risiko mit einigen Algorithmen, die Deadlocks erkennen und Deadlock wiederherstellen. Wenn mehr als ein Prozess aktiv wird, kann der Erkennungsalgorithmus wiederholt ausgelöst werden. Dies kann vermieden werden, indem sichergestellt wird, dass nur ein Prozess (ausgewählt nach dem Zufallsprinzip oder nach Priorität ausgewählt wird) tätig wird.
Bruce
Punkte
8311
Ein Thread agiert oft als Reaktion auf die Aktion eines anderen Threads. Wenn die Aktion des anderen Threads auch eine Reaktion auf die Aktion eines anderen Threads ist, kann es zu einem Livelock kommen.
Wie bei Deadlocks werden auch bei Livelocked Threads nicht in der Lage, weitere Fortschritte zu machen . Allerdings ist die Fäden werden nicht blockiert - sie sind einfach zu sehr damit beschäftigt, sich gegenseitig zu antworten, um die Arbeit wieder aufzunehmen . Dies ist vergleichbar mit zwei Personen, die versuchen, sich in einem Korridor zu überholen: Alphonse geht nach links, um Gaston passieren zu lassen, und Gaston geht nach rechts, um Alphonse passieren zu lassen. Als Alphonse sieht, dass sie sich immer noch gegenseitig blockieren, geht er nach rechts, während Gaston nach links geht. Sie blockieren sich immer noch gegenseitig, und so weiter...
Der Hauptunterschied zwischen Livelock y Deadlock ist, dass Threads nicht blockiert werden, sondern dass sie versuchen werden, kontinuierlich aufeinander zu antworten.
In diesem Bild versuchen beide Kreise (Threads oder Prozesse), dem jeweils anderen Platz zu machen, indem sie sich nach links und rechts bewegen. Aber sie können sich nicht weiter bewegen.
Daniel Frederico Lins Leite
Punkte
1254
Der gesamte Inhalt und alle Beispiele stammen von
Betriebssysteme: Interna und Designprinzipien
William Stallings
8º Ausgabe
Deadlock : Eine Situation, in der zwei oder mehr Prozesse nicht fortfahren können, weil sie auf die Ausführung eines der anderen Prozesse warten.
Nehmen wir zum Beispiel zwei Prozesse, P1 und P2, und zwei Ressourcen, R1 und R2. Nehmen wir an, dass jeder Prozess Zugang zu beiden Ressourcen benötigt, um einen Teil seiner Funktion auszuführen. Dann kann die folgende Situation eintreten: Das Betriebssystem weist R1 P2 und R2 P1 zu. Jeder Prozess wartet auf eine der beiden Ressourcen. Keiner der beiden Prozesse wird die Ressource, die er bereits besitzt, freigeben, bis er die andere Ressource erworben hat die andere Ressource erworben und die Funktion ausgeführt hat, die beide Ressourcen benötigt. Die beiden Prozesse sind in einer Sackgasse
Livelock : Eine Situation, in der zwei oder mehr Prozesse kontinuierlich ihren Zustand als Reaktion auf Veränderungen in dem/den anderen Prozess(en) ändern, ohne dass sie eine nützliche Arbeit leisten:
Verhungern : Eine Situation, in der ein lauffähiger Prozess vom Scheduler auf unbestimmte Zeit übersehen wird; obwohl er in der Lage ist, fortzufahren, wird er nie ausgewählt.
Nehmen wir an, dass drei Prozesse (P1, P2, P3) jeweils periodischen Zugriff auf die Ressource R benötigen. Betrachten wir die Situation, in der P1 im Besitz der Ressource ist und sowohl P2 als auch P3 verzögert auf diese Ressource warten. Wenn P1 seinen kritischen Abschnitt verlässt, sollte entweder P2 oder P3 Zugang zu R erhalten. Angenommen, das Betriebssystem gewährt P3 Zugang und P1 benötigt erneut Zugang, bevor P3 seinen kritischen Abschnitt abschließt. Wenn das Betriebssystem P1 den Zugriff gewährt, nachdem P3 seinen kritischen Abschnitt beendet hat, und anschließend abwechselnd P1 und P3 den Zugriff gewährt, kann P2 der Zugriff auf die Ressource auf unbestimmte Zeit verweigert werden, obwohl keine Deadlock-Situation vorliegt.
ANHANG A - THEMEN DER GLEICHZEITIGKEIT
Deadlock-Beispiel
Wenn beide Prozesse ihre Flags auf true setzen, bevor einer von ihnen die while-Anweisung ausgeführt hat, wird jeder denken, dass der andere in seinen kritischen Abschnitt eingetreten ist, was zu einem Deadlock führt.
/* 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;Livelock Beispiel
/* 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;[...] betrachten Sie die folgende Abfolge von Ereignissen:
- P0 setzt flag[0] auf true.
- P1 setzt flag[1] auf true.
- P0 prüft Flagge[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 Sequenz ließe sich beliebig verlängern, und keiner der Prozesse könnte in den kritischen Bereich eintreten. Streng genommen ist dies keine Blockierung Denn jede Änderung der relativen Geschwindigkeit der beiden Prozesse unterbricht diesen Zyklus und ermöglicht den Eintritt in den kritischen Bereich. Dieser Zustand wird bezeichnet als Livelock . Erinnern Sie sich daran, dass eine Blockade auftritt, wenn eine Reihe von Prozessen in ihre kritischen Abschnitte eintreten will, aber kein Prozess erfolgreich sein kann. Mit Livelock Es ist aber auch möglich, eine oder mehrere Ausführungssequenzen zu beschreiben, in denen kein Prozess jemals in seinen kritischen Abschnitt eintritt.
Keine Inhalte mehr aus dem Buch.
Und was ist mit Spinlocks?
Spinlock ist eine Technik, mit der die Kosten für den Sperrmechanismus des Betriebssystems vermieden werden. Normalerweise würden Sie das tun:
try
{
lock = beginLock();
doSomething();
}
finally
{
endLock();
}Ein Problem beginnt zu entstehen, wenn beginLock() kostet viel mehr als doSomething() . Überspitzt formuliert: Stellen Sie sich vor, was passiert, wenn die beginLock kostet 1 Sekunde, aber doSomething kosten nur 1 Millisekunde.
Wenn Sie in diesem Fall 1 Millisekunde gewartet hätten, wären Sie 1 Sekunde lang nicht behindert worden.
Warum die beginLock so viel kosten würde? Wenn das Schloss kostenlos ist, kostet es nicht viel (siehe https://stackoverflow.com/a/49712993/5397116 ), aber wenn die Sperre nicht frei ist, wird das Betriebssystem Ihren Thread "einfrieren", einen Mechanismus einrichten, um Sie aufzuwecken, wenn die Sperre freigegeben ist, und Sie dann in Zukunft wieder aufwecken.
All dies ist viel teurer als einige Schleifen zur Überprüfung des Schlosses. Deshalb ist es manchmal besser, ein "Spinlock" zu verwenden.
Zum Beispiel:
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;
}
}Wenn Ihre Implementierung nicht vorsichtig ist, können Sie auf Livelock fallen und die gesamte CPU für den Sperrmechanismus verwenden.
Siehe auch:
https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Ist meine Spinlock-Implementierung korrekt und optimal?
Zusammenfassung :
Deadlock Situation, in der niemand vorankommt und nichts tut (schlafen, warten usw.). Die CPU-Belastung wird niedrig sein;
Livelock Situation, in der niemand vorankommt, aber die CPU auf den Sperrmechanismus und nicht auf Ihre Berechnung verwendet wird;
Starvation: Situation, in der ein Prozess nie die Chance bekommt, zu laufen; durch reines Pech oder durch eine seiner Eigenschaften (niedrige Priorität, zum Beispiel);
Spinlock Technik zur Vermeidung der Kosten, die durch das Warten auf die Freigabe der Sperre entstehen.
Deepak Lamichhane
Punkte
14258
DEADLOCK Deadlock ist ein Zustand, in dem eine Aufgabe wartet unendlich lange auf Bedingungen wartet, die nie erfüllt werden können . - Aufgabe beansprucht exklusive Kontrolle über geteilte Ressourcen - Aufgabe hält Ressourcen, während sie auf die Freigabe anderer Ressourcen freigegeben werden sollen - Aufgaben können nicht gezwungen werden, Ressourcen wieder freizugeben - eine zirkuläre Wartebedingung besteht
LIVELOCK Livelock-Bedingungen können entstehen, wenn zwei oder mehrere Aufgaben von der gleichen Ressource abhängen und diese Ressource abhängen und eine zirkuläre Abhängigkeit verursachen verursacht, bei der diese Aufgaben laufen, wodurch alle Aufgaben mit niedrigerer Aufgaben mit niedrigerer Priorität blockieren (diese Aufgaben mit niedrigerer Priorität erfahren eine Bedingung Hungersnot genannt)
mmirwaldt
Punkte
801
Vielleicht veranschaulichen Ihnen diese beiden Beispiele den Unterschied zwischen einem Deadlock und einem Livelock:
Java-Beispiel für einen 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");
}
}
}Beispielhafte 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 2Java-Beispiel für ein 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
}
}
}Beispielhafte 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 zwingen die Threads, die Sperren in unterschiedlicher Reihenfolge zu erwerben. Während die Deadlock auf die andere Sperre wartet, wartet die lebende Sperre nicht wirklich - sie versucht verzweifelt, die Sperre zu erlangen, ohne die Chance, sie zu bekommen. Jeder Versuch verbraucht CPU-Zyklen.
- See previous answers
- Weitere Antworten anzeigen
