Haydab chiqaruvchi va haydab chiqarmaydigan rejalashtirish.
Xaydab chiqarmaydigan rejalashtirishda protsessorni egallagan jarayon toki unga ajratilgan vaqt kvanti to’lguncha yoki o’z ishini tugatganda protsessorni qaytarib beradi.
Xaydab chiqaruvchi rejalashtirishda protsessorni o’qish-yozish yoki boshqa qurilmalarga so’rov bo’lgan xolda qaytarib beradi.
Rejalashtirish algoritmi. Turli sinf masalalari uchun samarali va har hil maqsadlarga erishishga mo’ljallangan ko’p rejalashtirish algoritmi ko’p:
“Birinchi kelganga 1-xizmat ko’rsatiladi”- buning inglizcha nomi hisoblanadi. Bu algoritm eng sodda algoritmlarga kiradi. Sodda qilib aytganda navbat tushunchasini bildiradi. Agar jarayon tayyor holatga o’tgan bo’lsa, RSV, uning RSV siga ko’rsatkich navbat oxiriga qo’yiladi va jarayonlarni bajarish xolatiga o’tqazish navbat boshidan amalga oshiriladi.
2. “Charxpalak” algoritmi. Bu algoritmni inglizcha nomi RR (Round Robin) deb ataladi. Bu algoritm RSV algoritmiga o’xshash, lekan bunda xaydab chiqaruvchi rejim amal qiladi.
Kuyidagi rasmni ko’raylik:
10 dan 100 m.sek gacha fiksirlangan vaqt kvanti berilgan, faraz qilaylik shu vaqt o’tdi.
Misol uchun kuyidagicha resurs talabi bo’lsin va kvant sifatida vqtning 4 birligini qabul qilaylik.
Vaqt intervalida jarayonlarni protsessorni kutishi, bajarilish holatlari
Vaqt birligi
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
R0
|
B
|
B
|
B
|
B
|
T
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
R1
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
|
|
|
|
|
|
|
|
|
|
R2
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
B
|
|
|
|
|
|
|
|
|
|
|
3. “1-qisqa ishlaydigan” algoritmi inglizcha nomi Shortest – Job-Pirst (SJP). Bu algoritmning mohiyati qisqa vaqt talab qiladigan jarayonlarni 1 navbatda bajarish holatidir. Bu SJF algoritmi xam xaydab chiqaruvchi, ham haydab chiqarmaydigan rejada ishlaydi.
Misol: Faraz qilaylik kuyidagi jarayonlar berilgan bo’lsin. Bu misol xaydab chiqarmaydigan rejimda bo’lsin:
Vaqt intervalida jarayonlarni protsessorni kutishi, bajarilish holatlari
Vaqt birligi
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
R0
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
|
|
|
|
|
|
|
R1
|
T
|
B
|
B
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
R2
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
R3
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xaydab chiqarmaydigan rejim uchun umumiy kutish vaqti (4+1+0+9)/32=3,5
SJF algoritmini xaydab chiqaruvchi rejimda ko’ramiz va jarayonlar turli xil momentlarda navbatda paydo bo’lgan xolat uchun:
Misol:
jarayon
|
Navbat.paydo bo’lgan vaqt
|
Protsessorga talab
|
R0
|
0
|
6
|
R1
|
2
|
2
|
R2
|
6
|
7
|
R3
|
0
|
5
|
Vaqt intervalida jarayonlarni protsessorni kutishi, bajarilish holatlari
vaqt
jarayon
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
R0
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
B
|
|
|
|
|
|
|
|
R1
|
|
|
B
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R2
|
|
|
|
|
|
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
R3
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tpi (n+1) = ατ(n)+(P+α)T(n)pi
Ushbu rekurrent formula n+1 qadamdagi jarayon talab qiladigan protsessor vaqtini hisoblash formulasi:
T(n) - n dagi berilgan vaqt
τ(n) - n qadamdagi SRI -0 va 1 oralig’idagi son
α - 0 va 1 oralig’idagi son
Kafolatlangan rejalashtirish algoritmi tizimdagi n–ta jarayonning har biri ajratilgan 1/N uchun protsessor vaqtida bajarishi kafolatlanadi.
Faraz qilaylik jarayonning i= 1 dan N gacha nomerlangan. Ti ,
i- Tizimda bo’lgan vaqti, τ i seans davomida yonga ajratilgan jami protsessor vaqti. Xar bir jarayon Ti /N protsessor vaqtini olish xaqqoniy bo’lar edi. Agar τ i i /N shart yuzaga kelsa i-jarayonga nisbatan bu qancha nohaqlik bo’ladi. τ i >Ti /N bo’lsa i– jarayonga katta imtiyoz beradi.
τ i N/i - haqqoniylik koeffitsienti.
Prioritetli rejalashtirish
SJF va kafolatlangan rejalashtirish prioritetli rejalashtirishning hususiy olatidir.
Prioritetlar 2 xil bo’ladi – statik va dinamik.
Dinamik prioritet – ma’lum bir shartgacha ko’ra o’zgarib turadi.
Statik prioritet - jarayon paydo bo’lib, to tugaguncha o’zgarmaydi.
Xozirgi OSlarda dinamik prioritet qullaniladi.
Prioritet qandaydir sonlar diapazonidir.
M: 0 dan 3 lar gacha. Odatda kichik sonli prioriteti yuqori hisoblanadi. M: 0 yuqori hisoblanadi. Prioritet rejalashtirish 2 hil rejimda amal qilinadi: Haydab chiqaradigan, Xaydab chiqarmaydigan
Misol
jarayon
|
Navbat.paydo bo’lgan vaqt
|
Protsessorga talab
|
Prioritet
|
R0
|
0
|
6
|
4
|
R1
|
2
|
2
|
3
|
R2
|
6
|
7
|
2
|
R3
|
0
|
5
|
1
|
Vaqt intervalida jarayonlarni protsessorni kutishi, bajarilish holatlari
vaqt
jarayon
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
R0
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
B
|
|
|
|
|
|
|
|
R1
|
|
|
B
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R2
|
|
|
|
|
|
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
R3
|
B
|
B
|
B
|
B
|
B
|
B
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ko’p sathli navbatlar
Jarayonlarni guruxlarga ajratish imkoni bo’lgan, ularning xar bir gurux uchun o’z navbatini ajratamiz va bu navbatlar fiksirlangan prioritetga ega bo’ladi. Operatsion tizim jarayon navbatining prioriteti foydalanuvchi jarayonlari prioritetdan yuqori bo’ladi. Misol uchun: oliy o’quv yurtdagi markaziy kompyuterlarning arkaziy serverlari jarayonini ko’p satxli rejalashtirish.
Kuyidagi sxema chizamiz.
Tizim jarayonlari
|
Prioritet – 0, RR
|
Rektor jarayoni
|
Prioritet – 1, RR
|
Prof.-o’qituvchilar jarayoni
|
Prioritet – 2, RR
|
Fon jarayoni
|
Prioritet – 3, FCFS
|
Talabalar jarayoni
|
Prioritet – 4, RR
|
Teskari bog’lanishli ko’p satxli navbatlar sxemasi kuyidagicha:
Navbat, prioritet
RR.kvant 8
|
1-Navbat, prioritet- 1
RR kvant 16
|
2-Navbat, prioritet- 2
RR kvant 32
|
3-Navbat, prioritet- 3
FCFS
|
|
