Bölüm 14: İşletim Sistemi Tasarımı

14.1Tasarımın zorlukları ve hedefleri

Bir derleyici ya da veritabanı yazan ekip ne yapacağını oldukça iyi bilir. Derleyicinin girdisi bir dil tanımıyla, çıktısı bir komut kümesiyle belirlidir. İşletim sisteminin işi ise bu kadar net çizilmiş değildir. Üzerinde hangi programların çalışacağı, hangi donanımda ve kaç yıl kullanılacağı önceden bilinmez. Bu yüzden işletim sistemi tasarımı bir algoritma seçmekten çok, birbiriyle çatışan isteklerin dengelenmesidir.

14.1.1İşletim sistemi tasarlamak neden zor?

Tanenbaum, işletim sistemi tasarımını diğer yazılım projelerinden daha zor kılan sekiz etken sayar (Tablo 14.1). Bu etkenlerin bir kısmı yalnız büyüklükten, bir kısmı da işletim sisteminin konumundan kaynaklanır. İşletim sistemi donanım ile bütün uygulamalar arasında durur ve ikisinin de değişmesine dayanmak zorundadır.

Boyut tek başına ciddi bir sorundur. Kırk milyon satırın büyük kısmı sürücü kodudur, ama geri kalanı da tek bir kişinin aklında tutabileceğinden çok büyüktür. Böyle bir sistemde bir değişikliğin nereleri etkileyeceğini kestirmek zordur. Bu yüzden iyi tasarlanmış arayüzler ve bağımlılıkları sınırlayan bir yapı, kodun kendisi kadar önemlidir.

Eş zamanlılık işletim sistemine özgü bir zorluktur. Uygulama programcısı çoğu zaman tek iş parçacıklı düşünebilir. Çekirdek ise kesmelerle, birden çok çekirdekle ve aynı anda gelen sistem çağrılarıyla baştan beri eş zamanlıdır. Bir hata ancak belirli bir zamanlama denk geldiğinde ortaya çıkabilir ve yeniden üretilmesi günler sürebilir.

Düşmanca kullanıcılar ile yalıtıma rağmen paylaşım birbirini dengeleyen iki istektir. Sistem her kullanıcıyı diğerlerinden korumalıdır, ama kullanıcılar birlikte çalışabilmek için dosya ve bellek de paylaşmak ister. Paylaşım için açılan her kapı aynı zamanda bir saldırı yüzeyidir.

Son dört etken zamanla ilgilidir. Uzun ömür, sistemin bugün var olmayan donanıma uyum sağlamasını gerektirir. UNIX 1970'lerde tasarlandığında ne çok çekirdekli işlemciler ne de SSD'ler vardı. Genellik, tasarımcının tek bir kullanım biçimine göre iyileştirme yapmasını engeller. Taşınabilirlik donanıma bağımlı kodu sınırlamayı zorunlu kılar. Geriye dönük uyumluluk ise yayımlanmış her arayüzü kalıcı yapar. Uzun bakım ve onarım ihtiyacı, uzun ömür ile uyumluluk zorunluluğunun doğal sonucudur.

14.1.2Dört temel hedef

Zorlukların karşısında işletim sisteminin ne için var olduğunu açıkça koymak gerekir. Tanenbaum dört temel hedef sayar. Bu hedefler bir katman resmi gibi düşünülebilir: uygulamalar üstte, donanım altta, işletim sistemi aradadır (Şekil 14.1).

1. Soyutlamalar tanımlamak. Disk aslında numaralı bloklardan oluşan bir dizidir. Dosya ise adı, boyutu ve izinleri olan, bayt bayt okunan bir nesnedir. Aradaki farkı işletim sistemi kapatır. Tasarımın en zor kısmı doğru soyutlamayı bulmaktır. Çok ayrıntılı bir soyutlama donanımı yeterince gizlemez; çok kaba bir soyutlama ise bazı uygulamalara dar gelir.
2. İlkel işlemler sağlamak. Soyutlama ancak üzerinde işlem yapılabildiğinde işe yarar. Dosya için open, read, write ve close; süreç için fork ve execve; adres alanı için mmap; senkronizasyon için futex bu işlemlerdir.
3. Yalıtım sağlamak. Kullanıcılar ve süreçler birbirine karışmamalıdır. Her süreç kendi adres alanında çalışır; biri çökerse diğerleri etkilenmez. Yine de dosya izinleri ve paylaşımlı bellek gibi denetimli paylaşım yolları açık kalmalıdır.
4. Donanımı yönetmek. Kesmeler, zamanlayıcılar, MMU ve aygıt denetleyicileri bu hedefin konusudur. Düşük seviyeli işlerin çoğu bu katmanda yapılır; üstteki hedeflerin hepsi buna dayanır.

Dört hedef birbirinden bağımsız değildir. Yalıtım ancak donanım yönetimiyle, yani MMU ve ayrıcalık seviyeleriyle sağlanabilir. Soyutlamalar ise ilkel işlemler olmadan yalnız birer addır. Bu notun geri kalanı büyük ölçüde şu sorunun cevabıdır: bu hedefler hangi yapı ve hangi ilkelerle, ne kadar maliyetle gerçeklenir?

14.2Arayüz tasarımı

İşletim sisteminin dış dünyaya gösterdiği yüz, sistem çağrısı arayüzüdür. Uygulamalar bu arayüze göre yazılır ve arayüz bir kez yayımlandıktan sonra pratikte değiştirilemez. Bu yüzden arayüzün nasıl tasarlandığı, çekirdeğin içinin nasıl yazıldığından daha uzun ömürlü bir karardır.

14.2.1Yol gösterici ilkeler

İyi bir arayüz için kesin bir tarif yoktur, ama üç ilke tasarımcıya yol gösterir: basitlik, bütünlük ve verimlilik.

Basitlik için sıkça anılan söz Antoine de Saint-Exupéry'ye aittir: mükemmelliğe, eklenecek bir şey kalmadığında değil, çıkarılacak bir şey kalmadığında ulaşılır. Az sayıda kavramı öğrenmek, gerçeklemek ve doğrulamak kolaydır. Her yeni kavram, diğer bütün kavramlarla etkileşimi de beraberinde getirir.

Bütünlük basitliğin karşı ağırlığıdır. Einstein'a atfedilen söz bunu özetler: her şey olabildiğince basit olmalı, ama daha basit değil. Bir arayüz çok sade olduğu için gereken bir işi yapamıyorsa uygulamalar onu dolanmanın yollarını arar ve sonuç daha karmaşık olur. İdeal olan, az mekanizma ile çok iş yapabilmektir. MINIX 3 çekirdeği süreçler arası iletişim için yalnız birkaç ilkel sunar: send, receive, sendrec ve notify. Dosya sistemi, sürücüler ve bellek yönetimi bu birkaç ilkel üzerine kurulur.

Verimlilik ilkesi iki şey söyler. Birincisi, verimli gerçeklenemeyen bir özellik muhtemelen eklenmeye değmez. İkincisi, programcı bir çağrının yaklaşık maliyetini sezebilmelidir. lseek yalnız dosya ofsetini değiştirir ve ucuzdur; read ise disk erişimi gerektirebilir ve pahalı olabilir. Ucuz görünen bir çağrı gizlice pahalıysa programcı yanlış kararlar verir.

Bu üç ilkeden pratik bir kural çıkar: her sistem çağrısı tek bir işi iyi yapmalıdır. Özellik eklemek kolaydır, kaldırmak ise neredeyse imkânsızdır. Geriye dönük uyumluluk yüzünden yanlış bir karar yıllarca taşınır.

14.2.2Küçük güzeldir

Basitlik ilkesinin en somut ölçüsü sistem çağrısı sayısıdır. Az sayıda genel çağrı, çok sayıda özel çağrıdan iyidir. Gerçek sistemler bu ölçüde birbirinden büyük farklarla ayrılır (Şekil 14.3).

Ölçek logaritmik olduğu için çubuklar arasındaki fark gözü yanıltabilir. Windows'un çağrı sayısı seL4'ünkünün yaklaşık 140 katı, Linux'unki UNIX V7'ninkinin dokuz katından fazladır. Çağrı sayısı arttıkça saldırı yüzeyi de büyür: her çağrı, kötü niyetli bir girdinin çekirdeğe ulaşabileceği bir kapıdır.

seL4 mikro çekirdeği bu ilkenin uç örneğidir. Çekirdeği yaklaşık 10 bin satırdır ve biçimsel olarak doğrulanmıştır: C kodunun matematiksel bir belirtime uyduğu ispatlanmıştır. Milyonlarca satırlık bir çekirdekte böyle bir ispat bugünkü yöntemlerle mümkün değildir.

Linux'ta ise çağrı sayısı her yıl birkaç tane artar. Yakın zamanda eklenen io_uring_*, landlock_* ve mseal çağrıları buna örnektir. Windows farklı bir yol izler: belgelenmiş arayüz çekirdek çağrıları değil, Win32 API'dir. Çekirdek çağrıları sürümden sürüme değişebilir, çünkü uygulamalar onları doğrudan kullanmaz. Bu düzende araya giren kütüphane katmanı uyumluluğu korur.

14.2.3Kullanıcı arayüzü paradigmaları

Kullanıcı arayüzü çoğu zaman çekirdeğin parçası değildir. Yine de seçilen paradigma bütün sistemin tasarımını etkiler. Dört paradigma bugün yan yana yaşar.

• Komut satırı (CLI, command-line interface). Kabuk, metin komutları ve borular. Otomasyon ve uzaktan yönetim için hâlâ vazgeçilmezdir.
• WIMP / GUI. Pencere, simge, menü ve işaretçi (windows, icons, menus, pointer). Fare tuşlarının anlamı her uygulamada aynı olmalıdır.
• Dokunmatik ve mobil. Kaydırma ve yakınlaştırma gibi hareketler, tam ekran uygulamalar, bildirim merkezi.
• Ses, sohbet ve ajanlar. Sesli asistanlar ve doğal dil arayüzleri işletim sistemi hizmetlerine yeni bir giriş noktası açar.

Paradigmanın çekirdeğe etkisi en açık biçimde grafik arayüzde görülür. Bir GUI, olay güdümlü bir yürütme modeli, hızlı bir pencere sistemi ve tutarlı bir uygulama çerçevesi gerektirir. Bir tıklama, aygıttan uygulamaya uzanan bir yol izler (Şekil 14.4).

16 ms'lik bütçe, 1000 ms / 60 ≈ 16,7 ms hesabından gelir. Bu süre içinde olay çekirdekten pencere sistemine, oradan uygulamaya geçmeli, işlenmeli ve yeni kare çizilmelidir. Uzun süren tek bir işleyici bütün arayüzü dondurur. Paradigmalar arasında ortak olan ilke tutarlılıktır: aynı eylem her yerde aynı sonucu vermelidir.

14.2.4Yürütme paradigmaları

Bir programın akışını kimin belirlediği, işletim sisteminden ne isteyeceğini de belirler. İki temel paradigma vardır.

Algoritmik kodun tipik biçimi aşağıdakine benzer. Program başlar, sırayla bir şeyler yapar, gerektiğinde okur ve yazar, sonunda biter. Derleyiciler, sıralama programları ve toplu işler bu yapıdadır.

int main(void)
{
    int x, y;
    init();
    do_something();
    read(fd, &x, sizeof x);
    do_something_else();
    write(fd, &y, sizeof y);
    keep_going();
    exit(0);
}

Olay güdümlü kod ise bir döngü etrafında kurulur. get_message sıradaki olayı getirir, switch onu türüne göre ilgili koda yönlendirir. GUI'ler, ağ sunucuları ve mikro çekirdek sunucuları bu yapıdadır.

int main(void)
{
    msg_t msg;
    init();
    while (get_message(&msg)) {
        switch (msg.type) {
        case 1: ... ; break;
        case 2: ... ; break;
        case 3: ... ; break;
        }
    }
}

Paradigma seçimi sistem çağrılarını da biçimlendirir. Algoritmik model engelleyen (blocking) bir read ister: veri gelene kadar beklenir, sonra akış kaldığı yerden sürer. Olay güdümlü model ise “sıradaki olayı ver” türünden bir çağrı ister: get_message, epoll_wait ya da io_uring_enter. Bir işletim sistemi iki paradigmayı da desteklemek zorundadır.

14.2.5Kod izleme: olay döngüsü

Olay döngüsünün nasıl çalıştığını somut bir kodla izlemek mümkündür. Aşağıdaki programda üç olay türü vardır: tuş (KEY), tıklama (CLICK) ve zamanlayıcı (TIMER). Her biri kendi işleyicisine gider.

int main(void) {
    msg_t m;
    init();
    while (get_message(&m)) {
        switch (m.type) {
        case KEY:   on_key(&m);   break;
        case CLICK: on_click(&m); break;
        case TIMER: on_timer(&m); break;
        }
    }
    return 0;
}

init() pencereyi ve kaynakları hazırlar. while koşulu get_message(&m) çağrısının dönüş değeridir. Çağrı bir olay döndürürse 1, programın kapanması gerektiğini bildiren QUIT olayında ise 0 döner. switch olay türüne göre on_key, on_click ya da on_timer işleyicisini çağırır. İşleyici bitince döngü başa döner. İzleme sekiz adımdır (Tablo 14.2).

İzlemenin iki noktası önemlidir. Birincisi altıncı adımdır. Kuyruk boşken get_message hemen dönmez, süreci uyutur. Süreç bu sırada CPU harcamaz; yeni bir olay geldiğinde çekirdek onu uyandırır. Döngü bir “meşgul bekleme” değil, engelleyen bir çağrı etrafında kurulmuş bir yapıdır.

İkincisi işleyicilerin süresidir. Döngü tek iş parçacıklıdır; bir işleyici çalışırken kuyruktaki diğer olaylar bekler. on_timer imleci yakıp söndürmek gibi kısa bir iş yapar. Ama bir işleyici büyük bir dosyayı okumaya kalkarsa arayüz o süre boyunca donar. Uzun işler bu yüzden ayrı bir iş parçacığına verilir. Aynı kalıp nginx ve Node.js gibi sunucularda epoll ile, mikro çekirdek sunucularında da ileti kuyruğuyla kullanılır.

14.2.6Veri paradigmaları

Yürütme paradigması akışı, veri paradigması ise kaynakların nasıl adlandırılıp kullanıldığını belirler. İki büyük gelenek vardır (Şekil 14.6).

UNIX'in ilkesi “her şey bir dosyadır” biçiminde özetlenir. Normal dosya /home/ali/not.txt, NVMe diski /dev/nvme0n1, bir boru, çekirdek bilgisi /proc/cpuinfo ve bir soket aynı tanımlayıcı türüyle, yani dosya tanımlayıcısıyla (fd) kullanılır. Plan 9 bu fikri daha da ileri götürmüş, ağı ve pencereleri de dosya sistemi olarak sunmuştur. Windows'ta ise her şey bir nesnedir. Nesne yöneticisi dosyaları, olayları, mutex'leri, süreçleri ve iş parçacıklarını \Device\HarddiskVolume1 gibi adlarla tek bir ad alanında tutar; program onlara bir HANDLE ile erişir.

Ortak bir veri paradigmasının kazancı, aynı araçların her kaynakta çalışmasıdır. cat, dd ve kabuk yönlendirmesi hem dosyada hem aygıtta hem de çekirdek bilgisinde iş görür. cat /proc/loadavg komutu sistemin yük ortalamasını, hiçbir özel araç gerekmeden gösterir.

Bedeli de vardır. Bazı aygıtlar dosya modeline sığmaz. Bir kameranın çözünürlüğünü ayarlamak ya da bir ağ kartının ayarlarını değiştirmek read ve write ile doğal biçimde ifade edilemez. O zaman her şey ioctl gibi “kaçış kapılarına” yığılır. ioctl aygıta göre anlamı değişen bir komut numarası alır ve tek bir çağrının arkasında yüzlerce farklı işlem saklanır. Basitlik arayüzün yüzeyinden kalkmış, ama içerde kaybolmamıştır.

14.2.7Sistem çağrısı arayüzü

Arayüz ilkelerinin en somut uygulaması sistem çağrılarının kütüphaneyle ilişkisidir. Çekirdekte az ve genel çağrı, kütüphanede ise kolaylık fonksiyonları bulunur (Şekil 14.7).

Altı fonksiyon argümanların nasıl verildiğine (liste ya da dizi), programın PATH içinde aranıp aranmadığına ve ortamın açıkça verilip verilmediğine göre ayrılır. Bu farkların hepsi kullanıcı alanında çözülür. Çekirdek yalnız bir yol, bir argüman dizisi ve bir ortam dizisi görür. Yeni bir kolaylık eklemek çekirdeği değiştirmez; yalnız kütüphane büyür.

İkinci ilke bağımsız bileşenlerdir. UNIX süreç oluşturmayı iki çağrıya böler: fork ve execve. Arada çocuk süreç kendi ortamını hazırlayabilir: girdi ve çıktıyı yönlendirebilir, çalışma dizinini değiştirebilir, gereksiz dosyaları kapatabilir. Windows'ta ise CreateProcess tek çağrıda on parametre alır. Bu çağrı güçlüdür, ama her yeni ihtiyaç yeni bir parametre ya da bayrak demektir.

Modern eğilimler iki yönde ilerler. posix_spawn, fork ile tüm adres alanını kopyalama maliyetinden kaçınmak için süreç oluşturmayı tek adımda yapar. io_uring ise toplu çağrı arayüzüdür: tek bir kullanıcı–çekirdek geçişinde çok sayıda istek gönderilir. Her iki eğilim de maliyetin sezilebilir olması gerektiği ilkesinden doğmuştur.

14.3Sistem yapısı

Arayüz dışarıdan görünen yüzdür; yapı ise çekirdeğin içinin nasıl bölündüğünü anlatır. Hangi kod hangi adres alanında ve hangi ayrıcalıkla çalışır? Bir bileşen diğerini nasıl çağırır? Bu soruların cevabı sistemin hem hızını hem de hatalara dayanıklılığını belirler.

14.3.1Yapı seçenekleri: yalıtım ve hız

Yapı seçenekleri genellikle “monolitik”, “katmanlı”, “mikro çekirdek” gibi adlarla sayılır. Bu adların arkasında aslında birer tasarım kararı vardır. Her karar bir şey kazandırır ve bir bedel ister (Tablo 14.3).

Tablodaki satırların hepsi aynı ödünleşimin farklı noktalarıdır. Temel ödünleşim yalıtım ile performans arasındadır. Yalıtım sınırı her geçildiğinde bir bedel ödenir: bir tuzak, bir bağlam değiştirme ya da bir veri kopyası. Sınır ne kadar çoksa hatalar o kadar iyi hapsedilir, ama sistem o kadar yavaşlar.

İki yapının farkı tek bir dosya okumasında açıkça görülür (Şekil 14.8). Monolitik çekirdekte uygulama bir tuzakla çekirdeğe girer; VFS, ext4 ve disk sürücüsü birbirini doğrudan fonksiyon çağrısıyla çağırır. Mikro çekirdekte uygulamanın isteği bir ileti olarak dosya sunucusuna, oradan başka bir iletiyle disk sürücüsüne gider; cevap da aynı yoldan döner. Her ileti en az bir çekirdek geçişi ve bağlam değiştirme demektir.

Seçenekler birbirini dışlamaz. Linux monolitiktir, ama yüklenebilir modüller ve eBPF ile çalışırken genişletilebilir; çekirdek iş parçacıkları da kullanır. Windows NT ve macOS XNU mikro çekirdek fikirleriyle başlamış, ama performans için hizmetlerin çoğunu çekirdek adres alanına geri almıştır. Bu karma yapılar, saf modellerin ikisinin de pratikte bir şeyden fazla ödün verdiğini gösterir.

14.3.2Katmanlı sistemler

Katmanlı yapı, bağımlılığı tek yöne sınırlamanın en eski yoludur. Dijkstra'nın THE sistemi (1968) bu fikirle kurulmuştu. Her katman yalnız altındaki katmanın sunduğu soyutlamaları kullanır, üstündekini hiç bilmez. Tanenbaum modern bir işletim sistemi için yedi katmanlı bir tasarım önerir (Şekil 14.9).

Katmanların sırası keyfî değildir; bağımlılıklardan çıkar. Sanal bellek sayfaları diske yazdığı ve diskten okuduğu için aygıt sürücülerinin üstündedir. Dosya sistemi sayfa önbelleği için çerçeve ayırdığı için sanal belleğin üstündedir. İş parçacıkları kesme işlemeye ve bağlam değiştirmeye dayandığı için 2. katmanın üstündedir. Donanımı gizleyen 1. katman taşınabilirliği sağlar: yeni bir işlemciye taşırken öncelikle bu katman yeniden yazılır.

Bir read çağrısının katmanlardan geçişi yapıyı canlı olarak gösterir.

1. 7. katman. Uygulama read(fd, buf, n) çağırır ve tuzak sistem çağrısı işleyicisine gelir. Parametreler burada denetlenir: fd geçerli mi, tampon kullanıcı alanında mı?
2. 6. katman. Dosya sistemi (örneğin ext4) dosya ofsetini disk bloğuna çevirir; okunacak blok 4711'dir. Blok önbellekte yoksa alt katmanlardan istenir.
3. 5. katman. Sanal bellek, verinin konacağı sayfa önbelleği çerçevesini ayırır ve kullanıcı tamponunun eşlemesini doğrular.
4. 4. katman. NVMe sürücüsü okuma komutunu aygıtın kuyruğuna yazar.
5. 3. katman. Çağıran iş parçacığı G/Ç bitene kadar engellenir; çizelgeleyici başka bir iş parçacığını çalıştırır.
6. 2. katman. Aygıt işi bitirince kesme üretir. Kesme işleyicisi uyuyan iş parçacığını hazır yapar. Sonuç katmanlar boyunca yukarı döner ve read okunan bayt sayısını döndürür.

Katmanlı yapının bedeli her katman geçişinin maliyetidir. Saf katmanlı bir sistemde bir isteğin bütün katmanlardan tek tek geçmesi gerekir ve her geçiş bir fonksiyon çağrısı, bazen bir parametre kopyası ekler. Asıl zorluk ise katman sırasını seçmektir. Gerçek sistemlerde bağımlılıklar her zaman tek yönlü değildir. Sanal bellek sürücüleri kullanır, ama bir sürücü de kendi tamponları için bellek isteyebilir. Bu yüzden bugünkü sistemler katman fikrini bir düşünme aracı olarak kullanır, katı bir kural olarak değil.

14.3.3Genişletilebilir sistemler

İhtiyaçlar değiştikçe çekirdeğe yeni yetenekler eklemek gerekir. Her seferinde çekirdeği yeniden derleyip makineyi yeniden başlatmak pratik değildir. Genişletilebilir sistemlerde çekirdek temel işlevleri sağlar, yeni bileşenler ise çalışırken eklenir.

Genişletmenin en büyük sorunu güvenliktir. Üçüncü taraflar sisteme özellik ekleyebildiğinde, eklenen kodun çekirdeği bozmaması da sağlanmalıdır. Klasik yüklenebilir modül (insmod) tam yetkilidir: modüldeki bir hata çekirdeğin kendisindeki bir hatadan farksızdır ve sistemi çökertebilir. 1995'teki SPIN sistemi bu sorunu güvenli bir dille çözmeye çalışmış, eklentileri Modula-3 ile yazdırarak bellek hatalarını derleme anında engellemişti.

Linux'taki eBPF bugünkü cevaptır (Şekil 14.11). Program C ile yazılır ve clang ile BPF bayt koduna derlenir. Kullanıcı alanı bu bayt kodunu bpf() sistem çağrısıyla çekirdeğe verir. Çekirdekteki doğrulayıcı (verifier) programın bütün yollarını inceler. Döngüler sınırlı mı, her bellek erişimi güvenli mi? Program bir koşulu sağlamazsa yükleme reddedilir. Geçen program JIT derleyicisiyle yerel makine koduna çevrilir ve bir kancaya bağlanır.

eBPF kancaları bugün dört alanda kullanılır: izleme (kprobe ve tracepoint'ler), ağ (XDP ile paketlerin sürücü seviyesinde işlenmesi), güvenlik (LSM kancaları) ve Linux 6.12'den beri çizelgeleme (sched_ext). eBPF'in önemi, yalıtım ile genişletilebilirliği aynı anda sağlamasıdır. Kod çekirdek adres alanında çalıştığı için hızlıdır, doğrulayıcı sayesinde de çekirdeği çökertemez.

14.3.4Çekirdek iş parçacıkları

Çekirdeğin bazı işleri bir sistem çağrısına ya da kesmeye bağlı değildir. Bellek azaldığında sayfa geri kazanmak, günlüğü diske yazmak, kesmede yapılamayacak kadar uzun işleri bitirmek bunlara örnektir. Bu işler için çekirdek kendi iş parçacıklarını kullanır (Şekil 14.12).

Çekirdek iş parçacıkları normal iş parçacıkları gibi zamanlanır, engellenebilir ve uyuyabilir. Kesme işleyicisinde uyumak yasaktır; bu yüzden kesmede yapılamayan uzun işler bir çekirdek iş parçacığına ertelenir. Bağlam değiştirme de ucuzdur, çünkü adres alanı, yani sayfa tablosu değişmez. Linux'taki tipik örnekler şunlardır:

• kworker: ertelenmiş işleri (workqueue) yürütür.
• ksoftirqd: yumuşak kesmeleri işler; ağ paketlerinin işlenmesi gibi.
• kswapd: boş bellek azaldığında sayfa geri kazanır.
• jbd2: ext4'ün günlüğünü diske yazar.

Hepsinin atası kthreadd'dir. ps -ef çıktısında köşeli parantez içinde görünürler, örneğin [kswapd0]. Kullanıcı süreçleri çekirdek iş parçacığı oluşturamaz. Sistem çağrıları yalnız çekirdeğin zaten çalıştırdığı iş parçacıklarına iş verebilir; io_uring'in iş havuzu buna bir örnektir. Çekirdek iş parçacıkları yapıyı bir adım daha esnek hâle getirir: monolitik bir çekirdek de işini, ayrı ayrı zamanlanan bağımsız akışlara bölebilir.

14.4Tasarım ilkeleri

Yapı seçildikten sonra tasarımcı yüzlerce küçük kararla karşılaşır. Bu kararlarda tekrar tekrar işe yarayan birkaç ilke vardır. Bu ilkeler tek bir algoritma değil, bir düşünme biçimidir; aynı ilke bellek yönetiminde de dosya sisteminde de karşımıza çıkar.

14.4.1Mekanizma ve politikanın ayrılması

Bu ayrımın değeri, çekirdeği değiştirmeden farklı davranışlar elde edebilmektir. Çekirdek her durumu öngöremez. Ama iyi bir mekanizma sunarsa, durumu en iyi bilen taraf, yani uygulama ya da yönetici, politikayı kendisi seçer. Çizelgeleme bu ilkenin en açık örneğidir (Şekil 14.13).

Linux 6.12'deki sched_ext bu ilkeyi bir adım öteye taşır. Yalnız öncelikler değil, çizelgeleme politikasının tamamı bir eBPF programı olarak yüklenebilir. Çekirdek görev kuyruklarını, bağlam değiştirmeyi ve CPU'lara dağıtımı sağlar; hangi görevin ne zaman çalışacağına ise yüklenen program karar verir.

Aynı ayrım işletim sisteminin her yerinde görülür:

• Sayfalama. Mekanizma MMU ve çerçeve tahsisidir; politika hangi sayfanın çıkarılacağına karar veren kuraldır (LRU, saat).
• CPU frekansı. Mekanizma cpufreq sürücüsüdür; politika schedutil ya da powersave yöneticisidir.
• Güvenlik. Mekanizma LSM kancalarıdır; politika SELinux kurallarıdır.

14.4.2Diklik

Terim geometriden gelir: dik iki eksende bir yönde ilerlemek diğer eksendeki konumu değiştirmez. Tasarımda diklik, az sayıda kavramdan çok sayıda bileşim elde etmeyi sağlar. C dili basit bir örnektir. Bir değişkenin ömrü (static) ile türü birbirinden bağımsız seçilir: static int, static char *, static struct proc hepsi geçerlidir.

İşletim sistemlerinde en güzel örnek Linux'un clone çağrısıdır (Şekil 14.14). Yeni bir yürütme birimi oluşturulurken neyin paylaşılacağı ayrı ayrı bayraklarla seçilir. CLONE_VM adres alanını, CLONE_FS kök ve çalışma dizinini, CLONE_FILES açık dosya tablosunu, CLONE_SIGHAND sinyal işleyicilerini, CLONE_THREAD ise iş parçacığı grubunu paylaştırır.

Bayrakların hiçbiri verilmezse sonuç fork'tur: her şey kopyalanır. Hepsi verilirse sonuç pthread_create'tir: her şey paylaşılır. Süreç ve iş parçacığı böylece iki ayrı kavram değil, aynı mekanizmanın iki ucudur. Konteynerler de aynı çağrıyla, CLONE_NEWPID ve CLONE_NEWNET gibi CLONE_NEW* ad alanı bayraklarıyla kurulur.

Windows aynı soruna farklı bir dik tasarımla yaklaşır. Süreç bir kaynak kabıdır: adres alanı, tanıtıcılar ve güvenlik bilgisi süreçtedir. İş parçacığı ise çizelgeleme birimidir. İki kavram baştan ayrıdır ve her süreç bir ya da daha çok iş parçacığı içerir.

14.4.3Adlandırma: iki düzeyli adlar

Bir işletim sistemi binlerce nesneyi yönetir: dosyalar, süreçler, aygıtlar, bellek sayfaları, ağ uçları. İnsanlar bu nesnelere hatırlanabilir adlarla başvurmak ister. Sistemin içinde ise hızlı ve benzersiz bir sayı daha kullanışlıdır. Çözüm iki düzeyli adlandırmadır.

Aynı kalıp işletim sisteminin birçok yerinde tekrar eder (Tablo 14.4).

Aradaki eşlemenin en büyük kazancı, adı değiştirmeden nesneyi taşıyabilmektir. Bir web sitesi başka bir sunucuya taşındığında yalnız DNS kaydı değişir; kullanıcılar aynı adı yazmayı sürdürür. Bir sayfa diske atılıp başka bir çerçeveye geri yüklendiğinde yalnız sayfa tablosu güncellenir; program aynı sanal adresi kullanır. Tablodaki DNS satırı ilginçtir: orada eşleme iki kez yapılır. Ad önce IP adresine, IP adresi de ARP ile MAC adresine çevrilir.

14.4.4Ad çözümleme adım adım

İki düzeyli adlandırmanın bir maliyeti vardır: her ad kullanıldığında eşleme yapılmalıdır. Bir dosya yolunda bu eşleme bileşen bileşen yürür ve her bileşen disk erişimi gerektirebilir.

Yalnız dosyayı bulmak için yedi disk erişimi gerekmiştir. Bir sabit diskte her erişim milisaniyeler sürdüğü için bu yaklaşık on milisaniyelik bir gecikme demektir; dosyadan henüz tek bayt okunmamıştır. İki düzeyli adlandırmanın esnekliği ancak eşlemeler önbellekte tutulursa ucuz hâle gelir.

14.4.5Bağlama zamanı

Bir ad birçok farklı anda bağlanabilir. Bellek adresleri bunun iyi bir örneğidir (Şekil 14.17). Program yazılırken koda gömülen mutlak bir adres en erken bağlamadır. Derleme anında sabit bir yükleme adresi seçilebilir. Bağlama anında statik kütüphaneler programa eklenir. Yükleme anında yer değiştirme ve ASLR adresleri belirler. Çalışma anında ise sanal bellek, dlopen ve DNS bağlamayı son ana bırakır.

Erken bağlama basit ve hızlıdır, ama az esnektir. Program yalnız belirli bir adreste çalışır; kütüphane güncellenince program yeniden derlenmelidir. Geç bağlama daha karmaşıktır, çünkü ek bir dolaylılık ve çalışma zamanı maliyeti getirir. Karşılığında esneklik kazanılır: sayfa belleğin neresine yüklenirse yüklensin program çalışır, kütüphane güncellenince program değişmez.

İşletim sistemleri genel olarak geç bağlamayı seçer. Sanal bellek bunun en uç örneğidir: bir sayfanın fiziksel yeri her erişimde yeniden çözülür. Bu maliyet TLB sayesinde katlanılabilir düzeydedir. Geç bağlamanın bedeli ödenir, ama bedeli küçültmek için donanım yardımı alınır.

14.4.6Statik ve dinamik yapılar

Çekirdek veri yapılarının boyutu da bir tasarım kararıdır. Süreç tablosu, açık dosya tablosu ya da tampon havuzu derleme anında sabit boyutlu bir dizi olarak mı, yoksa çalışırken büyüyüp küçülen bir yapı olarak mı tutulmalı?

Eski UNIX çekirdeklerinde süreç tablosu sabit boyutlu bir diziydi ve bir süreç şöyle aranırdı:

found = 0;
for (p = &proc_table[0];
     p < &proc_table[PROC_TABLE_SIZE];
     p++) {
    if (p->proc_pid == pid) {
        found = 1;
        break;
    }
}

found sıfırlanır ve p işaretçisi tablonun ilk elemanına konur. Döngü p, tablonun sonundaki &proc_table[PROC_TABLE_SIZE] adresine ulaşana kadar sürer. Her turda girdinin proc_pid alanı aranan pid ile karşılaştırılır. Eşleşme olunca found = 1 yapılır ve break döngüden çıkar. p++ işaretçiyi bir bayt değil, bir struct proc boyu ilerletir; C'de işaretçi aritmetiği gösterilen türün boyutuyla yapılır.

Altı girdilik bir tabloda pid 42 aranıyor. Tablodaki pid'ler sırasıyla 1, 314, 0, 42, 977, 0'dır; 0 boş girdi demektir (Tablo 14.5).

Boş girdi de tek tek taranır; doğrusal aramanın bedeli budur. En kötü durumda tablonun tamamı taranır ve arama O(n) sürer. Ama küçük ve sabit bir tablo için bu basit kod yeterlidir.

Statik tablonun artıları basitlik ve öngörülebilirliktir: bellek ayırıcı gerekmez, tablo hiçbir zaman parçalanmaz. Eksisi, tablo dolunca yeni süreç oluşturulamamasıdır. Eski UNIX'te bu sınır NPROC sabitiydi. Dinamik bir yapı, örneğin bağlı liste, hash tablosu ya da Linux'taki xarray, bu sınırı kaldırır ve aramayı O(1)'e yaklaştırır. Bedeli bir bellek ayırıcı, parçalanma ve daha karmaşık kilitlemedir. Ara yol da vardır: boyutu ayarlanabilir tablolar. Linux'ta en büyük pid değeri /proc/sys/kernel/pid_max dosyasından okunur ve değiştirilebilir.

14.4.7Yukarıdan aşağı ve aşağıdan yukarı gerçekleme

Bir sistem tasarlandıktan sonra yazılmaya hangi uçtan başlanmalıdır? İki yaklaşım vardır (Şekil 14.19).

Yukarıdan aşağı (top-down) gerçeklemede önce sistem çağrısı işleyicileri yazılır. Alt katmanlar koçan (stub) olarak bırakılır. Koçan, doğru imzayla tanımlanmış ama içi boş olan ya da sabit bir değer döndüren fonksiyondur. Arayüz erken netleşir. Ama bütün sistem bitmeden gerçekçi bir test yapmak zordur, çünkü koçanlar gerçek davranışı taklit etmez.

Aşağıdan yukarı (bottom-up) gerçeklemede önce donanımı gizleyen katman, sonra kesmeler, zamanlayıcı, iş parçacıkları yazılır. Her katman bittiğinde test edilir, çünkü altındaki her şey gerçektir. Tanenbaum gerçeklemede bu yolu önerir. Tasarımın ise yukarıdan aşağı düşünülmesi gerekir: önce arayüz belirlenir, sonra o arayüzü sağlayacak katmanlar alttan üste kurulur.

14.4.8Eş zamanlı ve eş zamansız iletişim

Eş zamanlı iletişimin programlaması kolaydır. Akış sıralı okunur: istek, yanıt, sonraki satır. Bedeli, her bekleyen istek için bir iş parçacığının boşta durmasıdır. Mikro çekirdeklerde IPC genellikle eş zamanlıdır; L4 ve seL4 bu yolu izler. Gönderen yanıtı beklediği için çekirdeğin iletiyi tamponlamasına gerek kalmaz ve ileti doğrudan alıcıya aktarılabilir. Bu da IPC'yi çok hızlı yapar.

Eş zamansız iletişimde tek bir iş parçacığı binlerce isteği aynı anda yürütebilir. Ama yarış koşulları, hata yönetimi ve tamponlama zorlaşır. Bir isteğin hatası, onu gönderen kod çoktan başka bir işe geçmişken gelir. Linux'taki io_uring bu modelin güncel örneğidir. Gönderim (SQ, submission queue) ve tamamlanma (CQ, completion queue) halkaları kullanıcı alanı ile çekirdek arasında paylaşılır. Uygun ayarla, çekirdekteki bir iş parçacığı gönderim halkasını izlediği için sistem çağrısı yapılmadan bile istek gönderilebilir.

14.5Yararlı teknikler

İlkeler neyin hedefleneceğini söyler; teknikler ise hedefe nasıl varılacağını. Bu kısımdaki teknikler işletim sistemi kodunun her yerinde, çoğu zaman adı konmadan kullanılır. Her birinin kazancı ve bedeli vardır.

14.5.1Donanımı gizleme

Bir işletim sistemi birden çok işlemci mimarisinde çalışmak zorundadır. Her mimarinin başlatma kodu, yazmaç boyu ve kesme düzeni farklıdır. Bu farkların bütün koda dağılması taşınabilirliği öldürür. Çözüm, donanıma bağımlı kodu az sayıda dosyada toplamaktır. C'de bunun en eski aracı koşullu derlemedir.

İlk örnek CPU türüne göre farklı başlatma kodu seçer. config.h dosyası CPU sabitini tanımlar ve önişlemci yalnız eşleşen bloğu derlemeye bırakır.

#include "config.h"
void init(void)
{
#if (CPU == X86_64)
    /* x86-64 başlatma kodu */
#endif
#if (CPU == ARM64)
    /* ARM64 başlatma kodu */
#endif
#if (CPU == RISCV64)
    /* RISC-V başlatma kodu */
#endif
}

İkinci örnek sözcük uzunluğuna göre bir yazmaç türü seçer. 32 bitlik makinede Register bir int, 64 bitlik makinede bir long olur. Son dal bugünkü taşınabilir çözümdür: <stdint.h> içindeki uintptr_t her platformda bir işaretçiyi tutacak kadar büyük bir tamsayı türüdür.

#include "config.h"
#include <stdint.h>
#if (WORD_LENGTH == 32)
typedef int Register;
#elif (WORD_LENGTH == 64)
typedef long Register;
#else  /* bugün: taşınabilir */
typedef uintptr_t Register;
#endif
Register R0, R1, R2, R3;

Kodlar Tanenbaum'daki Pentium–UltraSPARC örneğinin güncellenmiş hâlidir. Bugünkü sistemlerde aynı fikir dizin düzeyinde uygulanır. Windows'ta donanıma bağımlı kod HAL'de (Hardware Abstraction Layer) toplanır. Linux'ta ise arch/x86, arch/arm64 ve arch/riscv gibi dizinlerdedir. Yeni bir işlemciye taşırken yalnız bu kısım yeniden yazılır.

14.5.2Dolaylılık

David Wheeler'a atfedilen söz tekniğin gücünü özetler: bilgisayar bilimindeki her sorun, bir dolaylılık düzeyi daha ile çözülebilir. Klavye girdisi iyi bir örnektir. Klavye bir tuşa basıldığında karakter göndermez; tuşun konumunu bildiren bir tarama kodu (scan code) gönderir. Bu kodu karaktere çeviren, işletim sistemindeki tuş eşlem tablosudur (keymap).

Ek adımın kazancı esnekliktir, bedeli ise bir tablo okumasıdır. Bu bedel çoğu zaman önemsizdir, ama sıcak bir yolda birikebilir. İşletim sistemlerinde dolaylılık her yerdedir: sanal bellekte sayfa tablosu, dosya tanımlayıcılarında süreç dosya tablosu, sembolik bağlarda başka bir yol, dosya sistemlerinde i-node, sürücülerde aygıt sınıfları. İki düzeyli adlandırma ve geç bağlama da birer dolaylılık örneğidir.

14.5.3Yeniden kullanım ve yeniden girişlilik

Büyük bir sistemde aynı türden sorunlar farklı yerlerde tekrar eder. Boş disk bloklarını, boş bellek çerçevelerini ve kullanılmayan PID'leri izlemek aynı sorundur: büyük bir kümede hangi elemanların boş olduğunu tutmak. Bu üçü için tek bir biteşlem (bitmap) modülü yazmak, üç ayrı kod yazmaktan iyidir. Linux bu ilkeyle ortak veri yapıları sunar: list.h'deki çift bağlı liste, kırmızı-siyah ağaç ve xarray çekirdeğin her yerinde kullanılır.

Yeniden kullanılacak kodun bir koşulu sağlaması gerekir: aynı anda birden çok yerden çağrılabilmelidir.

Çekirdekte yeniden girişlilik iki yoldan gerekir. Birincisi kesmelerdir: bir fonksiyon çalışırken kesme gelir ve kesme işleyicisi aynı fonksiyonu çağırabilir. İkincisi çok çekirdektir: başka bir CPU çekirdeği aynı kodu aynı anda çalıştırabilir. Standart C kütüphanesindeki strtok bu koşulu sağlamayan klasik bir örnektir.

char *strtok(char *s, const char *d)
{
    static char *last; /* paylaşılan durum! */
    ...
}

/* yeniden girişli sürüm: durum çağıranda */
char *strtok_r(char *s, const char *d,
               char **saveptr);

strtok bir dizgiyi ayraçlara göre parçalara böler. İlk çağrıda dizgi verilir; sonraki çağrılarda NULL verilir ve fonksiyon kaldığı yerden sürer. Kaldığı yeri içindeki static char *last değişkeninde saklar. Bu değişken yığında değil, bütün iş parçacıklarının paylaştığı veri kesimindedir. Yeniden girişli sürüm strtok_r ise aynı bilgiyi çağıranın verdiği saveptr işaretçisinde tutar.

14.5.4Kod izleme: strtok

Sorunun nasıl ortaya çıktığını görmek için strtok'un sadeleştirilmiş bir sürümü izlenebilir. my_strtok tek karakterlik bir ayraç alır ve durumunu static char *kalan değişkeninde tutar.

char *my_strtok(char *s, char ayr) {
    static char *kalan;     /* herkes paylaşır! */
    if (s) kalan = s;
    if (!kalan || !*kalan) return NULL;
    char *bas = kalan;
    while (*kalan && *kalan != ayr) kalan++;
    if (*kalan) *kalan++ = '\0';
    return bas;
}
/* main:   my_strtok(a, ',')  a = "ali,veli" */
/* kesme:  my_strtok(b, ';')  b = "x;y"      */
/* main:   my_strtok(NULL, ',')              */

Fonksiyon satır satır şöyle çalışır. s verilmişse kalan onun başına konur. kalan NULL ise ya da dizginin sonunu gösteriyorsa parça kalmamıştır ve NULL döner. Aksi hâlde parçanın başı bas'ta saklanır. while döngüsü kalan'ı ayraca ya da dizgi sonuna kadar ilerletir. Ayraç bulunduysa yerine '\0' yazılır ve kalan bir sonraki karaktere geçer. Fonksiyon bas'ı döndürür; dönen dizgi yazılan '\0''da biter.

Senaryo şöyledir. main, a = "ali,veli" dizgisini virgülle ayıklıyor. İlk parçayı aldıktan hemen sonra bir kesme geliyor ve kesme işleyicisi aynı fonksiyonla b = "x;y" dizgisini noktalı virgülle ayıklıyor. Ardından main kaldığı yerden sürüyor (Tablo 14.6).

• İlk çağrı. kalan = a olur. Döngü a[3]'teki virgüle kadar ilerler; virgülün yerine '\0' yazılır ve kalan a[4]'e, yani “veli”nin başına geçer. Dönüş "ali"'dir.
• Kesme. İşleyicinin çağrısı s = b ile gelir ve paylaşılan kalan'ın üzerine yazar. Noktalı virgül '\0' olur, kalan b[2]'yi gösterir, dönüş "x"'tir. main'in kaldığı yer kaybolmuştur.
• main sürer. main NULL geçer ve fonksiyonun hâlâ a üzerinde olduğunu varsayar. Ama kalan b[2]'yi gösterir. Döngü dizgi sonuna kadar ilerler; ayraç yoktur, kalan b[3]'te kalır. Dönüş "y"'dir; beklenen ise "veli"'ydi.

Hata nadiren ve zamanlamaya bağlı olarak görülür. Kesme tam iki çağrı arasına denk gelmezse program doğru çalışır. Bu tür hataları testle yakalamak bu yüzden zordur. Kök neden açıktır: çağrılar arasındaki durum paylaşılan bir static değişkende tutulur. Çözüm de açıktır: strtok_r(s, d, &kalan) gibi durumu çağırana taşımak. O zaman her çağıranın kendi kalan'ı olur ve kesme main'in durumuna dokunamaz.

14.5.5Kaba kuvvet ve önce hata denetimi

Elli girişlik bir tabloda doğrusal arama, bir hash tablosundan hem daha hızlı hem de daha hatasız olabilir. Hash fonksiyonunun hesabı, çakışma zincirleri ve yeniden boyutlandırma küçük bir tabloda kazandırdığından fazlasını harcar. Karmaşık algoritmaya ancak n büyükse ya da kod sık çalışan bir yoldaysa gerek vardır. Sıralama da benzerdir: küçük dizilerde ekleme sıralaması, büyük dizilerde birleştirme ya da öbek sıralaması uygundur.

İkinci teknik hata denetiminin yeriyle ilgilidir. Bir sistem çağrısı işleyicisi kullanıcıdan bir boyut ve bir tampon adresi alıyor; bir kilit ve bellek de gerekiyor. Kötü sıralama şöyledir:

lock(&tbl_lock);
buf = kmalloc(n, GFP_KERNEL);
if (n > MAX || !access_ok(u, n)) {
    kfree(buf);
    unlock(&tbl_lock);
    return -EINVAL;
}

Kod önce kilidi alır, sonra belleği ayırır, ancak ondan sonra parametrelerin geçerli olup olmadığına bakar. Parametre hatalıysa aldığı her şeyi ters sırayla geri vermek zorundadır: kfree, unlock, sonra hata kodu. Bu kod bir de kmalloc'un başarısız olma durumunu hiç denetlemiyor. İyi sıralama ise şöyledir:

if (n > MAX || !access_ok(u, n))
    return -EINVAL; /* önce denetle */
buf = kmalloc(n, GFP_KERNEL);
if (!buf)
    return -ENOMEM;
lock(&tbl_lock);
...

Önce parametreler denetlenir; hatalıysa hiçbir kaynak alınmadan -EINVAL döner. Ardından bellek ayrılır ve ayırmanın başarısı denetlenir. Kilit en son alınır. Hata yolunda geri alınacak bir şey kalmaz. Gerçek çekirdeklerde en sık görülen hatalardan biri, bir hata yolunda unlock'un unutulmasıdır. Önce hata denetimi bu hata sınıfını ortadan kaldırır.

14.6Performans

Her işletim sistemi hızlı olmak ister. Ama hız ancak doğruluk sağlandıktan sonra anlamlıdır ve her hızlandırma kodu daha karmaşık yapar. Bu kısım önce neyin hızlandırılacağına nasıl karar verileceğini, sonra en sık kullanılan teknikleri ele alır.

14.6.1Neden yavaş, neyi hızlandırmalı?

Donanım on yıllar içinde binlerce kat hızlandı, ama kullanıcının hissettiği hız aynı oranda artmadı. Artışın önemli bir kısmını yazılımın büyümesi tüketti. Bunun üç nedeni vardır. Birincisi özellik şişkinliğidir: her sürüm yeni özellik ekler, eskisini çıkaramaz. İkincisi geriye uyumluluk katmanlarıdır. Üçüncüsü güvenlik önlemleridir. Spectre ve Meltdown açıklarına karşı eklenen yamalar, örneğin çekirdek ve kullanıcı sayfa tablolarının ayrılması, her sistem çağrısının maliyetini artırdı. Genellik uğruna eklenen dolaylılık da her katmanda biraz zaman alır.

Neyin hızlandırılacağına ölçüm karar verir. Donald Knuth'un sözü bu konuda sıkça anılır: erken optimizasyon tüm kötülüklerin anasıdır. Önce doğru, sonra hızlı kod yazılır. Hızlandırma yalnız ölçümle darboğaz olduğu gösterilen kısımlara uygulanır. “İyi yeterlidir” ilkesi de buraya bağlanır: %5'lik bir kazanç için kodu iki kat karmaşıklaştırmak çoğu zaman değmez. Linux'ta ölçme araçları perf, eBPF tabanlı bpftrace ve alev grafikleridir.

Bir profilin nasıl okunacağını basit bir hesap gösterir (Şekil 14.23).

Bu hesabın genel biçimine Amdahl yasası denir.

Örnekteki değerler formüle uyar: p = 0,7 ve k = 2 için S = 1 / (0,3 + 0,35) ≈ 1,54; p = 0,3 için S = 1 / (0,7 + 0,15) ≈ 1,18. f sonsuz hızlı olsa bile hızlanma 1 / 0,3 ≈ 3,33 katı geçemez. Yasa, hızlandırma emeğinin yaygın durum üzerine harcanması gerektiğini sayısal olarak gösterir.

Ölçüm sonrasında başvurulan klasik teknikler beş tanedir: uzay-zaman ödünleşimi, önbellekleme, ipuçları, yerelliği kullanmak ve yaygın durumu hızlandırmak.

14.6.2Uzay-zaman ödünleşimi: bit sayma

Klasik örnek bir bayttaki 1 bitlerinin sayılmasıdır. Bu işlem bellek ayırıcılarının biteşlemlerinde ve izin maskelerinde sık yapılır. İlk sürüm her biti bir döngüyle tek tek sınar:

#define BYTE_SIZE 8
int bit_count(int byte)
{
    int i, count = 0;
    for (i = 0; i < BYTE_SIZE; i++)
        if ((byte >> i) & 1)
            count++;
    return count;
}

Döngü i'yi 0'dan 7'ye kadar sayar. Her turda bayt i bit sağa kaydırılır ve en düşük bit 1 ile maskelenir: (byte >> i) & 1. Sonuç 1 ise sayaç artar. Örnek bayt 0xB7'dir; ondalık 183, ikili 1011 0111 (Tablo 14.7).

Bit 3 ve bit 6 sıfırdır; bu turlarda dal alınmaz ve sayaç değişmez. Döngü sekiz kez döner ve 6 döndürür. Bellek kullanımı yok denecek kadar azdır. Ama bayt başına sekiz tur, her turda bir kaydırma, bir maskeleme, bir karşılaştırma ve bir dal vardır. Dal tahmini başarısız olduğunda işlemcinin boru hattı boşaltılır ve bu ek maliyet getirir.

Daha hızlı iki sürüm yer harcayarak zaman kazanır:

/* (b) makro: döngü yok */
#define bit_count(b) ((b&1) + ((b>>1)&1) + \
    ((b>>2)&1) + ... + ((b>>7)&1))

/* (c) tablo: 256 bayt */
char bits[256] =
    {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ...};
#define bit_count(b) (int) bits[b]

(b) makrosu döngüyü açar: sekiz terim doğrudan toplanır. Döngü ve dal yoktur, ama yaklaşık 24 komut gerekir. (c) ise 256 girişlik bir tablo kullanır. Tablonun i. girdisi, i'nin ikili gösterimindeki 1 sayısıdır. Bit sayma tek bir bellek okumasına iner (Şekil 14.25). Yöntemlerin karşılaştırması Tablo 14.8'de verilmiştir.

Tablonun son satırı bugünün gerçeğidir. x86-64 ve ARM64 işlemcilerinde 1 bitlerini sayan özel bir komut vardır ve derleyici __builtin_popcount çağrısını bu komuta çevirir. Yine de uzay-zaman ödünleşimi önemini korur, çünkü aynı fikir donanımın yardım etmediği yüzlerce başka hesapta kullanılır.

14.6.3Kod izleme: yarım bayt tablosu

256 baytlık tablo ile döngü arasında bir orta nokta vardır. Bir bayt iki yarım bayta (nibble) bölünürse 16 girişlik bir tablo yeter. Tablo da elle yazılmak yerine bir döngüyle kurulabilir:

char yarim[16];          /* 16 bayt */
void tablo_kur(void) {
    yarim[0] = 0;
    for (int i = 1; i < 16; i++)
        yarim[i] = (i & 1) + yarim[i >> 1];
}
int bit_say(unsigned char b) {
    return yarim[b & 0x0F] + yarim[b >> 4];
}

tablo_kur fonksiyonunun dayandığı gözlem şudur. i'nin 1 bitleri sayısı, en düşük bitinin değeri ile i >> 1'in 1 bitleri sayısının toplamıdır. i >> 1 her zaman i'den küçüktür; bu yüzden döngü küçükten büyüğe ilerlerken o değer çoktan hesaplanmıştır. Bu bir dinamik programlama yinelemesidir.

Tablo hazır olunca bit_say baytı iki yarıya ayırır. b & 0x0F alt dört biti, b >> 4 üst dört biti verir. İki tablo değeri toplanır. Döngü ve dal yoktur (Tablo 14.9).

0xB7 için iki bellek okuması ve bir toplama yeter; döngülü sürüm aynı bayt için sekiz tur dönmüştü. Yarım bayt tablosu 16 bayt yer kaplar, 256'lık tablonun on altıda biri kadar. Karşılığında bir okuma ve bir toplama fazladır. Aynı soruya, ne kadar yer harcanacağına göre birkaç farklı cevap verilebildiği görülür.

14.6.4Uzay-zaman ödünleşimi: renk paleti

Ödünleşim ters yönde de işler: biraz zaman harcayarak büyük ölçüde yer kazanılabilir. Renk paleti bunun klasik örneğidir (Şekil 14.27).

Bir görüntüde her piksel için doğrudan kırmızı, yeşil ve mavi değerleri saklanabilir. Bu piksel başına 3 bayttır. Görüntüde en fazla 256 farklı renk kullanılıyorsa başka bir yol vardır. Kullanılan renkler bir palet tablosunda toplanır ve her piksel için yalnız 1 baytlık bir indis saklanır. Görüntü gösterilirken her indis paletten gerçek renge çevrilir.

Kazanılan yerin bedeli iki türlüdür. Zaman bedeli, her piksel gösterilirken yapılan tablo bakışıdır. Kısıt bedeli ise en fazla 256 renk sınırıdır; fotoğraf gibi binlerce rengi olan bir görüntü bu biçime kayıpsız sığmaz. GIF ve PNG-8 bu yöntemi kullanır; GIF ayrıca LZW ile sıkıştırır. Paletin kendisi 768 bayttır ve görüntü büyüdükçe toplam içindeki payı önemsizleşir.

14.6.5Önbelleğe almak

Genel kural basittir: aynı sonuç tekrar tekrar hesaplanıyorsa saklanır. Ad çözümleme bunun için biçilmiş kaftandır. /usr/ast/mbox yolunu önbelleksiz bulmak yedi disk okuması istiyordu. Çekirdek çözdüğü her yolun sonucunu bir tabloda tutarsa aynı yol ikinci kez sorulduğunda diske hiç gidilmez (Tablo 14.11).

Üç durum ayırt edilir. Önbellek yokken /usr/ast/mbox'ı bulmak için kök i-node'u, kök dizini, /usr i-node'u, /usr dizini, /usr/ast i-node'u ve /usr/ast dizini okunur. Bu altı disk okumasıdır; dosyanın kendi i-node'u ile yedi olur. Önbellekte tam yol varsa tek bir bellek araması yeter ve disk erişimi sıfırdır. Önbellekte yalnız /usr/ast varsa arama oradan sürer: kısmi isabet de kazançtır.

Linux'ta bu iş birkaç önbellekle yapılır. Dizin girdisi önbelleği (dcache, dentry cache) yol bileşenlerini i-node'lara eşler. i-node önbelleği i-node'ların kendisini, sayfa önbelleği ise dosya içeriğini tutar. Linux'ta boş RAM'in çoğu zaman “dolu” görünmesinin nedeni budur: kullanılmayan bellek bu önbelleklere verilir ve gerektiğinde geri alınır.

Önbelleğin bedeli tutarlılıktır. Bir dosya silinir ya da yeniden adlandırılırsa ona ait kayıt geçersiz kılınmalıdır; yoksa önbellek var olmayan bir dosyayı gösterir. Bu yük, önbellekteki değerin her zaman doğru olması şartından gelir. İşletim sisteminde önbellekler her katmandadır: TLB, CPU önbellekleri, sayfa önbelleği, dcache, ARP ve DNS önbellekleri.

14.6.6Kod izleme: yol önbelleği

Kısmi isabeti de kullanan bir yol çözümleyici birkaç satırla yazılabilir. bil[] yolun bileşenlerini, n bileşen sayısını tutar. Fonksiyon önbellekteki en uzun öneki bulur ve yalnız kalan bileşenleri diskten çözer.

/* bil[]: "usr","bal","tez.tex"; n = 3 */
int cozumle(char *bil[], int n) {
    int k = n, ino = KOK, okuma = 0;
    while (k > 0 && !onbellekte(bil, k, &ino))
        k--;              /* en uzun önek */
    for (int j = k; j < n; j++) {
        ino = dizinde_ara(ino, bil[j]);
        okuma += 2;       /* i-node + blok */
        onbellege_ekle(bil, j + 1, ino);
    }
    return ino;
}

Fonksiyonun iki aşaması vardır. Birinci aşamada k, n'den başlayıp azalır. onbellekte(bil, k, &ino), ilk k bileşenden oluşan yolun önbellekte olup olmadığına bakar; varsa i-node numarasını ino'ya yazar. Döngü ilk isabette ya da k 0'a inince durur. k 0'a inerse ino başlangıç değeri olan kök i-node'unda (KOK = 1) kalır. İkinci aşamada kalan her bileşen için dizinde_ara çağrılır. Bu çağrı dizinin i-node'unu ve dizin bloğunu okur; bu yüzden okuma 2 artar. Bulunan sonuç onbellege_ekle ile önbelleğe eklenir.

Önbellekte başlangıçta beş yol vardır: /usr (6), /usr/ast (26), /usr/ast/mbox (60), /usr/bal (45) ve /usr/bal/paper.ps (85). Sırayla üç arama yapılıyor (Tablo 14.12).

• İlk arama. Tam yol /usr/bal/tez.tex önbellekte yoktur, k 2'ye iner. /usr/bal önbellektedir: ino = 45. Kökten başlamaya gerek kalmamış, iki bileşen bedavaya gelmiştir. Kalan tek bileşen için 45'in i-node'u ve dizin bloğu okunur: tez.tex → 131. Sonuç önbelleğe eklenir.
• Aynı yol yeniden. Tam yol artık önbellektedir. Birinci döngü hemen durur, ikinci döngü hiç dönmez. Disk okuması 0'dır.
• /etc/passwd. Ne tam yol ne de /etc önbellektedir; k 0'a iner ve çözüm kök i-node'undan başlar. Kök i-node'u ve kök dizin bloğu okunur: etc → 14; /etc önbelleğe girer. Ardından /etc i-node'u ve dizin bloğu: passwd → 212. Toplam 4 okuma.

Önbelleksiz yolda bileşen başına iki okuma gerekir; en uzun önek önbellekteyse yalnız kalan bileşenler için ödeme yapılır. En kötü durum, hiçbir önekin önbellekte olmadığı durumdur ve maliyet bileşen sayısıyla doğru orantılıdır. Linux'ta bu önbellek dcache'tir ve bileşenleri ayrı ayrı tutar; mantık ise aynıdır. Kodun saydığı okumalar dosyanın kendi i-node'unu içermez; fonksiyon yalnız i-node numarasını döndürür.

14.6.7İpuçları

İpucu önbelleğe benzer, ama aradaki fark önemlidir. Önbellekteki değer her zaman doğru olmalıdır; bu yüzden kaynak değiştiğinde önbellek güncellenmek zorundadır ve bu tutarlılık yükü getirir. İpucunda böyle bir yük yoktur. İpucu yanlış çıkarsa sistem bunu kullanım anında fark eder ve yavaş yola döner (Şekil 14.29).

Dağıtık bir dosya sistemi örneği tekniği açıklar. İstemci, bir dosyanın hangi sunucuda olduğunu bir ipucu olarak tutar. Dosya bir sunucudan diğerine taşınabilir ve istemcinin bundan haberi olmayabilir. İstemci önce ipucundaki B sunucusuna sorar. B dosyayı gerçekten tutuyorsa iş bitmiştir. Tutmuyorsa istemci dizin hizmetine başvurur, dosyanın yeni yerini öğrenir ve ipucunu günceller. Dosya taşındığında hiçbir istemciye haber vermek gerekmez.

Diğer örnekler:

• Web'de yönlendirme önbelleği. Bir adresin taşındığı yer hatırlanır; yanlışsa sunucu yeniden yönlendirir.
• Dal tahmini. İşlemci dalın yönünü tahmin eder ve o yoldan çalışmaya başlar; tahmin yanlışsa sonuçları atar.
• madvise(MADV_SEQUENTIAL). Uygulama çekirdeğe bir bellek bölgesini sırayla okuyacağını bildirir. Çekirdek daha agresif önden okuma yapar. İpucu yanlışsa yalnız performans düşer, doğruluk bozulmaz.

14.6.8Yerelliği kullanmak

Zamansal yerellik önbelleğin temelidir: yakın zamanda kullanılan şey tutulursa bir sonraki istek büyük olasılıkla isabet eder. Uzamsal yerellik ise önden okumanın ve büyük sayfaların temelidir: bir blok istendiğinde ardındaki birkaç blok da getirilir.

Yerelliği kullanmanın bir yolu, birlikte kullanılan verileri yan yana koymaktır (Şekil 14.30). BSD'nin hızlı dosya sistemi (FFS) diski silindir gruplarına, ext4 ise blok gruplarına böler. Bir dosyanın i-node'u ile veri blokları aynı gruba konur; böylece i-node'u okuduktan sonra veriye ulaşmak için diskin kolu uzağa gitmez. Aynı ilke işlemcide de geçerlidir. Bir iş parçacığı hep aynı CPU çekirdeğinde zamanlanırsa o çekirdeğin L1 ve L2 önbellekleri “sıcak” kalır. NUMA makinelerinde bellek, iş parçacığının çalıştığı düğümden ayrılır.

14.6.9Yaygın durumu hızlandırmak: futex

Butler Lampson'ın sistem tasarımı üzerine verdiği öğütlerden biri şudur: yaygın durum hızlı, nadir durum doğru olmalıdır. Amdahl yasası bunun nedenini gösterir; kazanç en çok zaman alan kısmı hızlandırmaktan gelir. Kilitler bu ilkenin en güzel örneğidir.

Bir kilidi almak için her seferinde çekirdeğe girmek pahalıdır: bir sistem çağrısı, mod geçişi ve kuyruk işlemleri. Oysa ölçümler, kilitlerin büyük çoğunluğunun çekişmesiz alındığını gösterir. Kilidi isteyen iş parçacığı çoğu zaman tektir. Yaygın durum buysa hızlandırılması gereken de odur.

Kilit sözcüğü üzerinde atomik karşılaştır-değiştir (CAS, compare-and-swap) işlemi kullanılır. CAS bir bellek sözcüğünü, beklenen değere eşitse yeni değerle tek bir bölünmez adımda değiştirir ve başarılı olup olmadığını bildirir. İki iş parçacığının kilidi sırayla istediği bir senaryo dört adımda izlenir (Tablo 14.13).

• Hızlı yol. A, CAS ile 0'ı 1 yapar. Çekirdeğe hiç girilmez; işlem birkaç nanosaniye sürer.
• Yavaş yol. B de kilidi ister; kilit sözcüğü 0 olmadığı için CAS başarısız olur. B değeri 2 yapar, yani “bekleyen var” işaretini koyar, ve futex(FUTEX_WAIT) ile çekirdekte uyur. Çekirdeğe yalnız burada girilir.
• Bırakma. A kilidi bırakırken sözcüğü 0 yapar ve eski değere bakar. Eski değer 2 ise futex(FUTEX_WAKE) çağırır ve B uyanıp kilidi alır. Eski değer 1 olsaydı hiç çağrı yapmazdı.

Çekişmesiz bir kilit alma ve bırakma işlemi böylece hiç sistem çağrısı yapmadan biter. Çekirdek yalnız gerçekten bekleme gerektiğinde devreye girer. 1, 2 değerlerinin ayrımı da yaygın durum ilkesinin parçasıdır: kimse beklemiyorsa bırakırken bile çekirdeğe gidilmez.

Aynı ilkenin başka örnekleri de vardır. Sistem çağrılarının sık kullanılanları için çekirdekte kısa bir hızlı yol bulunur. clock_gettime gibi bazı çağrılar vDSO sayesinde çekirdeğe hiç girmeden, kullanıcı alanına eşlenmiş bir sayfadan okunur. TLB isabeti de aynı mantıktadır: adres çevirisinin yaygın durumu tablo yürüyüşü olmadan biter.

14.7Proje yönetimi

Bir işletim sistemi yüzlerce, bazen binlerce kişinin yıllarca süren emeğidir. Bu ölçekte teknik kararlar kadar insanların nasıl birlikte çalıştığı da sonucu belirler. Fred Brooks'un IBM OS/360 projesinden çıkardığı dersler bugün de geçerlidir.

14.7.1Efsanevi adam-ay ve Brooks yasası

Adam-ay yanıltıcı bir birimdir, çünkü işin kişiler arasında serbestçe bölünebildiğini varsayar. 12 adam-aylık bir iş, 12 kişiyle 1 ayda bitmez. Kişiler birbirleriyle eşgüdüm kurmak zorundadır ve iletişim yolu sayısı ekip büyüdükçe karesel artar.

Her yeni kişi herkesle eşgüdüm kurmak zorundadır: toplantılar, belgeler ve arayüz anlaşmaları artar. Gecikmiş bir projeye eklenen kişinin bir de eğitilmesi gerekir. Onu eğitecek olanlar da projeyi zaten bilen, en değerli kişilerdir. Kısa vadede eklenen her kişi ekibin toplam verimini düşürür. Brooks yasası bu iki etkinin birleşimidir.

Brooks, OS/360 deneyimine dayanarak bir zaman dağılımı da önerir: zamanın 1/3'ü planlamaya, 1/6'sı kodlamaya, 1/4'ü modül testine, 1/4'ü sistem testine. 12 aylık bir projede bu planlamaya 4, kodlamaya 2, modül testine 3 ve sistem testine 3 ay demektir. Kod yazmak işin yalnız altıda biridir; zamanın yarısı teste gider.

14.7.2Takım yapısı, deneyim ve gümüş kurşun

İletişim yükünü azaltmanın yolu, ekibi küçük ve güçlü takımlara bölmektir. Harlan Mills'in önerdiği ve Brooks'un benimsediği cerrah ekibi modelinde baş programcı tasarlar ve kodlar; diğerleri ona destek olur: biri yardımcıdır, biri belgeleri yönetir, biri araçları hazırlar. Kavramsal bütünlük birkaç kişide kalır. Brooks'a göre bir sistemin kavramsal bütünlüğü, tasarımının en önemli niteliğidir.

Linux'un geliştirme düzeni bu fikrin bugünkü, büyük ölçekli bir biçimidir (Şekil 14.33). Binlerce katkıcının yamaları önce sürücü ve alt alan bakımcılarına, oradan alt sistem bakımcılarına, en sonunda Linus Torvalds'a akar. Her düzeyde kavramsal bütünlüğü koruyan, sayıca az bir grup vardır.

Deneyimin rolü de büyüktür. İyi bir programcı ortalamanın kat kat üzerinde verimlidir; bu fark ekipteki kişi sayısından daha belirleyici olabilir. Brooks'un iki uyarısı buraya bağlanır. Birincisi “birini atmayı planlayın” sözüdür: ilk sürüm büyük olasılıkla atılacaktır, bu yüzden baştan bir prototip olarak düşünülmelidir. İkincisi ikinci sistem etkisidir: ilk sistemini başarıyla bitiren bir tasarımcı, ikincisine ilkinde bıraktığı bütün süsleri ekler ve sistem şişer.

Brooks 1986'daki “No Silver Bullet” makalesinde daha genel bir sonuca varır: yazılım geliştirmede verimi tek başına on kat artıracak bir “gümüş kurşun” yoktur. Karmaşıklığı ikiye ayırır. Arızi karmaşıklık (accidental complexity) araçlardan ve dillerden gelir; daha iyi derleyiciler, editörler ve diller onu azaltır. Özsel karmaşıklık (essential complexity) ise sorunun kendisindedir ve hiçbir araç onu ortadan kaldıramaz. Bir işletim sisteminin eş zamanlılığı, güvenlik gereksinimleri ve uyumluluk yükü özseldir. Yapay zekâ destekli kodlama araçları da bu tabloyu değiştirmez: kod yazmayı hızlandırırlar, ama tasarım sorumluluğunu kaldırmazlar.

14.8Test ve hata ayıklama

Brooks'un zaman dağılımında testin payı yarıdır. İşletim sistemlerinde bu pay belki daha da büyüktür, çünkü çekirdekteki bir hata bütün sistemi etkiler. Bu kısım çekirdek kodunun neden zor test edildiğini, hangi test türlerinin ve araçların kullanıldığını ve bir hatanın hangi yollarla bulunduğunu anlatır.

14.8.1İşletim sistemi kodunu test etmek neden zor?

Bir uygulamada başarısız olan test çoğu zaman yalnız bir hata mesajı üretir. Çekirdekte ise beş etken işi zorlaştırır.

• Ayrıcalıklı mod. Hatayı yakalayacak bir üst katman yoktur. Çekirdekte tek bir hatalı işaretçi bir oops ya da panic üretir ve bütün sistemi, test düzeneğiyle birlikte düşürür.
• Eş zamanlılık. Kesmeler, ön alım ve çok çekirdek sayısız iç içe geçme üretir. Bir hata ancak nadir bir zamanlamada ortaya çıkar.
• Belirlenimsizlik. Bazı hatalar her çalıştırmada tekrarlanmaz. Bunlara şakayla heisenbug denir: printk eklemek bile zamanlamayı değiştirip hatayı saklayabilir.
• Çeşitlilik. Binlerce sürücü, birçok mimari (x86-64, arm64, RISC-V) ve on binlerce Kconfig seçeneği vardır. Bütün bileşimleri denemek mümkün değildir.
• Uzun ömürlü durum. Bellek sızıntıları ve sayaç taşmaları ancak sistem günlerce çalıştıktan sonra görünür.

Test türleri bu zorluklara göre katmanlanır (Tablo 14.14).

Çekirdekte başarısız bir test çoğu zaman makinenin kendisini kaybetmek demektir. Bu yüzden testler sanal makinelerde koşulur; her testin bir zaman aşımı vardır ve makine çökerse otomatik olarak yeniden başlatılır.

14.8.2Çekirdek test piramidi

Linux'taki test araçları bir piramit oluşturur (Şekil 14.34). Tabanda çok sayıda hızlı birim testi, tepede az sayıda yavaş ama gerçekçi sistem testi vardır.

• KUnit. Testler çekirdekle birlikte derlenir ve iç işlevleri doğrudan çağırır. UML (User-Mode Linux) ya da QEMU'da saniyeler içinde koşar; kunit.py run komutuyla başlatılır. Çıktı KTAP biçimindedir.
• kselftest. tools/testing/selftests altındadır. Çalışan çekirdeğin sistem çağrılarını ve cgroup, bpf, ağ gibi arayüzlerini dışarıdan, kullanıcı alanından sınar; make kselftest ile koşulur.
• LTP. Linux Test Project binlerce testten oluşur: sistem çağrılarının anlamı, POSIX uyumu, dosya sistemi ve stres senaryoları. Dağıtımlar yeni sürümden önce LTP koşar.

KernelCI bu testleri sürekli entegrasyon içinde birçok ağaç ve dalda, çok sayıda mimari ve Kconfig bileşiminde koşar. QEMU'nun yanında gerçek kartlardan oluşan laboratuvarlar da kullanılır. Bir gerileme bulunduğunda KernelCI onu otomatik olarak ikili aramayla bir commit'e kadar daraltır. 0-day bot ve syzbot benzer sürekli test hizmetleridir.

14.8.3Dinamik denetleyiciler

Bir test ancak hatanın bir belirtisini görebiliyorsa onu yakalar. Bellek hatalarının çoğu ise belirti vermez: dizinin bir bayt ötesine yazmak çoğu zaman başka bir nesneyi sessizce bozar ve sistem çok sonra, ilgisiz bir yerde çöker. Dinamik denetleyiciler bu sessiz hataları ilk geçersiz erişim anında görünür kılar (Tablo 14.15).

KASAN'ın tipik bir raporu iki satırla başlar:

BUG: KASAN: slab-use-after-free in mydrv_release+0x54/0x90
Read of size 8 at addr ffff888012a4c010 by task cat/1432

İlk satır hatanın türünü (slab-use-after-free: serbest bırakılmış bir slab nesnesine erişim) ve yerini verir: mydrv_release fonksiyonunun 0x54 baytındaki komut. İkinci satır erişimin boyunu, adresini ve hangi görevin yaptığını söyler: cat komutunun 1432 numaralı süreci 8 baytlık bir okuma yapmıştır. Raporun devamında nesnenin nerede ayrıldığını ve nerede serbest bırakıldığını gösteren iki yığın izi gelir; nesnenin ömrü bunlardan çıkarılır.

Denetleyicilerin bedeli yüksektir. KASAN çekirdeği birkaç kat yavaşlatır ve belleğin yaklaşık sekizde birini gölgeye ayırır. KCSAN ve lockdep de belirgin yük getirir. Bu yüzden geliştirme, test ve sürekli entegrasyon çekirdeklerinde açılırlar. Üretim sistemlerinde ise örneklemeli ve düşük maliyetli KFENCE kullanılabilir: yalnız ara sıra seçilen ayırmaları denetler.

14.8.4Kod izleme: KASAN gölge belleği

KASAN'ın her erişimden önce yaptığı denetim, sadeleştirilmiş hâliyle şöyledir:

/* 8 baytlık bölge başına 1 gölge bayt:
   0: hepsi geçerli, 1..7: ilk k bayt,
   < 0: kırmızı bölge ya da serbest */
void kasan_denetle(void *a, int boy) {
    int8_t s = *(int8_t *)(((uintptr_t)a >> 3)
                           + GOLGE_OFS);
    if (s == 0) return;            /* hızlı yol */
    if (((uintptr_t)a & 7) + boy - 1 >= s)
        rapor(a, s);
}
/* p = kmalloc(13); p[3]; p[12]; p[13]; */
/* kfree(p); p[0]; */

Fonksiyon önce gölge baytı bulur. Adres 3 bit sağa kaydırılır, yani 8'e bölünür; sonuca sabit bir ofset eklenir. Gölge baytı 0 ise bölgenin tamamı geçerlidir ve denetim tek bir karşılaştırmayla biter. Bu hızlı yoldur ve erişimlerin büyük çoğunluğu buradan geçer. Değer sıfır değilse erişimin bölge içindeki son baytının konumu hesaplanır: (a & 7) + boy - 1. Bu konum gölge değerine eşit ya da büyükse erişim geçerli baytların dışına taşıyordur ve rapor üretilir. Negatif bir gölge değeri her konumda bu koşulu sağlar.

Senaryoda p = kmalloc(13) çağrılıyor. Çekirdeğin ayırıcısı 13 baytlık istek için 16 baytlık bir yuva verir. Gölge şöyle kurulur: ilk 8 bayt tamamen geçerlidir (0), ikinci bölgenin ilk 13 − 8 = 5 baytı geçerlidir (5), arkasındaki bölge kırmızı bölgedir (0xfc, yani −4). Ardından sırayla p[3], p[12] ve p[13] okunuyor; sonra kfree(p) ve p[0] geliyor (Tablo 14.16).

p[12], 13 baytlık nesnenin son geçerli baytıdır ve sorunsuz geçer. p[13] ise dizinin bir bayt ötesidir. Gerçek bir çekirdekte bu bayt yuvanın dolgusuna ya da başka bir nesneye ait olabilir; KASAN olmadan hata sessiz kalırdı. KASAN onu ilk geçersiz erişimde raporlar.

kfree(p) nesnenin gölgesini 0xfb (serbest) olarak işaretler. Yuva bir süre karantinada bekletilir; hemen yeniden kullanılırsa yeni nesnenin gölgesi geçerli olur ve eski işaretçiyle yapılan erişim gizlenir. p[0] okunduğunda gölge −5'tir ve rapor, nesnenin ayrıldığı ve serbest bırakıldığı yerlerin yığın izleriyle birlikte gelir.

14.8.5Kod izleme: lockdep kilit sırası çizgesi

Kilitlenmelerin en sık nedeni, iki kilidin farklı yerlerde ters sırayla alınmasıdır. Bir iş parçacığı A'yı tutarken B'yi, diğeri B'yi tutarken A'yı isterse ikisi sonsuza kadar bekleyebilir. lockdep bu durumu kilitlenme yaşanmadan önce bulur.

void lock_acquire(task *t, int L) {
    for (int i = 0; i < t->n; i++) {
        int H = t->tutulan[i];
        if (yol_var(L, H))   /* L → … → H */
            uyar("olası kilitlenme", H, L);
        kenar_ekle(H, L);    /* H, L'den önce */
    }
    t->tutulan[t->n++] = L;
}
void lock_release(task *t) { t->n--; }
/* T1: A,B   T2: B,C   T3: C,A */

lock_acquire, görev L kilidini alırken çağrılır. Görevin o an tuttuğu her H kilidi için iki şey yapılır. Önce çizgede L'den H'ye bir yol olup olmadığına bakılır. Böyle bir yol varsa bir yerde L tutulurken (dolaylı yoldan) H alınmıştır ve şimdi tersi yapılıyor demektir: uyarı verilir. Sonra H → L kenarı eklenir. En sonda L tutulan kilitler listesine konur. lock_release listeden son kilidi çıkarır.

Üç görev farklı zamanlarda çalışıyor: T1 önce A'yı sonra B'yi, T2 önce B'yi sonra C'yi, T3 önce C'yi sonra A'yı alıyor (Tablo 14.17).

Üç görev hiç aynı anda çalışmamıştır ve gerçek bir kilitlenme olmamıştır. Ama bir gün T1 A'yı, T2 B'yi, T3 C'yi aynı anda tutarsa her biri bir sonrakinin kilidini bekler: T1 B'yi, T2 C'yi, T3 A'yı. Bu dairesel bekleme bir kilitlenmedir. lockdep bunu tek bir çalıştırmada, olmadan önce gösterir. Gücü buradan gelir: zamanlamaya bağlı, nadir bir hatayı belirlenimci bir çizge denetimine çevirir.

14.8.6Fuzzing: syzkaller döngüsü

Linux çekirdeğinin en verimli hata bulucusu syzkaller'dır (Şekil 14.37). Döngü altı adımda işler.

1. Açıklamalar. syzkaller sistem çağrılarının imzalarını syzlang açıklamalarından bilir: hangi argüman dosya tanıtıcısı, hangisi bayrak, hangisi işaretçidir. Korpus başta boştur ya da tohum programlardan oluşur.
2. Üretim ve mutasyon. Üretici korpustan bir program seçip değiştirir ya da yenisini üretir; örneğin openat → ioctl → mmap → close. Argümanlar türlerine uygun seçildiği için çağrılar hemen EINVAL ile reddedilmez.
3. Çalıştırma. Program, KASAN, KCSAN ve lockdep açık bir test çekirdeğiyle çalışan QEMU sanal makinelerinde koşar. VM çökse bile ana makine etkilenmez; syz-manager VM'i yeniden başlatır.
4. Kapsam. KCOV, çekirdekte geçilen temel blokları (PC değerlerini) kaydeder. Bu geri bildirim rastgele denemeyi yönlendirilmiş bir aramaya çevirir.
5. Korpus. Yeni bir kod yolu açan program korpusa eklenir ve sonraki mutasyonların tohumu olur. Döngü her VM'de saniyede yüzlerce programla durmadan döner.
6. Rapor. Bir çökme ya da KASAN raporu gelirse syzkaller programı yeniden üretir, en küçük hâline indirger ve çoğu zaman bir C yeniden üreticisi çıkarır. syzbot bunu otomatik olarak geliştiricilere bildirir.

Fuzzer ile denetleyici birbirini tamamlar. Fuzzer tek başına yalnız çökmeleri görür. Bellek bozan ama çökmeyen bir hata, fuzzer'ın gözünde başarılı bir çalıştırmadır. KASAN gibi denetleyiciler bu sessiz bozulmaları ilk geçersiz erişimde görünür kılar ve onları çökmeye çevirir. syzkaller'ın KASAN açık bir çekirdekle çalıştırılmasının nedeni budur.

14.8.7Gözlem ve iz sürme araçları

Bir hata bulunduktan sonra nedenini anlamak için sistemin içini görmek gerekir. Linux bunun için katman katman araçlar sunar (Tablo 14.18).

bpftrace ile tek satırlık bir program, sistemde hangi sürecin hangi dosyayı açtığını canlı olarak gösterir:

# hangi süreç hangi dosyayı açıyor?
bpftrace -e 'tracepoint:syscalls:sys_enter_openat { printf("%s %s\n", comm, str(args.filename)); }'

Program sys_enter_openat tracepoint'ine bağlanır. openat sistem çağrısı her başladığında çalışır ve sürecin adını (comm) ile açılmak istenen dosya adını yazdırır. Çekirdeği yeniden derlemek ya da makineyi yeniden başlatmak gerekmez; program doğrulayıcıdan geçtiği için çalışan bir üretim sisteminde bile güvenle kullanılabilir.

Araç seçiminde genel kural, önce gözlem sonra tahmindir: log ve izler hipotez kurmayı sağlar. Ama ağır bir printk zamanlamayı değiştirip bir yarış hatasını gizleyebilir. Bu yüzden düşük yüklü izleyiciler, ftrace ve eBPF, tercih edilir.

14.8.8QEMU ve gdb ile çekirdek hata ayıklama

Bazen izler yetmez ve çekirdeği adım adım çalıştırmak gerekir. Bunun en kolay yolu çekirdeği QEMU'da çalıştırıp dışarıdan gdb ile bağlanmaktır.

# 1. terminal: -s → gdb sunucusu :1234
#             -S → CPU başta durur
qemu-system-x86_64 -kernel bzImage \
  -append "console=ttyS0 nokaslr" \
  -nographic -s -S
# 2. terminal
gdb vmlinux
(gdb) target remote :1234
(gdb) hbreak start_kernel
(gdb) continue
(gdb) bt
(gdb) lx-dmesg  # çekirdek gdb betiği

İlk terminalde QEMU çekirdeği başlatır. -s seçeneği 1234 numaralı portta bir gdb sunucusu açar; -S ise CPU'yu en baştan durdurur, böylece daha ilk komuttan önce bağlanılabilir. console=ttyS0 çekirdeğin çıktısını seri hatta, yani terminale yönlendirir. nokaslr çekirdek adres alanı rastgeleleştirmesini kapatır; böylece gdb'deki semboller gerçek adreslerle eşleşir. İkinci terminalde gdb, sembol bilgisi içeren sıkıştırılmamış vmlinux dosyasıyla açılır (CONFIG_DEBUG_INFO). target remote :1234 QEMU'ya bağlanır. hbreak start_kernel çekirdeğin C'deki giriş noktasına bir donanım kesme noktası koyar. continue ile oraya kadar çalışılır, bt çağrı yığınını gösterir. lx-dmesg, çekirdeğin kendi gdb betiklerinden biridir ve log tamponunu yazdırır. Aynı oturum gerçek donanımda seri hat üzerinden kgdb ile de kurulabilir (kgdboc=ttyS0,115200).

Gerçek bir hatada ilk bakılan şey oops mesajıdır:

BUG: kernel NULL pointer dereference,
     address: 0000000000000010
Oops: 0000 [#1] PREEMPT SMP NOPTI
CPU: 2 PID: 1432 Comm: cat
Tainted: G           O  6.12.0
RIP: 0010:mydrv_read+0x2a/0x80 [mydrv]
Call Trace:
 vfs_read+0xa4/0x2f0
 ksys_read+0x63/0xe0
 do_syscall_64+0x82/0x170

Mesaj satır satır okunur. İlk satır hatanın türünü verir: 0x10 adresinde bir NULL işaretçi erişimi. Bu tipik olarak NULL bir yapı işaretçisi üzerinden, yapının başından 16 bayt ötedeki bir alana erişmektir. CPU: 2 PID: 1432 Comm: cat hatayı hangi çekirdekte, hangi sürecin tetiklediğini söyler. Tainted: G O çekirdeğin “lekeli” olduğunu gösterir; O ağaç dışı bir modülün yüklü olduğu anlamına gelir. RIP: mydrv_read+0x2a/0x80 hatalı komutun yeridir: mydrv_read fonksiyonunun başından 0x2a bayt ötesi; fonksiyonun boyu 0x80'dir. scripts/faddr2line bu bilgiden kaynak dosyadaki satırı bulur. Çağrı izi aşağıdan yukarı okunur: do_syscall_64 → ksys_read → vfs_read → sürücü. Yani bir read sistem çağrısı VFS üzerinden sürücüye gelmiş ve sürücüde çökmüştür.

Oops yalnız o süreci öldürür; sistem çalışmayı sürdürebilir, ama artık güvenilir değildir. panic_on_oops=1 ayarı oops'u doğrudan panic'e çevirir. Windows dünyasında bunun karşılığı WinDbg'dir: çekirdek modunda ağ, USB ya da sanal makine üzerinden hata ayıklanır ve mavi ekran dökümleri !analyze -v ile incelenir. Driver Verifier (verifier.exe) sürücüleri özel havuz, IRQL ve kaynak sızıntısı denetimleriyle zorlayarak hataları erkenden yakalar.

14.8.9Regresyon avı: git bisect

Bir hata v6.11'de yokken v6.12'de ortaya çıkmışsa, onu getiren değişikliği bulmanın sistemli bir yolu vardır. İki sürüm arasındaki commit'ler bir dizi oluşturur ve dizinin bir noktasından sonra hata vardır. Bu noktayı bulmak bir ikili arama sorusudur.

git bisect start
git bisect bad v6.12
git bisect good v6.11
# #500: derle, başlat, sına
git bisect bad
git bisect good   # #250
git bisect good   # #375
git bisect bad    # #437
git bisect run ./sina.sh
git bisect reset

Komutlar şu işi yapar. git bisect start aramayı başlatır. bad v6.12 ve good v6.11 iki ucu bildirir. Git aradaki commit'lerin ortasındakini çalışma dizinine çıkarır. Her adımda çekirdek derlenir, başlatılır ve sınanır; sonuca göre git bisect bad ya da git bisect good yazılır. Bir noktadan sonra sınama bir betiğe bırakılabilir: git bisect run ./sina.sh kalan adımları kendisi yürütür. Bitince git bisect reset başlangıç dalına döner.

Her yanıt aday sayısını yarıya indirir: 1000 → 500 → 250 → 125 → 62 → … Bu yüzden gereken test sayısı commit sayısının logaritmasıyla büyür.

1000 commit için ⌈log₂ 1000⌉ = 10'dur, çünkü 2⁹ = 512 < 1000 ≤ 1024 = 2¹⁰. Bir milyon commit olsaydı bile yalnız ⌈log₂ 10⁶⌉ = 20 test gerekirdi. 12 000 commit için sınır 14'tür: 2¹³ = 8192 < 12 000 ≤ 16 384 = 2¹⁴.

git bisect run betiğin çıkış koduna bakar. Betik 0 ile biterse commit iyi, 1 ile 127 arasında (125 hariç) bir kodla biterse kötü sayılır. 125 özel bir anlama gelir: “bu commit sınanamaz, atla”. Örneğin o commit'te çekirdek derlenmiyorsa betik 125 döndürür ve git komşu bir commit'i dener. Performans gerilemelerinde ölçüm gürültülü olduğu için betik birkaç ölçümün ortalamasını almalıdır.

14.9İşletim sistemlerinde eğilimler

İşletim sistemleri uzun ömürlü olduğu için bugünkü kararlar on yıllar sonraki donanımı ve uygulamaları da karşılamalıdır. Bu kısım, tasarımı bugün en çok etkileyen eğilimleri toplar.

14.9.1Genel tablo

Tanenbaum'ın eski baskılarında ayrı birer eğilim sayılan ağ işlemleri, paralel ve dağıtık sistemler ve çoklu ortam artık her sistemin olağan parçasıdır. Bu yüzden ayrı birer eğilim olarak değil, tablodaki ilgili satırların içinde düşünülür.

Sanallaştırma satırı yalıtım–performans ödünleşiminin yeniden çizilmesidir. Çok kiracılı bir bulutta farklı müşterilerin kodu aynı makinede çalışır ve aralarındaki asıl sınır artık işletim sistemi çekirdeği değil, hipervizördür. Konteynerler aynı çekirdeği paylaştığı için hafif ve hızlıdır, ama çekirdekteki bir açık bütün konteynerleri etkiler. Firecracker gibi mikro-VM'ler her iş yüküne ayrı ve çok küçük bir sanal makine vererek iki dünyanın arasında bir nokta seçer.

Pille çalışan sistemlerde amaç enerjidir. DVFS (dynamic voltage and frequency scaling) işlemcinin gerilimini ve frekansını yüke göre değiştirir. “Hızla bitir ve uyu” stratejisinde iş en yüksek hızda bitirilir ve işlemci hemen derin uyku durumuna geçirilir. Android Doze, ekran kapalıyken uygulamaların arka plan işlerini toplu pencerelere erteler.

14.9.2Çok çekirdek ve geniş adres alanları

Bugün sunucularda yuva başına 128–192 çekirdek, telefonlarda ise büyük ve küçük çekirdeklerin karıştığı (big.LITTLE) yongalar vardır. Tek bir büyük çekirdek kilidi bu ölçekte işlemez: bütün çekirdekler aynı kilidi beklerse eklenen her çekirdek boşa gider. Gereken araçlar ince taneli kilitler, okuyucuların hiç kilit almadığı RCU (read-copy-update) ve her çekirdeğe ayrı veri yapılarıdır. Heterojen çekirdeklerde çizelgeleyici bir de hangi işin hangi tür çekirdeğe gideceğine karar verir.

64 bitlik adresler de yeni olanaklar açar (Şekil 14.39).

Bu genişlikte bir adres alanında bütün dosyaları belleğe eşlemek (mmap) ya da bütün süreçlerin tek bir adres alanını paylaştığı sistemler kurmak mümkün olur. Bedeli daha derin bir sayfa tablosu yürüyüşüdür: 5 düzeyli tabloda bir TLB ıskası beş bellek okuması ister. Geniş adres alanı TLB üzerindeki baskıyı da artırır.

14.9.3Rust, eBPF ve unikernel'ler

Son eğilim, çekirdeğin hangi dille ve hangi biçimde yazıldığıyla ilgilidir. Üç gelişme öne çıkar.

Rust ile çekirdek. Linux 6.1 (Aralık 2022) ile Rust desteği ana dala girdi; ardından ilk Rust sürücüleri geldi. Amaç, serbest bırakma sonrası kullanım ve taşma gibi bellek hatalarını derleme anında önlemektir. Çekirdek güvenlik açıklarının önemli bir kısmı bu türden hatalardır. Rust'ın sahiplik ve ödünç alma kuralları bir nesnenin ömrünü derleyicinin denetlemesini sağlar. Windows çekirdeğinde de Rust ile yazılmış bileşenler vardır. Bu, KASAN'ın çalışma anında yakaladığı hataları daha kod derlenirken engellemek demektir.

eBPF. Doğrulanmış küçük programlarla çekirdeği yeniden derlemeden genişletmek; izleme, ağ (XDP), güvenlik ve çizelgeleme (sched_ext) alanlarında kullanılır. Genişletilebilir sistem fikri, eBPF ile ilk kez geniş ölçekte üretime girmiştir.

Unikernel. Exokernel'in kütüphane işletim sistemi (libOS) fikrinin bulut sürümüdür. Tek bir uygulama, ona gereken işletim sistemi kütüphaneleriyle birlikte tek bir görüntü olarak derlenir ve hipervizör üzerinde tek adres alanında çalışır (Şekil 14.40). MirageOS ve Unikraft bu yaklaşımın örnekleridir.

Unikernel'in kazancı küçüklük ve hızdır. Görüntü yalnız gereken kodu içerdiği için saldırı yüzeyi küçüktür ve açılış milisaniyeler sürer. Kullanıcı–çekirdek geçişi olmadığı için sistem çağrıları sıradan fonksiyon çağrılarına dönüşür. Tek uygulamalı mikro hizmetler için uygundur. Bedeli, hata ayıklamanın zorlaşması ve birden çok uygulamanın aynı görüntüde çalıştırılamamasıdır. Yalıtımı ise artık hipervizör sağlar.

14.10Özet

• İşletim sistemi tasarımını sekiz etken zorlaştırır: devasa boyut, eş zamanlılık, düşmanca kullanıcılar, yalıtıma rağmen paylaşım, uzun ömür, genellik, taşınabilirlik ve geriye dönük uyumluluk.
• Bir işletim sisteminin dört temel hedefi soyutlamalar tanımlamak, bu soyutlamalar üzerinde ilkel işlemler (sistem çağrıları) sağlamak, yalıtım sağlamak ve donanımı yönetmektir.
• İyi bir arayüz basit, bütün ve verimlidir. Çekirdekte az ve genel çağrı, kütüphanede kolaylık fonksiyonları bulunur: altı exec fonksiyonu tek bir execve'ye dönüşür. Sistem çağrısı sayısı seL4'te ≈ 12, Linux'ta ≈ 460'tır.
• Algoritmik kodda akışı program, olay güdümlü kodda dış olaylar belirler. Olay döngüsü engelleyen bir get_message etrafında kurulur; uzun bir işleyici bütün arayüzü dondurur. UNIX'te her şey bir dosya, Windows'ta her şey bir nesnedir.
• Sistem yapısındaki temel ödünleşim yalıtım ile performans arasındadır. Monolitik çekirdek hızlıdır ama hata yalıtımı yoktur; mikro çekirdek hataları hapseder ama her istekte IPC öder. Katman sırası bağımlılıklardan çıkar. eBPF, doğrulayıcı sayesinde güvenli genişletme sağlar.
• Mekanizma bir işin nasıl yapılacağını, politika neyin yapılacağını belirler; sched_ext politikanın tamamını eBPF programı olarak yükler. Diklik ayrı kavramları bağımsız birleştirir: clone bayrakları fork ile pthread_create arasındaki her bileşimi verir.
• İki düzeyli adlandırma harici adı dahili sayıya eşler ve nesneyi adını değiştirmeden taşımayı sağlar. Önbelleksiz /usr/ast/mbox çözümlemesi 7 disk okuması ister. İşletim sistemleri genellikle geç bağlamayı seçer.
• Statik tablolar basittir ama dolunca büyüyemez; dinamik yapılar esnektir ama ayırıcı ve kilitleme ister. Gerçekleme aşağıdan yukarı, tasarım yukarıdan aşağı yapılır. Eş zamanlı iletişim kolay, eş zamansız iletişim ölçeklenebilirdir.
• Teknikler: donanıma bağımlı kodu az sayıda dosyada toplamak, dolaylılık, yeniden kullanım, yeniden girişlilik (paylaşılan static durum yok; strtok_r), kaba kuvvet ve önce hata denetimi.
• Hızlandırılacak kısmı ölçüm belirler; Amdahl yasası kazancın sınırını verir. Uzay-zaman ödünleşimi (bit sayma tablosu, renk paleti), önbellek (her zaman doğru), ipucu (yanlış olabilir, kullanmadan önce doğrulanır), yerellik ve yaygın durumu hızlandırma (futex) klasik tekniklerdir.
• Brooks yasası: gecikmiş projeye eleman eklemek onu daha da geciktirir; iletişim yolu sayısı n(n − 1)/2 ile karesel artar. Kod yazmak işin yalnız altıda biridir ve gümüş kurşun yoktur.
• Çekirdek testi KUnit, kselftest ve LTP ile katmanlanır. KASAN, KCSAN, UBSAN, lockdep ve kmemleak sessiz hataları görünür kılar; syzkaller bunları kapsam güdümlü fuzzing ile tetikler. ftrace, perf ve eBPF gözlem, QEMU ve gdb adım adım hata ayıklama, git bisect ise en çok ⌈log₂ n⌉ testle regresyon avı sağlar.
• Eğilimler: sanallaştırma ve bulut, çok çekirdek, geniş adres alanları, enerji verimliliği, gömülü sistemler, Rust, eBPF ve unikernel'ler.

14.11Kavram listesi

• soyutlama abstraction
• ilkel işlem primitive
• yalıtım isolation
• sistem çağrısı system call
• basitlik, bütünlük, verimlilik simplicity, completeness, efficiency
• olay güdümlü kod event-driven code
• olay döngüsü event loop
• monolitik çekirdek monolithic kernel
• mikro çekirdek microkernel
• katmanlı yapı layered system
• exokernel exokernel
• genişletilebilir sistem extensible system
• eBPF extended Berkeley Packet Filter
• çekirdek iş parçacığı kernel thread
• politika / mekanizma policy / mechanism
• diklik orthogonality
• harici ad, dahili ad external name, internal name
• bağlama zamanı binding time
• koçan stub
• eş zamanlı / eş zamansız iletişim synchronous / asynchronous communication
• koşullu derleme conditional compilation
• dolaylılık indirection
• yeniden girişlilik reentrancy
• kaba kuvvet brute force
• uzay-zaman ödünleşimi space-time trade-off
• önbellek cache
• ipucu hint
• yerellik locality
• futex fast userspace mutex
• Brooks yasası Brooks's law
• gölge bellek shadow memory
• fuzzing fuzzing
• regresyon regression
• unikernel unikernel

14.12Kendini Dene

1. Olay döngüsündeki işleyiciler bir sayaç tutuyor: KEY 1, CLICK 10 ekliyor; TIMER sayaç 10'dan büyükse onu sıfırlıyor. Olaylar CLICK CLICK TIMER KEY KEY KEY TIMER QUIT sırasıyla gelirse döngü bitince sayaç kaçtır?

   Cevap

   3. Sayaç sırasıyla 10, 20, 0 (20 > 10), 1, 2, 3 olur. Son TIMER'da 3 > 10 sağlanmadığı için sayaç değişmez. QUIT'te get_message 0 döndürür ve döngü biter.

2. Yol önbelleğinde /var → 30 kaydı var, başka ilgili kayıt yok. cozumle() fonksiyonu /var/log/syslog için kaç disk okuması sayar? Önbellek tamamen boş olsaydı kaç sayardı? Dosyanın kendi i-node'u da okunursa toplamlar nedir?

   Cevap

   /var önbellekteyken k = 1'de durulur; log ve syslog diskten çözülür: 2 + 2 = 4 okuma. Önbellek boşken k 0'a iner ve üç bileşen kökten çözülür: 6 okuma. Dosyanın i-node'u da sayılırsa 5 ve 7 olur.

3. yarim tablosuyla bit_say(0xE3) hangi iki girdiyi okur ve ne döndürür?

   Cevap

   0xE3 = 1110 0011. Alt yarı 3, üst yarı E'dir. yarim[3] = 2 ve yarim[E] = 3; sonuç 5. Döngülü sürüm aynı sonuca sekiz turda ulaşır.

4. 1920 × 1080 bir görüntü (a) piksel başına 24 bit RGB ile, (b) piksel başına 4 bitlik indis ve 16 renklik palet (renk başına 3 bayt) ile saklanıyor. Boyutlar ve oran nedir?

   Cevap

   (a) 1920 × 1080 × 3 = 6 220 800 bayt. (b) İki piksel bir bayta sığar: 1920 × 1080 / 2 = 1 036 800 bayt, palet 16 × 3 = 48 bayt; toplam 1 036 848 bayt. Oran yaklaşık 6'dır. Bedeli, her piksel için tablo bakışı ve 16 renk sınırıdır.

5. Bir programın süresinin %40'ı sikistir() fonksiyonunda geçiyor. Bir seçenek bu fonksiyonu 4 kat, diğer seçenek programın geri kalanını 2 kat hızlandırmak. Hangisi daha çok kazandırır?

   Cevap

   İkisi de eşittir. Birincide süre 60 + 40/4 = 70, ikincide 40 + 60/2 = 70 olur; hızlanma iki durumda da 100 / 70 ≈ 1,43 kat. Amdahl yasasıyla: 1 / (0,6 + 0,1) = 1 / (0,4 + 0,3) ≈ 1,43. Hangi kısmın ne kadar hızlanabildiği, payı kadar önemlidir.

6. 12 kişilik ekip gecikmiş bir projeye 4 kişi daha ekliyor. İletişim yolu sayısı kaçtan kaça çıkar? Kişi sayısındaki artışla karşılaştırıldığında ne görülür?

   Cevap

   12 · 11 / 2 = 66 yoldan 16 · 15 / 2 = 120 yola çıkar: yaklaşık 1,82 kat. Kişi sayısı ise yalnız 16 / 12 ≈ 1,33 kat artmıştır. Yeni gelenlerin eğitimi de mevcut ekibin zamanından yer; Brooks yasasının iki nedeni budur.

7. git bisect için #0 iyi, #64 kötü; ilk kötü commit #45. Git her adımda ⌊(iyi + kötü) / 2⌋'yi sınatıyor. Hangi commit'ler sınanır? 5000 commit'lik bir aralıkta en çok kaç test gerekir?

   Cevap

   #32 iyi, #48 kötü, #40 iyi, #44 iyi, #46 kötü, #45 kötü: 6 test, ⌈log₂ 64⌉ = 6. 5000 commit için ⌈log₂ 5000⌉ = 13, çünkü 2¹² = 4096 < 5000 ≤ 8192 = 2¹³.

8. p = kmalloc(20) 32 baytlık bir yuva veriyor. KASAN gölge baytları ne olur? 4 baytlık p[8], p[16] ve p[18] okumalarından hangisi raporlanır?

   Cevap

   Gölge: 0, 0, 4, 0xfc. İlk iki bölge tamamen geçerli, üçüncü bölgenin ilk 20 − 16 = 4 baytı geçerli, dördüncü kırmızı bölgedir. p[8]: gölge 0, hızlı yol. p[16]: (16 & 7) + 4 − 1 = 3, 3 ≥ 4 değil, geçerli. p[18]: 2 + 4 − 1 = 5 ≥ 4, rapor: okuma 18–21. baytları kapsar ve 20 ile 21 nesnenin dışındadır.

9. Dört görev farklı zamanlarda çalışıyor: T1 önce A sonra B'yi, T2 önce C sonra D'yi, T3 önce B sonra C'yi, T4 önce D sonra A'yı alıyor. lockdep hangi anda uyarır? T4 önce A sonra D'yi alsaydı ne olurdu?

   Cevap

   Kenarlar sırasıyla A → B, C → D, B → C olur. T4 D'yi tutarken A'yı istediğinde A → B → C → D yolu vardır ve yeni D → A kenarı bir çevrim kapatır: uyarı T4'ün A'yı alışındadır. T4 önce A sonra D'yi alsaydı A → D kenarı eklenirdi; çevrim oluşmaz ve uyarı verilmezdi.

10. Aşağıdakilerden hangileri mekanizma, hangileri politikadır? (a) cpufreq sürücüsünün işlemci frekansını değiştirmesi, (b) schedutil yöneticisinin frekansı yüke göre seçmesi, (c) LRU yer değiştirme kuralı, (d) MMU'nun TLB ıskasında sayfa tablosunu yürümesi, (e) SELinux kuralları.

    Cevap

    Mekanizma: (a) ve (d); işin nasıl yapılacağını belirlerler ve hangi kararın verileceğinden bağımsızdırlar. Politika: (b), (c) ve (e); neyin yapılacağına karar verirler ve aynı mekanizma üzerinde değiştirilebilirler.

14.13İleri okuma

• B. W. Lampson, “Hints for Computer System Design”, ACM SOSP, 1983: arayüz, gerçekleme ve performans üzerine kısa öğütlerin klasik derlemesidir; “yaygın durumu hızlı yap” ve ipucu fikri buradan gelir.
• F. P. Brooks Jr., The Mythical Man-Month, 20. yıl baskısı, 1995: Brooks yasası, cerrah ekibi, ikinci sistem etkisi ve “No Silver Bullet” makalesi tek kitapta toplanmıştır.
• U. Drepper, “Futexes Are Tricky”, 2011: futex tabanlı kilidin adım adım nasıl doğru yazılacağını, 0–1–2 durumlarının nedenini ve sık yapılan yanlışları anlatır.
• Linux çekirdek belgeleri, docs.kernel.org/dev-tools/: KASAN, KCSAN, UBSAN, kmemleak, KUnit ve kselftest'in nasıl açılıp kullanıldığını çekirdeğin kendi belgesinde verir.

14.14Kaynaklar

1. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı (2014) / 5. baskı (2023), Pearson — Bölüm 12: Operating System Design.
2. B. W. Lampson, “Hints for Computer System Design”, ACM SOSP, 1983 (ve 2020 güncellemesi “Hints and Principles for Computer System Design”).
3. F. P. Brooks Jr., The Mythical Man-Month: Essays on Software Engineering, 20. yıl baskısı, Addison-Wesley, 1995 — “No Silver Bullet” (1986) dahil.
4. J. H. Saltzer, M. F. Kaashoek, Principles of Computer System Design: An Introduction, Morgan Kaufmann, 2009.
5. D. R. Engler, M. F. Kaashoek, J. O'Toole, “Exokernel: An Operating System Architecture for Application-Level Resource Management”, SOSP 1995.
6. G. Klein vd., “seL4: Formal Verification of an OS Kernel”, SOSP 2009; J. N. Herder vd., MINIX 3 güvenilirlik çalışmaları.
7. Linux çekirdeği belgeleri: Rust (docs.kernel.org/rust), BPF ve sched_ext; H. Franke vd., “Fuss, Futexes and Furwocks”, 2002.