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