Merhabalar. Hemmen konuya başlayalım..
Ama öncelikle şunu söylemeliyim ki bu yazıyı okumadan önce processler konusunda ön bilgiye ihtiyacınız olabilir.
İyi okumalar..
Scheduling dilimize zamanlama olarak çeviriliyor. Bir kaç process işlemciye geldiğinde işlemcinin zamanlamasının nasıl yapılacağını yani Cpu Scheduling konusunu anlatacağız.
Bu olay için kullanılan bazı algoritmalar var. Bu algoritmaları anlatmadan önce bunları birbirinden ayıran kriterlerden bahsetmek istiyorum.
CPU Scheduling Algoritmaları Optimizasyon Kriterleri
CPU UTILIZATION : İşlemcinin yoğunluğu, meşguliyeti anlamına gelir.
THROUGHTPUT : Execute işlemi yapılan bir zaman diliminde tamamlanan process sayısı.
TURNAROUND TIME : Bir processin çalıştırılıp bitmesi arasında geçen süre
WAITING TIME : Bir process’in ready list’ te bekleme süresi.
RESPONSE TIME : Üretilen ilk cevap’a kadar geçen süre
Bir CPU Scheduling algoritmasını en iyi yapan durumlar ;
Max CPU Utilızatıon
Max Throughtput
Min Turnaround time
Min Waiting time
Min Response Time
olması durumudur.
CPU SCHEDULING ALGORİTMALARI
Algoritmaları anlatmadan önce processlerin çalışma zamanları ve sıralarını Gantt Chart adındaki bir çizim yöntemi ile çizeceğiz. İsterseniz araştırabilirsiniz.
İlk algoritmamız ile başlayalım;
- First Come – First Served (FCFS) Algoritması
İlk gelen ilk servis edilir diyebiliriz. İşlemciye ilk gelen ilk işlenmeye başlar. O process işini bitirdiğinde bir sonraki devam eder.
Process Burst Time
P1 24
P2 3
P3 3
Yukarıdaki değerlere sahip 3 processimiz olsun. Burst Time çalışma zamanlarını ifade eder.
Diyelimki CPU’muza P1,P2,P3 sırası ile gelsinler.
O zaman bu duruma uygun Gantt Chart’ımız şu şekilde olur ;
[1]
0. sürede çalışmaya başladık. 24 birim P1 process’imiz çalıştı. Daha sonra P2 process’imiz 3 birim çalıştı ve daha sonra ise P3 process’imiz görüldüğü üzere 3 birim çalıştı. Toplamda 3 process 30 birimde bitirilmiş oldu.
Processlerin ortamala bekleme sürelerini hesaplamak istediğimizde;
P1 : 0 , P2 : 24 , P3 : 27 birim beklemiştir.
Ortalama bekleme süresi : (0+24+27)/3 =17 bulunur.
Peki ya sıra P2,P3,P1 olsaydı. Bu sefer ;
[1]
şeklimiz bu şekilde olacaktı.
Bu durumda bekleme süreleri : P1 : 0 , P2 : 3 , P3 : 6 olur.
Ortalama bekleme süreleri ise : (0+3+6)/3 = 3 birim sonucunu elde ederiz.
Bu bir önceki durum daha çok istenilen bir durumdur.
- Shortest Jop First (SJF) Algoritması
Adındanda anlaşılacağı üzere en kısa süren işi en önce yaptığımız bir algoritmadır.
Process setindeki en kısa çalışma süresi olan hangi process ise o önce çalıştırılır. Eğer çalışma süreleri eşit ise yığına önce giren process çalıştıralacaktır.
Bir örnek daha iyi anlayacağız. Aşağıdaki örnekte 4 processimiz var ve çalışma zamanları verilmiştir.
[1]
Gördüğünüz üzere processler şemaya en kısa çalışma süresinden en uzun çalışma süresine doğru sırayla yerleştirilmiştir.
Bekleme zamaları sırayla 3,16,9,0 olduğundan ortalama bekleme süresinin 7 çıktığını görebiliyoruz.
- Shortest Remaining Time First (SRTF)
En küçük olan en önce çalıştırılır ancak processler CPU’ya aynı anda gelmezler.
Gelen yeni process, çalışmakta olan processten küçük çalışma zamanına sahipse çalışan process preemt edilir. Suspend edilir. Yani durdurulur. Eşitse çalışmakta olan process devam eder.
Aşağıda ki örnekte gördüğünüz üzere Arrival Time değeri de bulunmakta. Bu değer process’in CPU ya ulaşma zamanını göstermektedir.
[1]
Bu algoritma biraz karışık gibi görünebilir. Ama dikkatli incelediğinizde kolayca anlayabileceksiniz.
Öncelikle ilk önce P1 process’i gelmiş. P1, 1 birim çalıştıktan sonra P2 geliyor. P1 in geriye kalan çalışma süresi 7 ama gelen P2’nin çalışma süresi 4 birim olduğu için P1 process’i durdurulup P2 process i çalışmaya devam etmiştir. Bir birim sonra P3 gelmiş ama P2’nin kalan çalışma süresi 3 olduğu ve P3’ün çalışma süresi 9 olduğu için küçük olan P2 çalışmaya devam etmiştir. Bir sonraki P4 içinde aynı durum geçerli.
P2 işini bitirdikten sonra durdurulan processlerden en küçük olanı P4 çalışmaya başlar o bitince bir büyük olan o bitince bir büyüğü derken buradan sonra algortima normal SJF(Shortest Jop First Algoritması) gibi çalışır.
Ayrıca burada dikkat edilmesi gereken bir hususta ortalama zamanı hesaplama olayıdır. Dikkat ettiyseniz P1’in bekleme süresini hesaplarken (10-1) yapıyoruz çünkü en son çalışan P1 10 birim beklemesine karşılık o 10 birimin tamamı bekleyerek geçmemiş ilk 1 birimini çalışmıştır yani 9 birim beklemiştir. Ayrıca örneğin P2 de bekleme süresi hesaplanırken (1-1) denilmesinin sebebi P2 tamam 1 birim sonra çalışmaya başlamış ama zaten 1 birim sonra gelmiş olasıdır. Yani hiç vakit kaybetmeden işleme başlamıştır.
Buradanda anlaşılacağı üzere bekleme zamanı hesaplarken Arrival Time değerlerini bekleme zamanından çıkarıyoruz. Çünkü o kadar süre boyunca zaten sırada yoktular.
- Priorty Algoritması
Priorty öncelik anlamına gelmektedir. Buradanda anlayacağınız üzere processleri öncelik sıralarına göre CPU’da işlenmesine izin vereceğiz.
Hemen bir örnek ile açıklayalım.
[1]
Yukarıda gördüğünüz gibi bu algortitmada karşımıza priorty değerleri çıkıyor.
Ve biz processleri şemamıza yerleştirirken başka hiçbir şey’e bakmazsızın priorty sıralarına göre yerleştiriyoruz.
Böylece önceliği en yüksek olan process en önce çalışmış oluyor.
Vee son algoritmamız ;
- Round Robin Algoritması
Bu algoritmada ise her process CPU zamanının küçük bir kısmını kullanır. Bu zamana quantum (kuantum) süresi diyoruz. Bu süre genellikle 10-100ms civarındadır. Bu algoritmada process’e dur deriz durur, çalış deriz çalışır (birazdan göreceğiz). Bu nedenle Response time minimumdur. Arada kalan processlerin hepsi Context-Switching olabilir bu bir dezavantajdır. Bu algoritmanın sorunu kuantum süresini iyi ayarlayabilmektir.
Kısaca context-Switching ; bir process’i durdurp başka bir process’i başlatmaktır. Çok yapıldığında işlemciye yük olur.
Şimdi örneğimizde kolayca anlayacağız :
[1]
Yukarıda görüldüğü üzere kuantum süresi (q) 4 verilmiştir. Ve processler 4 birimlik zaman dilimlerinde sırasıyla çalışmaktadır. Resimde de yazdığı üzere bu algoritmanın Turnaround time’ı SJF(Shortest Jop First) algoritmasından daha uzun bir ortalamaya sahip olmasına karşın Response time’i daha küçüktür.
Okulda öğrendiklerimi anlatmaya çalıştığım bir yazının daha sonuna geldik.
Okuduğunuz için teşekkürler..
İyi çalışmalar..
Kaynaklar :
[1] Operating System Slides Instructor: Ok. Mustafa Gökmen
Muhammed Pektaş Blog 