Co to jest impas?

Podczas pisania aplikacji wielowątkowych jednym z najczęściej występujących problemów są zakleszczenia.

Moje pytania do społeczności to:

1. Co to jest impas?

2. Jak je wykrywasz?

3. Czy sobie z nimi radzisz?

4. I wreszcie, jak im zapobiegasz?

Blokada występuje, gdy wiele procesów próby uzyskania dostępu do tych samych zasobów w tym samym czasie.

Jeden proces przegrywa i musi czekać na zakończenie drugiego.

Zakleszczenie występuje, gdy proces czeka wciąż trzyma się do innego zasobu, że pierwsze potrzeby przed nim może zakończyć.

A więc przykład:

Zasoby A i B są używane przez proces X i proces Y.

• X zaczyna używać A.
• X i Y próbują zacząć używać B.
• Y „wygrywa” i jako pierwszy otrzymuje B.
• teraz Y musi użyć A
• A jest zablokowane przez X, które czeka na Y

Najlepszym sposobem uniknięcia zakleszczeń jest unikanie krzyżowania się procesów w ten sposób. Ogranicz potrzebę blokowania czegokolwiek tak bardzo, jak tylko możesz.

W bazach danych unikaj dokonywania wielu zmian w różnych tabelach w jednej transakcji, unikaj wyzwalaczy i przełączaj się na optymistyczne / brudne / zerowe odczyty tak często, jak to możliwe.

Pozwólcie, że wyjaśnię przykład z prawdziwego świata (a nie do rzeczywistości) sytuacji impasu z filmów kryminalnych. Wyobraź sobie, że przestępca trzyma zakładnika, a przeciwko temu policjant trzyma również zakładnika, który jest przyjacielem przestępcy. W tym przypadku przestępca nie wypuści zakładnika, jeśli policjant nie pozwoli puścić swojego przyjaciela. Policjant nie wypuści również przyjaciela przestępcy, chyba że przestępca wypuści zakładnika. Jest to nieskończona, niewiarygodna sytuacja, ponieważ obie strony nalegają na zrobienie pierwszego kroku od siebie.

Scena kryminalna i policjant

Tak więc po prostu, gdy dwa wątki wymagają dwóch różnych zasobów, a każdy z nich ma blokadę zasobu, którego potrzebuje drugi, jest to impas.

Kolejne wysokopoziomowe wyjaśnienie impasu: złamane serca

Spotykasz się z dziewczyną i dzień po kłótni obie strony są ze złamanymi sercami i czekają na -przepraszam-i-przegapiłem-ciebie- telefon. W tej sytuacji obie strony chcą się komunikować wtedy i tylko wtedy, gdy jedna z nich otrzyma od drugiej przepraszam telefon. Ponieważ żaden z nich nie rozpocznie komunikacji i nie będzie czekał w stanie pasywnym, oba będą czekać, aż druga osoba rozpocznie komunikację, co kończy się zakleszczeniem.

Zakleszczenia wystąpią tylko wtedy, gdy masz dwa lub więcej zamków, które można zdobyć w tym samym czasie i są one chwytane w różnej kolejności.

Sposoby uniknięcia zakleszczeń to:

• unikaj zamków (jeśli to możliwe),
• unikaj posiadania więcej niż jednego zamka
• zawsze bierz zamki w tej samej kolejności.

Aby zdefiniować impas, najpierw zdefiniowałbym proces.

Proces : Jak wiemy, proces to nic innego jak programwykonanie.

Zasoby : do wykonania procesu programu potrzebne są zasoby. Kategorie zasobów mogą obejmować pamięć, drukarki, procesory, otwarte pliki, napędy taśmowe, dyski CD-ROM itp.

Zakleszczenie : Zakleszczenie to sytuacja lub stan, w którym co najmniej dwa procesy zatrzymują pewne zasoby i próbują zdobyć więcej zasobów i nie mogą zwolnić zasobów, dopóki nie zakończą wykonywania.

Stan lub sytuacja impasu

Na powyższym diagramie są dwa procesy P1 i p2 oraz dwa zasoby R1 i R2 .

Zasób R1 jest przydzielony do procesu P1, a zasób R2 do procesu p2 . Aby zakończyć realizację procesu, P1 potrzebuje zasobu R2 , więc żądanie P1 dla R2 , ale R2 jest już przydzielone do P2 .

W ten sam sposób Proces P2 do ukończenia wykonania wymaga R1 , ale R1 jest już przydzielone do P1 .

oba procesy nie mogą zwolnić swoich zasobów do momentu zakończenia ich wykonywania i dopóki nie zakończą. Więc oboje czekają na kolejne zasoby i będą czekać wiecznie. Więc to jest stan DEADLOCK .

Aby nastąpiło zakleszczenie, muszą być spełnione cztery warunki.

1. Wzajemne wykluczenie - każdy zasób jest obecnie przydzielony dokładnie do jednego procesu lub jest dostępny. (Dwa procesy nie mogą jednocześnie kontrolować tego samego zasobu ani znajdować się w ich krytycznej sekcji).
2. Trzymaj i czekaj - procesy aktualnie posiadające zasoby mogą zażądać nowych zasobów.
3. Bez uprzedzenia - gdy proces przechowuje zasób, nie może zostać odebrany przez inny proces lub jądro.
4. Cykliczne czekanie - każdy proces oczekuje na uzyskanie zasobu, który jest utrzymywany przez inny proces.

i wszystkie te warunki są spełnione na powyższym schemacie.

Zakleszczenie ma miejsce, gdy wątek oczekuje na coś, co nigdy się nie wydarzy.

Zwykle dzieje się tak, gdy wątek oczekuje na muteks lub semafor, który nigdy nie został zwolniony przez poprzedniego właściciela.

Często się to zdarza, gdy masz sytuację obejmującą dwa wątki i dwa zamki, takie jak ta:

Thread 1               Thread 2

Lock1->Lock();         Lock2->Lock();
WaitForLock2();        WaitForLock1();   <-- Oops!

Zwykle je wykrywasz, ponieważ rzeczy, których się spodziewasz, nigdy się nie zdarzają lub aplikacja całkowicie się zawiesza.

Możesz rzucić okiem na te wspaniałe artykuły w sekcji Deadlock . Jest w C #, ale idea jest nadal taka sama dla innych platform. Cytuję tutaj dla łatwego czytania

Zakleszczenie występuje, gdy dwa wątki czekają na zasób przechowywany przez drugi, więc żaden z nich nie może kontynuować. Najłatwiej to zilustrować za pomocą dwóch zamków:

object locker1 = new object();
object locker2 = new object();

new Thread (() => {
                    lock (locker1)
                    {
                      Thread.Sleep (1000);
                      lock (locker2);      // Deadlock
                    }
                  }).Start();
lock (locker2)
{
  Thread.Sleep (1000);
  lock (locker1);                          // Deadlock
}

Zakleszczenie jest częstym problemem w wieloprocesorowych / wieloprogramowych problemach w systemie operacyjnym. Powiedzmy, że istnieją dwa procesy P1, P2 i dwa globalnie współużytkowane zasoby R1, R2, aw sekcji krytycznej oba zasoby muszą być dostępne

Początkowo system operacyjny przypisuje R1 do przetwarzania P1 i R2 do przetwarzania P2. Ponieważ oba procesy działają jednocześnie, mogą rozpocząć wykonywanie swojego kodu, ale PROBLEM pojawia się, gdy proces trafia do sekcji krytycznej. Więc proces R1 będzie czekał na wypuszczenie R2 przez proces P2 i odwrotnie ... Więc będą czekać wiecznie (DEADLOCK CONDITION).

Mała ANALOGIA ...

Twoja Matka (OS),
Ty (P1),
Twój brat (P2),
Jabłko (R1),
Nóż (R2),
sekcja krytyczna (cięcie jabłka nożem).

Na początku twoja matka daje ci jabłko i nóż twojemu bratu.
Oboje są szczęśliwi i grają (wykonują swoje kody).
Każdy z was chce kiedyś pokroić jabłko (część krytyczna).
Nie chcesz dać jabłka swojemu bratu.
Twój brat nie chce ci dać noża.
Więc oboje będziecie czekać bardzo długo :)

Zakleszczenie ma miejsce, gdy dwa wątki zostają zablokowane, co uniemożliwia rozwój któregokolwiek z nich. Najlepszym sposobem na ich uniknięcie jest ostrożny rozwój. Wiele systemów wbudowanych chroni się przed nimi za pomocą timera watchdog (timera, który resetuje system, gdy zawiesi się na określony czas).

Zakleszczenie występuje, gdy istnieje cykliczny łańcuch wątków lub procesów, z których każdy zawiera zablokowany zasób i próbuje zablokować zasób przechowywany przez następny element w łańcuchu. Na przykład dwa wątki, które utrzymują odpowiednio zamek A i zamek B i oba próbują uzyskać drugi zamek.

Klasyczny i bardzo prosty program do zrozumienia sytuacji impasu : -

public class Lazy {

    private static boolean initialized = false;

    static {
        Thread t = new Thread(new Runnable() {
            public void run() {
                initialized = true;
            }
        });

        t.start();

        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        System.out.println(initialized);
    }
}

Gdy główny wątek wywołuje Lazy.main, sprawdza, czy klasa Lazy została zainicjowana i zaczyna inicjować klasę. Główny wątek ustawia teraz wartość initialized na false, tworzy i uruchamia wątek w tle, którego metoda uruchamiania ustawia wartość true, i czeka na zakończenie wątku w tle.

Tym razem klasa jest obecnie inicjowana przez inny wątek. W takich okolicznościach bieżący wątek, który jest wątkiem w tle, oczekuje na obiekcie Class do zakończenia inicjalizacji. Niestety, wątek wykonujący inicjalizację, główny wątek, czeka na zakończenie wątku w tle. Ponieważ dwa wątki czekają teraz na siebie, program jest DEADLOCKED.

Zakleszczenie to stan systemu, w którym żaden pojedynczy proces / wątek nie jest w stanie wykonać akcji. Jak wspominali inni, zakleszczenie jest zwykle wynikiem sytuacji, w której każdy proces / wątek chce uzyskać blokadę zasobu, który jest już zablokowany przez inny (lub nawet ten sam) proces / wątek.

Istnieją różne metody ich odnajdywania i unikania. Człowiek myśli bardzo intensywnie i / lub próbuje wielu rzeczy. Jednak radzenie sobie z równoległością jest notorycznie trudne i większość (jeśli nie wszyscy) ludzi nie będzie w stanie całkowicie uniknąć problemów.

Niektóre bardziej formalne metody mogą być przydatne, jeśli poważnie podchodzisz do tego rodzaju problemów. Najbardziej praktyczną metodą, jaką znam, jest podejście oparte na teorii procesu. Tutaj modelujesz swój system w jakimś języku procesu (np. CCS, CSP, ACP, mCRL2, LOTOS) i używasz dostępnych narzędzi do (modelowania) sprawdzania zakleszczeń (i być może także innych właściwości). Przykładowe zestawy narzędzi do użycia to FDR, mCRL2, CADP i Uppaal. Niektóre odważne dusze mogą nawet udowodnić, że ich systemy są wolne od impasu, używając metod czysto symbolicznych (dowodzenie twierdzeń; poszukaj Owickiego-Griesa).

Jednak te formalne metody zwykle wymagają pewnego wysiłku (np. Nauka podstaw teorii procesów). Ale myślę, że to po prostu konsekwencja faktu, że te problemy są trudne.

Zakleszczenie to sytuacja, w której jest mniej dostępnych zasobów, ponieważ żąda ich inny proces. Oznacza to, że gdy liczba dostępnych zasobów zmniejszy się, niż żąda użytkownik, to w tym czasie proces przechodzi w stan oczekiwania. Czasem oczekiwanie rośnie bardziej i nie ma szans, aby sprawdzić problem braku zasobów. ta sytuacja jest znana jako zakleszczenie. W rzeczywistości zakleszczenie jest dla nas poważnym problemem i występuje tylko w wielozadaniowym systemie operacyjnym. Dezadycja nie może wystąpić w jednozadaniowym systemie operacyjnym, ponieważ wszystkie zasoby są obecne tylko dla tego zadania, które jest aktualnie uruchomione ......

Powyższe wyjaśnienia są miłe. Mam nadzieję, że to również może być przydatne: https://ora-data.blogspot.in/2017/04/deadlock-in-oracle.html

W bazie danych, gdy sesja (np. Ora) chce zasobu utrzymywanego przez inną sesję (np. Dane), ale ta sesja (dane) również potrzebuje zasobu, który jest utrzymywany przez pierwszą sesję (ora). Może być zaangażowanych więcej niż 2 sesje, ale pomysł będzie ten sam. W rzeczywistości zakleszczenia uniemożliwiają dalsze działanie niektórych transakcji. Na przykład: Załóżmy, że ORA-DATA przechowuje blokadę A i żąda blokady B, a SKU utrzymuje blokadę B i żąda blokady A.

Dzięki,

Zakleszczenie występuje, gdy wątek oczekuje na zakończenie innego wątku i na odwrót.

Jak ominąć?
- Unikaj zagnieżdżonych blokad
- Unikaj niepotrzebnych blokad
- Użyj łączenia wątków ()

Jak to wykryjesz?
uruchom to polecenie w cmd:

jcmd $PID Thread.print

referencyjne : geeksforgeeks

Zakleszczenia występują nie tylko w przypadku zamków, chociaż jest to najczęstsza przyczyna. W C ++ można utworzyć zakleszczenie z dwoma wątkami i bez blokad, po prostu ustawiając każde wywołanie wątku join () na obiekcie std :: thread dla drugiego.

Kontrola współbieżności oparta na blokadach

Używanie blokowania do kontrolowania dostępu do zasobów udostępnionych jest podatne na zakleszczenia, a sam harmonogram transakcji nie może zapobiec ich wystąpieniu.

Na przykład systemy relacyjnych baz danych używają różnych blokad, aby zagwarantować właściwości ACID transakcji .

Niezależnie od używanego systemu relacyjnych baz danych, blokady będą zawsze uzyskiwane podczas modyfikowania (np. UPDATELub DELETE) określonego rekordu tabeli. Bez blokowania wiersza, który został zmodyfikowany przez aktualnie działającą transakcję, bezpieczeństwo Atomicity zostało naruszone .

Co to jest impas

Jak wyjaśniłem w tym artykule , zakleszczenie występuje, gdy dwie współbieżne transakcje nie mogą zostać wykonane, ponieważ każda z nich czeka, aż druga zwolni blokadę, jak pokazano na poniższym diagramie.

Ponieważ obie transakcje są w fazie pozyskiwania blokady, żadna z nich nie zwalnia blokady przed uzyskaniem następnej.

Wychodzenie z sytuacji impasu

Jeśli używasz algorytmu kontroli współbieżności, który opiera się na blokadach, zawsze istnieje ryzyko uruchomienia w sytuacji zakleszczenia. Zakleszczenia mogą wystąpić w każdym środowisku współbieżności, nie tylko w systemie bazy danych.

Na przykład program wielowątkowy może zakleszczyć się, jeśli dwa lub więcej wątków oczekuje na blokady, które zostały wcześniej pobrane, tak że żaden wątek nie może wykonać żadnego postępu. Jeśli dzieje się tak w aplikacji Java, JVM nie może po prostu zmusić wątku do zatrzymania wykonywania i zwolnienia blokad.

Nawet jeśli Threadklasa ujawnia stopmetodę, ta metoda jest przestarzała od wersji Java 1.1, ponieważ może powodować pozostawienie obiektów w niespójnym stanie po zatrzymaniu wątku. Zamiast tego Java definiuje interruptmetodę, która działa jako wskazówka, ponieważ wątek, który zostaje przerwany, może po prostu zignorować przerwanie i kontynuować wykonywanie.

Z tego powodu aplikacja Java nie może odzyskać sprawności po sytuacji zakleszczenia, a na jej twórcy spoczywa odpowiedzialność za zlecenie żądań przejęcia blokady w taki sposób, aby zakleszczenia nigdy nie wystąpiły.

Jednak system bazy danych nie może wymusić danej kolejności przejęcia blokad, ponieważ nie można przewidzieć, jakie inne blokady dana transakcja będzie chciała uzyskać dalej. Za zachowanie kolejności blokad odpowiada warstwa dostępu do danych, a baza danych może jedynie pomagać w odtwarzaniu po sytuacji zakleszczenia.

Silnik bazy danych uruchamia oddzielny proces, który skanuje wykres bieżącego konfliktu pod kątem cykli oczekiwania na blokadę (spowodowanych zakleszczeniami). Po wykryciu cyklu silnik bazy danych wybiera jedną transakcję i przerywa ją, powodując zwolnienie blokad, dzięki czemu druga transakcja może być kontynuowana.

W przeciwieństwie do maszyny JVM transakcja bazy danych jest zaprojektowana jako niepodzielna jednostka pracy. W związku z tym wycofanie pozostawia bazę danych w spójnym stanie.

Aby uzyskać więcej informacji na ten temat, zapoznaj się również z tym artykułem .

Mutex to w istocie blokada, zapewniająca chroniony dostęp do współdzielonych zasobów. W systemie Linux typ danych muteksu wątku to pthread_mutex_t. Przed użyciem zainicjalizuj go.

Aby uzyskać dostęp do współdzielonych zasobów, musisz zablokować mutex. Jeśli mutex jest już w zamku, wywołanie zablokuje wątek do momentu odblokowania muteksu. Po zakończeniu wizyty we współdzielonych zasobach musisz je odblokować.

Ogólnie rzecz biorąc, istnieje kilka niepisanych podstawowych zasad:

• Uzyskaj blokadę przed użyciem udostępnionych zasobów.

• Trzymanie zamka tak krótko, jak to możliwe.

• Zwolnij blokadę, jeśli wątek zwróci błąd.