# Ma'ruza 6. OTda ko'p vazifalilikni ta'minlash usullari. Jarayonlar, oqimlar, tolalar. Jarayonlararo aloqa. Sinxronizatsiya

> *Методы обеспечения многозадачности в ОС. Процессы, потоки, волокна. Межпроцессное взаимодействие. Синхронизация.*

---

## Ma'ruza rejasi

1. Ko'p vazifalilik: asosiy tushunchalar
2. Jarayon: model, holatlar, PCB
3. Jarayonning hayot sikli: `fork`, `exec`, `wait`, `exit`
4. Windowsda jarayonlar
5. Protsessorni rejalashtirish: mezonlar va algoritmlar
6. Linux va Windows rejalashtiruvchilari. Kontekstni almashtirish
7. Oqimlar (threads)
8. Tolalar (fibers) va korutinalar
9. Jarayonlararo aloqa: umumiy ko'rinish
10. Kanallar (pipe, FIFO) va signallar
11. Umumiy xotira, xabarlar navbati, soketlar. Windowsda IPC
12. Sinxronizatsiya: poyga holati va kritik seksiya
13. Sinxronizatsiya primitivlari
14. Sinxronizatsiyaning klassik masalalari
15. O'zaro bloklanish (deadlock)
16. Linuxda jarayonlarni kuzatish vositalari
17. Amaliy topshiriqlar, odatiy xatolar, nazorat savollari

---

# 1. Ko'p vazifalilik: asosiy tushunchalar

**Ko'p vazifalilik (multitasking)** — OTning bir nechta vazifani (dasturni) shunday bajarish xususiyatiki, protsessor bitta bo'lsa ham, ularning har biri oldinga siljiydi.

Kompyuterda bir vaqtda brauzer, muharrir, musiqa pleyeri, antivirus va o'nlab tizim xizmatlari ishlaydi. Protsessor yadrolari odatda 4–16 ta, vazifalar esa yuzlab. OT protsessorni vazifalar orasida tez almashtirib, **bir vaqtdalik illyuziyasini** yaratadi.

### Konkurentlik va parallellik

| Tushuncha | Ta'rif | Misol |
|---|---|---|
| **Konkurentlik (concurrency)** | Bir nechta vazifa bitta vaqt oralig'ida *bajarilish jarayonida* bo'ladi; bitta yadroda ular navbatlashadi | Bitta ofitsiant 5 ta stolga navbat bilan xizmat qiladi |
| **Parallellik (parallelism)** | Bir nechta vazifa turli yadrolarda *jismonan bir vaqtda bajariladi* | 5 ta ofitsiant 5 ta stolga bir vaqtda xizmat qiladi |

```
Konkurentlik (1 yadro):       Parallellik (2 yadro):
CPU0: A A B B A C C B A       CPU0: A A A A A A
                              CPU1: B B B B B B
```

Parallellik bir nechta yadrosiz mumkin emas, konkurentlik esa bitta yadroda ham mumkin.

### Tarixiy rivojlanish

| Bosqich | G'oya | Hal qiladigan muammo |
|---|---|---|
| **Paketli ishlov berish** | Vazifalar qat'iy navbat bilan bajariladi | Dasturlarni qo'lda yuklash |
| **Multidasturlash** | Xotirada bir nechta dastur; biri kiritish-chiqarishni kutayotganda boshqasi bajariladi | I/O amallarida protsessorning bekor turishi |
| **Vaqtni taqsimlash (time sharing)** | Har bir vazifaga qisqa **vaqt kvanti** beriladi | Interaktivlik: terminallarda ko'plab foydalanuvchilar |
| **Ko'p protsessorlilik / ko'p yadrolilik** | Haqiqiy parallellik | Chastotani oshirmasdan unumdorlikni oshirish |

### Kooperativ va siqib chiqaruvchi ko'p vazifalilik

* **Kooperativ (non-preemptive)** — vazifa protsessorni o'zi bo'shatadi (`yield` ni chaqiradi yoki I/O da bloklanadi). Agar dastur cheksiz siklga tushsa, butun tizim "qotib qoladi". Windows 3.x va 9-versiyagacha bo'lgan Mac OS shunday ishlagan.
* **Siqib chiqaruvchi (preemptive)** — vaqt kvanti tugaganda OT protsessorni **taymer uzilishi** orqali o'zi tortib oladi. Hech bir dastur CPU ni egallab ola olmaydi. Barcha zamonaviy OTlar shunday ishlaydi: Linux, Windows NT va undan keyingilari, macOS.

> **Asosiy g'oya:** siqib chiqarish apparat taymeri tufayli mumkin. U davriy ravishda uzilish hosil qiladi, boshqaruv yadroga o'tadi va rejalashtiruvchi protsessorni keyin kimga berishni hal qiladi.

### Protsessor va kiritish-chiqarish bilan chegaralangan vazifalar

* **CPU-bound** — vaqtining katta qismini hisoblashga sarflaydi (videoni siqish, kompilyatsiya). Uzun CPU "portlashlari".
* **I/O-bound** — vaqtining katta qismida disk, tarmoq yoki foydalanuvchini kutadi (matn muharriri, veb-server). Qisqa CPU portlashlari.

Har qanday jarayonning hayoti — **CPU burst** (protsessorda ishlash) va **I/O burst** (kiritish-chiqarishni kutish) navbatlashuvidan iborat. Yaxshi rejalashtiruvchi I/O-bound vazifalarga ustuvorlik beradi: ular CPU ni tez bo'shatadi, foydalanuvchi esa tez javob oladi.

---

# 2. Jarayon: model, holatlar, PCB

**Jarayon (process)** — bu bajarilish holatidagi dastur va OT unga ajratgan barcha resurslar: manzil maydoni, ochiq fayllar, hisob ma'lumotlari, registrlar holati.

**Dastur** — diskdagi passiv fayl (`/usr/bin/python3`). **Jarayon** — faol mohiyat. Bitta dasturdan ko'p jarayon ishga tushirish mumkin: uchta terminal oynasi — bu `bash` ning uchta jarayoni.

### Jarayonning manzil maydoni

```
Yuqori manzillar
┌──────────────────────────┐
│ Stek (stack)        ↓    │  lokal o'zgaruvchilar, qaytish manzillari
│                          │
│         (bo'sh)          │
│                          │
│ Uyum (heap)         ↑    │  malloc / new
├──────────────────────────┤
│ BSS                      │  initsializatsiyalanmagan global o'zgaruvchilar
│ Data                     │  initsializatsiyalangan global o'zgaruvchilar
│ Text (kod)               │  mashina ko'rsatmalari, faqat o'qish
└──────────────────────────┘
Quyi manzillar
```

Har bir jarayonning **o'z virtual manzil maydoni** bor. A jarayondagi `0x601040` manzili va B jarayondagi xuddi shu manzil **turli** jismoniy kataklarni ko'rsatadi. Shuning uchun jarayonlar izolyatsiyalangan: birining xatosi boshqasining xotirasini buzmaydi.

### Jarayon holatlari modeli (5 holat)

```
          admit                      dispatch
  ┌─────┐ ─────▶ ┌───────┐ ──────────────────▶ ┌─────────┐  exit   ┌────────────┐
  │ New │        │ Ready │                     │ Running │ ──────▶ │ Terminated │
  └─────┘        └───────┘ ◀────────────────── └─────────┘         └────────────┘
                     ▲      interrupt (kvant tugadi)  │
                     │                                │ I/O yoki hodisani kutish
                     │      I/O tugadi          ┌─────▼────┐
                     └───────────────────────── │ Waiting  │
                                                └──────────┘
```

| Holat | Tavsif |
|---|---|
| **New (yangi)** | Jarayon yaratilmoqda, OT tuzilmalarni ajratmoqda |
| **Ready (tayyor)** | Jarayon bajarilishga tayyor va faqat protsessorni kutmoqda |
| **Running (bajarilmoqda)** | Jarayon ko'rsatmalari CPU da bajarilmoqda |
| **Waiting / Blocked (kutish)** | Jarayon hodisani kutmoqda: I/O tugashi, signal, myuteksning bo'shashi |
| **Terminated (tugagan)** | Jarayon ishini tugatdi, OT resurslarni bo'shatmoqda |

O'tishlarni tushunish muhim:

* **Running → Ready** — jarayon siqib chiqarildi (kvant tugadi yoki ustuvorroq jarayon paydo bo'ldi). U ishlashni *davom ettirishi mumkin edi*.
* **Running → Waiting** — jarayonning o'zi davom eta olmaydi: u ma'lumotlarni kutmoqda.
* **Waiting → Running** to'g'ridan-to'g'ri **mumkin emas**: I/O tugagach, jarayon avval Ready navbatiga tushadi.

Bitta yadroda har bir lahzada Running holatida **ko'pi bilan bitta** jarayon bo'ladi.

### Linuxda jarayon holatlari

`ps` buyrug'i holatni `STAT` ustunida ko'rsatadi:

| Kod | Ma'nosi |
|---|---|
| `R` | Running yoki Runnable (bajarilmoqda yoki tayyor) |
| `S` | Interruptible sleep — signal bilan to'xtatish mumkin bo'lgan kutish |
| `D` | Uninterruptible sleep — I/O ni kutish, signal bilan to'xtatilmaydi |
| `T` | Stopped — to'xtatilgan (Ctrl+Z, `SIGSTOP`) |
| `Z` | Zombie — tugagan, lekin ota-jarayon qaytish kodini o'qimagan |

Linux Ready va Running ni farqlamaydi: ikkalasi ham `R` bilan belgilanadi.

### Jarayonni boshqarish bloki (PCB)

**PCB (Process Control Block)** — yadroning ma'lumotlar tuzilmasi bo'lib, unda OT jarayon haqida biladigan hamma narsa saqlanadi. Linuxda bu `struct task_struct`, Windowsda — `EPROCESS` / `KPROCESS`.

| PCB maydoni | Misol |
|---|---|
| Identifikator | PID, PPID (ota-jarayon PID i) |
| Holat | Ready, Running, Waiting... |
| CPU konteksti | Buyruqlar hisoblagichi (PC), registrlar, stek ko'rsatkichi |
| Rejalashtirish | Ustuvorlik, nice, sarflangan CPU vaqti |
| Xotira | Sahifalar jadvallari, segment chegaralari |
| Fayllar | Ochiq fayl deskriptorlari jadvali |
| Xavfsizlik | UID, GID, capabilities |
| Hisob | Boshlanish vaqti, sarflangan CPU vaqti |

Linuxda PCB ning bir qismi `/proc` psevdo fayl tizimi orqali ko'rinadi:

```bash
cat /proc/$$/status | head -12     # $$ — joriy qobiqning PID i
ls -l /proc/$$/fd                   # ochiq fayl deskriptorlari
cat /proc/$$/stat | awk '{print $3}'   # holat (R, S, ...)
```

---

# 3. Jarayonning hayot sikli: `fork`, `exec`, `wait`, `exit`

Unix-ga o'xshash OTlarda jarayon yaratish ikki qadamga bo'lingan:

1. **`fork()`** — joriy jarayonning **nusxasini** yaratish.
2. **`exec()`** — shu jarayondagi dasturni boshqasiga almashtirish.

### `fork()` — bitta funksiya, ikkita qaytish

`fork()` bir marta chaqiriladi, lekin boshqaruvni **ikki marta** qaytaradi: ota-jarayonda va bola-jarayonda.

| Qayerda | `fork()` qaytaradigan qiymat |
|---|---|
| Ota-jarayonda | Yaratilgan bola-jarayonning PID i (> 0) |
| Bola-jarayonda | 0 |
| Xatoda (ota-jarayonda) | −1, bola-jarayon yaratilmagan |

```c
// gcc fork1.c -o fork1
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    int x = 5;
    pid_t pid = fork();
    if (pid == -1) { perror("fork"); return 1; }

    if (pid == 0) {                       // bola-jarayon
        x += 10;
        printf("child:  PID=%d PPID=%d x=%d\n", getpid(), getppid(), x);
        exit(0);
    }
    wait(NULL);                           // ota-jarayon bolani kutadi
    printf("parent: PID=%d child=%d x=%d\n", getpid(), pid, x);
    return 0;
}
```

Natija (PID lar boshqacha bo'ladi):

```
child:  PID=4312 PPID=4311 x=15
parent: PID=4311 child=4312 x=5
```

> **Muhim:** ota-jarayonda `x` 5 ga tengligicha qoldi. `fork()` dan keyin bola-jarayonda xotiraning **o'z nusxasi** bo'ladi. Bir jarayondagi o'zgarishlar boshqasida ko'rinmaydi.

### Copy-on-Write (COW)

Har bir `fork()` da gigabaytlab xotirani nusxalash juda sekin bo'lar edi. Shuning uchun yadro **yozishda nusxalash** usulidan foydalanadi: `fork()` dan keyin ota va bola bir xil jismoniy sahifalarni "faqat o'qish" belgisi bilan birgalikda ishlatadi. Sahifaning haqiqiy nusxasi faqat jarayonlardan biri uni **o'zgartirmoqchi** bo'lganda yaratiladi. Agar bola-jarayon darhol `exec()` ni chaqirsa, deyarli hech narsa nusxalanmaydi.

### Bir nechta `fork()` da jarayonlarni sanash

Har bir `fork()` uni bajarayotgan jarayonlar sonini ikki baravar oshiradi.

```c
fork();
fork();
fork();
printf("salom\n");
```

```
                 P0
        fork1 ┌──┴──┐
              P0    P1
     fork2 ┌──┴┐   ┌┴──┐
           P0  P2  P1  P3
   fork3  ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
          P0 P4 P2 P5 P1 P6 P3 P7      → 2³ = 8 jarayon, 8 ta "salom" satri
```

Umumiy formula: `n` ta ketma-ket `fork()` dan keyin **2ⁿ jarayon** hosil bo'ladi (ulardan 2ⁿ − 1 tasi yangi).

Mantiqiy operatorli murakkabroq holat. `&&` va `||` operatorlari o'ng qismini **har doim ham** hisoblamaydi:

```c
if (fork() && fork())   // ikkinchi fork ni faqat OTA bajaradi (u yerda birinchi fork() != 0)
    fork();
printf("x\n");          // natija: 4 jarayon
```

> **Buferlash tuzog'i:** `printf` `stdout` buferiga yozadi. Agar chiqish faylga yoki kanalga yo'naltirilgan bo'lsa, bufer `\n` da tozalanmaydi va `fork()` da **xotira bilan birga nusxalanadi** — satrlar bir necha marta chop etiladi. `fork()` dan oldin `fflush(stdout)` ni chaqiring yoki buferlashni o'chiring: `setvbuf(stdout, NULL, _IONBF, 0)`.

### `exec()` — boshqa dasturni ishga tushirish

`exec` funksiyalar oilasi (`execl`, `execv`, `execvp`, `execve`...) jarayonning kodi, ma'lumotlari va stekini yangi dastur bilan **almashtiradi**. PID **saqlanadi**, ochiq fayl deskriptorlari ham (`FD_CLOEXEC` bayrog'isiz bo'lsa). Muvaffaqiyatli bo'lsa, `exec` **qaytmaydi**.

```c
pid_t pid = fork();
if (pid == 0) {
    execlp("ls", "ls", "-l", "/tmp", (char *)NULL);
    perror("execlp");          // faqat exec muvaffaqiyatsiz bo'lsa bajariladi
    _exit(127);
}
int status;
waitpid(pid, &status, 0);
if (WIFEXITED(status))
    printf("ls exited %d\n", WEXITSTATUS(status));
```

`bash` qobig'i har bir buyruqni aynan shunday ishga tushiradi: `fork()` → bola-jarayonda `exec()` → ota-jarayonda `wait()`.

```
bash ──fork()──▶ bash (nusxa) ──exec("ls")──▶ ls ──exit(0)──▶ zombie
  │                                                              │
  └──────────────────── waitpid() ◀──────────────────────────────┘
                     (bash qaytish kodini oladi, zombi yo'qoladi)
```

### `exit()` va `wait()`: zombilar va yetimlar

* **`exit(code)`** jarayonni yakunlaydi. Yadro xotira va fayllarni bo'shatadi, lekin ota-jarayon o'qimaguncha qaytish kodi bilan **jarayonlar jadvalidagi yozuvni saqlaydi**.
* **`wait()` / `waitpid()`** — ota-jarayon bolaning tugashini kutadi va uning qaytish kodini oladi.

| Vaziyat | Nomi | Nima sodir bo'ladi |
|---|---|---|
| Bola tugadi, ota hali `wait` ni chaqirmagan | **Zombi (zombie, `Z`)** | Jarayonlar jadvalida faqat yozuv qoladi (PID va qaytish kodi). Zombi CPU va xotirani iste'mol qilmaydi, lekin PID ni egallaydi |
| Ota-jarayon boladan oldin tugadi | **Yetim (orphan)** | Bolani `init` / `systemd` jarayoni (PID 1) yoki tayinlangan subreaper "asrab oladi"; u o'zi `wait` ni chaqiradi |

> Bitta zombi zararsiz. Lekin server minglab bola-jarayon yaratib, `wait` ni chaqirmasa, jarayonlar jadvali to'ladi va yangi jarayon yaratib bo'lmaydi. Zombini `kill` buyrug'i bilan **o'ldirib bo'lmaydi**: u allaqachon o'lgan. Ota-jarayon `wait` ni chaqirishi yoki ota-jarayonni yakunlash kerak — shunda zombini `init` asrab oladi va tozalaydi.

### Jarayonlar daraxti

Har bir jarayonning (PID 1 dan tashqari) ota-jarayoni bor. Barcha jarayonlar ildizi `systemd` (PID 1) bo'lgan daraxtni hosil qiladi:

```bash
pstree -p | head -20
ps -eo pid,ppid,stat,cmd --forest | head -20
```

---

# 4. Windowsda jarayonlar

Windowsda `fork()` yo'q. Jarayon ko'rsatilgan dasturni darhol yuklaydigan bitta **`CreateProcess`** funksiyasi bilan yaratiladi:

```c
STARTUPINFO si = { sizeof(si) };
PROCESS_INFORMATION pi;
if (CreateProcess(L"C:\\Windows\\System32\\notepad.exe", NULL, NULL, NULL,
                  FALSE, 0, NULL, NULL, &si, &pi)) {
    WaitForSingleObject(pi.hProcess, INFINITE);   // waitpid analogi
    DWORD code;
    GetExitCodeProcess(pi.hProcess, &code);
    CloseHandle(pi.hThread);
    CloseHandle(pi.hProcess);
}
```

| Jihat | Linux / POSIX | Windows |
|---|---|---|
| Yaratish | `fork()` + `exec()` | `CreateProcess()` (bir qadam) |
| Kutish | `wait()`, `waitpid()` | `WaitForSingleObject(hProcess)` |
| Identifikatsiya | PID (son) | PID + **deskriptor (HANDLE)** |
| Ierarxiya | Qat'iy daraxt, PPID muhim | Ota eslab qolinadi, lekin ierarxiya zaif |
| Zombilar | Ota `wait` ni chaqirmaguncha bor | Jarayon obyekti kamida bitta HANDLE ochiq ekan yashaydi |
| Guruhlash | Jarayon guruhlari, sessiyalar, cgroups | **Job objects** (guruh uchun CPU, xotira cheklovlari) |
| Rejalashtirishning minimal birligi | Oqim (task) | Oqim |

Windowsda jarayonlarni ko'rish: Vazifalar dispetcheri, `tasklist`, PowerShell da `Get-Process`, Process Explorer (Sysinternals).

```powershell
Get-Process | Sort-Object CPU -Descending | Select-Object -First 5
tasklist /FI "IMAGENAME eq notepad.exe"
taskkill /PID 4312 /F
```

---

# 5. Protsessorni rejalashtirish: mezonlar va algoritmlar

**Rejalashtiruvchi (scheduler)** — Ready navbatidagi qaysi jarayon protsessorni olishini tanlaydigan yadro komponenti. **Dispetcher (dispatcher)** almashtirishning o'zini bajaradi.

### Qaror qachon qabul qilinadi

1. Jarayon Running dan Waiting ga o'tadi (I/O so'rovi).
2. Jarayon Running dan Ready ga o'tadi (taymer uzilishi).
3. Jarayon Waiting dan Ready ga o'tadi (I/O tugadi).
4. Jarayon tugaydi.

Agar qarorlar faqat 1 va 4 holatlarda qabul qilinsa — rejalashtirish **siqib chiqarmaydigan**. Agar 2 va 3 da ham — **siqib chiqaruvchi**.

### Sifat mezonlari

| Mezon | Ta'rif | Maqsad |
|---|---|---|
| CPU bandligi (utilization) | CPU band bo'lgan vaqt ulushi | ↑ max |
| O'tkazish qobiliyati (throughput) | Vaqt birligida tugallangan jarayonlar soni | ↑ max |
| **Aylanish vaqti (turnaround time)** | Tugash − Kelish | ↓ min |
| **Kutish vaqti (waiting time)** | Ready navbatidagi vaqt = Aylanish − CPU davomiyligi | ↓ min |
| Javob vaqti (response time) | Birinchi ishga tushish − Kelish | ↓ min |

### Rejalashtirish algoritmlari

| Algoritm | Tamoyil | Siqib chiqaruvchimi? | Afzalliklari | Kamchiliklari |
|---|---|---|---|---|
| **FCFS** (First Come, First Served) | Kim oldin kelsa, o'sha oldin bajariladi | Yo'q | Oddiy, tartib bo'yicha adolatli | **Karvon effekti**: qisqa vazifalar uzunining orqasida kutadi |
| **SJF** (Shortest Job First) | Eng qisqa CPU burst li vazifa tanlanadi | Yo'q | Minimal o'rtacha kutish vaqti (siqib chiqarmaydiganlar orasida) | Davomiylik oldindan noma'lum; uzun vazifalar ochligi |
| **SRTF** (Shortest Remaining Time First) | Siqib chiqaruvchi SJF: yangi qisqa vazifa joriysini siqib chiqaradi | Ha | Umuman minimal o'rtacha kutish | Tez-tez almashtirish, ochlik |
| **Ustuvorlik bo'yicha** | Eng yuqori ustuvorlikdagi vazifa bajariladi | Ikkala variant | Muhim vazifalar tezroq | Past ustuvorliklilar ochligi → yechim: **qarish (aging)** |
| **RR** (Round Robin) | Aylana navbat, har biriga `q` kvant | Ha | Yaxshi javob vaqti, ochlik yo'q | Katta o'rtacha aylanish vaqti; sifat `q` ga bog'liq |
| **MLFQ** (teskari aloqali ko'p darajali navbat) | Turli ustuvorlikdagi bir nechta navbat; kvantini sarflagan vazifa pastga tushadi | Ha | I/O-bound vazifalarni o'zi ajratadi | Sozlash murakkab |

### Yechilgan misol

To'rtta jarayon (vaqt millisekundlarda):

| Jarayon | Kelish | CPU burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |

**FCFS:**

```
| P1      | P2  | P3        | P4    |
0         8     12          21      26
```

Kutish: P1 = 0, P2 = 8 − 1 = 7, P3 = 12 − 2 = 10, P4 = 21 − 3 = 18.
**O'rtacha kutish = (0 + 7 + 10 + 18) / 4 = 8,75 ms.**

**SJF (siqib chiqarmaydigan):** 0 vaqtda faqat P1 bor — u oxirigacha bajariladi. 8 vaqtda tayyorlar orasidan eng qisqasini tanlaymiz: P2 (4), keyin P4 (5), keyin P3 (9).

```
| P1      | P2  | P4    | P3        |
0         8     12      17          26
```

Kutish: P1 = 0, P2 = 7, P4 = 12 − 3 = 9, P3 = 17 − 2 = 15. **O'rtacha = 31 / 4 = 7,75 ms.**

**SRTF (siqib chiqaruvchi):** 1 vaqtda P2 (4) keladi — P1 da 7 > 4 qolgan, P1 siqib chiqariladi.

```
|P1| P2  | P4    | P1      | P3        |
0  1     5       10        17          26
```

Kutish = Aylanish − Burst: P1 = (17 − 0) − 8 = 9, P2 = (5 − 1) − 4 = 0, P4 = (10 − 3) − 5 = 2, P3 = (26 − 2) − 9 = 15. **O'rtacha = 26 / 4 = 6,5 ms.**

**RR, kvant q = 4:**

```
| P1  | P2  | P3  | P4  | P1  | P3  |P4| P3 |
0     4     8     12    16    20    24 25   26
```

Kutish: P1 = 20 − 8 − 0 = 12, P2 = 8 − 4 − 1 = 3, P3 = 26 − 9 − 2 = 15, P4 = 25 − 5 − 3 = 17. **O'rtacha = 47 / 4 = 11,75 ms.**

| Algoritm | O'rtacha kutish | O'rtacha aylanish vaqti |
|---|---|---|
| FCFS | 8,75 | 15,25 |
| SJF | 7,75 | 14,25 |
| **SRTF** | **6,5** | **13,0** |
| RR (q = 4) | 11,75 | 18,25 |

> **Xulosa:** SRTF minimal o'rtacha kutishni beradi, lekin kelajakni bilishni talab qiladi. RR o'rtacha kutishda yutqazadi, ammo hech bir vazifa keyingi kvantigacha `(n − 1) · q` dan ko'p kutmaydi — interaktiv tizimlarga aynan shu kerak.

### RR uchun kvantni tanlash

* Kvant **juda katta** → RR FCFS ga aylanadi, javob yomonlashadi.
* Kvant **juda kichik** → vaqtning katta qismi kontekstni almashtirishga ketadi.
* Amaliyot: kvant kontekstni almashtirish vaqtidan (mikrosekundlar birligi) sezilarli katta bo'lishi kerak; odatiy qiymatlar — 1 dan 100 ms gacha.

---

# 6. Linux va Windows rejalashtiruvchilari. Kontekstni almashtirish

### Linux: CFS va EEVDF

* 2007-yildan (yadro 2.6.23) Linuxda **CFS (Completely Fair Scheduler)** ishlagan. U har bir vazifa uchun **virtual bajarilish vaqtini** (`vruntime`) saqlaydi va har doim eng kichik `vruntime` li vazifani tanlaydi (tayyor vazifalar qizil-qora daraxtda saqlanadi).
* **6.6** yadrosidan (2023) asosiy algoritm **EEVDF** (Earliest Eligible Virtual Deadline First) bo'ldi. U CPU ni adolatli taqsimlash g'oyasini saqlaydi, lekin kechikish talablarini yaxshiroq hisobga oladi.
* Oddiy vazifalarning ustuvorligi **nice** qiymati bilan −20 (eng yuqori) dan +19 (eng past) gacha beriladi. Ustuvorlikni oshirishni (nice ni kamaytirishni) faqat root qila oladi.
* Real vaqt vazifalari uchun 1–99 ustuvorlikli `SCHED_FIFO` va `SCHED_RR` siyosatlari bor. Ular har doim oddiy vazifalarni siqib chiqaradi.

```bash
nice -n 10 ./long_job          # pasaytirilgan ustuvorlik bilan ishga tushirish
renice -n 5 -p 4312            # ishlayotgan jarayonning nice qiymatini o'zgartirish
chrt -p 4312                   # rejalashtirish siyosatini ko'rsatish
ps -eo pid,ni,pri,cls,cmd | head
taskset -c 0 ./job             # jarayonni 0-yadroga bog'lash (CPU affinity)
```

### Windows

Windows **oqimlarni** **32 ta ustuvorlik darajasi** bo'yicha rejalashtiradi: 0 — sahifalarni nollash oqimi, 1–15 — dinamik (oddiy), 16–31 — real vaqt. Har bir daraja ichida siqib chiqaruvchi RR ishlatiladi. Klaviatura kiritishini kutib olgan oqim yoki faol oyna oqimi **ustuvorlikni vaqtincha oshirishni (priority boost)** oladi.

```powershell
Start-Process notepad -PassThru | ForEach-Object { $_.PriorityClass = 'BelowNormal' }
```

### Kontekstni almashtirish (context switch)

**Kontekstni almashtirish** — joriy jarayon (oqim) holatini uning PCB siga saqlash va keyingisining holatini yuklash.

```
A jarayon                Yadro                      B jarayon
  bajarilmoqda
     │  taymer uzilishi
     └──────────▶ A registrlarini PCB(A) ga saqlash
                  rejalashtiruvchi: B ni tanlash
                  registrlarni PCB(B) dan yuklash
                  (jarayon almashsa — sahifa jadvallarini almashtirish)
                                  └──────────▶ bajarilmoqda
```

Almashtirish — bu **qo'shimcha xarajat**: bu vaqtda foydali ish bajarilmaydi. Bundan tashqari, almashtirishdan keyin protsessor keshlari va TLB "soviydi". **Bitta jarayon oqimlari** orasida almashtirish jarayonlar orasidagidan arzonroq: sahifa jadvallarini almashtirish kerak emas.

```bash
grep ctxt /proc/stat                         # yuklanishdan beri jami almashtirishlar
grep ctxt_switches /proc/$$/status           # jarayon uchun voluntary / nonvoluntary
vmstat 1 5                                   # cs ustuni — sekundiga almashtirishlar
```

* **Ixtiyoriy (voluntary)** — jarayon o'zi bloklandi (I/O ni kutmoqda).
* **Majburiy (nonvoluntary)** — jarayon siqib chiqarildi (kvant tugadi).

---

# 7. Oqimlar (threads)

**Oqim (thread)** — jarayon ichidagi bajarilish birligi: o'z registrlari va steki bo'lgan alohida ko'rsatmalar ketma-ketligi. Jarayonning barcha oqimlari **umumiy manzil maydonida** ishlaydi.

### Nima umumiy, nima o'ziniki

| Jarayonning barcha oqimlari uchun umumiy | Har bir oqimning o'ziniki |
|---|---|
| Kod (text) | Buyruqlar hisoblagichi (PC) |
| Global o'zgaruvchilar, uyum | Registrlar |
| Ochiq fayllar va soketlar | Stek |
| PID, hisob ma'lumotlari (UID) | Oqim identifikatori (TID) |
| Signal ishlovchilari | Signal maskasi, `errno` |
| | Thread-Local Storage (TLS) |

```
         Jarayon (bitta manzil maydoni)
┌───────────────────────────────────────────────────┐
│  Kod  │  Global ma'lumotlar │  Uyum  │  Fayllar   │
├───────────────┬───────────────┬───────────────────┤
│  1-oqim       │  2-oqim       │  3-oqim           │
│  registr, PC  │  registr, PC  │  registr, PC      │
│  stek         │  stek         │  stek             │
└───────────────┴───────────────┴───────────────────┘
```

### Oqimlar nima uchun kerak

1. **Javob berish tezligi** — ishchi oqim fayl yuklayotganda GUI oqimi foydalanuvchiga javob beradi.
2. **Resurslarni bo'lishish** — oqimlar umumiy ma'lumotlarni darhol ko'radi, IPC kerak emas.
3. **Tejamkorlik** — oqim yaratish va oqimlar orasida almashtirish jarayonlarnikiga qaraganda arzon.
4. **Masshtablash** — bitta jarayon oqimlari turli yadrolarda parallel bajariladi.

Bu afzalliklarning narxi — **izolyatsiya yo'q**: bitta oqimdagi xato (masalan, noto'g'ri ko'rsatkich bo'yicha murojaat) butun jarayonni tugatadi, umumiy ma'lumotlarga bir vaqtda kirish esa **sinxronizatsiyani** talab qiladi (12–13-bo'limlar).

### Jarayonmi yoki oqimmi?

| Mezon | Jarayon | Oqim |
|---|---|---|
| Manzil maydoni | O'ziniki | Jarayonning boshqa oqimlari bilan umumiy |
| Yaratish narxi | Yuqori | Past |
| Almashtirish | Qimmatroq (sahifa jadvallarini almashtirish) | Arzonroq |
| Ma'lumot almashish | IPC orqali | Umumiy xotira orqali to'g'ridan-to'g'ri |
| Xatoda izolyatsiya | Birining xatosi boshqalarga ta'sir qilmaydi | Xato butun jarayonni o'ldiradi |
| Misol | Chrome yorliqlari — alohida jarayonlar | So'rovlarga ishlov beradigan veb-server oqimlari |

### Oqimlarni amalga oshirish modellari

| Model | Tavsif | Afzalliklari | Kamchiliklari | Misol |
|---|---|---|---|---|
| **N:1** (foydalanuvchi darajasidagi oqimlar) | Jarayonning barcha oqimlari bitta yadro oqimiga akslanadi; kutubxona almashtiradi | Juda tez almashtirish | Bloklovchi tizim chaqiruvi **barcha** oqimlarni to'xtatadi; parallellik yo'q | Javadagi dastlabki Green threads |
| **1:1** (yadro darajasidagi oqimlar) | Har bir foydalanuvchi oqimi — alohida yadro oqimi | Haqiqiy parallellik; birining bloklanishi boshqalarga xalaqit bermaydi | Yaratish qimmatroq; yadro har bir oqimni biladi | Linux NPTL, Windows |
| **M:N** (gibrid) | M ta foydalanuvchi oqimi N ta yadro oqimida | Afzalliklarni birlashtiradi | Murakkab amalga oshirish | Go gorutinalari, Java 21 virtual oqimlari |

### Linuxda oqimlar

Linux yadrosida alohida "oqim" tushunchasi yo'q: jarayon ham, oqim ham — `task_struct` bilan tavsiflanadigan **vazifa (task)**. Farq vazifa ota bilan qaysi resurslarni **bo'lishishida**. Buni `clone()` tizim chaqiruvi bayroqlari belgilaydi:

```
fork()            ≈ clone(SIGCHLD)                            — hech narsani bo'lishmaydi
pthread_create()  ≈ clone(CLONE_VM | CLONE_FS | CLONE_FILES |
                          CLONE_SIGHAND | CLONE_THREAD | ...)  — deyarli hammasini bo'lishadi
```

Bitta jarayon oqimlarining **PID** i bir xil (yadroda bu TGID — oqimlar guruhi identifikatori), lekin **TID** lari har xil.

```bash
ps -eLf | head                  # LWP — oqim identifikatori (TID), NLWP — oqimlar soni
ls /proc/<PID>/task             # har bir oqim — alohida katalog
top -H -p <PID>                 # top da jarayon oqimlari
```

### POSIX Threads (pthreads)

```c
// gcc threads.c -o threads -pthread
#include <pthread.h>
#include <stdio.h>

void *worker(void *arg) {
    int id = *(int *)arg;
    printf("worker %d started\n", id);
    return NULL;
}

int main(void) {
    pthread_t t[3];
    int ids[3] = {1, 2, 3};
    for (int i = 0; i < 3; i++)
        pthread_create(&t[i], NULL, worker, &ids[i]);
    for (int i = 0; i < 3; i++)
        pthread_join(t[i], NULL);       // tugashini kutamiz, jarayonlar uchun wait() kabi
    printf("all done\n");
    return 0;
}
```

| Funksiya | Vazifasi |
|---|---|
| `pthread_create` | Oqim yaratish |
| `pthread_join` | Oqim tugashini kutish va natijani olish |
| `pthread_detach` | Oqimni "ajratish": resurslar o'zi bo'shaydi, `join` kerak emas |
| `pthread_exit` | Joriy oqimni tugatish |
| `pthread_self` | Joriy oqim identifikatori |

> `worker 1/2/3 started` satrlarining tartibi **aniqlanmagan**: uni rejalashtiruvchi tanlaydi. Sinxronizatsiyasiz ma'lum tartibga tayanadigan dastur xatoga ega.

### Windowsda oqimlar

```c
DWORD WINAPI Worker(LPVOID arg) { /* ... */ return 0; }

HANDLE h = CreateThread(NULL, 0, Worker, NULL, 0, NULL);
WaitForSingleObject(h, INFINITE);    // pthread_join analogi
CloseHandle(h);
```

Ko'p sonli qisqa vazifalar uchun Linuxda ham, Windowsda ham **oqimlar hovuzidan (thread pool)** foydalaniladi: oldindan bir nechta oqim yaratiladi va ular umumiy navbatdan vazifa oladi. Shunda har bir so'rov uchun oqim yaratib, yo'q qilishga to'g'ri kelmaydi.

---

# 8. Tolalar (fibers) va korutinalar

**Tola (fiber)** — yadro emas, **dasturning o'zi** boshqaradigan "yengillashtirilgan oqim". Tolalar oddiy oqim ichida bajariladi va **kooperativ** almashtiriladi: tola boshqaruvni boshqa tolaga aniq beradi.

```
Yadro oqimi (OT rejalashtiruvchisi ko'radi)
└── A tola ──yield──▶ B tola ──yield──▶ C tola ──yield──▶ A tola ...
    (almashtirish — foydalanuvchi maydonida, tizim chaqiruvisiz)
```

| Xususiyat | Oqim (thread) | Tola (fiber) |
|---|---|---|
| Kim rejalashtiradi | OT yadrosi | Dastur (kutubxona) |
| Ko'p vazifalilik turi | Siqib chiqaruvchi | Kooperativ |
| Almashtirish narxi | Tizim chaqiruvi, mikrosekundlar | Bir nechta registrni saqlash, nanosekundlar |
| Parallellik | Ha, turli yadrolarda | Bitta oqim ichida yo'q |
| Bloklovchi chaqiruv | Bitta oqimni bloklaydi | Shu oqimdagi **barcha** tolalarni bloklaydi |
| Soni | Minglab | Yuz minglab va millionlab |

### Windowsda tolalar

```c
LPVOID mainFiber, f1;

VOID CALLBACK FiberFunc(LPVOID arg) {
    printf("fiber: step 1\n");
    SwitchToFiber(mainFiber);          // boshqaruvni aniq berish
    printf("fiber: step 2\n");
    SwitchToFiber(mainFiber);
}

int main(void) {
    mainFiber = ConvertThreadToFiber(NULL);
    f1 = CreateFiber(0, FiberFunc, NULL);
    SwitchToFiber(f1);                 // → "fiber: step 1"
    SwitchToFiber(f1);                 // → "fiber: step 2"
    DeleteFiber(f1);
    return 0;
}
```

POSIX da shunga o'xshash mexanizm — `getcontext` / `makecontext` / `swapcontext` funksiyalari (`<ucontext.h>`). Ular eskirgan deb e'lon qilingan, lekin glibc da hamon ishlaydi.

### Korutinalar va zamonaviy tillar

**Korutina (coroutine)** — bajarilishini to'xtatib, keyinroq o'sha joydan davom ettira oladigan funksiya. Bu til darajasidagi o'sha kooperativ ko'p vazifalilik g'oyasi:

* Python, C#, JavaScript, Rust dagi `async` / `await`;
* Go gorutinalari (M:N modeli, runtime ularni OT oqimlariga o'zi taqsimlaydi);
* Java 21 virtual oqimlari (Project Loom).

Tolalar va korutinalar juda ko'p bir vaqtdagi ulanishlarga ega serverlar uchun yaxshi mos keladi, bu yerda vazifalar asosan **tarmoqni kutadi**: har bir ulanish uchun yadro oqimini ushlab turish juda qimmat.

### Bajarilish birliklarini taqqoslash

| | Jarayon | Oqim | Tola / korutina |
|---|---|---|---|
| Xotira izolyatsiyasi | Ha | Yo'q | Yo'q |
| Kim rejalashtiradi | OT | OT | Dastur |
| Siqib chiqarish | Ha | Ha | Yo'q (kooperativ) |
| Parallellik | Ha | Ha | Faqat bir nechta oqim orqali |
| Narx | Yuqori | O'rta | Past |

---

# 9. Jarayonlararo aloqa: umumiy ko'rinish

Jarayonlar izolyatsiyalangan: biri boshqasining xotirasini o'qiy olmaydi. Lekin ular ma'lumot almashishi kerak: qobiq `ls` chiqishini `grep` ga uzatadi, brauzer yorliq jarayoni bilan muloqot qiladi, veb-server — ma'lumotlar bazasi bilan. Buning uchun OT **jarayonlararo aloqa (IPC, Inter-Process Communication)** mexanizmlarini taqdim etadi.

Ikkita asosiy model mavjud:

```
  Xabar uzatish                         Umumiy xotira
┌──────┐  send   ┌──────┐            ┌──────┐          ┌──────┐
│  A   │ ──────▶ │yadro │            │  A   │          │  B   │
└──────┘         │bufer │            └──┬───┘          └───┬──┘
                 └──┬───┘               │   ┌──────────┐   │
┌──────┐  receive   │                   └──▶│  umumiy  │◀──┘
│  B   │ ◀──────────┘                       │  xotira  │
└──────┘                                    └──────────┘
 yadro har bir uzatishda qatnashadi    yadro faqat sozlashda qatnashadi
```

| Model | Afzalliklari | Kamchiliklari |
|---|---|---|
| **Xabar uzatish** (pipe, xabarlar navbati, soket) | Oddiylik, yadro o'zi sinxronlaydi, tarmoq orqali ham ishlaydi | Har bir xabar yadro orqali nusxalanadi — sekinroq |
| **Umumiy xotira** | Maksimal tezlik: nusxalash yo'q | Sinxronizatsiya uchun dasturchining o'zi javobgar |

### IPC mexanizmlari sharhi

| Mexanizm | Yo'nalish | Jarayonlar qarindoshligi | Tarmoq orqali | Xususiyatlari |
|---|---|---|---|---|
| Anonim kanal (`pipe`) | Bir tomonlama | Faqat qarindosh (`fork` orqali) | Yo'q | Baytlar oqimi, shell dagi `|` |
| Nomlangan kanal (FIFO) | Bir tomonlama | Istalgan | Yo'q | Fayl tizimida nomi bor |
| Signallar | Xabarnoma | Istalgan (huquq bilan) | Yo'q | Faqat signal raqami, ma'lumotsiz |
| Xabarlar navbati | Ikki tomonlama | Istalgan | Yo'q | Chegaralari va ustuvorliklari bor xabarlar |
| Umumiy xotira | Umumiy | Istalgan | Yo'q | Eng tez, sinxronizatsiya kerak |
| Semaforlar (nomlangan) | — | Istalgan | Yo'q | Ma'lumot uzatish emas, sinxronizatsiya |
| Unix soketlari (`AF_UNIX`) | Ikki tomonlama | Bitta mashinadagi istalgan | Yo'q | Fayl deskriptorlarini uzatish mumkin |
| TCP/UDP soketlari | Ikki tomonlama | Istalgan | **Ha** | Universal mexanizm |
| Xotiraga akslangan fayllar (`mmap`) | Umumiy | Istalgan | Yo'q | Faylga bog'langan umumiy xotira |

---

# 10. Kanallar (pipe, FIFO) va signallar

### Anonim kanal

**Kanal (pipe)** — yadrodagi bir yo'nalishli bufer. Bir jarayon unga bir uchidan yozadi, boshqasi ikkinchi uchidan o'qiydi. Ma'lumotlar yozilish tartibida o'qiladi (FIFO).

Siz kanallardan har kuni foydalanasiz:

```bash
ps aux | grep python | wc -l
```

Qobiq ikkita kanal va uchta jarayon yaratadi. `ps` ning standart chiqishi `grep` ning standart kirishiga ulanadi va hokazo.

`pipe(fd)` tizim chaqiruvi ikkita deskriptor yaratadi: `fd[0]` — o'qish uchun, `fd[1]` — yozish uchun. `fork()` dan keyin bola-jarayon ikkalasini ham meros qilib oladi.

```c
// gcc pipe.c -o pipe
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    int fd[2];                    // fd[0] — o'qish, fd[1] — yozish
    if (pipe(fd) == -1) { perror("pipe"); return 1; }

    pid_t pid = fork();
    if (pid == 0) {               // bola-jarayon: o'quvchi
        close(fd[1]);             // keraksiz uchini yopamiz
        char buf[64];
        ssize_t n = read(fd[0], buf, sizeof buf - 1);
        buf[n] = '\0';
        printf("child %d got: %s\n", getpid(), buf);
        close(fd[0]);
        return 0;
    }
    close(fd[0]);                 // ota-jarayon: yozuvchi
    const char *msg = "salom, bola!";
    write(fd[1], msg, strlen(msg));
    close(fd[1]);                 // o'quvchi EOF oladi
    wait(NULL);
    return 0;
}
```

Kanal ishlash qoidalari:

* **Bo'sh** kanaldan `read` ma'lumot paydo bo'lguncha jarayonni **bloklaydi**.
* **To'la** kanalga `write` jarayonni bloklaydi (Linuxda standart sig'im — 64 KiB).
* **Barcha** yozish deskriptorlari yopilganda `read` 0 qaytaradi — bu fayl oxiri (EOF).
* Birorta ham o'quvchisi bo'lmagan kanalga yozish **`SIGPIPE`** signalini hosil qiladi.

> **Odatiy xato:** kanalning ishlatilmaydigan uchini yopishni unutish. Agar bola-jarayon o'zida `fd[1]` ni yopmasa, u hech qachon EOF olmaydi: yozish uchini o'zi ochiq "ushlab turadi" — va abadiy qotib qoladi.

### Nomlangan kanal (FIFO)

Anonim kanalning nomi yo'q, shuning uchun undan faqat qarindosh jarayonlar foydalana oladi. **FIFO** — fayl tizimida nomi bor kanal:

```bash
mkfifo /tmp/myfifo
ls -l /tmp/myfifo            # prw-r--r-- ... 'p' turi — pipe
# 1-terminal:
cat /tmp/myfifo              # yozuvchi bo'lmaguncha bloklanadi
# 2-terminal:
echo "salom" > /tmp/myfifo   # 1-terminalda "salom" paydo bo'ladi
rm /tmp/myfifo
```

FIFO orqali o'tgan ma'lumotlar **diskka yozilmaydi** — fayl tizimidagi nom faqat jarayonlar kanalni topishi uchun kerak.

### Signallar

**Signal** — jarayonga hodisa haqida asinxron xabarnoma. Signal faqat **raqam** olib boradi, unda ma'lumot yo'q.

| Signal | № | Standart harakat | Qachon paydo bo'ladi |
|---|---|---|---|
| `SIGINT` | 2 | Tugatish | Terminalda Ctrl+C |
| `SIGKILL` | 9 | Tugatish | `kill -9`; **ushlab yoki e'tiborsiz qoldirib bo'lmaydi** |
| `SIGSEGV` | 11 | Tugatish + xotira dampi | Ruxsat etilmagan xotiraga murojaat |
| `SIGPIPE` | 13 | Tugatish | O'quvchisiz kanalga yozish |
| `SIGTERM` | 15 | Tugatish | Standart `kill`; tugashga "muloyim" so'rov |
| `SIGCHLD` | 17* | E'tiborsiz qoldiriladi | Bola-jarayon tugadi yoki to'xtadi |
| `SIGSTOP` | 19* | To'xtatish | **Ushlab bo'lmaydi** |
| `SIGTSTP` | 20* | To'xtatish | Ctrl+Z |
| `SIGCONT` | 18* | Davom ettirish | `fg`, `bg`, `kill -CONT` |

\* x86/ARM dagi Linux uchun raqamlar; boshqa tizimlarda ular farq qilishi mumkin. Skriptlarda nomlarni yozish ishonchliroq: `kill -TERM`.

Jarayon har bir signal uchun (`SIGKILL` va `SIGSTOP` dan tashqari) quyidagilardan birini tanlay oladi: standart harakatni bajarish, e'tiborsiz qoldirish yoki **ishlovchi** o'rnatish.

```c
// gcc sig.c -o sig
#include <signal.h>
#include <stdio.h>
#include <unistd.h>

volatile sig_atomic_t stop = 0;

void on_sigint(int sig) { stop = 1; }       // ishlovchida — faqat bayroq o'rnatish

int main(void) {
    struct sigaction sa = {0};
    sa.sa_handler = on_sigint;
    sigaction(SIGINT, &sa, NULL);
    printf("PID=%d, press Ctrl+C\n", getpid());
    while (!stop) pause();                  // signalni kutamiz
    printf("SIGINT received, clean shutdown\n");
    return 0;
}
```

> Signal ishlovchisida faqat **async-signal-safe** funksiyalarni chaqirish mumkin. `printf` va `malloc` ularga **kirmaydi**. To'g'ri yondashuv — `volatile sig_atomic_t` turidagi bayroqni o'rnatish, barcha ishni esa asosiy siklda bajarish.

```bash
kill -l                  # signallar ro'yxati
kill -TERM 4312          # jarayondan tugashni so'rash
kill -9 4312             # majburan o'ldirish (oxirgi chora)
kill -STOP 4312; kill -CONT 4312
trap 'echo "Ctrl+C ushlandi"' INT     # bash da signal ishlovchisi
```

Nima uchun darhol `SIGKILL` emas, avval `SIGTERM`? `SIGTERM` dasturga to'g'ri yakunlash imkonini beradi: ma'lumotlarni saqlash, fayllarni yopish, vaqtinchalik fayllarni o'chirish. `SIGKILL` jarayonni bir zumda o'ldiradi va ma'lumotlar yo'qolishi mumkin.

---

# 11. Umumiy xotira, xabarlar navbati, soketlar. Windowsda IPC

### POSIX umumiy xotirasi

Eng tez almashish usuli: bir nechta jarayon o'z manzil maydonlariga **bitta** jismoniy xotira sohasini akslantiradi.

```c
// Yozuvchi. gcc shm_writer.c -o shm_writer  (eski glibc da -lrt kerak)
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

int main(void) {
    int fd = shm_open("/demo_shm", O_CREAT | O_RDWR, 0600);  // obyekt yaratish
    ftruncate(fd, 4096);                                      // o'lchamni belgilash
    char *p = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    strcpy(p, "salom from shared memory");
    printf("written, run the reader\n");
    munmap(p, 4096);
    close(fd);
    return 0;
}
```

```c
// O'quvchi. gcc shm_reader.c -o shm_reader
#include <fcntl.h>
#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>

int main(void) {
    int fd = shm_open("/demo_shm", O_RDONLY, 0);
    char *p = mmap(NULL, 4096, PROT_READ, MAP_SHARED, fd, 0);
    printf("read: %s\n", p);
    munmap(p, 4096);
    close(fd);
    shm_unlink("/demo_shm");                                  // obyektni o'chirish
    return 0;
}
```

Linuxda POSIX shared memory obyektlari `/dev/shm` dagi fayllar sifatida ko'rinadi:

```bash
ls -l /dev/shm
```

> Umumiy xotira kirishni **sinxronlamaydi**. Agar yozuvchi va o'quvchi bir vaqtda ishlasa, o'quvchi yarim yozilgan ma'lumotlarni ko'rishi mumkin. Shuning uchun u **semaforlar** (`sem_open`) yoki `PTHREAD_PROCESS_SHARED` atributli myutekslar bilan birga ishlatiladi.

Eski **System V IPC** interfeysi ham mavjud (`shmget`, `msgget`, `semget`). Uning obyektlari jarayonlar tugagandan keyin o'chirilmaydi va quyidagi buyruq bilan ko'rinadi:

```bash
ipcs -a              # System V xotira segmentlari, navbatlar, semaforlar
ipcrm -m <shmid>     # segmentni o'chirish
```

### Xabarlar navbati

**Xabarlar navbati** xabarlarni **chegaralarini saqlagan holda** (baytlar oqimini uzatadigan kanaldan farqli) va POSIX variantida **ustuvorliklar** bilan saqlaydi.

```c
// gcc mq.c -o mq   (Linuxda: eski glibc da -lrt)
mqd_t q = mq_open("/demo_mq", O_CREAT | O_RDWR, 0600, NULL);
mq_send(q, "task-42", 8, 5);          // 5 ustuvorlikli xabar
char buf[8192]; unsigned prio;
mq_receive(q, buf, sizeof buf, &prio);  // eng yuqori ustuvorlikli xabarni oladi
mq_close(q);
mq_unlink("/demo_mq");
```

### Soketlar

**Soket** — ikki tomonlama aloqa kanalining oxirgi nuqtasi. Bir xil interfeys (`socket`, `bind`, `listen`, `accept`, `connect`, `send`, `recv`) quyidagicha ishlaydi:

* **mahalliy** — Unix domain sockets (`AF_UNIX`). Ulardan, masalan, Docker (`/var/run/docker.sock`) va systemd foydalanadi;
* **tarmoq orqali** — TCP/UDP (`AF_INET`, `AF_INET6`).

```bash
ss -xl | head          # tinglayotgan Unix soketlari
ss -tlnp               # tinglayotgan TCP soketlari va jarayonlar
```

Ko'rib chiqilgan mexanizmlar orasida faqat soketlar jarayonlarga **turli kompyuterlarda** o'zaro aloqa qilish imkonini beradi.

### Windowsda IPC

| Windows mexanizmi | Linuxdagi analogi |
|---|---|
| Anonim kanallar (`CreatePipe`) | `pipe()` |
| Nomlangan kanallar (`\\.\pipe\name`, `CreateNamedPipe`) | FIFO, lekin **ikki tomonlama** va tarmoq orqali ishlaydi |
| Fayllarni akslantirish (`CreateFileMapping` + `MapViewOfFile`) | `shm_open` + `mmap` |
| Pochta qutilari (Mailslots) | Keng tarqatiladigan datagrammalar |
| Soketlar (Winsock) | BSD soketlari |
| `WM_COPYDATA` (oyna xabarlari) | — |
| COM / RPC / ALPC | D-Bus, RPC |
| Signallar yo'q; `GenerateConsoleCtrlEvent` va hodisalar bor | Signallar |

---

# 12. Sinxronizatsiya: poyga holati va kritik seksiya

### Poyga holati (race condition)

**Poyga holati** — dastur natijasi parallel oqimlar yoki jarayonlar amallarining qaysi tartibda bajarilishiga bog'liq bo'lgan vaziyat.

Klassik misol — ikkita oqim umumiy hisoblagichni milliontadan oshiradi:

```c
// gcc race.c -o race -pthread
#include <pthread.h>
#include <stdio.h>

#define N 1000000
long counter = 0;                         // umumiy o'zgaruvchi

void *worker(void *arg) {
    for (int i = 0; i < N; i++)
        counter++;                        // atomar amal EMAS!
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, worker, NULL);
    pthread_create(&t2, NULL, worker, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %ld (expected %d)\n", counter, 2 * N);
    return 0;
}
```

2+ yadroli kompyuterda haqiqiy ishga tushirish:

```
counter = 1068612 (expected 2000000)
counter = 1049141 (expected 2000000)
```

Natija **har safar boshqacha** va kutilganidan kam. Nima uchun? `counter++` amali protsessor darajasida **uchta** qadamdan iborat:

```
1. LOAD   R ← counter      (xotiradan registrga o'qish)
2. ADD    R ← R + 1        (oshirish)
3. STORE  counter ← R      (qaytarib yozish)
```

Agar oqimlar omadsiz navbatlashsa, bitta oshirish **yo'qoladi**:

| Qadam | A oqim | B oqim | Xotiradagi counter |
|---|---|---|---|
| 1 | LOAD R=5 | | 5 |
| 2 | | LOAD R=5 | 5 |
| 3 | ADD R=6 | | 5 |
| 4 | | ADD R=6 | 5 |
| 5 | STORE 6 | | 6 |
| 6 | | STORE 6 | **6** (7 bo'lishi kerak edi) |

Bu **yo'qolgan yangilanish (lost update)** deyiladi.

> **Data race** — xususiy holat: ikki oqim bitta xotira katagiga sinxronizatsiyasiz murojaat qiladi va ulardan kamida bittasi yozadi. C va C++ da data race — **aniqlanmagan xatti-harakat**: kompilyator poyga yo'q deb taxmin qilib kod yaratishga haqli.

### Kritik seksiya

**Kritik seksiya** — oqim umumiy ma'lumotlarga murojaat qiladigan kod qismi. Kritik seksiyada bir vaqtda **ko'pi bilan bitta** oqim bo'lishini kafolatlash kerak.

```
  kirish (entry section)      ← ruxsat olish (lock)
  KRITIK SEKSIYA              ← umumiy ma'lumotlar bilan ishlash
  chiqish (exit section)      ← bo'shatish (unlock)
  qolgan kod
```

Kritik seksiya masalasining to'g'ri yechimi **uchta talabga** javob berishi kerak:

1. **O'zaro istisno (mutual exclusion)** — kritik seksiyada ko'pi bilan bitta oqim.
2. **Progress** — agar seksiya bo'sh va kimdir kirmoqchi bo'lsa, kim kirishi haqidagi qaror chekli vaqtda qabul qilinadi; kirishga da'vo qilmayotgan oqimlar bu qarorda qatnashmaydi.
3. **Cheklangan kutish (bounded waiting)** — ushbu oqim kutayotganda boshqa oqimlar seksiyaga necha marta kirishi mumkinligining chegarasi bor. Aks holda **ochlik** bo'lishi mumkin.

### Nima uchun oddiy bayroq-o'zgaruvchi ishlamaydi

```c
int busy = 0;
// kirish:
while (busy) { }      // kutamiz
busy = 1;             // egallaymiz
```

Ikkala oqim bir vaqtda `busy == 0` ni ko'rishi va ikkalasi ham kirishi mumkin. Bayroqni tekshirish va o'rnatish — **ikkita alohida amal**, ular orasida almashtirish sodir bo'lishi mumkin.

### Peterson algoritmi (ikki oqim uchun)

Ikki oqim uchun klassik dasturiy yechim (`i` = 0 yoki 1, `j = 1 − i`):

```c
int flag[2] = {0, 0};   // flag[i] = 1: i oqim kirmoqchi
int turn;               // kimning navbati yon berish

void lock(int i) {
    int j = 1 - i;
    flag[i] = 1;        // men kirmoqchiman
    turn = j;           // lekin navbatni boshqasiga beraman
    while (flag[j] && turn == j) { }   // boshqasi kirmoqchi va hozir uning navbati ekan, kutaman
}
void unlock(int i) { flag[i] = 0; }
```

Algoritm uchala talabni ham qanoatlantiradi. Lekin **zamonaviy protsessorlarda** u bu ko'rinishda ishlamaydi: protsessor va kompilyator xotiraga o'qish va yozish amallarini **qayta tartiblashi** mumkin. To'g'ri ishlashi uchun atomar amallar yoki xotira to'siqlari (`atomic_thread_fence`) kerak. Shuning uchun amalda apparat yordamidan foydalaniladi.

### Apparat yordami: atomar amallar

Protsessor **bo'linmas holda bajariladigan** ko'rsatmalarni taqdim etadi:

* **Test-and-Set (TAS)** — eski qiymatni atomar o'qish va 1 ni yozish.
* **Compare-and-Swap (CAS)** — atomar: "agar qiymat `expected` ga teng bo'lsa, `new` ni yoz"; muvaffaqiyatli bo'ldimi, shuni qaytaradi.
* **Fetch-and-Add** — atomar qo'shish va eski qiymatni qaytarish (x86 da `lock xadd`).

```c
#include <stdatomic.h>
atomic_long counter = 0;
atomic_fetch_add(&counter, 1);       // atomar counter++ — poyga yo'q
```

TAS asosida eng oddiy blokirovkani qurish mumkin:

```c
atomic_flag lk = ATOMIC_FLAG_INIT;
void lock(void)   { while (atomic_flag_test_and_set(&lk)) { } }   // band ekan, aylanamiz
void unlock(void) { atomic_flag_clear(&lk); }
```

---

# 13. Sinxronizatsiya primitivlari

### Myuteks (mutex)

**Myuteks** (mutual exclusion) — **egasi** bor blokirovka: uni faqat bloklagan oqimning o'zi ochishi mumkin. Agar myuteks band bo'lsa, oqim **uxlaydi** (Waiting ga o'tadi) va protsessorni sarflamaydi.

```c
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    for (int i = 0; i < N; i++) {
        pthread_mutex_lock(&m);      // kritik seksiyaga kirish
        counter++;
        pthread_mutex_unlock(&m);    // chiqish
    }
    return NULL;
}
```

Myuteks bilan natija har doim `counter = 2000000`.

### Spin-blokirovka (spinlock)

**Spin-blokirovkani** kutayotgan oqim uxlamaydi, balki uni doimiy tekshirib, **siklda aylanadi** ("faol kutish").

| | Myuteks | Spin-blokirovka |
|---|---|---|
| Kutish | Uyqu (CPU sarflanmaydi) | Faol (CPU sarflanadi) |
| Band bo'lganda egallash narxi | Kontekstni almashtirish | Protsessor sikllari |
| Qachon foydali | Kritik seksiya uzun yoki I/O ni o'z ichiga oladi | Seksiya juda qisqa, ko'p yadroli tizimda |
| Qayerda qo'llaniladi | Foydalanuvchi dasturlari | OT yadrosi, uzilish ishlovchilari |

> **Bir yadroli** tizimda spin-blokirovka ma'nosiz: kutayotgan oqim aylanayotganda blokirovka egasi bajarila olmaydi va uni bo'shata olmaydi.

### Semafor

**Semafor** (E. Deykstra, 1965) — ikkita atomar amalga ega `S` butun sonli hisoblagich:

* **`wait(S)`** (P, `sem_wait`, "down"): agar `S > 0` bo'lsa, `S` ni 1 ga kamaytirib, davom etish; aks holda `S` musbat bo'lguncha bloklanish.
* **`signal(S)`** (V, `sem_post`, "up"): `S` ni 1 ga oshirish va kutayotgan oqimlardan birini uyg'otish.

Semafor turlari:

* **Ikkilik** (0 va 1 qiymatlar) — myuteksga o'xshaydi, lekin uning **egasi yo'q**: `signal` ni istalgan oqim chaqirishi mumkin.
* **Sanovchi** (0..N qiymatlar) — resursning bir vaqtdagi foydalanuvchilari sonini cheklaydi. Misol: ma'lumotlar bazasiga bir vaqtda 3 tadan ortiq ulanish emas.

```c
#include <semaphore.h>
sem_t slots;
sem_init(&slots, 0, 3);       // 0 — bitta jarayon oqimlari orasida; boshlang'ich qiymat 3

sem_wait(&slots);             // bitta joyni egallash (0 bo'lsa — kutish)
use_database();
sem_post(&slots);             // joyni bo'shatish
```

> macOS da nomsiz `sem_init` semaforlari qo'llab-quvvatlanmaydi; u yerda nomlangan `sem_open` ishlatiladi. Linuxda ikkala variant ham ishlaydi.

Semafordan **tartiblash** uchun ham foydalanish mumkin: "B oqim 2-qadamni faqat A oqimning 1-qadamidan keyin bajarishi kerak":

```
sem_t done = 0;
A oqim:  step1();  sem_post(&done);
B oqim:  sem_wait(&done);  step2();     // step2 har doim step1 dan keyin
```

| | Myuteks | Semafor |
|---|---|---|
| Qiymat | Bloklangan / bo'sh | Butun son ≥ 0 |
| Egasi | Bor | Yo'q |
| Vazifasi | O'zaro istisno | Resurslarni sanash va oqimlar orasida signal berish |

### Shartli o'zgaruvchi (condition variable)

Ba'zan oqim shunchaki blokirovka bo'shashini emas, **shart bajarilishini** kutishi kerak ("navbatda element paydo bo'ldi"). Shartni tekshirib siklda aylanish — isrofgarchilik. **Shartli o'zgaruvchi** boshqa oqim signal bergunicha uxlab turish imkonini beradi.

```c
pthread_mutex_lock(&m);
while (!condition)                  // HAR DOIM while, if emas
    pthread_cond_wait(&cv, &m);     // atomar: m ni qo'yib yuborib uxlash; uyg'onganda m ni qayta egallash
/* shart bajarildi, m egallangan */
pthread_mutex_unlock(&m);

// Boshqa oqim:
pthread_mutex_lock(&m);
condition = 1;
pthread_cond_signal(&cv);           // kutayotgan bitta oqimni uyg'otish (broadcast — hammasini)
pthread_mutex_unlock(&m);
```

Nima uchun `if` emas, `while`? Birinchidan, **soxta uyg'onishlar (spurious wakeups)** bo'ladi. Ikkinchidan, uyg'ongan oqim myuteksni qayta egallayotganda boshqa oqim shartni "olib ketishga" ulgurgan bo'lishi mumkin. Shuning uchun uyg'ongandan keyin shartni qayta tekshirish kerak.

### Monitor

**Monitor** — ma'lumotlar, myuteks va shartli o'zgaruvchilarni birlashtiradigan til konstruksiyasi: monitor metodlari avtomatik ravishda o'zaro istisno bilan bajariladi. Misollar: Javada `synchronized` + `wait/notify`, C# da `lock` + `Monitor`.

### O'qish-yozish blokirovkasi va to'siq

* **Read-write lock** (`pthread_rwlock_t`) — **bir vaqtda ko'p o'quvchi** yoki **bitta yozuvchi**. O'qishlar yozishlardan ancha ko'p bo'lganda foydali (kesh, ma'lumotnoma).
* **To'siq (barrier)** (`pthread_barrier_t`) — N ta oqim bir-birini kutadigan nuqta. Hammasi kelmaguncha hech biri oldinga o'tmaydi. Qadamba-qadam parallel hisoblashlarda qo'llaniladi.

### Windowsdagi primitivlar

| Windows | POSIX |
|---|---|
| `CRITICAL_SECTION`, `SRWLOCK` | `pthread_mutex_t`, `pthread_rwlock_t` |
| Mutex (`CreateMutex`) — yadro obyekti, jarayonlar orasida ishlaydi | `PTHREAD_PROCESS_SHARED` li myuteks |
| Semaphore (`CreateSemaphore`) | `sem_t` |
| Event (`CreateEvent`, `SetEvent`) | Shartli o'zgaruvchi + bayroq |
| `CONDITION_VARIABLE` | `pthread_cond_t` |
| `Interlocked*` (`InterlockedIncrement`) | `<stdatomic.h>` |
| `WaitForSingleObject` / `WaitForMultipleObjects` | `sem_wait`, `pthread_join`, `waitpid`... |

### Primitivni qanday tanlash kerak

| Vazifa | Primitiv |
|---|---|
| Oddiy hisoblagich yoki bayroqni himoyalash | Atomar o'zgaruvchi |
| Ma'lumotlar tuzilmasini himoyalash | Myuteks |
| Ko'p o'qish, kam yozish | Read-write lock |
| Bir vaqtdagi foydalanuvchilar sonini cheklash | Sanovchi semafor |
| Shart bajarilishini kutish | Shartli o'zgaruvchi + myuteks |
| **Jarayonlarni** sinxronlash | Nomlangan semafor, umumiy xotiradagi process-shared myuteks |
| Yadrodagi juda qisqa seksiya | Spin-blokirovka |

---

# 14. Sinxronizatsiyaning klassik masalalari

Bu uchta masala — real vaziyatlarning modellari. Har qanday yangi sinxronizatsiya mexanizmi ularda tekshiriladi.

### 1. Ishlab chiqaruvchi–iste'molchi (cheklangan bufer)

Ishlab chiqaruvchi elementlarni N o'lchamli buferga qo'yadi, iste'molchi ularni oladi. Bufer **to'la** bo'lsa, ishlab chiqaruvchi kutishi kerak; **bo'sh** bo'lsa — iste'molchi.

**Semaforlardagi yechim** (uchta semafor):

```
semaphore mutex = 1;    // bufer bilan ishlashda o'zaro istisno
semaphore empty = N;    // bo'sh joylar soni
semaphore full  = 0;    // band joylar soni

Ishlab chiqaruvchi:             Iste'molchi:
  item = produce();               wait(full);
  wait(empty);                    wait(mutex);
  wait(mutex);                      item = take();
    put(item);                    signal(mutex);
  signal(mutex);                  signal(empty);
  signal(full);                   consume(item);
```

> **Tartib muhim!** Agar ishlab chiqaruvchi `wait(mutex)` ni `wait(empty)` dan **oldin** bajarsa va bufer to'la bo'lsa, u `mutex` ni ushlab turgan holda uxlab qoladi. Iste'molchi joy bo'shatish uchun kira olmaydi — **o'zaro bloklanish**.

**Myuteks va shartli o'zgaruvchilardagi yechim** (tekshirilgan, natija `sum = 55`):

```c
// gcc pc.c -o pc -pthread
#include <pthread.h>
#include <stdio.h>

#define SIZE 4
int buf[SIZE], in = 0, out = 0, count = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;

void put(int x) {
    pthread_mutex_lock(&m);
    while (count == SIZE)                    // if emas, while!
        pthread_cond_wait(&not_full, &m);
    buf[in] = x; in = (in + 1) % SIZE; count++;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&m);
}

int get(void) {
    pthread_mutex_lock(&m);
    while (count == 0)
        pthread_cond_wait(&not_empty, &m);
    int x = buf[out]; out = (out + 1) % SIZE; count--;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&m);
    return x;
}

void *producer(void *a) { for (int i = 1; i <= 10; i++) put(i); put(-1); return NULL; }
void *consumer(void *a) {
    long sum = 0; int x;
    while ((x = get()) != -1) sum += x;
    printf("sum = %ld\n", sum);              // 55
    return NULL;
}

int main(void) {
    pthread_t p, c;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);
    pthread_join(p, NULL); pthread_join(c, NULL);
    return 0;
}
```

Qayerda uchraydi: `cmd1 | cmd2` konveyeri (kanal buferi), oqimlar hovuzining vazifalar navbati, chop etish buferi, tarmoq paketlari navbati.

### 2. O'quvchilar–yozuvchilar

Ko'p oqim umumiy ma'lumotlarni o'qiydi, ba'zilari — o'zgartiradi. O'quvchilar **bir vaqtda** ishlashi mumkin, yozuvchi esa — faqat **yolg'iz**.

```
semaphore rw_mutex = 1;   // yozuvchining (va birinchi o'quvchining) kirishi
semaphore mutex = 1;      // read_count ni himoyalash
int read_count = 0;

Yozuvchi:               O'quvchi:
  wait(rw_mutex);         wait(mutex);
    write();                read_count++;
  signal(rw_mutex);         if (read_count == 1) wait(rw_mutex);   // birinchi o'quvchi yozuvchilarni bloklaydi
                          signal(mutex);
                            read();
                          wait(mutex);
                            read_count--;
                            if (read_count == 0) signal(rw_mutex); // oxirgi o'quvchi yozuvchilarni kiritadi
                          signal(mutex);
```

> Bu variantda ("o'quvchilar ustuvorligi") o'quvchilar uzluksiz kelsa, yozuvchi abadiy **och qolishi** mumkin. Yozuvchilar ustuvorligiga ega va "adolatli" variantlar mavjud. Tayyor amalga oshirish — `pthread_rwlock_t`.

### 3. Tushlik qilayotgan faylasuflar

Beshta faylasuf dumaloq stol atrofida o'tiradi, qo'shnilar orasida bittadan vilka yotadi (jami 5 ta). Ovqatlanish uchun faylasufga qo'shni **ikkala** vilka kerak.

```
              F0
         v4        v0
      F4              F1
         v3        v1
          F3  v2  F2
```

Sodda yechim — "chap vilkani, keyin o'ngini olish". Agar beshtasi ham bir vaqtda chap vilkani olsa, har biri o'ng vilkani abadiy kutadi — **o'zaro bloklanish**.

Yechish usullari:

1. **Resurslarni tartiblash:** vilkalarni raqamlaymiz, har kim avval **kichikroq raqamli** vilkani oladi. F4 faylasuf avval v4 emas, v0 ni oladi — kutish sikli uziladi.
2. **Ovqatlanuvchilar sonini cheklash:** stolga bir vaqtda 4 tadan ortiq faylasuf o'tirmaydi (qiymati 4 bo'lgan semafor).
3. **Asimmetriya:** juft faylasuflar avval chap vilkani, toqlari — o'ngini oladi.
4. **Ikkala vilkani atomar olish**, umumiy myuteks ostida.

---

# 15. O'zaro bloklanish (deadlock)

**O'zaro bloklanish (tupik, deadlock)** — jarayonlar (oqimlar) guruhi bir-birini cheksiz kutadigan vaziyat: har biri boshqasiga kerakli resursni ushlab turadi va boshqasi ushlab turgan resursni kutadi.

```c
// 1-oqim                           // 2-oqim
lock(A);                            lock(B);
lock(B);   // B ni kutadi (2-oqimda) lock(A);   // A ni kutadi (1-oqimda)
```

**Hayotiy misol:** ikki mashina tor ko'prikda uchrashdi. Har biri ko'prikning yarmini egalladi va ikkinchisi orqaga qaytmaguncha hech kim o'ta olmaydi.

### Koffmanning to'rtta sharti (1971)

O'zaro bloklanish faqat to'rttala shart **bir vaqtda** bajarilganda mumkin:

| № | Shart | Ma'nosi |
|---|---|---|
| 1 | **O'zaro istisno** | Resursdan faqat bitta jarayon foydalana oladi |
| 2 | **Ushlab turish va kutish (hold and wait)** | Jarayon resursni ushlab turadi va boshqasini kutadi |
| 3 | **Siqib chiqarishning yo'qligi (no preemption)** | Resursni kuch bilan tortib olib bo'lmaydi, faqat ixtiyoriy beriladi |
| 4 | **Siklik kutish (circular wait)** | P1 → P2 → ... → Pn → P1 sikli mavjud, bunda har biri keyingisining resursini kutadi |

**Kamida bitta** shartni buzish kifoya — o'zaro bloklanish imkonsiz bo'ladi.

### Resurslarni taqsimlash grafi

* Doira — jarayon, kvadrat — resurs, kvadratdagi nuqtalar — resurs nusxalari.
* **P → R** strelkasi — jarayon resursni *so'ramoqda*.
* **R → P** strelkasi — resurs jarayonga *ajratilgan*.

```
   ┌────┐  so'rov   ┌───┐  ajratilgan ┌────┐
   │ P1 │ ────────▶ │ B │ ──────────▶ │ P2 │
   └────┘           └───┘             └────┘
      ▲                                  │
      │ ajratilgan  ┌───┐     so'rov     │
      └──────────── │ A │ ◀──────────────┘
                    └───┘
          P1 → B → P2 → A → P1 sikli  ⇒  o'zaro bloklanish
```

Qoida: agar har bir resursning **bitta nusxasi** bo'lsa, **grafdagi sikl ⇔ o'zaro bloklanish**. Agar nusxalar bir nechta bo'lsa, sikl zarur, lekin yetarli shart emas.

### O'zaro bloklanishga qarshi kurash usullari

| Yondashuv | G'oya | Misol |
|---|---|---|
| **Oldini olish (prevention)** | Loyihalash bosqichida 4 shartdan birini buzish | Blokirovkalarni egallashning yagona tartibi (siklik kutishni buzadi); barcha resurslarni birdaniga so'rash (ushlab turish va kutishni buzadi) |
| **Chetlab o'tish (avoidance)** | Resursni faqat holat **xavfsiz** qolsa berish | Bankir algoritmi |
| **Aniqlash va tiklash (detection)** | Tupiklarga yo'l qo'yish, davriy sikllarni qidirish va bartaraf etish | Qurbon jarayonni tugatish, tranzaksiyani orqaga qaytarish (MBBTlar shunday qiladi) |
| **E'tiborsiz qoldirish ("tuyaqush algoritmi")** | Tupiklarni kamdan-kam deb hisoblab, ularga resurs sarflamaslik | Umumiy maqsadli OTlarning ko'pchiligi foydalanuvchi dasturlariga nisbatan shunday qiladi |

Dasturchi uchun eng amaliy usul — **blokirovkalarni egallashning yagona tartibi**: agar barcha oqimlar har doim `A` ni `B` dan oldin egallasa, sikl hosil bo'la olmaydi.

### Bankir algoritmi (Deykstra)

OT har bir jarayonning **maksimal ehtiyojini** oldindan biladi. Resurs faqat berilgandan keyin tizim **xavfsiz holatda** qolsa beriladi: jarayonlarni tugatishning shunday tartibi mavjudki, unda har biri yetishmayotgan resurslarni ola oladi.

Belgilashlar: **Allocation** — hozir ajratilgan; **Max** — maksimal ehtiyoj; **Need = Max − Allocation**; **Available** — bo'sh.

**Misol** (A, B, C — 3 turdagi resurs; jami 10, 5, 7):

| Jarayon | Allocation (A B C) | Max (A B C) | Need (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |

**Available = (3, 3, 2).**

Xavfsizlikni tekshirish algoritmi: `Work = Available`; `Need ≤ Work` bo'lgan jarayonni qidiramiz; u tugadi va resurslarni qaytardi deb hisoblaymiz: `Work += Allocation`; takrorlaymiz.

| Qadam | Jarayon | Need ≤ Work? | Tugagandan keyin Work |
|---|---|---|---|
| 1 | P1 | (1,2,2) ≤ (3,3,2) ✓ | (3,3,2) + (2,0,0) = **(5,3,2)** |
| 2 | P3 | (0,1,1) ≤ (5,3,2) ✓ | + (2,1,1) = **(7,4,3)** |
| 3 | P0 | (7,4,3) ≤ (7,4,3) ✓ | + (0,1,0) = **(7,5,3)** |
| 4 | P2 | (6,0,0) ≤ (7,5,3) ✓ | + (3,0,2) = **(10,5,5)** |
| 5 | P4 | (4,3,1) ≤ (10,5,5) ✓ | + (0,0,2) = **(10,5,7)** |

Barcha jarayonlar tugashi mumkin. Holat **xavfsiz**, xavfsiz ketma-ketlik — **⟨P1, P3, P0, P2, P4⟩**.

Pi jarayon resurs **so'raganda**: (1) `Request ≤ Need` ni tekshirish; (2) `Request ≤ Available` ni tekshirish, aks holda kutish; (3) resurslarni *shartli* ajratib, xavfsizlik tekshiruvini ishga tushirish; holat xavfli bo'lsa — orqaga qaytarish va jarayonni kutishga majburlash.

> Xavfli holat ≠ o'zaro bloklanish. U faqat OT tupik yo'qligini **kafolatlay olmasligini** bildiradi.

Amalda bankir algoritmi umumiy maqsadli OTlarda ishlatilmaydi: jarayonlarning maksimal ehtiyojlarini oldindan bilish mumkin emas. Lekin u xavfsiz holat g'oyasini juda yaxshi ko'rsatadi.

### Yaqin muammolar

* **Dinamik bloklanish (livelock)** — oqimlar bloklanmagan, ular faol nimadir qilmoqda, lekin oldinga siljish yo'q. Yo'lakda bir vaqtda bir-biriga yo'l beradigan ikki odam kabi.
* **Ochlik (starvation)** — oqim resursni cheksiz ola olmaydi, chunki boshqalar uni doim chetlab o'tadi. Yechim — qarish (aging), adolatli navbatlar.
* **Ustuvorlik inversiyasi** — yuqori ustuvorlikli H oqim past ustuvorlikli L ushlab turgan myuteksni kutadi, L esa CPU olmaydi, chunki o'rta ustuvorlikli M ishlamoqda. Yechim — **ustuvorlikni meros qilish**: L vaqtincha H ning ustuvorligini oladi (`PTHREAD_PRIO_INHERIT`). Mashhur holat — 1997-yilda Mars Pathfinder marsoxodidagi nosozliklar.

---

# 16. Linuxda jarayonlarni kuzatish vositalari

| Vazifa | Buyruq |
|---|---|
| Jarayonlar ro'yxati | `ps aux`, `ps -ef` |
| Jarayonlar daraxti | `pstree -p`, `ps -ef --forest` |
| Real vaqtdagi yuklama | `top`, `htop` (`top` da: `H` — oqimlar, `1` — yadrolar bo'yicha) |
| Jarayon oqimlari | `ps -eLf`, `ls /proc/<PID>/task`, `top -H -p <PID>` |
| Jarayonni nomi bo'yicha topish | `pgrep -a nginx`, `pidof nginx` |
| Signal yuborish | `kill -TERM <PID>`, `pkill -f script.py`, `killall firefox` |
| Ustuvorlik | `nice`, `renice`, `chrt` |
| Jarayonning tizim chaqiruvlari | `strace -f -p <PID>`, `strace -c ./prog` |
| Ochiq fayllar va kanallar | `lsof -p <PID>`, `ls -l /proc/<PID>/fd` |
| IPC obyektlari | `ipcs -a`, `ls /dev/shm`, `ss -xl` |
| Kontekstni almashtirishlar | `vmstat 1`, `pidstat -w 1` |
| Qobiqning fon vazifalari | `jobs`, `bg`, `fg`, `&`, `Ctrl+Z`, `nohup`, `disown` |

```bash
sleep 300 &                       # fonda ishga tushirish
jobs                              # [1]+ Running  sleep 300 &
ps -o pid,ppid,stat,ni,cmd -p $!  # $! — oxirgi fon jarayonining PID i
kill %1                           # 1-vazifani tugatish
```

Misol: ishlayotgan dasturning oqimlari va kanallarini ko'rish:

```bash
./pc &                                     # ishlab chiqaruvchi–iste'molchi misoli
ps -o pid,nlwp,cmd -p $!                   # NLWP — oqimlar soni
strace -f -e trace=futex ./race 2>&1 | tail   # Linuxda myutekslar futex orqali amalga oshirilgan
```

---

# 17. Amaliy topshiriqlar

Topshiriqlarni Linux (Ubuntu/Debian) virtual mashinasida bajaring. Kompilyatorni o'rnating: `sudo apt install build-essential strace psmisc`.

### 1-topshiriq. Jarayonlar daraxti

1. `pstree -p $$` va `ps -o pid,ppid,stat,cmd --forest` ni bajaring.
2. `sleep 100 &` ni ishga tushiring va uning PPID ini toping. Uning ota-jarayoni kim?
3. `/proc/<PID>/status` dan `State`, `PPid`, `Threads`, `voluntary_ctxt_switches` maydonlarini toping.

### 2-topshiriq. `fork` va zombi

1. 3-bo'limdagi `fork1.c` dasturini kompilyatsiya qiling. Nima uchun ota-jarayonda `x = 5` ekanini tushuntiring.
2. Bola-jarayon darhol tugaydigan, ota-jarayon esa `wait` ni **chaqirmasdan** 30 soniya uxlaydigan dastur yozing. Boshqa terminalda zombini toping: `ps -eo pid,ppid,stat,cmd | grep Z`.
3. `wait(NULL)` qo'shing va zombi yo'qolganiga ishonch hosil qiling.

### 3-topshiriq. Jarayonlarni sanash

Har bir parcha nechta satr chop etishini oldindan ayting, keyin tekshiring (`setvbuf(stdout, NULL, _IONBF, 0)` ni unutmang):

```c
for (int i = 0; i < 3; i++) { fork(); printf("i=%d\n", i); }
```

```c
if (fork() || fork()) fork();
printf("y\n");
```

### 4-topshiriq. Poyga va uni bartaraf etish

1. 12-bo'limdagi `race.c` ni besh marta ishga tushiring. Natijalarni yozib oling.
2. Dasturni uch usulda tuzating: myuteks, `atomic_fetch_add`, har bir oqim lokal o'zgaruvchiga sanab, uni umumiyga myuteks ostida bir marta qo'shadi. Vaqtni solishtiring: `time ./race`.

### 5-topshiriq. Kanal va FIFO

1. `pipe.c` ni kompilyatsiya qiling. Bola-jarayondagi `close(fd[1])` satrini o'chiring va uni EOF gacha siklda o'qiydigan qilib o'zgartiring. Nima bo'ladi? Nima uchun?
2. FIFO orqali bir terminaldagi `ls -l /etc` chiqishini boshqa terminaldagi `wc -l` ga uzating.

### 6-topshiriq. Signallar

1. `sig.c` ni kompilyatsiya qiling. Dasturga boshqa terminaldan `SIGINT`, `SIGTERM` va `SIGKILL` yuboring. Xatti-harakati qanday farq qiladi?
2. Ctrl+C bosilganda o'zining vaqtinchalik faylini o'chiradigan, `trap` li bash skript yozing.

### 7-topshiriq. Ishlab chiqaruvchi–iste'molchi va rejalashtiruvchi

1. `pc.c` ni ishga tushiring va undagi `while` ni `if` ga almashtiring. Nima uchun dastur noto'g'ri ishlashi mumkin, garchi siz buni katta ehtimol bilan ko'rmasangiz ham?
2. Bitta yadroda (`taskset -c 0`) nice 0 va nice 19 bilan ikkita cheksiz `yes > /dev/null &` siklini ishga tushiring. `top` da `%CPU` ni solishtiring. Natijani tushuntiring.

---

# 18. Odatiy xatolar

| Xato | Oqibati | To'g'risi |
|---|---|---|
| `fork()` natijasini tekshirmaslik | −1 xatoda dastur oldindan aytib bo'lmaydigan tarzda ishlaydi | `pid == -1` ni qayta ishlash |
| Bola-jarayonlar uchun `wait()` ni chaqirmaslik | Zombilar to'planishi, PID larning tugashi | `wait`/`waitpid` yoki `SIGCHLD` ishlovchisi |
| Bo'sh bo'lmagan `stdout` buferida `fork()` | Chiqishning takrorlanishi | `fork()` dan oldin `fflush(stdout)` |
| Kanalning ishlatilmaydigan uchlarini yopmaslik | O'quvchi EOF olmaydi va qotib qoladi | Keraksiz uchni `fork()` dan keyin darhol yopish |
| Umumiy ma'lumotlarga sinxronizatsiyasiz kirish | Poyga, "tasodifiy" xatolar | Myuteks yoki atomar amallar |
| `pthread_cond_wait` oldidan `while` o'rniga `if` | Shart bajarilmagan holda ishlash | Shartni har doim `while` siklida tekshirish |
| Blokirovkalarni turli tartibda egallash | O'zaro bloklanish | Yagona global egallash tartibi |
| Kritik seksiya ichida uzoq amal (I/O) | Qolgan oqimlar bekor turadi | Kritik seksiyani minimallashtirish |
| Xato yo'lida `unlock` ni unutish | Abadiy blokirovka | Yagona chiqish nuqtasi, RAII (`std::lock_guard`) |
| Sinxronizatsiya o'rniga `volatile` | Poyga saqlanadi: `volatile` atomarlik bermaydi | `atomic_*` yoki myuteks |
| Signal ishlovchisida `printf` | libc ichida o'zaro bloklanish | Faqat `volatile sig_atomic_t` bayrog'i |
| Darhol `kill -9` | Ma'lumotlarning yo'qolishi, "iflos" vaqtinchalik fayllar | Avval `SIGTERM`, keyin `SIGKILL` |

---

# 19. Eslab qolish kerak

1. **Ko'p vazifalilik** — CPU ni almashtirish hisobiga bir vaqtdalik illyuziyasi; siqib chiqaruvchi ko'p vazifalilik taymer uzilishlariga asoslangan.
2. **Jarayon** — o'z manzil maydoniga ega bajarilayotgan dastur; OT u haqidagi hamma narsani **PCB** da saqlaydi.
3. Jarayonning asosiy holatlari: **New, Ready, Running, Waiting, Terminated**.
4. Unixda jarayon **`fork()` + `exec()`** juftligi bilan yaratiladi; ota-jarayon qaytish kodini **`wait()`** orqali oladi, aks holda **zombi** qoladi.
5. `n` ta ketma-ket `fork()` dan keyin **2ⁿ** jarayon mavjud bo'ladi.
6. Rejalashtiruvchi Ready navbatidan jarayon tanlaydi; **SRTF** o'rtacha kutishni minimallashtiradi, **RR** yaxshi javob vaqtini ta'minlaydi.
7. **Oqim** — jarayon ichidagi bajarilish birligi; oqimlar xotirani bo'lishadi, lekin stek va registrlari o'ziniki.
8. **Tolalar va korutinalar** foydalanuvchi maydonida kooperativ almashtiriladi — arzon, lekin siqib chiqarishsiz.
9. **IPC**: xabar uzatish (pipe, FIFO, navbatlar, soketlar) yoki umumiy xotira (tez, lekin sinxronizatsiya kerak).
10. **Poyga** natija bajarilish tartibiga bog'liq bo'lganda paydo bo'ladi; `counter++` atomar emas.
11. Kritik seksiya masalasining yechimi: **o'zaro istisno, progress, cheklangan kutish**. Vositalar — myutekslar, semaforlar, shartli o'zgaruvchilar, atomar amallar.
12. **O'zaro bloklanish** Koffmanning to'rttala shartini talab qiladi; amalda uning oldi **blokirovkalarni egallashning yagona tartibi** bilan olinadi.

---

# 20. Nazorat savollari

1. Konkurentlik parallellikdan nimasi bilan farq qiladi? Bitta yadroda konkurentlik mumkinmi?
2. Siqib chiqaruvchi ko'p vazifalilik kooperativdan nimasi bilan farq qiladi? Siqib chiqarishni qaysi qurilma mumkin qiladi?
3. Dastur jarayondan nimasi bilan farq qiladi?
4. Jarayonning besh holat diagrammasini chizing. Nima uchun Waiting → Running o'tishi mumkin emas?
5. PCB da nima saqlanadi? Linuxda PCB qanday ataladi?
6. `fork()` ota-jarayonda va bola-jarayonda nima qaytaradi?
7. Nima uchun `fork()` dan keyin bola-jarayonda o'zgaruvchining o'zgarishi ota-jarayonda ko'rinmaydi? Copy-on-write nima?
8. To'rtta ketma-ket `fork()` chaqiruvidan keyin nechta jarayon bo'ladi?
9. `exec()` nima qiladi? PID saqlanadimi?
10. Zombi jarayon va yetim jarayon nima? Zombini `kill -9` buyrug'i bilan o'ldirish mumkinmi?
11. Windowsdagi `CreateProcess` `fork` + `exec` juftligidan nimasi bilan farq qiladi?
12. Kutish vaqti va aylanish vaqtiga ta'rif bering.
13. Karvon effekti nima? U qaysi algoritmga xos?
14. Nima uchun SJF ni amalda amalga oshirish qiyin?
15. Kvant o'lchami RR ishiga qanday ta'sir qiladi?
16. CFS dagi `vruntime` nima? Linuxda 6.6 versiyadan boshlab qaysi rejalashtiruvchi ishlatiladi?
17. Nima uchun oqimlar orasida almashtirish jarayonlar orasidagidan arzonroq?
18. Bitta jarayon oqimlari nimani bo'lishadi va har birida nima o'ziniki?
19. N:1, 1:1 va M:N oqim modellarini solishtiring.
20. Tola oqimdan nimasi bilan farq qiladi?
21. "Xabar uzatish" va "umumiy xotira" IPC modellarini solishtiring.
22. Nima uchun yozish uchi yopilmasa, kanal o'quvchisi qotib qolishi mumkin?
23. `SIGTERM` `SIGKILL` dan nimasi bilan farq qiladi? Qaysi signallarni ushlab bo'lmaydi?
24. Nima uchun `counter++` atomar amal emas? Yangilanish yo'qoladigan navbatlashuvni ko'rsating.
25. Kritik seksiya masalasi yechimiga qo'yiladigan uchta talabni ayting.
26. Myuteks semafordan nimasi bilan farq qiladi? Spin-blokirovkadan-chi?
27. Nima uchun `pthread_cond_wait` oldidan `if` emas, `while` ishlatiladi?
28. Ishlab chiqaruvchi–iste'molchi masalasida `wait(empty)` va `wait(mutex)` o'rni almashtirilsa nima bo'ladi?
29. Koffmanning to'rtta shartini ayting. Blokirovkalarni egallashning yagona tartibi ulardan qaysi birini buzadi?
30. Bankir algoritmi bo'yicha 15-bo'limdagi holat xavfsizmi, aniqlang va xavfsiz ketma-ketlikni toping.

---

# 21. Glossariy

| O'zbekcha | Ruscha | English |
|---|---|---|
| Ko'p vazifalilik | Многозадачность | Multitasking |
| Konkurentlik / parallellik | Конкурентность / параллелизм | Concurrency / parallelism |
| Jarayon | Процесс | Process |
| Oqim | Поток | Thread |
| Tola | Волокно | Fiber |
| Korutina (hamdastur) | Сопрограмма | Coroutine |
| Jarayonni boshqarish bloki | Блок управления процессом | Process Control Block (PCB) |
| Rejalashtiruvchi | Планировщик | Scheduler |
| Vaqt kvanti | Квант времени | Time slice / quantum |
| Kontekstni almashtirish | Переключение контекста | Context switch |
| Siqib chiqarish | Вытеснение | Preemption |
| Kutish vaqti / aylanish vaqti | Время ожидания / оборота | Waiting time / turnaround time |
| Jarayonlararo aloqa | Межпроцессное взаимодействие | Inter-Process Communication (IPC) |
| Kanal | Канал | Pipe |
| Signal | Сигнал | Signal |
| Umumiy xotira | Разделяемая память | Shared memory |
| Xabarlar navbati | Очередь сообщений | Message queue |
| Soket | Сокет | Socket |
| Sinxronizatsiya | Синхронизация | Synchronization |
| Poyga holati | Состояние гонки | Race condition |
| Kritik seksiya | Критическая секция | Critical section |
| O'zaro istisno | Взаимное исключение | Mutual exclusion |
| Myuteks | Мьютекс | Mutex |
| Semafor | Семафор | Semaphore |
| Shartli o'zgaruvchi | Условная переменная | Condition variable |
| O'zaro bloklanish (tupik) | Взаимоблокировка | Deadlock |
| Ochlik | Голодание | Starvation |
| Ustuvorlik inversiyasi | Инверсия приоритетов | Priority inversion |
| Zombi jarayon / yetim jarayon | Процесс-зомби / сирота | Zombie / orphan process |

---

# 22. Adabiyotlar

1. Tanenbaum A., Bos H. *Modern Operating Systems.* 4th ed. — Pearson, 2014. — 2-bob "Processes and Threads", 6-bob "Deadlocks" (rus tilida: *Современные операционные системы*, СПб.: Питер, 2015).
2. Silberschatz A., Galvin P., Gagne G. *Operating System Concepts.* 10th ed. — Wiley, 2018. — 3–8-boblar.
3. Arpaci-Dusseau R., Arpaci-Dusseau A. *Operating Systems: Three Easy Pieces.* — 2018 (bepul: ostep.org). — "Virtualization: CPU" va "Concurrency" qismlari.
4. Kerrisk M. *The Linux Programming Interface.* — No Starch Press, 2010. — 20–37, 43–55-boblar.
5. Downey A. *The Little Book of Semaphores.* — Green Tea Press (bepul).
6. Russinovich M. va boshq. *Windows Internals.* 7th ed., Part 1. — Microsoft Press, 2017. — 3–4-boblar (jarayonlar, oqimlar, rejalashtirish).
7. Hujjatlar: `man 2 fork`, `man 3 exec`, `man 2 wait`, `man 7 pipe`, `man 7 signal`, `man 7 shm_overview`, `man 7 pthreads`, `man 7 sem_overview`, `man 7 sched`.
8. Microsoft Learn: *Processes and Threads*, *Synchronization*, *Interprocess Communications*.