Yazan : Şadi Evren ŞEKER
Bir zamanlama algoritması (CPU Scheduling) şekli olan en kısa iş ilk (Shortest job first, SJF veya Shortest Job Next, SJN) 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.
Algoritma, bazı kaynaklarda, SPF (Shortest Process First , En kısa işlem ilk) olarak da geçmektedir. Ne yazık ki algoritma, bir işlem (process) çalıştırılmadan, tam olarak ne kadar zaman alacağının bilinmemesinden dolayı sadece teorik uygulamalara sahiptir. Ayrıca tam başarının mümkün olmadığı sezgisel (heuristic) algoritmalarla birlikte kullanılması da mümkündür.
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.
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
bu tam olarak nasıl yapılır peki ?
peki bunun preemptive SJF olanını c#da kodları mevcut mu acaba siz hocam??
Yazıda da bahsedildiği üzere SJF algoritması, gerçekleştirilmesi imkansız olan, teorik bir algoritmadır. Bunun sebebi, bir işlemin çalışmadan ne kadar süreceğinin, çalıştırılmadan bilinememesidir. Diğer bir deyişle, işlemci zamanlayıcısı (CPU Scheduler) hangi işlemin çalışacağını, işlemlerin uzunluğuna bakara belirler. Oysaki işletim sistemlerinde, işlemlerin (process) çalışma süreleri bilinemez. Tahmin için bazı istatistiksel yöntemler kullanılsada %100 başarılı bir yöntem bulunmamakta ve kısacası SJF algoritması tam olarak kodlanamamaktadır.
Diğer bir konu da C# dilinde kodlama istiyor olmanız. Bilebildiğim kadarıyla C# dilinde yazılmış bir işletim sistemi henüz yok. İşletim sistemi kodlama için C# dili uygun bir dil değildir.
Başarılar
şey ama ben su yönden istiyordum average time turnaround time gibi hesaplanabilecek şeyler için c# dilince istiyordum. ben mesela sjfnin non-preemtive algorithmasını kendim c#da yaptım ama preemptive algorithmasını yapamadım işin içinden çıkamadım. average time mı falan hesaplamak icin c dilinde java dilinde gördüm bu takım şeyler ama c#’a nasıl uyarlıcam hocam onları_?
Anladığım kadarıyla SJF algoritmasının bir simulasyonunu kodlamak istiyorsunuz. Bu kodun yazılması çok zor olmasa gerek, daha önce C dilinde yazdığım kod elimde var.
Ne mutlu ki şu anda Pardus kullandığım ve C# dilinde kod yazamadığım için bu kod talebinizi cevaplayamıyorum ancak isterseniz C dilindeki kodu yayınlayabilirim veya zaten internette çok sayıdaki yayınlanmış kodlardan faydalanabilirsiniz.
Başarılar
ben c#da form üzerinde kullanarak FCFS VE sjf NON-preemptive yazdım hocam. simdi sjf preemptive yapmaya calısıyorum. acaba c dilindekini ben c# diline ceviremez miyim acaba hocam?
hocam merhaba, Shortest Remainig Time algoritmasını da açıklayıp örnek yapabilir misiniz?
Hocam iyi günler öncellikle siteniz için çok teşekkür ederim gerçekten inanılmaz açıklayıcı ve anlaşılır ve sade bir site oluşturmuşsunuz çok işime yaradı fakat kafamı karıştıran bir problem var.Şimdi yazınızda SJF nin non preemptive olduğunu söylemişsiniz bunu anladım ancak aşağıda yorumlarda ise preemptive demişsiniz daha doğrusu algoritma istendiğinde preemptive istendiğinde non preemptive gibi davranabildiğini söylemişsiniz sanırım ya da ben mi yanlış anladım eğer böyle davranabiliyorsa bu nasıl gerçekleşiyor acaba açıklayabilirseniz çok sevinirim şimdiden Teşekkürler…
SJF non-preemptive’dir. özel durumlarda preemptive olarak tasarlanabilir (yeni iş gelmesi gibi durumlarda schedular’ın tetiklenmesi olabilir ancak siz genel olarak non-preemptive (yani işe başladığında bitene kadar başka işin cpu’ya verilmeyeceğini) kabul edebilirsiniz).
Başarılar