DeadLock (Zakleszczenie)

Zakleszczenie, blokada wzajemna (ang. deadlock) – sytuacja, w której co najmniej dwie różne akcje czekają na siebie nawzajem, więc żadna nie może się zakończyć.

Istnieją cztery warunki konieczne do powstania zakleszczenia:
1. Wzajemne wykluczanie Przynajmniej jeden zasób w systemie musi być niepodzielny, co oznacza, że tego zasobu może używać w określonym czasie tylko jeden proces.
Inne procesy, które chcą z niego skorzystać muszą oczekiwać na jego zwolnienie.
2. Przetrzymywanie i oczekiwanie Musi istnieć proces, który ma przydzielony co najmniej jeden zasób i równocześnie oczekuje na przydział innego zasobu posiadanego
przez inny proces.
3. Brak wywłaszczeń Jeśli proces otrzymał zasoby, to nie można mu ich odebrać.
Trzeba poczekać, aż zwolni je z własnej inicjatywy.
4. Czekanie cykliczne Musi istnieć zbiór procesów {P0, P1, . . . , Pn} w stanie oczekiwania, takich że każdy z nich czeka na zasób lub zasoby przetrzymywane przez swojego następnika, a proces Pn czeka na zasób(-oby) przetrzymywany przez P0.

Przykład

---

#include <windows.h>
#include <stdio.h>

#define NO_THREADS 2
int suma;
int PierwszaFlaga;
int DrugaFlaga;

DWORD WINAPI Thread1(LPVOID lpParam)
{
    for (int i = 0; i < 100000; i++)
    {
        PierwszaFlaga = 1;
        while (DrugaFlaga)
            Sleep(20);

        suma = suma + 1;
        PierwszaFlaga = 0;
    }
    return 0;
}

DWORD WINAPI Thread2(LPVOID lpParam)
{
    for (int i = 0; i < 100000; i++)
    {
        DrugaFlaga = 1;
        while (PierwszaFlaga)
            Sleep(20);

        suma = suma + 1;
        DrugaFlaga = 0;
    }
    return 0;
}

int main()
{
    HANDLE hThread[NO_THREADS];
    DWORD dwThreadId[NO_THREADS];

    suma = 0;
    PierwszaFlaga = 0;
    DrugaFlaga = 0;

    hThread[0] = CreateThread(
        NULL,    // Security attributes
        0,       // Default stack size
        Thread1, // Worker function
        NULL,    // Arguments for thread function
        0,       // Default creation flag
        &dwThreadId[0]);

    hThread[1] = CreateThread(
        NULL,    // Security attributes
        0,       // Default stack size
        Thread2, // Worker function
        NULL,    // Arguments for thread function
        0,       // Default creation flag
        &dwThreadId[1]);
    WaitForMultipleObjects(NO_THREADS, hThread, TRUE, INFINITE);
    CloseHandle(hThread[0]);
    CloseHandle(hThread[1]);
    printf("suma=%d\n", suma);
    return 0;
}

---

Wyjście:

Wyjaśnienie:

---

---

Przykład Rozwiązania : Przez użycie funkcji CRITICAL_SECTION ;

---

#include <windows.h>
#include <stdio.h>

#define NO_THREADS 2
int suma;
CRITICAL_SECTION cs;
DWORD WINAPI Thread1(LPVOID lpParam)
{
    for (int i=0; i<100000; i++)
    {
        EnterCriticalSection(&cs);
        suma = suma + 1;
        LeaveCriticalSection(&cs);
    }
    return 0;
}


int main()
{
    HANDLE hThread[NO_THREADS];
    DWORD dwThreadId[NO_THREADS];

    suma = 0;
    InitializeCriticalSection(&cs);

    hThread[0] = CreateThread(
        NULL,                   //Security attributes
        0,                      //Default stack size
        Thread1,          //Worker function
        NULL,                   //Arguments for thread function
        0,                      //Default creation flag
        &dwThreadId[0]
    );

    hThread[1] = CreateThread(
        NULL,                   //Security attributes
        0,                      //Default stack size
        Thread1,          //Worker function
        NULL,                   //Arguments for thread function
        0,                      //Default creation flag
        &dwThreadId[1]
    );

    WaitForMultipleObjects(NO_THREADS, hThread, TRUE, INFINITE);
    DeleteCriticalSection(&cs);

    CloseHandle(hThread[0]);
    CloseHandle(hThread[1]);

    printf("suma=%d\n", suma);

    return 0;
}

---

Wyjście:

---

Źródła; https://pl.wikipedia.org/wiki/Zakleszczenie

Prezentacja: https://achilles.tu.kielce.pl/portal/Members/84df831b59534bdc88bef09b15e73c99/archive/semestr-i-2019-2020/pdf/so1/lecture/os_lect_6cs.pdf