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

Czy ktoś może wyjaśnić przykładami (kodem), jaka jest różnica między impasem a blokowaniem aktywnym ?

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

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.

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.

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)

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.

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