SJF (Shortest Job First – En Kısa İşletim Süresi Olan Önce) Algoritması
Bu algoritmada CPU boş olduğunda, kalan prosesler içinde çalışma süresi en küçük olan çalışması için işlemciye sunulur. Eğer iki prosesin kalan süreleri aynı ise o zaman FCFS algoritması uygulanır. Ortalama bekleme süresi düşünüldüğünde SJF optimumdur. Verilmiş bir proses serisi için en düşük bekleme sürelerini elde etmiştir.
SJF Türleri:
- Kesintisiz SJF : Eğer CPU bir prosese tahsis edilmişse, CPU işlem zamanı bitmeyince proses kesilemez.
- Kesintili SJF : Eğer CPU işlem zamanı, şu anda çalışan prosesin kalan işlem zamanından küçük olan yeni bir proses sisteme sunulmuşsa, eski proses kesilir. Bu yönteme, SRTF( Shortest Remaining Time First – En kısa işlem zamanı kalan, birinci) yöntem denir.
Örnek 1:
P1, P2, P3, P4 görevleri aşağıdaki ardışıklık ile sunulmuş olduğunu varsayalım. Buna göre kesintisiz SJF yöntemine göre ortalama bekleme süresini bulalım:
Bekleme süresi; P1 = 3; P2 = 9; P3 = 16; P4 = 0
Ortalama bekleme süresi; ( 3 + 9 + 16 + 0) / 4 = 7
Oysa; ilk gelen önce (FCFS) algoritmasıyla işlem yapılmış olsaydı,
Bekleme süresi; P1 = 0; P2 = 6; P3 = 13; P4 = 21
Ortalama bekleme süresi; ( 0 + 6 + 13 + 21) / 4 = 10.5
Örnek 2:
P1, P2, P3, P4 görevleri aşağıdaki ardışıklık ile sunulmuş olduğunu varsayalım. Buna göre kesintisiz SJF yöntemine göre ortalama bekleme süresini bulalım:
Bekleme süresi; P1 = 0; P2 = (8-2)=6; P3 = (7-4)=3; P4 = (12-5)=7
Ortalama bekleme süresi; ( 0 + 6 + 3 + 7) / 4 = 4
Örnek 3:
P1, P2, P3, P4 görevleri aşağıdaki ardışıklık ile sunulmuş olduğunu varsayalım. Buna göre kesintili SJF yöntemine göre ortalama bekleme süresini bulalım:
Doğma süresi en küçük olan P4 ile işleme başlanır. 1. sn’de P2 işlemi doğacaktır. Çalışma süresi çalışan P4 işleminin kalan zamanından küçük olduğu için P4 kesilir ve P2 işlenmeye başlar. 2. sn’de P3 işlemi doğar, fakat P3’ün çalışma süresi çalışan P2 işleminin kalan zamanından küçük olmadığı için işlem kesilmez ve P2 işlemeye devam eder. 3. sn’de P1 işlemi doğar fakat P1’in çalışma süresi çalışan P2 işleminin kalan zamanından küçük olmadığı için işlem kesilmez ve P2 işlemeye devam eder. P2 işlemi bittikten sonra kalan çalışma sürelerinden kısa olan işlem ile devam edilir. Önce P4, sonra P1 ve en son P3 işlenir.
Bekleme süresi; P1 = (8-3)=5; P2 = (1-1)=0; P3 = (16-2)=14; P4 = (0-0+4-1)=3
Ortalama bekleme süresi; ( 5 + 0 + 14 + 3) / 4 = 5.5
Örnek 4:
P1, P2, P3, P4 görevleri aşağıdaki ardışıklık ile sunulmuş olduğunu varsayalım. Buna göre kesintili SJF yöntemine göre ortalama bekleme süresini bulalım:
Doğma süresi en küçük olan P1 ile işleme başlanır. 2. sn’de P2 işlemi doğacaktır. Çalışma süresi çalışan P1 işleminin kalan zamanından küçük olduğu için P1 kesilir ve P2 işlenmeye başlar. 4. sn’de P3 işlemi doğar, çalışma süresi çalışan P2 işleminin kalan zamanından küçük olduğu için P2 kesilir ve P3 işlenmeye başlar 5. sn’de P3 işlemi sonlanır, P4 işlemi doğar. Fakat P2’nin kalan süresi çalışan P4 işleminin kalan zamanından küçük olduğu için işlem P4 kesilir ve P2 işlemeye devam eder. P2 işlemi bittikten sonra kalan çalışma sürelerinden kısa olan işlem ile devam edilir. Önce P4, sonra P1 işlenir.
Bekleme süresi; P1 = (0-0+11-2)=9; P2 = (2-2+5-4)=1; P3 = (4-4)=0; P4 = (7-5)=2
Ortalama bekleme süresi; ( 9 + 1 + 0 + 2) / 4 = 3
Örnek 5:
Bekleme süresi; P0 = 0; P1 = (3-2)=1; P2 = (11-4)=7; P3 = (15-6)=9; P4 = (9-8)=1
Ortalama bekleme süresi; ( 0 + 1 + 7 + 9 + 1) / 5 = 3.6
Örnek 6:
Örnekte verilen proses tablosundaki işlemcilerin SPT stratejisi ile işlemciye alınması:
Proseslerin geliş zamanlarına bakıldığında 0. birim zamanda gelen ilk ve tek prosesin P1 olduğu görülür. Bu sebepten dolayı P1 direkt işlemciye aktarılır.
İşlemci P1′ i çalıştırırken 1 birim zamanın ardından P3, 2 birim zamanın ardından P2 ve 6 birim zaman sonrasında P4 prosesleri giriş yapar, bekleme sırası {P3, P2, P4}. P1 işlemciyi terk ettiği anda işlemciye yüklenecek diğer proses bekleme sırasındaki en düşük işlem süresine sahip olan proses olacaktır. P3, P2 ve P4′ ün işlem süreleri karşılaştırıldığında en düşük işlem süresine sahip olan P4 bekleme sırasından çıkarılıp işlemciye aktarılır.
Ardından biraz önce olduğu gibi kalan diğer 2 prosesin bekleme süreleri karşılaştırılır ve bu süreye göre P2 prosesi bekleme sırasını terk eder.
Son olarak bekleme sırasında kalan son proses P3 işlemciye yönlendirilir.
Bekleme süresi; P1 = 0; P2 = (8-2)=6; P3 = (11-1)=10; P4 = (7-6)=1
Ortalama bekleme süresi; ( 0 + 6 + 10 + 1) / 4 = 4.25
<< LIFO (Last In First Out – Son Gelen Önce) Algoritması | En Kısa İşletim Süresi Kalan Önce (Shortest Remaining Time First) >>
