Sinxronizatsiya - mutex va semafor - Operatsion tizimlar

Oldingi bo'limda umumiy o'zgaruvchi buzilishini ko'rdik. Endi uni qanday himoya qilishni o'rganamiz.

Kritik soha #

Kritik soha - umumiy ma'lumotga tegadigan kod bo'lagi

Yaxshi yechim uchun uch shart

O'zaro istisno - bir vaqtda faqat bitta oqim kritik sohada;
Rivojlanish - hech kim kritik sohada bo'lmasa, kutayotgan kira olsin;
Cheklangan kutish - hech kim mangu kutmasin.

Bunga qo'shimcha: yechim protsessorlar soniga yoki tezligiga bog'liq bo'lmasligi kerak.

Mutex - o'zaro istisno qulfi #

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

#define OQIMLAR 4
#define QADAMLAR 100000

int umumiy_hisob = 0;
pthread_mutex_t qulf = PTHREAD_MUTEX_INITIALIZER;

void *oshir(void *arg) {
    (void) arg;

    for (int i = 0; i < QADAMLAR; i++) {
        pthread_mutex_lock(&qulf);
        umumiy_hisob++;                 /* kritik soha */
        pthread_mutex_unlock(&qulf);
    }

    return NULL;
}

int main(void) {
    pthread_t oqimlar[OQIMLAR];

    for (int i = 0; i < OQIMLAR; i++) {
        pthread_create(&oqimlar[i], NULL, oshir, NULL);
    }

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

    int kutilgan = OQIMLAR * QADAMLAR;

    printf("Kutilgan : %d\n", kutilgan);
    printf("Natija   : %d\n", umumiy_hisob);
    printf("To'g'rimi? %s\n", umumiy_hisob == kutilgan ? "ha" : "yo'q");

    return 0;
}

Natija

Kutilgan : 400000
Natija   : 400000
To'g'rimi? ha

Mutex yaratishning ikki usuli

/* 1. Statik - eng oddiy */
pthread_mutex_t qulf = PTHREAD_MUTEX_INITIALIZER;

/* 2. Dinamik - sozlash kerak bo'lganda */
pthread_mutex_t qulf;
pthread_mutex_init(&qulf, NULL);
/* ... ishlatish ... */
pthread_mutex_destroy(&qulf);

Global mutex uchun birinchi usul yetarli. Strukturaning ichidagi mutex uchun ikkinchisi kerak.

Har bir lock uchun bitta unlock

pthread_mutex_lock(&qulf);

if (xato_holat) {
    return -1;              /* XATO: qulf ochilmadi - deadlock */
}

pthread_mutex_unlock(&qulf);

Erta qaytish qulfni ochmasa, boshqa oqimlar mangu kutadi.

Yechim - qaytishdan oldin ochish:

if (xato_holat) {
    pthread_mutex_unlock(&qulf);
    return -1;
}

Yoki kritik sohani imkon qadar qisqa qilish - shunda ichida shartlar ham bo'lmaydi.

Kritik soha qanchalik katta bo'lsin? #

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

#define OQIMLAR 4
#define QADAMLAR 50000

long umumiy = 0;
pthread_mutex_t qulf = PTHREAD_MUTEX_INITIALIZER;

/* Yomon: har bir qadamda qulflaymiz */
void *sekin(void *arg) {
    (void) arg;

    for (int i = 0; i < QADAMLAR; i++) {
        pthread_mutex_lock(&qulf);
        umumiy += i;
        pthread_mutex_unlock(&qulf);
    }

    return NULL;
}

/* Yaxshi: mahalliy yig'ib, oxirida bir marta qulflaymiz */
void *tez(void *arg) {
    (void) arg;
    long mahalliy = 0;

    for (int i = 0; i < QADAMLAR; i++) {
        mahalliy += i;
    }

    pthread_mutex_lock(&qulf);
    umumiy += mahalliy;
    pthread_mutex_unlock(&qulf);

    return NULL;
}

static long ishga_tushir(void *(*vazifa)(void *)) {
    pthread_t oqimlar[OQIMLAR];
    umumiy = 0;

    for (int i = 0; i < OQIMLAR; i++) {
        pthread_create(&oqimlar[i], NULL, vazifa, NULL);
    }

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

    return umumiy;
}

int main(void) {
    long a = ishga_tushir(sekin);
    long b = ishga_tushir(tez);

    printf("Sekin usul natijasi : %ld\n", a);
    printf("Tez usul natijasi   : %ld\n", b);
    printf("Natijalar bir xilmi? %s\n", a == b ? "ha" : "yo'q");

    return 0;
}

Natija

Sekin usul natijasi : 4999900000
Tez usul natijasi   : 4999900000
Natijalar bir xilmi? ha

Kritik soha imkon qadar qisqa bo'lsin

Ikkala usul ham bir xil natija beradi, lekin ikkinchisi 200 000 marta emas, atigi 4 marta qulflaydi.

Qoida: qulf ichida faqat umumiy ma'lumotga tegadigan kod tursin. Hisoblash, fayl o'qish, printf - bularning hammasini qulfdan tashqariga chiqaring.

Uzun kritik soha «qulf uchun kurash» (lock contention) keltirib chiqaradi: oqimlar ishlash o'rniga navbat kutadi va ko'p yadrodan foyda qolmaydi.

Atomik amallar #

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

#define OQIMLAR 4
#define QADAMLAR 100000

atomic_int hisob = 0;               /* qulfsiz, lekin xavfsiz */

void *oshir(void *arg) {
    (void) arg;

    for (int i = 0; i < QADAMLAR; i++) {
        atomic_fetch_add(&hisob, 1);
    }

    return NULL;
}

int main(void) {
    pthread_t oqimlar[OQIMLAR];

    for (int i = 0; i < OQIMLAR; i++) {
        pthread_create(&oqimlar[i], NULL, oshir, NULL);
    }

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

    printf("Kutilgan : %d\n", OQIMLAR * QADAMLAR);
    printf("Natija   : %d\n", atomic_load(&hisob));
    printf("To'g'rimi? %s\n",
           atomic_load(&hisob) == OQIMLAR * QADAMLAR ? "ha" : "yo'q");

    return 0;
}

Natija

Kutilgan : 400000
Natija   : 400000
To'g'rimi? ha

Atomik amallar mutexdan tezroq

atomic_fetch_add protsessorning maxsus buyrug'iga aylanadi. U qulf olishni, kutishni va oqim almashinuvini talab qilmaydi.

	Mutex	Atomik
Tezlik	Sekinroq	Tezroq
Nima himoyalaydi	Istalgan kod bo'lagi	Faqat bitta o'zgaruvchi
Bloklanish	Bor	Yo'q
Murakkablik	Oddiy	Chegaralangan

Bitta hisoblagich uchun - atomik. Bir necha o'zgaruvchini birga o'zgartirish kerak bo'lsa - mutex.

C11 dan beri <stdatomic.h> standart tarkibida.

Shart o'zgaruvchisi (condition variable) #

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

pthread_mutex_t qulf = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t shart = PTHREAD_COND_INITIALIZER;

int malumot_tayyor = 0;
int qiymat = 0;

void *ishlab_chiqaruvchi(void *arg) {
    (void) arg;

    pthread_mutex_lock(&qulf);

    qiymat = 42;
    malumot_tayyor = 1;
    printf("  Ishlab chiqaruvchi: ma'lumot tayyor\n");

    pthread_cond_signal(&shart);        /* kutayotganni uyg'otamiz */
    pthread_mutex_unlock(&qulf);

    return NULL;
}

void *istemolchi(void *arg) {
    (void) arg;

    pthread_mutex_lock(&qulf);

    while (!malumot_tayyor) {           /* while, if emas! */
        pthread_cond_wait(&shart, &qulf);
    }

    printf("  Iste'molchi: qiymat = %d\n", qiymat);
    pthread_mutex_unlock(&qulf);

    return NULL;
}

int main(void) {
    pthread_t ishlab, istemol;

    pthread_create(&istemol, NULL, istemolchi, NULL);
    pthread_create(&ishlab, NULL, ishlab_chiqaruvchi, NULL);

    pthread_join(ishlab, NULL);
    pthread_join(istemol, NULL);

    printf("Ikkala oqim tugadi\n");
    return 0;
}

Natija

  Ishlab chiqaruvchi: ma'lumot tayyor
  Iste'molchi: qiymat = 42
Ikkala oqim tugadi

Uyg'ongandan keyin shartni qayta tekshirish shart

if emas, while yozing

if (!malumot_tayyor) {
    pthread_cond_wait(&shart, &qulf);    /* XAVFLI */
}

Ikki sabab:

Sababsiz uyg'onish - POSIX standarti oqim hech qanday signalsiz uyg'onishi mumkinligini ochiq aytadi;
Poyga - siz uyg'onguningizcha boshqa oqim ma'lumotni olib qo'yishi mumkin.

while bilan yozsangiz, oqim uyg'onib shartni qayta tekshiradi va kerak bo'lsa yana uxlaydi. Bu har doim to'g'ri.

Ishlab chiqaruvchi va iste'molchi #

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

#define HAJM 4
#define JAMI 10

int bufer[HAJM];
int boshi = 0, oxiri = 0, soni = 0;

pthread_mutex_t qulf = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t bosh_joy_bor = PTHREAD_COND_INITIALIZER;
pthread_cond_t malumot_bor = PTHREAD_COND_INITIALIZER;

void *ishlab_chiqaruvchi(void *arg) {
    (void) arg;

    for (int i = 1; i <= JAMI; i++) {
        pthread_mutex_lock(&qulf);

        while (soni == HAJM) {
            pthread_cond_wait(&bosh_joy_bor, &qulf);
        }

        bufer[oxiri] = i;
        oxiri = (oxiri + 1) % HAJM;
        soni++;

        pthread_cond_signal(&malumot_bor);
        pthread_mutex_unlock(&qulf);
    }

    return NULL;
}

void *istemolchi(void *arg) {
    (void) arg;
    long yigindi = 0;

    for (int i = 0; i < JAMI; i++) {
        pthread_mutex_lock(&qulf);

        while (soni == 0) {
            pthread_cond_wait(&malumot_bor, &qulf);
        }

        yigindi += bufer[boshi];
        boshi = (boshi + 1) % HAJM;
        soni--;

        pthread_cond_signal(&bosh_joy_bor);
        pthread_mutex_unlock(&qulf);
    }

    printf("Iste'molchi yig'indisi: %ld\n", yigindi);
    printf("Kutilgan yig'indi     : %d\n", JAMI * (JAMI + 1) / 2);

    return NULL;
}

int main(void) {
    pthread_t ishlab, istemol;

    pthread_create(&ishlab, NULL, ishlab_chiqaruvchi, NULL);
    pthread_create(&istemol, NULL, istemolchi, NULL);

    pthread_join(ishlab, NULL);
    pthread_join(istemol, NULL);

    printf("Buferda qolgan: %d\n", soni);

    return 0;
}

Natija

Iste'molchi yig'indisi: 55
Kutilgan yig'indi     : 55
Buferda qolgan: 0

Bu naqsh hamma joyda uchraydi

Ishlab chiqaruvchi-iste'molchi (producer-consumer) - parallel dasturlashning eng muhim naqshi:

veb server: so'rovlarni qabul qiluvchi va qayta ishlovchi oqimlar;
video pleer: dekodlovchi va ekranga chiqaruvchi;
jurnal tizimi: xabar yozuvchilar va faylga saqlovchi;
| quvuri: bir dastur yozadi, ikkinchisi o'qiydi.

Ikki shart o'zgaruvchisi kerak: biri «joy bo'shadi», ikkinchisi «ma'lumot keldi» uchun.

Semafor #

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

#define OQIMLAR 5
#define BIR_VAQTDA 2

sem_t ruxsat;
pthread_mutex_t chiqish_qulfi = PTHREAD_MUTEX_INITIALIZER;
int ayni_paytda = 0;
int eng_kop = 0;

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

    sem_wait(&ruxsat);                  /* joy bo'shashini kutamiz */

    pthread_mutex_lock(&chiqish_qulfi);
    ayni_paytda++;
    if (ayni_paytda > eng_kop) {
        eng_kop = ayni_paytda;
    }
    pthread_mutex_unlock(&chiqish_qulfi);

    /* ish bajarilmoqda */
    for (volatile long i = 0; i < 1000000; i++) { }

    pthread_mutex_lock(&chiqish_qulfi);
    ayni_paytda--;
    pthread_mutex_unlock(&chiqish_qulfi);

    sem_post(&ruxsat);                  /* joyni bo'shatamiz */

    (void) raqam;
    return NULL;
}

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

    sem_init(&ruxsat, 0, BIR_VAQTDA);

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

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

    sem_destroy(&ruxsat);

    printf("Jami oqimlar        : %d\n", OQIMLAR);
    printf("Ruxsat etilgan chegara: %d\n", BIR_VAQTDA);
    printf("Eng ko'pi bilan birga : %d\n", eng_kop);
    printf("Chegara buzilmadimi?  : %s\n", eng_kop <= BIR_VAQTDA ? "ha" : "yo'q");

    return 0;
}

Natija

Jami oqimlar        : 5
Ruxsat etilgan chegara: 2
Eng ko'pi bilan birga : 2
Chegara buzilmadimi?  : ha

Mutex va semafor farqi

	Mutex	Semafor
Nechta kirishi mumkin	1 ta	N ta
Kim ochadi	Faqat egasi	Har kim
Vazifasi	O'zaro istisno	Resurs sanog'i

Mutex - hojatxona eshigi: kim kirsa, o'sha chiqadi.

Semafor - avtoturargoh: 50 ta joy bor, kirgan sari sanoq kamayadi. Kirgan mashina boshqa, chiqqani boshqa bo'lishi mumkin.

Semaforni signal berish uchun ham ishlatish mumkin: bir oqim sem_post, boshqasi sem_wait qiladi.

sem_init ning uchinchi argumenti - boshlang'ich qiymat. 1 bo'lsa, semafor mutex kabi ishlaydi (lekin egalik tekshiruvisiz).

O'qish-yozish qulfi #

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

pthread_rwlock_t qulf = PTHREAD_RWLOCK_INITIALIZER;
int umumiy_qiymat = 100;

void *oquvchi(void *arg) {
    (void) arg;

    pthread_rwlock_rdlock(&qulf);       /* bir vaqtda ko'p o'quvchi */
    int qiymat = umumiy_qiymat;
    pthread_rwlock_unlock(&qulf);

    (void) qiymat;
    return NULL;
}

void *yozuvchi(void *arg) {
    (void) arg;

    pthread_rwlock_wrlock(&qulf);       /* faqat bitta yozuvchi */
    umumiy_qiymat += 1;
    pthread_rwlock_unlock(&qulf);

    return NULL;
}

int main(void) {
    pthread_t oqimlar[10];

    for (int i = 0; i < 8; i++) {
        pthread_create(&oqimlar[i], NULL, oquvchi, NULL);
    }

    for (int i = 8; i < 10; i++) {
        pthread_create(&oqimlar[i], NULL, yozuvchi, NULL);
    }

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

    printf("Boshlang'ich qiymat : 100\n");
    printf("Ikki yozuvchidan keyin: %d\n", umumiy_qiymat);

    return 0;
}

Natija

Boshlang'ich qiymat : 100
Ikki yozuvchidan keyin: 102

Qachon rwlock foydali?

Ma'lumot ko'p o'qilib, kam yoziladigan hollarda:

sozlamalar keshi;
marshrutlar jadvali;
foydalanuvchi sessiyalari.

Oddiy mutexda o'quvchilar ham navbat kutadi. rwlock da esa barcha o'quvchilar bir vaqtda kira oladi.

Lekin ehtiyot bo'ling: rwlock mutexdan murakkabroq va sekinroq. O'qish nisbati juda yuqori bo'lmasa, oddiy mutex tezroq bo'lishi mumkin. Avval o'lchang, keyin tanlang.

Sinxronizatsiya vositalarini tanlash #

Qaysi birini ishlatish kerak?

Vaziyat	Vosita
Bitta hisoblagich	Atomik
Bir necha o'zgaruvchini birga o'zgartirish	Mutex
«Nimadir tayyor bo'lishini kutish»	Shart o'zgaruvchisi
N ta resursni cheklash	Semafor
Ko'p o'qish, kam yozish	rwlock
Umuman almashish shart emas	Hech narsa - eng yaxshisi

Oxirgi qator eng muhimi: eng tez sinxronizatsiya - umuman kerak bo'lmagani.

Har bir oqim o'z ma'lumoti bilan ishlab, natijalarni oxirida birlashtirish - ko'pincha eng tez va eng xavfsiz yechim.

Amaliy topshiriq

Oldingi bo'limdagi poyga holatini mutex bilan tuzating.
unlock ni ataylab olib tashlab, dastur qotib qolishini ko'ring.
Kritik sohani kattalashtirib, tezlik farqini o'lchang.
atomic_fetch_add bilan hisoblagichni yozing.
Mutex va atomik variantlar tezligini taqqoslang.
Shart o'zgaruvchisi bilan ikki oqimni sinxronlang.
while o'rniga if yozib, nima o'zgarishini o'ylab ko'ring.
Ishlab chiqaruvchi-iste'molchi buferini 1 ga kamaytiring.
Semafor bilan bir vaqtda 3 ta oqimga ruxsat bering.
rwlock bilan ko'p o'quvchili tizim yozing.

Xulosa #

Kritik soha - umumiy ma'lumotga tegadigan kod bo'lagi.
Mutex bir vaqtda faqat bitta oqimni kiritadi.
Har bir lock uchun aynan bitta unlock bo'lishi shart - erta qaytishlarda ehtiyot bo'ling.
Kritik soha imkon qadar qisqa bo'lsin.
Atomik amallar bitta o'zgaruvchi uchun mutexdan tezroq.
Shart o'zgaruvchisi «nimadir tayyor bo'lishini» kutish uchun.
pthread_cond_wait ni doim while sikli ichida chaqiring.
Semafor N ta resursni cheklaydi; uni har kim ochishi mumkin.
rwlock ko'p o'qish, kam yozish holatida foydali.
Eng yaxshi sinxronizatsiya - umuman kerak bo'lmagani.

Keyingi bo'limda qulflar keltirib chiqaradigan eng jiddiy muammoni - deadlock ni ko'ramiz.

Kritik soha #

Mutex - o'zaro istisno qulfi #

Kritik soha qanchalik katta bo'lsin? #

Atomik amallar #

Shart o'zgaruvchisi (condition variable) #

Ishlab chiqaruvchi va iste'molchi #

Semafor #

O'qish-yozish qulfi #

Sinxronizatsiya vositalarini tanlash #

Xulosa #

Xatolik topdingizmi?