İşletim Sistemlerinde CPU Zamanlama Algoritmaları

CPU Zamanlaması nedir?

CPU Zamanlama başka bir işlem beklemedeyken hangi işlemin yürütme için CPU'ya sahip olacağını belirleme işlemidir. CPU planlamasının ana görevi, CPU ne zaman boşta kalırsa, işletim sisteminin yürütme için hazır kuyruğunda mevcut olan işlemlerden en az birini seçmesini sağlamaktır. Seçim işlemi CPU zamanlayıcısı tarafından gerçekleştirilecektir. Yürütülmeye hazır olan bellekteki işlemlerden birini seçer.

Bu CPU zamanlama eğitiminde şunları öğreneceksiniz:

CPU Programlama Türleri

İşte iki tür Zamanlama yöntemi:

Önleyici Zamanlama

Önleyici Çizelgeleme'de görevler çoğunlukla önceliklerine göre atanır. Bazen, daha düşük öncelikli görev hala çalışıyor olsa bile, daha yüksek öncelikli bir görevi daha düşük öncelikli başka bir görevden önce çalıştırmak önemlidir. Düşük öncelikli görev bir süre tutulur ve daha yüksek öncelikli görevin yürütülmesini bitirdiğinde devam eder.

Önleyici Olmayan Zamanlama

Bu tür zamanlama yönteminde CPU, belirli bir işleme tahsis edilmiştir. CPU'yu meşgul eden süreç, ya bağlamı değiştirerek ya da sonlandırarak CPU'yu serbest bırakır. Çeşitli donanım platformları için kullanılabilecek tek yöntemdir. Bunun nedeni, önleyici zamanlama gibi özel bir donanıma (örneğin bir zamanlayıcı) ihtiyaç duymamasıdır.

Planlama ne zaman Önleyici veya Önleyici Olmayan?

Planlamanın önleyici mi yoksa önleyici olmayan mı olduğunu belirlemek için şu dört parametreyi göz önünde bulundurun:

  1. Bir işlem, çalışan durumdan bekleme durumuna geçer.
  2. Belirli işlem, çalışan durumdan hazır duruma geçer.
  3. Belirli süreç, bekleme durumundan hazır duruma geçer.
  4. Süreç yürütmesini tamamladı ve sonlandırıldı.

Yalnızca 1. ve 4. koşullar geçerlidir, planlamaya önleyici olmayan denir.

Diğer tüm zamanlamalar önleyicidir.

Önemli CPU zamanlama Terminolojileri

  • Patlama Süresi/Yürütme Süresi: İşlemin yürütmeyi tamamlaması için gereken bir süredir. Aynı zamanda çalışma süresi olarak da adlandırılır.
  • Varış zamanı: bir süreç hazır duruma girdiğinde
  • Bitirme zamanı: işlem tamamlandığında ve sistemden çıkıldığında
  • Çoklu programlama: Hafızada aynı anda bulunabilen birkaç program.
  • Meslekler: Herhangi bir kullanıcı etkileşimi olmayan bir program türüdür.
  • kullanıcı: Kullanıcı etkileşimi olan bir program türüdür.
  • İşlem: Hem iş hem de kullanıcı için kullanılan referanstır.
  • CPU/IO patlama döngüsü: CPU ve G/Ç etkinliği arasında değişen işlem yürütmeyi karakterize eder. CPU süreleri genellikle G/Ç süresinden daha kısadır.

CPU Zamanlama Kriterleri

Bir CPU zamanlama algoritması aşağıdakileri en üst düzeye çıkarmaya ve en aza indirmeye çalışır:

Büyüt:

CPU kullanımı: CPU kullanımı, işletim sisteminin CPU'nun mümkün olduğunca meşgul kalmasını sağlamak için ihtiyaç duyduğu ana görevdir. Yüzde 0 ila 100 arasında değişebilir. Ancak, RTOS için, düşük seviye için yüzde 40 ve yüksek seviye sistem için yüzde 90 arasında değişebilir.

verim: Birim zaman başına yürütmesini tamamlayan işlem sayısı, çıktı olarak bilinir. Bu nedenle, CPU işlemi yürütmekle meşgul olduğunda, o sırada iş yapılır ve birim zamanda tamamlanan işe Verimlilik denir.

Küçültmek:

Bekleme süresi: Bekleme süresi, belirli bir işlemin hazır kuyruğunda beklemesi gereken bir miktardır.

Tepki Süresi: İlk yanıt üretilene kadar talebin gönderildiği süredir.

Geri Dönüş Süresi: Geri dönüş süresi, belirli bir işlemi yürütmek için gereken süredir. Belleğe girmek için beklemek, kuyrukta beklemek ve CPU üzerinde yürütmek için harcanan toplam sürenin hesaplanmasıdır. İşlem teslim süresi ile tamamlanma süresi arasındaki süre, geri dönüş süresidir.

Aralık Zamanlayıcısı

Zamanlayıcı kesintisi, önceden alma ile yakından ilgili bir yöntemdir. Belirli bir işlem CPU tahsisini aldığında, belirli bir aralığa bir zamanlayıcı ayarlanabilir. Hem zamanlayıcı kesintisi hem de önleme, bir işlemi CPU patlaması tamamlanmadan önce CPU'yu geri döndürmeye zorlar.

Çok programlı işletim sistemlerinin çoğu, bir işlemin sistemi sonsuza kadar bağlamasını önlemek için bir tür zamanlayıcı kullanır.

Gönderici nedir?

İşleme CPU'nun kontrolünü sağlayan bir modüldür. Gönderici, her bağlam anahtarında çalışabilmesi için hızlı olmalıdır. Gönderim gecikmesi, CPU zamanlayıcısının bir işlemi durdurmak ve diğerini başlatmak için ihtiyaç duyduğu süredir.

Dispatcher tarafından gerçekleştirilen işlevler:

  • Bağlam Değiştirme
  • Kullanıcı moduna geçiş
  • Yeni yüklenen programda doğru konuma hareket.

CPU zamanlama Algoritması türleri

Temel olarak altı tür süreç çizelgeleme algoritması vardır.

  1. İlk Gelen İlk Servis (FCFS)
  2. Önce En Kısa İş (SJF) Planlaması
  3. En Kısa Kalan Süre
  4. Öncelikli Planlama
  5. Yuvarlak Robin Zamanlama
  6. Çok Düzeyli Kuyruk Planlama

Zamanlama Algoritmaları



Önce gelen alır

İlk Gelene Önce Hizmet, FCFS'nin tam şeklidir. En kolay ve en basit CPU zamanlama algoritmasıdır. Bu tür bir algoritmada, CPU'yu talep eden süreç önce CPU tahsisini alır. Bu zamanlama yöntemi bir FIFO kuyruğu ile yönetilebilir.

Süreç hazır kuyruğuna girerken, PCB'si (Proses Kontrol Bloğu) kuyruğun kuyruğu ile bağlantılıdır. Bu nedenle, CPU serbest kaldığında, kuyruğun başında sürece atanmalıdır.

FCFS yönteminin özellikleri:

  • Önleyici olmayan ve önleyici zamanlama algoritması sunar.
  • İşler her zaman ilk gelene ilk hizmet esasına göre yürütülür
  • Uygulaması ve kullanımı kolaydır.
  • Ancak bu yöntemin performansı zayıftır ve genel bekleme süresi oldukça yüksektir.

En Kısa Kalan Süre

SRT'nin tam formu Kalan en kısa süre'dir. Ayrıca SJF önleyici zamanlama olarak da bilinir. Bu yöntemde süreç, tamamlanmasına en yakın olan göreve tahsis edilecektir. Bu yöntem, daha yeni bir hazır durum işleminin daha eski bir işlemin tamamlanmasını beklemesini önler.

SRT zamanlama yönteminin özellikleri:

  • Bu yöntem çoğunlukla kısa işlerin tercih edilmesi gereken toplu iş ortamlarında uygulanır.
  • Bu, gerekli CPU zamanının bilinmediği paylaşılan bir sistemde uygulamak için ideal bir yöntem değildir.
  • Her işlemle bir sonraki CPU patlamasının uzunluğu olarak ilişkilendirin. Böylece işletim sistemi bu uzunlukları kullanır, bu da işlemi mümkün olan en kısa sürede planlamaya yardımcı olur.

Öncelik Bazlı Zamanlama

Öncelik çizelgeleme, önceliğe dayalı bir süreç çizelgeleme yöntemidir. Bu yöntemde, zamanlayıcı çalışacak görevleri önceliğe göre seçer.

Öncelik zamanlaması, işletim sisteminin öncelik atamalarını dahil etmesine de yardımcı olur. Önceliği daha yüksek olan süreçler önce gerçekleştirilmelidir, oysa eşit önceliklere sahip işler sıralı veya FCFS esasına göre yürütülür. Öncelik, bellek gereksinimlerine, zaman gereksinimlerine vb. göre karar verilebilir.

Round-Robin Zamanlama

Round robin, en eski ve en basit zamanlama algoritmasıdır. Bu algoritmanın adı, her bir kişinin sırayla bir şeyden eşit pay aldığı yuvarlak-robin ilkesinden gelir. Çoğunlukla çoklu görevlerde zamanlama algoritmaları için kullanılır. Bu algoritma yöntemi, süreçlerin açlıktan ölmeden yürütülmesine yardımcı olur.

Round-Robin Çizelgelemenin Özellikleri

  • Round robin, saat odaklı hibrit bir modeldir.
  • Belirli bir görevin işlenmesi için atanan zaman dilimi minimum olmalıdır. Ancak, farklı işlemler için değişebilir.
  • Olaya belirli bir zaman sınırı içinde yanıt veren gerçek zamanlı bir sistemdir.

Önce En Kısa İş

SJF, (önce en kısa iş) 'in tam bir biçimidir ve bir sonraki yürütme için en kısa yürütme süresine sahip işlemin seçilmesi gereken bir zamanlama algoritmasıdır. Bu zamanlama yöntemi, önleyici veya önleyici olmayabilir. Yürütmeyi bekleyen diğer işlemler için ortalama bekleme süresini önemli ölçüde azaltır.

SJF Programlamanın Özellikleri

  • Tamamlanacak bir zaman birimi olarak her işle ilişkilidir.
  • Bu yöntemde, CPU müsait olduğunda, bir sonraki işlem veya tamamlanma süresi en kısa olan iş ilk önce yürütülür.
  • Önleyici olmayan bir politika ile uygulanmaktadır.
  • Bu algoritma yöntemi, işlerin tamamlanmasını beklemenin kritik olmadığı toplu tip işleme için kullanışlıdır.
  • Önce yürütülmesi gereken ve çoğunlukla daha kısa geri dönüş süresi olan daha kısa işler sunarak iş çıktısını iyileştirir.

Çok Düzeyli Kuyruklar Planlama

Bu algoritma, hazır kuyruğu çeşitli ayrı sıralara ayırır. Bu yöntemde, işlemler, işlem önceliği, bellek boyutu vb. gibi işlemin belirli bir özelliğine dayalı olarak bir kuyruğa atanır.

Ancak, işleri zamanlamak için başka tür algoritmaları kullanması gerektiğinden, bu bağımsız bir zamanlama işletim sistemi algoritması değildir.

Çok Düzeyli Kuyruk Zamanlamasının Özellikleri:

  • Bazı özelliklere sahip işlemler için çoklu kuyruklar korunmalıdır.
  • Her kuyruğun ayrı zamanlama algoritmaları olabilir.
  • Her sıra için öncelikler verilir.

Bir Zamanlama Algoritmasının Amacı

Bir zamanlama algoritması kullanmanın nedenleri şunlardır:

  • CPU, verimliliğini artırmak için zamanlamayı kullanır.
  • Rakip süreçler arasında kaynakları tahsis etmenize yardımcı olur.
  • Çoklu programlama ile maksimum CPU kullanımı elde edilebilir.
  • Yürütülecek işlemler hazır kuyruğundadır.

Özet:

  • CPU zamanlaması, başka bir işlem beklemedeyken hangi işlemin yürütme için CPU'ya sahip olacağını belirleme işlemidir.
  • Önleyici Çizelgeleme'de görevler çoğunlukla önceliklerine göre atanır.
  • Önleyici olmayan zamanlama yönteminde CPU, belirli bir işleme tahsis edilmiştir.
  • Burst süresi, işlemin yürütülmesini tamamlaması için gereken süredir. Aynı zamanda çalışma süresi olarak da adlandırılır.
  • CPU kullanımı, işletim sisteminin CPU'nun mümkün olduğunca meşgul kalmasını sağlamak için ihtiyaç duyduğu ana görevdir.
  • Birim zaman başına yürütmesini tamamlayan işlem sayısı, çıktı olarak bilinir.
  • Bekleme süresi, belirli bir işlemin hazır kuyruğunda beklemesi gereken bir miktardır.
  • İlk yanıt üretilene kadar talebin gönderildiği süredir.
  • Geri dönüş süresi, belirli bir işlemi yürütmek için gereken süredir.
  • Zamanlayıcı kesinti, önceden alma ile yakından ilgili bir yöntemdir,
  • Dağıtıcı, CPU'nun sürece kontrolünü sağlayan bir modüldür.
  • Altı tür süreç çizelgeleme algoritması şunlardır:
  • İlk Gelen İlk Servis (FCFS), 2) En Kısa-Öncelikli (SJF) Planlama 3) En Kısa Kalan Süre 4) Öncelikli Programlama 5) Round Robin Programlama 6) Çok Düzeyli Kuyruk Planlama
  • İlk Gelen İlk Hizmet yönteminde, CPU'yu talep eden süreç, ilk olarak CPU tahsisini alır.
  • En Kısa Kalan sürede süreç, tamamlanmasına en yakın olan göreve tahsis edilecektir.
  • Öncelikli Zamanlama'da, zamanlayıcı önceliğe göre çalışacak görevleri seçer.
  • Bu Round robin zamanlaması, her kişinin sırayla bir şeyden eşit pay aldığı prensipte çalışır.
  • En kısa işte önce, sonraki yürütme için en kısa yürütme süresi seçilmelidir.
  • Çok düzeyli çizelgelemede yöntem, hazır kuyruğu çeşitli ayrı sıralara ayırır. Bu yöntemde, süreçler belirli bir özelliğe dayalı olarak bir kuyruğa atanır.
  • CPU, verimliliğini artırmak için zamanlamayı kullanır.