Deadlock - o'lik qulflanish - Operatsion tizimlar

Ikki oqim bir-birini kutadi va hech qaysisi hech qachon davom eta olmaydi. Bu deadlock - parallel dasturlashning eng qo'rqinchli xatosi.

Klassik misol #

Doira hosil bo'ldi - hech kim davom eta olmaydi

/* DIQQAT: bu dastur qotib qoladi - uni ishga tushirmang */

pthread_mutex_t qulf1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t qulf2 = PTHREAD_MUTEX_INITIALIZER;

void *oqim_a(void *arg) {
    pthread_mutex_lock(&qulf1);
    sleep(1);
    pthread_mutex_lock(&qulf2);         /* B ni kutadi */

    pthread_mutex_unlock(&qulf2);
    pthread_mutex_unlock(&qulf1);
    return NULL;
}

void *oqim_b(void *arg) {
    pthread_mutex_lock(&qulf2);
    sleep(1);
    pthread_mutex_lock(&qulf1);         /* A ni kutadi */

    pthread_mutex_unlock(&qulf1);
    pthread_mutex_unlock(&qulf2);
    return NULL;
}

sleep(1) nima uchun qo'yilgan?

sleep bo'lmasa, dastur ko'pincha muammosiz ishlaydi - birinchi oqim ikkala qulfni tezda olib, ishini tugatadi.

sleep deadlock ehtimolini oshiradi va muammoni ko'rinadigan qiladi.

Amaliy dasturlarda sleep yo'q, lekin uning o'rniga fayl o'qish, tarmoq so'rovi yoki og'ir hisob turadi. Natija bir xil - oqim kechikadi va deadlock yuz beradi.

Shuning uchun deadlock sinovda chiqmay, ishlab chiqarishda katta yuklamada paydo bo'ladi.

Deadlock ning to'rt sharti #

Bu shartlarni 1971-yilda Edward Coffman aniqlagan

Yechim: qulflarni bir tartibda olish #

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

pthread_mutex_t qulf1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t qulf2 = PTHREAD_MUTEX_INITIALIZER;

int hisob1 = 100;
int hisob2 = 200;

/* Ikkala oqim ham qulf1 ni BIRINCHI oladi */
void *otkazma_a(void *arg) {
    (void) arg;

    pthread_mutex_lock(&qulf1);
    pthread_mutex_lock(&qulf2);

    hisob1 -= 10;
    hisob2 += 10;

    pthread_mutex_unlock(&qulf2);
    pthread_mutex_unlock(&qulf1);

    return NULL;
}

void *otkazma_b(void *arg) {
    (void) arg;

    pthread_mutex_lock(&qulf1);         /* xuddi shu tartib */
    pthread_mutex_lock(&qulf2);

    hisob2 -= 20;
    hisob1 += 20;

    pthread_mutex_unlock(&qulf2);
    pthread_mutex_unlock(&qulf1);

    return NULL;
}

int main(void) {
    pthread_t a, b;

    pthread_create(&a, NULL, otkazma_a, NULL);
    pthread_create(&b, NULL, otkazma_b, NULL);

    pthread_join(a, NULL);
    pthread_join(b, NULL);

    printf("Hisob 1 : %d\n", hisob1);
    printf("Hisob 2 : %d\n", hisob2);
    printf("Jami    : %d (o'zgarmasligi kerak)\n", hisob1 + hisob2);
    printf("Deadlock bo'lmadimi? ha - dastur tugadi\n");

    return 0;
}

Natija

Hisob 1 : 110
Hisob 2 : 190
Jami    : 300 (o'zgarmasligi kerak)
Deadlock bo'lmadimi? ha - dastur tugadi

Qulf tartibi - eng ishonchli yechim

Barcha oqimlar qulflarni bir xil tartibda olsin. Shunda doiraviy kutish (4-shart) mumkin emas.

Amalda tartibni qanday belgilash kerak?

Manzil bo'yicha: &qulf1 < &qulf2 bo'lsa, birinchisini oldin ol;
Raqam bo'yicha: har bir qulfga tartib raqami bering;
Nom bo'yicha: alifbo tartibida.

Manzil bo'yicha usul dinamik obyektlar uchun qulay:

void ikkitasini_qulfla(pthread_mutex_t *a, pthread_mutex_t *b) {
    if (a < b) {
        pthread_mutex_lock(a);
        pthread_mutex_lock(b);
    } else {
        pthread_mutex_lock(b);
        pthread_mutex_lock(a);
    }
}

Yechim: `trylock` bilan orqaga chekinish #

#include <stdio.h>
#include <pthread.h>
#include <time.h>

/* usleep POSIX.1-2008 da olib tashlangan - nanosleep ishlatamiz */
static void kutish(long mikrosoniya) {
    struct timespec vaqt = {
        .tv_sec = mikrosoniya / 1000000L,
        .tv_nsec = (mikrosoniya % 1000000L) * 1000L
    };

    nanosleep(&vaqt, NULL);
}

pthread_mutex_t qulf1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t qulf2 = PTHREAD_MUTEX_INITIALIZER;

int muvaffaqiyat = 0;
pthread_mutex_t hisob_qulfi = PTHREAD_MUTEX_INITIALIZER;

void *ishchi(void *arg) {
    int teskari = *(int *) arg;

    pthread_mutex_t *birinchi = teskari ? &qulf2 : &qulf1;
    pthread_mutex_t *ikkinchi = teskari ? &qulf1 : &qulf2;

    for (int urinish = 0; urinish < 100; urinish++) {
        pthread_mutex_lock(birinchi);

        if (pthread_mutex_trylock(ikkinchi) == 0) {
            /* ikkalasini ham oldik */
            pthread_mutex_unlock(ikkinchi);
            pthread_mutex_unlock(birinchi);

            pthread_mutex_lock(&hisob_qulfi);
            muvaffaqiyat++;
            pthread_mutex_unlock(&hisob_qulfi);

            return NULL;
        }

        /* ikkinchisi band - birinchisini ham qo'yib yuboramiz */
        pthread_mutex_unlock(birinchi);
        kutish(1000);                   /* biroz kutamiz */
    }

    return NULL;
}

int main(void) {
    pthread_t a, b;
    int togri = 0, teskari = 1;

    pthread_create(&a, NULL, ishchi, &togri);
    pthread_create(&b, NULL, ishchi, &teskari);

    pthread_join(a, NULL);
    pthread_join(b, NULL);

    printf("Teskari tartibda qulflandi, lekin deadlock bo'lmadi\n");
    printf("Muvaffaqiyatli tugagan oqimlar: %d / 2\n", muvaffaqiyat);

    return 0;
}

Natija

Teskari tartibda qulflandi, lekin deadlock bo'lmadi
Muvaffaqiyatli tugagan oqimlar: 2 / 2

usleep o'rniga nanosleep

Eski kodlarda usleep(1000) uchraydi, lekin u POSIX.1-2008 da olib tashlangan. Qat'iy standart rejimida kompilyatsiya qilsangiz:

Natija

error: implicit declaration of function 'usleep'

Zamonaviy almashtiruvchisi - nanosleep. U aniqroq (nanosoniya darajasida) va standart tarkibida qoladi.

struct timespec vaqt = {.tv_sec = 0, .tv_nsec = 1000000L};   /* 1 ms */
nanosleep(&vaqt, NULL);

trylock «ushlab kutish» shartini buzadi

pthread_mutex_trylock qulf band bo'lsa kutmaydi - darhol xato qaytaradi.

Shunda oqim ushlab turgan qulfini ham qo'yib yuboradi va qaytadan urinadi. Doiraviy kutish hosil bo'lmaydi.

Diqqat: bu yerda tirik qulflanish (livelock) xavfi bor - ikkala oqim bir vaqtda urinib, bir vaqtda chekinsa, ular abadiy «raqsga tushishi» mumkin.

Shuning uchun usleep tasodifiy vaqtga qo'yilsa yaxshiroq - bu tarmoq protokollaridagi «exponential backoff» g'oyasi.

Ovqatlanuvchi faylasuflar #

Dijkstra 1965-yilda qo'ygan bu masala hozir ham o'rgatiladi

#include <stdio.h>
#include <pthread.h>

#define FAYLASUFLAR 5
#define OVQATLANISH 20

pthread_mutex_t choplar[FAYLASUFLAR];
int ovqatlandi[FAYLASUFLAR] = {0};

void *faylasuf(void *arg) {
    int raqam = *(int *) arg;
    int chap = raqam;
    int ong = (raqam + 1) % FAYLASUFLAR;

    /* Oxirgi faylasuf teskari tartibda oladi - doira uziladi */
    if (raqam == FAYLASUFLAR - 1) {
        int vaqtinchalik = chap;
        chap = ong;
        ong = vaqtinchalik;
    }

    for (int i = 0; i < OVQATLANISH; i++) {
        pthread_mutex_lock(&choplar[chap]);
        pthread_mutex_lock(&choplar[ong]);

        ovqatlandi[raqam]++;            /* ovqatlanmoqda */

        pthread_mutex_unlock(&choplar[ong]);
        pthread_mutex_unlock(&choplar[chap]);
    }

    return NULL;
}

int main(void) {
    pthread_t oqimlar[FAYLASUFLAR];
    int raqamlar[FAYLASUFLAR];

    for (int i = 0; i < FAYLASUFLAR; i++) {
        pthread_mutex_init(&choplar[i], NULL);
    }

    for (int i = 0; i < FAYLASUFLAR; i++) {
        raqamlar[i] = i;
        pthread_create(&oqimlar[i], NULL, faylasuf, &raqamlar[i]);
    }

    for (int i = 0; i < FAYLASUFLAR; i++) {
        pthread_join(oqimlar[i], NULL);
    }

    int jami = 0;
    int hammasi_tokis = 1;

    for (int i = 0; i < FAYLASUFLAR; i++) {
        jami += ovqatlandi[i];

        if (ovqatlandi[i] != OVQATLANISH) {
            hammasi_tokis = 0;
        }

        pthread_mutex_destroy(&choplar[i]);
    }

    printf("Har bir faylasuf %d martadan ovqatlanishi kerak edi\n", OVQATLANISH);
    printf("Jami ovqatlanish : %d\n", jami);
    printf("Hammasi to'liq ovqatlandimi? %s\n", hammasi_tokis ? "ha" : "yo'q");
    printf("Deadlock bo'lmadi - dastur tugadi\n");

    return 0;
}

Natija

Har bir faylasuf 20 martadan ovqatlanishi kerak edi
Jami ovqatlanish : 100
Hammasi to'liq ovqatlandimi? ha
Deadlock bo'lmadi - dastur tugadi

Faylasuflar masalasining boshqa yechimlari

Yechim	G'oya
Assimetriya	Bittasi teskari tartibda oladi (yuqoridagi)
Ofitsiant	Markaziy nazoratchi ruxsat beradi (semafor)
N-1 chegara	Bir vaqtda ko'pi bilan 4 ta faylasuf stolda
Ikkalasini birga olish	Ikkala cho'p bo'sh bo'lsagina olish

Eng oddiy va samarali - birinchi yechim. U qo'shimcha resurs talab qilmaydi.

Deadlock ni aniqlash #

Terminal

# Qotib qolgan jarayonning oqimlarini ko'rish
gdb -p 1234
(gdb) thread apply all bt

Natija

Thread 3 (Thread 0x7f2a...):
#0  __lll_lock_wait ()
#1  pthread_mutex_lock ()
#2  0x... in oqim_b () at deadlock.c:24     ← qulf1 ni kutmoqda

Thread 2 (Thread 0x7f2b...):
#0  __lll_lock_wait ()
#1  pthread_mutex_lock ()
#2  0x... in oqim_a () at deadlock.c:15     ← qulf2 ni kutmoqda

Ikkala oqim ham pthread_mutex_lock da qotib qolgan - bu deadlock ning aniq belgisi.

Avtomatik aniqlash vositalari

Terminal

# ThreadSanitizer - poyga va deadlock ni topadi
gcc -std=c17 -g -fsanitize=thread dastur.c -o dastur -pthread
./dastur

Natija

WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
  Cycle in lock order graph: M1 => M2 => M1

Eng qimmatlisi: ThreadSanitizer deadlock haqiqatan sodir bo'lmasa ham uni topa oladi. U qulflar tartibini kuzatadi va xavfli naqshni aniqlaydi.

valgrind --tool=helgrind ham shunga o'xshash ishni bajaradi.

Tirik qulflanish (livelock) #

#include <stdio.h>
#include <pthread.h>
#include <time.h>

static void kutish(long mikrosoniya) {
    struct timespec vaqt = {
        .tv_sec = mikrosoniya / 1000000L,
        .tv_nsec = (mikrosoniya % 1000000L) * 1000L
    };

    nanosleep(&vaqt, NULL);
}

pthread_mutex_t qulf1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t qulf2 = PTHREAD_MUTEX_INITIALIZER;

int urinishlar = 0;
pthread_mutex_t hisob = PTHREAD_MUTEX_INITIALIZER;

void *ishchi(void *arg) {
    int teskari = *(int *) arg;

    pthread_mutex_t *birinchi = teskari ? &qulf2 : &qulf1;
    pthread_mutex_t *ikkinchi = teskari ? &qulf1 : &qulf2;

    for (int i = 0; i < 50; i++) {
        pthread_mutex_lock(birinchi);

        if (pthread_mutex_trylock(ikkinchi) == 0) {
            pthread_mutex_unlock(ikkinchi);
            pthread_mutex_unlock(birinchi);
            return NULL;                /* ish bajarildi */
        }

        pthread_mutex_unlock(birinchi);

        pthread_mutex_lock(&hisob);
        urinishlar++;
        pthread_mutex_unlock(&hisob);

        kutish(100 + (i % 7) * 50);     /* har xil kutish - livelock dan qochamiz */
    }

    return NULL;
}

int main(void) {
    pthread_t a, b;
    int togri = 0, teskari = 1;

    pthread_create(&a, NULL, ishchi, &togri);
    pthread_create(&b, NULL, ishchi, &teskari);

    pthread_join(a, NULL);
    pthread_join(b, NULL);

    printf("Ikkala oqim tugadi\n");
    printf("Muvaffaqiyatsiz urinishlar 50 dan kammi? %s\n",
           urinishlar < 100 ? "ha" : "yo'q");

    return 0;
}

Natija

Ikkala oqim tugadi
Muvaffaqiyatsiz urinishlar 50 dan kammi? ha

Livelock - deadlock dan ham ayyor

	Deadlock	Livelock
Holat	Oqimlar uxlaydi	Oqimlar ishlaydi
Protsessor	Bo'sh	100% band
`top` da ko'rinishi	Jarayon qotgan	Jarayon juda band
Aniqlash	Osonroq	Qiyinroq

Livelock da oqimlar doim harakatda, lekin hech qanday foydali ish bajarilmaydi. Ular bir-biriga yo'l berib, abadiy o'rin almashadi.

Xuddi tor koridorda ikki odam bir-biriga yo'l bermoqchi bo'lib, bir vaqtda bir tomonga qadam tashlagani kabi.

Yechim: kutish vaqtini tasodifiy qilish.

Ochlik (starvation) #

Uchta muammoning farqi

Muammo	Nima sodir bo'ladi
Deadlock	Hech kim davom etmaydi - hammasi kutadi
Livelock	Hammasi harakatda, lekin ilgarilamaydi
Ochlik	Ba'zilar ishlaydi, biri hech qachon navbat olmaydi

Ochlik odatda ustuvorlik yoki adolatsiz qulf tufayli yuz beradi. Masalan rwlock da o'quvchilar to'xtovsiz kelib tursa, yozuvchi hech qachon navbat olmasligi mumkin.

Linux mutexlari adolatli emas - qulfni kutayotgan oqimlardan istalgani tanlanishi mumkin. Adolat kerak bo'lsa, o'zingiz navbat tuzishingiz kerak.

Deadlock dan qochish qoidalari #

Amaliy qoidalar

#	Qoida
1	Qulflarni doim bir xil tartibda oling
2	Bir vaqtda imkon qadar kam qulf ushlang
3	Qulf ushlab turib boshqa funksiyani chaqirmang
4	Qulf ushlab turib I/O qilmang
5	Kritik sohani qisqa tuting
6	Iloji bo'lsa atomik amallar ishlating
7	Umumiy ma'lumotdan butunlay voz keching
8	Ishlab chiqishda ThreadSanitizer yoqing

3-qoida ayniqsa muhim: chaqirilgan funksiya ichida yana qulf olinishi mumkin va siz buni bilmaysiz. Bu «yashirin» deadlock ning eng ko'p sababi.

Rekursiv mutex #

#include <stdio.h>
#include <pthread.h>

pthread_mutex_t qulf;

void ichki_funksiya(void) {
    pthread_mutex_lock(&qulf);          /* ikkinchi marta qulflaymiz */
    printf("  Ichki funksiya ishladi\n");
    pthread_mutex_unlock(&qulf);
}

void tashqi_funksiya(void) {
    pthread_mutex_lock(&qulf);
    printf("Tashqi funksiya boshlandi\n");

    ichki_funksiya();                   /* oddiy mutexda bu deadlock */

    printf("Tashqi funksiya tugadi\n");
    pthread_mutex_unlock(&qulf);
}

int main(void) {
    pthread_mutexattr_t xususiyat;

    pthread_mutexattr_init(&xususiyat);
    pthread_mutexattr_settype(&xususiyat, PTHREAD_MUTEX_RECURSIVE);
    pthread_mutex_init(&qulf, &xususiyat);

    tashqi_funksiya();

    pthread_mutex_destroy(&qulf);
    pthread_mutexattr_destroy(&xususiyat);

    printf("Deadlock bo'lmadi - rekursiv mutex ishladi\n");

    return 0;
}

Natija

Tashqi funksiya boshlandi
  Ichki funksiya ishladi
Tashqi funksiya tugadi
Deadlock bo'lmadi - rekursiv mutex ishladi

Rekursiv mutex - yechim emas, plastir

Oddiy mutexda o'zingizni qulflashga urinish - darhol deadlock. Rekursiv mutex buni ruxsat beradi va sanoqni yuritadi.

Lekin ko'p tajribali dasturchilar uni yomon belgi deb hisoblaydi: agar rekursiv mutex kerak bo'lsa, demak kod tuzilishi noto'g'ri - qulf ushlab turib boshqa funksiyani chaqiryapsiz.

Yaxshiroq yechim - kodni ikkiga bo'lish:

/* Ochiq funksiya: qulflaydi */
void ish_bajar(void) {
    pthread_mutex_lock(&qulf);
    ish_bajar_ichki();
    pthread_mutex_unlock(&qulf);
}

/* Ichki funksiya: qulf allaqachon olingan deb hisoblaydi */
static void ish_bajar_ichki(void) {
    /* ... */
}

Amaliy topshiriq

Deadlock keltirib chiqaruvchi dastur yozing va uni Ctrl+C bilan to'xtating.
gdb -p bilan ulanib, thread apply all bt qiling.
Qulf tartibini bir xil qilib, deadlock yo'qolishini tasdiqlang.
-fsanitize=thread bilan kompilyatsiya qilib, ogohlantirishni o'qing.
Faylasuflar masalasini deadlock bilan yozing.
Assimetriya yechimini qo'llab, tuzating.
trylock bilan orqaga chekinish yechimini yozing.
Barcha oqimlarga bir xil usleep berib, livelock yaratishga urinib ko'ring.
Rekursiv mutexni oddiy mutexga almashtirib, natijani ko'ring.
Coffman shartlarining har biri uchun buzish usulini yozing.

Xulosa #

Deadlock - oqimlar bir-birini kutib, hech qaysisi davom eta olmaydigan holat.
To'rt shart kerak: o'zaro istisno, ushlab kutish, tortib olib bo'lmaslik, doiraviy kutish.
Bittasini buzsangiz - deadlock bo'lmaydi.
Eng ishonchli yechim: qulflarni bir xil tartibda olish.
trylock «ushlab kutish» shartini buzadi, lekin livelock xavfini keltiradi.
Ovqatlanuvchi faylasuflar - klassik masala; eng oddiy yechim bittasini teskari tartibga o'tkazish.
Livelock da oqimlar ishlaydi, lekin ilgarilamaydi - protsessor 100% band bo'ladi.
Ochlik - biri hech qachon navbat olmaydi.
Qulf ushlab turib boshqa funksiyani chaqirmang.
ThreadSanitizer deadlock sodir bo'lmasa ham uni topa oladi.
Rekursiv mutex - odatda noto'g'ri tuzilishning belgisi.

Keyingi bo'limda xotira boshqaruviga o'tamiz.

Klassik misol #

Deadlock ning to'rt sharti #

Yechim: qulflarni bir tartibda olish #

Yechim: trylock bilan orqaga chekinish #

Ovqatlanuvchi faylasuflar #

Deadlock ni aniqlash #

Tirik qulflanish (livelock) #

Ochlik (starvation) #

Deadlock dan qochish qoidalari #

Rekursiv mutex #

Xulosa #

Xatolik topdingizmi?

Yechim: `trylock` bilan orqaga chekinish #