En Kısa İş İlk (Shortest Job First)

Yazan : Şadi Evren ŞEKER

Bir zamanlama algoritması şekli olan en kısa iş ilk (Shortest job first, SJF) algoritmasında o anda elde bulunan işler biritilmek için gereken süreye göre sıralanırlar. En kısa olan işe öncelik verilerek sırayla işler alınır.

Çalışma mantığı olarak kesintisiz (non-preemptive) bir algoritma olan bu yaklaşımda bir iş başladıktan sonra başka bir işin araya girme şansı yoktur.

Basitçe eldeki işlerin en kısasını yaparak performans artışı sağlamaya çalışır. Ancak algoritmanın bir dez avantajı kıtlık (starvation) doğurma riskidir.

Olayı şöyle düşünelim, elimizde uzunlukları 4,5,6 olan işler olsun. Algoritmamız en kısa olan 4 uzunluğundaki işten başlayacaktır. Ve diyelim ki 4 biter bitmez veya henüz bitmeden uzunluğu 3 olan başka bir iş gelsin. Algoritmamız 5 uzunluğundaki iş yerine daha kısa olan 3 uzunluğundaki işe öncelik verecektir.

Bu süreç böylece sonsuza kadar gidebilir. Yani henüz 5 ve 6 uzunluğundaki işlere sıra gelmeden hep daha kısa olan işlerin gelerek önceliği alması ve 5 ve 6 uzunluğundaki işlere hiçbir zaman sıra gelmemesi söz konusudur.

Bu algoritmanın çalışmasını aşağıdaki örnek için inceleyelim:

İşlem	CPU Zamanı
A	10
B	15
C	7

Yukarıda verilen işlerin aynı anda başladığını ve sıra beklediklerini düşünelim. Algoritmamız öncelikle bu işlemleri uzunluk sırasına koyacak ardından en kısa olan iş ile başlayacaktır. En kısa olan işimiz C işi ve uzunluğu 7′dir o halde çalışma sıramız aşağıdaki şekilde olur:

Zaman	İşlem	Çalışma	Kalan
0	C	7	0
7	A	10	0
17	B	15	0

Yukarıda görüldüğü üzere bir işlem bir kere başladıktan sonra başka işlem araya girmemektedir. Ayrıca en kısa iş her zaman en önce çalışmaktadır.

Okuyucu bu tabloyu round robin ve ilk gelen çalışır algoritmalarındaki çalışma tabloları ile karşılaştırabilir.

« İlk Gelen Çalışır (First Come First Serve, FSFC, FIFO) | Kıtlık (Starvation) »

Yorumlar

Toplam 4 yorum var.

hılkat | 10 May 2009, 20:00
merhabalar,
elımde 4 ,6,10 birimlik işler olsun.4 bırımlık ışın iki birimini yaptıktan sonra 3 bırımlık bır ış gelırse 4 bırımlık işimi tamamlar yoksa (sjf ye gore) 3 bırımlık işimi yapar.dıyelım kı 3 bırımlık işi yaptı tam o sırada 2 bırımlık bır iş parcacıgı daha geldı o zaman 4 bırımlık işin kalan ıkı bırımlık işini mi yapar yoksa yenı gelen 2 bırımlık işi mi yapar?
ilginiz için şimdiden tesekkurler…..
Şadi Evren ŞEKER | 10 May 2009, 22:38
CPU zamanlaması (scheduling) preemptive (kesintili) ve nonpreemptive (kesintisiz) olarak ikiye ayrılır. Şayet kullanılan sjf (shortest job first) algoritması preemptive ise (yani elindeki işi bitirmeden başkasına geçebiliyorsa) sizin verdiğiniz örnekte anlık olarak en küçük işi yapar.

Yani 4 birimlik A,6 birimlik B, 10 birimlik C işleri olsun. Başlangıç için 4 birimlik A işi ile başlayacaktır.
A işinin 2 birimi bittikten sonra (2 birim kaldıktan sonra) yeni bir D işi 2 birimlik olarak gelirse eşit önceliğe sahip iki iş var demektir. Burası tasarıma göre değişmekle birlikte elindeki 2 birimlik işin önceliği olması avantajlıdır çünkü iş değiştirmek maliyetlidir. Ancak yeni geleni almasının SJF algoritmasına göre yanlış olduğu söylenemez.
sonuçta CPU üzerinde çalışan A işi ile devam etmesi daha doğrudur diyebiliriz.

Sizin sorunuzdaki kritik nokta siz işe başlamadan önceki çalışma sürelerini esas alıyorsunuz. Oysaki sistemde her zaman kalan işe bakılır yani A işi 2 birim çalıştıktan sonra artık 4 birimlik iş değil 2 birimlik iştir. CPU zamanlayıcısı (scheduler) geri dönüp çalışmadan önceki süresine bakmaz kalan zamana bakar.

umarım yardımcı olur.

başarılar
Zeynep Şadoglu | 11 May 2009, 12:14
Merhaba
Örnegin sırasıyla 4,3,2 birimlik A,B,C işleri var. Bu işlerden önce A nın 2 birimlik işi yapiılıyor.Sonra B nin işi yapılıp bitiriliyur. dAha sonra Anın 2 birimlik Cnin de 2 birimlik işi kalmış oluyor .SJF algoritmasına göre önce A mı yoksa C mi işlem görür. biraz acele olursa sevinirim. Teşekkürler..
Şadi Evren ŞEKER | 11 May 2009, 13:46
Şayet bahsettiğiniz şekilde ABC işlerinin sırasıyla 432 birimlik işleri varsa ve zamanlama (Scheduling) algoritması SJF ise A işi önce değil C işi önce başlar. Dolayısıyla çalışma sırasıyla:
0. zamanda C işi 2 birim çalışır
2. zamanda B işi 3 birim çalışır
5. zamanda A işi 4 birim çalışır
9. zamanda bütün işler bitmiş olur.

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'En Kısa İş İlk (Shortest Job First)' isimli yazı 19 Nov 2008 tarihinde, saat: 18:22 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 856 defa okunmuştur.

Benzer yazıları işletim sistemleri kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar