İşletim Sistemi 101 – #5 (CPU Scheduling)

Giriş

Bir önceki yazımda process’lerden bahsetmiştim. Bu yazımda ise ister “multithreaded” ister “single-threaded” olsun, bir işin CPU’ya gönderilmesi için olmazsa olmaz bir konudan, CPU scheduling‘ten bahsedeceğim.

Hep tekrar ettiğimiz bir nokta: İşletim sistemi kaynakları doğru yönetmelidir. Ve kaynaklarımız sınırlı. Bir CPU çekirdeğinde aynı anda yalnızca bir iş yapılabilir ve daha bilgisayarımızı açar açmaz çalışan servisler, aslına bakarsanız ciddi iş yükü oluşturuyor.

Örneğin anti-malware yazılımınız çalışıyor. Güncellemelerini, günlük görevlerini yapmaya başlıyor. Wi-Fi kartınız, etrafındaki ağları aramaya başlıyor, otomatik bağlanmasını istediğiniz denk gelirse bağlanıyor. USB yollarına takılı olan cihazlar varsa ayağa kaldırılıyor. Ses, parlaklık, klavye aydınlatması, fonksiyon tuşları gibi işlevlerden sorumlu servisler ayağa kalkıyor. İşletim sistemi, kendi log’larını yazıyor. Kullanıcı oturumunuzu yöneten servisler ayağa kalkıyor. Daha neler neler…

Sonrasında kullanıcı, bilgisayarını kullanmaya başlıyor. Kullanıcının açtığı process’ler de dâhil oluyor curcunaya. Ama ortada – genelde – 1-8 arası CPU çekirdeği var. Bu CPU’yu en verimli şekilde kullanabilmek için geliştirilen bazı modeller var. Bunlardan biri, ilk paragrafta bahsi geçen “thread” kavramı.

Thread Nedir?

Process’lerin çalıştırılmasını “scheduler” yönetir (bu konuya değineceğiz). Thread’leri ise process’lerin içindeki alt process’ler olarak düşünebiliriz. Process’lerin bir birim zamanda birden fazla görevi eş zamanlı yürütebilmelerine olanak sağlayan yapıya “thread” diyebiliriz.

Olayı şöyle örnekleyelim. 1 CPU’muz var. 4 çekirdeği var. 4 çekirdeği de eş zamanlı eş yapabiliyor diyelim. Bizim de elimizde 4 birimlik iş olsun. Eğer single-threaded yapıda bir uygulamamız varsa, işini bitirebilmesi için 4 tura ihtiyaç duyar. Çünkü birim zamanda yalnızca bir çekirdeği kullanabilmekte, dolayısıyla bir iş yapabilmektedir. Fakat uygulamamız multithreaded yapıda ise, bir CPU turunda 4 çekirdeğe parçalı olarak yerleşerek işini “paralel^1 yapabilir ve 1 turda bitirebilir. Anlamadık mı?

Kabaca örneklemeyi deneyelim. Bir e-posta istemcisini düşünün. CPU’da oldukça kısıtlı olan zamanını single-threaded modda geçiriyorsa, her CPU turunda sadece bir iş yapabilir:

  1. Kimden, kime, konu gibi üst bilgileri çek. (Tur bitti, bekle.)
  2. E-posta içeriğini çek. (Tur bitti, bekle.)
  3. E-posta içerisinde yer alan imza, bir web sunucusundan görsel (kartvizit gibi) içeriyor. Onu getir. (Tur bitti, bekle.)
  4. Gönderen kişi “alındı onayı” istemiş. Onay verecek miyim diye sor. (Tur bitti, bekle.)
  5. Alındı onayını gönderdim. Karşıya ilet. (Tur bitti, bekle.)
  6. E-postayı okudum. Sunucuda da okunmuş işaretle.

Eğer aynı istemci, multithreaded yazılmış olsaydı ve elimizde kullanılabilir durumda 2 çekirdek olsaydı, bu işler eş zamanlı yapılabilir ve yukarıdaki adımlar 3 turda tamamlanabilirdi.

Başka bir örnek. Web tarayıcınızı açın. Sonra “Görev Yöneticisi” gibi bir yerden işlemlere bakın. Tarayıcıda 2 sekme açın. 2 farklı web sayfasına gidin. Process listesine tekrar bakın. Tarayıcınız yüksek ihtimalle, hem sekmeler için hem de bir sekme içinde farklı görevleri yerine getirmek için thread’ler açmış olacak. Hatta şansınız yaver gider ve doğru thread’i durdurmayı başarırsanız, sekmelerden birinin tamamen ya da kısmen çöktüğünü görebilirsiniz.

Kısa bir bilgi: Özellikle telefonlarda deli gibi çekirdek sayısı çıkıyor karşımıza. Soru: “Çift çekirdekli 2 GHz hıza sahip işlemci mi daha iyidir yoksa 4 çekirdekli 1.4 GHz hıza sahip işlemci mi?” Diğer tüm özelliklerinin aynı olduğunu kabul edelim. Bir tanesi 2×2’den 4 GHz hıza sahip teoride. Diğeri ise 4×1.4’ten 5.6 GHz. Dört çekirdekli olan daha iyi o zaman? Yok işte, öyle olmuyor. Kullanacağınız uygulama – diyelim ki sıradan bir mobil oyun – eğer multithreaded yazılmadıysa (geliştirilmediyse) sadece 1 çekirdek kullanabilir. Dolayısıyla o uygulama için çift çekirdekli 2 GHz işlemci daha iyi olur. Çünkü tek çekirdekteki hızı daha yüksektir. Öte yandan uygulamayı bu şekilde yazan kişilere de sormak lazım “Neden?” diye.

Giriş kısmında, henüz bilgisayar açılmışken yapılması gereken işlerden bahsetmiştim. İşletim sistemleri – kendileri de bir yazılım olduğu için – kaynakları doğru kullanacak şekilde hazırlanırlar. En azından bunu denerler. Bir işletim sistemi; aygıt yönetimi, bellek yönetimi, disk yönetimi gibi ayrı işleri için ayrı thread’lere sahip olabilir. Hatırlarsanız bir önceki yazımda “Kernel Thread Daemon”dan bahsetmiştim. Bütün process’ler ve dolayısıyla process’lerin thread’leri, bu arkadaşa bağlı çalışıyordu.

Process ve Thread Farkı

  • Process’ler birbirinden bağımsız yapılardır. Thread’ler ise, process’lere bağlı çalışan iş parçalarıdır. Bir process’in birden fazla thread’i olabilir.
  • Process’e dair tutulan bilgiler, thread’e kıyasla daha fazladır (Process Control Block’u hatırlayın.). Thread’ler ise; process’lerinin state’lerini, process’lerine atanan kaynakları miras alır.^2
Process içinde thread'ler. Thread'lerin code, data gibi segment'leri ortak kullanmalarına bir örnek. (Operating System Concepts Essentials kitabından alınmıştır.)
Process içinde thread’ler. Thread’lerin code, data gibi segment’leri ortak kullanmalarına bir örnek. (Operating System Concepts Essentials kitabından alınmıştır.)

Neden Thread?

  • E-posta istemcisi örneğine geri dönelim. Bir e-posta yazmak istediğinizde, uygulama sizi beklemek zorundadır. Klavyeden tuşlara basacaksınız, “Gönder” düğmesine tıklayacaksınız. Bu sırada process, sizinle meşgul. Sizden gelecek etkileşimleri bekliyor. Eğer single-threaded bir yapıda olsaydı, siz bu e-postayı yazma işini bitirene kadar başka hiçbir şeyle ilgilenemezdi. Fakat multithreaded çalışırsa, bir thread sizin e-posta yazmanız için beklerken başka bir thread arkaplanda yeni e-posta olup olmadığını kontrol etmeye devam edebilir.
  • Kaynakların process’ler arasında paylaştırılabilmesi için geliştirici tarafından ekstra bir çaba gerekir. Fakat multithreaded yazılmış bir uygulama, yapısı gereği, zaten kaynaklarını kendi içindeki thread’ler arasında paylaşabilir durumdadır.
  • Her iş için ayrı bir process demek, her iş için process oluşturma sürecinin tekrarlanması demek. Önceki yazımda değindiğim gibi, bu gerçekten maliyetli bir iş. Fakat bir process içinde birden fazla thread oluşturmak, onlarca kat hızlı olabilir. Ek olarak, thread’ler arasında “context switching” yapmak (buna da değineceğiz), process’ler arasındakine göre çok daha hızlıdır.
  • Yukarıda verdiğim mobil uygulama örneğinde olduğu gibi, donanımın hakkını vermek için thread’lerden faydalanırız. İster çift, ister dört, ister sekiz çekirdeğiniz olsun. Eğer uygulama, single-threaded çalışıyorsa, biri hariç diğer tüm çekirdekler hiçbir işe yaramaz. (Önemli bir nokta. İşletim sistemleri bazı çekirdekleri sabit ya da belirli görevlere atamış olabilir. Dolayısıyla CPU’nuzun diğer çekirdekleri de kullanılmaya devam edebilir fakat sizin kullandığınız uygulama tarafından değil.)

CPU Scheduling

Gelelim esas konumuza. Herhangi bir anda hangi process’in çalışacağına karar verilmesi gerekir. Tabii ki bu karar, işletim sisteminin sorumluluğundadır ve “scheduler” tarafından verilir (bu konuya değineceğiz dediklerimden ilki). Scheduler’ın bu kararı vermesinde rol alan algoritmalar vardır ki bu algoritmalara “scheduling algorithm” denir.

Geçmiş zamanda, batch system’lerde, scheduling daha kolaydı. Delikli kart bloklarını hangi sırada koyarsanız, o sırada çalışır. Siz Ahmet’in programını Mehmet’in programından önce yüklerseniz (evet, fiziken kartları makineye yüklerseniz) Ahmet’in programının önce çalışması kaçınılmazdır. Programların tape’lere kaydedildiği zamanı düşünelim. Eğer Mehmet’in programı, şerit üzerinde Ahmet’in programından daha önce yazıldıysa, önce Mehmet’in programı çalışır. Bu mekanizmalar “sıralı erişim” yapar. Telefonunuzda istediğiniz müziği açabiliyorsunuz ama kaset çalar kullanırken ileri sarmak zorundasınız, aynı mantık. Biri rastgele erişimi desteklerken diğeri sıralı erişimi destekler. Hemen bir hatırlatma: Random Access Memory‘e (Rastgele Erişimli Bellek, RAM) neden rastgele erişimli denildiğini anladınız mı? 🙂

Günümüz sistemlerinde ise birden fazla işi eş zamanlı yapabilmemizi sağlayan olay, CPU scheduling sayesinde CPU zamanının verimli kullanılmasıdır.

CPU Burst vs. I/O Burst

Çoook acil bir işim var. Hemen bir dilekçe yazıp çıktı almam lazım. Çabuk, acele. Tık, tık, tık, tık, tık… 8 tane metin editörü açtım. 7’sini kapattım, biri kaldı. İşletim sistemine bakın, nasıl hizmet veriyor bana. Editör önümde açık, bekliyor. CPU’da bekliyor beni iş yapmak için. Bütün kaynaklar önüme serilmiş. Saniyede milyarlarca işlemi hobi olarak yapan cihaz, beni bekliyor. “Bugün ayın kaçı? Tarihi sağ üste mi yazıyorduk? Başlıktan önce miydi sonra mıydı? Kuruma mı yazayım müdürlüğe falan mı?” Milyarlarca işlem kapasitesi, gigabyte’lar düzeyinde bellek, 100’ün üzerinde tuş tek yürek olmuş; keyfimi bekliyor.

İşte, ilk başta “hadi hadi hadi” diyerek başlattığımız süreçlere “CPU burst” diyebiliriz. Programımız, gerçekten açılmak istiyor. Process için ilgili kayıtlar oluşturuluyor. Görüntü önümüze geliyor. Bunlar hep CPU ile bağlantılı işler. Sonrasında ise benden bir girdi bekleniyor. Bu tarafa ise “I/O burst” diyebiliriz. Yazdık, bitirdik. Editör yine çalışıyor biz yazdıkça. Fakat bir birim çalışıyorsa belki 1000 birim bizi bekliyor. CPU’nun hızına yetişmemiz imkânsız. Sonrasında ise “kaydet” butonuna basıyoruz. Yazdıklarımız, CPU’ya kıyasla oldukça hantal kalan hard disk’e yazılmaya başlanıyor. Çıktı süreci başladı, yine I/O burst yapıyoruz. Yine yavaşız. Dosyayı yazıcıya gönderdik, yine yavaşız. Process’ler, herhangi bir dış kaynaktan etkileşim beklemeye başladılarsa, I/O sürecine girmiş olurlar. Bu süreç, CPU sürecine göre aşırı yavaştır ve beklemeye değmez. Bir başka deyişle, siz o editörü açıp boş boş bakarken, işletim sistemi sizi çoktan unutmuştur ve başka işlere dönmüştür bile. Neredeyse bütün programların girdi/çıktı ile uğraştığını düşünürsek, process’lerin de CPU burst ile I/O burst arasında gidip geldiğini söyleyebiliriz.

Web tarayıcımızı açtık. Önceki oturumdan kalan 24 sekme otomatik olarak yüklendi. CPU’muz çalışıyor. Bu oturumlara ait bilgiler getiriliyor, web adreslerine istekler gönderiliyor, gelen yanıtlar işleniyor, ekranda gösteriliyor. Peki ya sonra? Elimizi fareye uzatıyoruz. Tık, tık, kaydır, oku. Yine aynı durum. CPU burst oldu. I/O burst’e geçildi. Tak, bir input geldi bizden. Fare tekerleğini kaydırdık. Ekranda birtakım değişiklikler yaşandı. Sonra yine bekle, okuyorum.

İşleri Hangi Durumlarda Planlamalıyız?

Scheduler’dan bahsettik. Peki scheduler’a ne zaman, hangi durumlarda iş düşüyor? Ne zaman devreye girip yetkisini kullanması gerekiyor?

  • Yeni bir process oluşturuldu ve kuyruğa girdi. Ne zaman, ne sıklıkla, ne süreyle çalıştıralım?
  • Process durduruldu. Kuyruktan çıkarıldı. Bu process’in ortadan kaybolması, diğer process’lere ayırdığımız zamanı ve atadığımız önceliği nasıl etkileyecek?
  • Process bloklandı. Peki neden? Kullanıcıdan bir etkileşim bekliyorsa, sonlara atılabilir. Çünkü kullanıcı yavaştır. Peki bir “A” process’i, “B” process’inin işini bitirmesini beklediği için bloklandıysa ne olacak? Bir an önce “B”yi çalıştırıp bitirsek, bu sayede “A” da tekrar işine dönebilir hâle gelse olmaz mı? Peki scheduler bu bilgiye sahip mi?
  • Editör örneğine dönelim. Klavyeden bir tuşa basmam bekleniyordu. Bastım. Şimdi ne olacak? Tam ben tuşa bastığım sırada çalışmakta olan process çalışmaya devam mı etsin? Benim yazı yazmak için kullandığım process hemen devreye mi alınsın? Yoksa konudan bağımsız başka bir process’in daha öncelikli bir işi var ve herkes onu mu bekleyecek? Önceki yazılarımdan birinde, “a” ve “aaaaaaaaaaaaaaaaa” örneği vermiştim hatırlarsanız. Bunlar hep scheduling 🙂

Nonpreemptive vs. Preemptive

CPU scheduling algoritmalarını nonpreemptive ve preemptive olmak üzere ikiye ayırabiliriz.

Nonpreemptive” scheduling yapıyorsak, bir process’i CPU’ya göndeririz fakat durması için zorlamayız. Bu process; CPU ile işi bittiğinde, I/O beklediğinde, başka bir process’in işini bitirmesinde ihtiyaç duyduğunda CPU’dan gönüllü olarak ayrılır ve diğer process’lerin kullanabilmesi için CPU’yu serbest bırakır. Bu scheduling yöntemine “voluntary” ya da “cooperative” de denir.

Preemptive” scheduling’de ise, CPU’yu kullanmakta olan process’e “Tamam, yeter artık.” deme şansına sahip oluruz. Process’lerin çalışabilmek için önceden planlanmış süreleri olur. Bu süre, nanosaniyeler düzeyinde olabilir. Süresi dolan process, CPU’dan kaldırılır ve yerine – eğer varsa – bekleyen başka bir process konulur.

Bazı donanım platformlarında, preemptive scheduling için gerekli olan “zaman ölçme” mekanizmaları bulunmadığı için, mecburen nonpreemptive scheduling kullanılır. “Saat kaç oldu ki?” dediğinizde, bu durumu hatırlayın. 🙂

Bakıldığında, preemptive scheduling çok daha mantıklı görünüyor. Nonpreemptive bir yapıda, bir process CPU’yu kullanmaya başlar ve sürekli olarak bir işle meşgul olursa, diğer process’lere sıra gelmez değil mi? Fakat preemptive scheduling’in implementasyonu da gerek donanım gerekse yazılım tarafında ek gereksinimleri beraberinde getiriyor. Ayrıca, şöyle bir senaryo düşünelim. “A” process’i bir veri hazırlamakla yükümlü olsun. “B” process’i ise hazırlanan bu veri üzerinde işlem yapmakla yükümlü diyelim. Preemptive sistem. “A” process’i çalışıyor, veriyi hazırlıyor. “B” process’i devreye girip bu veriyi işliyor. Sonra “A” process’i yeni bir veri seti hazırlarken süresi doluyor ve veriyi doğru şekilde hazırlayamadan sıra “B” process’ine geliyor. “B” process’i bakıyor, veriyi işlemeye çalışıyor fakat bu veri tutarsız. O da savıyor sırasını. Şimdi ne olacak? 🙂

Dispatcher

CPU scheduling için kullanılan bir başka bileşen de “dispatcher“dır. Dispatcher’ın görevi, scheduler tarafından seçilen process ile ilgili aşağıdaki işlemleri yapmaktır:

  • Context switching
  • User mode’a geçiş
  • Yeni process’in çalışmaya devam edebilmesi için bir önceki turda kaldığı instruction’a geçiş yapmak

Context SwitchinG

“Bu konuya değineceğiz” dediklerimden ikincisi. Process control block’taki verileri neden tutuyorduk? Process hakkında bilgi sahibi olmak için. Bu bilgileri tutuyoruz ki, sıra tekrar bu process’e geldiğinde hiçbir şey olmamış gibi kaldığımız yerden devam edebilelim. İşte process’in durumunu PCB’ye kaydetme ve sıradaki process’in bilgilerini getirme işine “context switching” diyoruz.^3

User Mode vs. Kernel Mode

Kısaca açıklamaya çalışacağım. Bilgisayarı ben kullanıyorsam “user mode”, işletim sistemi kullanıyorsa “kernel mode” aktiftir diyebiliriz.^4

Bir sistemin, kullanıcının uygulamaları için çalıştığı duruma “user mode” denir. Ne zaman ki işletim sisteminin çekirdeği (kernel) bir iş yapmak durumunda kalır, sistem o zaman “kernel mode“a geçer. Bir medya oynatıcıyı çalıştırdım. Bu process “user mode”da çalışıyor. Bir müzik dosyasını açmak istedim. Uygulamam, diskten veri okumak zorunda. Bu durumda “open” ya da “read” gibi bir system call devreye giriyor. Kernel bu okuma işini devralıyor. Dolayısıyla sistem “kernel mode”a geçiyor. Bir metin editörünü açıyorum. User mode. Klavyemden birtakım girdiler gönderiyorum. Klavyem işletim sistemine çağrıda bulunuyor. Kernel mode. Yazımı yazıyorum, son kez göz gezdiriyorum. User mode. Kaydet tuşuna bastım. Uygulamam “write” system call’ı gönderdi. Kernel mode.

Sistemin hangi modda çalıştığını, donanım üzerinde “mode bit” dediğimiz bir bitle tutuyoruz. Mode bit 0 ise sistem kernel mode’dadır, 1 ise user mode’da. User mode, oldukça kısıtlı bir mod iken; kernel mode donanıma müdahale edebilen ayrıcalıklı bir moddur. Başka bir deyişle; sizin kullandığınız uygulama sırf siz istediğiniz diye ya da kendi kendine disk’le, RAM’le, ağ kartlarıyla vs. muhatap olamaz. Bu talepleri system call’lar ile işletim sistemine iletir. İşletim sistemi yapılması gereken işleri çekirdeğine yaptırır, sonucunu uygulamanıza iletir.

Neden Scheduling?

CPU scheduling yapılmasının belli başlı amaçları vardır.

  • CPU’yu mümkün mertebe kullanmak. Herhangi bir sistemde bir CPU kullanılmıyorsa, bu israf kabul edilir. Gerçekten. Madem bu kadar fazla işlem yapmayacaktık, neden bu işlemciyi satın aldık? Bu bilgisayar çalışıyor, peki neden iş yapmıyor? İşletim sistemi bu durumu önlemek için tüm process ve thread’leri doğru şekilde planlayıp çalıştırmak zorundadır.
  • Birim zamanda yapılan iş miktarını (throughput) arttırmak. Eğer bir process I/O bekliyorsa, neden diğer işleri yapmaya devam etmeyelim? Gerçekten tüm gün boyunca kullanıcının bir tuşa basmasını mı bekleyeceğiz?
  • Bir process’in başlangıcı ve bitişi arasında geçen süreye “turnaround time” denir ve scheduling bu süreyi minimumda tutmayı amaçlar. Aynı anda başlattığımız 2 işimiz var. Biri 10 saniyelik, diğeri 10 saatlik olsun. Bu işlerin birbirinden bağımsız olduğunu kabul edersek, 10 saniyelik işi erkene almak daha mantıklı olmaz mı? Diğer senaryoda 10 saniyelik işin bitmesi 10 saat + 10 saniye sürecektir. Markettesiniz, önünüzdeki müşteri arabayı doldurmuş. Siz de kola alıp çıkacaksınız. Let the games begin.
  • Bekleme sürelerini azaltmak. Process’lerin state’lerinden bahsetmiştik. Scheduling, bir process’i mümkün mertebe az süre bekletmek ister. Aksi durum devlet dairesi.
  • Tepki süresini (response time) mümkün mertebe kısa tutmak. Yukarıdaki “turnaround time” örneğinde, process’in işini bitirmesi için diske veri yazması gereken bir senaryo düşünün. Disk yavaş, CPU’nun suçu ne? Bu nedenle farklı bir kriter hayatımıza giriyor,”response time“. Process’in işimize yanıt verme süresi. Tamamlamasını geciktiren farklı etmenler olabilir, ancak işimizi yapmaya başladığını bilmek istiyoruz. Scheduling, response time’ı minimumda tutmayı amaçlar. Hastanede kayıt masasına geldiniz. Kimlik numaranızı verdiniz. Görevli bu bilgiyi girdi. “Bugün sistemler biraz yavaş da..” dedi. Olsun. Response verdi bize, sorun yok. Sistemin çalışmasını bekliyoruz şu an. Görevli, bizim işimizi aksatmıyor. Elinden geleni yaptı. Bekliyoruz. CPU gözünden düşünürsek de, I/O tarafı yavaş kaldı, sorun bizlik değil.

Scheduling Algoritmaları

Scheduling Kategorileri

Farklı amaçlar için kurulan farklı sistemlerin birbirinden farklı çalışması gayet doğaldır. Aynı durum, CPU scheduling için de geçerlidir. Farklı sistemlerde, farklı algoritmalar kullanılabilir. Kullanılan bu algoritmaları 3 temel gruba ayırabiliriz.

Batch

Her ne kadar eski gözükse de, batch sistemler günümüzde de bazı iş kollarında kullanılmaktadır. Bu sistemlerde, yapılması gereken bir ya da birkaç iş vardır ve bu işlerin tamamlanması gerekmektedir. Makine, bu işler için dedike çalışmaktadır. Bu tarz sistemlerin başında “Eee hadi ilgilen benimle.” diyen kullanıcılar beklemez. 🙂

Bu sistemlerde process’ler arası context switching bir hayli azalacağından performans artışı gözlemlenir. Batch sistemlerde kullanılan scheduling algoritmaları, gayet tabii farklı sistemlerde de kullanılabilir.

Interactive

Büyük çoğunluğumuzun kullandığı sistemler, interactive sistemler. Bu sistemlerde kullanıcılar ve kullanıcıların işleri var. Process’ler bir yanıt dönüyor, kullanıcılar bu yanıta göre gerekli adımları atıyor. Karşılıklı bir etkileşim söz konusu. Web tarayıcınızı açtınız. Bunun için bir etkileşim şart. Sistem size yanıt verdi. Açtı. Şimdi ne yapması gerekiyor? Tekrar kapatabilirsiniz, belirli bir web sayfasına gitmek isteyebilirsiniz, gizli moda geçebilirsiniz, tarayıcı geçmişinize bakabilirsiniz vs.

Böyle sistemlerde preemptive algoritmalar kaçınılmazdır. Benzer durum sunucular için de geçerlidir. Sunucular, birim zamanda mümkün mertebe fazla kullanıcının işini yapmak ister. Şu an dünya üzerinde popüler bir web sitesini ziyaret eden bütün insanları düşünün. Bu web sitesine ait sunucular, bu kullanıcıların her birine hizmet veriyor. Preemptive bir yapıda çalışmasalar, bir process bitene kadar diğer tüm ziyaretçilerin beklemesi gerekirdi.

Real Time

Real time (gerçek zamanlı) sistemlerde, yapılması gereken işin anında ve acilen yapılması gerekir. Bu tarz sistemler genelde birtakım olayları kontrol eder ve/veya bu olaylara karşı aksiyon alır.

Örneğin, bir uçağın irtifa takibini yapan process’i düşünün. Ya da kabin basıncı, motor arızası kontrolü gibi sistemlerini. Düşünsenize, sağ motoru kaybetmişiz ama o sırada işletim sisteminde başka bir process çalışmakta olduğu için haberi biraz geç gelmiş. Farkedince gerekli uyarı verip önlem alması gereken process de çalışamamış çünkü o sırada kaptanın anons process’i çalışıyormuş. Kabul edilebilir bir durum değil. Otonom araçlar, otopilotlar, üretim robotları gibi sistemleri düşünün. Bu tarz sistemlerde çalışan process’ler preemptive algoritmalara bile gerek duymayabilir. Çünkü kendileri, zaten “işini yap ve çık” mantığıyla hazırlanmış yazılımlardır. Takdir edersiniz ki bu tarz sistemlerdeki CPU scheduling de epey farklı olacaktır.

First-Come, First-Served Scheduling

En basit algoritmalardan biridir. First in first out (FIFO) olarak isimlendirildiğini de görebilirsiniz. FCFS algoritması, Ankara’nın EGO’su gibidir: Erken Gelen Oturur.

Process’ler FIFO kuyruğuna girer. Bir process çalışırken, diğerleri bekler. Bu process’in işi bitince, sıradaki process çalıştırılır. Olur da bu process, I/O bekleme gibi birtakım sebeplerden dolayı blocked durumuna düşerse, kuyruğun en sonuna atılır.

Klasik devlet hastanesi aslında (öncelikli hastaların olmadığı senaryoyu düşünelim tabii ki). Erken geldim, sıra aldım. Önce ben geldim. İlk ben muayene olacağım. Doktor beni tahlile gönderdi. İşim bitmedi aslında, ama blocked oldum. Sonraki hastanın muayenesi başladı. Ben ne oldum? Kuyruğun en arkasına atıldım. Sonuç bekliyorum. Bu process’lerin bazıları ilacını yazdırıp gidiyor. Bazıları sonuç sırasına giriyor. FIFO’nun en sonuna gönderilen process’ler tekrar aynı sıraya giriyor.

FCFS nonpreemptive bir algoritmadır. Process “Kolay gelsin hocam.” diyerek ayrılmadan ya da tahlile, görüntülemeye gönderilmeden CPU’yu bırakmaz. İmplementasyonu kolaydır. Fakat bekleme süreleri konusunda sıkıntılı senaryoları olabilir. Hastane örneğinden biraz kopacağız belki ama, muayene ve ameliyatların aynı yerde aynı kişi tarafından yapıldığını düşünelim. Bir hasta sadece reçetesini imzalatmak istiyor olabilir. Başka bir hasta sadece “Tahlillerin temiz, problem yok.” sözünü duymaya gelmiş olabilir. Diğer bir hasta, raporlu ilacını tekrar yazdırmak için gelmiştir. Bu işler kolaylıkla halledilebilecekken 18 saat sürecen bir kalp ameliyatını beklediklerini düşünün. Yapacak bir şey yok. FIFO kullanıyorsak, iş bitene ya da blocked olana kadar bekleyecekler.

Shortest-Job-First Scheduling

En kısa işin en önce yapıldığı algoritmadır. SJF algoritmasının verimli olabilmesi için bazı ön koşullar vardır. Bunlardan biri, sürekli aynı işleri yapan bir sistem olması. Çalışacak process’ler bellidir, process’lerin CPU yükü bellidir. Bu algoritma kullanılabilir. Fakat çoğu sistemde, kuyruğa giren process’in ne kadar çalışacağını önceden bilemeyiz. Bu durumda şöyle bir yaklaşım sergilenebilir. Process’lerin birim zamanda CPU burst’leri takip edilir ve bir noktadan sonra “tahmini” olarak hangi process’in daha kısa süreceği tespit edilebilir. İkinci konu ise, bu process’lerin kuyruğa birlikte girmesidir. Çünkü kuyruğa sonradan gelen process, önceden gelmiş ve çalışmaya başlamış process’lere kıyasla daha kısa sürecek olabilir.

Eğer çalışma zamanları aynıysa, ilk gelen process öncelikli çalıştırılır (FCFS). Bu algoritma nonpreemptive yapıdadır.

Shortest Remaining Time Next Scheduling

SJF algoritmasının preemptive implementasyonu diyebiliriz. Bu algoritmada, process’in toplam zamanından ziyade kalan zamanına bakılır. Örneğin, kuyrukta 1 , 5, 9, 11 birim zamanda tamamlanacak dört process olsun. Kuyruğa sonradan gelecek ve 3 birim zamana ihtiyaç duyan beşinci process, kuyruğun sonuna eklenmez, önceliklendirilir.

Tabii ki bu algoritmanın implementasyonunda da process’in ne kadar CPU burst yapacağının bilinmesi ya da en azından tahmin edilebilmesi gerekmektedir.

Round-Robin Scheduling

En sık kullanılan algoritmalardandır. Ayrıca oldukça “adil” çalışır. Her process için önceden belirlenmiş bir çalışma süresi, time quantum (time slice) vardır. Eğer bir process, quantum’un sonunda çalışmaya devam etmek istiyorsa, CPU’dan geri çağırılır. Eğer quantum dolmadan işi bittiyse ya da blocked duruma düştüyse de yine CPU’dan geri çağırılır ve diğer process’lerden biri çalıştırılır. Tahmin edeceğiniz üzere preemptive bir algoritmadır.

Quantum süresi, genelde 10 – 100 milisaniye arasındadır. Process kuyruğu FIFO’ya benzer fakat düz bir hat değil, dairesel gibi düşünebilirsiniz. Her process sırayla CPU’ya gönderiliyor. Zamanı dolunca ya da işi bitince bir sonraki process çalıştırılıyor. Daire tamamlanıyor.

RR algoritmasında bekleme süreleri genelde uzundur. Bütün işler birlikte ilerletilmeye çalışılır. Ek olarak, ayrı bir kararın da verilmesi lazım: time quantum. Ne kadar olsun? Her process 1 milisaniye çalışsın, böylece hiçbirinin durduğunu fark edemeyiz diyelim. Peki bu değişim için gerekli context switching ve dispatch süreleri ne olacak? Her milisaniyenin sonunda PCB güncelle, PCB’den veri oku, CPU’ya iş getir… Context switching burada ciddi bir iş yükü ve zaman kaybı oluşturur. O zaman her process 1000 ms çalışsın diyelim. Diyemeyiz, bu sefer de – işi olan – her process CPU’yu koca bir saniye boyunca meşgul eder. O sırada bilgisayarımızı kullanamadığımızı rahatlıkla fark edebiliriz. Bu durum da FCFS’ye yakın bir görüntü oluşturur.

Priority Scheduling

RR algoritmasına göre her process aynı önceliğe sahiptir ve hepsi aynı süre çalışabilir. Fakat kullanıcıların düşüncesi daha farklı olabilir. Örneğin, arkada bir download yaparken film izlediğimizi düşünelim. İndirme işinin daha öncelikli olmasını istemezsiniz. Filminizi kesintisiz ve sorunsuz olarak izlemek istersiniz. İndirme arkaplanda olan ve zaten bir süre bekleyeceğiniz bir iştir. Bu tarz arkaplan işleri yapılırken bilgisayarınızı kullanmaya devam etmek istersiniz.

Farklı bir sistem düşünelim. Örneğin müzik yayını yapan bir sistem. Ücretli ve ücretsiz kullanıcıları olsun. Bu sistemde ücretli kullanıcılara ait işlemlerin daha hızlı gerçekleştirilmesinin istenmesi gayet mümkündür.

Priority scheduling’te her process’in bir öncelik numarası vardır. Öncelikler belirli bir sayı aralığında verilir. Örneğin 0 – 255 diyelim. Bazı sistemler öncelik numarası düşükse, öncelik de düşüktür diyebilir. Bazı sistemler de öncelik numarasının düşük olmasını “daha öncelikli” olarak yorumlayabilir. İmplementasyona göre farklılıklar olması normaldir.

Bu algoritmalardaki en büyük problem, belirsiz bloklanma süreleri (indefinite blocking), dolayısıyla CPU’ya duyulan açlıktır (starvation)^5. Yüklü çalışan bir sisteme katılan yeni bir process, önceliği çok düşük olduğu için günlerce bekleyebilir. BİR SÖYLENTİYE GÖRE, 1973 yılında MIT’deki IBM 7094 makinesi kapatıldığında, sisteme 1967 yılında eklenmiş düşük öncelikli bir process’in 6 yıldır hâlâ sırasını beklediği görülmüş^6. Zamanında yaptığım iş başvuruları gibi yani.

Bu sorunun çözümü olarak, Türk televizyonlarının vaz geçilmesi olan “yaşlandırma yönteminden” (aging)^7 faydalanılıyor. Process, kuyrukta bekledikçe önceliği kademeli olarak arttırılıyor. Bu sayede process’in yaşayacağı starvation süresi azaltılıyor.

Bazı sistemler RR algoritması ile priority algoritmasını birlikte kullanabilir. Şöyle ki, benzer önceliğe sahip process’ler gruplandırılır. Sonrasında Round-Robin devreye girer ve yüksek öncelikli process’leri gezerek tamamlamaya çalışır. Eğer yüksek öncelik grubunda bir process kalmadıysa, bir alt önceliğe geçilir ve oradaki process’ler çalıştırılır.

Multilevel Queue Scheduling

Process’lerin rahatlıkla gruplanabildiği sistemlerde kullanılmak için tasarlanmıştır. Etkileşim gerektiren process’ler, arkaplanda çalışması gereken process’ler, sistem için kritik düzeydeki process’ler gibi gruplar oluşturulur ve bu gruplar farklı process kuyrukları olarak işlenir.

Bu kuyrukların her biri için farklı scheduling algoritmaları kullanılabilir. Yüksek öncelik grubunda olan process’ler için Round-Robin tercih edilirken, düşük öncelikteki arkaplan işleri için FCFS görmemiz mümkündür. Bu yapıda, CPU zamanının büyük çoğunluğu RR ile çalışacak yüksek öncelikli gruplara atanabilirken, bir kısmı da FCFS ile çalışacak arkaplan işlerine ayrılabilir.

Yine MIT’de, IBM7094 üzerinde koşan Compatible TimeSharing System (CTSS) tasarımcıları bir sorunla karşılaşır. Sistem, belleğinde sadece bir process tutabildiği için process değişimi oldukça yavaştır. Yani her process değişiminde bellekteki process verileri diske yazılıyor ve sonraki process’in verileri diskten belleğe getiriliyordu. Bu nedenle time quantum’u arttırmayı düşündüler. Fakat bu da – yukarıda açıklamaya çalıştığım gibi – tepki süresini uzatabiliyordu. Bu nedenle çok katmanlı bir kuyruk oluşturdular ve öncelikleri kategorize ettiler. Yüksek önceliğe sahip process’ler daha sık context switching’e maruz kalırken, düşük önceliklerdeki process’ler daha uzun süreler çalışıyordu. Bu sayede hem yüksek öncelikli process’ler birlikte daha hızlı çalışıyor hem de düşük öncelikli process’ler için context switching daha az yapılıyor ve zaman kaybı azalıyordu.

Bir gün bir kullanıcı, kendi process’i çalışırken terminalinden “Enter” tuşuna basar. Sistem, bu process’in interactive bir process’e dönüşeceğini düşündüğü için öncelik grubunu yükseltir. Yüksek CPU kullanımına ihtiyaç duyan bu kullanıcı, birkaç saniyede bir enter tuşuna basarak sistemi yanıltmayı başarır ve aldığı tepki sürelerinde inanılmaz bir iyileşme görür. Sonra bu bilgi arkadaşlar arasında yayılır. 🙂

Multilevel Feedback Qeueue Scheduling

Multilevel Queue Scheduling’te, process’ler sisteme katıldığında bir kuyruğa dahil edilir ve orada kalırlar. Örneğin bir arkaplan process’i, arkaplan process’i olarak çalışmaya devam eder. Doğası budur.

Multilevel Feedback Queue Scheduling’te ise, process’lerin kuyruklar arasında geçişine izin verilir. Burada amaç, process’in karakterinden ziyade sistemi meşgul etme süresine göre değerlendirilmesidir. Yüksek önceliğe sahip bir process CPU zamanınını çok kullanıyorsa, önceliği düşürülür. Ek olarak, düşük öncelik grubunda uzun süre bekleyen process’ler de yüksek öncelik gruplarına taşınabilir.

Yüksek öncelikli process’ler, düşük time quantum değerine sahip kuyruklarda işlenirken, öncelik grubu düştükçe kullanılan algoritma FCFS bile olabilir. Bu yapı, gayet kullanışlı görünse de implementasyonu nispeten daha zordur.

Guaranteed Scheduling

Eğer n kullanıcı varsa, senin işlemlerin 1/n kadar CPU kullanır. Eğer p process’in varsa, CPU’nun 1/p zamanını alırsın. Herkese, her şeye aynı süre.

Bu sistemin doğru çalışabilmesi için, her process’in kullandığı CPU zamanları takip edilmelidir. Process’in gerçekten kullandığı ve aslında kullanması CPU zamanı oranlanır. Örneğin, bir process’in 10 birim çalışması lazımdı fakat 5 çalışmış. 5/10 = 0.5 oranı elde edilir. Farklı bir process’in ise 10 birim çalışması gerekirken 40 birim çalıştığını düşünelim. 40/10 = 4 oranı elde edilir. Oranı 0.5 olan process’e öncelik verilir ve denge sağlanmaya çalışılır.

Lottery Scheduling

Oldukça basit görünüyor aslında. Bütün process’lere sistem kaynakları için piyango bileti dağıtılıyor. Çekiliş yapılıyor ve kazanan process’ler ödül olarak kaynağı kullanıyor.

Burada da yine öncelikli process’lerin şansı var. Örneğin her process 10 bilet alabiliyorken, öncelikli process’lere 20 bilet veriliyor. Kazanma şansları kasten arttırılıyor. Dolayısıyla, biletlerin %n oranına sahip process, uzun vadede, kaynakların da %n’ine sahip oluyor.

Bu scheduling yöntemini ilginç kılan noktalardan biri, sisteme henüz katılmış bir process’in de piyangoyu kazanma ihtimalinin olması. Bu da scheduling’in, yeni katılan process’lere daha hızlı tepki verebilmesini sağlıyor. Birbiriyle ilintili işler yapan process’ler, kendi işlerini tamamladıklarında ilişkili oldukları process’e bütün biletlerini devredebilir ve o process’in kazanma şansını arttırabilir.

Bu yöntem, diğer yöntemlerle çözülmesi güç konularda kullanılabilir. Örneğin bir video server’ımız var ve farklı FPS oranlarında yayın dağıtan process’lere sahip. Process’lerin 10, 15, 25 FPS yayın yaptıklarını düşünelim. Bu durumda biletleri 10, 15, 25 oranında dağıtırız ve böylece kaynakları da bu oranda – iş yüküne göre – dağıtmış oluruz.

Fair-Share Scheduling

Bu zamana kadarki algoritmalarda, process’i kimin başlattığı konusunu düşünmedik. Çok kullanıcılı bir sistemde bir kullanıcının 400, diğer kullanıcının 100 process’i olduğunu düşünelim. RR gibi bir algoritma, tüm process’leri geziyordu hatırlarsanız. Bu durumda bir kullanıcının bir turda 400 parça işi yapılıyorken, diğer kullanıcının 100 parça işi yapılır.

Bu durumu engellemek için, CPU zamanı process’ler arasında değil, kaynaklar arasında dağıtılır. Yukarıdaki örnek için konuşursak, birinci kullanıcının birinci process’i çalıştıktan sonra, ikinci kullanıcının birinci process’i çalıştırılır (kaynakların eşit şekilde dağıtıldığını varsayarsak). Birinci kullanıcının 100. process’i sonrasında, ikinci kullanıcının 100. process’i çalıştırılır. Birinci kullanıcının 101’inden sonra ise ikinci kullanıcının 1’i, çalışmaya kaldığı yerden devam edebilir.

Real-Time Sistemlerde Scheduling

Burada da scheduling iki farklı kategoriye ayrılır. Hard real time, deadline’ın mutlaka yakalanmasının gerektiği, aksi takdirde çok ciddi sonuçlar doğurabilecek durumlardır. Soft real time ise, her ne kadar istenmese de deadline gecikmesinin kabul edilebileceği durumlardır.

Burada işler oldukça değişiyor. Process’in hard ya da soft kategoride olması, ihtiyaç duyduğu ya da ihtiyaç duyması muhtemel CPU zamanı gibi birçok etmen işin içine giriyor ve bu değerler formülize ediliyor.

Detaylı bilgi edinmek isteyenler şu iki makaleyi inceleyebilirler:

Sonuç Olarak

Process’lerin oluşturulması, çalıştırılması ve durdurulması – gördüğünüz gibi – oldukça detaylı bir süreç. Tabii ki işler burada anlatılanlarla kalmıyor. Burada anlattığım konu başlıkları, oldukça yüzeysel. İşin implementasyon tarafına geçildiğinde çok daha farklı ve beklenmedik sonuçlar çıkabilir, MIT örneğinde olduğu gibi.

Bir dahaki sefere “Bu bilgisayar niye yavaşladı ya kasıp duruyor!!!” derken, biraz da işletim sistemine hak verin derim. 🙂

Bağlantılar

1 , 2- Chapter 4. Threads and Processes, https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux_for_real_time/7/html/reference_guide/chap-threads_and_processes

3 – Context switch, https://en.wikipedia.org/wiki/Context_switch

4 – User mode and kernel mode, https://docs.microsoft.com/en-us/windows-hardware/drivers/gettingstarted/user-mode-and-kernel-mode

5 – Starvation (computer science), https://en.wikipedia.org/wiki/Starvation_(computer_science)

6, 7 – Starvation and Aging in Operating Systems, https://www.geeksforgeeks.org/starvation-and-aging-in-operating-systems/

Referans

1 – Operating System Concepts Essentials, Abraham SILBERSCHATZ (Yale University), Peter Baer GALVIN (Corporate Technologies, Inc.), Greg GAGNE (Westminster College)

2 – Modern Operating Systems, Andrew S. TANENBAUM, Herbert BOS (Vrije Universiteit)

“İşletim Sistemi 101 – #5 (CPU Scheduling)” için bir yorum

Bir cevap yazın

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