|
Shortest Job First (SJF) algoritmi
|
| bet | 45/222 | | Sana | 15.05.2024 | | Hajmi | 5,84 Mb. | | #236377 |
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.
|
| |
