Bölüm 9: Sanal Bellek

9.1Sanal belleğe giriş

Sayfalamalı bir sistemde süreç, adres alanını sabit boyutlu sayfalar hâlinde görür ve her sayfa fiziksel bellekte bir çerçeveye yerleşir. Klasik sayfalama sürecin bütün sayfalarının bellekte olmasını bekler. Sanal bellek bu koşulu kaldırır: sayfaların bir kısmı bellekte, bir kısmı diskte durabilir ve süreç yine çalışır. Bu kesim önce sayfalamanın gerekli parçalarını kısaca hatırlatır, sonra koşulu kaldırmanın neden değerli olduğunu anlatır.

9.1.1Ön bilgi: sayfalama ve TLB

Sürecin ürettiği her adres bir sanal adrestir (virtual address). Donanım bu adresi iki parçaya ayırır: üst bitler sayfa numarası p, alt bitler sayfa içindeki konum, yani ofset d'dir. 4 KB'lık sayfada ofset 12 bittir. Sayfa tablosu p'yi bir çerçeve numarası f'ye çevirir; ofset hiç değişmeden fiziksel adrese taşınır. Fiziksel adres böylece f ile d'nin yan yana yazılmasıdır.

Sayfa tablosu bellekte durduğu için her erişimde tabloya gitmek bellek trafiğini ikiye katlardı. Bunu TLB (translation lookaside buffer) önler. TLB, son kullanılan sayfa–çerçeve eşlemelerini tutan küçük ve çok hızlı bir önbellektir. Programlar kısa sürede az sayıda sayfaya dokunduğu için isabet oranı %99'un üstündedir. Iskada donanım sayfa tablosunu yürür; x86-64'te bu yürüyüş 4 ya da 5 düzeylidir (Şekil 9.1).

Sayfa tablosunun her girdisi çerçeve numarasının yanında birkaç bit taşır. Geçerli (present) biti sayfanın bellekte olup olmadığını söyler. R (referans, x86'da accessed) biti sayfaya erişildiğinde donanımca 1 yapılır. M (değişti, x86'da dirty) biti sayfaya yazıldığında 1 olur. Koruma bitleri de yazma iznini (R/W), kullanıcı erişimini (U/S) ve kod çalıştırma yasağını (NX) belirler. R ve M bitleri yer değiştirme algoritmalarının hammaddesidir. Geçerli biti 0 olan bir girdiye erişim ise bir sayfa hatası doğurur. Sayfa bellekte değilse yedekleme deposundan getirilir; gerekirse seçilen bir kurban sayfanın yerine yüklenir.

Farklı adreslerle çeviriyi, TLB isabet ve ıskalarını, sayfa hatalarını denemek için Sayfalama ve Adres Çevirisi Simülatörü kullanılabilir.

9.1.2Neden sanal bellek?

Gerçek programlara bakıldığında bir programın tamamının nadiren kullanıldığı görülür. Hata durumlarını işleyen kod çoğu çalıştırmada hiç yürümez. Seyrek kullanılan seçenekler ve özellikler bellekte boşuna yer kaplar. Programcılar dizileri en kötü duruma göre büyük ayırır: 100×100'lük bir tablo çoğu zaman 10×10'u kadar dolar. Programın tamamı gerekli olduğunda bile hepsi aynı anda gerekmez.

Eski çözüm takastı (swapping): sürecin tamamı belleğe getirilir ya da bütünüyle diske götürülür. Büyük bir süreçte bu çok pahalıdır, çünkü süreç birkaç sayfasını kullanacak olsa bile bütün görüntüsü taşınır.

Bu ayrımın kazançları hem programcıya hem sisteme yansır:

• Program fiziksel bellekle sınırlı değildir. 16 GB'lık bir makinede sanal boyutu 40 GB'ı aşan süreçler çalışabilir.
• Her süreç daha az çerçeve kullanır, dolayısıyla aynı bellekte daha çok süreç tutulur. Çok programlama derecesi ve CPU kullanımı artar.
• Yükleme ve takas için daha az G/Ç gerekir: yalnız kullanılan sayfalar okunur. Programlar daha hızlı başlar.
• Sayfa paylaşımı kolaylaşır; aynı çerçeve birden çok sürecin tablosunda görünebilir.

Sanal bellekten önce fiziksel bellekten büyük programlar elle parçalara bölünürdü. Bu eski katman (overlay) yönteminde programcı, programı birbirinin yerine yüklenecek parçalara ayırmak ve yüklemeyi kendisi yönetmek zorundaydı. Sanal bellekle aynı iş işletim sistemince sayfa düzeyinde ve otomatik olarak yapılır.

9.1.3Sanal adres alanı

Sürecin bellekteki mantıksal görünümüne sanal adres alanı denir. Süreç kendini 0'dan başlayan bitişik adreslerde görür. Fiziksel bellek ise dağınık çerçevelerden oluşur ve iki görünüm arasındaki eşlemeyi MMU yapar.

Alanın düzeni bütün Unix benzeri sistemlerde aynı mantığı izler (Şekil 9.3). En altta kod (text), onun üstünde ilk değerli veri ve sıfırla başlayan bss bölümü vardır. Öbek (heap) bunların üstünden yukarı doğru büyür. Yığın (stack) en yüksek kullanıcı adresinden aşağı doğru büyür. Arada paylaşımlı kütüphanelerin ve mmap bölgelerinin eşlendiği alan durur. Geri kalan kullanılmayan aralıklar boşluktur (hole).

Boşluğun çerçeve harcamaması önemlidir. Yığın ya da öbek yeni bir sayfaya taşınana kadar o sayfa için fiziksel bellek ayrılmaz. Böyle, büyük kısmı kullanılmayan bir adres alanına seyrek adres alanı (sparse address space) denir. Sayfa tablosu da boşluklar için girdi tutmak zorunda değildir; çok düzeyli tabloda kullanılmayan alt tablolar hiç ayrılmaz.

Bugünkü x86-64 işlemciler 48 bitlik sanal adres kullanır; bunun yarısı, 128 TiB, kullanıcıya ayrılır. 5 düzeyli sayfalamayla sanal adres 57 bite çıkar. Adres alanı düzeni rastgeleleştirme (ASLR, address space layout randomization) bölgelerin yerini her çalıştırmada rastgele kaydırır. Böylece saldırgan bir kütüphanenin ya da yığının adresini önceden bilemez.

Sanal bellek iki yolla kurulabilir. Bugün evrensel olan yol talebe bağlı sayfalamadır. Değişken boyutlu kesimlerle çalışan talebe bağlı kesimleme ise tarihsel bir yaklaşımdır; Burroughs bilgisayarları ve OS/2 bunu kullanmıştı. Linux'ta bir sürecin bölgeleri cat /proc/self/maps ile görülebilir. Çıktının her satırı bir sanal bellek alanıdır (VMA, virtual memory area): başlangıç ve bitiş adresi, izinler ve varsa eşlenen dosya.

9.1.4Paylaşımlı sayfalar ve kütüphaneler

Sanal belleğin bir yan kazancı da paylaşımdır. Aynı fiziksel çerçeve birden çok sürecin sayfa tablosunda görünebilir; her süreç onu kendi adres alanının istediği yerinde görür (Şekil 9.4).

• Paylaşımlı kütüphane (libc, libstdc++): salt okunur kod sayfaları her süreçte kendi adresinde eşlenir, ama fiziksel kopya tektir. Yüz süreç libc kullansa da libc kodu bellekte bir kez durur.
• Paylaşımlı bellekle süreçler arası iletişim: iki süreç aynı bölgeyi eşler; birinin yazdığını öteki hemen görür.
• fork(): çocuk süreç yaratılırken sayfalar kopyalanmaz, paylaşılır. Kopya ancak biri yazınca çıkarılır.

Yazılabilir veri sayfaları her süreçte özeldir. Paylaşımın güvenli olmasının nedeni kod sayfalarının salt okunur olmasıdır: hiçbir süreç ortak kopyayı değiştiremez.

9.2Talebe bağlı sayfalama

Bir program diskten yüklenirken iki seçenek vardır. Birincisi bütün programı baştan belleğe okumaktır; ama kullanıcı programın küçük bir kısmını kullanacaksa bu boşa harcanmış zaman ve bellektir. İkincisi sayfaları ancak gerektiğinde getirmektir. Sanal bellek sistemleri ikinci yolu izler.

9.2.1Tembel yükleme

Bu tembel yaklaşımın getirisi açıktır: daha az G/Ç, daha az bellek, daha hızlı başlatma ve aynı bellekte daha çok kullanıcı. Bedeli ise her ilk erişimin bir gecikme yaratmasıdır. Bir erişimde üç durum ayrılır:

1. Adres sürecin hiçbir bölgesinde değilse erişim geçersizdir; süreç sonlandırılır.
2. Adres geçerli bir bölgededir ve sayfa bellektedir; erişim normal yürür.
3. Adres geçerlidir ama sayfa bellekte değildir; sayfa getirilir ve erişim yinelenir.

Bu işi yapan birime sayfalayıcı (pager) denir. Eski kitaplarda “tembel takasçı” (lazy swapper) adı da geçer, ama yanıltıcıdır: takasçı bütün süreci taşır, sayfalayıcı ise tek tek sayfalarla uğraşır (Şekil 9.5).

En uç biçimine saf talebe bağlı sayfalama denir. Süreç hiç sayfası bellekte olmadan başlatılır; ilk komut bile bir sayfa hatasıyla gelir. İlk birkaç yüz mikrosaniyede hatalar art arda yağar. Ama süreç gereken sayfaları topladıkça hata oranı hızla düşer. Bunu sağlayan, programların yerellik (locality) özelliğidir: bir program kısa bir süre içinde adres alanının küçük bir bölgesinde çalışır. Döngüler aynı kodu, diziler komşu adresleri, yığın en üstteki birkaç sayfayı kullanır. Yerellik olmasaydı her komut birkaç sayfa hatası doğurur ve talebe bağlı sayfalama işe yaramazdı.

9.2.2Geçerli–geçersiz biti

Talebe bağlı sayfalama, sayfa tablosu girdisindeki tek bir bitle çalışır.

i biti iki farklı durumu kapsar. Donanım ikisini ayırmaz; ikisinde de tuzak üretir. Ayrımı işletim sistemi kendi kayıtlarına, yani VMA listesine bakarak yapar. Aşağıdaki örnek dört sayfalık bir bölgede bu ayrımı adım adım izler.

9.2.3Sayfa hatasının işlenmesi

Silberschatz'ın klasik şeması bir sayfa hatasının işlenmesini altı adımda anlatır (Şekil 9.7). Süreç M adresinden bir değer yüklemek istiyor ve M'nin sayfasına ait girdinin biti i'dir.

1. Referans. MMU girdiyi okur ve sayfanın bellekte olmadığını görür.
2. Tuzak. Donanım çekirdeğe geçer. Çekirdek referansın geçerli olup olmadığına bakar; geçersizse süreci sonlandırır.
3. Sayfa yedek depoda. Sayfanın diskteki yeri bulunur; bu yer takas alanı ya da bir dosya olabilir. Boş bir çerçeve seçilir.
4. Getirme. Disk okuma işi çizelgelenir ve sayfa çerçeve 7'ye okunur. Okuma milisaniyeler sürebileceği için CPU bu arada başka bir sürece verilir.
5. Tabloyu güncelleme. Girdiye çerçeve 7 yazılır, bit v yapılır.
6. Yeniden başlatma. Hataya yol açan komut baştan çalışır. Süreç, sayfa hiç eksik değilmiş gibi devam eder.

Sayfa hatası, tuzakların hata (fault) türündendir. Bu türde kaydedilen program sayacı hatayı yapan komutu gösterir, bir sonrakini değil. Komutun yeniden çalıştırılabilmesi bu sayede mümkündür. x86 işlemciler hatalı sanal adresi ayrıca CR2 yazmacına yazar; işleyici hangi sayfanın istendiğini oradan okur.

Bir ayrıntı da boş çerçeveyle ilgilidir. Üçüncü adımda boş çerçeve yoksa bir kurban seçilmelidir. Kurban değiştirilmişse (kirliyse) önce diske yazılır. Yazma sürerken çerçeve “meşgul” işaretlenir ki başka bir hata onu da kurban seçmesin. Kurbanı seçmek, sayfa yer değiştirme algoritmalarının işidir.

9.2.4Kod izleme: adres çevirisi ve sayfa hatası

Adres çevirisini donanım yapar, ama mantığını birkaç satır C ile yazmak mümkündür. Aşağıdaki ceviri() fonksiyonu 4 KB'lık sayfalarla bir sanal adresi fiziksel adrese çevirir; TLB ıskasında sayfa tablosuna gider, gerekirse sayfa hatası işleyicisini çağırır.

int ceviri(int va) {
  int p = va >> 12;      /* sayfa no */
  int d = va & 0xFFF;    /* ofset */
  int f = tlb_ara(p);    /* -1: ıska */
  if (f < 0) {
    if (!pt[p].gecerli)  /* bellekte yok */
      sayfa_hatasi(p);   /* diskten al */
    f = pt[p].cerceve;
    tlb_ekle(p, f);
  }
  pt[p].R = 1;
  return (f << 12) | d;
}

İlk iki satır adresi parçalar. va >> 12 adresi 12 bit sağa kaydırarak sayfa numarasını bulur; va & 0xFFF alt 12 biti, yani ofseti ayırır. tlb_ara(p) TLB'de sayfayı arar ve bulamazsa −1 döndürür. Iskada if bloğu çalışır: girdinin geçerli biti 0 ise sayfa_hatasi(p) sayfayı diskten getirir ve girdiyi günceller. Ardından çerçeve tablodan okunur ve eşleme TLB'ye eklenir. Her durumda sayfanın R biti 1 yapılır; yer değiştirme algoritmaları bu biti kullanır. Son satır çerçeve numarasını 12 bit sola kaydırıp ofsetle birleştirir.

Başlangıç durumunda TLB'de sayfa 0 (çerçeve 1) ve sayfa 1 (çerçeve 4) vardır. Sayfa 2 bellektedir (çerçeve 5) ama TLB'de değildir. Sayfa 3 ise diskte durur. Fonksiyon sırayla üç adresle çağrılıyor (Tablo 9.1).

• 0x2A10. Üst bitler 0x2, alt 12 bit 0xA10'dur: p = 2, d = 0xA10. TLB'de p = 2 yoktur, f = -1. Girdi 2'nin biti v olduğu için sayfa hatası çağrılmaz. f = 5 tablodan okunur ve (2, 5) TLB'ye eklenir. R biti 1 olur; sonuç (5 << 12) | 0xA10 = 0x5A10.
• 0x2B04. Aynı sayfanın başka bir baytı: p = 2, d = 0xB04. Bu kez TLB'de isabet vardır, if bloğu atlanır ve sayfa tablosuna hiç gidilmez. Sonuç 0x5B04'tür. Yerellik sayesinde erişimlerin büyük çoğunluğu bu kısa yolu izler.
• 0x3008. p = 3, d = 0x008. TLB'de yoktur. Girdi 3'ün biti i'dir, yani sayfa hatası oluşur. Çekirdek sayfayı diskten boş çerçeve 7'ye okur; süreç bu sırada bekler. İşleyici girdiyi (v, 7) yapar. Komut yeniden çalışınca f = 7 okunur ve TLB'ye eklenir; sonuç 0x7008'dir (Şekil 9.8).

Üç çeviride 1 TLB isabeti ve 2 ıska vardır; ıskalardan biri sayfa hatasına, yani disk G/Ç'sine dönüşmüştür. Fonksiyonun kendisi O(1)'dir. Asıl maliyet, ıskanın tablo yürüyüşünde ve özellikle sayfa hatasının disk okumasındadır. İkisinin farkı birkaç büyüklük mertebesidir.

9.2.5Sayfa hatasının zaman çizelgesi

Ders kitapları sayfa hatasını on beş ayrıntılı adımda anlatır. Bu adımlar üç büyük maliyete toplanır: tuzağı işlemek (mikrosaniyeler), sayfayı okumak (HDD'de milisaniyeler, NVMe SSD'de 10–100 µs) ve süreci yeniden başlatmak (mikrosaniyeler). Zaman çizelgesi bunları A süreci, çekirdek, disk ve B süreci satırlarında gösterir (Şekil 9.9).

1. Adım 1–5. Çekirdeğe tuzak; kullanıcı yazmaçları ve süreç durumu kaydedilir. Kesmenin sayfa hatası olduğu ve referansın geçerli olduğu anlaşılır. Sayfanın diskteki yeri bulunur.
2. Adım 6–9. Okuma isteği disk ya da SSD kuyruğuna konur. Aygıt beklenir; HDD'de arama ve dönme gecikmesi eklenir. Bu arada CPU başka bir sürece, B'ye verilir.
3. Adım 10–13. “G/Ç tamamlandı” kesmesi gelir. B'nin durumu kaydedilir, kesmenin diskten geldiği anlaşılır. Sayfa tablosu güncellenir ve A hazır kuyruğuna alınır.
4. Adım 14–15. A yeniden CPU'yu aldığında yazmaçları ve sayfa tablosu yüklenir; yarıda kalan komut baştan çalışır.

Çizelge bir şeyi açıkça gösterir: sayfa hatası A için uzun bir bekleme, sistem için ise yalnız bir bağlam değiştirmedir. CPU boşa gitmez; okuma sürerken B ilerler. Ama A'nın gözünden tek bir bellek erişimi, normal süresinin binlerce katına çıkmıştır. Bu farkın sayısal karşılığı etkin erişim süresidir.

9.2.6Komutu yeniden başlatma ve hata türleri

Sayfa hatasından sonra komutun baştan çalışabilmesi, talebe bağlı sayfalamanın donanımdan istediği tek gerçek özelliktir. Hata, komut getirilirken ya da bir işlenen okunurken oluşabilir. Çoğu durumda komutu baştan çalıştırmak yeter: komut henüz hiçbir şeyi değiştirmemiştir.

Zor durum, komutun bir kısmını değiştirdikten sonra hata almasıdır. IBM 360'ın MVC komutu 256 bayta kadar bir bloğu taşır. Kaynak ya da hedef blok sayfa sınırını aşıyorsa taşıma yarıda hata alabilir. Bloklar örtüşüyorsa kaynak çoktan bozulmuştur ve komut baştan çalıştırılamaz. Otomatik artırmalı adresleme de benzer bir sorun yaratır: komut yazmacı artırmıştır, yeniden çalışınca yanlış adresten başlar.

Motorola 680x0 ailesinde MOVE.L 6(A1),2(A0) komutu üç sözcük uzunluğundadır. İkinci işlenen okunurken hata olursa program sayacı komutun içinde bir yeri gösterir. İşletim sistemi komutun nerede başladığını bilemez. Bu yüzden bazı işlemciler her komuttan önce program sayacını gizli bir yazmaca kopyalar.

Çözümler iki türlüdür. Birincisi, komut başlamadan önce dokunacağı bölgelerin iki ucunu da yoklamaktır; eksik sayfa varsa hata komut başlamadan alınır. İkincisi, değiştirilen değerleri geçici yazmaçlarda tutup hata olursa eski hâline döndürmektir. Bugünkü işlemcilerde kesin istisnalar (precise exceptions) bunu donanımda güvenceye alır: hata anında hatalı komuttan öncekiler tamamlanmış, sonrakiler hiç başlamamış görünür.

Linux, sayfa hatalarını sonuçlarına göre üç türe ayırır (Tablo 9.2). Ayrım performans açısından önemlidir, çünkü yalnız büyük hatalar disk G/Ç'si gerektirir.

Bir programın kaç küçük ve büyük hata yaptığı Linux'ta kolayca ölçülür:

$ /usr/bin/time -v ./prog | grep -i fault
$ ps -o min_flt,maj_flt -p PID
$ perf stat -e page-faults,major-faults ./prog

/usr/bin/time -v programın sonunda “Minor” ve “Major page faults” satırlarını basar. ps çalışan bir sürecin sayaçlarını gösterir. perf stat ise çekirdeğin olay sayaçlarını okur. Aynı program ikinci kez çalıştırıldığında büyük hata sayısı çoğu zaman sıfıra yakın çıkar: ilk çalıştırmada okunan dosya sayfaları sayfa önbelleğinde kalmıştır ve küçük hatayla eşlenir.

9.2.7Sayfalar nereden gelir?

Sayfa hatası işleyicisi eksik sayfayı getirmek için önce sayfanın kaynağını bilmelidir. Sayfalar kaynaklarına göre üç gruba ayrılır (Şekil 9.10).

• Dosya destekli sayfalar: kod, salt okunur veri ve mmap ile eşlenmiş dosyalar. Bellekteki kopya temizse atılır; gerektiğinde dosyadan yeniden okunur.
• Anonim sayfalar: öbek, yığın ve değiştirilmiş veri. Bunların arkasında bir dosya yoktur. Bellekten atılmadan önce takas alanına yazılmaları gerekir, yoksa içerik kaybolur.
• Sıfırla doldurulan sayfalar (zero-fill-on-demand): bss bölümünün ve yeni öbek sayfalarının ilk erişimi sıfırlanmış bir çerçeveyle karşılanır. Sıfırlama bir güvenlik gereğidir: çerçeve daha önce başka bir sürecin verisini taşıyor olabilir.

Hata anında boş çerçeve aramak zaman kaybıdır. Bu yüzden işletim sistemi bir boş çerçeve havuzu tutar ve hata işleyicisi oradan bir çerçeve alır. Havuz belirli bir eşiğin altına inince geri kazanım başlar ve sayfalar çıkarılarak havuz doldurulur. Takas alanı ayrı bir disk bölümü ya da bir dosya olabilir; Linux'ta etkin takas alanları swapon --show ile listelenir.

9.2.8Yedekleme deposu

Takas alanındaki yerin nasıl ayrılacağı konusunda iki yaklaşım vardır (Şekil 9.11).

• Statik ayırma. Süreç başlarken bütün boyu kadar bitişik takas alanı ayrılır ve başlangıç adresi süreç tablosuna yazılır. Sayfa k'nın diskteki adresi “taban + k × sayfa boyu” ile hesaplanır. Kod, veri ve yığın için ayrı alanlar ayrılabilir; büyüyebilen yığın bu durumda ayrıca ele alınır.
• Dinamik ayırma. Önceden yer ayrılmaz. Sayfa diske çıkarken boş bir yuva bulunur ve adresi sayfa başına tutulan bir disk eşleminde saklanır. Değişmemiş kod sayfaları hiç takasa yazılmaz; gerektiğinde çalıştırılabilir dosyadan yeniden okunur.

Takas alanının yeri de değişebilir. Linux geleneksel olarak ayrı bir takas bölümü kullanır, ama dosya sistemindeki bir takas dosyası da (swapfile) olur. Windows sayfaları pagefile.sys dosyasına yazar. Ayrı bölüm biraz daha hızlıdır, çünkü dosya sistemi katmanını atlar; dosya ise boyutu kolayca değiştirilebildiği için esnektir.

9.3Performans: etkin erişim süresi

Talebe bağlı sayfalama bellek erişimini ortalamada yavaşlatır. Erişimlerin çoğu normal hızda yürür, ama arada bir gelen sayfa hatası diske gitmeyi gerektirir. İkisinin ağırlıklı ortalaması sistemin gerçekte ne kadar hızlı olduğunu söyler.

Sayfa hatası süresi üç parçanın toplamıdır: tuzağı işlemek, sayfayı okumak ve süreci yeniden başlatmak. İlk ve son parça mikrosaniyeler sürer. Okuma ise depolamanın türüne göre değişir ve süreyi belirleyen odur. p = 0 ise hiç hata yoktur ve EAT = ma olur; p = 1 ise her erişim hatadır.

Sonuç çarpıcıdır. Erişimlerin %99,9'u 100 ns'de biter, ama kalan %0,1'in her biri 25 ms sürdüğü için ortalamayı o belirler. Bu yüzden asıl soru tersinden sorulur: belli bir yavaşlamaya razı olursak hata oranı en çok ne olabilir?

Hata oranı bu kadar düşük tutulabiliyorsa bunun nedeni yine yerelliktir. Ama sonuç, sistemin yer değiştirme kararlarında hata yapmaya hiç tahammülü olmadığını da gösterir.

Depolama teknolojisi değiştikçe hesap da değişir. 2026 itibarıyla NVMe SSD'den bir sayfa okumak 10–100 µs sürer. Linux'un zram mekanizmasında sayfa RAM'de sıkıştırılmış durur; “okuma” bir sıkıştırma çözme işlemidir ve yaklaşık 10 µs sürer (Tablo 9.3, Şekil 9.12).

NVMe satırının hesabı şöyledir: 0,999 × 100 + 0,001 × 100 000 = 99,9 + 100 = 199,9 ns. %10 sınırı ise 10 / 99 900 ≈ 1,0 × 10⁻⁴ çıkar. zram için 99,9 + 0,001 × 10 000 = 109,9 ns'dir.

Hızlı depolama hata cezasını iki üç büyüklük mertebesi küçültür: HDD'nin 25 ms'si NVMe'nin 100 µs'sinin 250, zram'ın 10 µs'sinin 2 500 katıdır. Yine de bellek hâlâ yüzlerce kat hızlıdır ve hata oranı EAT'yi belirlemeyi sürdürür. Yer değiştirme algoritmalarının bugün de önemli olmasının nedeni budur.

Silberschatz'ın 10. baskısı aynı hesabı 200 ns bellek ve 8 ms hata süresiyle yapar. p = 0,001 için EAT = 200 × 0,999 + 8 000 000 × 0,001 = 199,8 + 8 000 = 8 199,8 ns ≈ 8,2 µs bulunur. Bu, 8 199,8 / 200 ≈ 41 katlık bir yavaşlamadır. %10 sınırı ise 220 > 200 + 7 999 800 p eşitsizliğinden p < 2,5 × 10⁻⁶ çıkar.

9.4Yazınca kopyalama

fork() ebeveynin bir kopyasını yaratır. Saf hâliyle ebeveynin bütün sayfaları kopyalanmalıdır. Oysa çocukların çoğu yaratıldıktan hemen sonra exec() çağırır ve bu kopyaların hepsini çöpe atar. Sanal bellek bu israfı önlemenin yolunu verir.

9.4.1fork() ve paylaşılan sayfalar

Mekanizma koruma bitleri üzerine kuruludur. Yazma denemesi salt okunur sayfada bir koruma hatası doğurur. Çekirdek girdideki COW işaretini görünce bunun gerçek bir ihlal olmadığını anlar. Boş bir çerçeve alır, sayfanın içeriğini oraya kopyalar ve kopyayı yazana yazılabilir olarak eşler. Ardından yazma komutu yeniden çalışır (Şekil 9.13).

Hiç değiştirilmeyen sayfalar, örneğin kod ve salt okunur veri, iki süreç yaşadıkça paylaşılır. Bu yüzden fork() ardından exec() çağırmak neredeyse bedavadır: yalnız sayfa tabloları kopyalanır ve exec() onları da atar. Paylaşılan birim dosya ya da bölge değil, tek tek sayfalardır; yalnız yazılan sayfa kopyalanır.

Kopya için gereken çerçeve sıfırla doldurulan sayfaların havuzundan alınır. Bir de vfork() vardır. Bu çağrı sayfa tablosunu bile kopyalamaz: çocuk ebeveynin adres alanını doğrudan kullanır ve ebeveyn, çocuk exec() ya da _exit() çağırana kadar bekler. Çocuk bu arada bir değişkeni değiştirirse ebeveyn de değişikliği görür; bu yüzden vfork() tehlikelidir. Bugün yeni program başlatmak için posix_spawn() tercih edilir.

Paylaşımın doğru yönetilmesi için çekirdek her çerçeve için bir referans sayısı tutar: çerçeveyi kaç sayfa tablosu eşliyor. Bir koruma hatasında referans sayısı 1'den büyükse kopya gerekir. Sayı 1 ise sayfa artık yalnız bu sürecindir; kopyalamaya gerek kalmaz, sayfa yazılabilir yapılır.

9.4.2Kod izleme: fork() ve COW

Aşağıdaki program bir global değişken (veri sayfası D) ve bir öbek tamponu (öbek sayfası H) kullanır. Çocuk değişkeni okur ve değiştirir, ebeveyn tampona yazar.

int x = 1;                 /* veri: D */
int main(void) {
  char *b = malloc(4096);  /* öbek: H */
  b[0] = 'a';
  pid_t pid = fork();
  if (pid == 0) {          /* çocuk */
    printf("%d\n", x);    /* okuma */
    x = 2;                 /* yazma */
    _exit(0);
  }
  wait(NULL);
  b[0] = 'b';              /* ebeveyn */
  return 0;
}

İzleme, iki sürecin sayfa tablolarını ve çerçevelerin referans sayılarını adım adım takip eder (Tablo 9.4).

• Başlangıç. Ebeveyn D ve H sayfalarını yazılabilir (RW) olarak kullanıyor; b[0] = 'a' H'yi çoktan yüklemiştir.
• fork(). Çekirdek yalnız sayfa tablolarını kopyalar. İki tarafta da D ve H salt okunur (RO) işaretlenir, f1 ve f2'nin referans sayıları 2 olur.
• Çocuk x'i okur. Okuma izinli olduğu için hata da kopya da yoktur. Ekrana 1 basılır.
• Çocuk x = 2 yazar. D salt okunur olduğundan koruma hatası oluşur. Çekirdek COW'u tanır: f3'ü ayırır, D'nin içeriğini oraya kopyalar ve çocuğa RW olarak eşler. f1'in referans sayısı 1'e iner. Ebeveynin x'i hâlâ 1'dir.
• Çocuk çıkar. Eşlemeleri kaldırılır, f3 boş listeye döner, f2'nin referans sayısı da 1'e iner.
• Ebeveyn H'ye yazar. H hâlâ salt okunur işaretli olduğu için hata oluşur. Ama f2'nin referans sayısı 1'dir; kopyaya gerek yoktur, sayfa yalnız yazılabilir yapılır.

Program boyunca tek bir sayfa kopyalanmıştır. Ebeveynin D sayfası ise hâlâ RO işaretlidir. Ebeveyn D'ye yazarsa bir hata daha oluşur, ama o da referans sayısı 1 olduğu için kopyasız çözülür. Yöntemin bedeli, yazılan her paylaşılan sayfa için bir tuzak ve bir sayfa kopyalamadır. Kazancı ise hiç yazılmayan bütün sayfaların kopyalanmamasıdır.

9.5Bellek eşlemeli dosyalar

Bir dosyayı okumanın alışılmış yolu read() ve write() çağrılarıdır. Her çağrı bir sistem çağrısıdır ve veriyi çekirdek tamponu ile kullanıcı tamponu arasında kopyalar. Sanal bellek ikinci bir yol açar: dosyayı adres alanına eşlemek ve bellek gibi kullanmak.

9.5.1mmap() ve eşleme türleri

Eşlemenin kendisi hiçbir şey okumaz; yalnız bir VMA oluşturur. Sayfalar talebe bağlı getirilir: her sayfaya ilk erişim bir sayfa hatası üretir. Sayfa sayfa önbelleğinde zaten varsa hata küçüktür, yoksa büyüktür. Yazılan sayfalar kirli olur ve arka planda ya da msync() veya munmap() çağrısıyla dosyaya yazılır (Şekil 9.14).

mmap()'in bayrakları eşlemenin nasıl davranacağını belirler:

• MAP_SHARED: değişiklikler dosyaya ve aynı dosyayı eşleyen herkese görünür. İki süreç bu yolla paylaşımlı bellek kurup haberleşebilir.
• MAP_PRIVATE: yazmalar yazınca kopyalamayla özel bir kopyaya gider, dosya değişmez. Çalıştırılabilir dosyaların veri bölümü böyle yüklenir: program ilk değerleri dosyadan alır, değiştirdiklerini kendine saklar.
• MAP_ANONYMOUS: arkasında dosya olmayan, sıfırla doldurulan bir bölge. malloc() büyük blokları bu yolla ayırır.

Windows'ta aynı işi CreateFileMapping ile oluşturulan eşleme nesnesi ve MapViewOfFile çağrısı yapar.

Bellek eşlemenin üstünlüğü, kopyanın ortadan kalkmasıdır. Sayfa önbelleğindeki çerçeve doğrudan sürecin adres alanına eşlenir; çekirdek tamponundan kullanıcı tamponuna ikinci bir kopya yapılmaz. Ayrıca sık okunan küçük parçalar için sistem çağrısı maliyeti de ortadan kalkar. Bedeli, her yeni sayfanın bir sayfa hatası üretmesi ve G/Ç hatalarının sinyal olarak (SIGBUS) gelmesidir.

9.5.2Kod izleme: mmap

Aşağıdaki program 12 KiB'lık bir dosyayı paylaşımlı ve yazılabilir olarak eşler, bir bayt okur, bir bayt yazar, değişikliği diske aktarır ve eşlemeyi kaldırır.

int fd = open("veri.bin", O_RDWR);
struct stat st;
fstat(fd, &st);          /* 12 KiB = 3 sayfa */
char *p = mmap(NULL, st.st_size,
     PROT_READ | PROT_WRITE,
     MAP_SHARED, fd, 0);
close(fd);               /* eşleme sürer */
char c = p[0];           /* sayfa 0 */
p[5000] = 'x';           /* sayfa 1 */
msync(p, st.st_size, MS_SYNC);
munmap(p, st.st_size);

İzleme sayfa tablosu girdilerini ve sayfa önbelleğini birlikte takip eder (Tablo 9.5).

• Açma. Dosya açılır, fstat boyutun 12 KiB, yani 3 sayfa olduğunu söyler.
• mmap. Yalnız bir VMA oluşturulur; tablo girdileri boştur ve hiçbir sayfa okunmamıştır.
• close(fd). Eşlemeyi bozmaz, çünkü VMA dosyaya kendi referansını tutar.
• p[0]. Sayfa 0'a ilk erişim bir sayfa hatası doğurur. Blok 0 sayfa önbelleğine okunur (büyük hata) ve girdi geçerli olur.
• p[5000]. 5000 / 4096 = 1 (tam bölme), yani sayfa 1; ofset 5000 − 4096 = 904'tür. Yine hata ve okuma olur, ardından yazma sayfayı kirli yapar (M = 1).
• msync. MS_SYNC bayrağıyla kirli sayfa dosyaya yazılır ve çağrı yazma bitene kadar döner; M temizlenir. Sayfa 2'ye hiç dokunulmadığı için hiç okunmamıştır.
• munmap. VMA kaldırılır. Sayfalar sayfa önbelleğinde kalabilir; başka bir süreç dosyayı açarsa onları küçük hatayla kullanır.

9.6Sayfa yer değiştirme

Talebe bağlı sayfalamanın anlatımında her sayfa hatasında boş bir çerçeve bulunduğu varsayıldı. Gerçek sistemlerde bellek çoğu zaman doludur. Bunun nedeni israf değil, tam tersidir: boş duran RAM boşa harcanmış RAM'dir. İşletim sistemi boş belleği sayfa önbelleği olarak kullanır ve ancak gerektiğinde geri alır. Bu yüzden hata anında çoğunlukla bir sayfa çıkarılmalıdır.

9.6.1Boş çerçeve yoksa

Boş çerçeve yokken işletim sisteminin üç seçeneği vardır. Süreci sonlandırmak kabul edilemez: sanal bellek kullanıcıya görünmemelidir. Bütün bir süreci takas alanına atmak mümkündür, ama ağır bir önlemdir ve aşırı yüklenmede kullanılır. Olağan yol tek bir sayfanın yerini değiştirmektir.

Yer değiştirme, sayfa hatası işleyicisine beş adım ekler (Şekil 9.16):

1. Yer değiştirme algoritması bir kurban çerçeve seçer.
2. Kurban kirliyse (M = 1) takas alanına ya da dosyasına yazılır. Temizse yazmaya gerek yoktur; diskteki kopya zaten günceldir. Böylece G/Ç yarıya iner.
3. Kurbanın girdisi geçersiz yapılır ve eşlemesi TLB'den silinir. Çok çekirdekli sistemde diğer çekirdeklerin TLB'leri de temizlenmelidir; buna TLB vurusu (TLB shootdown) denir.
4. İstenen sayfa boşalan çerçeveye okunur.
5. Yeni sayfanın girdisi geçerli yapılır ve tuzağa yol açan komut yeniden başlatılır.

M biti burada önemli bir tasarruf sağlar. Kirli kurbanın bedeli iki disk işlemidir: bir yazma ve bir okuma. Temiz kurbanınki yalnız okumadır. Bu yüzden birçok algoritma, aynı derecede eski iki sayfadan temiz olanı tercih eder.

Sanal bellek sistemi iki ayrı soruyu yanıtlamalıdır. Çerçeve tahsisi: bir sürece kaç çerçeve verilecek? Yer değiştirme: hangi sayfa çıkacak? Bu kesim ikinci soruyla ilgilenir. İki sorunun amacı aynıdır: sayfa hatası sayısını en aza indirmek ve aynı sayfanın bellek ile disk arasında tekrar tekrar gidip gelmesini önlemek.

9.6.2Algoritmaları değerlendirmek

Bir algoritmayı değerlendirmek için onu bir dizi bellek erişimi üzerinde çalıştırır ve sayfa hatalarını sayarız. Gerçek adres dizileri milyonlarca öğe içerir, ama algoritmanın kararı yalnız sayfa numarasına bağlıdır. Bu yüzden diziyi kısaltmak mümkündür.

Bu notta algoritmalar Silberschatz'ın ortak dizisi üzerinde, 3 çerçeveyle çalıştırılır:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Dizide 20 referans ve 6 farklı sayfa (7, 0, 1, 2, 3, 4) vardır. Her farklı sayfanın ilk yüklenmesi kaçınılmaz bir hatadır; dolayısıyla hiçbir algoritma 6'nın altına inemez. Çerçeve sayısı arttıkça hata sayısının azalması beklenir (Şekil 9.17). Çerçeve sayısı 6'ya ulaşınca bütün sayfalar sığar ve yalnız ilk yüklemeler kalır.

Eğrideki değerler algoritmalar çalıştırılarak denetlenmiştir. FIFO'nun 2 ve 3 çerçevede aynı (15) kalması dikkat çekicidir: bir çerçeve eklemek bu dizide hiçbir şey kazandırmaz. Bölümde çalıştırılacak algoritmalar şunlardır: OPT, FIFO, LRU, ikinci şans, saat, NRU, NFU ve yaşlandırma, çalışma kümesi ve WSClock. Farklı dizilerle denemek için Sayfa Yer Değiştirme Simülatörü FIFO, OPT, LRU, LFU ve ikinci şansı adım adım çalıştırır.

9.6.3FIFO

FIFO'nun gerçeklemesi çok kolaydır ve hiçbir donanım biti gerektirmez. Sorunu, sayfanın ne zaman kullanıldığını hiç hesaba katmamasıdır. En eski sayfa, en yoğun kullanılan sayfa olabilir: başlangıçta yüklenen bir değişken bütün çalışma boyunca kullanılıyorsa FIFO onu yine de ilk fırsatta atar.

Ortak dizideki izleme şöyledir (Şekil 9.18). İlk üç referans (7, 0, 1) boş çerçevelere yüklenir: 3 hata. Kuyruk sırası 7, 0, 1'dir.

• Referans 4 (sayfa 2). Hata. Kuyruğun başındaki 7 çıkar, 2 sona girer. Kuyruk: 0, 1, 2. Hata sayısı 4.
• Referans 5 (0). Bellekte, isabet. FIFO'da isabet kuyruğu değiştirmez.
• Referans 6 (3). Hata; 0 çıkar. Kuyruk: 1, 2, 3. Hata 5.
• Referans 7 (0). Hata; 1 çıkar. 0 bir adım önce atılmıştı ve hemen geri istendi. Kuyruk: 2, 3, 0. Hata 6.
• Referans 8–11 (4, 2, 3, 0). Dördü de hata. Sırasıyla 2, 3, 0 ve 4 çıkar. Her biri bir sonraki adımlarda yeniden gerekecektir. Hata 10, kuyruk: 2, 3, 0.
• Referans 12, 13 (3, 2). İsabet.
• Referans 14, 15 (1, 2). Hata; 2 ve 3 çıkar. Hata 12, kuyruk: 0, 1, 2.
• Referans 16, 17 (0, 1). İsabet.
• Referans 18–20 (7, 0, 1). Üçü de hata; 0, 1 ve 2 çıkar. Toplam 15 hata.

Kurbanların sırası 7, 0, 1, 2, 3, 0, 4, 2, 3, 0, 1, 2'dir. Bu sıra tam olarak yüklenme sırasıdır; FIFO erişimi değil yüklenmeyi izler. Algoritmanın her adımı O(1)'dir: bir sayfanın bellekte olup olmadığı bir karma tablosuyla, kurban da kuyruğun başından bulunur.

9.6.4Belady anomalisi

Çerçeve sayısı arttıkça sayfa hatasının azalması doğal görünür. 1969'da Belady, Nelson ve Shedler bunun FIFO için her zaman doğru olmadığını gösterdi.

Anomalinin nedeni, FIFO'da iki çerçeve sayısındaki bellek içeriklerinin birbirinden kopmasıdır. 7. referanstan sonra 3 çerçevede {1, 2, 5}, 4 çerçevede {2, 3, 4, 5} bulunur. Küçük bellekte olan 1, büyük bellekte yoktur. Sıradaki referanslar tam da 1 ve 2 olduğu için küçük bellek kazanır.

Bazı algoritmalarda bu kopma hiç yaşanmaz.

LRU bir yığın algoritmasıdır. n çerçeveli LRU belleğinde son kullanılan n farklı sayfa durur. n + 1 çerçevelide son kullanılan n + 1 farklı sayfa durur ve ilki her zaman ikincinin içindedir. OPT de aynı özelliği taşır. Aynı dizide LRU 3 çerçeveyle 10, 4 çerçeveyle 8 hata yapar. FIFO ise yığın algoritması değildir; kümelerin bozulduğu adımlar bu örnekte 7., 8. ve 11. referanslardır.

9.6.5OPT

OPT'nin tanımı kolaydır, ama gerçeklenmesi imkânsızdır: işletim sistemi bir sürecin gelecekte hangi sayfaya erişeceğini bilemez. Bu yüzden OPT'ye “kristal küre” algoritması da denir. Yine de çok değerlidir, çünkü bir alt sınır verir. Yeni bir algoritmanın OPT'ye ne kadar yaklaştığı onun ne kadar iyi olduğunu söyler. Gerçek bir sistemde OPT ancak bir iz kaydedilip ikinci kez çalıştırılarak hesaplanabilir; ilk çalıştırma geleceği öğrenmek içindir.

Ortak dizideki izleme kurban seçimlerine odaklanır. Her hatada bellekteki sayfaların bir sonraki kullanım anı (referans numarası) karşılaştırılır (Tablo 9.6).

Referans 4'te bellekte 7, 0 ve 1 vardır. 0 hemen 5. referansta, 1 ise 14.'de gerekir; 7 ancak 18.'de gerekecektir. En uzağa kalan 7 çıkar. Referans 11'de sayfa 4 bir daha hiç kullanılmayacaktır; böyle bir sayfa varsa hemen kurban olur. Altı yer değiştirme ile 3 ilk yükleme toplamı 9 hata verir (Şekil 9.20). Bu sayı, bu dizi ve 3 çerçeve için ulaşılabilecek en iyi değerdir.

9.6.6LRU

OPT geleceğe bakar. Gelecek bilinemiyorsa en iyi tahmin yakın geçmiştir: yerellik ilkesine göre yakın geçmişte kullanılmayan bir sayfa yakın gelecekte de büyük olasılıkla kullanılmayacaktır. LRU bu fikri kurala dönüştürür; bir anlamda geriye bakan OPT'dir.

Ortak dizideki izleme FIFO'yla aynı başlar, ama isabetler artık sırayı değiştirir (Şekil 9.21).

• Referans 1–3. 7, 0, 1 boşlara yüklenir. 3 hata.
• Referans 4 (2). En uzun süredir kullanılmayan 7 çıkar. Hata 4.
• Referans 5 (0). İsabet; 0 artık en yeni sayfadır.
• Referans 6 (3). Bellekte 1, 2, 0 vardır; son kullanımları 3, 4 ve 5'tir. 1 çıkar. Hata 5. FIFO burada 0'ı atmıştı; LRU, 0'ın az önce kullanıldığını bilir.
• Referans 7 (0). İsabet. FIFO'nun hata yaptığı yerde LRU kazanır.
• Referans 8–11 (4, 2, 3, 0). Dördü de hata; sırayla 2, 3, 0 ve 4 çıkar. Hata 9. Bu dört adımda dizi her seferinde bir önce atılan sayfayı geri ister ve LRU da kötü sonuç verir.
• Referans 12, 13 (3, 2). İsabet.
• Referans 14 (1). 0 çıkar. Hata 10. Referans 15 (2) isabet.
• Referans 16 (0). 3 çıkar. Hata 11. Referans 17 (1) isabet.
• Referans 18 (7). 2 çıkar. Hata 12. Referans 19, 20 (0, 1) isabet.

LRU uygulamada çok iyi sonuç verir ve birçok algoritmanın yaklaşmaya çalıştığı hedeftir. Ama her bellek erişiminde bir kaydın güncellenmesini ister. Saniyede milyarlarca erişim yapan bir işlemcide bu iş donanım desteği olmadan yapılamaz. Bir uyarı da adlarla ilgilidir: en son kullanılanı atan algoritmanın adı MRU'dur (most recently used). LRU ise en eski kullanılanı atar.

9.6.7LRU'yu gerçeklemek: sayaç ve yığın

Tam LRU için iki klasik gerçekleme vardır.

Sayaç (zaman damgası). CPU'ya her bellek erişiminde artan mantıksal bir saat eklenir. Bir sayfaya her erişimde, saatin değeri o sayfanın tablo girdisine yazılır. Kurban, damgası en küçük olan sayfadır. Bu yöntemde güncelleme basit ama sıktır: her bellek erişimi sayfa tablosuna bir yazma demektir. Seçim ise pahalıdır: her hatada bütün tablo taranmalıdır. Saat taşmasına da çözüm gerekir.

Yığın. Sayfa numaraları bir yığında tutulur. Bir sayfaya erişilince sayfa yığının ortasından çıkarılır ve tepeye konur. Tepede en son kullanılan, en altta en uzun süredir kullanılmayan sayfa durur; kurban en alttakidir. Yığın, başı ve sonu işaretçili bir çift bağlı listeyle gerçeklenir. Ortadan bir düğümü çıkarıp başa eklemek en fazla altı işaretçi değişikliği ister. Kurban kuyruktan O(1)'de alınır ve arama gerekmez.

Yığın yönteminde güncelleme pahalı, seçim ucuzdur; sayaç yönteminde tersi. İkisi de her bellek erişiminde iş ister ve bugün hiçbir genel amaçlı işlemcinin donanımında bulunmaz. Pratikte LRU'ya yaklaşan, R bitine dayalı algoritmalar kullanılır.

9.6.8LRU'yu gerçeklemek: matris yöntemi

Tanenbaum küçük çerçeve sayıları için zarif bir donanım çözümü anlatır. n çerçeveli bir makinede donanım n × n bitlik bir matris tutar. Başlangıçta bütün bitler 0'dır.

Yöntemin neden çalıştığını görmek kolaydır. k'ya erişim, k. satırı “herkesten daha yeni” yapar: k. satırda kendi sütunu dışında her bit 1'dir. Aynı anda diğer her satırın k. biti 0 olur, yani “k'dan daha yeni değilim” bilgisi yazılır. Satır i'nin j. biti 1 ise i, j'den daha yakın zamanda kullanılmıştır.

Son durumu doğrulamak için kullanım sırasına bakmak yeter. Son erişimler sırasıyla 3 (onuncu), 2 (dokuzuncu), 0 (yedinci) ve 1'dir (altıncı). Satır değerlerinin büyükten küçüğe sırası 14, 12, 4, 0, yani 3, 2, 0, 1'dir. Matris tam LRU sırasını kodlar. Bedeli n² bittir: 4 çerçevede 16 bit sorun değildir, ama milyonlarca çerçeveli bir makinede yöntem kullanılamaz.

9.6.9İkinci şans

Tam LRU donanımı yoktur, ama hemen bütün işlemciler R bitini tutar. R biti, sayfanın son temizlendiğinden beri kullanılıp kullanılmadığını söyler. Kullanım sırasını vermez, ama “yakın zamanda kullanıldı mı?” sorusunu yanıtlar. FIFO'nun en büyük kusuru da tam bu soruyu sormamasıdır.

Bütün sayfaların R biti 1 ise ne olur? Algoritma bir tur döner, her sayfanın R'sini temizleyip onu sona taşır. Tur bitince baştaki sayfa yine ilk sayfadır ve R'si artık 0'dır; o atılır. Bu durumda ikinci şans saf FIFO gibi davranır. Algoritma her zaman sonlanır, çünkü en kötü durumda bir tur sonra her R biti 0'dır.

İkinci şansın zayıf yanı gerçeklemededir: sayfalar listede sürekli taşınır. Bu taşımalar gereksiz iştir ve aynı karar daha ucuza verilebilir.

9.6.10Saat algoritması

Yüklenen ya da erişilen sayfanın R'si donanımca 1 yapılır. El yalnız hata anında döner; isabetlerde kıpırdamaz. El sayfa tablosunda değil, çerçeve listesinde döner: fiziksel çerçeveleri sırayla dolaşır.

Ortak dizide saat algoritması şöyle çalışır. İlk üç referans 7, 0, 1'i çerçeve 0, 1, 2'ye yükler; üçünün de R'si 1'dir ve el çerçeve 0'ı gösterir (Tablo 9.7).

• Referans 4 (2). 7, 0 ve 1'in R'si 1'dir. El üçünün de R'sini temizleyip bir tur atar ve yine çerçeve 0'a, 7'ye gelir. 7'nin R'si artık 0'dır; 7 çıkar. Tüm R'ler 1 olduğu için saat burada FIFO gibi davranmıştır.
• Referans 5 (0). İsabet; donanım 0'ın R'sini 1 yapar, el kıpırdamaz.
• Referans 6 (3). El çerçeve 1'de, 0'ın üstündedir. R = 1 olduğu için 0 ikinci şans alır. El sonraki çerçevedeki sayfa 1'e geçer; onun R'si 0'dır ve 1 çıkar. FIFO burada 0'ı atmıştı.
• Referans 9 (2). Önceki taramada R'si temizlenen ve o zamandan beri kullanılmayan 0 hemen kurban olur. Saatin zayıflığı burada görünür: 0 az sonra, 11. referansta yeniden istenecektir.
• Sonuç. Toplam 14 hata. FIFO'dan (15) bir az, LRU'dan (12) iki fazla.

Saat algoritması LRU'ya kaba bir yaklaşımdır: yalnız “son taramadan beri kullanıldı mı?” sorusunu sorar. Buna karşılık her isabette hiçbir iş yapmaz, hatada da çoğu zaman birkaç adımda kurban bulur. Bu ucuzluk onu gerçek sistemlerin temeli yapmıştır.

9.6.11Kod izleme: saat algoritması

Aşağıdaki kod saat algoritmasını M bitiyle birlikte gerçekler. cer çerçeve dizisi, el saatin elidir; N çerçeve sayısıdır.

int kurban_sec(void) {
  while (cer[el].R == 1) { /* 2. şans */
    cer[el].R = 0;
    el = (el + 1) % N;
  }
  int k = el;              /* kurban */
  el = (el + 1) % N;
  return k;
}
void hata(int p) {
  int k = kurban_sec();
  if (cer[k].M) diske_yaz(k); /* kirli */
  cer[k].sayfa = p; cer[k].R = 1;
  cer[k].M = 0;
}

kurban_sec() içindeki while döngüsü, elin altındaki çerçevenin R'si 1 olduğu sürece döner: R'yi 0 yapar ve eli bir ilerletir (% N dairesel ilerlemeyi sağlar). R = 0 olan ilk çerçevede döngü biter. O çerçeve kurbandır ve el bir sonrakine geçer. hata() kurban kirliyse önce diske yazar; sonra yeni sayfayı R = 1, M = 0 ile yerleştirir.

Dört çerçevenin başlangıç durumu şöyledir: çerçeve 0'da s3 (R = 1, M = 0), çerçeve 1'de s8 (R = 0, M = 1), çerçeve 2'de s5 (R = 1, M = 0), çerçeve 3'te s6 (R = 1, M = 1). El çerçeve 2'dedir. Önce sayfa 9, sonra sayfa 4 için hata oluşuyor (Tablo 9.8).

İlk hatada el tam bir tur döner. s5, s6 ve s3 yakın zamanda kullanılmıştır ve ikinci şans alır. s8'in R'si 0'dır, ama M biti 1'dir: bellekteki kopya diskte yoktur. Atılmadan önce diske yazılır ve bu bir ek G/Ç'dir. s9 çerçeve 1'e R = 1, M = 0 ile yüklenir.

İkinci hatada el çerçeve 2'dedir. s5'in R'si önceki turda sıfırlanmıştı ve o zamandan beri kullanılmadı. Kurban hemen bulunur. s5 temizdir, diskteki kopya günceldir; yazmaya gerek yoktur ve temiz kurban daha ucuzdur. Son durumda çerçeveler (s3, 0, 0), (s9, 1, 0), (s4, 1, 0), (s6, 0, 1)'dir; el çerçeve 3'te bekler (Şekil 9.27). İki hatada 4 R biti sıfırlanmış ve 1 disk yazması yapılmıştır.

kurban_sec() en kötü durumda N + 1 adım sürer: bütün R'ler 1 ise el bir tur atar ve başladığı yerde biter. Ortalama durumda çok daha kısadır. Bellek çok büyükse tek bir el bile turunu çok geç tamamlar; bu sorunun çözümü iki elli saattir.

9.6.12NRU

Saat algoritması yalnız R bitine bakar. Oysa aynı derecede eski iki sayfadan temiz olanı atmak bir disk yazmasını kurtarır. NRU iki biti birlikte kullanır.

Sınıf numarası 2R + M'dir; R biti ağır basar. Bu tercih bilinçlidir: yakın zamanda kullanılmış temiz bir sayfayı atmak, kullanılmamış kirli bir sayfayı yazmaktan daha kötüdür. İlk bakışta sınıf 1 imkânsız görünebilir: bir sayfa kullanılmadan nasıl değişir? Değişmiştir, ama sonra bir saat tıkı R'sini silmiştir. M ise tıkla silinmez, çünkü sayfanın diske yazılması gerekip gerekmediğini söyler.

NRU'nun LRU'dan farkı ayrıntı düzeyindedir. LRU tam kullanım sırasını izler. NRU yalnız iki soruyu sorar: son saat aralığında kullanıldı mı, kirli mi? Sonuç kaba ama ucuzdur. Bir sınıfın içinde hangi sayfanın seçileceği belirsizdir; bu notta eşitlikte en eski yüklenen seçilir.

NRU'nun 11 hatası LRU'nun 12'sinden azdır. Bu, NRU'nun LRU'dan iyi olduğu anlamına gelmez. R ve M bitine dayalı algoritmaların sonucu tıkların nereye düştüğüne ve eşitlik kuralına bağlıdır. Kısa tek bir dizide şans payı büyüktür.

9.6.13Geliştirilmiş saat

NRU'nun sınıf fikri saat algoritmasının dairesel listesiyle birleştirilebilir. Silberschatz bu algoritmaya “geliştirilmiş ikinci şans” (enhanced second-chance) adını verir; eski macOS sürümleri de bunu kullanmıştı.

Algoritmada saat tıkı yoktur; R bitleri yalnız el geçerken temizlenir. Ortak dizi ve aynı yazmalarla izleme şöyledir:

• Referans 4 (2). Bellekte 7 (1, 0), 0 (1, 1), 1 (1, 0) vardır ve el çerçeve 0'dadır. Tur 1'de (0, 0) yoktur. Tur 2'de (0, 1) de yoktur, ama el geçerken bütün R'leri temizler. Yeniden tur 1'de el 7'nin üstündedir ve 7 artık (0, 0)'dır: 7 çıkar.
• Referans 6 (3*). 2 (1, 0), 0 (1, 1), 1 (0, 0); el çerçeve 1'de. Tur 1'de 0'ı geçer, 1'i (0, 0) bulur: 1 çıkar.
• Referans 8 (4). Tur 1 ve tur 2 sonuçsuz kalır; tur 2 bütün R'leri temizler. Yeniden tur 1'de 2 (0, 0) bulunur: 2 çıkar.
• Referans 9 (2*). Bellekte 4 (1, 0), 0 (0, 1), 3 (0, 1). Tur 1'de (0, 0) yoktur. Tur 2 elin altındaki 0'ı (0, 1) bulur: 0 çıkar ve önce diske yazılır (yazma 1).
• Sonraki hatalar. 11. referansta 4, 14.'de 0, 16.'da kirli 3 (yazma 2), 18.'de kirli 2 (yazma 3) çıkar.
• Sonuç. 11 hata, 3 kirli yazma (Şekil 9.29).

Sonuç NRU'yla aynıdır, ama kurbanlar farklıdır: NRU 7, 1, 2, 4, 0, 3, 0, 2'yi, geliştirilmiş saat 7, 1, 2, 0, 4, 0, 3, 2'yi atar. Fark 9. referansta doğar. NRU'da bir tık tüm R'leri silmiştir ve 4 sınıf 0'dadır. Geliştirilmiş saatte ise 4'ün R'si hâlâ 1'dir ve kirli ama kullanılmamış 0 seçilir. Bedel, bir hatada belleği birkaç kez taramaktır.

9.6.14NFU ve yaşlandırma

R biti yalnız son aralığı hatırlar. Daha uzun bir geçmişi yazılımla tutmak mümkündür.

NFU'nun kusuru hiç unutmamasıdır. Programın ilk evresinde çok kullanılan bir sayfa yüksek bir sayaç biriktirir. Program başka bir evreye geçip o sayfaya hiç dokunmasa bile sayacı yüksek kalır ve sayfa bellekte kalmayı sürdürür. Sayaç kullanım sayısını tutar, kullanım zamanını tutmaz. Küçük bir değişiklik bu kusuru giderir.

Sayfa 3 ve 5'in karşılaştırması yaşlandırmanın mantığını gösterir. İkisi de son iki tıkta kullanılmamıştır. Sayfa 3 en son tık 2'de kullanılmıştır (00100000), sayfa 5 de tık 2'de, ama ayrıca tık 0'da (00101000). Eşit yeni geçmişte daha uzun geçmiş belirleyici olur.

Yaşlandırma LRU'ya iyi yaklaşır, ama iki farkı vardır. Birincisi, aynı tık aralığında kullanılan iki sayfanın hangisinin daha sonra kullanıldığı bilinmez; ikisinin de en anlamlı biti 1'dir. İkincisi, 8 bitlik sayaç yalnız son 8 tıkı hatırlar. 9 tık önce kullanılan bir sayfa ile 1 000 tık önce kullanılan bir sayfanın sayacı aynıdır: 0. Tıklar yaklaşık 20 ms aralıkla gelirse 8 bit 160 ms'lik bir geçmiş demektir ve bu çoğu zaman yeterlidir.

9.6.15Yaşlandırma ortak dizide

Yaşlandırmayı ortak dizide çalıştırmak bir ayrıntıyı ortaya çıkarır. Tıklar her 4 referansta bir gelir. Yeni yüklenen sayfanın sayacı 0, R'si 1'dir. Karşılaştırmada henüz sayaca eklenmemiş R biti en anlamlı bit sayılır, yani 9 bitlik bir değer (R, sayaç) kullanılır. Bunu yapmasaydık yeni yüklenmiş sayfanın sayacı 0 olurdu ve sayfa hemen ilk hatada atılırdı. Eşitlikte en eski yüklenen sayfa seçilir.

Referans 4'te üç sayfanın anahtarı eşittir ve en eski yüklenen 7 çıkar. Ardından ilk tık gelir ve R'ler sayaçlara kaydırılır. Referans 6'da 2 ve 1'in anahtarı eşittir (yalnız sayaçlarında bir tık önceki kullanım var); 1 daha önce yüklendiği için çıkar. 0 ise 5. referansta yeniden kullanıldığı için R'si 1'dir ve korunur. Referans 9 ve 10'da kısa aralıkla iki hata olur: 2 için 3, 3 için 4 atılır. Toplam 10 hata yapılır (Şekil 9.31).

10 hatayla yaşlandırma bu dizide LRU'dan (12) iyidir, OPT'ye (9) çok yakındır. Bu sonuç da genellenmemelidir. Tek bir kısa dizi algoritmaları sıralamaya yetmez; tık sıklığı ya da eşitlik kuralı değişince sonuç değişir.

9.7Çalışma kümesi

Buraya kadarki algoritmalar tek bir soruyu yanıtladı: hangi sayfa çıkmalı? Denning 1968'de soruyu değiştirdi: bir sürecin verimli çalışması için bellekte hangi sayfaları tutması gerekir? Yanıt yine yerellikten gelir ve hem yer değiştirmeye hem de çerçeve tahsisine yön verir.

9.7.1Çalışma kümesi modeli

Bir süreç bir süre küçük bir sayfa grubunu kullanır, sonra başka bir gruba geçer. Örneğin bir fonksiyon çağrıldığında fonksiyonun kodu, yerel değişkenleri ve kullandığı global veriler bir yerellik oluşturur. Fonksiyon dönünce süreç başka bir yerelliğe geçer. Yerellikler birbiriyle örtüşebilir.

Δ'nın seçimi önemlidir. Δ çok küçükse pencere yerelliğin tamamını kapsamaz ve gerekli sayfalar dışarıda kalır. Çok büyükse birkaç yerellik üst üste biner ve küme gereğinden büyür. Δ = ∞ ise çalışma kümesi programın hayatı boyunca dokunduğu bütün sayfalardır. Modelin özü şudur: sürecin çalışma kümesi bellekteyse az hata olur; değilse süreç thrashing'e girer.

Çalışma kümesinin boyutu zamanla dalgalanır: t = 10'dan 37'ye boyutlar 5, 4, 5, 6, 7, 7, 7, 7, 6, 5, 5, 4, 4, 4, 4, 3, 2, 3, 3, 4, … biçiminde gider. Bir yerellikten ötekine geçişte küme geçici olarak büyür, çünkü pencere iki yerelliğin sayfalarını birlikte görür. Yeni yerellik oturunca küme küçülür.

9.7.2Çalışma kümesi algoritması

Kesin tanım, yani son k referansın kümesi, her bellek erişiminde kaydırılan bir yazmaç ister. Bu çok pahalıdır. Uygulanabilir yaklaşım referans sayısı yerine zamanı kullanır: çalışma kümesi, son τ sanal zaman içinde kullanılan sayfalardır. Sanal zaman sürecin kendi CPU süresidir; süreç beklerken akmaz ve saat tıklarıyla ölçülür.

Bütün sayfalar çalışma kümesindeyse, yani R = 0 olanların hepsinin yaşı τ'dan küçükse, R = 0 olanlar arasında en eskisi seçilir. Hiç R = 0 sayfa yoksa rastgele bir sayfa seçilir; tercihen temiz bir sayfa. Algoritmanın dezavantajı her hatada bütün tabloyu taramaktır.

9.7.3WSClock

Çalışma kümesi fikri ile saatin dairesel listesini birleştiren algoritma Carr ve Hennessy'nin 1981 tarihli WSClock'udur. Tam tablo taraması yerine el, çerçeveleri sırayla dolaşır ve ilk uygun kurbanda durur.

Kirli eski sayfanın hemen atılmaması önemlidir. Yazma işi diske verilir, el ise temiz bir sayfa aramayı sürdürür. Yazma bitince sayfa temizlenmiş olur ve sonradan ucuza atılır. El tam bir tur atıp başladığı yere dönerse iki durum vardır:

• En az bir yazma çizelgelendiyse el, yazması biten ilk sayfaya kadar döner ve onu atar.
• Hiç yazma çizelgelenmediyse bütün sayfalar çalışma kümesindedir. Herhangi bir temiz sayfa atılır; o da yoksa elin altındaki sayfa yazılıp atılır.

Tanenbaum'un örneğinde el önce zamanı 2014 olan sayfadadır. R = 1, yani sayfa bu tıkta kullanılmıştır ve iyi bir kurban değildir. R temizlenir, zaman 2204 yapılır, el ilerler. Sıradaki sayfanın zamanı 1213, R'si 0'dır. Yaşı 2204 − 1213 = 991 > τ olduğu için çalışma kümesinde değildir. Temizse kurban olur; kirli olsaydı yazması çizelgelenir ve el ilerlerdi. Yeni sayfa bu çerçeveye zaman 2204 ve R = 1 ile yüklenir. WSClock basit, verimli ve uygulamada yaygın bir tasarımdır.

9.7.4WSClock ortak dizide

WSClock'u ortak dizide çalıştırmak için sanal zaman olarak referans numarası alınır ve τ = 4 seçilir. Yazmalar NRU'dakiyle aynıdır (2., 6., 9., 15. referanslar). Yazması çizelgelenen sayfa, tur sonunda temizlenmiş kabul edilir.

• Referans 4 (2). El 7, 0 ve 1'i sırayla gezer; üçünün de R'si 1'dir. R'ler temizlenir, zamanları 4 yapılır. Tur biter, yazma yoktur. İlk temiz sayfa 7'dir (0 kirlidir) ve 7 çıkar.
• Referans 6 (3*). 0: R = 1 → R = 0, zaman 6. 1: R = 0, yaş 6 − 4 = 2 ≤ τ, çalışma kümesinde. 2: R = 1 → R = 0, zaman 6. Tur biter, yazma yoktur. Elden başlayınca ilk temiz sayfa 1'dir; 1 çıkar.
• Referans 8 ve 9. Aynı biçimde önce 2, sonra 4 ilk temiz sayfa olarak çıkar.
• Referans 14 (1). Bellekte 0*, 3*, 2* vardır; üçü de kirlidir ve R'leri 1'dir. Tur biter, temiz sayfa yoktur: elin altındaki 0 yazılıp atılır (yazma 1).
• Referans 16–18. Her seferinde çalışma kümesinde olmayan temiz bir sayfa bulunamaz; tur sonunda ilk temiz sayfa çıkar: sırasıyla 1, 0, 1.
• Referans 19 (0). 3: R = 0, yaş 19 − 14 = 5 > τ ve kirli: yazması çizelgelenir. 2: yaş 3 ≤ τ. 7: R = 1 → R = 0. Tur biter; yazılan 3 artık temizdir ve kurban olur (yazma 2).
• Referans 20 (1). 7 ilk temiz sayfa olarak çıkar.
• Sonuç. 13 hata, 2 kirli yazma (Şekil 9.35).

13 hata, LRU'dan bile kötü bir sonuçtur. Bunun nedeni örneğin küçüklüğüdür: 3 çerçeveyle her sayfa çalışma kümesindedir ve τ ölçütü hiçbir sayfayı ayırt edemez. Algoritma çoğu hatada tur sonundaki yedek kurala, “ilk temiz sayfa”ya düşer. Çalışma kümesi fikrinin getirisi, binlerce çerçeveli bir bellekte ve uzun bir çalışmada ortaya çıkar.

9.8Algoritmaların karşılaştırması

9.8.1Ortak dizideki sonuçlar

Ortak dizide (3 çerçeve) bütün algoritmaların sonucu yan yana konabilir (Tablo 9.10, Şekil 9.36).

Tablodaki sıralama yanıltıcı olabilir. R ve M bitli algoritmalar, LRU'nun hiç kullanmadığı yazma ve tık bilgisinden yararlanır; kısa tek bir dizi genel bir sıralama vermez. Tanenbaum'un değerlendirmesi uzun ölçümlere dayanır: pratikte en iyi iki algoritma yaşlandırma ve WSClock'tur. NFU ise hiç unutmadığı için LRU'ya iyi yaklaşmaz; iyi yaklaşım yaşlandırmadır.

9.8.2İş yükü politikayı belirler

Bir algoritmanın iyiliği erişim örüntüsüne bağlıdır. Bunu görmek için OSTEP'teki deney tekrarlanabilir. 100 farklı sayfaya 10 000 erişim yapan üç yapay iş yükü vardır. Her biri, çerçeve sayısı 0'dan 100'e kadar değiştirilerek beş politikayla çalıştırılır (Şekil 9.37). Rastgele politika için 5 denemenin ortalaması alınır.

• Yerelliksiz iş yükü. Her erişim 100 sayfadan rastgele seçilir. Geçmiş geleceğe dair hiçbir şey söylemez; LRU, FIFO, saat ve rastgele aynı doğruyu izler ve isabet oranı yaklaşık çerçeve / 100'dür. Yalnız geleceği bilen OPT öndedir. 100 çerçevede bütün sayfalar sığar ve hepsi %99 isabete ulaşır (kalan %1 ilk yüklemelerdir).
• 80-20 iş yükü. Erişimlerin %80'i sayfaların %20'sine gider. Sıcak sayfalar varsa geçmişi kullanan politikalar kazanır. 20 çerçevede OPT %81, LRU %58, saat %56, FIFO ve rastgele yaklaşık %53 isabet verir. Saat LRU'ya çok yakındır; FIFO rastgeleden iyi değildir.
• Döngü iş yükü. 0, 1, …, 49, 0, 1, … sırayla tekrarlanır. Bellekten biraz büyük bir döngü LRU'nun en kötü durumudur. 49 çerçevede atılan sayfa hep en yakında gerekecek olandır ve LRU, FIFO ve saat her erişimde ıskalar: %0. Rastgele %95,5, OPT %97,5 isabet verir. 50 çerçevede döngü sığar ve hepsi %99,5'e çıkar.

Bu deney bu not için Python'da yeniden çalıştırılmıştır. Rastgele sayı üretecine bağlı küçük farklarla aynı sonuçlar çıkar: 80-20'de 20 çerçeve için OPT %80,7, LRU %58,1, saat %55,2, FIFO %52,7, rastgele %52,4; döngüde 49 çerçeve için OPT %97,5, rastgele %95,5, diğerleri %0.

Döngü örüntüsü yalnız yapay bir deney değildir. Büyük bir dosyayı baştan sona bir kez okumak da bir taramadır ve LRU'yu gerçek sistemlerde vurur: bir daha kullanılmayacak dosya sayfaları sıcak sayfaları bellekten kovar. Linux bu yüzden yeni sayfayı önce etkin olmayan listeye koyar ve ancak ikinci erişimde etkin listeye taşır.

9.9Çerçeve tahsisi

Birden çok süreç belleği paylaştığında ikinci soru ortaya çıkar: her sürece kaç çerçeve verilmeli?

9.9.1Eşit ve orantılı tahsis

Tahsisin iki sınırı vardır. Alt sınırı mimari belirler: bir komutun dokunabileceği bütün sayfalar aynı anda bellekte olmalıdır, yoksa komut hiç tamamlanamaz. Komutun kendisi, işlenenleri ve dolaylı adresler sayfa sınırlarını aşabilir. Örneğin IBM 370'in bellekten belleğe taşıma komutu MVC altı çerçeve isteyebilir: komutun kendisi, kaynak blok ve hedef blok ayrı ayrı iki sayfaya taşabilir. Üst sınır ise boş fiziksel bellektir. Bu iki sınır arasında üç yaklaşım vardır.

Öncelikli tahsiste yüksek öncelikli süreç, sayfa hatası yaptığında düşük öncelikli bir sürecin çerçevesini alabilir. Çok programlama derecesi değiştikçe tahsis de değişir: yeni bir süreç gelince herkesin payı biraz azalır. NUMA (bellek erişimi eşit olmayan) sistemlerde bir çerçevenin nerede olduğu da önemlidir. Süreç, çalıştığı işlemci düğümüne yakın bellekten beslenmelidir; uzak düğümün belleği daha yavaştır.

9.9.2Yerel ve genel yer değiştirme

Kurbanın hangi çerçeveler arasından seçileceği de bir karardır.

Genel politika belleği daha verimli kullanır: boşta duran çerçeveler ihtiyacı olana geçer ve toplam verim artar. Bedeli öngörülemezliktir. Bir sürecin çalışma süresi, başka süreçlerin bellek davranışına göre çok değişebilir; aynı program bir gün 10, ertesi gün 30 saniye sürebilir. Yerel politika bu tutarlılığı sağlar, ama bir süreçte boşta duran çerçeveler sıkışan başka bir sürece geçemez. Ayrıca çalışma kümesi büyüyüp küçülürken çerçeve sayısını ayarlayan ayrı bir mekanizma ister; sayfa hatası sıklığı bu mekanizmadır. Linux ve Windows genel geri kazanım kullanır; sınırlar cgroup'lar ve iş nesneleriyle konur.

9.10Thrashing

9.10.1Boşa çabalama

Mekanizma bir kısır döngüdür. Bir sürecin çalışma kümesi belleğe sığmazsa süreç sürekli hata yapar. Attığı sayfa hemen yeniden gerekir; o sayfayı getirmek için başka bir gerekli sayfayı atar. Süreçler zamanlarının çoğunu sayfa beklemekle geçirir, disk kuyruğu dolar, hazır kuyruğu boşalır ve CPU kullanımı düşer.

Durumu kötüleştiren bir geri besleme de vardır. Eski sistemlerin uzun vadeli çizelgeleyicileri CPU kullanımını izler ve düşük kullanımı “CPU boşta, daha çok iş alabiliriz” diye yorumlardı. Yeni süreç sisteme girince herkesin çerçeve payı daha da küçülür, hatalar artar, CPU kullanımı daha da düşer ve çizelgeleyici bir süreç daha ekler. Çok programlama derecesi arttıkça CPU kullanımı önce yükselir, bir noktadan sonra hızla çöker (Şekil 9.40).

Nedenin formülü kısadır: Σ |WS_i| > m, yani çalışma kümelerinin toplamı bellekten büyüktür. Yerel yer değiştirme thrashing'i bir süreçle sınırlar: sıkışan süreç başkalarının çerçevesini çalamaz. Ama sorunu çözmez; o süreç yine thrashing'dedir ve disk kuyruğunu doldurarak başkalarının sayfa hatalarını da yavaşlatır.

Çareler bellekle talep arasındaki dengeyi kurmaya dayanır. Çok programlama derecesi düşürülür: bazı süreçler askıya alınır ya da takasa atılır. RAM eklenir. Son çare, sistemin bellek tükenmesi öldürücüsüdür (OOM, out of memory). Linux'ta belirti vmstat 1 çıktısında görülür: si ve so sütunlarında yüksek takas trafiği, wa sütununda yüksek G/Ç beklemesi. /proc/pressure/memory dosyası (PSI, pressure stall information) bellek baskısını, süreçlerin bellek yüzünden beklediği zamanın yüzdesi olarak verir.

9.10.2Çalışma kümesi ve PFF ile önlemek

Çalışma kümesi stratejisi. İşletim sistemi her sürecin çalışma kümesini izler ve toplam talebi hesaplar: D = Σ |WS_i|. D > m ise thrashing yaklaşıyor demektir ve bir süreç askıya alınır; sayfaları yazılır, çerçeveleri diğerlerine dağıtılır. D yeterince küçükse yeni bir süreç başlatılabilir. Askıdan dönen süreç için önce çalışma kümesini yüklemek, yani ön sayfalama yapmak, dönüşteki hata fırtınasını önler.

Sayfa hatası sıklığı. Çalışma kümesini izlemek pahalıdır. Daha doğrudan bir geri besleme, sürecin hata oranına bakmaktır.

Hata oranı yüksek ama verilecek boş çerçeve yoksa bir süreç askıya alınır ve çerçeveleri dağıtılır. Sayfa hataları ile yerellikler arasında da bir bağ vardır. Süreç yeni bir yerelliğe geçerken hata oranında bir tepe oluşur. Çalışma kümesi yüklenince oran düşer ve bir sonraki geçişe kadar düşük kalır. PFF bu tepeleri “daha çok çerçeve gerek”, sakin dönemleri “fazla çerçeve var” diye okur.

9.10.3Kod izleme: PFF

Aşağıdaki fonksiyon PFF'in basit bir biçimidir. Her sayfa hatasında çağrılır. t şimdiki referans numarası, s->son son hatanın zamanı, C eşiktir. Son hatadan bu yana geçen süre C'den büyükse hatalar seyrektir ve son hatadan beri kullanılmayan sayfalar bırakılır. Küçükse hatalar sıktır ve hiçbir sayfa atılmadan küme büyür.

void pff(Surec *s, int p, int t) {
  if (t - s->son > C) {   /* seyrek hata */
    for (int i = s->n - 1; i >= 0; i--)
      if (s->kume[i].R == 0)
        cikar(s, i);    /* kullanılmadı */
  }
  for (int i = 0; i < s->n; i++)
    s->kume[i].R = 0;     /* sıfırla */
  ekle(s, p);             /* R = 1 ile */
  s->son = t;
}

Seyrek hata dalında döngü kümeyi sondan başa doğru dolaşır. Bu yön bilinçlidir: cikar() bir öğeyi silince arkadaki öğeler bir sola kayar. Baştan sona gezilseydi bir öğe atlanırdı. Ardından bütün R bitleri sıfırlanır, böylece bir sonraki hatada “bu aralıkta kullanıldı mı?” sorusu yeniden sorulabilir. Yeni sayfa R = 1 ile eklenir ve hata zamanı kaydedilir.

Süreç belleksiz başlıyor; C = 2 ve referans dizisi (zaman 1'den 14'e) 1 2 1 3 1 3 1 3 4 4 5 4 5 2'dir (Tablo 9.11).

• t = 1, 2, 4. Aralıklar 1, 1 ve 2'dir; hiçbiri C'yi aşmaz. Hatalar sıktır, hiçbir sayfa atılmaz; küme 3 sayfaya büyür. Aradaki 3. referans (s1) isabettir.
• t = 9. 5–8. referanslar s1 ve s3'e isabet eder ve R bitlerini 1 yapar. s4 hatasında aralık 5 > 2'dir: hatalar seyrektir. Son hatadan beri kullanılmayan (R = 0) tek sayfa s2'dir ve çıkarılır.
• t = 11. Aralık 2 ≤ C. Hiçbir sayfa atılmaz ve küme 4 sayfaya büyür. Süreç yeni bir yerelliğe (s4, s5) geçerken eski sayfalar (s1, s3) hâlâ bellektedir.
• t = 14. 12. ve 13. referanslar s4 ve s5'e isabet eder. s2 hatasında aralık 3 > 2'dir. R = 0 olan s3 ve s1 çıkarılır. Son küme s4 (R = 0), s5 (R = 0), s2 (R = 1)'dir.

14 referansta 6 hata olmuştur. Yerellik 1–3 sayfalarından 4–5 sayfalarına kayınca önce hatalar sıklaşmış ve küme büyümüştür. Sonra seyrek bir hata, eski yerelliğin sayfalarını bırakmanın fırsatı olmuştur. Fonksiyonun maliyeti küme boyutuyla doğrusaldır, O(n); ama yalnız hata anlarında çalışır.

9.11Tasarım konuları

Yer değiştirme algoritması ve tahsis politikası sanal bellek sisteminin yalnız bir kısmıdır. Sistemin gerçekte ne kadar iyi çalışacağını birçok küçük karar belirler: kurban ne zaman aranır, sayfalar önceden getirilir mi, sayfa ne kadar büyük olmalı, programcı ne yapabilir, hangi sayfalar asla atılmamalı?

9.11.1Temizleme politikası ve sayfalama daemonu

Kurbanı ancak sayfa hatası anında aramak, hatayı yapan süreci gereksiz yere bekletir. Kurban kirliyse süreç hem yazmayı hem okumayı bekler. Daha iyi bir yol, boş çerçeveleri önceden hazır tutmaktır.

Önceden yazmanın getirisi şudur: tahliye anı geldiğinde sayfa çoğu zaman temizdir ve hata yalnız bir okuma bekler. Serbest bırakılan çerçeve de hemen silinmez. İçeriği yerinde kalır ve sayfa yeniden gerekirse havuzdan geri alınabilir; bu durumda disk okuması yerine küçük bir hata yeter.

Bu işi saat algoritmasıyla yapmanın bir yolu iki elli saattir. Öndeki el kirli sayfaları yazdırır ve R bitlerini temizler. Arkadaki el belli bir mesafeden onu izler ve hâlâ R = 0 olan, yani iki el arasındaki sürede kullanılmayan sayfaları serbest bırakır. Elleri arasındaki mesafe, bir sayfaya “kullanılmak için” verilen süreyi belirler.

Linux'ta bu daemonun adı kswapd'dir ve bellek bölgesi başına üç su seviyesiyle çalışır: min, low ve high (Şekil 9.43). Boş sayfa sayısı low'un altına inince kswapd uyanır ve sayfaları arka planda geri kazanır. Sayı high'a çıkınca yeniden uykuya döner. Sayı min'in de altına inerse ayırma yapan süreç beklemeden işe girişir ve geri kazanımı kendisi yapar; buna doğrudan geri kazanım denir ve gecikmeyi artırır. Kirli dosya sayfalarını ayrıca writeback iş parçacıkları diske yazar.

9.11.2Ön sayfalama

Talebe bağlı sayfalama, süreç başlarken ve askıdan dönerken bir hata fırtınası yaşar: her sayfa ayrı bir hatayla, ayrı bir G/Ç'yle gelir.

Ön sayfalamanın kârlı olup olmadığı basit bir hesapla görülür. s sayfa önceden getirilsin ve bunların α oranı gerçekten kullanılsın (0 ≤ α ≤ 1). Kazanç α·s sayfa hatasının önlenmesidir. Bedel (1 − α)·s gereksiz sayfanın okunması ve bellekte yer tutmasıdır. α 1'e yakınsa ön sayfalama kazandırır, 0'a yakınsa kaybettirir (Şekil 9.44).

Bu örnekte eşik düşüktür, çünkü toplu okuma çok ucuzdur. Toplu okumanın maliyeti tek tek hatalarınkine yaklaştıkça eşik yükselir. Klasik uygulama, askıya alınan sürecin çalışma kümesini hatırlayıp geri dönüşte yüklemektir. Linux dosyalar için önden okuma (readahead), takas için page-cluster ayarını kullanır. Uygulama da ipucu verebilir: madvise(MADV_WILLNEED) ya da mmap(MAP_POPULATE). Windows'ta Prefetcher ve SysMain (eski adı SuperFetch) sık kullanılan sayfaları sistem boştayken yükler.

9.11.3Sayfa boyutu

Sayfa boyutunu genellikle donanım belirler, ama yeni bir mimari tasarlanırken bu bir seçimdir ve birbirine karşı çeken etkenler vardır (Tablo 9.12).

İki etkeni basit bir modelle tartmak mümkündür. Süreç boyutu s bayt, sayfa tablosu girdisi e bayt, sayfa boyutu p bayt olsun. Sayfa tablosu s/p girdi, yani se/p bayt tutar. Sürecin son sayfası ortalama yarı boş kalır ve p/2 bayt iç parçalanma yaratır.

Kanıt türev almaktır: f′(p) = −se/p² + 1/2 = 0 denkleminden p² = 2se çıkar. İkinci türev pozitif olduğu için bu nokta bir en küçük değerdir.

Model kabadır; TLB'yi ve G/Ç'yi hiç hesaba katmaz. Yine de 4 KB'ın neden onlarca yıl standart kaldığını açıklar. 2026 itibarıyla x86-64 4 KB sayfa kullanır ve 2 MB ile 1 GB'lık büyük sayfaları destekler. Apple Silicon 16 KB sayfa kullanır. Android 15 ve sonrası 16 KB sayfalı çekirdekleri destekler. Bazı ARM64 sunucular 64 KB sayfayla çalışır. 1 KB'lık sayfalar yalnız eski sistemlerde görülür. Eğilim, bellek büyüdükçe sayfanın da büyümesidir.

9.11.4TLB erimi ve büyük sayfalar

Sürecin çalışma kümesi erime sığmıyorsa erişimlerin önemli bir kısmı TLB ıskasıyla sonuçlanır ve zaman sayfa tablosu yürüyüşüne gider. Erimi artırmanın iki yolu vardır. Girdi sayısını artırmak pahalıdır, çünkü TLB ilişkisel bellektir ve her girdi paralel karşılaştırma devresi ister. Sayfayı büyütmek çok daha etkilidir (Şekil 9.46).

x86-64'te büyük sayfalar 2 MB ve 1 GB'dır. Linux iki yol sunar: uygulamanın açıkça istediği hugetlbfs ve çekirdeğin kendiliğinden kullandığı şeffaf büyük sayfalar (THP, transparent huge pages). THP'de khugepaged iş parçacığı ardışık küçük sayfaları arka planda büyük sayfalarda birleştirir. 6.x çekirdekleri ayrıca çok boyutlu folyo ve mTHP desteğiyle 4 KB ile 2 MB arasındaki boyutları da kullanabilir. Windows'ta büyük sayfa kullanmak için özel bir ayrıcalık gerekir.

Büyük sayfanın bedelleri de vardır: iç parçalanma, büyük bitişik fiziksel bölge bulma zorunluluğu (bunun için bellek sıkıştırma gerekebilir), sayfa başına daha uzun kopyalama ve sıfırlama süresi. Büyük sayfadan en çok yararlanan yazılımlar veritabanları ve sanal makinelerdir; ikisi de büyük ve sık erişilen bellek bölgeleri kullanır.

9.11.5Program yapısı ve yerellik

Talebe bağlı sayfalama programcıya görünmez olmalıdır, ama programcının seçimleri hata sayısını büyük ölçüde değiştirebilir. En bilinen örnek iki boyutlu dizinin gezilme sırasıdır. C dizileri satır öncelikli (row-major) saklar: data[i][0], data[i][1], … bellekte ardışıktır.

int data[128][128];   /* satır = 1 sayfa */
/* A: sütun sütun */
for (int j = 0; j < 128; j++)
  for (int i = 0; i < 128; i++)
    data[i][j] = 0;
/* B: satır satır */
for (int i = 0; i < 128; i++)
  for (int j = 0; j < 128; j++)
    data[i][j] = 0;

Dizi 128 × 128 int'tir; sayfa 128 sözcüktür, yani her satır tam bir sayfadır. Sürece 64 çerçeve ayrılmıştır, başta hiçbiri dolu değildir ve yer değiştirme LRU'dur.

Aynı ilke başka boyutlarda da geçerlidir. 64 × 1024'lük bir int dizisinde (her satır 4 KB = bir sayfa) 32 çerçeveyle satır satır doldurma 64, sütun sütun doldurma 64 × 1 024 = 65 536 hata yapar: 1 024 kat fark. Fortran ise dizileri sütun öncelikli saklar ve orada doğru sıra tersidir.

Veri yapısı seçimi de yerelliği etkiler. Yığın iyi yerellik gösterir: erişimler hep tepeye yakındır. Karma tablosu ise erişimleri bilerek dağıtır ve kötü yerellik gösterir. İşaretçi kovalayan bağlı yapılar da düğümleri belleğe dağıttığı için kötüdür. Derleyiciler bazen döngü değiştirme (loop interchange) dönüşümüyle iç ve dış döngünün yerini kendiliğinden değiştirir. Derleyici ve yükleyici de kodu sayfa sınırlarını gözeterek yerleştirebilir: birbirini çağıran fonksiyonları aynı sayfaya koymak gibi.

9.11.6G/Ç kilitleme ve sayfa sabitleme

Bazı sayfaların, en azından bir süre için, kesinlikle atılmaması gerekir. En önemli örnek G/Ç tamponlarıdır.

Sorunun iki çözümü vardır. Birincisi, G/Ç süresince tampon çerçevesini kilitlemektir. İkincisi, G/Ç'yi her zaman çekirdek tamponlarına yapıp veriyi sonra kullanıcı tamponuna kopyalamaktır; bu güvenlidir ama fazladan bir kopya ister.

Sabitlenen başka sayfalar da vardır. Çekirdek kodunun ve verisinin bir kısmı hiç atılmaz; sayfa hatası işleyicisinin kendisi atılsaydı onu kim getirirdi? Gerçek zamanlı süreçler gecikmeye tahammül edemediği için belleklerini mlock() ya da mlockall() ile kilitler. Linux sürücüleri kullanıcı sayfalarını pin_user_pages() ile sabitler; RDMA ağ kartları, GPU'lar ve io_uring'in sabit tamponları bunu kullanır. IOMMU ise aygıtların da çevrilmiş adres kullanmasını sağlar ve yanlış adrese DMA yapılmasını donanımda engeller.

Bir öncelik inceliği de vardır. Düşük öncelikli bir süreç, uzun bir beklemeden sonra sayfasını yeni getirmiş ama henüz hiç çalışmamış olabilir. Bu sayfanın R biti 0'dır ve yüksek öncelikli bir sürecin hatası onu hemen kurban seçebilir. Getirme emeği boşa gider. Bu yüzden yeni yüklenmiş sayfa bir kez kullanılana kadar kilitli tutulabilir.

Kilitlemenin riski de açıktır: kilitli bir sayfa unutulursa çerçeve sonsuza dek kullanılamaz. Çok sayıda kilit belleği daraltır ve thrashing'i kolaylaştırır. Bu yüzden kullanıcının kilitleyebileceği bellek sınırlıdır; Linux'ta sınır ulimit -l ile görülür.

9.12Çekirdek belleği

Kullanıcı süreçlerinin belleği sayfalanır ve boş çerçeve havuzundan gelir. Çekirdeğin kendi belleği ise farklı kurallara uyar. Çekirdek belleğinin çoğu sayfalanmaz, çünkü sayfa hatası işleyicisi gibi kodlar hata almamalıdır. Çekirdek sayfa boyutundan çok daha küçük yapılar ayırır (süreç tanımlayıcıları, dosya nesneleri, semaforlar) ve sayfa düzeyindeki ayırma bunlar için israftır. Bazı aygıtlar DMA için fiziksel olarak bitişik bellek ister, çünkü sanal adresleri bilmezler. Bu ihtiyaçlar için iki ayırıcı kullanılır.

9.12.1Buddy sistemi

Buddy sisteminin asıl güçlü yanı birleştirmedir (coalescing). C_L bırakılınca kardeşi C_R boşsa ikisi B_L'yi yeniden oluşturur; B_R de boşsa A_L oluşur ve bu böyle sürer. Kardeşin adresini bulmak tek bir işlemdir: k boyutlu bir bloğun kardeşinin adresi, blok adresinin k'ya karşılık gelen bitinin çevrilmesiyle bulunur (adres XOR boyut). Linux'un sayfa ayırıcısı bir buddy ayırıcısıdır. 0'dan 10'a kadar mertebe için ayrı boş listeler tutar: 4 KB'tan 4 MB'a kadar. Listelerin durumu cat /proc/buddyinfo ile görülür.

9.12.2Kod izleme: buddy ayırıcı

Aşağıdaki kod buddy ayırıcının özünü gösterir. Boyutlar KB cinsinden 2'nin kuvveti olarak tutulur: ayir(k) 2^k KB'lık bir blok ister. bos[j], 2^j KB'lık boş blokların listesidir. cek(j) listeden bir blok alır, ekle(j, a) listeye ekler, sil(k, b) listede varsa çıkarıp doğru döndürür.

int ayir(int k) {          /* 2^k KB */
  int j = k;
  while (bos[j] == NULL) j++;
  int a = cek(j);
  while (j > k) {   /* böl, sağ yarı boş */
    j--; ekle(j, a + (1 << j));
  }
  return a;
}
void birak(int a, int k) {
  int b = a ^ (1 << k);    /* kardeş */
  while (k < MAX && sil(k, b)) {
    a = a < b ? a : b;     /* birleş */
    k++; b = a ^ (1 << k);
  }
  ekle(k, a);
}

ayir() önce boş blok bulunan en küçük j ≥ k listesini arar ve oradan bir blok çeker. Sonra blok istenen boya inene kadar ikiye bölünür: her bölmede sağ yarı (a + (1 << j)) boş listeye eklenir, sol yarı bölünmeye devam eder. birak() kardeşin adresini a ^ (1 << k) ile bulur. Kardeş aynı boydaki boş listedeyse onu listeden çıkarır, iki bloğun küçük adreslisini yeni blok yapar ve bir üst boyda yeniden dener. Kardeş boş değilse ya da en büyük boya (MAX) ulaşıldıysa blok listeye eklenir.

256 KB'lık bölgeyle (MAX = 8) başlanır ve sırayla A = ayir(5), B = ayir(6), birak(0, 5), birak(64, 6) çağrılır (Tablo 9.13).

• A = ayir(5). 21 KB'lık istek 32 KB'a (2⁵) yuvarlanmıştır. bos[5], bos[6] ve bos[7] boştur; ilk dolu liste bos[8]'dir: j = 8. @0'daki 256 KB'lık blok çekilir. j = 7'de sağ yarı @128, j = 6'da @64, j = 5'te @32 boş listelere girer. j = k olunca döngü biter ve sol yarı, @0'daki 32 KB, A'ya verilir.
• B = ayir(6). bos[6]'da @64 hazırdır; bölme gerekmez. A'nın iç parçalanması 32 − 21 = 11 KB'tır.
• birak(0, 5). Kardeşin adresi tek bit çevrilerek bulunur: 0 ⊕ 32 = 32. @32 bos[5]'tedir; birleşip @0'da 64 KB olurlar. Yeni kardeş 0 ⊕ 64 = 64'tür, ama @64'ü B kullanıyor. Birleşme durur, @0 bos[6]'ya eklenir.
• birak(64, 6). Kardeş 64 ⊕ 64 = 0 boştur; 128 KB'lık @0 oluşur. Yeni kardeş @128 de boştur ve birleşip 256 KB olurlar. k = MAX olduğundan döngü durur; bölge başlangıçtaki gibi tek parçadır.

Ayırma ve bırakma, bölme ve birleşme sayısı kadar adım sürer; bu da en çok mertebe sayısı kadardır, yani O(log n). Boyut başına ayrı boş liste tutulduğu için arama da hızlıdır. Kardeşin adresinin XOR ile bulunması, blokların hep kendi boyutunun katı olan adreslerde başlamasına dayanır.

9.12.3Buddy: istek dizisi örneği

A, B ve C için toplam iç parçalanma 58 + 29 + 48 = 135 K'dır. Buddy ayırma ve birleştirmede hızlıdır, ama en kötü durumda bloğun yaklaşık yarısı boşa gider: 2^k + 1 baytlık bir istek 2^k+1 baytlık blok alır. Bu yüzden küçük nesneler için buddy'nin üstüne ikinci bir ayırıcı kurulur.

9.12.4Slab ayırıcı

Bir slab üç durumdan birindedir: dolu (bütün nesneleri kullanımda), kısmi (bir kısmı kullanımda) ve boş. Nesneler önbellekte önceden kurulmuş durumda bekler; ayırma, listeden bir nesne çekmektir (Şekil 9.51).

Bir isteğin yolu şöyledir. fork() yeni bir task_struct ister. Ayırıcı önce kısmi slablardaki boş bir nesneye bakar; bulursa onu verir. Kısmi slab dolarsa boş slablara geçilir. Kısmi ya da boş slab kalmadıysa buddy ayırıcıdan yeni sayfalar alınır ve yeni bir slab kurulur. Bellek baskısı olduğunda boşalan slablar buddy ayırıcıya geri verilir.

Slab ayırıcıyı Bonwick 1994'te Solaris için tasarladı. Yararları şunlardır:

• Parçalanma yoktur: nesneler tam boyutludur ve sayfa içinde yan yana paketlenir.
• Ayırma ve bırakma O(1)'dir; bırakılan nesne yalnız “boş” işaretlenir.
• Önbellekteki nesneler sıcak ve hazırdır; her ayırmada yeniden kurulmaları gerekmez.
• CPU başına listeler kilitsiz bir hızlı yol sağlar.

Linux'ta slab ayırıcının üç gerçeklemesi uzun süre birlikte yaşadı: SLAB, SLUB ve SLOB. SLOB 6.4 sürümünde, klasik SLAB 6.8 sürümünde (2024) kaldırıldı; bugün tek ayırıcı SLUB'dır. Genel amaçlı kmalloc() de boyut sınıflarına ayrılmış slab önbelleklerinden beslenir. Önbelleklerin durumu slabtop ve /proc/slabinfo ile izlenir.

9.13Gerçek sistemler

9.13.1Linux: sayfa geri kazanımı

Linux'ta geri kazanım su seviyeleriyle tetiklenir. Bir bölgenin boş sayfa sayısı low'un altına inince kswapd uyanır; min'in altına inerse ayırma yapan süreç doğrudan geri kazanım yapar ve gecikme artar.

Klasik Linux geri kazanımı saate benzeyen iki liste çifti kullanır: etkin (active) ve etkin olmayan (inactive) listeler. Anonim ve dosya sayfaları için ayrı birer çift vardır (Şekil 9.52). Yeni sayfa etkin olmayan listeye girer; yeniden erişilirse etkin listeye yükselir. Etkin listenin kuyruğundaki sayfalar yaşlandıkça etkin olmayan listeye iner. Kurbanlar etkin olmayan listenin kuyruğundan seçilir. Anonim kurban takasa ya da zswap'a gider, temiz dosya sayfası yalnız atılır. Kilitli sayfalar için ayrıca atılamaz (unevictable) bir liste vardır.

Bu iki liste düzeni, döngü örüntüsünün LRU'yu vurmasına karşı bir önlemdir: bir kez okunan dosya sayfaları etkin olmayan listede kalır ve sıcak sayfaları kovamaz. vm.swappiness ayarı (0–200) anonim sayfaları takasa atmakla dosya sayfalarını bırakmak arasındaki tercihi belirler. Bellek gerçekten tükenirse OOM öldürücü bir süreci seçip sonlandırır.

9.13.2Linux: MGLRU, zswap ve zram

MGLRU (multi-generational LRU, çok nesilli LRU) 2022'de Linux 6.1 ile geldi. Sayfalar iki liste yerine dört nesle ayrılır. Erişim bitleri sayfa tabloları yürünerek toplu hâlde toplanır; erişilen sayfa en genç nesle taşınır, kurban en yaşlı nesilden seçilir (Şekil 9.53). Sonuç daha az CPU harcaması ve daha iyi kurban seçimidir. MGLRU ChromeOS ve Android'de varsayılandır; birçok dağıtım çekirdeği derleme seçeneğiyle açar. Durumu /sys/kernel/mm/lru_gen/enabled dosyasından okunur.

zswap, takasın önünde duran sıkıştırılmış bir önbellektir. Anonim sayfa diske gitmeden önce RAM'de sıkıştırılır ve bir havuzda tutulur. Havuz dolunca en eski girdiler gerçek takas aygıtına yazılır. zram ise RAM'de sıkıştırılmış bir blok aygıtıdır ve doğrudan takas alanı olarak kullanılır; sayfalar diske hiç gitmez. Fedora 33'ten beri, Android ve ChromeOS zram'ı varsayılan olarak kullanır.

Sıkıştırma CPU harcar, ama diske gitmekten yüzlerce kat ucuzdur. EAT hesabında zram'ın 10 µs'lik hata süresi bunu sayılarla gösterir: p = 0,001'de HDD 251 kat, zram yalnız %10 yavaşlama getirir.

9.13.3Windows: çalışma kümeleri ve sıkıştırma

Windows, Denning'in modelini adıyla kullanır. Her sürecin bir çalışma kümesi vardır ve kümenin en az ve en çok sınırları belirlenmiştir. Sayfa hatası kümede yer açar ya da kümeyi büyütür. Bellek azalınca çalışma kümesi yöneticisi (balance set manager) kümeleri kırpar.

Kırpılan sayfa hemen silinmez (Şekil 9.54). Temizse bekleme (standby) listesine, kirliyse değiştirilmiş (modified) listeye gider. Değiştirilmiş sayfalar yazılınca bekleme listesine geçer. Bekleme listesindeki bir sayfa yeniden istenirse küçük bir hatayla geri alınır. Serbest ve sıfırlanmış listeler yeni ayırmaları besler.

Windows 10 (2015) ile bellek sıkıştırma geldi: kırpılan sayfalar sistem sürecindeki bir sıkıştırma deposunda tutulur; pagefile.sys dosyasına yazmak son çaredir. Önceden getirme işini Prefetcher ve SysMain yapar. Büyük sayfalar VirtualAlloc(MEM_LARGE_PAGES) ile istenir.

macOS ve iOS da benzer bir yol izler: sıkıştırılmış bellek kullanılır. iOS'ta takas hiç yoktur; bellek baskısında sistem, Jetsam mekanizmasıyla arka plandaki uygulamaları sonlandırır. Üç sistemin ortak noktası, diske gitmeden önce bellekte kalan her imkânı denemektir.

9.14Özet

• Sanal bellek mantıksal belleği fiziksel bellekten ayırır. Süreç kısmen bellekteyken çalışır; program fiziksel bellekle sınırlı kalmaz, aynı bellekte daha çok süreç tutulur ve paylaşım kolaylaşır.
• Talebe bağlı sayfalamada sayfa yalnız erişildiğinde getirilir. Geçersiz girdiye erişim sayfa hatası tuzağı üretir. Çekirdek referansı denetler, sayfayı yedekleme deposundan boş bir çerçeveye okur, tabloyu günceller ve komutu yeniden başlatır.
• Linux sayfa hatalarını küçük (G/Ç yok), büyük (diskten okuma) ve geçersiz (SIGSEGV) diye ayırır. Sayfalar dosya destekli, anonim ya da sıfırla doldurulan sayfalardır.
• Etkin erişim süresi EAT = (1 − p) × ma + p × hata süresi'dir. HDD'de (25 ms) p = 0,001 belleği 251 kat yavaşlatır; %10 yavaşlama için p < 4 × 10⁻⁷ gerekir. NVMe ve zram cezayı küçültür, ama yok etmez.
• Yazınca kopyalama, fork() sonrasında sayfaları paylaştırır ve yalnız yazılan sayfayı kopyalar; kopyanın gerekip gerekmediğini çerçevenin referans sayısı belirler. mmap() dosyayı adres alanına eşler; MAP_SHARED değişiklikleri dosyaya, MAP_PRIVATE özel bir kopyaya yazar.
• Boş çerçeve yoksa bir kurban seçilir; kirli kurban önce diske yazılır. Algoritmalar referans dizisi üzerindeki hata sayısıyla karşılaştırılır.
• Ortak dizide (3 çerçeve) OPT 9, yaşlandırma 10, NRU ve geliştirilmiş saat 11, LRU 12, WSClock 13, saat 14, FIFO 15 hata yapar. OPT gerçeklenemez ama alt sınırdır.
• FIFO Belady anomalisi gösterebilir: 1 2 3 4 1 2 5 1 2 3 4 5 dizisinde 3 çerçeve 9, 4 çerçeve 10 hata yapar. LRU ve OPT yığın algoritmalarıdır ve anomali göstermez.
• Tam LRU donanım ister (sayaç, yığın, matris). Pratikte R ve M bitlerine dayalı yaklaşımlar kullanılır: ikinci şans, saat, NRU, geliştirilmiş saat, NFU ve yaşlandırma. Yaşlandırma LRU'ya iyi yaklaşır; NFU hiç unutmadığı için yaklaşamaz.
• Çalışma kümesi WS(t, Δ), son Δ referansta kullanılan sayfalardır. Çalışma kümesi algoritması ve WSClock bu fikri sanal zaman ve τ eşiğiyle gerçekler.
• İş yükü politikayı belirler: yerelliksiz erişimde politikalar eşittir, sıcak sayfalarda LRU kazanır, bellekten biraz büyük döngüde LRU sıfır isabet verir.
• Çerçeveler eşit, orantılı ya da önceliğe göre dağıtılır; kurban yerel ya da genel seçilir. Σ |WS_i| > m olunca thrashing başlar; çalışma kümesi stratejisi ve PFF çok programlama derecesini ayarlayarak onu önler.
• Tasarım kararları: sayfalama daemonu ve su seviyeleri, ön sayfalama (α eşiği), en uygun sayfa boyutu √(2se), TLB erimi ve büyük sayfalar, satır öncelikli gezme, G/Ç tamponlarının sabitlenmesi.
• Çekirdek belleği buddy ayırıcıyla 2'nin kuvveti bloklar hâlinde ayrılır ve kardeşler XOR ile bulunup birleştirilir; küçük nesneler için slab (Linux'ta SLUB) kullanılır.
• Linux etkin/etkin olmayan listeler, MGLRU, zswap ve zram; Windows çalışma kümeleri, bekleme listeleri ve bellek sıkıştırma kullanır.

9.15Kavram listesi

• sanal bellek virtual memory
• sanal adres virtual address
• talebe bağlı sayfalama demand paging
• sayfa hatası page fault
• yedekleme deposu (takas alanı) backing store (swap space)
• etkin erişim süresi effective access time
• yazınca kopyalama copy-on-write
• bellek eşlemeli dosya memory-mapped file
• sayfa önbelleği page cache
• sayfa yer değiştirme page replacement
• referans dizisi reference string
• referans biti / kirli bit reference bit / dirty bit
• Belady anomalisi Belady's anomaly
• optimal algoritma (OPT) optimal page replacement
• en uzun süredir kullanılmayan (LRU) least recently used
• ikinci şans second chance
• saat algoritması clock algorithm
• yaşlandırma aging
• yerellik locality
• çalışma kümesi working set
• thrashing (boşa çabalama) thrashing
• TLB translation lookaside buffer
• iç parçalanma internal fragmentation
• buddy (kardeş) sistemi buddy system
• slab ayırıcı slab allocator
• sıkıştırma compression

9.16Kendini Dene

1. Referans dizisi 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6, çerçeve sayısı 4. FIFO, LRU ve OPT kaçar sayfa hatası yapar?

   Cevap

   FIFO 14, LRU 10, OPT 8. LRU'nun kurbanları sırasıyla 3, 4, 5, 6, 1, 7; OPT'ninkiler 4, 5, 1, 7'dir. 7 farklı sayfa olduğu için en az 7 hata kaçınılmazdır; OPT buna çok yaklaşır. 3 çerçeveyle sonuçlar FIFO 16, LRU 15, OPT 11'dir.

2. Bellek erişimi 50 ns, sayfa hatası hizmet süresi 10 ms. Yavaşlamanın %20'yi geçmemesi için p en çok ne olabilir?

   Cevap

   %20 yavaşlama EAT < 60 ns demektir. 10 ms = 10 000 000 ns. 60 > 50 + (10 000 000 − 50) p → p < 10 / 9 999 950 ≈ 1,0 × 10⁻⁶: yaklaşık bir milyon erişimde birden az hata.

3. Dört boş çerçeve ve 1 2 3 4 1 5 2 6 1 3 dizisiyle saat algoritması (el başta çerçeve 0'da, el yalnız hatada döner) kaç hata yapar? Hangi sayfalar çıkar?

   Cevap

   8 hata. İlk dört referans boşlara yüklenir; 1 isabettir. 5 gelince dört sayfanın da R'si 1'dir; el hepsini temizleyip bir tur atar ve 1'i çıkarır. 2 isabettir (R ← 1). 6 gelince el 2'nin R'sini temizler ve R'si 0 olan 3'ü çıkarır. 1 gelince elin altındaki 4 (R = 0) çıkar. 3 gelince el 5'in R'sini temizler, 2'yi çıkarır. Kurbanlar 1, 3, 4, 2'dir.

4. Referans dizisi (zaman 1'den) 1 2 1 3 2 4 4 5 4 5 6 1, Δ = 4. W(4), W(8) ve W(12) nedir?

   Cevap

   W(4) = {1, 2, 3} (1 2 1 3), W(8) = {2, 4, 5} (2 4 4 5), W(12) = {1, 4, 5, 6} (4 5 6 1). Kümeler süreç yeni sayfalara geçtikçe kayar; W(12) bir yerellik geçişi sırasında büyümüştür.

5. 2 048 girdili bir TLB'nin 16 KB'lık sayfalarla erimi nedir? Çalışma kümesi 48 MB olan bir süreç için yeterli midir?

   Cevap

   2 048 × 16 KB = 32 768 KB = 32 MB. 48 MB'lık çalışma kümesi sığmaz; erişimlerin bir kısmı TLB ıskasıyla sayfa tablosu yürüyüşüne gider. 2 MB'lık büyük sayfalar erimi 4 GB'a çıkarırdı.

6. Süreç boyutu 2 MB, sayfa tablosu girdisi 4 bayt. Ek maliyet se/p + p/2 modeline göre en uygun sayfa boyutu nedir?

   Cevap

   p = √(2se) = √(2 × 2²¹ × 2²) = √(2²⁴) = 2¹² = 4 KB.

7. 128 K'lık bir buddy bölgesinde sırayla A = 10 K, B = 30 K, C = 20 K isteniyor; sonra A ve C bırakılıyor. Her istek nereye yerleşir, toplam iç parçalanma nedir, en sonda boş bloklar nelerdir?

   Cevap

   A 16 K'ya yuvarlanır: 128 → 64 + 64 → 32 + 32 → 16 + 16; A 0–16'yı alır (6 K). B 32 K: boş 32–64 hazırdır (2 K). C 32 K: boş 64–128 bölünür, C 64–96'yı alır (12 K). Toplam 20 K. A bırakılınca kardeşi 16–32 boştur, 0–32 oluşur; onun kardeşinde B vardır, dur. C bırakılınca kardeşi 96–128 boştur, 64–128 oluşur; kardeşi 0–64 bölünmüştür, dur. Boş bloklar 0–32 ve 64–128; B 32–64'tedir.

8. fork() sonrasında 50 sayfa yazınca kopyalamayla paylaşılıyor. Çocuk 0–4 numaralı sayfalara yazıyor; ardından ebeveyn 0, 1 ve 10 numaralı sayfalara yazıyor. Kaç sayfa kopyalanır?

   Cevap

   6. Çocuğun beş yazması beş kopya üretir. Ebeveyn 0 ve 1'e yazdığında bu çerçevelerin referans sayısı artık 1'dir; kopya gerekmez, sayfa yalnız yazılabilir yapılır. Sayfa 10 hâlâ paylaşılıyordur (referans sayısı 2) ve altıncı kopyayı üretir.

9. Üç sayfanın (s0, s1, s2) 8 bitlik yaşlandırma sayaçları başta 0. Dört tıkta görülen R bitleri: tık 0: 1 1 0, tık 1: 1 0 1, tık 2: 0 1 1, tık 3: 0 1 0. Yaşlandırma ve NFU hangi sayfayı atar?

   Cevap

   Sayaçlar s0 = 00110000 (48), s1 = 11010000 (208), s2 = 01100000 (96). Yaşlandırma s0'ı atar: son iki tıkta hiç kullanılmamıştır. NFU sayaçları 2, 3, 2'dir; s0 ile s2 eşittir ve NFU ikisini ayırt edemez. Oysa s2 bir tık önce kullanılmıştı ve daha yenidir.

10. Bir sunucuda CPU kullanımı %10'a düştü, takas diski sürekli meşgul. Bir yönetici “CPU boşta” diyerek kuyruğa yeni toplu işler eklemek istiyor. Ne olur? Doğru müdahale nedir?

    Cevap

    Sistem thrashing'dedir: Σ |WS_i| belleği aşmıştır ve süreçler sayfa bekliyor. Yeni iş her sürecin çerçeve payını daha da küçültür, hatalar artar ve CPU kullanımı daha da düşer. Doğrusu çok programlama derecesini düşürmektir: bazı süreçleri askıya almak ya da takasa atmak, kalıcı çözüm olarak RAM eklemek. PFF bu kararı süreç başına hata oranıyla otomatik verir.

9.17İleri okuma

• R. H. Arpaci-Dusseau ve A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, “Swapping: Mechanisms”, “Swapping: Policies” ve “Complete VM Systems” bölümleri: yer değiştirme politikalarını yerelliksiz, 80-20 ve döngü iş yükleriyle karşılaştırır, VAX/VMS ve Linux'un sanal bellek tasarımını anlatır; ostep.org'da ücretsizdir.
• P. J. Denning, “The Working Set Model for Program Behavior”, Communications of the ACM, 11(5), 1968: çalışma kümesi kavramını ve thrashing'e karşı kullanımını ortaya koyan temel makaledir.
• J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator”, USENIX Summer 1994: nesne önbelleği fikrini ve Solaris'teki ölçümleri kısa ve okunaklı bir biçimde verir.
• Linux çekirdek belgeleri, admin-guide/mm/multigen_lru.rst ve admin-guide/mm/zswap.rst: MGLRU'nun nesillerini ve zswap'ın ayarlarını çekirdeğin kendi belgesinde anlatır.

9.18Kaynaklar

1. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018 — Bölüm 10: Virtual Memory.
2. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı (2014) / 5. baskı (2023), Pearson — Bölüm 3: Memory Management.
3. R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), ostep.org — “Swapping: Mechanisms”, “Swapping: Policies”, “Complete VM Systems”.
4. L. A. Belady, “A Study of Replacement Algorithms for a Virtual-Storage Computer”, IBM Systems Journal 5(2), 1966; P. J. Denning, “The Working Set Model for Program Behavior”, CACM 11(5), 1968.
5. R. W. Carr, J. L. Hennessy, “WSCLOCK — A Simple and Effective Algorithm for Virtual Memory Management”, SOSP 1981; J. Bonwick, “The Slab Allocator”, USENIX Summer 1994.
6. Linux çekirdek belgeleri: admin-guide/mm/multigen_lru.rst, admin-guide/mm/zswap.rst, admin-guide/mm/transhuge.rst, admin-guide/blockdev/zram.rst.
7. P. Yosifovich, A. Ionescu, M. Russinovich, D. Solomon, Windows Internals, 7. baskı, Kısım 1, Bölüm 5: Memory management.