|
Ustuvorliklar bo‘yicha rejalashtirish
|
| bet | 46/222 | | Sana | 15.05.2024 | | Hajmi | 5,84 Mb. | | #236377 |
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, 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
|
| |
