Earliest Deadline First (edf) cpu rejalashtirish algoritmi Earliest Deadline First (edf)

Earliest Deadline First (EDF) CPU rejalashtirish algoritmi
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 qaraganda juda samarali. U protsessordan foydalanishni taxminan 100% ga oshirishi 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 amalga oshirilishi mumkin bo'lgan jadvalni topadi. Mumkin bo'lgan jadval - bu tizimdagi barcha vazifalar belgilangan muddatda bajarilishi. Agar EDF real vaqt tizimidagi barcha vazifalar uchun bajariladigan jadvalni topa olmasa, demak, real vaqt tizimlarida boshqa hech qanday vazifalarni rejalashtirish algoritmlari amalga oshirilishi mumkin bo'lgan 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 vazifani oldindan muddatidan oldinroq boshqa davriy misol bajarishga tayyor bo'lsa va faol bo'lsa, oldindan hal qilinishi mumkin. Earliest Deadline First rejalashtirish algoritmida imtiyozga ruxsat beriladi.
Misol:
P1 va P2 ikkita jarayonni ko'rib chiqing.
P1 davri p ₁ = 50
bo'lsin, P1 ning ishlov berish vaqti t ₁ = 25 bo'lsin.
P2 davri ₂ davr = 75
bo'lsin, P2 ning ishlov berish vaqti t ₂ = 30 bo'lsin.

Yechim uchun qadamlar:

1. 
   Pf P1 muddati oldinroq, shuning uchun P1>P2 ustuvorligi.
   
2. 
   Dastlab P1 ishlaydi va uning bajarilishini 25 marta 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 qayta ishlashni 55-daqiqada yakunlaydi.
   
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