Scheduling Algorithms (Zamanlama Algoritmaları)

Merhaba arkadaşlar,

İşletim Sistemlerinden devam ediyoruz. Ama az önce, kelepçeleriyle ünlenmiş Kazım fenere gol attı. :) Bu notu ilettikten sonra konumuza başlayalım. Öncelikle scheduling, ya da naı diğer zamanlama, nedir? Scheduling, bekleyen process'lerden hangisinin çalışacağına karar veren mekanizmadır en basit tanımla. Bu kararı vermek için çeşitli algoritmalar tanımlanmış. Sırayla bu algoritmalara göz atacağız. Ama ondan önce iki kavramdan bahsedeyim. Preemptive ve Non-Preemptive.
Preemptive algoritmalarda, bir process seçilir ve belli bir süre çalışmasına müsaade edilir. Bu süre bitince de process askıya alınır ve başka process seçilir ve o çalışmaya başlar artık.
Non-Preemptive algoritmalarda ise yine bir process seçilir. Ancak o process kendi isteği ile sonlanana kadar çalışır. Zaten non-preemptive de kelime olarak kesintisiz demek. Kesintisiz bir şekilde process çalışıyor...
(Bu iki kavramı bana hatırlatan Tanenbaum'un Operating System kitabına atıfta bulunmalıyım)
Algoritmalara geçelim isterseniz...

First Come First Served: En kolay algoritmalardan birisi oluyor kendileri. Non-Preemptive bir algoritmadır. Process'ler hangi sırayla gelirse, o sırada çalışır. Non-Preemptive olduğu için de işini bitirene kadar da çalışır. Bu process'ler "kuyruk"ta tutulur. Gelen process kuyruğun sonuna geçer ve sırasını bekler. Çalışan process ise işi bitince kuyruğun sonuna atılır. Konuya yeni başladık, anlaşılması için bir örnek yapalım hemen.
A-B-C-D processleri olsun. Yazdıldıkları sırada da gelmiş olsunlar.
A:1    B:2    C:3    D:4 ms'de işini yapıyor olsun.
Önce A geldi. 1 ms'de işini halletti. Sistem 1 ms bekledi.
Sonra B geldi. A 1 ms'de işini yaparken B onu bekliyordu. Ardından 2 ms'de de kendi işini halletti. 1+2=3 ms de B process'i için gereken zaman...
Akabinde C geldi. A process'i işini yaparken 1 ms bekledi. Ardından 2 ms de B process'i işini yaparken bekledi. 3 ms'de de kendi işini halletti. 1+2+3=6 ms de C process'i için gereken zaman.
Son olarak D process'i geldi. A process'i işini yaparken 1 ms bekledi. 2 ms de B process'i işini yaparken bekledi. Ardından 3 ms de C process'i için bekledi. Kendisi de 4ms'de işini halletti. 1+2+3+4=10 ms
Her process için ortalama bekleme süresi=1+3+6+10/4=5 ms...

Shortest Job First: Bu algoritma da Non-Preemptive'dir. Süresi daha az olan process önce çalışır. Hangi process'in ne kadar çalışacağı da bilinmelidir bu yüzden, ki en büyük sorunu da budur. Bunu bildiğimizde, işini bitirmek için en fazla zamana ihtiyacı olan process kuyruğun en sonuna atılır. Kısa sürede bitirebilen process olduğu sürece, kuyruğun sonunda bekler, uzun sürede bitirecek olan process'ler... Aynı örneği bu algoritma için de yapalım hemen:

A-B-C-D processleri olsun. Bu algoritmada process'lerin geliş sırası önemsizdir.
A:4    B:2    C:1    D:3 ms'de işini yapıyor olsun. (Diğer sorudan farklı olarak süreleri değiştirdim, aman dikkat!!)
Sistem bakacak ve en kısa sürede işini C process'inin bitirebileceğini görecek(1 ms değeri en küçük değer çünkü). Önce C process'i işini yapacak. 1 ms sürede..
Ardından 2 ms ile B process'i işini yapar. Fazla uzatmayayım, akabinde 3 ms ile D process'i ve en son da 4 ms ile A process'i işini yapar bu algoritmaya göre.

Shortest Remaining Time Next: Bu algoritmada process'in geçmişiyle ilgilenmiyoruz. Process'in işini bir an önce bitirmesi esastır. Yani process'in işini bitirmesine ne kadar kalmış, o önemli. Yalnız bu algoritma Preemptive'dir. Yani belli bir süre verirsin process'e. O sürede yaptıysa ne ala; yoksa kuyruğun en sonuna şutlarız kendilerini. Yeni bir process geldiğinde kuyruğa, hemen hali hazırda çalışmasına izin verdiğimiz process ile karşılaştırırız. Eğer yeni process'in çalışmasını bitirmesi için gerek süre, çalışan process'inkinden daha az ise, çalışan process'i bloklarız ve yeni gelen process'i çalıştırırız. Eğer Non-Preemptive olsaydı, asla bloklayamazdık; çalışan process'in keyfini beklerdik. :)

Yazıma burada ara veriyorum. Okunurluğun düşmemesi önemli. Daha da önemlisi Forza'da gese-febe maçındaki muhtemel kırmızı kart sayısına dair iddialaştık, takip edeyim maçın ikinci yarısını. :)

Yarın görüşürüz..