Protsessordan foydalanish (CPU utilization) - maksimal bo‘lishi mumkin bo‘lgan vaqt davrida uni bandlik rejimida saqlash
hisoblanadi. Optimallashtirish mezoni: bu ko‘rsatkichni maksimallashtirish.
Tizimning o‘tkazish qobiliyati (throughput) - vaqt birligi ichida o‘zining bajarilishini tugatadigan jarayonlar soni (o‘rtacha) hisoblanadi.
Jarayonga ishlov berish vaqti (turnaround time) - qandaydir jarayonni bajarilishi uchun zarur bo‘ladigan vaqt hisoblanadi. Optimallash mezoni: bu ko‘rsatkichni minimallashtirish.
Kutish vaqti (waiting time) - jarayon bajarilishga tayyor jarayonlar navbatida kutadigan vaqt hisoblanadi.
Javob vaqti (response time) - interfaol tizimda vazifani bajarilish vaqti eng yaxshi mezon bo‘lmasligi mumkin.
Istalgan optimallashdagi kabi strategiyaga bog‘liq bo‘lmagan holda, barcha mezonlarni bir vaqtda qoniqtirish mumkin emas. Quyida turli rejalashtirish algoritimlarini (yoki strategiyalarini) ko‘rib chiqamiz va ko‘rsatilgan mezonlarning optimalligiga erishish nuqtai nazaridan ularning afzalliklari va kamchiliklarini ko‘rib chiqamiz.
Jarayonlarni rejalashtirish algoritmlari
First-Come-First-Served (FCFS) algoritmi
First-Come-First-Served (kelish tartibida xizmat ko‘rsatish, ya’ni, birinchi kelganga birinchi xizmat ko‘rsatish (FIFO) kabi bir xil) – algoritmi eng oddiy rejalashtirish algoritmi bo‘lib, bunda protsessorning resurslari jarayonlarga ular iste’mol qiladigan resurslarga, xususan, jarayonning bajarilishi uchun talab qilinadigan u bildirgan vaqtga bog‘liq bo‘lmagan holda tizimga kelishi (kirishi) tartibida taqdim etiladi. Bu va boshqa algoritmlarni ko‘rib chiqishda jarayonlarning nomlari va ularning qandaydir vaqt birliklarida ifodalanadigan bajarilish vaqt diapazonlarini Gant diagrammalaridan (Gantt charts) foydalanib aniqlaymiz.
Quyidagi misolni ko‘rib chiqamiz. J1, J2 va J3 jarayonlar quyidagi aktivliklar davrlari bilan ko‘rsatilgan tartibda tizimga kiritilgan bo‘lsin:
2.3- jadval
Jarayon
|
Aktivlik davri
|
J1
|
24
|
J2
|
3
|
J3
|
3
|
U holda ularni rejalashtirish uchun FCFS algoritmidan foydalanishda protsessorni birinchi bo‘lib uzoq bo‘lishiga qaramasdan, birinchi jarayonni oladi. Bu holda protsessorni jarayonlar orasida taqsimlanishi 2.18- rasmda tasvirlangan.
2.18- rasm. FCFS algoritmi bo‘yicha rejalashtirish sxemasi (1- misol)
Shunday qilib, kutish vaqti J1 = 0; J2= 24; J3 = 27 bo‘ladi. O‘rtacha kutish vaqti: (0 + 24 + 27)/3 = 17
Agar jarayonlar tartibi boshqacha - J2, J3, J1 bo‘lsa (tizimga oxirgi kiritilgan jarayon – eng uzoq), u holda ularni rejalashtirish natijasi mutlaqo boshqacha bo‘ladi (2.19- rasm).
2.19- rasm. FCFS algoritmi bo‘yicha rejalashtirish sxemasi (2- misol)
Bu holda jarayonlarni kutish vaqti: J1 = 6; J2 = 0; J3 = 3. O‘rtacha kutish vaqti: (6 + 0 + 3)/3 = 3
Bu natija oldingi natijaga qaraganda ancha yaxshi. Birinchi misol namoyish etgan natija samarasi (convoy effect) – qisqa jarayon
uzoq jarayondan keyin xizmat ko‘rsatiladigan hollarda jarayonlarni o‘rtacha kutish vaqtini ortishi deyiladi.
Shortest Job First (SJF) algoritmi
Shortest Job First (SJF, dastlab eng qisqa vazifani bajarish) algoritmi protsessorni rejalashtirish algoritmi bo‘lib, bunda protsessor birinchi navbatda tizimdagi mavjud jarayonlardan eng qisqasiga beriladi. Bu holda har bir jarayon bilan uning navbatdagi aktivlik davri davomiyligi bog‘lanadi. Bu davomiylik eng qisqa jarayonga birinchi xizmat ko‘rsatilishi uchun ishlatiladi. Bu algoritmni qo‘llanishining ikkita sxemalari bo‘lishi mumkin:
Jarayonlarni uzmasdan – jarayonga protsessor berilayotgan vaqtda uning vaqt kvanti tugamasdan jarayon uzilmasligi kerak.
Jarayonlarni uzish bilan – agar aktivlik vaqti aktiv jarayonning qolgan vaqtidan kichik bo‘lgan yangi jarayon kelsa, aktiv jarayonni to‘xtatish. Bu sxema Shortest-Remaining-Time-First (SRTF – dastlab eng qisqa vaqt) nomi bilan ma’lum.
Ko‘rish qiyin emaski, SJF algoritmi u berilgan jarayonlar to‘plami uchun minimal o‘rtacha kutish vaqtini ta’minlashi mazmunida optimal bo‘ladi. Jarayonlarni uzmasdan SJF algoritmining qo‘llanishiga misolni ko‘rib chiqamiz. Jarayonlar to‘plami, tizimda ularning paydo bo‘lishi vaqtlari va ularning aktivligi vaqtlari quyidagicha:
2.4- jadval
Jarayon
|
Paydo bo‘lish vaqti
|
Aktivlik vaqti
|
J1
|
0.0
|
7
|
J2
|
2.0
|
4
|
J3
|
4.0
|
1
|
J4
|
5.0
|
4
|
Jarayonlarni uzmasdan SJF algoritmi bo‘yicha jarayonlarni rejalashtirish sxemasi 2.20- rasmda keltirilgan.
2.20- rasm. Jarayonlarni uzmasdan SJF algoritmi bo‘yicha jarayonlarni rejalashtirish sxemasi
Bu holda o‘rtacha kutish vaqti = (0 + 6 + 3 + 7)/4 = 4. Endi o‘sha jarayonlarga uzilishli SJF algoritmini qo‘llaymiz va o‘rtacha kutish vaqti qanday o‘zgarishini tahlil qilamiz. Algoritmning qo‘llanishi natijasi 2.21- rasmda tasvirlangan.
2.21- rasm. Jarayonlar uzilishli SJF algoritmi bo‘yicha jarayonlarni rejalashtirish sxemasi
Bu holda tizimga qisqaroq jarayon tushishi momentida jarayonning uzilishi prinsipi bir necha marta qo‘llanadi: 2 momentda 1- jarayon uziladi va qisqaroq 2- jarayon bajarila boshlanadi, 4 momentda 2- jarayon uziladi va qisqaroq 3- jarayon bajarila boshlanadi.
Diagrammadan ko‘rinib turibdiki, jarayonlarning uzilishi prinsipining qo‘llanishi tufayli protsessordagi jarayonning uzluksiz bajarilishi davrlari yonma-yon bo‘lishi va boshqa jarayonlarni bajarilishi davrlarini bilan o‘rin almashishi mumkin.
Bu holda o‘rtacha kutish vaqti = (9 + 1 + 0 +2)/4 = 3, ya’ni kutilganidek, u jarayonlarni uzilishi prinsipi qo‘llanilmasligiga qaraganda kichik bo‘ldi.
Ustuvorliklar bo‘yicha rejalashtirish
Bu algoritmda har bir jarayon bilan uning ustuvorligi (butun son) bog‘lanadi. Protsessor eng katta ustuvorlikli jarayonga beriladi (kichik son yuqoriroq ustuvorlikni bildiradi, ya’ni jarayonning eng yuqori ustuvorligini 1 ga teng deb olamiz).
Bu algoritm oldingi algoritm kabi uzilishli va uzilishsiz variatlarga ega. Shu bilan birga, SJF algoritmiga ustuvorliklar bo‘yicha rejalashtirish sifatida qarash mumkin, unda navbatdagi aktivlik vaqti ustuvorlik hisoblanadi. Ustuvorliklar bo‘yicha rejalashtirishda "ochlik" (starvation) muammosi – past ustuvorlikli jarayonlar hech qachon bajarilmasligi va cheksiz kutadigan vaziyatlar vujudga keladi. Operatsion tizimlarda bu muammoni yechishning
an’anaviy usuli jarayonning ortishini hisobga olish (aging) hisoblanadi. Vaqt o‘tishi bilan jarayonning ustuvorligi tizim orqali oshiriladi.
Round Robin (RR) algoritmi
Round Robin (RR, halqali tizim) algoritmi bu barcha jarayonlarga navbat bo‘yicha bir xil vaqt kvantlarini berish hisoblanadi. Algoritmning nomi AQShdagi ommaviy qarta o‘yinidan kelib chiqadi. Bu algoritmda har bir jarayon protsessor vaqtining uncha katta bo‘lmagan kvanti – odatda 10-100 millisekundni oladi. Bu vaqt tugagandan keyin jarayon uziladi va tayyor jarayonlarni oxiriga joylashtiriladi.
Agar bajarilishga tayyor jarayonlar navbatida n jarayonlar va vaqt kvanti q ga teng bo‘lsa, u holda har bir jarayon 1/n protsessor vaqtini eng kattasi q birlikdan bir marta qismlab oladi. Hech bir jarayon (n-1) q vaqt birligidan ortiq kutmaydi.
Bu algoritmning unumdorligi q koeffitsientga bog‘liq:
agar q yuqori bo‘lsa, u holda algoritm FCFS algoritmga deyarli ekvivalent;
agar q past bo‘lsa, u holda q tarkibiy qayta ulanish vaqtidan katta bo‘lishi kerak, aks holda bitta jarayondan boshqa jarayonga qayta ulanishga ustama sarflar o‘ta katta bo‘ladi.
RR algoritmini qo‘llanilishi misolini ko‘rib chiqamiz. Tizimda aktivlik vaqtli quyidagi jarayonlar mavjud bo‘lsin:
2.5- jadval
Jarayon
|
Aktivlik vaqti
|
J1
|
53
|
J2
|
17
|
J3
|
68
|
J4
|
24
|
q = 20 vaqt kvantili RR algoritm bo‘yicha protsessorni rejalashtirish sxemasi 2.22- rasmda keltirilgan.
2.22- rasm. RR algoritmini qo‘llanishiga misol (q = 20)
Odatda RR algoritmi SJF algoritmga qaraganda yomon aylanish vaqtiga ega (chunki har bir jarayon vaqt kvantlari boshqa jarayonlarga beriladigan vaqtda navbatdagi vaqt kvantini kutishi kerak bo‘ladi), lekin yaxshi javob vaqtiga ega. 2.23- rasmda kontekstni almashtirishlar sonining vaqt kvantiga bog‘liqligi ko‘rsatilgan: kvant qancha kichik bo‘lsa, kontekstni almashtirishlar soni shuncha ko‘p bo‘ladi.
2.23- rasm. Protsessor kvant vaqti va kontekstni almashtirish vaqti
Ko‘p darajali navbat
Binobarin, tizimdagi jarayonlar turli o‘ziga xosliklarga (masalan, paketli va interaktiv) ega bo‘lishi mumkin, amalda operatsion tizimlarda bajarilishga tayyor jarayonlar navbati ikkita navbatlarga bo‘linadi:
asosiy (interaktiv jarayonlar);
fon (paketli jarayonlar).
Har bir navbat o‘z rejalashtirish algoritmiga ega bo‘ladi. Asosiy navbat RR, fon navbat FCFS rejalashtirish algoritmiga ega bo‘ladi. Bu aralash algoritmda navbatlar orasidagi rejalashtirish, ya’ni u yoki bu
navbatdan jarayonlarni tanlash algoritmi zarur bo‘ladi. Navbatlar orasidagi rejalashtirish quyidagi turlarga bo‘linadi:
Qayd etilgan ustuvorlikli – asosiy navbatdan, keyin fon navbatdan barcha jarayonlarga xizmat ko‘rsatish. Bunda “och qolish” ehtimolligi mavjud.
Vaqt oralig‘ini ajratish – har bir navbat qandaydir protsessor vaqt oralig‘ini oladi, u jarayonlar orasida taqsimlanishi mumkin, masalan, 80% asosiy navbatdagi RRga va 20% fon navbatdagi FCFSga taqsimlanishi mumkin.
2.24- rasmda jarayonlarni rejalashtirish uchun ko‘p darajali navbat tuzilmasiga real misol keltirilgan.
2.24- rasm. Ko‘p darajali navbatni rejalashtirishga misol
Eng yuqori ustuvorlikka tizim jarayonlari ega, keyin interaktiv jarayonlar, undan past ustuvorlikka esa matn tahrirlagichlari chaqiriladigan interaktiv jarayonlarga ega (ular foydalanuvchilarning sekin ishlashi tufayli sezilarli katta vaqtni egallaydi), keyin paketli va nihoyat talabalar jarayonlari keladi.
Real vaziyat shunday, lekin muallif talabalar jarayonlarini “kamsitilishini” to‘g‘ri hisoblamaydi. Aynan ularga tizim jarayonlaridan keyingi ustuvorlikni, masalan, diplom ishlarini himoya qilishdan oldingi davrda berish kerak bo‘ladi.
|
