Telekommunikatsiya injiniringi va kasb ta’limi fakulteti”

Dumaloq Robin (RR)



FCFS algoritmining modifikatsiyasi bu "Dumaloq Robin" ("Dumaloq Robin" - AQShdagi bolalar karuselining bir turi) yoki qisqacha RR deb nomlangan algoritmdir. Aslida, bu xuddi shu algoritm, faqat oldindan rejalashtirish rejimida amalga oshiriladi. Siz tsikl bilan tashkil etilgan tayyor jarayonlarning butun majmuasini tasavvur qilishingiz mumkin - jarayonlar karuselda o'tiradi. Karusel shu tariqa aylanadiki, har bir jarayon protsessor yaqinida kichik vaqt bo'lagi uchun, odatda 10 - 100 millisekundlarda joylashgan (5-rasm). Jarayon protsessor yaqinida bo'lganida, protsessor o'z ixtiyorida bo'ladi va uni bajarish mumkin.

Ushbu algoritm oldingisiga o'xshash tarzda, tayyor holatda bo'lgan jarayonlarni FIFO navbati bilan tartibga solish orqali amalga oshiriladi. Rejalashtiruvchi navbatdagi ijro uchun navbatning boshida joylashgan jarayonni tanlaydi va ma'lum bir vaqt kesimidan keyin uzilish hosil qilish uchun taymerni o'rnatadi.
Jarayonni amalga oshirishda ikkita variant mavjud:
- jarayon talab qiladigan doimiy protsessordan foydalanish vaqti (joriy CPU portlashining qolgan qismi) vaqt bo'lagi davomiyligidan kam yoki unga teng. Keyin jarayon, o'z xohish-irodasi bilan, protsessorni vaqt bo'lagi tugashidan oldin chiqaradi, navbatning boshidanoq bajarish uchun yangi jarayon tanlanadi va taymer yana kvantni sanay boshlaydi.




- protsessorning joriy portlash jarayonining qolgan qismi vaqt bo'lagidan kattaroq. Keyinchalik, bu kvant tugagandan so'ng, jarayon taymer tomonidan to'xtatiladi va bajarishga tayyor bo'lgan jarayonlar navbatining oxiriga qo'yiladi va protsessor uning boshida jarayon tomonidan foydalanish uchun ajratiladi.



Eng qisqa-birinchi-ish (SJF)



FCFS va RR algoritmlarini ko'rib chiqilishidan, ular uchun jarayonlar bajarilish uchun navbatdagi jarayonlarning tartibi qanchalik muhimligi aniq. Agar qisqa vazifalar navbatda uning boshlanishiga yaqinroq bo'lsa, unda ushbu algoritmlarning umumiy ko'rsatkichlari sezilarli darajada oshadi. Agar siz tayyor holatdagi jarayonlar uchun navbatdagi CPU portlash vaqtini bilsangiz, unda jarayonni navbatning boshidan emas, balki protsessor portlashining minimal davomiyligi bilan jarayonni tanlashingiz mumkin. Agar bunday jarayonlar ikki yoki undan ko'p bo'lsa, ulardan birini tanlash uchun bizga allaqachon ma'lum bo'lgan FCFS algoritmidan foydalanish mumkin. Bunday holda vaqtni kvantlash qo'llanilmaydi. Ta'riflangan algoritm birinchi navbatda eng qisqa ish (SJF) deb nomlanadi.

SJF qisqa muddatli rejalashtirish algoritmi oldindan yoki oldindan bo'lmasligi mumkin. Preefektiv bo'lmagan SJF rejalashtirish bilan protsessor tanlangan jarayonga hisoblash tizimidagi voqealardan qat'i nazar, kerakli bo'lgan barcha vaqt davomida beriladi. SJF-ni oldindan rejalashtirish tanlangan jarayon ishlayotganda ishga tayyor navbatda (yangi tug'ilgan yoki qulfdan chiqarilgan) yangi jarayonlarning ko'rinishini hisobga oladi. Agar yangi jarayonning protsessor portlashi ishlayotgan protsessorning qolgan portlashidan kam bo'lsa, u holda yangi jarayon oldindan ishlaydigan bo'ladi.
SJF algoritmini amalga oshirishdagi asosiy qiyinchilik - bu ishlaydigan protsessorlar uchun keyingi CPU portlashining aniq vaqtini bilish imkonsizligidir. Ommaviy tizimlarda ish bajarilishi kerak bo'lgan protsessor vaqtining miqdori foydalanuvchi tomonidan ish yaratilganda belgilanadi. Ushbu parametr qiymati uzoq muddatli SJF rejalashtirishni amalga oshirish uchun ishlatilishi mumkin. Agar foydalanuvchi kerakli vaqtdan ko'proq vaqtni belgilasa, u natijani kutgandan ko'proq kutadi, chunki vazifa keyinchalik tizimga yuklanadi. Agar u ozroq vaqtni belgilasa, topshiriq oxirigacha hisoblanmasligi mumkin. Shunday qilib, ommaviy tizimlarda protsessor vaqtini baholash muammosining echimi foydalanuvchi elkasiga o'tkaziladi. Qisqa muddatli rejalashtirish bilan siz jarayonning tarixiga asoslanib, faqat keyingi CPU portlashining davomiyligini taxmin qilishingiz mumkin.