Bölüm 5: CPU Çizelgeleme

5.1Temel kavramlar

Tek görevli eski bir sistemde çizelgeleme sorunu yoktur: bellekte tek program vardır ve CPU onu çalıştırır. Program diskten veri beklediğinde CPU da boşta bekler. Çok programlı (multiprogramming) sistemler bu boşluğu doldurmak için bellekte aynı anda birçok süreç tutar. Bir süreç beklemeye geçince CPU başka birine verilir. Fikir basittir, ama hemen bir soru doğurur: hazır bekleyenlerden hangisi seçilmelidir? Bu bölümün konusu o sorudur.

5.1.1Çizelgeleme nedir?

Çizelgeleyicinin amacı iki parçalıdır. Birincisi CPU'yu boş bırakmamaktır: hazır süreç varken CPU boşta kalmamalıdır. İkincisi, sistemin hedefini iyileştirmektir. Hedef ortama göre değişir: masaüstünde hızlı tepki, sunucuda yüksek verim, paylaşımlı makinede adalet, gömülü denetleyicide son tarihe uymak. Aynı algoritma bir hedefte iyi, ötekinde kötü olabilir; bölüm boyunca bu ödünleşim tekrar tekrar karşımıza çıkacak.

Bir süreç hayatı boyunca kuyruklar arasında dolaşır (Şekil 5.1). Yeni süreç hazır kuyruğuna girer. Çizelgeleyici onu seçince CPU'da çalışır. Zaman dilimi dolarsa saat kesmesiyle durdurulur ve hazır kuyruğuna geri döner. G/Ç isterse bekleme kuyruğuna geçer, G/Ç bitince yeniden hazır olur. İşi bitince sistemden çıkar. Her çekirdekte aynı anda en fazla bir süreç çalışır; çalışanlar dışındaki bütün süreçler bir kuyruktadır.

Hazır kuyruğu adına rağmen FIFO olmak zorunda değildir. Algoritmaya göre bir öncelik kuyruğu, dengeli bir ağaç ya da sırasız bir bağlı liste olabilir. Linux'un adil çizelgeleyicisi örneğin kırmızı-siyah ağaç kullanır. Kuyruktaki kayıtlar da süreçlerin kendisi değil, süreç denetim bloklarıdır (PCB).

Bir ayrıntı daha: iş parçacıklarını destekleyen modern çekirdekler aslında süreçleri değil, çekirdek iş parçacıklarını çizelgeler. Çok iş parçacıklı bir süreçte her iş parçacığı hazır kuyruğunda ayrı bir kayıttır. Ders kitapları yine de “süreç çizelgeleme” deyimini kullanır; bu notta da süreç sözcüğü “çizelgelenen birim” anlamındadır.

5.1.2CPU–G/Ç patlama döngüsü

Çizelgelemenin başarısı süreçlerin gözlenen bir özelliğine dayanır: yürütme, CPU çalışması ile G/Ç beklemesi arasında gidip gelir. Süreç bir süre hesap yapar, sonra bir dosya okur ve bekler, sonra yine hesap yapar.

Gerçek sistemlerde ölçülen CPU patlama sürelerinin dağılımı hep aynı biçimdedir (Şekil 5.3). Çok sayıda kısa patlama, az sayıda uzun patlama vardır. Grafik üstel ya da ona benzer, sağa doğru uzun kuyruklu bir eğridir. Bu gözlem, kısa patlamalı süreçlere öncelik veren algoritmaların neden işe yaradığını açıklar.

Süreçler patlama yapılarına göre iki gruba ayrılır (Şekil 5.4). CPU'ya bağlı (CPU-bound) süreç uzun CPU patlamaları ve seyrek G/Ç yapar; video kodlama, derleme ya da bilimsel hesap böyledir. G/Ç'ye bağlı (I/O-bound) süreç kısa CPU patlamalarından sonra uzun G/Ç beklemelerine girer; metin düzenleyici, kabuk ya da veritabanı istemcisi buna örnektir. Bir süreç zamanla gruptan gruba geçebilir: önce dosyaları okuyan, sonra uzun hesap yapan bir program iki evreyi de yaşar.

Çizelgeleme açısından belirleyici olan G/Ç beklemesinin uzunluğu değil, CPU patlamasının kısalığıdır. G/Ç'ye bağlı bir süreç hazır olduğunda hemen çalıştırılırsa birkaç milisaniyede yeni bir G/Ç isteği verir. Böylece disk ya da ağ kartı da meşgul kalır. Bu süreç uzun bir CPU işinin arkasında bekletilirse aygıt boşta kalır. Disk teknolojisi CPU'dan çok daha yavaş geliştiği için süreçlerin büyük kısmı zamanla G/Ç'ye bağlı hâle gelmiştir. Bu yüzden G/Ç'ye bağlı süreçleri bekletmemek modern çizelgeleyicilerin ortak tasarım ilkesidir.

5.1.3G/Ç ile örtüşme: patlamaları ayrı iş saymak

Bir sürecin her CPU patlamasını ayrı, kısa bir iş saymak, çizelgeleyiciye G/Ç ile hesaplamayı örtüştürme fırsatı verir. Bu fikir bölümdeki algoritmaların çoğunun arkasında yatar; en iyi bir örnekle anlaşılır.

Gerçek bir sistem patlama sürelerini önceden bilmez. Bu yüzden “kısa patlamalıyı öne al” kuralı ancak dolaylı olarak uygulanabilir. Çok düzeyli geri beslemeli kuyruk tam olarak bunu yapar: süreçlerin davranışını gözleyip kısa patlamalıları üst kuyruklarda tutar.

5.1.4Çizelgeleme kararları ne zaman alınır?

Çizelgeleyici sürekli çalışan bir döngü değildir; belirli olaylarda çağrılır. Süreç durum diyagramında dört geçiş bir karar gerektirebilir (Şekil 5.6):

1. Çalışıyor → bekliyor. Süreç G/Ç ister ya da bir çocuğunu wait() ile bekler. CPU boşalır; yeni bir süreç seçmek zorunludur.
2. Çalışıyor → hazır. Saat kesmesi gelir, sürecin zaman dilimi dolmuştur. Çalışanı durdurup başkasını seçmek isteğe bağlıdır.
3. Bekliyor → hazır. Bir G/Ç tamamlanır ve bekleyen süreç uyanır. Uyanan süreç o an çalışandan daha önemliyse çalışanı kesebilir.
4. Sonlanma. Süreç exit() ile biter. CPU boşalır; seçim yine zorunludur.

1. ve 4. durumlarda başka seçenek yoktur: CPU boştur ve birine verilmelidir. 2. ve 3. durumlarda ise CPU hâlâ bir süreci çalıştırıyor; çizelgeleyici onu çalışmaya bırakmayı da seçebilir. Çizelgeleyiciler bu iki durumda karar verip vermediklerine göre ikiye ayrılır.

5.1.5Kesmeli ve kesmesiz çizelgeleme

Kesmesiz çizelgeleme saat kesmesine ihtiyaç duymaz ve bağlam değiştirme sayısı azdır. Bedeli, sistemin her programın iyi niyetine bağlı kalmasıdır. Windows 3.x ve klasik Mac OS (9 ve öncesi) işbirlikçi çoklu görev kullanıyordu. Sonsuz döngüye giren tek bir program CPU'yu hiç bırakmadığı için bütün sistemi kilitleyebiliyordu. Kesmeli çizelgeleme bunu saat kesmesiyle önler: çekirdek belirli aralıklarla CPU'yu geri alır. Bugün bütün genel amaçlı işletim sistemleri kesmelidir (Şekil 5.7).

Kesmenin de bir bedeli vardır. İki süreç ortak bir veriyi paylaşıyorsa biri veriyi güncellerken kesilebilir. Öteki süreç verinin yarım kalmış, tutarsız hâlini okuyabilir. Bu yarış durumu (race condition) riski, kesmeli sistemlerde senkronizasyon araçlarını zorunlu kılar. Ayrıca her kesme bir bağlam değiştirme demektir ve bu da CPU zamanı harcar.

Aynı soru çekirdeğin kendi kodu için de sorulur. Bir süreç sistem çağrısının ortasında çekirdek kodunu çalıştırırken kesilebilir mi? Eski UNIX çekirdekleri çağrının bitmesini beklerdi. Linux 2.6 sürümünden beri çekirdek kodu da kesilebilir; kesme yalnız çalışan kod hiçbir kilit tutmuyorsa yapılır. Çekirdek bunu her görev için tuttuğu preempt_count sayacıyla izler: sayaç sıfırsa kesmek güvenlidir. Gerçek zamanlı kullanım için geliştirilen PREEMPT_RT yamaları yaklaşık yirmi yıllık çalışmadan sonra 2024'te Linux 6.12 ile ana çekirdeğe girdi. Bu yapılandırmada kesme işleyicileri de iş parçacığı olarak çalışır ve kesilebilir; en kötü durum gecikmesi mikrosaniyeler düzeyine iner.

Hangi yaklaşımın seçileceği ortama bağlıdır. Gece çalışan toplu işlerde kesmesiz ya da uzun dilimli kesmeli algoritmalar yeterlidir, çünkü kimse ekran başında beklemez. Etkileşimli sistemlerde ve sunucularda kesme zorunludur: bir sürecin CPU'yu tekeline alması öteki kullanıcıların isteklerini dakikalarca bekletebilir.

5.1.6Görev dağıtıcı ve bağlam değiştirme

Seçim yapmak ile seçilen süreci çalıştırmak iki ayrı iştir. Seçimi çizelgeleyici yapar; bu bir politikadır. Seçilen süreci CPU'ya yerleştirmek ise bir mekanizmadır ve onu görev dağıtıcı üstlenir.

Dağıtıcı her bağlam değiştirmede çalıştığı için çok hızlı olmalıdır. Bugünkü işlemcilerde doğrudan maliyet birkaç mikrosaniyedir. Dolaylı maliyet daha büyük olabilir: yeni sürecin verisi önbellekte yoktur ve ilk erişimler ıskalarla yavaşlar. Tablo 5.1 süreçler arası bir geçişte nelerin değiştiğini özetler.

Linux'ta bağlam değiştirmeler doğrudan ölçülebilir. vmstat 1 komutu her saniye bir satır basar; cs sütunu o saniyedeki toplam bağlam değiştirme sayısıdır. Tek bir süreç için /proc/<pid>/status dosyası iki sayaç tutar. voluntary_ctxt_switches, sürecin bloke olarak CPU'yu kendisinin bıraktığı geçişleri sayar. nonvoluntary_ctxt_switches ise çizelgeleyicinin süreci zorla kestiği geçişleri sayar. G/Ç'ye bağlı bir süreçte ilk sayaç, CPU'ya bağlı bir süreçte ikincisi büyür.

5.1.7Ortama göre hedefler

Tek bir “en iyi” çizelgeleyici yoktur, çünkü sistemlerin istedikleri farklıdır. Tanenbaum hedefleri ortamlara göre gruplar (Tablo 5.2). Bazı hedefler her sistemde geçerlidir. Adalet, benzer süreçlerin benzer CPU payı almasıdır. Politika uygulama, sistemin koyduğu kurala uymaktır; örneğin güvenlik denetim süreçlerinin önce çalışması. Denge ise CPU'nun ve G/Ç aygıtlarının birlikte meşgul tutulmasıdır.

Orantılılık ilginç bir hedeftir. Kullanıcı büyük bir dosyayı sıkıştırmanın uzun süreceğini bilir ve bekler. Ama bir pencereyi kapatmanın birkaç saniye sürmesine katlanmaz. İyi bir etkileşimli çizelgeleyici gecikmeyi işin algılanan büyüklüğüyle orantılı tutar.

Toplu işler eski zamanlardan kalma bir kavram değildir. Bankaların gece çalışan bordro ve hesap kapatma işleri, bilimsel hesaplar, yapay zekâ modellerinin eğitimi ve sürekli tümleştirme (CI) derlemeleri bugün de toplu iştir. Yüksek başarımlı hesap merkezlerinde bu işler Slurm gibi kuyruk yöneticileriyle sıraya konur. Hedefler çoğu zaman birbiriyle çelişir: tepki süresini kısaltmak için sık bağlam değiştirmek, her geçişin maliyeti yüzünden verimi düşürür.

5.1.8Çizelgeleme ölçütleri

Algoritmaları karşılaştırmak için hedefleri ölçülebilir büyüklüklere çevirmek gerekir. Bir sürecin hayatındaki üç an bu ölçütlerin hepsini tanımlamaya yeter: sisteme geliş anı G, CPU'ya ilk çıkış anı İ ve bitiş anı B (Şekil 5.9).

İlk iki ölçütün büyük, son üçünün küçük olması istenir. Gerçek sistemlerde CPU kullanımı hafif yüklü bir makinede %40, yoğun bir sunucuda %90 dolayındadır. Ölçütlerin hiçbiri tek başına yeterli değildir; algoritmalar arasındaki farklar en açık ortalama bekleme, ortalama dönüş ve ortalama tepki sürelerinde görünür.

Bu ölçütlerden biri ötekilerden daha temeldir. Bir sürecin CPU süresi ve G/Ç süresi programın kendisine aittir; hangi algoritma seçilirse seçilsin değişmez. Çizelgeleyicinin etkileyebildiği tek şey sürecin hazır kuyruğunda beklediği süredir. Dönüş süresi = CPU süresi + G/Ç süresi + bekleme süresi olduğuna göre, iki algoritma arasındaki dönüş farkı bekleme farkının ta kendisidir.

Tepki süresi ile bekleme süresi kolay karışır. Tepki yalnız ilk beklemeyi ölçer: kullanıcı komutu yazdıktan sonra ekranda ilk hareketi ne zaman görür? Bekleme süresi ise sürecin hayatı boyunca kuyrukta geçirdiği bütün aralıkların toplamıdır. Kesmeli bir algoritmada süreç birçok kez kesilip kuyruğa dönebilir; tepki süresi küçük kalırken bekleme süresi büyüyebilir.

Etkileşimli sistemlerde ortalamadan çok tepki süresinin varyansı önemlidir. Komutların çoğu 0,1 saniyede, arada bir de 5 saniyede yanıtlanırsa kullanıcı bunu, hepsinin 0,5 saniyede yanıtlanmasından daha rahatsız edici bulur. Son olarak ağırlıklı (normalleştirilmiş) dönüş süresi, dönüş süresinin CPU süresine oranıdır. İdeal değeri 1'dir ve kısa işlerin ne kadar cezalandırıldığını gösterir.

5.2Temel algoritmalar

Algoritmaları anlamanın en iyi yolu onları elle çalıştırmaktır. Bu kesimdeki algoritmalar aynı dört süreç üzerinde adım adım izlenir; her birinin sonunda bekleme, dönüş ve tepki ortalamaları ile bağlam değiştirme sayısı verilir. Böylece bir algoritmanın neyi iyileştirip neyi kötüleştirdiği sayılarla görülür.

5.2.1Ortak süreç kümesi

Tablo 5.3 bölüm boyunca kullanılan ortak kümeyi verir. Dört süreç birer milisaniye arayla gelir; CPU süreleri 4 ile 9 ms arasındadır. Öncelik sütunu yalnız öncelik algoritmasında kullanılır (Şekil 5.10).

Hesaplarda dört kural geçerlidir. Küçük öncelik sayısı yüksek öncelik demektir. Eşitlikte önce gelen süreç kazanır. Round Robin'de bir sürecin geldiği anda başka bir sürecin dilimi doluyorsa yeni gelen kuyruğa önce girer. Bağlam değiştirme süresi sıfır kabul edilir ve süreçler G/Ç yapmaz. Bu varsayımlar gerçekçi değildir, ama algoritmaların farkını yalın biçimde gösterir. Aynı hesapları farklı kümelerle denemek için CPU çizelgeleme simülatörü kullanılabilir; simülatör Gantt şemasını ve ölçütleri anında çizer.

Bağlam değiştirme sayısı da şöyle sayılır: Gantt şemasında art arda gelen iki parçanın süreci farklıysa bir geçiş vardır. İlk sürecin CPU'ya çıkması geçiş sayılmaz. Bir süreç diliminin sonunda kuyrukta tek başınaysa yeni dilime geçmesi de geçiş değildir.

5.2.2FCFS

FCFS, gerçeklemesi en kolay algoritmadır: yeni süreç kuyruğun sonuna eklenir, CPU boşalınca baştaki çıkarılır. Her iki işlem O(1)'dir. Ortak kümede izleme şöyledir:

• t = 0. Kuyrukta yalnız P1 vardır. P1 CPU'yu alır ve 8 ms boyunca bırakmaz. Bu sürede P2, P3 ve P4 gelip sırayla kuyruğa girer.
• t = 8. P1 biter. Kuyruğun başındaki P2 çalışır. P2 1'de gelmişti, 8 − 1 = 7 ms bekledi.
• t = 12. P2 biter, P3 çalışır; 12 − 2 = 10 ms bekledi.
• t = 21. P3 biter, P4 çalışır; 21 − 3 = 18 ms bekledi. P4 26'da biter (Şekil 5.11; Tablo 5.4).

Ortalama bekleme 35 / 4 = 8,75 ms, ortalama dönüş 61 / 4 = 15,25 ms'dir. Kesmesiz algoritmalarda süreç ilk kez çalışmaya başladığında bitene kadar sürdüğü için tepki süresi bekleme süresine eşittir. Gantt şemasında üç geçiş vardır: P1→P2, P2→P3, P3→P4.

5.2.3Konvoy etkisi

FCFS'nin ortalama bekleme süresi sabit değildir; süreçlerin geliş sırasına aşırı duyarlıdır. Silberschatz'ın klasik örneği bunu açıkça gösterir.

Sorun, süreçlerin G/Ç yaptığı dinamik bir ortamda daha da büyür. Bir CPU'ya bağlı süreç C ile birkaç G/Ç'ye bağlı süreç (I1, I2, I3) düşünelim. C uzun patlamasıyla CPU'yu tutarken G/Ç'ye bağlı süreçlerin G/Ç'leri biter ve hepsi hazır kuyruğunda C'nin arkasına dizilir. Bu sırada disk boştadır. C sonunda G/Ç'ye gidince I1, I2, I3 kısa patlamalarını hızla bitirir ve diske giderler. Bu kez CPU boşta kalır. Ardından C geri gelir ve döngü yinelenir.

FCFS'de açlık yoktur: her süreç önündekiler bitince mutlaka çalışır. Ama kesmesiz olduğu için tek bir uzun iş sistemi uzun süre tutabilir. Bu yüzden FCFS etkileşimli sistemlere uygun değildir. Yine de birçok algoritmanın içinde yaşar: eşit öncelikli süreçler arasındaki bağı çözmek için genellikle geliş sırasına bakılır.

5.2.4Kod izleme: FCFS bekleme süresi

FCFS'nin bekleme hesabı tek bir döngüyle yapılabilir. Aşağıdaki C fonksiyonu geliş sırasına göre sıralanmış süreç dizisini alır, her sürecin beklemesini yazar ve ortalamayı basar.

/* p[] geliş sırasına göre sıralı */
void fcfs(Surec p[], int n) {
  int t = 0, top = 0;
  for (int i = 0; i < n; i++) {
    if (t < p[i].gelis) t = p[i].gelis;
    int bekleme = t - p[i].gelis;
    t += p[i].sure;          /* bitiş */
    top += bekleme;
    printf("%s: %d\n", p[i].ad, bekleme);
  }
  printf("ort = %.2f\n", (double) top / n);
}

t, CPU'nun boşaldığı anı tutan saattir; top beklemelerin toplamıdır. Döngü her süreç için önce saatin sürecin gelişinden geride olup olmadığına bakar. Geride ise CPU boşta beklemiştir ve saat geliş anına ileri alınır. Ortak kümede süreçler CPU boşalmadan geldiği için bu satır hiç çalışmaz, ama boşluklu kümelerde gereklidir. Sonra bekleme t - p[i].gelis olarak hesaplanır: süreç gelişinden CPU'yu alana kadar beklemiştir. t += p[i].sure saati sürecin bitişine taşır. En sonda toplam süreç sayısına bölünür; (double) dönüşümü tam sayı bölmesini önler (Tablo 5.5).

Fonksiyon O(n) zamanda çalışır ve ek bellek kullanmaz. Dizinin sıralı olması gerekir; sıralama O(n log n) sürer. Programın çıktısında ondalık ayırıcı noktadır, çünkü printf C yerel ayarıyla çalışır.

5.2.5SJF: en kısa iş önce

Konvoy örneği bir ipucu verir: kısa işleri öne almak ortalama beklemeyi düşürür. SJF bu fikri kurala dönüştürür.

Algoritmanın adı biraz yanıltıcıdır. Seçimi işin toplam uzunluğu değil, bir sonraki CPU patlamasının uzunluğu belirler. Daha doğru ad “en kısa sonraki CPU patlaması” olurdu.

Gerekçe şudur. Dört iş a, b, c, d sürelerinde ve bu sırayla çalışsın. İlk iş a sürede biter, ikincisi a + b'de, üçüncüsü a + b + c'de, dördüncüsü a + b + c + d'de. Ortalama dönüş (4a + 3b + 2c + d) / 4'tür. İlk işin süresi dört dönüş süresinin hepsine eklenir, sonuncununki yalnız birine. En büyük katsayı a'nındır; toplamı küçültmek için en kısa iş başa konmalıdır. Herhangi bir sırada komşu iki iş kısa olan önde olacak biçimde yer değiştirirse toplam ya azalır ya aynı kalır. Bu yer değiştirmeler sonunda sıra SJF sırasına varır (Şekil 5.14).

Teoremin iki koşulu vardır ve ikisi de önemlidir. Birincisi işlerin aynı anda hazır olmasıdır. İşler farklı zamanlarda geliyorsa kesmesiz SJF optimal değildir: uzun bir iş başladıktan hemen sonra kısa bir iş gelirse SJF onu bekletmek zorundadır. Bu durumda optimal olan, kesmeli sürüm SRTF'dir. İkinci koşul sürelerin bilinmesidir. Toplu sistemlerde kullanıcı işini gönderirken bir süre sınırı verir; Slurm'deki --time seçeneği buna örnektir. Kısa sınır veren işin önce çalışma şansı artar, ama süre aşılırsa iş sonlandırılır. Kısa vadeli çizelgelemede ise sonraki patlama hiçbir şekilde bilinemez; ancak geçmiş patlamalardan tahmin edilebilir.

SJF'nin bir de açlık sorunu vardır. Sürekli kısa işler gelirse uzun bir iş hiç seçilmeyebilir. SJF ortalama bekleme ve dönüş süresini en aza indirmeyi hedefler; CPU kullanımını artırmaz. CPU, bu bölümdeki her algoritmada hazır iş olduğu sürece zaten meşguldür.

5.2.6SJF ortak kümede ve ağırlıklı dönüş

Ortak kümede süreçler farklı anlarda gelir ve kesmesiz SJF'nin zayıflığı görünür. t = 0'da yalnız P1 vardır ve CPU'yu alır. Sonradan gelen kısa işler P1'i durduramaz.

• t = 0. Yalnız P1 hazır; 0–8 çalışır.
• t = 8. P1 bitti. Hazır: P2 (4), P3 (9), P4 (5). En kısa P2; 8–12 çalışır.
• t = 12. Hazır: P3 (9), P4 (5). En kısa P4; 12–17 çalışır.
• t = 17. Yalnız P3 kaldı; 17–26 çalışır (Şekil 5.16; Tablo 5.6).

SJF, FCFS'ye göre ortalama beklemeyi 8,75'ten 7,75'e indirdi. İlk iki süreç FCFS ile aynı çalıştı; fark, P4'ün P3'ün önüne geçmesinden geldi. P4'ün beklemesi 18'den 9'a düştü, P3'ünki 10'dan 15'e çıktı: kısa işe kazandırılan 9 ms, uzun işten alınan 5 ms'den fazladır.

Ağırlıklı dönüş süresi bu takası daha görünür kılar. Tablo 5.7 beş işlik başka bir kümede iki algoritmayı karşılaştırır.

SJF'de A 0–4 çalışır. t = 4'te B (3), C (5), D (2) ve E (4) hazırdır; en kısa D 4–6 çalışır. Sonra B 6–9, E 9–13 ve en son C 13–18 gelir. C'nin ağırlıklı dönüşü 16 / 5 = 3,2'dir. SJF'nin ortalaması 2,12, FCFS'ninki 2,8'dir. FCFS'de en büyük ceza 2 ms'lik D'ye düşer: 11 ms'lik dönüşü CPU süresinin 5,5 katıdır.

FCFS'nin kısa işleri cezalandırması uç bir kümede daha çarpıcıdır. A (geliş 0, CPU 1), B (1, 100), C (2, 1), D (3, 100) kümesinde 1 ms'lik C, B'nin arkasında 99 ms bekler. C'nin dönüşü 100, ağırlıklı dönüşü 100 / 1 = 100 olur. Aynı beklemeye uğrayan D'nin ağırlıklı dönüşü ise yalnız 199 / 100 = 1,99'dur. Uzun iş için 99 ms bekleme önemsizdir, kısa iş için felakettir.

5.2.7Sonraki patlamayı tahmin: üstel ortalama

SJF'yi kısa vadeli çizelgede kullanmanın tek yolu sonraki patlamayı tahmin etmektir. Yaygın yöntem, geçmiş patlamaların üstel ortalamasıdır.

Formül yeni tahmini iki bilginin karışımı olarak kurar: en son ölçüm ve geçmişin özeti olan eski tahmin. α ikisinin ağırlığını belirler. α = 0 ise son ölçüm hiç hesaba katılmaz ve tahmin hep τ₀ kalır. α = 1 ise yalnız son patlama sayılır; tahmin bir öncekiyle aynıdır. Yaygın seçim α = ½'dir: son ölçüm ile geçmiş eşit ağırlık alır.

Adı formül açıldığında anlaşılır:

τ_n+1 = α t_n + (1 − α) α t_n−1 + (1 − α)² α t_n−2 + … + (1 − α)ⁿ⁺¹ τ₀

1 − α birden küçük olduğu için her eski ölçümün ağırlığı bir öncekinden (1 − α) kat azdır. α = ½ için son ölçümün ağırlığı ½, bir öncekinin ¼, daha öncekinin ⅛'dir. Tanenbaum aynı fikri yaşlandırma (aging) adıyla anlatır: tahminler T₀, T₀/2 + T₁/2, T₀/4 + T₁/4 + T₂/2, … diye ilerler. Bu “yaşlandırma” sözcüğü öncelik çizelgemedeki yaşlandırmayla karıştırılmamalıdır; ikincisi açlığı önleme yöntemidir.

Aşağıdaki program α = 0,5 ve τ₀ = 10 ile yedi patlamalık bir diziyi işler.

double tau = 10.0;      /* τ0 */
const double a = 0.5;  /* α */
int t[] = { 6, 4, 6, 4, 13, 13, 13 };
for (int n = 0; n < 7; n++) {
  printf("%.1f %d\n", tau, t[n]);
  tau = a * t[n] + (1 - a) * tau;
}
printf("sonraki: %.1f\n", tau);

Döngü her adımda önce o patlama için yapılmış tahmini ve gerçek değeri basar, sonra tahmini günceller. Güncelleme satırı formülün birebir karşılığıdır: a * t[n] son ölçümün payı, (1 - a) * tau eski tahminin payıdır. Döngü bitince yedi ölçümün hepsini görmüş tahmin “sonraki” diye basılır (Tablo 5.8).

Programın çıktısı yedi satır 10.0 6, 8.0 4, 6.0 6, 6.0 4, 5.0 13, 9.0 13, 11.0 13 ve son olarak sonraki: 12.0'dır. Dizinin ilk yarısında patlamalar 4 ile 6 arasında gidip gelir ve tahmin bu aralığa iner. Patlamalar 13'e sıçrayınca tahmin 5 → 9 → 11 → 12 diye birkaç adımda yetişir; her adımda kalan farkın yarısını kapatır. Tahminin gerçeği bir gecikmeyle izlediği Şekil 5.17'de açıkça görülür.

α'nın seçimi bir ödünleşimdir. Aynı dizi α = 0,75 ile çalıştırılırsa son tahmin ≈ 12,9 olur ve sıçramaya daha hızlı yetişilir; ama tek bir aykırı ölçüm de tahmini o kadar sarsar. α = 0,25 ile son tahmin ≈ 10,3'te kalır: tahmin kararlıdır, ama değişime geç uyar.

5.2.8SRTF: en kısa kalan süre önce

Ortak kümede SRTF izlemesi:

• t = 0. Yalnız P1 vardır ve çalışmaya başlar.
• t = 1. P2 gelir (4 ms). P1'in kalanı 8 − 1 = 7'dir. 4 < 7 olduğu için P1 kesilir, P2 çalışır.
• t = 2. P3 gelir (9). P2'nin kalanı 3'tür ve 3 ≤ 9; kesme yoktur.
• t = 3. P4 gelir (5). P2'nin kalanı 2'dir ve 2 ≤ 5; kesme yoktur.
• t = 5. P2 biter. Kalan süreler P1 7, P3 9, P4 5; en kısa P4 seçilir ve 5–10 çalışır.
• t = 10. P4 biter. Kalanlar P1 7, P3 9; P1 10–17 kaldığı yerden devam eder.
• t = 17. P1 biter, P3 17–26 çalışır (Şekil 5.18; Tablo 5.9).

SRTF bu kümede ortalama beklemeyi 6,5 ms'ye indirir; incelediğimiz algoritmaların en iyisidir. Bedeli dört bağlam değiştirmedir (P1→P2, P2→P4, P4→P1, P1→P3). Kesmeli algoritmalarda tepki ile bekleme ayrışır: P1'in tepki süresi 0, ama bekleme süresi 9'dur, çünkü 1–10 aralığında kuyrukta beklemiştir.

SRTF, işler farklı zamanlarda geldiğinde ortalama bekleme açısından optimaldir; ama SJF'nin iki sorununu da devralır. Kalan süreleri bilmek gerekir ve uzun işler açlık çekebilir. Ayrıca her gelişte karşılaştırma yapıldığı için geçiş sayısı artabilir.

5.2.9Öncelik çizelgeleme

Sayının yönü sistemden sisteme değişir ve bu sık bir karışıklık kaynağıdır. Linux'un nice değerinde ve çekirdek içi öncelik ölçeğinde küçük sayı yüksek önceliktir. Windows'ta ise büyük sayı yüksek önceliktir: 31 en yüksek düzeydir.

Öncelikler iç ya da dış etkenlerden gelir. İç öncelikler ölçülebilir büyüklüklere dayanır: bellek gereksinimi, açık dosya sayısı, ölçülen ortalama G/Ç patlamasının CPU patlamasına oranı. Dış öncelikler işletim sisteminin dışında belirlenir: işin önemi, ödenen ücret, kurumun politikası. SJF aslında öncelik çizelgemenin özel bir durumudur; önceliği tahmin edilen sonraki patlama belirler. Bütün öncelikler eşitse algoritma FCFS'ye döner.

Öncelik çizelgeleme kesmeli ya da kesmesiz olabilir. Kesmeli sürümde yeni gelen süreç çalışandan daha öncelikliyse onu keser. Kesmesiz sürümde yeni süreç kuyruğun başına konur ama çalışanın bitmesini bekler. Aynı öncelik düzeyindeki süreçler arasında RR uygulanabilir; Şekil 5.19(b) bu birleşimi gösterir.

(b) şıkkında öncelik 1'deki P4 tek başına 0–7 çalışır. Öncelik 2'de P2 (5) ile P3 (8) iki milisaniyelik dilimlerle dönüşümlü çalışır: P2 7–9, P3 9–11, P2 11–13, P3 13–15, P2 15–16'da biter, P3 16–20'de biter. Öncelik 3'te P1 (4) ile P5 (3) aynı biçimde 20–27 arasını paylaşır. Beklemeler P1 22, P2 11, P3 12, P4 0, P5 24'tür.

Öncelik çizelgemenin önemli bir yan etkisi öncelik terslemesidir (priority inversion). Yüksek öncelikli H süreci, düşük öncelikli L'nin tuttuğu bir kilidi beklesin. L kilidi bırakmak için çalışmalıdır, ama orta öncelikli M süreçleri sürekli L'nin önüne geçer. Sonuçta H, kendisinden düşük öncelikli M'lerin hepsini beklemek zorunda kalır. Çözüm öncelik kalıtımıdır: kilidi tutan L, kilit bırakılana kadar bekleyenin önceliğini geçici olarak devralır.

Ortak kümede kesmeli öncelik çizelgeleme şöyle ilerler (öncelikler P1 2, P2 3, P3 1, P4 4):

• t = 0. Yalnız P1 vardır ve çalışır.
• t = 1. P2 gelir (öncelik 3). Çalışan P1'in önceliği 2 daha yüksektir; kesme yok.
• t = 2. P3 gelir (öncelik 1). P1'den yüksektir; P1 kesilir, P3 çalışır.
• t = 3. P4 gelir (öncelik 4). P3'ten düşüktür; kesme yok.
• t = 11. P3 biter. Hazır: P1 (2), P2 (3), P4 (4). P1 11–17 kalan 6 ms'sini çalışır.
• t = 17. P2 17–21, ardından P4 21–26 çalışır (Şekil 5.20; Tablo 5.10).

Ortalama bekleme 10,75 ms ile FCFS'den bile kötüdür. Bu şaşırtıcı değildir: öncelik algoritması bekleme süresini değil, önemli işlerin bekletilmemesini hedefler. En önemli P3 hiç beklemedi; en önemsiz P4 18 ms bekledi.

5.2.10Açlık ve yaşlandırma

Öncelik çizelgemede açlık gerçek bir sorundur. Yüksek öncelikli işler sürekli gelirse düşük öncelikli bir iş sonsuza kadar bekleyebilir. Bir söylentiye göre 1973'te MIT'deki IBM 7094 kapatıldığında 1967'de gönderilmiş ve hâlâ çalışmamış düşük öncelikli bir iş bulunmuştu. Yaşlandırma bu beklemeye üst sınır koyar.

Yaşlandırma açlığı ortadan kaldırmaz, ama sonsuz beklemeyi sınırlı bir beklemeye çevirir. Sınır öncelik aralığıyla ve artış hızıyla orantılıdır. Bir sistemde öncelikler 0 ile 63 arasında olsun ve her 10 saniyede bir artırılsın. Önceliği 63 olan süreç hiç çalışmasa bile en geç 63 × 10 = 630 saniyede (10,5 dakika) en yüksek önceliğe ulaşır.

5.3Round Robin

FCFS adildir ama kesmesizdir; SJF ve SRTF ortalamada iyidir ama süreleri bilmek ister. Etkileşimli sistemler ise süre bilgisi olmadan herkese çabuk tepki veren bir algoritmaya ihtiyaç duyar. Round Robin bu ihtiyaca verilen en eski ve en yaygın cevaptır.

5.3.1Döngüsel sıra ve zaman dilimi

RR'nin en değerli özelliği, bekleme için kesin bir üst sınır vermesidir. Kuyrukta n süreç varsa ve dilim q ise hiçbir süreç bir sonraki dilimini (n − 1) · q süreden uzun beklemez. Çünkü önündeki her süreç en fazla bir dilim kullanır. Örneğin 5 süreç ve 20 ms dilimle her süreç en geç 80 ms'de bir kez CPU'ya çıkar. Tepki süresi sınırlıdır ve açlık yoktur.

Bedeli dönüş süresindedir. RR süreçleri dönüşümlü çalıştırdığı için hepsi işin sonuna kadar uzar; dönüş süresi genellikle SJF'den kötüdür. Buna karşılık tepki süresi çok daha iyidir. Silberschatz'ın klasik örneği farkı sayılarla gösterir (Şekil 5.23).

Bu örnekte P2 ilk turda 17 ms'lik işini bitirir. P4 ikinci turda kalan 4 ms'sini 117–121 arasında kullanır; parça çok dar olduğu için şemada etiketi yoktur. Bitişler P1 134, P2 37, P3 162, P4 121'dir. Beklemeler P1 134 − 53 = 81, P2 20, P3 162 − 68 = 94, P4 121 − 24 = 97; ortalama 292 / 4 = 73 ms. SJF sırası (P2, P4, P1, P3) beklemeleri 0, 17, 41, 94 yapar ve ortalama 38 ms'ye iner. Ama SJF'de P3 ilk kez 94. ms'de CPU'ya çıkar; RR'de ise 37. ms'de.

RR'nin bir zayıflığı da G/Ç'ye bağlı süreçlere karşı tutumudur. G/Ç'ye bağlı süreç dilimin küçük bir kısmını kullanıp bloke olur, G/Ç bitince kuyruğun sonuna döner. CPU'ya bağlı süreçler ise her seferinde dilimin tamamını kullanır. Sonuçta CPU'ya bağlılar CPU'dan daha büyük pay alır. Bu dengesizlik, MLFQ ve “sanal RR” (G/Ç'den dönen sürece ayrı, öncelikli bir yardımcı kuyruk) gibi iyileştirmelerin çıkış noktasıdır.

5.3.2Ortak kümede q = 2 ve q = 5

RR'yi ortak kümede iki farklı dilimle izleyelim. Kural hatırlanmalıdır: bir sürecin dilimi dolarken o arada yeni süreçler gelmişse yeniler kuyruğa önce, dilimi dolan süreç sonra girer.

Ortalama tepki 2 ms'ye düştü; bu, şimdiye kadarki en iyi değerdir. Ama ortalama bekleme 12,75 ve ortalama dönüş 19,25 ms ile en kötüsüdür. Gantt şemasında 13 parça ve 12 bağlam değiştirme vardır. Gerçek bir sistemde her geçiş birkaç mikrosaniye yer; bu küçük örnekte sıfır kabul edilse de dilim küçüldükçe yük büyür.

Aynı küme q = 5 ile çalıştırıldığında tablo değişir. P1 0–5 çalışır (kalan 3); bu sürede gelen P2, P3, P4 kuyruğa önce girer. P2 5–9'da dilim dolmadan biter. P3 9–14 (kalan 4), P4 14–19'da biter. P1 19–22'de, P3 22–26'da biter (Şekil 5.25; Tablo 5.12).

Daha büyük dilimle geçiş sayısı 12'den 5'e iner; ortalama bekleme 11'e, dönüş 17,5'e iyileşir. Buna karşılık ortalama tepki 2'den 5,5 ms'ye çıkar. Dilim büyüdükçe RR FCFS'ye yaklaşır.

5.3.3Kod izleme: rr()

RR'nin çekirdeği birkaç satırlık bir döngüdür. Aşağıdaki fonksiyon geliş sırasına göre sıralı diziyi alır ve her sürecin bitiş anını basar. gelenleri_ekle(p, n, &k, t) yardımcı fonksiyonu, t anına kadar gelmiş ama henüz kuyruğa girmemiş süreçleri sırayla kuyruğa ekler. k, dizide eklenecek sıradaki sürecin indisidir.

/* p[] geliş sırasına göre sıralı */
void rr(Surec p[], int n, int q) {
  int t = 0, k = 0;     /* k: sıradaki */
  gelenleri_ekle(p, n, &k, t);
  while (!bos()) {
    Surec *s = cikar();  /* baştaki */
    int dilim = min(q, s->kalan);
    t += dilim; s->kalan -= dilim;
    gelenleri_ekle(p, n, &k, t); /* önce */
    if (s->kalan > 0) ekle(s);   /* sonra */
    else printf("%s %d\n", s->ad, t);
  }
}

Döngünün her turu bir dağıtımdır. Kuyruğun başındaki süreç çıkarılır ve min(q, s->kalan) kadar çalıştırılır: kalan süre dilimden kısaysa süreç dilimi doldurmadan biter. Saat ilerletilir, kalan süre azaltılır. Ardından gelen iki satırın sırası RR'nin bağ çözme kuralını belirler. Önce bu dilim sırasında gelen yeni süreçler eklenir, sonra işi bitmeyen süreç kuyruğun sonuna döner. İki satır yer değiştirseydi dilimi dolan süreç yeni gelenlerin önüne geçerdi ve çizelge farklı olurdu. İşi biten süreç kuyruğa dönmez; adı ve bitiş anı basılır (Tablo 5.13).

Kuyruk boşalınca döngü biter: 8 dağıtım ve 7 bağlam değiştirme. Beklemeler P1 20 − 8 = 12, P2 8 − 1 − 4 = 3, P3 26 − 2 − 9 = 15, P4 25 − 3 − 5 = 17; ortalama 11,75 ms. Ortalama dönüş 18,25, ortalama tepki (0 + 3 + 6 + 9) / 4 = 4,5 ms'dir (Şekil 5.26).

Her tur O(1) zamanda çalışır: kuyruktan çıkarma ve kuyruğa ekleme sabit sürelidir. Toplam tur sayısı, her sürecin CPU süresinin q'ya bölünüp yukarı yuvarlanmasının toplamıdır. Bu örnekte 2 + 1 + 3 + 2 = 8'dir. Dolayısıyla q küçüldükçe dağıtım sayısı ters orantılı olarak büyür.

5.3.4Zaman dilimi seçimi

RR'nin tek parametresi q'dur ve davranışı büyük ölçüde ona bağlıdır. Ortak küme farklı dilimlerle çalıştırıldığında Tablo 5.14 elde edilir (Şekil 5.27).

Tablodan üç sonuç çıkar. Birincisi, q küçüldükçe tepki iyileşir ama geçiş sayısı artar. İkincisi, ortalama bekleme ve dönüş q ile tekdüze değişmez: q = 3, q = 2'den de kötüdür; q = 5, q = 6'dan iyidir. Üçüncüsü, q en uzun patlamaya (burada P3'ün 9 ms'si) eşit ya da ondan büyük olunca hiçbir süreç kesilmez ve RR tam olarak FCFS olur.

Dönüş süresinin q ile tekdüze değişmediği başka bir kümede de görülür. P1 6, P2 3, P3 1, P4 7 ms (hepsi t = 0'da) için ortalama dönüş q = 1'den 7'ye 11; 11,5; 10,75; 11,5; 12,25; 10,5; 10,5 olur (Şekil 5.28, sağ). Genel kural şudur: süreçlerin çoğu işini tek dilimde bitirebiliyorsa ortalama dönüş iyileşir.

Gerçek sistemde her bağlam değiştirme s süre tutarsa, dilimini sonuna kadar kullanan süreçlerle CPU'nun boşa giden oranı

kayıp oranı = s / (q + s)

olur. Her turda q kadar yararlı iş ve s kadar geçiş vardır. q = 4 ms ve s = 1 ms ise kayıp 1 / 5 = %20'dir: CPU zamanının beşte biri yalnız süreç değiştirmeye gider. q = 100 ms'de kayıp ≈ %1'e iner, ama on süreçlik bir kuyrukta her süreç bir saniyeye yakın bekler ve sistem ağır tepki verir.

Bugün bağlam değiştirme birkaç mikrosaniye sürer, tipik dilimler 1–100 ms arasındadır. Bu yüzden doğrudan geçiş yükü küçüktür; asıl maliyet önbelleğin soğumasıdır. Linux'un EEVDF çizelgeleyicisinde temel dilim 0,75 ms × (1 + log₂ CPU sayısı) formülüyle hesaplanır. Formülde CPU sayısı en fazla 8 alınır; bu yüzden 8 ve daha çok çekirdekte dilim 3 ms'dir. Windows istemci sürümlerinde dilim yaklaşık iki saat tıkıdır. Silberschatz'ın pratik kuralı şudur: CPU patlamalarının yaklaşık %80'i q'dan kısa olmalıdır. Böylece süreçlerin çoğu dilimini doldurmadan G/Ç'ye gider; dilim yalnız uzun CPU işlerini sınırlar.

Bir örnek, iyi seçilmiş bir dilimin konvoy etkisini nasıl kırdığını gösterir. P1 24, P2 3, P3 3 ms kümesinde FCFS ortalama bekleme 17 ms idi. q = 4 ile P1 0–4, P2 4–7, P3 7–10 ve P1 10–30 çalışır. Beklemeler 6, 4 ve 7, ortalama 17 / 3 ≈ 5,67 ms'dir.

5.4Çok düzeyli kuyruklar

Gerçek bir sistemde süreçler türdeş değildir. Ses çalan bir süreç, kullanıcının yazdığı metin düzenleyici ve gece yedeği alan bir betik aynı kuyrukta adil biçimde yarışmamalıdır. Çok düzeyli kuyruklar süreçleri sınıflara ayırır ve her sınıfa kendi kuyruğunu ve kuralını verir.

5.4.1Çok düzeyli kuyruk (MLQ)

Tipik bir düzende ön plandaki etkileşimli süreçler kısa dilimli RR ile, arka plandaki toplu süreçler FCFS ile çizelgelenir. Kuyruklar arası seçim için iki yol vardır. Sabit öncelikte üst kuyruk boşalmadan alt kuyruk hiç çalışmaz. Toplu bir iş, etkileşimli kuyrukta süreç olduğu sürece bekler ve açlık çekebilir. Zaman paylaşımında her kuyruğa CPU'nun belirli bir oranı verilir; örneğin %80 ön plana, %20 arka plana.

MLQ'nun yükü düşüktür: süreç kuyruğa bir kez atanır ve bir daha taşınmaz. Ama esnek değildir. Bir süreç zamanla davranış değiştirse bile kuyruğu değişmez. Sınıfı yanlış tahmin edilen bir süreç ya hak etmediği önceliği alır ya da hak ettiğinden yoksun kalır. Bu sabit atamalı yapı MLQ'dur; süreçlerin davranışına göre kuyruk değiştirdiği yapıya geri beslemeli kuyruk denir.

5.4.2Geri beslemeli kuyruk (MLFQ) ve kuralları

MLFQ, bölümün en başında sorulan soruya pratik bir cevap verir: patlama sürelerini bilmeden kısa işleri nasıl öne alırız? Cevap, süreçleri gözlemektir. Her yeni iş önce kısa sayılır ve en üst kuyruğa konur. Gerçekten kısaysa orada hızla biter. Uzunsa dilimini doldurur ve bir alt kuyruğa iner. Böylece algoritma geçmişten öğrenir ve SJF'ye yaklaşır.

Kuralların her biri bir sorunu çözer. İlk ikisi temel çizelgeyi kurar. Üçüncüsü yeni işlere tanınan avantajdır: kısa bir komut hemen çalışıp biter. Dördüncüsü uzun işleri aşağı iter; hakkın düzeydeki toplam kullanım olarak sayılması kandırılmayı önler. Beşincisi açlığı önler ve davranışı değişen işe yeni bir şans verir.

MLFQ'yu tanımlayan parametreler şunlardır: kuyruk sayısı, her kuyruğun algoritması ve dilimi, işin ne zaman alt ya da üst kuyruğa geçeceği ve yeni işin hangi kuyruğa gireceği. Genellikle üst kuyruklarda dilim kısa, alt kuyruklarda uzundur: üstte kısa işler hızla döner, altta uzun işler daha seyrek ama daha uzun çalışır. Bu esneklik MLFQ'yu en genel ama aynı zamanda ayarlaması en zor algoritma yapar.

5.4.3MLFQ adım adım

Kısa B ve D üst kuyrukta hızla biter; tepki süreleri 6 ve 0'dır. Uzun A aşağı süzülür ve en son biter. Ortalama tepki 4 ms'dir. MLFQ hiçbir süreç süresini bilmeden kısa işleri öne almıştır: yaptığı tek şey her işin ne kadar CPU kullandığını saymaktır.

5.4.4MLFQ uygulamada

MLFQ'nun kurallarının neden böyle olduğu, olmadığı zaman ortaya çıkan sorunlardan anlaşılır.

Oyun oynama (gaming). Kuralın ilk hâli “dilimini dolduran iş aşağı iner, dilimden önce CPU'yu bırakan aynı düzeyde kalır” olsaydı kötü niyetli bir program bundan yararlanabilirdi. Program dilim bitmeden hemen önce kısa bir G/Ç yapar, örneğin 10 ms'lik dilimin 9,9 ms'sini kullanır. Hiç alt kuyruğa inmez ve CPU'nun büyük kısmını tekeline alır. Çözüm hakkı düzeydeki toplam kullanım olarak saymaktır (kural 4). İş CPU'yu kaç parçada kullanırsa kullansın, toplam 10 ms dolunca aşağı iner (Şekil 5.32).

Açlık ve davranış değişimi. Çok sayıda etkileşimli iş varsa üst kuyruklar hiç boşalmaz ve alt kuyruktaki uzun işler aç kalır. Ayrıca uzun bir hesap işi sonradan etkileşimli hâle gelirse alt kuyrukta kaldığı için bu fark edilmez. Periyodik öncelik yükseltme (kural 5) iki sorunu birlikte çözer. S'nin seçimi zordur. Çok büyük seçilirse uzun işler yine aç kalır; çok küçük seçilirse etkileşimli işler CPU'yu yeterince alamaz. OSTEP bu tür değerleri “vudu sabitleri” diye anar.

Tarihçe. MLFQ fikrini ilk kez Corbató ve ekibi 1962'de MIT'deki CTSS sisteminde uyguladı. CTSS'te öncelik sınıfları 1, 2, 4 ve 8 dilim çalışırdı; dilimlerini bitiren iş bir alt sınıfa inerdi. Terminalde Enter tuşuna basılınca süreç en üst sınıfa taşınıyordu, çünkü sistem onun etkileşimli hâle geldiğini varsayıyordu. Kullanıcılar bunu kısa sürede fark etti ve uzun işlerini hızlandırmak için arada bir Enter'a bastı. Oyun oynama sorununun ilk örneklerinden biri budur.

Bugün. MLFQ fikri birçok gerçek sistemde yaşar. Solaris'in zaman paylaşımlı (TS) sınıfı her öncelik düzeyinin dilimini ve aşağı ya da yukarı geçiş kuralını bir tabloyla tanımlar. FreeBSD'nin ULE çizelgeleyicisi, Windows'un dinamik öncelikleri ve macOS da aynı fikri kullanır. Linux ise 2.6.23 sürümünden beri bu tür öncelik sezgileri yerine adil paylaşıma dayanır; önce CFS, sonra EEVDF ile.

5.5Orantılı pay

Şimdiye kadarki algoritmalar dönüş ya da tepki süresini iyileştirmeye çalıştı. Orantılı pay (proportional share) çizelgeleyicileri başka bir hedef koyar: her süreç ya da kullanıcı CPU'nun önceden belirlenmiş bir payını almalıdır. Bulut sunucusunda müşteri parasını ödediği payı, paylaşımlı bir makinede her kullanıcı adil payını ister.

5.5.1Garantili ve adil paylaşım

Garantili çizelgemede oranı 0,5 olan süreç payının yalnız yarısını almıştır ve öne geçer. Oranı 2,0 olan süreç payının iki katını almıştır ve oranı düşenlere yol verir. Hesap için çizelgeleyicinin her sürecin ne zamandan beri var olduğunu ve o zamandan beri ne kadar CPU kullandığını tutması yeterlidir. Tanenbaum'daki anlamıyla garantili çizelgeleme bu pay garantisidir; önceden belirlenmiş bir zaman programına göre çalışmak değildir.

Süreç başına adalet, çok süreç açan kullanıcıyı ödüllendirir. Kullanıcı 1 dört süreç (A, B, C, D), kullanıcı 2 tek süreç (E) çalıştırsın. Süreç başına RR'de beş süreç eşit pay alır ve kullanıcı 1 CPU'nun %80'ini alır. Adil paylaşımda pay önce kullanıcılara bölünür: her kullanıcıya %50. Kullanıcı 1'in payı kendi dört süreci arasında, kullanıcı 2'ninki E'ye gider. Sıra A, E, B, E, C, E, D, E biçimini alır. Paylar politikayla da belirlenebilir; kullanıcı 1'e 2/3 pay verilirse her üç dilimin ikisi onun süreçlerine gider (Şekil 5.33).

Bugün adil paylaşım Linux'ta denetim grupları (cgroups) ile yapılır. cgroup v2'de her grubun cpu.weight değeri vardır ve CPU grup ağırlıklarına göre bölünür. systemd her kullanıcıyı user-UID.slice adlı bir gruba koyar; bu yüzden bir kullanıcının yüz süreç açması öteki kullanıcının payını azaltmaz. Kubernetes de kapsayıcılara verilen CPU isteklerini bu ağırlıklara çevirir.

5.5.2Piyango çizelgeleme

Waldspurger ve Weihl'in 1994'te önerdiği yöntemin en çekici yanı basitliğidir. Gereken tek şey bir rastgele sayı üreteci ve süreç listesi üzerinde birikimli bir toplamdır. Önceliği ifade etmek de kolaydır: daha önemli süreç daha çok bilet alır. Yeni gelen süreç bilet alır almaz kazanabilir; algoritma bu anlamda hemen tepki verir.

Biletler, adil paylaşımın zor işlerini de çözer. Bilet devrinde bir istemci sunucudan yanıt beklerken kendi biletlerini geçici olarak sunucuya verir; böylece sunucu, en çok bekleyen istemcinin işine hız verir. Bilet para birimi, bir kullanıcının kendi biletlerini kendi süreçleri arasında istediği birimle bölmesine izin verir; sistem bunu küresel değere çevirir. Birbirine güvenen süreçlerin olduğu bir ortamda enflasyon da kullanılabilir: daha çok CPU'ya ihtiyacı olan süreç kendi bilet sayısını geçici olarak artırır.

Piyangonun zayıflığı olasılıksal olmasıdır. Kısa vadede adaletsiz olabilir: eşit biletli iki iş 10 dilimi 7–3 bölüşebilir. Pay ancak çekiliş sayısı arttıkça bilet oranına yaklaşır. Aynı oranı deterministik olarak sağlayan yöntem stride çizelgemedir.

5.5.3Kod izleme: çekiliş döngüsü

OSTEP piyangonun karar döngüsünü şöyle verir. Süreçler bilet sayılarıyla birlikte bir bağlı listededir; getrandom(0, totaltickets) 0 ile toplam bilet arasında bir sayı döndürür.

/* her dilimde bir çekiliş */
int counter = 0;
int winner = getrandom(0, totaltickets);
node_t *current = head;
while (current) {
  counter = counter + current->tickets;
  if (counter > winner)
    break;          /* kazanan bulundu */
  current = current->next;
}
/* current: CPU’yu alacak süreç */
calistir(current);

Döngü listeyi baştan tarar ve counter değişkeninde o ana kadarki biletlerin toplamını tutar. Her düğümde düğümün biletleri toplama eklenir. Toplam çekilen sayıyı aştığı anda çekilen bilet bu düğümün aralığındadır ve döngü kırılır. Aşmıyorsa sonraki düğüme geçilir. İzleme için çekilen sayılar sırayla 47, 35 ve 12 olarak sabitlenmiştir; bilet listesi A 30, B 10, C 60'tır (toplam 100). A 0–29, B 30–39, C 40–99 numaralı biletleri tutar (Tablo 5.16).

Her yeni çekilişte sayaç sıfırdan başlar ve liste baştan taranır. Üç dilimde A, B ve C birer kez çalıştı. Oysa beklenen paylar %30, %10 ve %60'tır; kısa vadede pay biletlerle orantılı değildir, ancak uzun vadede 30 : 10 : 60'a yaklaşır.

Bir çekilişin maliyeti en kötü durumda O(n)'dir, çünkü kazanan listenin sonunda olabilir. Liste bilet sayısına göre azalan sıralanırsa en çok biletli süreçler başta olur ve tarama ortalamada kısalır. Çok süreçli sistemlerde birikimli toplamlar bir ağaçta tutularak seçim O(log n)'ye indirilebilir.

5.5.4Stride çizelgeleme

Çok bileti olan sürecin adımı küçüktür; pass değeri yavaş artar ve sık seçilir. Az bileti olanın adımı büyüktür; bir kez çalışınca uzun süre geride kalır. Waldspurger 1995'te bu yöntemi piyangonun deterministik eşi olarak önerdi (Tablo 5.17; Şekil 5.35).

8 dilimde A 2, B 1, C 5 kez çalıştı. Oran tam olarak 2 : 1 : 5'tir; bu da bilet oranı 100 : 50 : 250'nin kendisidir. Sekizinci dilimin sonunda üç pass değeri de 200'dür: bir tam döngü tamamlanmıştır ve aynı desen yeniden başlar. Piyangoda aynı oran ancak uzun vadede ve yaklaşık olarak tutar.

Stride'ın bir dezavantajı küresel durumdur. Sisteme yeni bir süreç girdiğinde pass değeri ne olmalıdır? Sıfır verilirse öteki süreçlerin pass değerleri yüzlerce olduğu için yeni süreç uzun süre CPU'yu tekeline alır. Bu yüzden yeni süreç o andaki en küçük pass değeriyle başlatılır. Piyangoda böyle bir sorun yoktur; yeni süreç yalnız biletlerini getirir ve hemen adil bir şans elde eder. Linux CFS'in sanal çalışma süresi fikri stride'a çok yakındır: vruntime bir pass sayacı, ağırlığın tersi de adımdır.

5.6Çok işlemcili çizelgeleme

Bugün bir telefonda bile sekiz çekirdek bulunur. Birden çok CPU varken çizelgeleyici iki soruya cevap vermek zorundadır: hangi iş çalışsın ve hangi CPU'da çalışsın? İkinci soru, önbellekler ve bellek düzeni yüzünden göründüğünden zordur.

5.6.1İş parçacığı çizelgeleme: PCS ve SCS

Çekirdek süreçleri değil, çekirdek iş parçacıklarını çizelgeler. Kullanıcı iş parçacıklarını ise bir kütüphane ya da dilin çalışma zamanı yönetir. Bu iki katmanlı yapı iki ayrı yarışma kapsamı doğurur.

Pthreads kapsamı bir öznitelikle sorgulamaya ve ayarlamaya izin verir:

pthread_attr_t attr;
int scope;
pthread_attr_init(&attr);
pthread_attr_getscope(&attr, &scope);
if (scope == PTHREAD_SCOPE_PROCESS)
  printf("PCS\n");
/* Linux ve macOS yalnızca SYSTEM */
pthread_attr_setscope(&attr,
                      PTHREAD_SCOPE_SYSTEM);
pthread_create(&tid, &attr, runner, NULL);

Program bir öznitelik nesnesi oluşturur ve varsayılan kapsamı okur. Kapsam PTHREAD_SCOPE_PROCESS ise PCS basar. Ardından kapsamı sisteme ayarlar ve iş parçacığını bu öznitelikle oluşturur. Linux, Windows ve macOS 1:1 modelini kullandığı için yalnız SCS'yi destekler. Linux'ta varsayılan kapsam zaten PTHREAD_SCOPE_SYSTEM'dir ve program bir şey basmaz; PCS istemek ENOTSUP hatası verir.

PCS fikri işletim sistemlerinde terk edilse de dil çalışma zamanlarında geri döndü. Java 21'in sanal iş parçacıkları ve Go'nun goroutine'leri, çalışma zamanının kendi çizelgeleyicisiyle az sayıda taşıyıcı iş parçacığına eşlenir. Çekirdek yalnız taşıyıcıları görür; hangi sanal iş parçacığının hangi taşıyıcıda çalışacağına çalışma zamanı karar verir.

5.6.2Ortak kuyruk ve çekirdek başına kuyruk

Çok işlemcili çizelgelemenin iki temel düzeni vardır. Asimetrik çok işlemlemede (AMP) tek bir ana işlemci bütün çizelgeleme kararlarını ve G/Ç işlemlerini yapar; ötekiler yalnız kullanıcı kodu çalıştırır. Basittir, çünkü çekirdek veri yapılarına tek işlemci erişir, ama ana işlemci darboğaz olur. Simetrik çok işlemlemede (SMP) her işlemci kendi çizelgeleme kararını verir. Bütün modern sistemler SMP'dir (Şekil 5.37).

SMP'de hazır süreçleri tutmanın iki yolu vardır. Ortak kuyrukta bütün çekirdekler aynı kuyruktan iş alır. Yük kendiliğinden dengelenir, çünkü boşalan her çekirdek kuyruktaki sıradaki işi alır. Ama kuyruğa her erişim bir kilit ister ve çekirdek sayısı arttıkça kilit çekişmesi büyür. Ayrıca bir iş her seferinde farklı bir çekirdekte çalışabilir; önbelleğindeki veri işe yaramaz.

Çekirdek başına kuyrukta her çekirdeğin kendi hazır kuyruğu vardır. Buna iki düzeyli çizelgeleme de denir: iş önce bir çekirdeğe atanır, sonra o çekirdeğin kuyruğundan çalışır. Kilit neredeyse gerekmez ve iş aynı çekirdekte kaldığı için önbelleği sıcak kalır. Linux, Windows ve FreeBSD bu düzeni kullanır. Bedeli, kuyrukların zamanla dengesizleşebilmesidir: bir çekirdekte beş iş beklerken öteki boşta kalabilir. Bu yüzden yük dengeleme gerekir.

5.6.3Çok çekirdek ve donanım iş parçacıkları

Modern işlemcilerde bir çekirdek zamanının büyük kısmını bellek beklerken geçirebilir. Önbellek ıskası olduğunda veri ana bellekten gelene kadar yüzlerce çevrim geçer. Silberschatz bu bellek beklemesinin (memory stall) çekirdek zamanının %50'sine varabildiğini belirtir (Şekil 5.38).

Eş zamanlı çoklu iş parçacığı (SMT; Intel'de Hyper-Threading) bu boşluğu doldurur. Bir çekirdekte iki donanım iş parçacığı bulunur; her birinin kendi yazmaç kümesi vardır, yürütme birimleri ise ortaktır. Biri bellek beklerken öteki komut yürütür. İşletim sistemi her donanım iş parçacığını ayrı bir mantıksal CPU olarak görür; dört çekirdekli ve SMT'li bir işlemci sekiz mantıksal CPU gösterir.

Böylece iki düzeyli bir çizelgeleme ortaya çıkar. İşletim sistemi hangi yazılım iş parçacığının hangi mantıksal CPU'da çalışacağını seçer. Çekirdeğin donanımı ise o an hangi donanım iş parçacığının yürüyeceğini seçer. İşletim sistemi bu ayrımı bilmelidir. Kardeş mantıksal CPU'lar yürütme birimlerini paylaşır. Bu yüzden boş bir fiziksel çekirdek varken iki yoğun işi aynı çekirdeğin iki mantıksal CPU'suna koymak kötü bir karardır; ikisi de yavaşlar.

5.6.4Yük dengeleme

Çekirdek başına kuyrukta dengesizlik kendiliğinden düzelmez; birinin müdahale etmesi gerekir. İki yöntem birbirini tamamlar ve Linux ikisini de kullanır. Periyodik dengeleyici birkaç milisaniyede bir çalışıp büyük farkları giderir. Bir çekirdeğin kuyruğu boşaldığında ise beklemeden çekme göçü yapılır: boştaki çekirdek en yüklü kuyruktan bir iş çalar (Şekil 5.40).

Denge sağlansa da bedeli vardır. Taşınan işin önbelleği yeni çekirdekte soğuktur ve ilk erişimleri ıskayla başlar. Linux bu yüzden dengelemeyi katmanlı yapar. Bu katmanlara çizelgeleme alanları (scheduling domains) denir. Önce aynı fiziksel çekirdeğin SMT kardeşleri arasında, sonra ortak son düzey önbelleği paylaşan çekirdekler arasında dengeler. NUMA düğümleri arasındaki dengeleme daha seyrek ve daha büyük bir dengesizlik eşiğiyle yapılır, çünkü orada göçün bedeli en büyüktür. İşlerin çekirdeklere dağıtımı ve göçün etkisi çok çekirdekli çizelgeleme simülatöründe adım adım izlenebilir.

5.6.5Kod izleme: dengele()

Çekme dengelemesinin özü kısa bir fonksiyondur. q[c].n, c numaralı çekirdeğin kuyruk uzunluğudur; gocur(kaynak, hedef) kaynak kuyruğun sonundaki işi hedef kuyruğa taşır.

void dengele(int bu) {   /* boştaki CPU */
  int en = bu;
  for (int c = 0; c < NCPU; c++)
    if (q[c].n > q[en].n) /* daha yüklü */
      en = c;
  int t = (q[en].n - q[bu].n) / 2;
  for (int k = 0; k < t; k++)
    gocur(&q[en], &q[bu]); /* sondan */
}

Fonksiyon, kuyruğu boşalan çekirdeğin numarasıyla (bu) çağrılır. İlk döngü en yüklü kuyruğu bulur: en başlangıçta bu'dur ve daha uzun bir kuyruk görüldükçe güncellenir. Ardından taşınacak iş sayısı farkın yarısı olarak hesaplanır. Farkın tamamı taşınsaydı dengesizlik yalnız yön değiştirirdi; yarısı taşınınca iki kuyruk birbirine yaklaşır. Son döngü o kadar işi kaynağın sonundan alır (Tablo 5.18; Şekil 5.41).

İşlerin kuyruğun sonundan alınmasının bir nedeni vardır. Sondakiler en uzun süre beklemiş olanlar değil, en son gelenlerdir; önbelleğe en az veri yüklemiş, yani önbellekleri en soğuk olan işlerdir. Bunları taşımak afinite kaybını en aza indirir. Fonksiyonun zamanı O(NCPU + t)'dir. Gerçek çekirdeklerde yalnız kuyruk uzunluğuna değil, işlerin ağırlıklarına ve son zamanlardaki CPU kullanımlarına da bakılır.

5.6.6Afinite, NUMA ve heterojen çekirdekler

Linux katı afiniteyi sched_setaffinity() sistem çağrısıyla sunar; kabukta taskset -c 0-3 ./prog komutu programı 0–3 numaralı CPU'larla sınırlar. Veritabanları ve gerçek zamanlı uygulamalar bunu sıkça kullanır.

Afinite sorusu NUMA (tekdüze olmayan bellek erişimi) mimarisinde daha da büyür. Çok soketli sunucularda her işlemcinin kendine yakın bir belleği vardır. Yerel belleğe erişim hızlı, öteki düğümün belleğine ara bağlantı üzerinden erişim yavaştır. İyi bir çizelgeleyici iş parçacığını belleğinin bulunduğu düğümde çalıştırır. Linux'un otomatik NUMA dengelemesi sayfa erişimlerini örnekler; görevleri verilerine ya da sayfaları görevlerine yaklaştırır (Şekil 5.42).

Yük dengeleme ile afinite birbiriyle çelişir. Göç dengeyi sağlar ama önbelleği ve bellek yerelliğini bozar. Afinite yerelliği korur ama çekirdeklerin bir kısmı boşta kalırken ötekiler aşırı yüklenebilir. Gerçek çizelgeleyiciler ikisi arasında eşiklerle denge kurar: dengesizlik küçükse işler yerinde kalır, büyükse taşınır.

Son yıllarda çekirdekler de türdeş olmaktan çıktı. Heterojen çok işlemcili yongalarda başarımı yüksek ama çok enerji harcayan çekirdeklerle yavaş ama verimli çekirdekler bir aradadır. ARM'ın big.LITTLE ve DynamIQ düzenleri, Intel'in 12. nesilden beri P ve E çekirdekleri, Apple M serisi buna örnektir. Intel'in Thread Director donanımı işletim sistemine hangi iş parçacığının hangi tür çekirdeğe uygun olduğu konusunda ipuçları verir. Linux'un enerji farkında çizelgelemesi (EAS, Energy Aware Scheduling) her işi, başarım hedefini karşılayan ve en az enerji harcayan çekirdeğe koyar. Arka plan işleri verimli çekirdeklere, kullanıcının beklediği işler güçlü çekirdeklere gider.

5.7Gerçek zamanlı çizelgeleme

Genel amaçlı bir sistemde işin geç bitmesi can sıkar ama yanlış değildir. Gerçek zamanlı bir sistemde ise doğru sonuç geç gelirse yanlış sayılır. Bir hava yastığı denetleyicisinin çarpışmayı 40 ms sonra fark etmesi hiç fark etmemesiyle aynıdır. Bu sistemlerde çizelgelemenin hedefi ortalamayı iyileştirmek değil, her işin son tarihini garanti etmektir.

5.7.1Katı ve yumuşak gerçek zaman, gecikme

ABS fren sistemi, hava yastığı, endüstriyel robot denetimi ve uçuş denetimi katı gerçek zamanlıdır. Video akışı, internet üzerinden ses (VoIP), oyunlar ve ses çalma yumuşak gerçek zamanlıdır: bir çerçeve geç gelirse görüntü bir an takılır, ama sistem çalışmaya devam eder.

Gerçek zamanlı sistemin tepkisini ölçen büyüklük olay gecikmesidir (event latency): bir olayın gerçekleşmesinden ona hizmet eden sürecin çalışmaya başlamasına kadar geçen süre. Bu süre birkaç bileşenin toplamıdır (Şekil 5.43). Kesme gecikmesi, kesmenin gelmesinden kesme hizmet yordamının (ISR) başlamasına kadar geçen süredir. Ardından ISR çalışır. Son olarak dağıtım gecikmesi gelir: çizelgeleyicinin çalışan süreci durdurup gerçek zamanlı süreci başlatması.

Dağıtım gecikmesinin çakışma evresinde iki iş yapılır. Çekirdekte çalışan herhangi bir iş kesilir ve gerçek zamanlı sürecin ihtiyaç duyduğu, düşük öncelikli bir sürecin tuttuğu kaynak bırakılır. Bu evrenin kısa olması için çekirdeğin kesmeli olması gerekir; çekirdek kodu kesilemeseydi uzun bir sistem çağrısının bitmesi beklenirdi. Bu yüzden gerçek zamanlı sistemler kesmeli, öncelik tabanlı bir çekirdek ister. Yalnız bu da katı garanti için yetmez. Sistem yeni bir görev kabul etmeden önce, görev eklendiğinde bütün son tarihlerin hâlâ karşılanıp karşılanamayacağını sınamalıdır. Bu sınamaya kabul denetimi (admission control) denir.

Gerçek zamanlı algoritmalar statik ya da dinamik olabilir. Statik algoritmalarda öncelikler sistem çalışmadan önce bir kez hesaplanır; hız monoton çizelgeleme böyledir. Dinamik algoritmalarda kararlar çalışma anında verilir; en erken son tarih önce böyledir.

5.7.2Periyodik görevler ve hız monoton çizelgeleme

Gerçek zamanlı görevlerin çoğu periyodiktir. Bir sensör her 10 ms'de bir okunur, bir kontrol döngüsü her 50 ms'de bir yeni çıkış hesaplar.

RM'nin arkasındaki sezgi basittir: daha sık çalışması gereken görev daha acildir. RM, statik öncelikli algoritmalar arasında optimaldir. Bir görev kümesi herhangi bir statik öncelik atamasıyla çizelgelenebiliyorsa RM ile de çizelgelenebilir. RM'nin çizelgeleyemediği kümeyi başka hiçbir statik öncelik ataması çizelgeleyemez.

Sınır n arttıkça azalır. Tablo 5.19 birkaç değeri verir; n sonsuza giderken sınır ln 2 ≈ 0,693'e yaklaşır. Yani görev sayısı ne olursa olsun, toplam kullanım %69,3'ü aşmıyorsa RM'nin başarısı garantidir.

Teoremin yönü önemlidir: koşul yeterlidir, gerekli değildir. Kullanım sınırın altındaysa RM kesin başarır. Sınırın üstündeyse RM yine başarabilir ya da başaramayabilir; testten sonuç çıkmaz. Karar vermek için çizelgeyi bir hiperperiyot boyunca (periyotların en küçük ortak katı kadar) çizmek gerekir. Toplam kullanım 1'i aşıyorsa ise hiçbir algoritma kümeyi çizelgeleyemez: CPU'dan saniyede bir saniyeden fazla iş isteniyordur.

5.7.3RM ile EDF aynı kümede

EDF'nin çizelgelenebilirlik koşulu çok daha cömerttir: kesmeli, bağımsız ve son tarihi periyot sonu olan görevler için ΣU ≤ 1 yeterli ve gereklidir. EDF CPU'yu teorik olarak %100'e kadar kullanabilir. İki algoritmanın farkını, RM'nin testi geçemediği bir kümede görelim.

EDF'nin üstünlüğünün bedeli vardır. Öncelikler dinamik olduğu için her karar anında son tarihleri karşılaştırmak gerekir. Daha önemlisi aşırı yükte davranışıdır. Toplam kullanım geçici olarak 1'i aşarsa RM'de yalnız düşük öncelikli görevler kaçırır ve hangisinin kaçıracağı öngörülebilir. EDF'de ise kaçırmalar bir zincir gibi yayılabilir ve hangi görevin etkileneceğini önceden söylemek zordur.

EDF'ye yakın bir fikir, orantılı pay gerçek zamanlı çizelgemedir. Toplam T pay uygulamalar arasında dağıtılır; N pay alan uygulama CPU'nun N/T'sini alır. Kabul denetimi toplamı aşan isteği reddeder. Linux'un SCHED_DEADLINE politikası (3.14 sürümünden beri) EDF'yi sabit bant genişliği sunucusu (CBS) korumasıyla birleştirir. Her görev bir çalışma süresi, son tarih ve periyot bildirir. Görev bildirdiğinden fazla çalışmaya kalkarsa bir sonraki periyoda kadar durdurulur; böylece kötü davranan bir görev ötekilerin garantisini bozamaz. Periyodik görev kümeleri için RM ve EDF çizelgeleri, kullanım oranı ve kaçırılan son tarihler gerçek zamanlı çizelgeleme simülatöründe denenebilir.

5.7.4Kod izleme: Liu–Layland testi

RM'nin yeterlilik testi kısa bir fonksiyondur. Fonksiyon üç değer döndürür: 1 (RM kesin yeter), 0 (test karar veremez) ve −1 (kullanım 1'i aştığı için hiçbir algoritma çizelgeleyemez).

int rm_test(Gorev g[], int n) {
  double U = 0;
  for (int i = 0; i < n; i++)
    U += (double) g[i].t / g[i].p;
  double sinir = n * (pow(2, 1.0/n) - 1);
  if (U <= sinir) return 1; /* yeter */
  if (U <= 1.0) return 0;   /* belirsiz */
  return -1;            /* imkânsız */
}

Döngü her görevin kullanımını toplar; (double) dönüşümü tam sayı bölmesini engeller. Ardından sınır hesaplanır. pow(2, 1.0/n) ifadesindeki 1.0 önemlidir: 1/n yazılsaydı n ≥ 2 için tam sayı bölmesi 0 verir, sınır da 0 çıkardı. Son iki karşılaştırma üç sonucu ayırır (Tablo 5.20).

Birinci kümede 0,75 ≤ 0,7798 olduğu için fonksiyon 1 döndürür ve RM bütün son tarihleri karşılar. İkinci küme, Örnek 5.17'deki kümedir. Kullanım sınırı aşar ama 1'in altındadır; fonksiyon 0 döndürür. Bu kümede RM gerçekten son tarih kaçırır, EDF ise karşılar. 0 sonucu “RM başarısız olur” demek değildir: P1 (p = 40, t = 10) ve P2 (p = 60, t = 30) kümesinin kullanımı 0,25 + 0,5 = 0,75 ≤ 0,828'dir ve test 1 verir. Sınırı biraz aşan başka bir küme de RM ile çizelgelenebilir olabilir; bunu yalnız çizelgenin kendisi gösterir. Fonksiyonun zamanı O(n)'dir.

5.7.5Kod izleme: EDF çizelgeleyici

EDF'nin karar kuralı her zaman adımında uygulanabilir. Aşağıdaki program üç periyodik görevi 12 ms boyunca, milisaniyede bir karar vererek çizelgeler.

/* A(P=3,C=1) B(P=4,C=1) C(P=6,C=2) */
for (int t = 0; t < 12; t++) {
    for (int i = 0; i < n; i++)
        if (t % P[i] == 0) {      /* yeni iş */
            kalan[i] = C[i];
            teslim[i] = t + P[i];
        }
    int s = -1;
    for (int i = 0; i < n; i++)
        if (kalan[i] > 0 &&
            (s < 0 || teslim[i] < teslim[s]))
            s = i;
    if (s >= 0) kalan[s]--;     /* 1 ms */
}

P[i] periyot, C[i] çalışma süresi, kalan[i] geçerli işin kalan süresi, teslim[i] de geçerli işin son tarihidir. Her milisaniyenin başında periyodu yeni başlayan görevlerin işleri yenilenir: kalan süre C[i]'ye, son tarih t + P[i]'ye ayarlanır. İkinci döngü işi kalmış görevler arasından son tarihi en küçük olanı seçer. Karşılaştırma katı küçüktür (<) olduğu için eşitlikte dizideki ilk görev kazanır. Seçilen görevin kalan süresi 1 azalır. Hiç iş yoksa s −1 kalır ve CPU o milisaniye boştur.

Görevler A (P = 3, C = 1), B (P = 4, C = 1) ve C (P = 6, C = 2)'dir. Toplam kullanım 1/3 + 1/4 + 2/6 = 11/12 ≈ 0,917 ≤ 1'dir. Periyotların en küçük ortak katı 12 olduğu için 12 ms'lik bir pencere bütün deseni gösterir (Tablo 5.21; Şekil 5.47).

12 ms'de 11 ms iş yapılır ve 1 ms boşluk kalır; bu, 1 − 11/12 kadardır. Hiçbir iş son tarihini kaçırmaz. t = 4 anı EDF'yi RM'den ayırır: B'nin periyodu C'ninkinden kısadır ve RM olsaydı B çalışırdı. EDF ise son tarihlere bakar: C'nin işi 6'da, B'ninki 8'de bitmelidir; C seçilir. Bu küme RM ile de kaçırmasız çizelgelenir, ama kullanımı (0,917) üç görevli Liu–Layland sınırını (0,780) aştığı için RM'nin başarısını yalnız çizelge gösterebilir.

Programın zamanı adım başına O(n)'dir. Gerçek EDF uygulamaları her milisaniye karar vermez; yalnız iş geldiğinde ya da bittiğinde karar verir ve hazır işleri son tarihe göre sıralı bir öncelik kuyruğunda tutar. Böylece her karar O(log n) sürer.

5.7.6POSIX gerçek zamanlı çizelgeleme

POSIX'in gerçek zamanlı uzantısı (POSIX.1b) iş parçacıklarına çizelgeleme politikası atamayı sağlar. Tablo 5.22 Linux'ta kullanılabilen politikaları özetler.

pthread_attr_t attr;
struct sched_param sp;
int policy;
pthread_attr_init(&attr);
pthread_attr_getschedpolicy(&attr, &policy);
/* kalıtım kapatılmazsa politika yok sayılır */
pthread_attr_setinheritsched(&attr,
                      PTHREAD_EXPLICIT_SCHED);
pthread_attr_setschedpolicy(&attr, SCHED_FIFO);
sp.sched_priority = 50;          /* 1..99 */
pthread_attr_setschedparam(&attr, &sp);
pthread_create(&tid, &attr, runner, NULL);

Program önce öznitelik nesnesini hazırlar ve varsayılan politikayı okur. Ardından önemli bir satır gelir: pthread_attr_setinheritsched ile kalıtım kapatılır. Varsayılan durumda yeni iş parçacığı politikasını oluşturan iş parçacığından devralır; kalıtım kapatılmazsa öznitelikte ayarlanan politika sessizce yok sayılır. Sonra politika SCHED_FIFO, öncelik 50 yapılır ve iş parçacığı oluşturulur.

Gerçek zamanlı politikalar ayrıcalık ister: Linux'ta CAP_SYS_NICE yetkisi gerekir; yetkisiz bir süreçte pthread_create EPERM döndürür. Kabukta aynı iş chrt -f 50 ./prog komutuyla yapılır. Gerçek zamanlı bir iş parçacığı sonsuz döngüye girerse sistemi kilitleyebilir. Linux buna karşı varsayılan olarak gerçek zamanlı işlere her saniyenin en fazla 0,95 saniyesini verir; kalan 0,05 saniye normal süreçlere kalır. Bu sınır sched_rt_runtime_us ayarıyla değiştirilebilir. İşlev adlarında bir ayrıntı da sık yanlış yazılır: adlar pthread_attr_getschedpolicy ve pthread_attr_setschedpolicy'dir; “sched” ile “policy” arasında alt çizgi yoktur.

5.8İşletim sistemi örnekleri

Gerçek çizelgeleyiciler bölümdeki fikirlerin birleşimidir. Linux gerçek zamanlı işler için öncelik kuyruklarını, normal işler için orantılı payı kullanır. Windows ise MLFQ'ya benzeyen dinamik önceliklerle çalışır.

5.8.1Linux çizelgeleme sınıfları

Linux çizelgeleyicisi modülerdir: her görev bir çizelgeleme sınıfına aittir ve sınıflar sabit bir öncelik sırasıyla sorulur. Çizelgeleyici önce en üst sınıfa “çalıştıracak görevin var mı?” diye sorar; yoksa bir alttakine geçer. Üst sınıfta hazır görev varken alttakiler hiç çalışmaz (Tablo 5.23).

Bu sıra, aynı CPU'da hazır üç görevden hangisinin önce çalışacağını doğrudan belirler. SCHED_DEADLINE görevi, öncelik 50'li SCHED_FIFO görevinden önce gelir. O da nice değeri −20 olan normal görevden önce gelir. nice değeri yalnız adil sınıfın içindeki payı etkiler; bir normal görevi gerçek zamanlı görevin önüne geçiremez (Şekil 5.48).

Çekirdek içinde tek bir öncelik ölçeği kullanılır ve küçük sayı yüksek önceliktir. 0–99 aralığı gerçek zamanlı görevlerindir; kullanıcının verdiği rt_priority (1–99) çekirdek önceliğine 99 − rt_priority olarak çevrilir. 100–139 aralığı normal görevlerindir: nice −20 → 100, nice 0 → 120, nice 19 → 139. SCHED_RR politikasının varsayılan dilimi 100 ms'dir.

5.8.2CFS: sanal çalışma süresi

Linux 2.6.23'ten 6.5'e kadar normal görevleri Tamamen Adil Çizelgeleyici (Completely Fair Scheduler, CFS) çizelgeledi. CFS'in amacı ideal bir çok görevli işlemciyi taklit etmektir. İdeal işlemcide n görev varsa her biri aynı anda CPU'nun 1/n'i hızında çalışırdı. Gerçek CPU bir anda tek görev çalıştırabildiği için CFS her görevin bu idealden ne kadar geride kaldığını izler ve en çok geride kalanı çalıştırır.

Ağırlık nice değerinden gelir. nice 0'ın ağırlığı 1024'tür; her nice adımı ağırlığı yaklaşık 1,25 kat değiştirir. nice 5'in ağırlığı 335, nice −5'inki 3121'dir. Yaklaşık 1,25 katlık fark, iki CPU'ya bağlı görev arasında aşağı yukarı %10'luk CPU payı farkına karşılık gelir. nice 0 bir görev için vruntime gerçek süreyle aynı hızda artar. Ağırlığı küçük (nice'ı büyük) görevin vruntime'ı daha hızlı artar; bu yüzden daha seyrek seçilir.

İki CPU'ya bağlı görev düşünelim: A nice 0 (ağırlık 1024), B nice 5 (ağırlık 335). Uzun vadede ikisinin vruntime'ı aynı hızda ilerlemelidir; bu da paylarının ağırlıklarıyla orantılı olmasını gerektirir. A 1024 / (1024 + 335) = 1024 / 1359 ≈ %75, B ≈ %25 alır; oran yaklaşık 3 : 1'dir. B 10 ms çalışınca vruntime'ı 10 × 1024 / 335 ≈ 30,6 ms artar.

G/Ç'ye bağlı görevler bu düzende kendiliğinden ödüllenir. Uyuyan görev CPU kullanmadığı için vruntime'ı artmaz; uyandığında CPU'ya bağlı görevlerin gerisinde kalmıştır ve hemen öne geçer. Uzun süre uyuyan bir görevin geri döndüğünde CPU'yu uzun süre tekeline alması da istenmez. CFS bu yüzden uyanan görevin vruntime'ını en küçük vruntime'ın biraz gerisine çeker; geride kalmış göreve verilen avantaj sınırlıdır (Şekil 5.49).

Hazır görevler vruntime anahtarıyla bir kırmızı-siyah ağaçta tutulur. Ekleme ve silme O(log n) sürer. En soldaki düğüm, yani vruntime'ı en küçük görev, ayrıca bir işaretçide önbelleğe alınır; bu yüzden seçim O(1)'dir.

5.8.3Kod izleme: vruntime

Aşağıdaki kod CFS'in seçim kuralını basitleştirilmiş bir tık işleyicisi olarak gösterir. Her tıkta en soldaki görev 3 ms (3000 µs) çalıştırılır, vruntime'ı güncellenir ve ağaca yeniden eklenir.

#define DELTA 3000  /* 3 ms, µs olarak */
/* nice 0 → 1024, nice 5 → 335 */
void tik(void) {
  Gorev *g = en_soldaki(); /* en solda */
  calistir(g, DELTA);
  g->vruntime += DELTA * 1024 / g->agirlik;
  agaca_ekle(g);      /* yeniden sırala */
}

en_soldaki() vruntime'ı en küçük görevi döndürür; eşitlikte ağaca önce eklenmiş görev soldadır. calistir görevi 3 ms çalıştırır. Güncelleme satırı tam sayı aritmetiğiyle yapılır: A için 3000 × 1024 / 1024 = 3000, B için 3 072 000 / 335 = 9170 (kalan atılır). Son satır görevi yeni vruntime'ına göre ağaçtaki yerine koyar. Başlangıçta iki görevin vruntime'ı da 0'dır (Tablo 5.24).

9 tıkta A 7, B 2 kez çalıştı. Kısa vadede oran 7 : 2'dir; uzun vadede 1024 : 335 ağırlık oranına, yani ≈ %75 – %25'e yaklaşır. Aynı kural 10 000 tık çalıştırıldığında A 7535, B 2465 tık alır. CFS'te sabit bir zaman dilimi yoktur; pay doğrudan ağırlıktan çıkar. Gerçek CFS süreyi nanosaniye ile ölçer ve sabit tık yerine bir “zamanlayıcı gecikmesi” penceresini görevler arasında ağırlıklarına göre böler; ama seçim kuralı aynıdır. Bu kural stride çizelgemenin pass sayacıyla aynı fikirdir: vruntime pass, 1024 / ağırlık adımdır.

5.8.4EEVDF

CFS adil payı iyi sağlıyordu, ama gecikmeye duyarlı görevler için birçok sezgisel ayara ihtiyaç duyuyordu. Linux 6.6 sürümünde normal görevlerin çizelgeleyicisi EEVDF ile değiştirildi. EEVDF (Earliest Eligible Virtual Deadline First), Stoica ve Abdel-Wahab'ın 1995'te önerdiği bir algoritmadır. CFS'teki sezgilerin yerine iki net ölçüt koyar: uygunluk ve sanal son tarih.

Uygunluk koşulu adaleti, son tarih ise gecikmeyi yönetir. Payından fazlasını almış görev (v > V) uygun değildir ve bekler; böylece kimse payını aşamaz. Uygun görevler arasında kısa dilim isteyen görevin son tarihi daha yakındır ve önce çalışır. Kısa dilim isteyen görev daha sık ama daha kısa çalışır; uzun vadede payı değişmez.

Örnekte kısa dilim isteyen B beş seçimin dördünü aldı, ama her seferinde yalnız 1 ms çalıştı. A ise bir kez, 3 ms çalıştı. Uygunluk koşulu B'nin öne kaçmasını sınırlar: B ortalamanın önüne geçtiğinde (üçüncü adım) uygunluğunu kaybetmiş ve A'ya yol vermiştir. Linux 6.12'den beri gecikmeye duyarlı bir görev sched_setattr() çağrısıyla kendisi için kısa dilim isteyebilir. Ağırlıklar nice ile CFS'tekiyle aynı biçimde hesaplanır.

5.8.5Windows öncelikleri

Windows kesmeli, öncelik tabanlı bir çizelgeleyici kullanır. Hazır iş parçacıklarından önceliği en yüksek olan çalışır. Bloke olana, dilimi bitene ya da daha yüksek öncelikli bir iş parçacığı hazır olana kadar CPU'da kalır. 32 öncelik düzeyi vardır ve büyük sayı yüksek önceliktir. 1–15 değişken sınıf, 16–31 gerçek zamanlı sınıftır. 0 düzeyi, boş bellek sayfalarını sıfırlayan sistem iş parçacığına (zero-page thread) ayrılmıştır. Her düzeyin kendi kuyruğu vardır; hiç hazır iş parçacığı yoksa boşta (idle) iş parçacığı çalışır.

Bir iş parçacığının sayısal önceliği iki bilgiden çıkar: sürecinin öncelik sınıfı ve iş parçacığının o sınıf içindeki göreli önceliği (Tablo 5.25).

Değişken sınıftaki iş parçacıklarının önceliği zamanla değişir; bu, MLFQ'nun Windows'taki karşılığıdır. Bir G/Ç tamamlandığında iş parçacığının önceliği geçici olarak artırılır. Artış klavye ve fare gibi etkileşimli aygıtlarda disk G/Ç'sinden daha büyüktür. Ön plandaki pencerenin iş parçacıkları ve GUI olaylarıyla uyanan iş parçacıkları da artış alır. Artırılmış öncelik her dilimde 1 azalarak tabana döner ve hiçbir zaman 15'i aşmaz. Açlığa karşı da bir önlem vardır: yaklaşık 4 saniye boyunca hazır olduğu hâlde çalışamamış iş parçacığının önceliği bir dilimlik süre için 15'e çıkarılır. Dilim istemci sürümlerinde yaklaşık 2, sunucu sürümlerinde 12 saat tıkıdır; sunucuda uzun dilim bağlam değiştirmeyi azaltıp verimi artırır (Şekil 5.51).

5.9Algoritmaları değerlendirme

Bu kadar algoritma arasından belirli bir sistem için hangisi seçilmelidir? Önce ölçüt belirlenir: örneğin “en uzun tepki süresi 300 ms'yi aşmasın, bu koşulla verim en büyük olsun”. Sonra algoritmalar bu ölçüte göre değerlendirilir. Değerlendirmenin dört yolu vardır.

5.9.1Dört yöntem ve Little yasası

Deterministik modelleme. Önceden verilmiş belirli bir iş yükü için her algoritmanın sonucu hesaplanır. Bu bölümdeki bütün Gantt şemaları deterministik modellemedir. Yöntem kesin ve basittir, sonuçlar karşılaştırılabilir sayılardır. Zayıflığı, sonucun yalnız o girdi için geçerli olmasıdır: başka bir kümede sıralama değişebilir.

Kuyruk modelleri. Gerçek sistemde iş yükü her gün değişir, ama süreçlerin geliş ve hizmet sürelerinin dağılımı ölçülebilir. Kuyruk kuramı bu dağılımlardan ortalama kuyruk uzunluğu, ortalama bekleme süresi ve kullanım gibi büyüklükleri hesaplar. En temel araç Little yasasıdır.

Kararlı durumda sisteme giren süreç sayısı çıkan süreç sayısına eşittir. Saniyede λ süreç gelir ve her biri W saniye kalırsa, herhangi bir anda içeride ortalama λ × W süreç bulunur. Saniyede 7 süreç gelir ve her biri ortalama 2 saniye kalırsa sistemde ortalama 14 süreç vardır. Yasa geliş ve hizmet dağılımlarından bağımsızdır; bu yüzden çok geniş bir alanda kullanılır. Herhangi iki büyüklük biliniyorsa üçüncüsü bulunur. Bir sunucuya saniyede 6 istek geliyor ve sistemde ortalama 18 istek bulunuyorsa her istek ortalama W = 18 / 6 = 3 saniye kalır (Şekil 5.52).

Kuyruk modellerinin sınırı, matematiksel olarak çözülebilmeleri için yapılan varsayımlardır. Gelişlerin Poisson dağılımına uyduğu gibi varsayımlar gerçek iş yüklerinde tam tutmaz; karmaşık algoritmaların modeli de çoğu zaman çözülemez.

Simülasyon. Sistemin programlanmış bir modeli kurulur: saat, kuyruklar, çizelgeleyici. Model rastgele üretilmiş ya da gerçek bir sistemden kaydedilmiş iz (trace) verisiyle çalıştırılır. İz verisi gerçek olayların sırasını koruduğu için sonuçlar gerçeğe yakındır. Bedeli zamandır: ayrıntılı bir simülasyon saatler sürebilir ve kayıtlar büyük yer tutar.

Gerçekleştirme. En kesin yol algoritmayı gerçek çekirdeğe koyup denemektir. Bu yol eskiden pahalıydı: çekirdeği değiştirmek, derlemek ve yeniden başlatmak gerekiyordu. Bugün Linux'un sched_ext altyapısı BPF ile yazılmış çizelgeleyicileri çekirdeği yeniden derlemeden yüklemeye izin verir; büyük şirketler farklı çizelgeleyicileri üretimde A/B testiyle karşılaştırır. Gerçekleştirmenin ince bir sorunu da vardır: kullanıcılar ve programcılar algoritmaya uyum sağlar. CTSS'te Enter tuşuna basan kullanıcılar bunun ilk örneğiydi; ölçülen davranış algoritma yüzünden değişebilir.

5.9.2Ortak kümede karşılaştırma

Ortak kümede incelenen bütün algoritmaların sonuçları Tablo 5.26'da bir araya getirilmiştir (Şekil 5.53).

SRTF ortalama beklemede en iyisidir (6,5), ama sürelerin bilinmesini ister. RR q = 2 tepkide en iyisidir (2), ama en çok geçişi yapar ve beklemede en kötüsüdür. Kesmeli öncelik bekleme süresini değil önemi optimize eder; ortalaması FCFS'den kötü, ama en önemli P3 hiç beklemez. Tek bir “en iyi” algoritma yoktur. Seçim hedefe bağlıdır: tepki, verim, adalet ya da son tarih. Gerçek sistemlerin MLFQ ya da EEVDF gibi karma yapılar kullanmasının nedeni budur: kısa işleri öne alırken kimseyi aç bırakmamaya ve tepkiyi sınırlı tutmaya çalışırlar.

5.9.3Dönüş, tepki ve adalet üzerine üç alıştırma

5.10Özet

• Kısa vadeli çizelgeleyici CPU boşalınca hazır kuyruğundan bir süreç seçer; görev dağıtıcı bağlamı değiştirir, kullanıcı moduna geçer ve programa atlar. Aradaki süre dağıtım gecikmesidir.
• Süreçler CPU ve G/Ç patlamaları arasında gidip gelir. Patlamaların çoğu kısadır; G/Ç'ye bağlı süreçleri bekletmemek aygıtları meşgul tutar. Her patlamayı ayrı iş saymak G/Ç ile hesaplamayı örtüştürür.
• Karar dört durumda alınır: çalışıyor → bekliyor, çalışıyor → hazır, bekliyor → hazır ve sonlanma. Kesmesiz çizelgeleyici yalnız 1. ve 4. durumda, kesmeli olan dördünde de karar verir.
• Ölçütler: CPU kullanımı ve verim büyük; dönüş (B − G), bekleme (dönüş − CPU) ve tepki (İ − G) süreleri küçük olmalıdır. Çizelgeleyici yalnız bekleme süresini etkiler.
• FCFS basit ve açlıksızdır, ama geliş sırasına duyarlıdır ve konvoy etkisi yaratır. SJF hepsi hazır işlerde ortalama beklemeyi en aza indirir; sonraki patlama üstel ortalamayla tahmin edilir: τ_n+1 = α t_n + (1 − α) τ_n. SRTF kesmeli sürümdür ve ortak kümede en düşük beklemeyi (6,5 ms) verir.
• Öncelik çizelgemede açlık yaşlandırmayla, öncelik terslemesi öncelik kalıtımıyla çözülür.
• RR her sürece en fazla q süre verir; hiçbir süreç (n − 1) · q'dan uzun beklemez. q küçüldükçe tepki iyileşir, geçiş artar; kayıp oranı s / (q + s)'dir. q en uzun patlamayı aşınca RR FCFS olur.
• MLQ süreçleri kalıcı sınıflara ayırır. MLFQ davranışa göre taşır: yeni iş üstte başlar, düzeydeki hakkını bitiren iner, belirli aralıklarla herkes en üste çıkar.
• Orantılı pay: garantili ve adil paylaşım (Linux cgroup cpu.weight), olasılıksal piyango ve deterministik stride (adım = sabit / bilet, en küçük pass çalışır).
• Çok işlemcide modern sistemler SMP ve çekirdek başına kuyruk kullanır; dengesizlik itme ve çekme göçüyle giderilir, göç ise afiniteyi bozar. SMT çekirdekleri, NUMA ve heterojen çekirdekler kararı karmaşıklaştırır.
• Gerçek zamanda RM statik önceliklidir; ΣU ≤ n(2^1/n − 1) yeterli koşuldur. EDF dinamiktir; ΣU ≤ 1 yeterli ve gereklidir. Linux SCHED_DEADLINE EDF ile CBS'yi birleştirir.
• Linux sınıfları sırayla sorar: stop, deadline, rt, fair, ext, idle. CFS en küçük vruntime'ı seçer (vruntime += Δ × 1024 / ağırlık); EEVDF uygun görevler arasında en erken sanal son tarihi seçer. Windows 32 düzeyli öncelik ve dinamik artırma kullanır.
• Değerlendirme yöntemleri: deterministik modelleme, kuyruk modelleri (Little yasası n = λ × W), simülasyon ve gerçekleştirme.

5.11Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• çizelgeleyici scheduler
• hazır kuyruğu ready queue
• CPU patlaması CPU burst
• kesmeli / kesmesiz çizelgeleme preemptive / nonpreemptive scheduling
• görev dağıtıcı dispatcher
• bağlam değiştirme context switch
• verim throughput
• dönüş süresi turnaround time
• tepki süresi response time
• konvoy etkisi convoy effect
• en kısa iş önce shortest-job-first
• üstel ortalama exponential average
• açlık starvation
• yaşlandırma aging
• öncelik terslemesi priority inversion
• zaman dilimi time slice (quantum)
• çok düzeyli geri beslemeli kuyruk multilevel feedback queue
• piyango çizelgeleme lottery scheduling
• yük dengeleme load balancing
• işlemci afinitesi processor affinity
• hız monoton çizelgeleme rate-monotonic scheduling
• en erken teslim zamanı önce earliest deadline first

5.12Kendini Dene

1. P1 (geliş 0, CPU 7), P2 (1, 3), P3 (3, 2), P4 (6, 1). Kesmesiz SJF ve SRTF ile ortalama bekleme süreleri nedir?

   Cevap

   SJF: P1 0–7 kesilmez; t = 7'de hazır P2 (3), P3 (2), P4 (1); sıra P4 7–8, P3 8–10, P2 10–13. Beklemeler 0, 9, 5, 1; ortalama 15 / 4 = 3,75 ms. SRTF: t = 1'de P2 (3) < P1'in kalanı 6, P1 kesilir; P2 1–4, P3 4–6, P4 6–7, P1 7–13. Beklemeler 6, 0, 1, 0; ortalama 7 / 4 = 1,75 ms.

2. A (geliş 0, CPU 5), B (1, 4), C (2, 3); RR, q = 2. Yeni gelen süreç, dilimi biten süreçten önce kuyruğa girer. Gantt şeması ve ortalama bekleme nedir?

   Cevap

   A 0–2, B 2–4, C 4–6, A 6–8, B 8–10 (biter), C 10–11 (biter), A 11–12 (biter). Bitişler A 12, B 10, C 11. Beklemeler A 12 − 0 − 5 = 7, B 10 − 1 − 4 = 5, C 11 − 2 − 3 = 6; ortalama 6 ms. Ortalama tepki (0 + 1 + 2) / 3 = 1 ms.

3. α = 0,25 ve τ₀ = 10 ms. Ölçülen patlamalar 4, 4 ve 16 ms. τ₃ nedir? α = 0,25 seçmenin bu dizideki etkisi nedir?

   Cevap

   τ₁ = 0,25 · 4 + 0,75 · 10 = 8,5; τ₂ = 0,25 · 4 + 0,75 · 8,5 = 7,375; τ₃ = 0,25 · 16 + 0,75 · 7,375 ≈ 9,53 ms. Küçük α geçmişe çok ağırlık verir: iki kısa patlamadan sonra tahmin hâlâ 7'nin üstündedir ve 16'ya sıçrayan patlamaya da yavaş yetişir.

4. MLFQ: Q0 (q = 3), Q1 (q = 6), Q2 (FCFS). A (geliş 0, CPU 12), B (2, 2), C (5, 6). İşler ne zaman biter?

   Cevap

   A 0–3 dilimini doldurur ve Q1'e iner. B 3–5'te Q0'da biter. t = 5'te gelen C 5–8 Q0 dilimini doldurur ve Q1'e iner. A Q1'de 8–14 çalışır, dilimini doldurup Q2'ye iner (kalan 3). C Q1'de 14–17'de biter. A Q2'de 17–20'de biter. Bitişler B 5, C 17, A 20.

5. Bir sistemde kesmesiz çizelgeleyici kullanılıyor. Çalışan süreç bir dosya okuması başlatıyor ve bu sırada daha önce başlatılmış bir disk okuması bitiyor. Bu iki olaydan hangisinde çizelgeleyici çağrılır?

   Cevap

   Yalnız ilkinde. Çalışan süreç G/Ç isteyince bekleme durumuna geçer ve CPU boşalır (çalışıyor → bekliyor); seçim zorunludur. Disk okumasının bitmesi bir süreci bekliyor → hazır durumuna geçirir; kesmesiz çizelgeleyici çalışan süreci durdurmaz, uyanan süreç hazır kuyruğuna girer.

6. Stride çizelgemede A'nın 40, B'nin 20, C'nin 80 bileti var; adım = 10 000 / bilet. Eşitlikte A, B, C sırası. İlk 7 dilimde çalışma sırası nedir?

   Cevap

   Adımlar A 250, B 500, C 125. Sıra A, B, C, C, A, C, C. A 2, B 1, C 4 dilim alır; oran 2 : 1 : 4 = 40 : 20 : 80. Yedinci dilimin sonunda üç pass değeri de 500'dür.

7. Üç periyodik görev: T1 (p = 4, t = 1), T2 (p = 5, t = 2), T3 (p = 10, t = 3). Liu–Layland testi ne söyler? RM gerçekten son tarih kaçırır mı?

   Cevap

   U = 0,25 + 0,4 + 0,3 = 0,95. Üç görev için sınır ≈ 0,780; test karar veremez (sonuç 0). 20 ms'lik hiperperiyot boyunca RM çizelgesi çizilirse (T1 0–1, T2 1–3, T3 3–4, T1 4–5, T2 5–7, T3 7–8, T1 8–9, T3 9–10, …) hiçbir son tarih kaçırılmaz. Test yeterli koşuldur, gerekli değil.

8. Linux CFS'de CPU'ya bağlı iki görev var: A nice −5 (ağırlık 3121), B nice 0 (ağırlık 1024). Payları yaklaşık nedir? Hangisinin vruntime'ı daha hızlı artar?

   Cevap

   A 3121 / 4145 ≈ %75, B ≈ %25. vruntime += Δ × 1024 / ağırlık olduğundan B'nin vruntime'ı aynı çalışma süresinde yaklaşık 3 kat hızlı artar; B daha seyrek seçilir.

9. Çekirdek başına kuyruklu bir sistemde neden ortak tek kuyruk kullanılmaz? Çekirdek başına kuyruğun bedeli nedir?

   Cevap

   Ortak kuyrukta her erişim bir kilit ister; çekirdek sayısı arttıkça kilit çekişmesi büyür ve iş her seferinde farklı çekirdekte çalışabildiği için önbelleği soğuk kalır. Çekirdek başına kuyrukta kilit gerekmez, afinite korunur; ama kuyruklar dengesizleşebilir ve yük dengeleme (itme ve çekme göçü) gerekir. Göç eden iş yeni çekirdekte önbelleği soğuk bulur.

10. RR'de q = 9 ms ve her bağlam değiştirme 1 ms. Süreçler dilimlerini sonuna kadar kullanıyor. CPU zamanının yüzde kaçı geçişe gider? q = 4'e göre ne değişir?

    Cevap

    1 / (9 + 1) = %10. q = 4'te kayıp 1 / 5 = %20 idi. Dilim büyüdükçe kayıp azalır, ama kuyruktaki her süreç bir sonraki dilimini daha uzun bekler ve tepki süresi kötüleşir.

5.13İleri okuma

• R. H. Arpaci-Dusseau ve A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, “Scheduling: Introduction”, “The Multi-Level Feedback Queue”, “Lottery Scheduling” ve “Multiprocessor Scheduling” bölümleri: MLFQ kurallarını sorunlardan yola çıkarak kurar, piyango ve stride çizelgelemeyi kısa C kodlarıyla anlatır; ostep.org'da ücretsizdir.
• C. L. Liu ve J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM, 20(1), 1973: RM'nin optimalliğini ve kullanım sınırını, EDF'nin ΣU ≤ 1 koşulunu kanıtlayan temel makaledir.
• Linux çekirdek belgeleri, Documentation/scheduler/sched-eevdf.rst ve sched-deadline.rst: EEVDF'in uygunluk ve sanal son tarih kurallarını ve SCHED_DEADLINE'ın kabul denetimini çekirdeğin kendi belgesinde anlatır.
• P. Yosifovich ve diğerleri, Windows Internals, 7. baskı, Kısım 1, Bölüm 4: Windows'un öncelik düzeylerini, dilim hesabını, dinamik artırmaları ve çok işlemcili iş parçacığı seçimini ayrıntılı verir.

5.14Kaynaklar

1. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018 — Bölüm 5: CPU Scheduling.
2. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı (2014) / 5. baskı (2023), Pearson — Kesim 2.4: Scheduling.
3. R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), ostep.org — Bölüm 7–10: Scheduling, MLFQ, Lottery, Multiprocessor.
4. P. Yosifovich, A. Ionescu, M. Russinovich, D. Solomon, Windows Internals, 7. baskı, Kısım 1, 2017 — Bölüm 4: Thread scheduling.
5. Linux çekirdek belgeleri: sched-eevdf.rst, sched-design-CFS.rst, sched-deadline.rst, sched-ext.rst; sched(7) kılavuz sayfası.
6. I. Stoica, H. Abdel-Wahab, “Earliest Eligible Virtual Deadline First”, 1995.
7. C. L. Liu, J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM, 20(1), 1973, s. 46–61.
8. C. A. Waldspurger, W. E. Weihl, “Lottery Scheduling: Flexible Proportional-Share Resource Management”, OSDI, 1994.