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
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
- Visual Basic ile Gösterici (Pointer) Kullanımı
- Hasse Çizgeleri (Hasse Diagrams)
- Zeki Vekiller (Akıllı Ajanlar, Intelligent Agents, Zeki Etmenler )
- Integral Kriptoanalizi ( Toplam Tecessüsü , Integral Cryptoanalysis)
- Diferansiyel Kriptoanalizi ( Fark Tecessüsü , Differential Cryptoanalysis)
- Sierpinski Üçgeni (Sierpinski Triangle)
- C ile programlamaya giriş final sınavı çözümleri
- Çok Seviyeli Sıralar (Multi Level Queues)
- Çift Özetleme (Double Hashing)
- İkinci Dereceden Sondalama (Quadratic Probing)
Yapılan Son Yorumlar
- Abdurrahman ulusoy: merhaba hocam. gelişigüzel...
- Oguz Okutan: Merhaba hocam.. Fonksiyonlarda degere göre...
- Şadi Evren ŞEKER: Null, NULL, nil veya null olarak...
- Fatih Kabakci: hocam merhabalar,...
- kara: Çok güzel anlatılmış gerçekten teşekkürler...
- Şadi Evren ŞEKER: Bahsettiğiniz şekil dönüşümü...
- Caner: Kullanıcıdan açı girdisi almıyorsanız...
- Furkan Yediyildiz: Algoritmanin mantigi cok güzel...
- havva: çok sağolun çok güzel açıklamalar var tşk...
- Şadi Evren ŞEKER: typedef komutu, bir yapıdan yeni bir...
- fatih kabakci: hocam ben structures ile ilgili bir sorum...
- Şadi Evren ŞEKER: evet, yukarıda açıklanan, herhangi...
- Abdurrahman ulusoy: fi açısından teta kadar döndürme...
- Şadi Evren ŞEKER: Hayır yok, bir noktanın, herhangi...
- Abdurrahman ulusoy: Bu durumda yukarıdaki formüllerin...
- Abdurrahman ulusoy: Merhaba hocam Üstteki mesajımda...
- mustafa ekmekcioğlu: merhaba şadi bey ben hacettepe...
- Şadi Evren ŞEKER: Talebiniz üzerine...
- Evren Kocaturk: ve bunu matlab üzerinde, gerekli...
- Evren Kocaturk: teşekkürler, işime yarayacak gibi,...
Yakın Yazılar
En Kısa İş İlk (Shortest Job First)
Priority Queue (Öncelik Sırası, Rüçhan Sırası)
Kesintili Zamanlama (Preemptive Scheduling)
Bağlantılar
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…..
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
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..
Ş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.