Yazan : Şadi Evren ŞEKER

Bu yazının amacı, işletim sistemleri teorisinde sık kullanılan zamanlama kavramlarını açıklamaktır. Bu yazıda anlatılması hedeflenen kavramlar:

  • Bekleme zamanı (waiting time)
  • Dönüş süresi (turnaround time)
  • İş üretimi (throughput)
  • Cevap süresi (response time)

Yukarıdaki bu kavramların kısa tanımlarını yaptıktan sonra bir örnek üzerinden açıklamaya çalışalım.

CPU zamanlama algoritmalarında (CPU scheduling algorithms) kullanılan bekleme zamanı, bir işlemin (process) bekleme sırasında (ready queue) geçirdiği toplam süredir. Benzer şekilde dönüş süresi, işlemin (process) çalıştırılması ile bitmesi arasındaki toplam zamandır. Throughput (iş üretimi) ise bir işlemcinin birim zamanda tamamladığı işlem (process) sayısıdır. Bir algoritmadaki cevap süresi (response time) ise işlemin algoritma tarafından, ne kadar zaman içerisinde ilk kez cevap verildiğidir.

Bu durumların hepsini örnek bir çalışma üzerinden görmeye çalışalım.

Örneğin işlemcilerin sisteme varış zamanları (arrival time) ve çalışma süreleri (CPU burst time)aşağıdaki şekilde olsun.

İşlem Ulaşma Zaman (Arrival Time) Çalışma Süresi (Burst Time)
P1 0 5
P2 0 3
P3 7 5
P4 8 9

Yukarıdaki örneği round robin algoritmasına göre çalıştıralım ve zaman birimi (time quadrant) olarak 2 birim kabul edelim. Bu durumda her 2 birimlik zamanda bir işlem değişimi (context switch ) olacak ve görevlendirici (dispatcher) bekleme sırasından (ready queue) yeni bir işlemi alarak işlemciye gönderecektir.

Süre 0-2 2-4 4-6 6-7 7-8 8-10 10-12 12-14 14-16 16-17 17-22
İşlem P1 P2 P1 P2 P1 P3 P4 P3 P4 P3 P4

Yukarıdaki gösterilen zaman çizgisinde önce geliş sırasına göre P1 işleminden başlanıyor ve zaman birimi olan 2 birim sonra bekleme sırasından bir sonraki işlem olan P2 çalıştırılıyor. Örneğin 7. Zaman biriminde P3 ulaşıyor ancak o sırada bekleme sırasında önde bulunan P1 işlemi bitirilerek 8. Zamanda P3 işlemi çalıştırılıyor.

Yukarıdaki bu örnekte, açıklamaya çalıştığımız zamanları hesaplayalım:

Sistemdeki işlemlerin bekleme zamanları aşağıdaki şekildedir:

P1 işlemi, 2-4 ve 6-7 zaman aralıklarında toplam 3 birim için bekleme sırasında (ready queue) beklemiştir.

P2 işlemi, 0-2 ve 4-6 zaman aralıklarında toplam 4 birim için bekleme sırasında (ready queue) beklemiştir.

P3 işlemi 7-8 , 10-12 ve 14-16 zaman aralıklarında toplam 5 birim için bekleme sırasında (ready queue) beklemiştir.

P4 işlemi 8-10, 12-14 ve 16-17 zaman aralıklarında toplam 5 birim için bekleme sırasında (ready queue) beklemiştir.

Ortalama bekleme zamanı için bütün işlemlerin bekleme zamanlarını toplayarak işlem sayısına bölüyoruz. Bu durumda 3 + 4 + 5 + 5 = 17 / 4 = 4.25 birimlik ortalama bekleme süresi vardır denilebilir.

Dönüş süresi hesaplanırken bir işlemin sisteme ulaşması ile bitmesi arasındaki zaman hesaplanmalıdır. Bu hesap her işlem için aşağıda verilmiştir.

P1 işlemi sisteme 0. Zamanda ulaşmış ve 8. Zamanda bitmiştir. Bu durumda dönüş süresi 8. Birimdir.

P2 işlemi sisteme 0. Zamanda ulaşmış ve 7. Zamanda bitmiştir. Bu durumda dönüş süresi 7. Birimdir.

P3 işlemi sisteme 7. Zamanda ulaşmış ve 17. Zamanda bitmiştir. Bu durumda dönüş süresi 10. Birimdir.

P4 işlemi sisteme 8. Zamana ulaşmış ve 22. Zamanda bitmiştir. Bu durumda dönüş süresi 14. Birimdir.

Ortalama dönüş süresi (average turn around time) ise bu değerlerin ortalamasıdır : 8 + 7 + 10 + 14 = 39 / 4 = 9.75 birim zaman olarak hesaplanabilir.

İş üretimi (throughput) hesabı için, sistemde toplam 22 birim zamanlık iş yapılmış ve bu süre içerisinde 4 işlem çalıştırılmıştır. Bu durumda 22 / 4 = 5.5 olarak hesaplanabilir.

Cevap sürelerini yine her işlem için ayrı ayrı hesaplayacak olursak:

P1 işlemi sisteme 0. Zamanda ulaşmış ve 0. Zamanda işlemcide ilk kez çalıştırılmaya başlamıştır. Bu durumda cevap süresi (response time ) 0. Birimdir.

P2 işlemi sisteme 0. Zamanda ulaşmış ve 2. Zamanda işlemcide ilk kez çalıştırılmaya başlamıştır. Bu durumda cevap süresi (response time ) 2. Birimdir.

P3 işlemi sisteme 7. Zamanda ulaşmış ve 8. Zamanda işlemcide ilk kez çalıştırılmaya başlamıştır. Bu durumda cevap süresi (response time ) 1. Birimdir.

P4 işlemi sisteme 8. Zamanda ulaşmış ve 10. Zamanda işlemcide ilk kez çalıştırılmaya başlamıştır. Bu durumda cevap süresi (response time ) 2. Birimdir.

Ortalama cevap süresi (average response time) hesaplanırken yine bu sayıların ortalaması bulunur: 0 + 2 + 1 + 2 = 5/4 = 1.25 birim zamandır.

Yorumlar

  1. yaprak

    merhaba Hocam, SCHED OTHER scheduling algoritması çalışma mantığını tam olarak anlayamadım, burada nice,goodness gibi değerler neyi ifade ediyor, bu algoritmada priortyler neye göre bulunuyor?

    bu sorular aslında işletim sistemleri dersini alan tüm arkadaşların kafasını karıştırdığı ve çözemediği sorulardan bir kaçı, verebileceğiniz cevaplar eminim diğer arkadaşlara da çok faydalı olacaktır.

    çok teşekkür ederim..

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      Linux kernel (çekirdek) kodlamasında bulunan ve posix kütüphanesinden erişilebilen zamanlama (scheduling) algoritması etiketidir. Bunlar üç tanedir:
      sched_rr : gerçek zamanlı ve sabit öncelikli (fixed priority) algoritmadır, dolayısıyla kıtlık (starvation) ihtimali bulunur. Round robin algoritmasını kullanır.
      sched_fifo: bir önceki ile aynıdır round robin yerine fifo kullanır.
      sched_other: zamanlaması diğer çalışan işlere göre değişen bir yapıda olan round robin algoritmasıdır.

      Aşağıdaki yazılar yardımcı olabilir:

      http://bilgisayarkavramlari.sadievrenseker.com/2008/11/19/ilk-gelen-calisir-first-come-first-serve-fsfc/
      http://bilgisayarkavramlari.sadievrenseker.com/2008/11/19/round-robin/
      http://bilgisayarkavramlari.sadievrenseker.com/2008/11/19/kesintili-zamanlama-preemptive-scheduling/
      http://bilgisayarkavramlari.sadievrenseker.com/2012/03/26/posix-thread-pthread-kutuphanesi/
      http://bilgisayarkavramlari.sadievrenseker.com/2008/11/19/kitlik-starvation/

  2. regaib

    Short-term Scheduler(kısa vadeli zamanlayıcı),long-term scheduler(uzun vadeli zamanlayıcı),medium-term scheduler(orta vadeli zamanlayıcı) nedir aralarında ilişki nasıldır . açıklayabilir misiniz.. ilginiz için teşekkürler hocam

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      Kısaca işlemler arasındaki değişimin (context switch) ne kadar hızlı olduğu ile ilgili bir sınıflandırmadır. Aşağıdaki yazılar yardımcı olacaktır:
      http://bilgisayarkavramlari.sadievrenseker.com/2010/03/20/islemci-zamanlari-cpu-timing/
      http://bilgisayarkavramlari.sadievrenseker.com/2008/11/19/islemci-zamanlama-cpu-scheduling/
      http://bilgisayarkavramlari.sadievrenseker.com/2008/11/19/bekleme-sirasi-ready-queue/
      http://bilgisayarkavramlari.sadievrenseker.com/2011/01/03/fair-share-scheduling-adil-paylasimli-zamanlama/
      http://bilgisayarkavramlari.sadievrenseker.com/2010/01/18/cok-seviyeli-siralar-multi-level-queues/

  3. İlker

    Hocam merhaba, günümüz işletim sistemlerinde kullanılan scheduler algoritmaları nelerdir acaba? (Linux,Windows,Mac,Android,IOS). Bu konuda pek bir tutarlı bilgi edinemedim. Şimdiden teşekkür ederim.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


7 × = kırk iki