HASAN TEZCAN computer science

CPU Scheduling | Hasan Tezcan

CPU Scheduling

İşlemci zamanlamak, çoklu işlem yapabilen işletim sistemlerinin temelini oluşturur. Bu işletim sistemleri, CPU kullanımını işlemler arasında değiştirerek bilgisayarlarımızı daha üretken hale getirirler.

Bu yazı boyunca temel CPU zamanlama kavramlarından ve bazı CPU zamanlama algoritmalarından bahsedeceğim.

Tek çekirdekli sistemlerde birim zamanda sadece bir işlem çalışabilir. Diğer işlemlerin çalışabilmesi için işlemci çekirdeklerinin boşalması ve tekrar zamanlanabilir hale gelmesi gerekir. Çoklu programlamanın amacı ise işlemci kullanımını en üst düzeye çıkartmaktır.

Basit bilgisayar sistemlerinde bir işlemin başlayabilmesi için diğeri işlemin bitmesi gerekir. Örnek olarak işlemciye gelen bir I/O işlemi aslında o dakikadan itibaren bir bir başka cihazın işlem biriminde çalışıyor olsa da henüz o cihazdan cevap gelmeyip işlem tamamlanmadığından cevap gelene kadar CPU boşa çalışmış olur. Fakat çoklu programlama ile birlikte zamanı daha verimli kullanmaya başlarız. Birkaç işlem aynı anda bellekte barınabilir ve bu sayede bir işlem beklerken işletim sistemi CPU’yu bu işlemden uzaklaştırıp CPU’ya yeni bir işlem verebilir. Böylece işlem gücü boşa harcanmamış olur.

Kaynakların zamanlanması verimlik bakımından çok önemlidir. Özellikle de en temel bilgisayar kaynağı olan işlemcinin zamanlanması bize büyük ölçüde verim sağlayacaktır.

Tekrar Eden CPU ve I/O İşlem Döngüsü

responsive-gif

CPU– I/O Burst Cycle

CPU zamanlamasının başarısı, gözlenen süreç özelliklerine bağlıdır. İşlem yürütme CPU yürütme döngüsünden ve I/O beklemesinden oluşur. İşlemler bu iki durum arasında değişmektedir.

İşlemler yürümeye CPU burst ile başlarlar sonrasında bunu bir I/O burst takip eder ve bunu da bir başka CPU burst ve sonra tekrar I/O burst ve en son sistemin istemesiyle bir CPU burst ile çalışma durdurulur. CPU - I/O burst döngüleri cihazdan cihaza değişseler de Figür 5.2 dekine benzer bir frekans eğrisine sahip olma eğilimindedirler.

CPU zamanının kullanılmasına CPU burst diyoruz.

responsive-gif

CPU Scheduler

İşlemci zamanlayıcısı

Bellekte(RAM) çalışmaya hazır halde bekleyen işlemlerden birini seçerek işlemciyi ona ayırır.

CPU Scheduler kararlarını işlem;

  1. Çalışma(running) durumundan bekleme(waiting) durumuna geçerken,
  2. Çalışma(running) durumundan hazır(ready) durumuna geçişte
  3. Bekleme(waiting) durumundan hazır(ready) durumuna geçişte
  4. Sonlandığında(terminates) verir.

responsive-gif

Dispatcher

İşlemleri Ready Quiden(RAM’den) CPU’ya yükleyen ardından da CPU’daki işlemleri RAM’e kaydeden yapı. Context switch‘i gerçekleştiren birim. Process’leri taşırken kaldığı yerleri kaydedip tekrar çalışma durumunda kaldığı yerden devam etmesini sağlar.(Register’ları, program counter’ları kaldığı yerden devam ettirir.)

Dispatch latency, dispecher’ların bir programı sonlandırıp diğerini başlatması için gereken süre.(gecikme süresi)

Scheduling Criteria

Zamanlama Kriterleri

Bu kriterlerden yalnızca “CPU untilization ve Throughput” değerinin fazla olmasını isteriz. Diğerlerinin değeri ne kadar az ise zamanlama optimizasyonları da o oranda iyi olur.


Scheduling Algorithms

Zamanlama algoritmaları

1. First-Come, First-Served Scheduling, "FCFS"

CPU’nun, işlemleri gelme sırasına göre işleme aldığı zamanlama algoritmasıdır. FCFS’da ilk gelen işlem ilk yapılır, o bittikten sonra sıradaki işlem CPU’ya alınır ve bu düzen böyle devam eder.

responsive-gif

responsive-gif

Convoy effect:

2. Shortest-Job-First Scheduling, "SJF"

İşlemleri burst time’ı en küçük olan ilk sırada olcak şekilde sıralar ve bu sırada işleme koyar. SJF en optimal zamanlama algoritmasıdır. Verilen bir iş kümesi için minimum ortalama bekleme süresini(average waiting time) sağlar.

Bu algoritmada zorluk işlemci kullanım sürelerini(burst time) tahmin etmektir.

responsive-gif

Not: Bu algortimanın çok verimli çalışmasına karşın sorunu bir işlemin çalışmadan önce burst time’ını bilemeyecek olmamızdır. İşlemlerin ancak çalıştıktan sonra ne kadar süre çalıştığını görebiliriz. Ama bunu anlamak için bazı analiz yöntemleri mevcut. Örneğin önceki verilere göre değerlendirimeler yapılabiliyor. Böylece bir sonraki işlemin ne kadar süreceği tahmin edilmeye çalışılıyor.

Determining Length of next CPU

İşlemci kullanım süresinin belirlenmesi

Sadece tahmin edilebilir.

Daha önceki işlemci kulanım süreleri kullanılarak üssel ortalama(exponential averaging) yöntemiyle tahmin edilebilir.

responsive-gif

Shortest-remaining-time-first örneği;

Demin çözdüğümüz soruya bir de ready kuyruğuna gelme zamanını(arrival time) eklersek bu sorunun çözümü nasıl değişir?

responsive-gif

3.Priority Scheduling

Öncelikli Zamanlama

Her bir işleme öncelik sayısı (tamsayı) atanır. CPU en öncelikli olan işleme tahsis edilir.

Preemptive(Kesilebilen işlem) ise işlem devam etse dahi o an daha öncelikli bir işlem geldiğinde yarıda kesilip öncelikli işlem yapılır.

Nonpreemptive(Kesilemeyen işlem)’lerde ise işlem tamamlandıktan sonra en yüksek öncelik kimde ise CPU’yu o işlem kullanır.

Bu algoritmanın yanında getirdiği bir problem vardır. Bu da Starvation problemidir(açlık). Düşük öncelikli bir işlem üzerine ondan daha öncelikli işlemlerin çokça gelmesi durumunda az öncelikli işlemimiz asla CPU’yu kullanamaz. Bu sorunu gidermek için bir çözüm de vardır.

Aging yöntemi(yaşlandırma) önüne aldığı her işlemde bu önceliği az olan işlemimizin önceliğini yavaş yavaş artırırız. Böylece bu önceliksiz işlem de sistem kaynaklarından yararlanabilir.

Priority Scheduling Örneği

responsive-gif

4. Round Robin Scheduling, "RR"

responsive-gif

İşlemlerin belirlenen bir süreye göre sıra sıra işleme sokulmasıdır. İşlemlerin CPU’da kalabileceği maksimum süreye time quantum denir. İşlemler time quantum’a göre sıra sıra işleme girer ve çıkarlar. Sırası gelen işlem ready queue’den alınıp CPU’da işleme konur time quantum süresi bitmesi ardından ready queue’nın sonuna koyulur, ready queue’da hazır bekleyen işlem de CPU’ya verilir. Bir işlemin time quantum’dan önce tamamlanması halinde ise bir sonraki işleme geçilir.

Time quantum’un artması ve azalmasıyla ortaya çıkan bazı problemler var. Bunlar;

Çok yüksek time quantum belirlersek örneğin;

Time quantum’a 1 yıl dersek; bu bir yılda sadece bir işlem çalışacak demek oluyor yani başka bir proses çalışmayacak. Tabi bu durumda işlem bir yıldan önce biteceği için. İşlem bittikten sonra öbür işlem gelecek … , Bir noktadan sonra aslında iş FCFS’a dönmüş oluyor.

"Çok yüksek time quantum belirlersek iş FCFS'a döner."

Time quantum’u çok düşük belirlememiz halinde de CPU’daki context switchlerin maliyeti artamaya başlıyor. Çünkü time quantum’u küçük belirlememiz çok sık process değişikliği yapmamıza sebep oluyor.

"Çok küçük time quantum belirlemek context switch maliyetini artırır."

responsive-gif

Round Robin Scheduling örneği;

responsive-gif

Turnaround Time, Time Quantum ile değişir;

responsive-gif

Hadi bunu kanıtlayalım;

responsive-gif

responsive-gif

responsive-gif

responsive-gif

Multilevel Queue

Şu ana kadar konuştuğumuz priority ve round-robin scheduling alogritmalarında tek bir kuyruk(queue) kullanılıyordu. Ve işlemler önceliklerine göre değerlendirip işleme konuyorlardı.

Multilevel Queue yönteminde ise ready queue bölünerek başka queue’ler oluşturuyor. Bu aşamadan sonra öncelik sıraları işlem bazında değil de kuyruk bazında değerlendirilmeye başlanıyor. Kuyruklardan birinde çok yoğun işlerin görüldüğü işlemler barındırılırken, bir diğer kuyrukta ise işlem yükü pek de ağır olamayan hafif işler tutulmaya başlanıyor.

İşlemleri öncelik sıralarına göre organize ettikten sonra da her bir kuyruk için başka bir zamanlama algoritması kullanabilir oluyoruz. Mesela işlem gücüne çok ihtiyaç duyduğumuz kuyruklarda (CPU yoğun işlemlerde) response time önemli olduğundan buna uygun olan Roud robin algoritmasını tercih ediyoruz. Öte yandan işlem önceliği çok olmayan düşük öncelikli işlemlerin tutulduğu kuyruklarda ise FCFS gibi bir algoritmayı kullanabiliriz.

foreground (interactive), cpu yoğun işlemlerin bulunduğu queue’ler background (batch), CPU’nun nispeten daha az kullanıldığı arkaplan işleri

responsive-gif


NOT: Anlatım boyunca gördüğünüz soru çözümlerinin tümü, tarafımca Figma’da tasarlanmıştır. Herhangi bir hata görmeniz taktirinde bana ulaşabilirsiniz.


> Kaynakça