Önce En Kısa İş (SJF): Önleyici, Önleyici Olmayan Örnek
Nathaniel Brooks
⚡ Akıllı Özet
En Kısa İşlem Önceliği (SJF), bir sonraki çalıştırılacak işlemi en kısa yürütme süresine sahip olan olarak seçen bir CPU zamanlama algoritmasıdır. Öncelikli veya önceliksiz olabilir ve işlemler için ortalama bekleme süresini önemli ölçüde azaltır.
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 veya önleyici olmayabilir. Yürütülmeyi bekleyen diğer işlemlerin ortalama bekleme süresini önemli ölçüde azaltır. SJF'nin tam biçimi Önce En Kısa İş'tir.
Temel olarak iki tür SJF yöntemi vardır:
- Önleyici Olmayan SJF
- Önleyici SJF
SJF Planlamanın Özellikleri
- Tamamlanacak zaman birimi olarak her iş ile ilişkilendirilir.
- Bu algoritma yöntemi, işlerin tamamlanmasını beklemenin kritik olmadığı toplu tip işleme için faydalıdır.
- Daha kısa süren işlerin önce yürütülmesini sağlayarak süreç verimliliğini artırabilir ve böylece işlem süresini kısaltabilir.
- Daha kısa süreli ve genellikle daha kısa işlem süresine sahip işler sunarak iş verimliliğini artırır; bu işler öncelikli olarak yürütülmelidir.
Önleyici Olmayan SJF
Önceliklendirme gerektirmeyen zamanlama yönteminde, bir işleme CPU döngüsü tahsis edildikten sonra, işlem bekleme durumuna geçene veya sonlandırılana kadar bu döngüyü elinde tutar.
Her birinin kendine özgü bir patlama süresi ve varış süresi olan aşağıdaki beş süreci ele alalım.
| İşlem Kuyruğu | Patlama zamanı | Varış zamanı |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
) 0 Adım Zaman = 0 anında, P4 gelir ve yürütmeye başlar.
) 1 Adım Zaman = 1'de, P3 işlemi gelir. Ancak P4'ün tamamlanması için hala 2 yürütme birimine ihtiyacı vardır. Yürütülmeye devam edecektir.
) 2 Adım Zaman = 2'te, P1 süreci gelir ve bekleme kuyruğuna eklenir. P4 yürütmeye devam edecek.
) 3 Adım Zaman = 3'te, P4 işlemi yürütülmesini tamamlayacaktır. P3 ve P1'in patlama süresi karşılaştırılır. P1 işlemi yürütülür çünkü patlama süresi P3'e kıyasla daha azdır.
) 4 Adım Zaman = 4'te, P5 süreci gelir ve bekleme kuyruğuna eklenir. P1 yürütmeye devam edecek.
) 5 Adım Zaman = 5'te, P2 süreci gelir ve bekleme kuyruğuna eklenir. P1 yürütmeye devam edecek.
) 6 Adım Zaman = 9'da, P1 işlemi yürütülmesini tamamlayacaktır. P3, P5 ve P2'nin patlama süresi karşılaştırılır. P2 işlemi, çoğuşma süresi en düşük olduğundan yürütülür.
) 7 Adım Zaman 10'da P2 çalışıyor, P3 ve P5 ise bekleme kuyruğunda bulunuyor.
) 8 Adım Zaman = 11'de P2 işlemi yürütülmesini tamamlayacaktır. P3 ve P5'in patlama süresi karşılaştırılır. P5 işlemi, çoğuşma süresi daha düşük olduğundan yürütülür.
) 9 Adım Zaman = 15'te P5 işlemi yürütülmesini tamamlayacaktır.
) 10 Adım Zaman = 23'te P3 işlemi yürütülmesini tamamlayacaktır.
) 11 Adım Yukarıdaki örnek için ortalama bekleme süresini hesaplayalım.
Wait time P4 = 0 - 0 = 0 P1 = 3 - 2 = 1 P2 = 9 - 5 = 4 P5 = 11 - 4 = 7 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2
Önleyici SJF
Öncelikli SJF planlamasında, işler geldikçe hazır kuyruğuna yerleştirilir. En kısa işlem süresine sahip işlem yürütülmeye başlar. Daha da kısa bir işlem süresine sahip bir işlem gelirse, mevcut işlem kaldırılır veya yürütülmesi durdurulur ve daha kısa süreli işe bir CPU döngüsü tahsis edilir.
Aşağıdaki beş süreci ele alalım:
| İşlem Kuyruğu | Patlama zamanı | Varış zamanı |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
) 0 Adım Zaman = 0 anında, P4 gelir ve yürütmeye başlar.
| İşlem Kuyruğu | Patlama zamanı | Varış zamanı |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
) 1 Adım Zaman = 1'de, P3 işlemi gelir. Ancak P4'ün işlem süresi daha kısadır. Bu nedenle, işlemin yürütülmesine devam edecektir.
) 2 Adım Zaman = 2'de, P1 süreci patlama süresi = 6 ile gelir. Patlama süresi P4'ünkinden daha fazladır. Dolayısıyla P4 yürütmeye devam edecek.
) 3 Adım Zaman = 3'de P4 işlemi yürütülmesini tamamlayacaktır. P3 ve P1'in patlama süresi karşılaştırılır. P1 işlemi, çoğuşma süresi daha düşük olduğundan yürütülür.
) 4 Adım Zaman = 4'te P5 süreci gelecektir. P3, P5 ve P1'in patlama süresi karşılaştırılır. P5 işlemi, çoğuşma süresi en düşük olduğundan yürütülür. P1 işlemi önceliklidir.
| İşlem Kuyruğu | Patlama zamanı | Varış zamanı |
|---|---|---|
| P1 | 5'dan 6'i kaldı | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
) 5 Adım Zaman = 5'te P2 işlemi gelecek. P1, P2, P3 ve P5 işlemlerinin işlem süreleri karşılaştırılıyor. İşlem süresi en kısa olduğu için P2 işlemi yürütülüyor. P5 işlemi ise önceliklendirilerek durduruluyor.
| İşlem Kuyruğu | Patlama zamanı | Varış zamanı |
|---|---|---|
| P1 | 5'dan 6'i kaldı | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3'dan 4'i kaldı | 4 |
) 6 Adım Zaman 6'da P2 çalışıyor.
) 7 Adım Zaman = 7'de P2 işlemi tamamlanır. P1, P3 ve P5 işlemlerinin çalışma süreleri karşılaştırılır. Çalışma süresi daha kısa olduğu için P5 işlemi yürütülür.
| İşlem Kuyruğu | Patlama zamanı | Varış zamanı |
|---|---|---|
| P1 | 5'dan 6'i kaldı | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3'dan 4'i kaldı | 4 |
) 8 Adım Zaman = 10'da P5 işlemi tamamlanacaktır. P1 ve P3 işlemlerinin çalışma süreleri karşılaştırılır. Çalışma süresi daha kısa olduğu için P1 işlemi yürütülecektir.
) 9 Adım Zaman 15'te P1 işlemi tamamlanır. Geriye sadece P3 işlemi kalır. Bu işlem de çalışmaya başlayacaktır.
) 10 Adım Zaman 23'te P3 görevini tamamlar.
) 11 Adım Yukarıdaki örnek için ortalama bekleme süresini hesaplayalım.
Wait time P4 = 0 - 0 = 0 P1 = (3 - 2) + 6 = 7 P2 = 5 - 5 = 0 P5 = 4 - 4 + 2 = 2 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6
SJF'nin Avantajları
SJF yöntemini kullanmanın faydaları/avantajları şunlardır:
- SJF sıklıkla uzun vadeli planlama için kullanılır.
- Bu, FIFO (İlk Giren İlk Çıkar) algoritmasına göre ortalama bekleme süresini azaltır.
- SJF yöntemi, belirli bir işlem kümesi için en düşük ortalama bekleme süresini verir.
- Çalışma sürelerinin önceden bilindiği, toplu olarak çalışan işler için uygundur.
- Uzun vadeli planlamanın toplu sistemi için, iş tanımından bir patlama süresi tahmini elde edilebilir.
- Kısa Süreli Planlama için bir sonraki patlama süresinin değerini tahmin etmemiz gerekir.
- Ortalama işlem süresi açısından muhtemelen en uygun olanıdır.
SJF'nin Dezavantajları/Eksileri
İşte SJF algoritmasının bazı dezavantajları/olumsuz yönleri:
- İşin tamamlanma süresinin daha erken bilinmesi gerekir ancak tahmin edilmesi zordur.
- Genellikle uzun vadeli planlama için toplu sistemde kullanılır.
- SJF uygulanamaz çünkü CPU zamanlaması kısa vadede. Bunun nedeni, yaklaşmakta olan CPU patlamasının uzunluğunu tahmin etmek için özel bir yöntemin bulunmamasıdır.
- Bu algoritma çok uzun geri dönüş sürelerine veya açlığa neden olabilir.
- Bir sürecin veya işin ne kadar süreceği konusunda bilgi gerektirir.
- Bu durum, ortalama işlem süresini azaltmayan bir açlığa yol açar.
- Yaklaşan CPU isteğinin uzunluğunu bilmek zordur.
- Geçen süre kaydedilmelidir, bu da işlemci üzerinde daha fazla yük oluşturur.
