Guruh: 310-19 Talaba: Izzatov Abdumalikxon

oldindan
 
ko'riladigan
 
yoki
 
oldindan
ko'riladigan
bo'ladi. Preemptiv bo'lmagan algoritmlar shunday ishlab
chiqilganki, jarayon ishga tushgandan so'ng, u belgilangan vaqtni
tugatmaguncha, uni oldindan o'tkazib bo'lmaydi, holbuki, preemptiv
rejalashtirish ustuvorlikka asoslanadi, bunda rejalashtiruvchi har qanday
vaqtda yuqori ustuvorlik bo'lganda past ustuvorlikdagi jarayonni oldini olishi
mumkin. jarayon tayyor holatga keladi.
Birinchi kelgan birinchi xizmat (FCFS)
•
Ishlar birinchi kelgan, birinchi bo'lib xizmat ko'rsatish asosida amalga 
oshiriladi.
•
Bu oldindan belgilanmaydigan, oldindan belgilab qo'yilgan rejalashtirish 
algoritmidir.
•
Tushunish va amalga oshirish oson.
•
Uni amalga oshirish FIFO navbatiga asoslangan.
•
O'rtacha kutish vaqti yuqori bo'lgani uchun unumdorligi past.

---

Har bir jarayonning kutish vaqti
quyidagicha -
Jaray
on
Kutish vaqti: xizmat ko'rsatish vaqti -
kelish vaqti
P0
0 - 0 = 0
P1
5 - 1 = 4
P2
8 - 2 = 6
P3
16 - 3 = 13
O'rtacha kutish vaqti: (0+4+6+13) / 4 = 5,75
Keyingi eng qisqa ish (SJN)
•
Bu birinchi navbatda eng qisqa ish
yoki SJF sifatida ham tanilgan
•
Bu oldindan belgilanmaydigan, oldindan belgilab qo'yilgan rejalashtirish
algoritmidir.
•
Kutish vaqtini minimallashtirish uchun eng yaxshi yondashuv.
•
Kerakli protsessor vaqti oldindan ma'lum bo'lgan ommaviy tizimlarda
amalga oshirish oson.
•
Kerakli protsessor vaqti noma'lum bo'lgan interaktiv tizimlarda amalga
oshirish mumkin emas.
•
Protsessor jarayon qancha vaqt olishini oldindan bilishi kerak.
4-topshiriq
Earliest Deadline First (EDF) real vaqt tizimlarida qo'llaniladigan optimal 
dinamik ustuvor rejalashtirish algoritmidir.
U real vaqtda statik va dinamik rejalashtirish uchun ishlatilishi mumkin.
EDF rejalashtirish uchun ishlarga ustuvorliklardan foydalanadi. Mutlaq 
muddatga muvofiq vazifaga ustuvorliklarni belgilaydi. Muddati eng yaqin 
bo'lgan vazifa eng yuqori ustunlikka ega bo'ladi. Ustuvorliklar dinamik tarzda 
belgilanadi va o'zgartiriladi. EDF real vaqt tizimlaridagi boshqa rejalashtirish 
algoritmlariga nisbatan juda samarali. U protsessordan foydalanishni 
taxminan 100% ga etkazishi mumkin, shu bilan birga barcha vazifalarning 
oxirgi muddatlarini kafolatlaydi.

---

EDF yadroning haddan tashqari yuklanishini o'z ichiga oladi. EDFda, agar 
protsessordan foydalanish 100% dan kam bo'lsa, bu barcha vazifalar 
belgilangan muddatga to'g'ri kelganligini anglatadi. EDF optimal mumkin 
bo'lgan jadvalni topadi. Mumkin bo'lgan jadval - bu tizimdagi barcha vazifalar 
belgilangan muddatda bajariladigan jadval. Agar EDF real vaqt tizimidagi 
barcha vazifalar uchun bajarilishi mumkin bo'lgan jadvalni topa olmasa, 
demak, real vaqt tizimlarida boshqa hech qanday vazifalarni rejalashtirish 
algoritmlari bajariladigan jadvalni bera olmaydi. Bajarish uchun tayyor bo'lgan
barcha vazifalar topshiriq bajarilsa, EDFga o'z muddatini e'lon qilish kerak.
EDF rejalashtirish algoritmi vazifalar yoki jarayonlarning davriy bo'lishiga 
muhtoj emas, shuningdek, vazifalar yoki jarayonlar protsessorning qattiq 
portlash vaqtini talab qiladi. EDFda har qanday bajaruvchi vazifa, agar 
muddati oldinroq bo'lgan har qanday boshqa davriy misol bajarishga tayyor 
bo'lsa va faol bo'lsa, oldindan hal qilinishi mumkin. Oldindan foydalanishga 
Earliest Deadline First rejalashtirish algoritmida ruxsat beriladi.
Misol:
P1 va P2 ikkita jarayonni ko'rib chiqing.
P1 davri p 1 = 50
bo'lsin, P1 ning ishlov berish vaqti t 1 = 25 bo'lsin.
P2 davri 2 davr = 75
bo'lsin, P2 ning ishlov berish vaqti t 2 = 30 bo'lsin.
Yechim uchun qadamlar:
1.Pf P1 muddati oldinroq, shuning uchun P1>P2 ustuvorligi.
2.Dastlab P1 ishlaydi va 25 marta bajarilishini yakunlaydi.
3.25 martadan so'ng, P2 50 martagacha bajara boshlaydi, P1 bajara oladi.
4.Endi (P1, P2) = (100, 75) muddatini solishtirganda, P2 bajarishda davom 
etadi.
5.P2 55-daqiqada qayta ishlashni tugatadi.
6.P1 75 vaqtgacha, P2 bajara oladigan vaqtgacha bajara boshlaydi.
7.Endi (P1, P2) = (100, 150) muddatini yana solishtirsak, P1 bajarishda 
davom etadi.

---

8.Yuqoridagi amallarni takrorlang…
9.Nihoyat, 150-da P1 ham, P2 ham bir xil muddatga ega, shuning uchun 
P2 o'zining ishlov berish vaqtigacha bajarilishini davom ettiradi, shundan 
so'ng P1 bajarila boshlaydi.
EDF rejalashtirish algoritmining cheklovlari:
•
Vaqtinchalik ortiqcha yuk muammosi
•
Resurs almashish muammosi
•
Samarali amalga oshirish muammosi
5-topshiriq
Rat
e monotonik rejalashtirish 
Haqiqiy vaqtda operatsion tizimlarning
 
statik 
ustuvor rejalashtirish toifasiga tegishli bo'lgan ustuvor algoritmdir . Bu 
tabiatan preemptivdir. Ustuvorlik ishtirok etayotgan jarayonlarning aylanish 
vaqtiga qarab belgilanadi. Agar jarayon kichik ish vaqtiga ega bo'lsa, u eng 
yuqori ustuvorlikka ega. Shunday qilib, agar yuqori ustuvorlikka ega bo'lgan 
jarayon bajarilishini boshlasa, u boshqa ishlaydigan jarayonlardan ustun 
bo'ladi. Jarayonning ustuvorligi uning davom etadigan davriga teskari 
proportsionaldir.Bu erda n - jarayonlar to'plamidagi jarayonlar soni, Ci - 
jarayonning hisoblash vaqti, Ti - jarayonning ishlash vaqti va U - 
protsessordan foydalanish.
Rate monotonik rejalashtirish algoritmining ishlashini tushunish uchun misol.