9-Ma’ruza. Jarayonlarni rejalashtirish algoritmlari va parametrlari. Semaforalar. Reja

Tayyor jarayonlar navbati (ready queue) – asosiy xotiradagi barcha bajarilishga tayyor bo'lgan jarayonlar to'plamini o'z ichiga oladi va o’zgartiriladigan navbat. Bu navbat tizim bajarilishiga imkon beradigan har bir yangi jarayonni, shuningdek, kiritish-chiqarish yoki kutilgan hodisa sodir bo’lganidan keyingi har qanday jarayonni o’z ichiga oladi.
Kiritish-chiqarishni kutayotgan jarayonlar navbati (device queues) – kiritish-chiqarish qurilmalari ishi natijasini kutib turuvchi jarayonlar to’plami (har bir qurilma o’zining navbatini tashkil qiladi).
Operatsion tizim tomonidan jarayonlarni boshqarish va tizimdagi jarayonlarning xatti-harakatlarini turli navbatlar orasidagi ko'chish sifatida ko'rish mumkin.
4-rasmda tayyor jarayonlar navbatini va kiritish-chiqarish qurilmalariga navbatini hosil qilish sxemasi tasvirlangan.

8-rasm Tayyor jarayonlar navbati va kiritish-chiqarish vurilmalariga navbat.
Tasvirdan ko’rinib turibdiki, tayyor jarayonlar navbatida kiritish-chiqarish tugallangan jarayonlar ham mavjud. Kiritish-chiqarishni kutayotgan yoki uni bajarish imkoniyati bo’lgan jarayonlar (mos qurilmalarni bo’shatish) qurilmaga navbatga qo’yilgan. Ba’zi qurilmalar bo’sh bo’lishi mumkin, boshqalari esa bittadan ko’p jarayon navbatini o’z ichiga olishi mumkin. Shuningdek, navbatni hosil qilishda ma’lumotlarning taqdim etilishi nuqtai nazaridan e’tibor qaratish kerakki. Navbatni hosil qilishning eng foydali usullaridan biri, navbat uchun jarayonning nafaqat boshiga, balki uning davomchisiga ham ko’rsatkich (havola) saqlanib qolishi kerak, bu esa navbatni yanada samarali boshqarish imkonini beradi (masalan, elementni tez qo’shish navbatning oxiridan (davomidan) amalga oshiriladi).
Navbatdagi jarayonning o’rni uning ustivorligi bilan aniqlanadi, bu haqda keyingi mavzularda to’liqroq to’xtalib o’tamiz. Navbatlar bilan ishlash (ma’lumotlar tuzilmasining klassik masalasi) algoritmlari haqida D.Knutning monografiyasi [15]da to’liq bayon qilingan.
Jarayonlarni rejalashtirish va navbatlar bilan ishlash sxemasi 5-rasmda tasvirlangan.

5-rasm. Jarayonlarni rejalashtirishning grafik ifodasi
Tayyor jarayonlar navbatidagi har bir jarayon qachondir protsessorga o’tadi va bajariladi. Bajarilish vaqtida bajarilishning to’xtatilishiga quyidagi holatlar sabab bo’lishi mumkin: sinxron kiritish-chiqarishga so’rov, jarayonga ajratilgan kvant vaqtning buzilishi, uzilish yoki qismjarayonning hosil bo’lishi. Oxirgi holat asosiy tushuntirishlarni talab qiladi.
Klassik UNIX sxemasida, tizimli fork chaqiruvida qismjarayonlarning hosil qilinishida qismjarayonlar uchun yangi virtual xotira maydoni yaratiladi, unga asosiy (ota) jarayonning xotira mazmuni nusxalanadi. Shundan so’ng ota jarayon protsessorni qismjarayonga bo’shatib beradi. Jarayonlarni parallelashtirish strategiyalari haqida keyingi ma’ruzalarda to’xtalamiz.
Jarayonlarni rejalashtirishni bajaruvchi rejalashtiruvchi
Operatsion tizimlarda jarayonlarni rejalashtirish bir nechta rejalashtiruvchilar tomonidan amalga oshiriladi. Ularning har biri o’ziga xos chaqiruv davriyligiga va o’zining aniq yechishi mumkin bo’lgan masalalari bor.
Uzoq muddatli rejalashtiruvchi (topshiriqlarni rejalashtiruvchilar) – qaysi jarayonlarni tayyor jarayonlar navbatiga qo’yish zarurligini aniqlaydi.
Qisqa muddatli rejalashtiruvchi (protsessorni rejalashtiruvchi) – qaysi jarayon navbatda bajarilishi kerak va qaysi jarayon protsessorga uzatilishi zarurligini aniqlaydi.
Tizimda vaqtni taqsimlash tartibini (rejimini) tatbiq etish uchun tizimga jarayonlarni chiqarish (diskka) va joylashtirish (xotiraga) rejalashtiruvchilarini qo’shish mumkin, bular qaysi foydalanuvchi jarayonlari xotiraga yuklanishi yoki diskka chiqarilishi zarurligini aniqlaydi. Bunday rejalashtiruvchilar qo’shilgan tizimning ishlash sxemasi 6-rasmda tasvirlangan.

6-rasm. Tizimga chiqarish va joylashtirish (yuklash) rejalashtiruvchilarini qo’shish sxemasi.
Rejalashtiruvchi va jarayonlar xususiyatlari. Har bir rejalashtiruvchi hra bir jarayon kabi o’zining hatti-harakatlari bilan alohida xususiyatlarga ega.
Qisqa muddatli rejalashtiruvchi tez-tez chaqiriladi, hech bo’lmaganda protsessorning navbatdagi kvant vaqtining buzilishidan oldin. Shuning uchun ham bu juda tez bo’lishi va iloji boricha samarali bajarilishi lozim. Bunday bo’lmasligi mumkin emas, masalan, ushbu rejalashtiruvchining ishlash vaqti kvant vaqtning o’zi bilan taqqoslanadigan bo’lsa – qo’shimcha xarajatlar (resurslar) juda katta bo’lib ketadi.
Uzoq muddatli rejalashtiruvchilar nisbatan kamdan-kam chaqiriladi, chunki tizim tezkor jarayonni tayyor jarayonlar navbatiga o’tkazish to’g’risida qaror qabul qilmaydi. Shuning uchun, u nisbatan sekin ishlashi mumkin, samarali tatbiq etilmaydi.
Ammo, umuman tizimning asosiy vazifasi iloji boricha ko'proq jarayonlarni saqlab qolishdir. Aynan uzoq muddatli rejalashtiruvchilar vaqt birligi ichida tizim xizmat ko’rsatish lozim bo’lgan jarayonlar soni - multidasturlash darajasini (koeffitsientini) aniqlab beradi.
Jarayonlarnining o’zi rejalashtirish nuqtai nazaridan o’zini turlicha tutishi mumkin. Jarayonlar quyidagicha bo’ladi:
Kiritish-chiqarishga yo’naltirilgan (I/O-bound) – hisoblashlarga nisbatan kiritish-chiqarishga ko’p vaqt yo’qotadigan jarayonlar. Bunday jarayonlar protsessorning ko’plab qisqa kvant vaqtini sarflaydi.
Protsessorni ishlatishga yo’naltirilgan (CPU-bound) – asosiy vaqtini hisoblashlarga sarflaydigan jarayonlar. Bunday jarayonlar protsessorning juda kichik uzoq muddatli kvand vaqtini talab qiladi.
Kontekstni almashtirish
Protsessor boshqa jarayonga almashganda, tizim, oldingi jarayoning holatini saqlab qolgan holda, yangi jarayon uchun saqlangan holatni yuklab olishi kerak. Tizimning bunday harakati kontekstni almashtirish (context switch) deb ataladi. Kontekstni almashtirish - bu ortiqcha yuk (overhead), chunki tizim bir jarayondan boshqasiga o'tishda hech qanday foydali ish qilmaydi.
Kontekstni almashtirish vaqti apparat ta’minotiga bog’liq. Yuqorida biz bunday hollarda tizimning zaruriy harakatlarini ko'rib chiqdik - to'xtatilgan jarayonning holatini PCB-da saqlash va qayta tiklanadigan jarayonning holatini PCB-dan tiklash.
Jarayonni hosil qilish - jarayonlar ustida bajariladigan asosiy amallardan hisoblanadi.
Ota jarayon qismjarayonlarni hosil qiladi, ular esa o’z navbatida boshqa jarayonlarni yaratadi, shu bilan jarayonlar daraxti shakllanadi.
Jarayonlarni yaratishda ota jarayon va qismjarayonlar o'rtasida resurslardan hamkorlikda foydalanish, ularni parallel ravishda amalga oshirish imkoniyati, xotiradan foydalanish va adreslash nuqtai nazaridan turli xil yondashuvlar mavjud.
Resurslarni baham ko’rish. Quyidagicha yondoshuvlar mavjud:
- ota-jarayon va qismjarayonlar barcha resurslarni birgalikda ishlatishadi;
- qism jarayonlar ota-jarayon resurslarining bir qismidan foydalanadi;
- ota-jarayon va qismjarayonlar umumiy resurslarga ega bo’lmaydi.
Bajarilish. Quyidagicha yondoshuvlar mavjud:
Ota-jarayon va qismjarayonlar birgalikda bajariladi;
Ota-jarayon qismjarayonlarning yakunlanishini kutadi.
Adreslash va xotiradan foydalanish. Quyidagicha yondoshuvlar mavjud:
- qismjarayonlarning adres maydoni ota-jarayonning adres maydonidan nusxa oladi; qism jarayon unga yuklangan dasturga ega;
- qismjarayon ota-jarayoni bilan bir xil xotira maydonida ishlaydi (engil jarayon).
UNIX tizimida ushbu masalalar quyidagicha hal qilinadi:
fork – bu yangi jarayonni yaratadigan tizim chaqiruvi. U ota-jarayoni xotirasini klonlaydi va qismjarayoni uchun yangi virtual adres maydonini yaratadi. Shundan so'ng, boshqa xotira maydonini yangi dastur bilan almashtirish uchun yana bir tizim chaqiruvi - exec (execve) amalga oshiriladi. Ota-jarayoni o'rniga qismjarayoni ishlashda davom etadi.
7-rasmda UNIX tizimidagi jarayonlar daraxti tasvirlangan.

7-rasm. UNIX tizimidagi jarayonlar daraxti.
Tizim yangidan yuklanishida ildiz jarayon root hosil qilinadi. U o’z navbatida uchta qismjarayonni yaratadi: init – tizimni ishga tushiruvchi; pagedaemon –xotirani sahifali tashkil etishni boshqaruvchi demon-jarayoni (tizimning qayta yuklanishigacha tizimda joylashadigan jarayon); swapper – chiqarish va yuklashni boshqaruvchi jarayon. Tizim ishga tushgandan keyin init jarayoni foydalanuvchi jarayonlarini hosil qiladi. Oxirgisi, o'z navbatida, yangilarini ishga tushirishi mumkin va hokazo.
Jarayon yo’q qilish – bu ham jarayonlar ustida bajariladigan asosiy amallardan biri. Odatda, jarayon oxirigi operatorni bajarganda va tzimli chaqiruv exit yordamida o’zining vakoloti doirasida OT ga murojaat qilganda yakunlanadi. Bunday holda, qismjarayonidan ota-jarayoniga ma'lumotlar uzatilishi mumkin - masalan, qismjarayoni tomonidan yaratilgan fayllar orqali. Jarayon resurslari operatsion tizim tomonidan bo’shatiladi. Ota-jarayon o’z ishi davomida abort (UNIX) tizimli chaqiruvi yordamida qismjarayonlarni yakunlashi mumkin. Bu quyidagi hollarda yuz beradi:
- qismjarayon unga ajratilgan resurslardan oshib ketganda;
- qismjarayonga yuklatilgan masala yechimiga zarurat qolmaganda;
- ota-jarayondan chiqishga to’g’ri kelganda, buning uchun qismjarayonlar o’z ishini yakunlagan bo’lishi shart. OT ota-jarayon ishini yakunlayotgan bo’lsa, qismjarayonning bajarilishda davom etishiga yo’l qo’ymaydi.
Oxirgi yakunlash holati jarayonlarni kaskad usulida yakunlash deb ataladi.