Resurslarni taqsimlash strategiyasi. Taqsimlanadigan resurslar va ularga murojaat

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:

1. 
   “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:

jarayon	R0	R1	R2	R3
Talab SRI burst	5	3	7	1

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

T_pi (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. T_i ,
i- Tizimda bo’lgan vaqti, τ _i seans davomida yonga ajratilgan jami protsessor vaqti. Xar bir jarayon T_i /N protsessor vaqtini olish xaqqoniy bo’lar edi. Agar τ _i i /N shart yuzaga kelsa i-jarayonga nisbatan bu qancha nohaqlik bo’ladi. τ _i >T_i /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