p0
|
İ
|
İ
|
İ
|
İ
|
H
|
H
|
H
|
H
|
H
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
p1
|
H
|
H
|
H
|
H
|
İ
|
İ
|
İ
|
İ
|
|
|
|
|
|
|
|
|
|
|
p2
|
H
|
H
|
H
|
H
|
H
|
H
|
H
|
H
|
İ
|
|
|
|
|
|
|
|
|
|
Cədvəldə “İ” hərfi icra vəziyyətində yerləşən proses üçün istifadə olunur, “H” hərfi ilə “hazır” vəziyyətdə olan proseslər üçün istifadə olunur, boş qalan xanalar isə bitmiş proseslərə uyğun gəlir. Proseslərin vəziyyətləri uyğun vaxt vahidinin müddəti üçün göstərilmişdir, yəni, 1 nömrəli sütun 0-dan 1-ə qədər olan vaxt müddətinə uyğun olur.
İcra olunmaq üçün birinci olaraq p0 prosesi seçilir. Onun CPU burst müddəti kvant vaxtından böyükdür, buna görə də, proses kvant vaxtının bitməsindən əvvəl, yəni, 4 vaxt vahidi müddətində icra olunur. Bundan sonra o, icraya “hazır” olan proseslər növbəsinin sonuna yerləşdirilir və o, p1, p2, p0 şəklini alır. Növbəti yerinə yetirilən p1 prosesi olacaqdır. Onun icra olunma vaxtı ayrılmış kvant qiyməti ilə üst-üstə düşür, buna görə də, proses bitənə qədər işləyir. İndi “hazır olma” vəziyyətində proseslər növbəsi p2 və p0 kimi iki proseslərdən ibarət olacaqdır. Prosessor p2 prosesi üçün ayrılır. O, onun üçün ayrılan prosessor vaxtının bitməməsinə qədər bitir və növbəti kvantlar həmin vaxta qədər öz işini bitirməmiş yeganə olan p0-a ölçülüb ayrılır. p0 prosesi üçün gözləmə vaxtı (uyğun sətirdə “H” simvollarının sayı) 5 vaxt vahidi, p1 prosesi üçün – 4 vaxt vahidi, p2 prosesi üçün isə - 8 vaxt vahidi təşkil edir. Beləliklə, bu alqoritm üçün gözləmənin orta vaxtı belə olacaqdır - (5+4+8)/3=5,6 (6) vaxt vahidi. Tam yerinə yetirilmə vaxtı p0 üçün (uyğun sətirdə boş olmayan sətirlərin sayı)18 vaxt vahidini, p1 prosesi üçün - 8 vaxt vahidi, p2 prosesi üçün 9 vaxt vahidi təşkil edir. Yerinə yetirilmənin orta tam vaxtı – (18+8+9)/3= 11,6 (6) vaxt vahidi təşkil edəcəkdir.
Çox yüngül bir şəkildə görmək olar ki, gözlənilmənin orta vaxtı və yerinə yetirilmənin orta tam vaxtı proseslərin əks qaydası üçün FCFS alqoritmi üçün uyğun vaxtlardan fərqlənmir və uyğun olaraq, 2 və 8 vaxt vahidlərinə bərabər olur.
RR alqoritminin məhsuldarlığına kvant vaxtının qiyməti güclü təsir göstərir. Kvant vaxtının qiyməti 1-ə bərabər olan və p0, p1, p2 proseslər qaydalı həmin misalı nəzərdən keçirək (cədvəl 3.3-ə bax).
Cədvəl 3.3
|
Vaxt
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
p0
|
İ
|
H
|
H
|
İ
|
H
|
İ
|
H
|
İ
|
H
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
p1
|
H
|
İ
|
H
|
H
|
İ
|
H
|
İ
|
H
|
İ
|
|
|
|
|
|
|
|
|
|
p2
|
H
|
H
|
İ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gözləmə vaxtı p0 prosesi üçün 5 vaxt vahidi, p1 prosesi üçün də 5 vaxt vahidi, p2 prosesi üçün isə -2 vaxt vahidinə bərabər olacaqdır. Bu halda gözləmənin orta vaxtı (5+5+2)/3=4 vaxt vahidi olacaqdır. İcra olunmanın orta tam vaxtı (18+9+3)/3=10 vaxt vahidi olacaqdır.
Hər bir proses özünün CPU burst-ni vaxta görə kəsilmə əmələ gəlməyənə qədər bitirə bildiyi kvant vaxtının çox böyük qiymətlərində RR alqoritmi FCFS alqoitminə çevrilir. Ən kiçik qiymətlərdə isə, elə bir xülya əmələ gəlir ki, n proseslərdən hər birisi məhsuldarlığı real prosessorun məhsuldarlığının 1/n hissəsi olan özünün virtual prosessorunda işləyir. Doğrudur, bu, yalnız proseslərin kontekst olaraq, bir vəziyyətdən digərinə keçməsinə sərf olunan vaxtın nəzərə alınmadığı şəraitdə nəzəri təhlildə mümkün ola bilər. Real şəraitlərdə kvant vaxtının ən kiçik qiymətlərində və uyğun olaraq, kontekst tez-tez bir vəziyyətdən digərinə keçdikdə, qaimə xərcləri bu vəziyyətdə sistem məhsuldarlığını kəskin şəkildə aşağı salır.
Shortest-Job-First (SJF)
FCFS və RR alqoritmlərini nəzərdən keçirtdikdə, biz, icra olunmağa hazır olan proseslərin, proseslər növbəsindəki yerləşmə qaydasının onlar üçün nə qədər əhəmiyyətli olduğunu gördük. Əgər qısa məsələlər növbədə, onun başlanğıcına yaxın yerdə yerləşmişsə, bu zaman bu alqoritmlərin ümumi məhsul-darlığı əhəmiyyətli dərəcədə artır. Əgər biz “hazır olma” vəziyyətində yerləşən proseslər üçün növbəti CPU burst vaxtını bilmiş olsaydıq, o zaman icra olunmaq üçün növbənin başlanğıcında olan prosesi deyil, minimal vaxt müddətli prosesi seçə bilərdik. Əgərsə, bu cür proseslər iki və ya daha çox olarsa, o zaman onlardan birinin seçimi üçün artıq bizə məlum olan FCFS alqoritmdən istifadə etmək olardı. Bu halda vaxtın kvantlanması tətbiq olunmur. Təsvir olunan alqoritm “birincinin ən qısa işi” və ya “Shortest Job First” (SJF ) adını almışdır.
Qısa müddətli planlaşdırma alqoritmi SJF həm sıxışdırılıb çıxarılan, həm də sıxışdırılıb çıxarılmayan ola bilər. Sıxışdırılıb çıxrılmama SJF planlaşdırmada - hesablama sistemində baş verən hadisələrdən asılı olmayaraq, seçilmiş prosesin sərəncamına ona lazım olan bütün vaxt müddətində prosessor verilir. Sıxışdırılıb çıxarılan SJF planlaşdırmada isə seçilmiş prosesin işi zamanı “icraya hazır olma” növbəsində (yenidən törənən və ya təcriddən azad olanlar arasından) yeni proseslərin əmələ gəlməsi nəzərə alınır. Əgər yeni prosesin CPU burst-i icra olunanın CPU burst qalığından kiçikdirsə, o zaman icra olunan proses yenisi tərəfindən sıxışdırılır.
Sıxışdırılıb çıxarılmayan SJF alqoritminin işinin misalını nəzərdən keçirək. Tutaq ki, “hazır olma” vəziyyətində p0, p1, p2 və p3 kimi 4 proses yerləşirlər və onlar üçün onların növbəti CPU burst vaxtları məlumdur. Bu vaxtlar cədvəl 3.4-də verilmişdir.
Cədvəl 3.4
|
Proses
|
p0
|
p1
|
p2
|
p3
|
Növbəti CPU burst müddəti
|
5
|
3
|
7
|
1
|
Əvvəllər olduğu kimi, belə fərz edəcəyik ki, proseslərin bütün fəaliyyəi yalnız bir CPU burst vaxt müddətindən istifadə ilə məhdudlaşır, proseslər giriş-çıxış əməliyyatlarını aparmır və kontekstin dəyişdirilmə vaxtını nəzərə almamaq olar.
Sıxışdırılıb çıxarılmayan SJF alqoritmindən istifadə etdikdə, icra olunmaq üçün birinci olaraq, CPU burst növbəti vaxt müddətinin ən kiçik qiymətinə malik olan p3 seçiləcəkdir. Onun bitməsindən sonra, icra olunmaq üçün p1 prosesi, sonra p0 və nəhayət p2 seçiləcəklər. Bu mənzərə cədvəl 3.5-də əks etdirilmişdir.
Cədvəldən göründüyü kimi, SJF alqoritmi üçün gözləmənin orta vaxtı (4+1+9+0)/4 = 3,5 vaxt vahidi olacaqdır. Yüngül şəkildə hesablamaq olar ki, proseslərin p0, p1, p2, p3 qaydasında FCFS alqoritmi üçün bu qiymət belə olacadır: (1+5+8+15)/4=7 vaxt vahidi, yəni, SJF alqoritmi üçün olandan 2 dəfə böyük olacaqdır.
Cədvəl 3.5
|
Vaxt
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
p0
|
H
|
H
|
H
|
H
|
İ
|
İ
|
İ
|
İ
|
İ
|
|
|
|
|
|
|
|
p1
|
H
|
İ
|
İ
|
İ
|
|
|
|
|
|
|
|
|
|
|
|
|
p2
|
H
|
H
|
H
|
H
|
H
|
H
|
H
|
H
|
H
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
İ
|
p3
|
İ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Göstərmək olar ki, proseslərin verilmiş toplusu üçün (əgər növbədə yeni proseslər əmələ gəlmirsə) SJF alqoritmi sıxışdırılıb çıxarılmayan alqoritmlər sinfi arasında gözləmənin orta vaxtının minimallaşması nöqteyi-nəzərindən optimal hesab olunur.
Sıxışdırılıb çıxarılan SJF planlaşdırma misalının nəzərdən keçirilməsi üçün biz p0, p1, p2 və p3 kimi bir sıra prosesləri götürək, onlar müxtəlif CPU burst vaxtlara malik olsunlar və icra olunmaq üçün hazır olan proseslər növbəsində onların əmələ gəlməsi müxtəlif anlarda baş vermiş olsun. (cədvəl 3.6).
|
