Jaka jest różnica między impasem a blokadą aktywności?

Odpowiedzi:

398

Zaczerpnięte z http://en.wikipedia.org/wiki/Deadlock :

W obliczeniach równoległych impas to stan, w którym każdy członek grupy działań czeka na zwolnienie blokady przez innego członka

Livelock jest podobny do impasu, oprócz tego, że stany procesów zaangażowanych w livelock stale zmieniać w odniesieniu do siebie, nikt postępującym. Livelock jest szczególnym przypadkiem głodu zasobów; ogólna definicja mówi tylko, że określony proces nie postępuje.

Prawdziwy przykład blokady na żywo występuje, gdy dwoje ludzi spotyka się w wąskim korytarzu i każda z nich stara się być uprzejma, odsuwając się na bok, aby przepuścić drugiego, ale ostatecznie kołyszą się z boku na bok, nie robiąc żadnego postępu, ponieważ obaj wielokrotnie się poruszają w ten sam sposób w tym samym czasie.

Livelock stanowi ryzyko w przypadku niektórych algorytmów wykrywających i przywracających impas. Jeśli zadziała więcej niż jeden proces, algorytm wykrywania zakleszczenia może być wielokrotnie wyzwalany. Można tego uniknąć, zapewniając działanie tylko jednego procesu (wybranego losowo lub priorytetowo).

mah
źródło
8
Znalazłem to już, ale nie mają tam przykładów, jak widać, i tak dzięki
macindows
61
Nie podam przykładu kodu, ale rozważę dwa procesy, każdy czekający na zasób, który ma inny, ale czeka w sposób nieblokujący. Kiedy każdy się uczy, nie może kontynuować, zwalnia wstrzymany zasób i śpi przez 30 sekund, a następnie odzyskuje swój pierwotny zasób, a następnie próbuje znaleźć zasób, który przechowywał inny proces, a następnie opuścił go, a następnie wznowił. Ponieważ oba procesy próbują sobie poradzić (po prostu źle), jest to blokada aktywna.
mah
4
czy możesz podać mi ten sam przykład, ale z impasem, z góry
dziękuję
32
Przykład impasu jest znacznie łatwiejszy ... załóżmy, że dwa procesy A i B, i każdy chce zasobu r1 i zasobu r2. Załóżmy, że A odbiera (lub już ma) r1, a B odbiera (lub już ma) r2. Teraz każdy próbuje zdobyć zasób, który ma drugi, bez żadnego limitu czasu. A jest zablokowane, ponieważ B zawiera r2, a B jest zablokowane, ponieważ A zawiera r1. Każdy proces jest blokowany i dlatego nie może zwolnić zasobu, którego chce drugi, powodując impas.
mah
2
W kontekście pamięci transakcyjnej znajduje się świetne wideo pokazujące impas i blokadę aktywności: youtube.com/watch?v=_IxsOEEzf-c
BlackVegetable
78

Livelock

Wątek często działa w odpowiedzi na działanie innego wątku. Jeśli działanie drugiego wątku jest również odpowiedzią na działanie innego wątku, może to skutkować blokowaniem aktywnym.

Podobnie jak w przypadku impasu, wątki z blokadą dynamiczną nie są w stanie dokonać dalszego postępu . Jednak wątki nie są zablokowane - są po prostu zbyt zajęty, odpowiadając na siebie, aby wznowić pracę . Jest to porównywalne do dwóch osób próbujących przejść obok siebie na korytarzu: Alphonse przesuwa się w lewo, aby przepuścić Gastona, podczas gdy Gaston przesuwa się w prawo, aby przepuścić Alphonse. Widząc, że nadal się blokują, Alphonse przesuwa się w prawo, a Gaston w lewo. Nadal się blokują i tak dalej ...

Główną różnicą między blokadą aktywności i zakleszczeniem jest to, że wątki nie będą blokowane, zamiast tego będą próbowały reagować na siebie w sposób ciągły.

Na tym obrazie oba kręgi (wątki lub procesy) będą próbowały dać sobie nawzajem miejsce, poruszając się w lewo i prawo. Ale nie mogą już iść dalej.

wprowadź opis zdjęcia tutaj

Buru
źródło
Przykłady kodu dla livelocks stackoverflow.com/questions/1036364/good-example-of-livelock
Yauhen Yakimovich
1
Ta rzecz ma nazwę. Być może slangowe słowo, ale nadal: schlumperdink : P
John Red
64

Cała treść i przykłady są tutaj

Systemy operacyjne: elementy wewnętrzne i zasady projektowania
William Stallings
8º Edition

Zakleszczenie : sytuacja, w której dwa lub więcej procesów nie jest w stanie kontynuować, ponieważ każdy z nich czeka na coś innego.

Rozważmy na przykład dwa procesy P1 i P2 oraz dwa zasoby R1 i R2. Załóżmy, że każdy proces potrzebuje dostępu do obu zasobów, aby wykonać część swojej funkcji. Następnie można mieć następującą sytuację: system operacyjny przypisuje R1 do P2, a R2 do P1. Każdy proces czeka na jeden z dwóch zasobów. Żadne z nich nie zwolni zasobu, który już posiada, dopóki nie zdobędzie drugiego zasobu i nie wykona funkcji wymagającej obu zasobów. Oba procesy są zakleszczone

Livelock : sytuacja, w której dwa lub więcej procesów stale zmienia swoje stany w odpowiedzi na zmiany w innych procesach bez wykonywania żadnej użytecznej pracy:

Głód : sytuacja, w której program uruchamiający jest pomijany w nieskończoność przez program planujący; chociaż jest w stanie kontynuować, nigdy nie jest wybrany.

Załóżmy, że każdy z trzech procesów (P1, P2, P3) wymaga okresowego dostępu do zasobu R. Rozważ sytuację, w której P1 jest w posiadaniu zasobu, a zarówno P2, jak i P3 są opóźnione, czekając na ten zasób. Kiedy P1 opuści sekcję krytyczną, P2 lub P3 powinny mieć dostęp do R. Załóżmy, że system operacyjny zapewnia dostęp do P3 i że P1 ponownie wymaga dostępu, zanim P3 zakończy sekcję krytyczną. Jeśli system operacyjny przyznaje dostęp do P1 po zakończeniu P3, a następnie naprzemiennie udziela dostępu do P1 i P3, wówczas P2 może zostać w nieskończoność pozbawiony dostępu do zasobu, nawet jeśli nie ma sytuacji zakleszczenia.

DODATEK A - TEMATY W KONKURENCJI

Przykład zakleszczenia

Jeśli oba procesy ustawią swoje flagi na true, zanim którekolwiek z nich wykona instrukcję while, wówczas każdy pomyśli, że drugi wszedł do swojej krytycznej sekcji, powodując impas.

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

Przykład 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;

[...] rozważ następującą sekwencję zdarzeń:

  • P0 ustawia flagę [0] na wartość true.
  • P1 ustawia flagę [1] na wartość true.
  • P0 sprawdza flagę [1].
  • P1 sprawdza flagę [0].
  • P0 ustawia flagę [0] na false.
  • P1 ustawia flagę [1] na false.
  • P0 ustawia flagę [0] na wartość true.
  • P1 ustawia flagę [1] na wartość true.

Sekwencję tę można przedłużyć w nieskończoność i żaden proces nie może wejść do swojej krytycznej sekcji. Ściśle mówiąc, nie jest to impas , ponieważ każda zmiana względnej prędkości dwóch procesów przerwie ten cykl i pozwoli wejść do sekcji krytycznej. Ten stan jest określany jako livelock . Przypomnij sobie, że impas występuje, gdy zestaw procesów chce wejść do swoich krytycznych sekcji, ale żaden proces nie może się powieść. Dzięki livelock możliwe są sekwencje wykonania, które się powiodły, ale można również opisać jedną lub więcej sekwencji wykonania, w których żaden proces nigdy nie wchodzi w krytyczną sekcję.

Już nie treści z książki.

A co ze spinlockami?

Spinlock to technika pozwalająca uniknąć kosztów mechanizmu blokady systemu operacyjnego. Zazwyczaj robiłbyś:

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

Problem zaczyna się pojawiać, gdy beginLock()kosztuje znacznie więcej niż doSomething(). W bardzo przesadnych słowach wyobraź sobie, co się dzieje, gdy beginLockkosztuje 1 sekundę, ale doSomethingkosztuje tylko 1 milisekundę.

W takim przypadku, jeśli czekałeś 1 milisekundę, unikniesz przeszkód przez 1 sekundę.

Dlaczego beginLockto kosztuje tak dużo? Jeśli blokada jest bezpłatna, nie kosztuje dużo (patrz https://stackoverflow.com/a/49712993/5397116 ), ale jeśli blokada nie jest wolna, system operacyjny „zamrozi” Twój wątek, skonfiguruj mechanizm, który Cię obudzi kiedy zamek zostanie zwolniony, a następnie obudzę cię ponownie w przyszłości.

Wszystko to jest znacznie droższe niż niektóre pętle sprawdzające zamek. Dlatego czasami lepiej jest zrobić „spinlock”.

Na przykład:

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

Jeśli twoja implementacja nie jest ostrożna, możesz spaść na livelock, wydając cały procesor na mechanizm blokujący.

Zobacz także:

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Czy moja implementacja blokady wirowania jest prawidłowa i optymalna?

Podsumowanie :

Zakleszczenie : sytuacja, w której nikt nie postępuje, nic nie robi (spanie, czekanie itp.). Zużycie procesora będzie niskie;

Livelock : sytuacja, w której nikt nie postępuje, ale procesor jest wydawany na mechanizm blokujący, a nie na twoje obliczenia;

Głód: sytuacja, w której jeden proces nigdy nie ma szans na ucieczkę; przez czysty pech lub przez część jego własności (na przykład niski priorytet);

Spinlock : technika unikania kosztów oczekiwania na uwolnienie blokady.

Daniel Frederico Lins Leite
źródło
Sir, przykład podany dla Deadlocka jest w rzeczywistości przykładem Spinlocka. Zakleszczenie występuje, gdy zestaw procesów jest zablokowany, które nie są w stanie gotowości lub działania i czekają na niektóre zasoby. Ale w naszym przykładzie każdy wykonuje jakieś zadanie, tj. Ciągle sprawdza stan. Popraw mnie, jeśli się mylę.
Vinay Yadav
Przykład jest tak minimalny, że ma otwartą szansę na taką interpretację, więc poprawiłem ją, aby była nieco bardziej wyraźna na temat ich różnicy. Mam nadzieję, że to pomaga.
Daniel Frederico Lins Leite
Dziękuję za dodanie informacji o spinlockach, według ciebie spinlocki to technika, a ty ją uzasadniłeś i zrozumiałem. Ale co z problemem odwrócenia priorytetu, gdy jeden proces P1 znajduje się w sekcji krytycznej, a inny proces P2 o wysokim priorytecie zostaje zaplanowany z wyprzedzeniem P1, to w tym przypadku procesor jest z P2, a nasz mechanizm synchronizacji z P1. Nazywa się to Spinlockiem, ponieważ P1 jest w stanie gotowości, a P2 jest w stanie uruchomienia . Problemem jest spinlock. Czy mam rację? Nie jestem w stanie dobrze zrozumieć zawiłości. Proszę o pomoc
Vinay Yadav
Sugeruję ci, abyś stworzył kolejne pytanie, w którym lepiej wyjaśnisz swój problem. Teraz, jeśli znajdujesz się w „przestrzeni użytkownika”, a P1 znajduje się w sesji krytycznej chronionej za pomocą SpinLocka zaimplementowanego z nieskończoną pętlą i jej wyprzedzeniem; wtedy P2 spróbuje wejść do niego, zawiedzie i spali cały swój odcinek czasu. Utworzyłeś livelock (jeden procesor będzie miał 100%). (złym zastosowaniem byłoby zabezpieczenie synchronizowanego We / Wy za pomocą spinlocka. Możesz łatwo wypróbować ten przykład). W „przestrzeni jądra” może ta notatka może ci pomóc: lxr.linux.no/linux+v3.6.6/Documentation/...
Daniel Frederico Lins Leite
Dziękuję bardzo za wyjaśnienie. W każdym razie twoja odpowiedź była dość opisowa i pomocna w przeciwieństwie do innych
Vinay Yadav
13

DEADLOCK Deadlock to stan, w którym zadanie czeka w nieskończoność na warunki, których nigdy nie można spełnić - zadanie twierdzi, że ma wyłączną kontrolę nad zasobami współdzielonymi - zadanie wstrzymuje zasoby podczas oczekiwania na zwolnienie innych zasobów - zadań nie można zmuszać do rozróżnienia zasobów - cykliczne oczekiwanie warunek istnieje

LIVELOCK Warunki Livelock mogą powstać, gdy dwa lub więcej zadań zależy od i używa jakiegoś zasobu, powodując warunek cyklicznej zależności, w którym zadania te działają nieprzerwanie, blokując w ten sposób wszystkie zadania o niższym priorytecie (te zadania o niższym priorytecie doświadczają stanu głodowego)

Deepak Lamichhane
źródło
Jeśli zadania „zablokowane” są zgodne z protokołami arbitrażu zasobów, które obejmują opóźnienia „wycofania” i spędzają większość czasu w stanie uśpienia, inne zadania nie będą głodowane.
greggo,
8

Być może te dwa przykłady ilustrują różnicę między impasem a blokadą na żywo:


Przykład Java dla impasu:

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

Przykładowe dane wyjściowe:

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

Przykład Java dla blokady na żywo:


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

Przykładowe dane wyjściowe:

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

Oba przykłady zmuszają wątki do zdobywania zamków w różnych porządkach. Podczas gdy impas czeka na drugi zamek, blokada blokady tak naprawdę nie czeka - desperacko próbuje zdobyć zamek bez szansy na jego zdobycie. Każda próba zużywa cykle procesora.

mmirwaldt
źródło
Kod jest fajny. Ale przykład blokady na żywo nie jest dobry. To, czy wątek jest blokowany na wartości, czy odpytuje o zmianę wartości, nie różni się koncepcyjnie. Łatwą zmianą, aby lepiej zilustrować blokadę na żywo, jest odblokowanie przez gwinty A i B blokad, które mają, gdy zdają sobie sprawę, że nie mogą uzyskać drugiej blokady, której potrzebują. Następnie śpią przez sekundę, ponownie zdobywają zamek, który pierwotnie mieli, następnie śpią przez kolejną sekundę i próbują ponownie zdobyć drugi zamek. Tak więc cykl dla każdego będzie następujący: 1) przejęcie-moje, 2) uśpienie, 3) próba nabycia innych i nieudane, 4) zwolnienie-wydobycie, 5) sen, 6) powtórzenie.
CognizantApe
1
Wątpię, czy blokady na żywo, o których myślisz, naprawdę istnieją wystarczająco długo, by powodować problemy. Kiedy zawsze rezygnujesz ze wszystkich blokad, które trzymasz, gdy nie możesz przydzielić kolejnej blokady, brakuje impasu (i blokady na żywo) „wstrzymaj i czekaj”, ponieważ tak naprawdę nie trzeba już czekać. ( en.wikipedia.org/wiki/Deadlock )
mmirwaldt
rzeczywiście brak martwego zamka, ponieważ są to blokady na żywo, które omawiamy. Podany przykład jest podobny do podanego standardowego przykładu korytarza: geeksforgeeks.org/deadlock-starvation-and-livelock , en.wikibooks.org/wiki/Operating_System_Design/Concurrency/… , docs.oracle.com/javase/tutorial/essential / concurrency /…
CognizantApe
0

Wyobraź sobie, że masz wątek A i wątek B. Oba są synchronisedna tym samym obiekcie, a wewnątrz tego bloku znajduje się zmienna globalna, którą aktualizują;

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

Tak więc, gdy nawlec wchodzi w whilepętlę i posiada blokadę, to robi to, co musi zrobić i ustawić commonVarsię true. Następnie przełóż B przychodzi, wchodzi w whilepętlę, a ponieważ commonVarjest trueteraz, że jest w stanie utrzymać blokadę. Robi to, wykonuje synchronisedblok i commonVarwraca do false. Teraz wątek A ponownie otrzymuje nowe okno procesora, miał właśnie opuścić whilepętlę, ale wątek B właśnie go ustawił false, więc cykl się powtarza. Wątki coś robią (więc nie są blokowane w tradycyjnym sensie), ale praktycznie za nic.

Warto też wspomnieć, że livelock niekoniecznie musi się tutaj pojawiać. Zakładam, że program planujący faworyzuje drugi wątek po synchronisedzakończeniu wykonywania bloku. Myślę, że przez większość czasu jest to trudny do przebicia oczekiwanie i zależy od wielu rzeczy, które dzieją się pod maską.

standardowe
źródło
Niezły przykład. Ilustruje również, dlaczego zawsze należy czytać i pisać atomowo w równoległym kontekście. Gdyby pętle while znajdowały się w blokach synchronizacji, powyższe nie stanowiłoby problemu.
CognizantApe