En Kısa İş İlk Planlama nedir?
Önce En Kısa İş (SJF) , bir sonraki yürütme için en küçük yürütme süresine sahip işlemin seçildiği bir algoritmadır. Bu planlama yöntemi önleyici olabilir veya olmayabilir. Yürütülmeyi bekleyen diğer işlemler için ortalama bekleme süresini önemli ölçüde azaltır. SJF'nin tam formu, Önce En Kısa İştir.
Temel olarak iki tür SJF yöntemi vardır:
- Önleyici Olmayan SJF
- Önleyici SJF
Bu İşletim Sistemi eğitiminde şunları öğreneceksiniz:
- En Kısa İş İlk Planlama nedir?
- SJF Çizelgelemesinin Özellikleri
- Önleyici Olmayan SJF
- Önleyici SJF
- SJF'nin avantajları
- SJF'nin Dezavantajları / Eksileri
SJF Çizelgelemesinin Özellikleri
- Tamamlanması gereken bir zaman birimi olarak her işle ilişkilendirilir.
- Bu algoritma yöntemi, işlerin tamamlanmasını beklemenin kritik olmadığı toplu iş tipi işleme için faydalıdır.
- Önce daha kısa işlerin yürütüldüğünden emin olarak süreç verimini artırabilir, dolayısıyla muhtemelen kısa bir geri dönüş süresine sahip olur.
- Çoğunlukla daha kısa bir geri dönüş süresine sahip olan, önce gerçekleştirilmesi gereken daha kısa işler sunarak iş çıktısını iyileştirir.
Önleyici Olmayan SJF
Önleme amaçlı olmayan programlamada, CPU döngüsü işleme tahsis edildiğinde, işlem bekleme durumuna ulaşana veya sonlandırılana kadar onu tutar.
Her biri kendi benzersiz patlama zamanına ve varış saatine sahip olan aşağıdaki beş işlemi düşünün.
| İşlem Sırası | Patlama zamanı | Varış zamanı |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Adım 0) Zaman = 0'da P4 gelir ve yürütmeye başlar.
Adım 1) = 1 anında, Süreç P3 gelir. Ancak P4'ün tamamlanması için hala 2 yürütme birimine ihtiyacı var. Yürütmeye devam edecek.
Adım 2) Zaman = 2'de, P1 işlemi gelir ve bekleme kuyruğuna eklenir. P4 yürütmeye devam edecek.
Adım 3) Zaman = 3 olduğunda, P4 süreci yürütmeyi bitirecektir. P3 ve P1'in patlama zamanı karşılaştırılır. Proses P1, çoğuşma süresi P3'e kıyasla daha az olduğu için yürütülür.
Adım 4) Zaman = 4'te, P5 süreci gelir ve bekleme kuyruğuna eklenir. P1 yürütmeye devam edecek.
Adım 5) Zaman = 5'te, P2 süreci gelir ve bekleme kuyruğuna eklenir. P1 yürütmeye devam edecek.
Adım 6) Zaman = 9'da, P1 işlemi yürütmeyi bitirecektir. P3, P5 ve P2'nin patlama zamanları karşılaştırılır. İşlem P2, çoğuşma süresi en düşük olduğu için yürütülür.
Adım 7) Zaman = 10'da P2 yürütülmektedir ve P3 ve P5 bekleme kuyruğundadır.
Adım 8) Zaman = 11 olduğunda, P2 işlemi yürütmeyi bitirecektir. P3 ve P5'in patlama zamanı karşılaştırılır. Proses P5, çoğuşma süresi daha düşük olduğu için yürütülür.
Adım 9) Zaman = 15 olduğunda, P5 süreci yürütmeyi bitirecektir.
Adım 10) Zaman = 23 olduğunda, P3 süreci yürütmeyi bitirecektir.
Adım 11) Yukarıdaki örnek için ortalama bekleme süresini hesaplayalım.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Önleyici SJF
Preemptive SJF Scheduling'de işler geldikçe hazır kuyruğa alınır. En kısa patlama süresine sahip bir işlem yürütmeye başlar. Daha kısa patlama süresine sahip bir işlem gelirse, mevcut işlem kaldırılır veya yürütmeden engellenir ve daha kısa olan işe CPU döngüsü tahsis edilir.
Aşağıdaki beş süreci düşünün:
| İşlem Sırası | Patlama zamanı | Varış zamanı |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Adım 0) Zaman = 0'da P4 gelir ve yürütmeye başlar.
| İşlem Sırası | Patlama zamanı | Varış zamanı |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Adım 1) = 1 anında, Süreç P3 gelir. Ancak, P4 daha kısa bir patlama süresine sahiptir. Yürütmeye devam edecek.
Adım 2) Zaman = 2'de, P1 işlemi çoğuşma süresi = 6 ile gelir. Çoğuşma süresi P4'ünkinden daha fazladır. Bu nedenle, P4 yürütmeye devam edecek.
Adım 3) Zaman = 3 olduğunda, P4 süreci yürütmeyi bitirecektir. P3 ve P1'in patlama zamanı karşılaştırılır. Proses P1, çoğuşma süresi daha düşük olduğu için yürütülür.
Adım 4) Zaman = 4'te, P5 süreci gelecektir. P3, P5 ve P1'in patlama zamanı karşılaştırılır. Proses P5, çoğuşma süresi en düşük olduğu için yürütülür. P1 işlemi önceliklidir.
| İşlem Sırası | Patlama zamanı | Varış zamanı |
| P1 | 6'da 5 kaldı | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Adım 5) Zaman = 5'te, P2 süreci gelecektir. P1, P2, P3 ve P5'in patlama zamanı karşılaştırılır. İşlem P2, çoğuşma süresi en az olduğu için yürütülür. İşlem P5 önceliklidir.
| İşlem Sırası | Patlama zamanı | Varış zamanı |
| P1 | 6'da 5 kaldı | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4'ün 3'ü kaldı | 4 |
Adım 6) Zaman = 6'da P2 yürütülüyor.
Adım 7) Zaman = 7'de, P2 yürütmeyi bitirir. P1, P3 ve P5'in patlama zamanı karşılaştırılır. Proses P5, çoğuşma süresi daha az olduğu için yürütülür.
| İşlem Sırası | Patlama zamanı | Varış zamanı |
| P1 | 6'da 5 kaldı | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4'ün 3'ü kaldı | 4 |
Adım 8) Zaman = 10 olduğunda, P5 yürütmeyi bitirecektir. P1 ve P3'ün patlama zamanı karşılaştırılır. Proses P1, çoğuşma süresi daha az olduğu için yürütülür.
Adım 9) Zaman = 15 olduğunda, P1 yürütmeyi bitirir. P3, kalan tek işlemdir. Yürütmeye başlayacak.
Adım 10) Zaman = 23 olduğunda, P3 yürütmeyi bitirir.
Adım 11) Yukarıdaki örnek için ortalama bekleme süresini hesaplayalım.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
SJF'nin avantajları
İşte SJF yöntemini kullanmanın faydaları / artıları:
- SJF, uzun vadeli çizelgeleme için sıklıkla kullanılır.
- FIFO (İlk Giren İlk Çıkar) algoritmasına göre ortalama bekleme süresini azaltır.
- SJF yöntemi, belirli bir süreç kümesi için en düşük ortalama bekleme süresini verir.
- Çalışma sürelerinin önceden bilindiği toplu olarak yürütülen işler için uygundur.
- Uzun vadeli çizelgelemenin parti sistemi için, iş tanımından bir çoğuşma süresi tahmini elde edilebilir.
- Kısa Süreli Çizelgeleme için, bir sonraki patlama zamanının değerini tahmin etmemiz gerekir.
- Ortalama geri dönüş süresi açısından muhtemelen optimal.
SJF'nin Dezavantajları / Eksileri
İşte SJF algoritmasının bazı dezavantajları / eksileri:
- İşin tamamlanma süresi daha erken bilinmelidir, ancak tahmin edilmesi zordur.
- Genellikle uzun vadeli çizelgeleme için bir toplu sistemde kullanılır.
- Kısa vadeli CPU planlaması için SJF uygulanamaz. Bunun nedeni, yaklaşan CPU patlamasının uzunluğunu tahmin etmek için belirli bir yöntem olmamasıdır.
- Bu algoritma, çok uzun geri dönüş sürelerine veya açlıktan ölmeye neden olabilir.
- Bir sürecin veya işin ne kadar süreceği bilgisi gerektirir.
- Ortalama geri dönüş süresini azaltmayan açlığa yol açar.
- Yaklaşan CPU talebinin uzunluğunu bilmek zor.
- İşlemcide daha fazla ek yüke neden olan geçen süre kaydedilmelidir.
Özet
- SJF, en küçük yürütme süresine sahip sürecin bir sonraki yürütme için seçildiği bir algoritmadır.
- SJF Çizelgeleme, tamamlanması gereken bir zaman birimi olarak her işle ilişkilendirilir.
- Bu algoritma yöntemi, işlerin tamamlanmasını beklemenin kritik olmadığı toplu iş tipi işleme için faydalıdır.
- Temel olarak iki tür SJF yöntemi vardır: 1) Önleyici Olmayan SJF ve 2) Önleyici SJF.
- Önleme amaçlı olmayan programlamada, CPU döngüsü işleme tahsis edildiğinde, işlem bekleme durumuna ulaşana veya sonlandırılana kadar onu tutar.
- Preemptive SJF Scheduling'de işler geldikçe hazır kuyruğa alınır.
- Kısa burst süreli bir işlem başlasa da, mevcut işlem kaldırılır veya yürütmeden engellenir ve daha kısa olan iş 1. yürütülür.
- SJF, uzun vadeli çizelgeleme için sıklıkla kullanılır.
- FIFO (İlk Giren İlk Çıkar) algoritmasına göre ortalama bekleme süresini azaltır.
- SJF planlamasında, İşin tamamlanma süresi önceden bilinmelidir, ancak tahmin edilmesi zordur.
- Kısa vadeli CPU planlaması için SJF uygulanamaz. Bunun nedeni, yaklaşan CPU patlamasının uzunluğunu tahmin etmek için belirli bir yöntem olmamasıdır.