#07 Öncelik, çok seviyeli kuyruk ve yük dengesi

Aşağıda defterde yazılan bütün satırlar ve bunlara eşlik eden sesli anlatımın tam metni bulunur.

1. 1. Hangi işe öncelik, hangi çekirdeğe yük?

   

   Geçen ders: sıra ve zamanlama ölçüleri

   Bugün: öncelik · kuyruklar · yük dengesi

   Sesli anlatım metni

   Geçen derste önce gelen, kısa iş ve zaman dilimli dönüş yöntemlerini aynı iş kümesinde karşılaştırdık. Bugün önceliklerin ve farklı kuyrukların seçimi nasıl değiştirdiğine bakıyoruz. Sonra tek çekirdekten çıkıp, işleri birden fazla çekirdeğe dağıtmayı düşüneceğiz. Bir işi erken seçmek ile bütün işleri dengeli dağıtmak ayrı kararlardır.

2. 2. Öncelik sayısının yönünü önce söyle

   

   Bu model: küçük sayı = yüksek öncelik

   A: geliş 0 · CPU 5 ms · öncelik 3

   B: geliş 1 · CPU 3 ms · öncelik 1

   C: geliş 2 · CPU 1 ms · öncelik 2

   Öncelik: önemli iş; risk: sonsuz bekleme

   Sesli anlatım metni

   Özgün modelimizde küçük öncelik sayısı daha yüksek öncelik demek. Bu evrensel bir numaralandırma değildir; başka bir sistem ters yön kullanabilir. Tek çekirdekte, geçiş maliyeti olmadan kesmeli seçim yapacağız. A, zaman sıfırda gelir, beş milisaniye işlemci ister; öncelik sayısı üç. B, birinci milisaniyede gelir, üç milisaniye iş ister; öncelik sayısı bir. C, ikinci milisaniyede gelir, bir milisaniye iş ister; öncelik sayısı iki. En kısa iş ile en yüksek öncelik aynı iş olmak zorunda değildir. Hastanede sıradan başvuru ile acil başvuruyu ayırmak gibi düşünün. Öncelik başka bir ihtiyacı temsil eder. Ama hep acil başvuru gelirse sıradan iş sonsuza kadar bekleyecek mi? Bugünün ikinci sorusu da bu.

3. 3. Kesmeli öncelik çizelgesini kur

   

   A: 0 → 1 ms; B gelince kesilir

   B: 1 → 4 ms

   C: 4 → 5; A kalan: 5 − 1 = 4 ms

   A: 5 → 9 ms; tamamlandı

   Öncelik ve kesme seçimini ayrı belirt.

   Sesli anlatım metni

   Başta yalnız A hazır. Sıfırdan bire kadar bir milisaniye çalışır. B geldiğinde B’nin önceliği daha yüksek olduğu için A kesilir. B, birden dörde kadar çalışır ve dördüncü milisaniyede biter. C arada geldi ama önceliği B’den düşük olduğu için B’yi kesmez. Sonra C, dörtten beşe kadar çalışır; beşinci milisaniyede biter. A’nın kalan işi beş eksi bir, dört milisaniyedir. A, beşten dokuza kadar çalışır ve dokuzuncu milisaniyede tamamlanır. Önceliği düşük olsa da yeni yüksek öncelikli iş gelmediği için sonunda işlemciyi aldı. Bu çizelge kesmeli öncelik içindi. Kesmesiz biçimde A kendiliğinden bırakana kadar sürebilirdi. Öncelik var demek, kesme politikasının da belli olduğu anlamına gelmez.

4. 4. Öncelik örneğinin bekleme hesabı

   

   A: 9 − 0 − 5 = 4 ms

   B: 4 − 1 − 3 = 0 ms

   C: 5 − 2 − 1 = 2 ms

   Ortalama: (4 + 0 + 2) / 3 = 2 ms

   Kontrol: gelişten önce çalışma yok; CPU işi korunur.

   Sesli anlatım metni

   Girdi çıktı olmadığı için bekleme, bitiş eksi geliş eksi işlemci işidir. A için dokuz eksi sıfır eksi beş; dört milisaniye bekleme. B için dört eksi bir eksi üç; sıfır milisaniye bekleme. B geldiği anda başlamıştı. C için beş eksi iki eksi bir; iki milisaniye bekleme. Toplam dört artı sıfır artı iki, altı. Altı bölü üç, iki milisaniye ortalama. İlk başlangıç, geliş ve bitiş zamanlarını karıştırmadan bulduk. Makullük kontrolü: hiç kimse gelişinden önce çalışmıyor ve her işin çalışma parçaları toplamı kendi ihtiyacına eşit. Bu iki kontrol, iyi görünen ama yanlış bir çizelgeyi yakalayabilir.

5. 5. Aç kalma ve yaşlandırma

   

   Aç kalma: hazır iş sürekli ertelenir.

   Model: öncelik 5; her 3 ms’de bir iyileşme

   Bekleme: 0 → 3 → 6 → 9 → 12 ms; öncelik: 5 → 4 → 3 → 2 → 1

   Yaşlandırma tek başına kesin başlama saati vermez.

   Sesli anlatım metni

   Sürekli yüksek öncelikli yeni işler gelirse düşük öncelikli bir hazır iş süresiz ertelenebilir. Buna aç kalma diyoruz. İş hazırdır ama politika ona sıra vermiyordur. Yaşlandırma, bekledikçe önceliğini artırmayı amaçlar. Öğretim kuralımızda başlangıç önceliği beş, her üç milisaniyelik beklemede sayı bir azalıyor ve birin altına inmiyor. Üçüncü milisaniyede dört, altıncıda üç, dokuzuncuda iki, on ikinci milisaniyede bir olur. Sayı azalırken öncelik yükseliyor; yönü başta tanımlamamızın nedeni buydu. Bu, işin tam o anda kesin çalışacağı garantisi değildir. Eşit öncelikteki seçim, hazır diğer işler ve sistemin kuralları da önemlidir. Adalet için bütün politikanın davranışını düşünmek gerekir.

6. 6. Çok seviyeli ile geri bildirimli kuyruk

   

   İki karar: kuyruk içi ve kuyruklar arası

   Sabit kuyruk ≠ geri bildirimli kuyruk

   Davranışa göre düzey değiştirme

   İniş · yükseltme · seçim kurallarını açık yaz.

   Sesli anlatım metni

   Çok seviyeli kuyruklarda işler gruplara ayrılır. Her kuyruğun kendi zamanlama yöntemi olabilir; ayrıca kuyruklar arasında hangi grubun ne zaman seçileceği belirlenmelidir. Sabit sınıflandırmada süreç seçilmiş kuyruğunda kalabilir. Geri bildirimli çok seviyeli kuyrukta ise davranışına göre kuyruk değiştirebilir. Bu ikisini aynı yapı sanmayın. Kısa ve etkileşimli işler yüksek düzeyden hizmet alırken, uzun işlemci işleri daha aşağıya taşınabilir. Bunun ayrıntısı kullanılan politika ve ölçülen davranışa bağlıdır. Alt kuyrukları sürekli ertelememek için yaşlandırma veya dönemsel yükseltme gibi kurallar da gerekebilir. Kutuları çizmek yetmez; iniş, çıkış ve seçim kuralları açık olmalıdır.

7. 7. Özgün geri bildirim örneği

   

   Model: üst dilim 2 ms; orta dilim 4 ms

   A: 0 → 2; B: 2 → 3 ve bitti

   A: 3 → 7; kalan 6 − 4 = 2 ms

   A: 7 → 9; toplam 2 + 4 + 2 = 8 ms

   Politika ve varsayımlar değişirse çizelge değişir.

   Sesli anlatım metni

   Küçük modelimizde üst kuyruk iki milisaniyelik, orta kuyruk dört milisaniyelik dilim verir. Alt kuyruk kesmesizdir. Dilimini tamamen kullanıp bitmeyen iş bir alt düzeye iner; yeni iş gelmiyor. Zaman sıfırda A sekiz, B bir milisaniye iş istiyor; sırada A önce. A sıfırdan ikiye çalışır ve altı işi kalır; orta kuyruğa iner. B ikiden üçe çalışıp üçüncü milisaniyede biter. Üst kuyruk boşaldı. A orta kuyrukta üçten yediye kadar dört milisaniye alır. Altı eksi dört, iki milisaniye işi kalır ve alta iner. Son iki milisaniyeyi yediden dokuza çalışır; dokuzuncu milisaniyede biter. A toplam iki artı dört artı iki, sekiz milisaniye işlemci kullanmıştır. Kısa B erken bitirken uzun A düzey değiştirdi. Bu, belirli bir gerçek işletim sistemi ölçümü değildir. Yeni işler, yükseltme ve geçiş maliyeti olsaydı çizelge de değişebilirdi.

8. 8. Çekirdekler arasında yükü dengele

   

   İlk dağılım: çekirdek A yükü 6 + 2 = 8 ms

   Diğer çekirdek: 4 ms; bütün işlerin bitişi 8 ms

   Dengeli dağılım: 6 ms ve 2 + 4 = 6 ms

   Kazanç: 8 − 6 = 2 ms

   Yük dengesi ve işlemci yakınlığı arasında karar

   Sesli anlatım metni

   Şimdi iki aynı çekirdekte bağımsız işler düşünün. A altı, B iki, C dört milisaniye istiyor. Maliyet ve kaynak çekişmesi yok. İlk çekirdeğe A ve B, ikinciye C verilirse ilk yük altı artı iki, sekiz milisaniyedir. İkinci çekirdeğin dört milisaniyelik işi daha erken biter. Bütün işlerin tamamlanması yavaş biten çekirdeğe bağlı; bu dağılımın bitişi sekiz milisaniye. Yeniden dağıtalım: A yalnız ilk çekirdekte altı milisaniye sürsün. B ve C ikinci çekirdekte, iki artı dört; altı milisaniye yük oluşturur. İki taraf da altıda bittiği için toplam tamamlanma altı milisaniye olur. Sekiz eksi altı, iki milisaniye kazanç. İşlemcileri hızlandırmadık; boş kalma ile yığılmayı azalttık. Yalnız iş sayısını eşitlemek, iş yükünü eşitlemek değildir. Gerçekte bir işi başka çekirdeğe taşımak önbellek ve bellek erişimi maliyeti doğurabilir. İşin aynı çekirdekte kalma eğilimine işlemci yakınlığı diyoruz. Yük dengesi ile yakınlığı birlikte değerlendirmek gerekir.

9. 9. Öncelik ile adalet birlikte düşünülür

   

   Soru: öncelik sayısının yönü belli mi?

   Yanıt: bu modelde küçük sayı daha yüksek.

   Aynı iş sayısı ≠ aynı CPU yükü

   Politikayı bütün kurallarıyla değerlendir.

   Sesli anlatım metni

   Kontrol sorusu: öncelik sayısı bir olan iş mi, beş olan iş mi önce seçilir? Önce bu sistemde sayıların yönünü bilmeniz gerekir. Bizim modelimizde küçük sayı daha yüksek öncelikti. Ama bu bilgiyi başka bir sisteme otomatik taşıyamazsınız. Karşılaştırmada kullandığınız kuralı önce okuyun. Bir diğer kontrol: iki kuyrukta aynı sayıda iş olması dengeli yük müdür? İşlerin süreleri farklıysa olmayabilir. İş sayısı ile işlemci iş miktarı ayrı ölçülerdir. Zamanlama yalnız bir listeyi sıralamak değildir. Öncelik, bekleme, kuyruk davranışı, çekirdek uygunluğu ve maliyet birlikte bir politika oluşturur.

10. 10. Üç yanlış içgüdü

    

    Öncelik sayısının yönünü varsayma.

    Geri bildirim, kuyruk değiştirme kuralıdır.

    Sayıları saymak, yükü ölçmek değildir.

    Tanımla · beklemeyi sınırla · yükü tart

    Sesli anlatım metni

    Birinci hata: büyük öncelik sayısı her sistemde daha önceliklidir. Hayır; yönü açıkça tanımlamak gerekir. İkinci hata: geri bildirimli kuyruk, yalnız çok sayıda sabit kuyruktur. Hayır; davranışa bağlı düzey geçişi onun ayırt edici özelliğidir. Üçüncü hata: dengeli iş sayısı, dengeli işlemci yüküdür. Hayır; süreler ve taşıma maliyetleri de önemlidir. Akılda kalan kural: önceliği tanımla, uzun beklemeyi sınırla, gerçek yükü ve maliyeti tart.

11. 11. İşlemci paylaşımı, açık politika ister

    

    Öncelik · geri bildirim · yük dengesi

    Ölçü ve varsayımı sonuçla birlikte tut.

    Sonraki ders: yarış durumu ve kritik bölge

    Sesli anlatım metni

    Bilgisayar modeline dönelim. Öncelik seçimi işlere farklı sıra verdi; geri bildirim kuyruklar arasında geçiş kurdu; yük dengesi hazır işleri uygun çekirdeklere dağıtmayı düşündürdü. Her hesapta geliş, çalışma ihtiyacı ve maliyet varsayımlarını açık tuttuk. Bir politika hazır işi sonsuza kadar ertelememeli; ama tek bir sayı bütün adalet ve performans davranışını anlatmaz. Bir sonraki derste sıra değişirken ortak verinin nasıl yanlış hale gelebildiğini göreceğiz. Yarış durumu, kritik bölge ve Peterson fikriyle senkronizasyona geçiyoruz. Görüşmek üzere.

Kaynak video: Öncelik, çok seviyeli kuyruk ve yük dengesi (7:57)