Scheduling Algorithms vol.2

Tekrar merhaba herkese,

Zamanlama algoritmalarında kaldığımız yerden ediyoruz. Eğer bundan önceki yazıyı okumadan bu kayda yönlendiyseniz:  http://gurkanalkan.blogspot.com/2011/03/scheduling-algorithms-zamanlama.html bağlantısına bir göz atın derim.

Round Robin Scheduling: Bu algoritmada tüm process'lere belli bir quantum süresi veriliyor. Eğer çalışan process'in quantum süresi dolduğunda hala çalışıyorsa, bloklanır ve listenin sonuna atılır; sıradaki process çalışmaya başlar. Bu algoritma tüm process'lerin aynı öncelikte olduğunu farz eder. Püf noktası ise quantum sürelerinin uzunluğudur. Çünkü bir process'ten başka bir process'e geçme işlemi de bayağı masraflı bir işlemdir. Eğer quantum süreleri kısa tutulursa, sürekli process'ler arasında geçişler olur ve bunun için de işlemci fazladan zaman ayırmış olur. Eğer quantum süresi bir uzun tutulursa, çalışan process için sorun yoktur belki ama bekleyen process'lere çok geç cevap verilmiş olur.

Priority Scheduling: Process'lere öncelik verir ve o önceliklere göre de çalıştırır. Önceliği yüksek olan çalışır haliyle. Ancak "priority"si, yani önceliği, yüksek olan process sürekli çalışır mı bu mantıkla? Eğer siz bir önlem almazsanız, çalışır. Bu yüzden şöyle bir yol izlenebilinir: her process'e belli bir quantum süresi verirsiniz. Quantum süresi dolan process'in de önceliğini düşürürsünüz. Örnek vereli hemen.
A:4   B:3   C:2 önceliklerine sahip olsun.
A process'inin quantum süresi dolunca, A'nın önceliği 3'e düşürülür. Ve B'nin arkasına geçer hemen. B çalışır, önceliği 2'ye düşer ve C process'inin arkasına geçer. Ardından A process(en son 3 olmuştu önceliği)'i çalışır ve önceliği 2'ye düşer, o da C ve B'nin arkasına yerleşir. Bu şekilde tüm process'ler çalıştırılmış olur. Tanenbaum ise her saat vuruşunda önceliği azaltma fikrini öne sürüyor ancak benim anlattığım yöntem daha makul görünüyor...

Guaranteed Scheduling: Process'leri schedule etmeden inceliyor bu algoritma; ne kadar quantum süresi vermiş ve o process bunun ne kadarını kullanmış vs. Verilen zamanın daha azını kullanmışsa, o process'in önceliği olur. Şöyle ki:
A:5 ms'de işini halledebiliyor.
B:10 ms'de işini halledebiliyor.
C:20 ms'de işini halledebiliyor.
Her birine 10 ms'lik quantum süresi atadığımızda: A'nın oranı 5/10=0,5 olur. Aynı hesapla B'nin oranı 1, C process'ininki de 2 olur. En kısa sürede A process'i işini halledeceğinden de öncelik onundur. Ne zamana kadar? Ta ki A process'i çok çalışıp da B process'inin oranına gelinceye dek...

Lottery Scheduling: Adından da belli olacağı üzere tamamen piyangonun size vurmasıyla alakalı. :) Her process'e bir bilet veriyor bu algoritma. Ve random olarak bir process'i seçiyorsunuz, kimin bileti çıkarsa artık.. Bir process istediği kadar bilete sahip olabilir ve ne kadar çok bileti olursa, şansı da o kadar yüksek olur. :) Bildiğiniz piyango olayı, ismi de o yüzden öyle. Örnek verelim hemen:
A-8 bilet
B-5 bilet
C-7 bilet
Random olarak bir bileti seçeceğiz ve bu bilet kimdeyse, o process çalışacak. A process'i en şanslısı çünkü 8 bileti var. Olay bu kadar basit. Random Number Generator mantığı lazım buraya ki daha adil ve düzgün bir dağıtım olabilsin process'ler arasında. Klasik kullanım yeri örneğini ben de vereyim: video server'lar. Saniyede kaç frame alacağına bakıp, process'lere o kadar bilet verirsiniz...

Fair-Share Scheduling: Bu algoritma process'ten ziyade kullancılarını göz önüne alır. O yüzden önce hangi kullanıcıda kaç process var olduğu belirlenmelidir. Örneğin birinci kullanıcının çok fazla process'i vardır, ikinci kullanıcının ise nispeten daha az... Bu durumda birinci kullanıcı daha fazla CPU zamanını kullanacaktır. İşte, yine adından da anlayacağınız, Fair-Share'den yana bu algoritma buna karşı çıkıyor ve diyor ki: madem iki kullanıcı var, CPU zamanını %50-%50 paylaştıralım.
Örnek verelim hemen. 1nci kullanıcının process'leri:A-B-C. 2nci kullanıcının processleri:D-E olsun.
Çalışma şekli şöyle olacaktır.
A-D-B-E-C-D-A-E-B-D-C-E........
Yani bir process ilk kullanıcıdan, bir process de ikinci kullanıcıdan gelir.

Three Level Scheduling: 3 aşamalı bir algoritmadır kendileri.
1.Admission Scheduler: Job'lar sisteme gelir ve kuyrukta bekletilir bu aşamada. Hangilerinin alınacağına karar verilir. Buna herhangi bir algoritma ile karar verilir.
2. Memory Scheduler: Hangi process'lerin memory'de kalacağı, hangilerinin diske yazılacağını belirleyen aşamadır.
3. CPU Scheduler: Yine herhangi bir algoritma kullanılarak, hangi process'in çalışacağına karar verilir.

Konumuz burada son buluyor. Sonra görüşürüz..

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..