# Talabalar uchun topshiriqlar: OTda ko'p vazifalilikni ta'minlash usullari. Jarayonlar, oqimlar, tolalar. Jarayonlararo aloqa. Sinxronizatsiya **Muhit:** Linux virtual mashinasi (Ubuntu 22.04+ yoki Debian 12). Kerakli paketlar: ```bash sudo apt update sudo apt install build-essential strace psmisc procps mkdir -p ~/lab6 && cd ~/lab6 ``` > **Diqqat:** amaliy topshiriqlarni **faqat virtual mashinada** bajaring. `fork()` bilan qilingan xato cheksiz jarayon yaratib, tizimni qotirib qo'yishi mumkin. Ehtiyot uchun ishni boshlashdan oldin `ulimit -u 300` ni bajaring. **Nima topshiriladi:** bitta hisobot fayli (PDF yoki Markdown), unda: * test va nazariy savollarga javoblar; * hisoblash masalalarining **to'liq yechimi** (faqat javob emas — Gantt diagrammalari, jadvallar, qadamlar); * amaliy topshiriqlar uchun: yozgan dastur kodi, bajargan buyruqlaringiz, **natijaning skrinshoti yoki matni** va qisqa tushuntirish; * keys topshiriqlari bo'yicha asoslangan javob. ### Ballar taqsimoti | Qism | Mavzu | Ball | |---|---|---| | 1-qism | Test (10 savol × 2 ball) | 20 | | 2-qism | Nazariy savollar (5 × 3 ball) | 15 | | 3-qism | Hisoblash va tahlil masalalari | 20 | | 4-qism | Amaliy laboratoriya topshiriqlari (6 × 5 ball) | 30 | | 5-qism | Keys topshiriqlari | 15 | | **Jami** | | **100** | | 6-qism | Murakkab topshiriqlar (ixtiyoriy, bonus) | +10 | --- ## 1-qism. Test Har bir savolda bitta to'g'ri javob bor. **1.** Bitta yadroli protsessorda bir nechta dastur "bir vaqtda" ishlayotgandek ko'rinadi. Bu nima deyiladi? * A) Parallellik * B) Konkurentlik * C) Multiprotsessorlik * D) Bu bitta yadroda mumkin emas **2.** Siqib chiqaruvchi ko'p vazifalilikda OT protsessorni jarayondan qanday tortib oladi? * A) Jarayon `yield()` ni chaqirguncha kutadi * B) Jarayon tugaguncha kutadi * C) Apparat taymerining uzilishi orqali * D) Jarayonga `SIGKILL` yuboradi **3.** Jarayon diskdan ma'lumot kelishini kutmoqda. I/O tugagandan keyin u qaysi holatga o'tadi? * A) Running * B) Ready * C) New * D) Terminated **4.** Quyidagi kod nechta "salom" satrini chop etadi (buferlash o'chirilgan)? ```c fork(); fork(); fork(); fork(); printf("salom\n"); ``` * A) 4 * B) 8 * C) 15 * D) 16 **5.** `fork()` dan keyin bola-jarayon global o'zgaruvchi `x` ni o'zgartirdi. Ota-jarayon nimani ko'radi? * A) Yangi qiymatni, chunki xotira umumiy * B) Eski qiymatni, chunki bolada xotiraning o'z nusxasi bor * C) Ota-jarayon bloklanadi * D) Segmentation fault yuz beradi **6.** Bitta jarayon oqimlari quyidagilardan qaysi birini **bo'lishmaydi**? * A) Global o'zgaruvchilarni * B) Ochiq fayl deskriptorlarini * C) Stekni * D) Uyumni (heap) **7.** Qaysi rejalashtirish algoritmi "karvon effekti"ga eng ko'p moyil? * A) FCFS * B) Round Robin * C) SRTF * D) MLFQ **8.** Qaysi signalni ushlab ham, e'tiborsiz qoldirib ham bo'lmaydi? * A) `SIGTERM` * B) `SIGINT` * C) `SIGKILL` * D) `SIGCHLD` **9.** Ikki oqim umumiy `counter` ni sinxronizatsiyasiz milliontadan oshiradi. Natija ko'pincha 2 000 000 dan kam. Asosiy sababi nima? * A) Kompilyator ikkinchi oqimni optimallashtirib o'chiradi * B) `counter++` bo'linmas amal emas: o'qish, qo'shish va yozish orasida boshqa oqim aralashishi mumkin * C) Oqimlarning har birida `counter` ning o'z nusxasi bor * D) Linux bir vaqtda faqat bitta oqimni bajaradi **10.** Barcha oqimlar har doim avval `A`, keyin `B` myuteksini egallaydi. Bu Koffmanning qaysi shartini buzadi va o'zaro bloklanishning oldini oladi? * A) O'zaro istisno * B) Ushlab turish va kutish * C) Siqib chiqarishning yo'qligi * D) Siklik kutish --- ## 2-qism. Nazariy savollar Har biriga 3–8 jumlada javob bering. **1.** Dastur va jarayon o'rtasidagi farqni tushuntiring. Nima uchun har bir jarayonning o'z virtual manzil maydoni bo'lishi muhim? **2.** Jarayonning beshta holatini sanab bering va har bir o'tishga (New → Ready, Ready → Running, Running → Ready, Running → Waiting, Waiting → Ready, Running → Terminated) misol keltiring. Nima uchun Waiting → Running o'tishi yo'q? **3.** Oqim (thread) va tolani (fiber) solishtiring: kim rejalashtiradi, almashtirish narxi, parallellik, bloklovchi tizim chaqiruvidagi xatti-harakat. Har biri qaysi vaziyatda afzal? **4.** Myuteks, semafor va shartli o'zgaruvchining farqini tushuntiring. Nima uchun `pthread_cond_wait` doim `while` sikli ichida chaqiriladi? **5.** IPC ning ikki modelini — xabar uzatish va umumiy xotirani — solishtiring. Har biriga ikkitadan Linux mexanizmi keltiring. Nima uchun umumiy xotira bilan birga semafor kerak? --- ## 3-qism. Hisoblash va tahlil masalalari **3.1. Rejalashtirish (4 ball).** Beshta jarayon berilgan (vaqt millisekundlarda): | Jarayon | Kelish vaqti | CPU burst | |---|---|---| | P1 | 0 | 7 | | P2 | 2 | 4 | | P3 | 3 | 6 | | P4 | 5 | 1 | | P5 | 6 | 3 | **FCFS**, **SJF** (siqib chiqarmaydigan), **SRTF** va **RR (q = 3)** algoritmlari uchun: * a) Gantt diagrammasini chizing; * b) har bir jarayonning kutish vaqti va aylanish vaqtini hisoblang; * c) o'rtacha kutish va o'rtacha aylanish vaqtini toping; * d) qaysi algoritm o'rtacha kutish bo'yicha eng yaxshi? RR da P4 ning javob vaqti (birinchi ishga tushish − kelish) qancha? Kelishuvlar: teng qiymatlarda oldin kelgan jarayon tanlanadi. RR da kvant tugagan paytda kelgan jarayonlar navbatga siqib chiqarilgan jarayondan **oldin** qo'yiladi. Kontekstni almashtirish vaqti hisobga olinmaydi. **3.2. Jarayonlarni sanash (3 ball).** Har bir dastur parchasi nechta satr chop etadi? Har biri uchun jarayonlar daraxtini chizing. (`stdout` buferlanmagan deb hisoblang.) ```c // A for (int i = 0; i < 2; i++) fork(); printf("A\n"); ``` ```c // B fork(); if (fork() == 0) fork(); printf("B\n"); ``` ```c // C if (fork() || fork()) fork(); printf("C\n"); ``` **3.3. Jarayonlar va o'zgaruvchilar (2 ball).** Dastur qanday satrlarni chop etadi (tartibi muhim emas)? Nechta jarayon yaratiladi? ```c int x = 1; if (fork() == 0) { x *= 2; if (fork() == 0) x *= 3; } printf("x=%d\n", x); ``` **3.4. Poyga holati (3 ball).** Umumiy o'zgaruvchi `balance = 10`. A oqim `balance += 5`, B oqim `balance -= 3` ni bajaradi. Har bir amal uch qadamdan iborat: `LOAD R ← balance`, `ADD/SUB`, `STORE balance ← R` (har bir oqimning o'z registri bor). * a) Quyidagi navbatlashuvdan keyin `balance` qanchaga teng? `A.LOAD, B.LOAD, B.SUB, B.STORE, A.ADD, A.STORE` * b) `balance` ning barcha mumkin bo'lgan yakuniy qiymatlarini toping. Qaysi biri to'g'ri? * c) Muammoni myuteks bilan qanday tuzatish kerak? Kodni yozing. **3.5. Semafor izi (3 ball).** Sanovchi semafor `S` ning boshlang'ich qiymati 2. To'rtta oqim quyidagi tartibda amallarni bajaradi (bloklangan oqimlar FIFO tartibida uyg'otiladi): | Qadam | Amal | |---|---| | 1 | T1: `wait(S)` | | 2 | T2: `wait(S)` | | 3 | T3: `wait(S)` | | 4 | T4: `wait(S)` | | 5 | T1: `signal(S)` | | 6 | T2: `signal(S)` | | 7 | T3: `signal(S)` | | 8 | T4: `signal(S)` | Har bir qadamdan keyin `S` qiymatini, bloklangan oqimlar ro'yxatini va resursdan hozir foydalanayotgan oqimlarni yozing. Bir vaqtda resursdan ko'pi bilan nechta oqim foydalanadi? **3.6. Bankir algoritmi (3 ball).** Tizimda A, B, C turdagi resurslar bor. Holat: | Jarayon | Allocation (A B C) | Max (A B C) | |---|---|---| | P0 | 1 1 0 | 4 3 2 | | P1 | 2 0 1 | 3 1 2 | | P2 | 1 1 1 | 5 2 3 | | P3 | 0 1 2 | 2 2 4 | **Available = (2, 1, 2).** * a) Need matritsasini va har bir turdagi resursning jami sonini toping. * b) Holat xavfsizmi? Xavfsiz ketma-ketlikni toping (bir nechta nomzod bo'lsa, eng kichik raqamli jarayonni tanlang). * c) P3 jarayoni (1, 0, 1) so'radi. Uni darhol berish mumkinmi? * d) c) dagi so'rov **o'rniga** P0 jarayoni (1, 1, 0) so'radi. Uni darhol berish mumkinmi? **3.7. Resurslarni taqsimlash grafi (2 ball).** R1, R2, R3, R4 resurslarining har biri bittadan nusxada. * P1 R1 ni ushlab turibdi va R2 ni so'ramoqda; * P2 R2 ni ushlab turibdi va R3 ni so'ramoqda; * P3 R3 ni ushlab turibdi va R4 ni so'ramoqda; * P4 R4 ni ushlab turibdi va hech narsa so'ramayapti. * a) Grafni chizing. O'zaro bloklanish bormi? Agar yo'q bo'lsa, jarayonlar qaysi tartibda tugaydi? * b) Endi P4 qo'shimcha ravishda R1 ni so'radi. Vaziyat qanday o'zgaradi? Qaysi jarayonlar bloklangan? --- ## 4-qism. Amaliy laboratoriya topshiriqlari Barcha fayllarni `~/lab6` katalogida yarating. Har bir topshiriq oxirida ko'rsatilgan natijani hisobotga qo'shing. ### 4.1. Jarayonlar daraxti va `/proc` (5 ball) **Maqsad:** jarayon ierarxiyasini va PCB ma'lumotlarini ko'rish. * `pstree -p $$` va `ps -o pid,ppid,stat,ni,cmd --forest` ni bajaring. Qobiqingizning ota-jarayonlari zanjirini `systemd` gacha yozing. * `sleep 300 &` ni ishga tushiring. `$!` orqali uning PID ini oling. * `/proc//status` dan `Name`, `State`, `PPid`, `Threads`, `voluntary_ctxt_switches`, `nonvoluntary_ctxt_switches` qatorlarini chiqaring. * `kill -STOP `, so'ng holatni qayta tekshiring; keyin `kill -CONT ` va `kill `. **Natija:** `pstree` chiqishi, `/proc//status` dan qatorlar va `STOP` dan oldin va keyin `State` qiymati. Holat qanday o'zgardi? ### 4.2. Zombi va yetim (5 ball) **Maqsad:** zombi va yetim jarayonni o'z ko'zingiz bilan ko'rish. * `zombie.c` dasturini yozing: bola darhol `exit(7)` bilan tugaydi, ota-jarayon `wait` ni **chaqirmasdan** 30 soniya uxlaydi. * Dastur ishlayotganda boshqa terminalda zombini toping: `ps -eo pid,ppid,stat,cmd | awk '$3 ~ /Z/'`. * Dasturni o'zgartiring: 30 soniyadan keyin `waitpid` ni chaqirib, bolaning qaytish kodini chop etsin. * `orphan.c` dasturini yozing: bola 3 marta 2 soniya oralig'ida o'z `PPID` ini chop etadi, ota esa 1 soniyadan keyin tugaydi. **Natija:** `Z` holatidagi `ps` qatori, chop etilgan qaytish kodi va `orphan` chiqishi. PPID nima uchun o'zgardi va qaysi jarayonga teng bo'ldi? ### 4.3. Poyga va uni bartaraf etish (5 ball) **Maqsad:** poyga holatini qayta hosil qilish va uch usulda tuzatish. * Ikkita oqim umumiy `counter` ni 10 000 000 tadan oshiradigan `race3.c` dasturini yozing. Rejim argument bilan tanlanadi: `0` — himoyasiz, `1` — myuteks, `2` — `atomic_fetch_add`, `3` — har bir oqim lokal o'zgaruvchiga sanab, uni oxirida bir marta myuteks ostida qo'shadi. * `gcc -O0 -pthread race3.c -o race3` bilan kompilyatsiya qiling. * Har bir rejimni `time ./race3 ` bilan 3 marta ishga tushiring. **Natija:** to'rt rejim uchun `counter` qiymatlari va `real` vaqtlar jadvali. Qaysi rejimlar to'g'ri? Qaysi biri eng tez va nima uchun? ### 4.4. Kanal orqali konveyer (5 ball) **Maqsad:** qobiq `|` operatorini qanday amalga oshirishini tushunish. * `ps aux | wc -l` buyrug'ini C da amalga oshiradigan `pipeline.c` dasturini yozing: `pipe()`, ikkita `fork()`, `dup2()`, `execlp()`, `wait()`. * Natijani `ps aux | wc -l` bilan solishtiring. * Tajriba: ota-jarayondagi `close(fd[1])` qatorini izohga oling va dasturni ishga tushiring. Nima bo'ladi? `Ctrl+C` bilan to'xtating. **Natija:** dastur kodi, ikkala natija va tajriba tavsifi. Tajribadagi xatti-harakatni tushuntiring. ### 4.5. Signallar va toza yakunlash (5 ball) **Maqsad:** `SIGTERM` va `SIGKILL` ning farqini amalda ko'rish. * `worker.c` dasturini yozing: u siklda hisoblagichni oshiradi (har 0,1 soniyada), `SIGTERM` yoki `SIGINT` olganda esa hisoblagichni `state.txt` fayliga yozadi va tugaydi. Ishlovchida faqat `volatile sig_atomic_t` bayrog'ini o'rnating. * Uni fonda ishga tushiring, 3 soniyadan keyin `kill -TERM ` yuboring. `state.txt` ni tekshiring. * `state.txt` ni o'chiring, dasturni qayta ishga tushiring va `kill -KILL ` yuboring. `state.txt` bormi? * Ctrl+C bosilganda vaqtinchalik faylini o'chiradigan `cleanup.sh` skriptini `trap` yordamida yozing. **Natija:** ikkala tajriba natijasi va skript matni. Nima uchun `SIGKILL` dan keyin fayl yo'q? ### 4.6. Rejalashtiruvchi va `nice` (5 ball) **Maqsad:** ustuvorlik CPU vaqtining taqsimlanishiga qanday ta'sir qilishini o'lchash. * Ikkita cheksiz jarayonni **bitta yadroda** ishga tushiring: ```bash taskset -c 0 nice -n 0 yes > /dev/null & taskset -c 0 nice -n 19 yes > /dev/null & ``` * `top` da (yoki `ps -o pid,ni,pcpu,cmd -C yes`) ularning `%CPU` qiymatlarini 10 soniya kuzating. * Ikkinchi jarayonning nice qiymatini `renice -n 5 -p ` bilan o'zgartiring va yana kuzating. * `killall yes` bilan to'xtating. **Natija:** har bir holat uchun `%CPU` qiymatlari. CFS/EEVDF da nice 0 ning vazni 1024, nice 5 niki 335, nice 19 niki 15 ekanini bilgan holda kutilgan ulushlarni hisoblang va o'lchanganlari bilan solishtiring. --- ## 5-qism. Keys topshiriqlari ### 5.1. Loyihalash: avtomatik dasturlarni tekshirish tizimi (8 ball) Universitet onlayn imtihon uchun server yaratmoqchi: * bir vaqtda **300 ta talaba** C tilidagi yechimini yuboradi; * har bir yechim kompilyatsiya qilinadi va **10 ta test** bilan ishga tushiriladi; talaba kodi **ishonchsiz**: u cheksiz siklga tushishi, xotirani tugatishi, `fork` bombasini ishga tushirishi mumkin; * natijalar ma'lumotlar bazasiga yoziladi, umumiy statistika (nechta yechim tekshirildi, nechtasi o'tdi) veb-sahifada real vaqtda ko'rsatiladi; * barcha hodisalar bitta jurnal fayliga yoziladi. Quyidagilarni loyihalang va **har bir qarorni asoslang**: * a) Qaysi qismlar alohida **jarayon**, qaysilari **oqim** bo'lishi kerak? Nima uchun? * b) Komponentlar orasida qaysi **IPC** mexanizmlaridan foydalanasiz? * c) Qaysi umumiy ma'lumotlar **sinxronizatsiyani** talab qiladi va qaysi primitiv bilan? * d) Talaba kodini xavfsiz ishga tushirish uchun OT ning qaysi vositalaridan foydalanasiz (vaqt, xotira, jarayonlar soni cheklovlari, signallar)? * e) Tizimda o'zaro bloklanish qayerda paydo bo'lishi mumkin va siz uning oldini qanday olasiz? ### 5.2. Kodni tahlil qilish: xatolarni toping (7 ball) Quyidagi kod ko'p oqimli serverning bir qismi. Unda **kamida 7 ta** jiddiy xato bor (sinxronizatsiya, signallar, IPC, jarayonlar). Ulardan **kamida 5 tasini** toping, har biri uchun nima uchun xato ekanini va qanday oqibatga olib kelishini tushuntiring va tuzatilgan kodni yozing. ```c typedef struct { pthread_mutex_t m; long balance; } account_t; pthread_mutex_t qm = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t qc = PTHREAD_COND_INITIALIZER; int queue_len = 0; long done_jobs = 0; void on_term(int sig) { printf("stopping...\n"); exit(0); } int transfer(account_t *from, account_t *to, long sum) { pthread_mutex_lock(&from->m); pthread_mutex_lock(&to->m); if (from->balance < sum) return -1; from->balance -= sum; to->balance += sum; pthread_mutex_unlock(&to->m); pthread_mutex_unlock(&from->m); return 0; } void take_job(void) { pthread_mutex_lock(&qm); if (queue_len == 0) pthread_cond_wait(&qc, &qm); queue_len--; pthread_mutex_unlock(&qm); } void *worker(void *arg) { for (;;) { take_job(); done_jobs++; } return NULL; } long count_processes(void) { int fd[2]; pipe(fd); if (fork() == 0) { dup2(fd[1], STDOUT_FILENO); execlp("ps", "ps", "aux", (char *)NULL); _exit(127); } char buf[4096]; long lines = 0; ssize_t n; while ((n = read(fd[0], buf, sizeof buf)) > 0) for (ssize_t i = 0; i < n; i++) if (buf[i] == '\n') lines++; return lines; } ``` Ishora: `transfer(&a, &b, …)` va `transfer(&b, &a, …)` bir vaqtda chaqirilishi mumkin; `count_processes` server ishlagan sari minglab marta chaqiriladi. --- ## 6-qism. Murakkab topshiriqlar (ixtiyoriy, bonus) ### 6.1. Buferlash jumbog'i (+5 ball) ```c // buf1.c printf("A"); fork(); printf("B\n"); ``` ```c // buf2.c for (int i = 0; i < 2; i++) { fork(); printf("i=%d\n", i); } ``` * a) `buf1` terminalda nima chop etadi? `A` nima uchun bir marta emas? * b) `buf2` terminalda nechta satr chop etadi? `./buf2 | cat` da-chi? Ikkala holat uchun har bir satr necha marta chiqishini aniq hisoblang va farqni tushuntiring. * c) Ikkala dasturni buferlashdan qat'i nazar har doim "kutilgan" natija beradigan qilib tuzating. ### 6.2. Poygadagi eng kichik natija (+5 ball) Ikki oqim umumiy `counter = 0` ni har biri **5 martadan** oshiradi. Har bir oshirish ikki atomar qadamdan iborat: `LOAD R ← counter` va `STORE counter ← R + 1`. Sinxronizatsiya yo'q. * a) `counter` ning mumkin bo'lgan eng katta yakuniy qiymati qancha? * b) Mumkin bo'lgan **eng kichik** yakuniy qiymat qancha? Bu qiymatga olib keladigan aniq navbatlashuvni ko'rsating. * c) Nima uchun yakuniy qiymat bundan kichik bo'la olmasligini isbotlang.