Bölüm 8: Bellek Yönetimi

8.1Bellek donanımı

Bellek yönetimini anlamak için önce belleğin kendisine bakmak gerekir. İşletim sistemi belleği soyut bir bayt dizisi olarak görür, ama bu dizinin arkasında hızları ve boyutları çok farklı birkaç katman vardır. Hangi katmanı donanımın, hangisini işletim sisteminin yönettiğini bilmek, sonraki bütün tasarım kararlarını açıklar.

8.1.1Bellek hiyerarşisi ve bellek yöneticisi

İşlemcinin doğrudan erişebildiği depolama yalnız iki yerdedir: yazmaçlar ve ana bellek. Bir komut, işlenenini yazmaçtan ya da bellekten alır; diskteki bir veriye ise doğrudan erişemez. Diskteki veri önce bir giriş/çıkış işlemiyle belleğe getirilmelidir. Bu yüzden çalışan bir programın kodu ve kullandığı veriler ana bellekte bulunmak zorundadır.

Bellek birimi de çok basit bir arayüz sunar. Ona yalnız bir adres akışı gelir: ya “şu adresi oku” ya da “şu adrese şu veriyi yaz”. Bellek birimi adresin nereden geldiğini bilmez. Adres bir komut sayacından, bir dizi indisinden ya da bir işaretçiden üretilmiş olabilir; bellek için hepsi aynıdır. Bu sadelik, adresleri belleğe varmadan önce değiştiren bir donanım katmanının neden mümkün olduğunu da gösterir.

Hız farkı ise çok büyüktür. Yazmaç bir saat turunda okunur. Ana bellekteki bir DRAM erişimi ise yüzlerce tur sürer ve bu sırada işlemci durur (stall). Aradaki boşluğu işlemcinin içindeki küçük ve hızlı bellekler, yani önbellekler (cache) kapatır. Şekil 8.1 bugünkü tipik değerleri gösterir: yazmaçlar bir nanosaniyenin altında, L1 ve L2 önbellek 1–5 ns, L3 10–20 ns, DRAM 80–120 ns, NVMe SSD 10–100 µs, sabit disk 5–10 ms. Yukarıdan aşağı inildikçe gecikme ve kapasite artar, bayt başına maliyet düşer.

Programcının bellekten beklentisi aslında gerçekleşmesi imkânsız bir listedir: belleğin sınırsız, çok hızlı, kalıcı ve korumalı olması. Tek bir teknoloji bu özelliklerin hepsini birden veremez. Gerçek çözüm hiyerarşidir. Küçük ve hızlı katmanlar sık kullanılan veriyi tutar, büyük ve yavaş katmanlar geri kalanını. İyi kurulmuş bir hiyerarşi programcıya “neredeyse en üst katman kadar hızlı, neredeyse en alt katman kadar büyük” bir bellek izlenimi verir.

Hiyerarşinin katmanlarını farklı yöneticiler denetler. Önbellekleri tamamen donanım yönetir; işletim sistemi onların içeriğine karışmaz. Ana belleği ise işletim sistemi yönetir. İşletim sisteminin bu işle uğraşan kısmına bellek yöneticisi denir.

Bellek yöneticisinin işi ile işlemci çizelgeleyicisinin işi sık karıştırılır. Hazır kuyruğundan sıradaki süreci seçmek çizelgeleyicinin görevidir. Bellek yöneticisi ise “hangi süreç nerede, ne kadar yer kaplıyor, kime ne kadar daha yer verilebilir” sorularıyla ilgilenir.

8.1.2Ana bellek türleri

“Bellek” sözcüğü gündelik dilde birkaç farklı donanım için kullanılır. Tablo 8.1'de dört temel tür karşılaştırılmıştır. Ana bellek olarak kullanılan tür RAM'dir (random access memory, rastgele erişimli bellek). RAM okunur ve yazılır, hızlıdır, ama uçucudur: güç kesilince içeriği kaybolur. DRAM hücreleri küçük kondansatörlerdir ve yük sızdığı için düzenli aralıklarla yenilenmeleri gerekir. SRAM ise yenileme istemez, daha hızlıdır ama daha pahalıdır ve daha çok yer kaplar. Bu yüzden ana bellek DRAM (bugün DDR5, LPDDR5X), önbellekler SRAM'dir.

ROM (read-only memory) üretim sırasında yazılır ve sonradan değiştirilemez. Kalıcıdır ve ucuzdur; basit aygıtlarda ve mikrodenetleyicilerde değişmeyecek kodu tutar. EEPROM ve onun bir türü olan flash bellek elektrikle silinip yeniden yazılabilir. Kalıcıdırlar, ama yazma işlemi okumadan çok yavaştır ve bir hücre ancak sınırlı sayıda yazılabilir. Bugünkü bilgisayarlarda BIOS/UEFI kodu ROM'da değil, anakarttaki bir SPI flash yongasında durur; ürün yazılımının güncellenebilmesi bundandır. SSD'ler, USB bellekler ve telefonların depolaması da NAND flash kullanır. Son olarak CMOS ya da NVRAM, bir pil ya da flash ile korunan küçük bir alandır; saat ve önyükleme ayarları burada tutulur.

Bellek yönetiminin konusu bu türlerden yalnız biridir: süreçlerin çalıştığı ana bellek, yani DRAM. Notun geri kalanında “bellek” sözcüğü bu anlamda kullanılır.

8.1.3Önbellek satırları ve yerellik

Önbellek ile ana bellek arasında veri tek tek baytlar hâlinde değil, sabit boyutlu bloklar hâlinde taşınır. Bu bloğa önbellek satırı (cache line) denir. Bugünkü işlemcilerin çoğunda satır 64 bayttır. Bellek bu boyutta ardışık satırlara bölünmüş gibi düşünülür: satır 0, 0–63 adreslerini; satır 1, 64–127 adreslerini kapsar ve böyle sürer.

Bir a adresinin hangi satırda olduğu basit bir bölmeyle bulunur. Satır numarası ⌊a / 64⌋, satır içindeki konum a mod 64'tür. 64 = 2⁶ olduğu için bu bölme gerçekte bir bit ayırma işlemidir: adresin alt 6 biti satır içi konumu, geri kalan üst bitleri satır numarasını verir. Şekil 8.2 200 adresini örnek alır. 200 ikili tabanda 11001000'dır. Alt altı bit 001000, yani 8; üst iki bit 11, yani 3'tür. Gerçekten de 3 × 64 + 8 = 200.

İşlemci bir sözcük okurken donanım önce önbelleğe bakar. Satır önbellekte varsa buna isabet (hit) denir ve veri L1'den 4–5 turda gelir. Yoksa ıska (miss) olur; istek bir alt düzeye, en kötü durumda DRAM'e iner ve yüzlerce tur sürer. Önbellek pahalı olduğu için küçüktür. Tek bir büyük önbellek yerine L1, L2, L3 gibi birbirinden büyük ve yavaş düzeyler kurulur.

Küçük bir önbelleğin büyük bir belleğin önünde işe yaramasının nedeni programların davranışıdır. Programlar belleğe rastgele erişmez; erişimlerde iki düzen vardır.

Zamansal yerellik (temporal locality)

Az önce kullanılan bir veri kısa süre içinde yine kullanılır. Döngü sayacı, döngü gövdesinin komutları ve sık çağrılan bir fonksiyon böyledir.

Uzamsal yerellik (spatial locality)

Bir adrese erişen program kısa süre içinde komşu adreslere de erişir. Bir diziyi baştan sona gezmek, ardışık komutları yürütmek böyledir.

Önbellek satırı uzamsal yerelliği kullanır: bir baytlık ıskada 64 baytın tamamı getirildiği için komşu baytlara sonraki erişimler isabet olur. Zamansal yerelliği ise satırın önbellekte kalması kullanır.

8.1.4Bir okumanın hiyerarşideki yolu

İşlemci LOAD R1, [x] komutuyla x değişkenini okumak istesin. Donanım önce en yakın ve en hızlı düzeye, L1'e bakar. Satır L1'de yoksa yaklaşık 1 ns kaybedilmiştir ve arama L2'de sürer. L2'de de, L3'te de ıska olursa, düzeylerin gecikmeleri toplanır: 1 + 4 + 15 = 20 ns. Sonunda veri DRAM'den gelir; bu da yaklaşık 80 ns ekler ve toplam 100 ns'yi bulur (Şekil 8.3).

DRAM'den gelen tek bir sözcük değil, sözcüğün bulunduğu 64 baytlık satırın tamamıdır. Satır yolda L3'e, L2'ye ve L1'e de yerleştirilir. Aynı satırdaki başka bir veriye ikinci kez erişildiğinde artık L1 isabeti olur ve yaklaşık 1 ns yeter (Şekil 8.4). İlk erişimin 100 ns'lik bedeli, satırın geri kalanına yapılan erişimlerle paylaşılmış olur. Önbelleği işe yarar kılan yerellik budur.

8.1.5Kod izleme: doğrudan eşlemeli önbellek

Bir satır önbelleğin hangi yerine konabilir? En basit cevap doğrudan eşlemedir (direct mapping): önbellek birkaç kümeye bölünür ve her blok yalnız tek bir kümeye gidebilir. Blok numarası b, küme sayısı K ise blok b mod K kümesine yerleşir. Kümede o anda başka bir blok varsa yeni gelen onu dışarı atar.

Aşağıdaki C parçası dört kümeli, 64 baytlık satırlı bir doğrudan eşlemeli önbelleği taklit eder. etiket dizisi her kümede o anda hangi bloğun bulunduğunu tutar; −1 boş demektir.

int adres[6] = {0, 8, 64, 256, 0, 72};
int etiket[4] = {-1, -1, -1, -1};
int isabet = 0, iska = 0;
for (int i = 0; i < 6; i++) {
  int blok = adres[i] / 64;
  int kume = blok % 4;
  if (etiket[kume] == blok) isabet++;
  else { etiket[kume] = blok; iska++; }
}

Döngü her adres için önce blok numarasını (adres / 64), sonra kümeyi (blok % 4) hesaplar. Kümedeki etiket bu blokla aynıysa isabet sayacı artar. Değilse blok kümeye yazılır ve ıska sayacı artar. Bu basitleştirilmiş modelde etiket olarak blok numarasının tamamı saklanır. Gerçek donanım küme numarasını adresten zaten bildiği için yalnız üst bitleri, yani gerçek etiketi saklar.

Döngü bittiğinde isabet = 2, iska = 4 olur; isabet oranı %33'tür. İzlemede iki farklı ıska türü görülür. İlk üç ıska kaçınılmazdır: bloklar önbelleğe ilk kez gelir. Bunlara zorunlu ıska denir. 3. ve 4. adımlardaki ıskalar ise başka nedenlidir. 0 ve 256 adresleri farklı bloklardadır (0 ve 4), ama ikisi de 0. kümeye düşer. Önbelleğin 2. ve 3. kümeleri boş durduğu hâlde bu iki blok birbirini kovar. Bu tür ıskaya çakışma ıskası (conflict miss) denir.

Çakışma ıskalarını azaltmanın yolu, bir bloğa birden çok yer tanımaktır. k yollu küme ilişkili (k-way set associative) önbellekte her küme k satır tutar. Blok yine tek bir kümeye gider, ama o kümenin k yerinden herhangi birine yerleşebilir.

8.1.6Kod izleme: ortalama erişim süresi

Bir hiyerarşinin ne kadar iyi çalıştığını tek bir sayıyla özetlemek mümkündür: ortalama bellek erişim süresi. Her erişim önce en üst düzeye uğrar ve o düzeyin süresini harcar. Iska olursa istek bir alt düzeye iner ve onun ortalama süresi eklenir. Bir düzeyin süresi s, ıska oranı m, altındaki düzeyin ortalama süresi T_alt ise:

T = s + m · T_alt

Formül kendini tekrar eder: alttaki düzeyin süresi de aynı biçimde hesaplanır. En alttaki DRAM her isteği karşıladığı için orada T yalnız DRAM'in süresidir. Aşağıdaki kod hesabı alttan yukarı doğru yapar.

/* L1, L2, L3, DRAM erişim süresi (ns) */
double sure[4] = {1, 4, 20, 80};
double iska[3] = {0.10, 0.40, 0.50};
double t = sure[3];         /* DRAM */
for (int k = 2; k >= 0; k--)
  t = sure[k] + iska[k] * t;
printf("ortalama = %.1f ns\n", t);

t önce DRAM'in 80 ns'siyle başlar. Döngü k = 2'den (L3) k = 0'a (L1) iner ve her turda bir üst düzeyin süresini hesaplar. Tablo 8.3 her turu gösterir.

Sonuç dikkat çekicidir. Her erişimin %10'u L1'i ıskaladığı hâlde ortalama 3,8 ns'dir. Bu, DRAM'in 80 ns'sinden yaklaşık 21 kat hızlıdır (80 / 3,8 ≈ 21,05). Hiyerarşiyi işe yarar kılan, üst düzeylerdeki yüksek isabet oranıdır.

Formülün biçimi ıska oranlarının ne kadar etkili olduğunu da gösterir. L1'in ıska oranı %10'dan %5'e inerse, alttaki 28 ns aynı kalır ve ortalama 1 + 0,05 × 28 = 2,4 ns olur. L1'in kendi süresini 1 ns'den 0,5 ns'ye indirmek ise yalnız 0,5 ns kazandırır. Ortalamaya ıskalar hâkimdir.

8.1.7Önbellek tasarımının dört sorusu

Her önbellek tasarımı dört soruya cevap vermek zorundadır.

1. Veri ne zaman önbelleğe konur? Genellikle ıska anında. Donanım ayrıca, erişim düzenini tahmin ederek sıradaki satırları önceden de getirir (prefetch).
2. Hangi satıra konur? Bu eşleme sorusudur: doğrudan eşlemeli, k yollu küme ilişkili ya da tam ilişkili.
3. Yer gerekince hangisi çıkar? Bu değiştirme politikasıdır: LRU'ya yakın yaklaşımlar, rastgele seçim ya da FIFO.
4. Çıkan satır nereye gider? Satır değiştirilmişse (“kirli” ise) çıkarken alt düzeye yazılır (write-back). Diğer seçenek her yazmayı hemen alt düzeye iletmektir (write-through).

Bu dört sorunun yanında üç ödünleşim vardır. Büyük önbellek daha çok isabet verir, ama daha yavaş ve daha pahalıdır. Daha akıllı bir değiştirme politikası isabeti artırır, ama donanımı karmaşıklaştırır. Çok çekirdekli işlemcilerde aynı satırın farklı çekirdeklerdeki kopyalarının güncel tutulması gerekir; buna tutarlılık denir ve MESI gibi protokollerle sağlanır.

Aynı dört soru yalnız donanım önbelleklerine özgü değildir. İşletim sisteminin yönettiği “önbelleklerde” de karşımıza çıkar: dosyaların tutulduğu sayfa önbelleğinde, sanal bellekte ve TLB'de. Bu notta anlatılacak TLB doğrudan bir önbellektir; sanal bellek ise ana belleği diskin önbelleği gibi kullanır.

8.2Adres alanı

Birden çok programın aynı bellekte güvenle çalışabilmesi için iki problemin çözülmesi gerekir. Birincisi korumadır: bir program başka bir programın belleğine erişememelidir. İkincisi yer değiştirmedir: bir program belleğin neresine yüklenirse yüklensin doğru çalışmalıdır. Bu kesim, iki problemin nereden çıktığını ve en basit donanım çözümünü anlatır.

8.2.1Soyutlama olmadan bellek

İlk bilgisayarlarda bellek için hiçbir soyutlama yoktu. 1960'lardan önceki ana çerçevelerde ve 1980'lerden önceki kişisel bilgisayarlarda her program fiziksel belleği olduğu gibi görürdü. MOV REGISTER1, 1000 komutu, fiziksel 1000 adresindeki sözcüğü okurdu. Programın gördüğü adres ile bellek yongasının gördüğü adres aynıydı.

Bu düzende bellekte aynı anda iki program bulunamaz. İkisi de aynı fiziksel adresleri kullanır ve biri ötekinin verisini ezer. Bellek yine de işletim sistemi ile tek bir kullanıcı programı arasında paylaşılabilir. Şekil 8.7 üç yaygın düzeni gösterir. (a)'da işletim sistemi RAM'in alt ucundadır. (b)'de işletim sistemi üst uçta, ROM'dadır. (c)'de aygıt sürücüleri üstte ROM'da, işletim sisteminin geri kalanı altta RAM'dedir. (a) ve (c) düzenlerinde kullanıcı programındaki bir hata işletim sisteminin bulunduğu bölgeye yazıp onu çökertebilir. (b) bazı gömülü sistemlerde, (c) ise MS-DOS çalıştıran ilk PC'lerde kullanıldı; orada BIOS sürücüleri ROM'daydı.

Bu yaklaşım tarihe karışmış değildir. Bellek yönetim birimi olmayan mikrodenetleyiciler bugün de böyle çalışır. Bunların çoğunda yine de bir bellek koruma birimi (memory protection unit, MPU) bulunur. MPU adres çevirisi yapmaz, yalnız belirli bölgelere erişim izinlerini denetler.

8.2.2Yer değiştirme problemi

İki programı aynı anda belleğe koymaya çalışınca ortaya çıkan sorunu Tanenbaum'un örneği açıkça gösterir. A ve B, 16 KB'lık iki programdır ve ikisi de 0 adresinden başlayacağı varsayılarak derlenmiştir. A'nın ilk komutu JMP 24, B'nin ilk komutu JMP 28'dir. İşletim sistemi A'yı 0 adresine, B'yi hemen üstüne, 16384 adresine yükler.

A sorunsuz çalışır. B ise ilk komutunda çöker. JMP 28, B'nin 28. baytındaki CMP komutuna atlamak ister. Ama 28 mutlak bir adrestir ve fiziksel 28 adresinde A'nın ADD komutu vardır. B, kendi kodu yerine A'nın ortasına atlar (Şekil 8.8).

Bu probleme yer değiştirme (relocation) problemi denir. Programdaki adresler, programın belleğe yüklendiği yere göre düzeltilmelidir. IBM 360'ın bulduğu ilk çözüm statik yer değiştirmedir: yükleyici programı belleğe koyarken her adres sözcüğüne programın başlangıç adresini ekler. B 16384'e yüklendiği için JMP 28, JMP 16412 olur (Şekil 8.9).

Statik yer değiştirmenin iki zayıf yanı vardır. Birincisi yükleme yavaşlar, çünkü programın her sözcüğüne bakılması gerekir. İkincisi daha ince bir sorundur: yükleyici hangi sözcüğün adres, hangisinin sıradan bir sayı olduğunu bilemez. B'nin ikinci komutu MOV REG1, 28, yazmaca 28 sayısını yükler. Bu 28 bir adres değildir; 16384 eklenirse program yanlış çalışır. Yükleyicinin doğru karar verebilmesi için derleyicinin, programın hangi sözcüklerinin adres olduğunu gösteren ek bir yer değiştirme bilgisi üretmesi gerekir.

8.2.3Taban ve limit yazmaçları

Koruma ve yer değiştirme problemlerini birlikte çözen soyutlama adres alanıdır.

Adres alanını gerçeklemenin en basit donanımı iki yazmaçtır. Taban yazmacı (base register) sürecin bellekteki başlangıç adresini, limit yazmacı (limit register) bölgenin uzunluğunu tutar. Program bellekte bitişik bir alana olduğu gibi yüklenir. Şekil 8.10 örneğinde taban 300040, limit 120900'dür. Süreç 300040 ile 300040 + 120900 − 1 = 420939 arasındaki adreslere erişebilir.

Bu iki yazmaç ayrıcalıklı komutlarla, yalnız çekirdek modunda yüklenebilir. Kullanıcı programı kendi tabanını ya da limitini değiştiremez; değiştirebilseydi koruma anlamsız olurdu. İşletim sistemi bağlam değiştirirken yeni sürecin taban ve limit değerlerini bu yazmaçlara koyar.

Tarihte bu düzenin iki uç örneği vardır. CDC 6600 süper bilgisayarı tam olarak böyle çalışıyordu. Intel 8088'in kesim yazmaçları ise yalnız taban işlevi görüyordu; limit yazmacı olmadığı için yer değiştirme vardı ama koruma yoktu.

8.2.4Donanımsal adres koruması

Taban ve limit yazmaçları korumayı her bellek erişiminde iki karşılaştırmayla sağlar. İşlemcinin ürettiği adres önce tabanla karşılaştırılır: adres tabandan küçükse tuzak oluşur. Sonra taban + limit ile karşılaştırılır: adres bu değerden küçük değilse yine tuzak oluşur. İki koşul da sağlanırsa erişim belleğe gider (Şekil 8.11). Karşılaştırmaları paralel çalışan özel donanım yapar ve erişimi yavaşlatmaz.

Tuzak oluşunca denetim çekirdeğe geçer. Çekirdek bunu adresleme hatası sayar ve süreci genellikle sonlandırır; Unix sistemlerinde süreç SIGSEGV sinyali alır. Denetim yalnız kullanıcı modundaki erişimler için yapılır. Çekirdek modunda denetim yoktur, çünkü işletim sisteminin bütün belleğe erişebilmesi gerekir: bir süreci belleğe yüklemek, bir sistem çağrısının argümanını kullanıcı tamponundan okumak bunu gerektirir.

8.2.5Adres bağlama zamanları

Bir program kaynak koddan bellekteki sürece giden yolda birkaç aşamadan geçer (Şekil 8.12). Derleyici main.c'yi nesne dosyasına (main.o) çevirir. Bağlayıcı bu dosyayı diğer nesne dosyaları ve statik kütüphanelerle birleştirip çalıştırılabilir dosyayı (a.out) üretir. Yükleyici bu dosyayı belleğe alır, dinamik kütüphaneleri ekler ve süreç çalışmaya başlar.

Adresler bu yolculuk boyunca biçim değiştirir. Kaynak kodda adresler semboliktir: programcı count adlı bir değişken yazar. Derleyici bu sembolü göreli bir adrese bağlar: “bu modülün başından 14 bayt sonra”. Bağlayıcı ya da yükleyici de göreli adresi mutlak bir adrese çevirir, örneğin 74014. Bir sembolün mutlak adrese ne zaman bağlandığı, programın bellekte taşınıp taşınamayacağını belirler. Tablo 8.5 üç seçeneği karşılaştırır.

Derleme zamanında bağlamada derleyici programın belleğe nereye yükleneceğini önceden bilir ve mutlak kod üretir. MS-DOS'un .COM dosyaları böyleydi. Başlangıç adresi değişirse program yeniden derlenmelidir. Yükleme zamanında bağlamada derleyici yeri değiştirilebilir kod üretir; mutlak adresler yükleme anında, statik yer değiştirmeyle belirlenir. Başlangıç adresi değişirse program yeniden yüklenir. Yürütme zamanında bağlamada ise adres çevirisi her erişimde, program çalışırken yapılır. Süreç çalışırken bir bellek bölgesinden ötekine taşınabilir. Bunun için özel donanım gerekir. Bugünkü genel amaçlı işletim sistemlerinin hepsi yürütme zamanında bağlama kullanır.

8.2.6Mantıksal ve fiziksel adres, MMU

Yürütme zamanında bağlama, iki tür adresi birbirinden ayırır.

Derleme ve yükleme zamanında bağlamada iki adres aynıdır. Yürütme zamanında bağlamada ise farklıdır ve aralarındaki dönüşümü çalışma anında bir donanım yapar: bellek yönetim birimi (memory management unit, MMU). Program yalnız mantıksal adresleri görür ve onlarla çalışır; fiziksel adresleri hiç görmez. Bir işaretçinin değerini ekrana yazdıran bir C programı, bu yüzden her zaman bir mantıksal adres yazdırır.

Şekil 8.13 MMU'nun yerini gösterir. Eski sistemlerde MMU ayrı bir yongaydı. Bugünkü işlemcilerde MMU, TLB'leri ve sayfa tablosu yürüyücüsüyle birlikte her çekirdeğin içindedir. Bellek veriyoluna çıkan her adres zaten fiziksel adrestir.

8.2.7MMU ile dinamik yer değiştirme

Taban-limit düzeninin yürütme zamanındaki biçiminde MMU iki iş yapar. Önce mantıksal adresi limitle karşılaştırır; adres limitten küçük değilse tuzak üretir. Sonra adrese taban değerini ekler ve fiziksel adresi bulur. Silberschatz bu yazmaca yer değiştirme yazmacı (relocation register) der; Tanenbaum'un taban yazmacıyla aynı şeydir.

Bu düzen, yer değiştirme probleminin örneğindeki B programını da kurtarır. B için taban = 16384, limit = 16384 olsun. JMP 28 komutu bellekte olduğu gibi kalır. Komut çalışınca MMU 28'i limitle karşılaştırır, geçerli bulur ve 28 + 16384 = 16412 fiziksel adresini üretir (Şekil 8.15). Statik yer değiştirmeye de, ek yer değiştirme bilgisine de gerek kalmaz; MOV REG1, 28 içindeki sabit hiç değişmez, çünkü yalnız belleğe giden adresler çevrilir.

Bunun bir bedeli vardır: her bellek erişiminde bir toplama ve bir karşılaştırma gerekir. Karşılaştırma hızlıdır. Toplama ise, elde yayılımı yüzünden, özel devreler kullanılmadıkça bir erişime göre yavaş kalır. Bu bedel, ileride sayfalamayla birlikte daha da büyüyecek bir sorunun ilk işaretidir: adres çevirisi her erişimin yolu üzerindedir ve çok hızlı olmak zorundadır.

8.3Bağlama ve yükleme

Bir programın belleğe yüklenmesi “dosyanın tamamını belleğe kopyala” kadar basit değildir. Program kütüphanelere başvurur; bu kütüphaneler programla birlikte mi, ayrı mı yüklenecek? Kullanılmayabilecek büyük bir kod parçası baştan mı yüklenmeli? Bu kesim bu soruların bugünkü cevaplarını anlatır.

8.3.1Dinamik yükleme

Dinamik yükleme (dynamic loading), bir rutinin çağrılana kadar belleğe alınmamasıdır. Programın ana kısmı yüklenir ve çalışmaya başlar. Bir rutine ihtiyaç duyulduğunda program onu kendisi yükletir. Hiç çağrılmayan kod hiç yüklenmez. Bu, hata işleme kodu gibi nadiren çalışan ama büyük kısımlar için yararlıdır.

Dinamik yükleme için özel donanım gerekmez; program buna göre tasarlanır. İşletim sistemi yalnız gerekli kütüphane işlevlerini sağlar. POSIX sistemlerinde bunlar dlopen, dlsym ve dlclose'dur; Windows'taki karşılıkları LoadLibrary ve GetProcAddress'tir. Aşağıdaki program matematik kütüphanesini çalışırken yükler ve içindeki sqrt işlevini çağırır.

#include <dlfcn.h>
#include <stdio.h>

int main(void) {
  void *h = dlopen("libm.so.6", RTLD_LAZY);
  if (!h) { puts(dlerror()); return 1; }
  double (*kok)(double) =
      (double (*)(double)) dlsym(h, "sqrt");
  printf("%.3f\n", kok(2.0));
  dlclose(h);
  return 0;
}

Program satır satır şöyle çalışır.

1. Program başladığında adres alanında yalnız main'in kodu, C kütüphanesi (libc), öbek ve yığın vardır. Matematik kütüphanesi (libm) yüklü değildir.
2. dlopen("libm.so.6", RTLD_LAZY) çağrısı dinamik bağlayıcıyı (ld.so) çalıştırır. Dinamik bağlayıcı dosyayı bulur ve mmap ile sürecin adres alanına eşler (Şekil 8.16). Yükleme programın isteğiyle, şimdi olur. Dönen h kütüphaneyi temsil eden bir tanıtıcıdır; dosya bulunamazsa NULL döner ve dlerror() nedenini bildirir.
3. dlsym(h, "sqrt") kütüphanenin sembol tablosunda sqrt adını arar ve bu sürecin adres alanındaki adresini döndürür. Dönen void * değeri, double alıp double döndüren bir işlev işaretçisine dönüştürülür.
4. kok(2.0) çağrısı işlev işaretçisi üzerinden yapılır ve ekrana 1.414 yazılır (%.3f biçimiyle √2).
5. dlclose(h) kütüphanenin referans sayısını bir azaltır. Sayı 0'a inince kütüphane adres alanından çıkarılır.

Eski glibc sürümlerinde bu programı derlerken -ldl seçeneği gerekirdi. glibc 2.34'ten beri bu işlevler libc'nin içindedir ve ek seçenek gerekmez.

8.3.2Statik ve dinamik bağlama

Program bir kütüphane işlevini çağırdığında, o işlevin kodunun bir yerde bulunması gerekir. Bunun iki yolu vardır. Statik bağlamada bağlayıcı (ld), derlemeden sonra kütüphane rutinlerini çalıştırılabilir dosyanın içine kopyalar; örneğin ld *.o -lc -lm. Dinamik bağlamada ise dosyada yalnız küçük bir taslak (stub) kalır. Rutinin gerçek adresi yürütme zamanında çözülür. Tablo 8.6 iki yaklaşımı karşılaştırır.

Dinamik bağlamanın en büyük kazancı bellektedir. Yüzlerce süreç aynı C kütüphanesini kullanır. Statik bağlamada her sürecin içinde ayrı bir kopya bulunurdu. Dinamik bağlamada kütüphanenin kod sayfaları fiziksel bellekte bir kez bulunur ve her sürecin adres alanına eşlenir (Şekil 8.17). Bu tür kütüphaneye paylaşımlı kütüphane (shared library) denir.

Güncelleme de kolaylaşır. C kütüphanesinde bir güvenlik açığı kapatıldığında yeni kütüphaneyi kurmak yeter; onu kullanan bütün programlar bir sonraki çalıştırmada yamalı sürümü kullanır. Statik bağlanmış programlar ise yeniden bağlanana kadar açığı taşır. Uyumsuz sürümler karışmasın diye kütüphanelerin bir sürüm adı (soname) vardır; örneğin libm.so.6'daki 6 böyle bir sürümdür. Bu önlem alınmadığında yaşanan karmaşa Windows dünyasında “DLL cehennemi” adıyla anılır.

8.3.3Tembel bağlama: PLT ve GOT

Ders kitaplarında dinamik bağlama genellikle şöyle anlatılır: taslak ilk çağrıldığında rutinin adresini bulur ve kendini bu adresle değiştirir. Bu anlatım kavramsal olarak doğrudur, ama Linux gibi ELF biçimli dosya kullanan sistemlerde değişen şey kod değildir. Gerçek düzenek iki tabloya dayanır.

PLT (procedure linkage table)

Çalıştırılabilir dosyadaki küçük atlama taslaklarının tablosudur. Program printf'i doğrudan değil, printf@plt taslağını çağırır. Kitaplardaki “taslak” budur.

GOT (global offset table)

Sürece özel, yazılabilir bir adres tablosudur. PLT taslağı, GOT'taki ilgili girdinin gösterdiği adrese dolaylı olarak atlar.

İlk çağrıda GOT girdisi gerçek printf'i değil, dinamik bağlayıcının çözücüsünü gösterir. Çözücü sembolü yüklü kütüphanelerde arar, bulduğu adresi GOT girdisine yazar ve printf'e atlar. Bundan sonraki çağrılar PLT → GOT → printf yolunu izler; araya yalnız bir dolaylı atlama girer. Bu düzene tembel bağlama (lazy binding) denir, çünkü bir sembol ancak ilk kullanıldığında çözülür. Tablo 8.7 adımları sıralar.

Değişenin kod değil GOT olması, paylaşım için kritiktir. Kod sayfaları hiç yazılmadığı için bütün süreçler arasında paylaşılabilir kalır. Her sürecin yalnız kendi GOT sayfası farklıdır. Bu işi işletim sistemi değil, kullanıcı alanında çalışan dinamik bağlayıcı yapar.

Tembel bağlamanın güvenlik açısından bir zayıflığı vardır: GOT yazılabilir olduğu için bir saldırgan bellek taşmasıyla oradaki bir adresi değiştirip denetimi ele geçirebilir. Bu yüzden birçok dağıtım programları -z now seçeneğiyle derler. Bu “tam RELRO” düzeninde bütün semboller yükleme anında çözülür ve GOT ardından salt okunur yapılır.

8.3.4Statik ve paylaşımlı kütüphane oluşturma

Bir C kaynak dosyasından (func.c) iki tür kütüphane üretilebilir. Statik kütüphane şu komutlarla oluşturulur ve kullanılır:

$ gcc -c func.c -o func.o
$ ar rcs libfunc.a func.o
$ gcc main.c -o main -static -L. -lfunc
$ ./main

ar aracı nesne dosyalarını tek bir arşivde (libfunc.a) toplar. Bağlayıcı bu arşivden yalnız programın gerçekten kullandığı nesneleri kopyalar. -static seçeneği, C kütüphanesinin de statik sürümünün (libc.a) kullanılmasını ister; sonuçta hiçbir paylaşımlı kütüphaneye bağımlı olmayan bir dosya çıkar.

Paylaşımlı kütüphane için adımlar şöyledir:

$ gcc -fPIC -c func.c -o func.o
$ gcc -shared -o libfunc.so func.o
$ gcc main.c -o main -L. -lfunc
$ export LD_LIBRARY_PATH=$(pwd)
$ ./main
$ ldd ./main   (libfunc.so => ./libfunc.so)

Buradaki kilit seçenek -fPIC'tir: konumdan bağımsız kod (position-independent code). Böyle derlenen kod mutlak adres kullanmaz. Atlamalar program sayacına göreli yapılır, global veriye ise GOT üzerinden erişilir. Bu sayede aynı fiziksel sayfa her süreçte farklı bir sanal adrese eşlenebilir. Adres alanı düzeninin rastgele seçilmesi (address space layout randomization, ASLR) de buna dayanır. ldd komutu, programın hangi paylaşımlı kütüphaneleri hangi dosyalardan alacağını gösterir.

LD_LIBRARY_PATH değişkeni deneme için kullanışlıdır ama kalıcı bir çözüm değildir. Kalıcı çözüm ya kütüphanenin arama yolunu çalıştırılabilir dosyaya gömmek (-Wl,-rpath,'$ORIGIN') ya da kütüphaneyi sistem dizinine kurup ldconfig çalıştırmaktır. Bugünkü dağıtımlar programların kendisini de konumdan bağımsız (position-independent executable, PIE) derler. Böylece programın kendi kodu da ASLR ile her çalıştırmada farklı bir adrese yüklenir.

8.4Takas

Bellekteki süreçlerin toplam ihtiyacı fiziksel belleği aşarsa ne olur? Bir çözüm, o an çalışmayan süreçleri geçici olarak diske taşımaktır. Bu fikre takas (swapping) denir.

8.4.1Standart takas

Standart takasta bir sürecin tamamı geçici olarak bir yedekleme deposuna (backing store), genellikle hızlı bir diske yazılır. Süreç yeniden çalışacağı zaman belleğe geri getirilir (Şekil 8.20). Takas sayesinde süreçlerin toplam bellek ihtiyacı fiziksel belleği aşabilir ve aynı anda daha çok süreç yürütülebilir; yani çoklu programlama derecesi artar.

Takastan dönen süreç, belleğin daha önceki yerine değil, o an boş olan başka bir yere yerleşebilir. Bu yüzden takas, yürütme zamanında bağlama gerektirir. Derleme ya da yükleme zamanında bağlanmış bir süreç ancak tam olarak eski yerine dönebilir.

Standart takasın bedeli aktarım süresidir. Silberschatz'ın örneğinde 100 MB'lık bir süreç, 50 MB/s aktarım hızlı bir diske yazılır. Dışarı yazmak 100 / 50 = 2 s, geri okumak da 2 s sürer; gidiş-dönüş 4 saniyedir. Bu süre boyunca takas edilen süreç çalışamaz.

Takas edilecek süreç seçilirken bir kısıt daha vardır: bekleyen giriş/çıkış işlemi olan bir süreç takas edilmemelidir. Süreç bir aygıttan veri bekliyorsa, aygıt veriyi doğrudan bellek erişimiyle (DMA) sürecin tamponuna yazacaktır. Süreç takas edilip yerine başka bir süreç yüklenirse, DMA aktarımı eski fiziksel adrese, yani artık başka sürecin belleğine yazar. Çare ya böyle bir süreci takas etmemek ya da giriş/çıkışı her zaman çekirdek tamponları üzerinden yapmaktır.

8.4.2Sayfa takası ve bugünkü sistemler

Bugün süreçlerin boyutları gigabaytlarla ölçülür. 1 GiB'lık bir süreç, 3 GB/s okuma-yazma hızlı bir NVMe SSD'de bile gidiş-dönüşte yaklaşık 2 × 1,07 / 3 ≈ 0,72 s tutar. Bu yüzden Linux, Windows ve macOS süreçleri bütün olarak değil, sayfa sayfa takas eder (Şekil 8.21). Yalnız uzun süredir kullanılmayan, yani “soğuk” sayfalar diske gider. 4 KiB'lık bir sayfa onlarca mikrosaniyede geri gelir.

Bugünkü sistemler diske gitmeden önce bir ara adım daha kullanır: sıkıştırma. Soğuk sayfalar önce bellekte sıkıştırılıp küçültülür. Linux'ta zswap ve zram, Windows'ta bellek sıkıştırma, macOS'ta sıkıştırıcı bunu yapar. Sıkıştırılmış bir sayfayı açmak, onu diskten okumaktan çok daha hızlıdır.

Mobil sistemlerde durum farklıdır. Flash belleğin yazma ömrü sınırlıdır ve her yazma enerji harcar. Bu yüzden telefonlarda geleneksel takas ya hiç yoktur ya da çok sınırlıdır. Android zram ile sıkıştırma yapar; bellek yine yetmezse lmkd arka plandaki uygulamaları sonlandırır. iOS da sıkıştırma kullanır ve gerekince uygulamaları sonlandırır (jetsam). Kullanıcı açısından bu, arka plandaki bir uygulamaya dönüldüğünde onun baştan başlaması olarak görülür.

8.5Bitişik tahsis

Taban ve limit yazmaçlarıyla çalışan bir sistemde her süreç bellekte tek parça, kesintisiz bir bölge kaplar. Bu kesim, böyle bir sistemde boş bölgelerin nasıl seçildiğini ve zamanla neden küçük, işe yaramaz parçalara bölündüğünü anlatır.

8.5.1Bitişik bellek tahsisi

Bellek önce iki bölgeye ayrılır: biri işletim sistemine, öteki kullanıcı süreçlerine. İşletim sistemi belleğin alt ya da üst ucuna konabilir. Linux ve Windows çekirdeği yüksek adreslere koyar. Kullanıcı bölgesinde ise her süreç tek bir bitişik bölgededir ve koruma taban-limit yazmaçlarıyla sağlanır.

Kullanıcı bölgesini süreçlere bölmenin iki yolu vardır. Sabit bölümlemede bellek baştan belirli sayıda ve boyda bölüme ayrılır; IBM OS/360'ın MFT sürümü böyle çalışırdı. Her bölüme bir süreç girer, dolayısıyla bölüm sayısı aynı anda bellekte bulunabilecek süreç sayısını, yani çoklu programlama derecesini belirler. Küçük bir süreç büyük bir bölüme girerse bölümün geri kalanı boşa gider. Değişken bölümlemede ise (OS/360 MVT) her sürece tam ihtiyacı kadar yer verilir. Süreçlerin arasında kalan boş bloklara delik (hole) denir.

Bir sorun daha vardır: süreçler büyür. Bir program malloc ile öbekten yer ister, fonksiyon çağrıları yığını derinleştirir. Bitişik bir bölgenin hemen üstünde başka bir süreç varsa büyüme imkânsızdır. Bu yüzden süreçlere baştan bir büyüme payı bırakılır (Şekil 8.22). (a)'da yalnız veri kesimi büyür. (b)'de yığın yukarıdan aşağı, veri aşağıdan yukarı büyür ve pay ikisinin arasında kalır. Süreç takas edilip geri getirildiğinde yalnız kullandığı kısım taşınır, boş pay taşınmaz.

8.5.2Değişken bölümleme

Değişken bölümlemede işletim sistemi bir tablo ya da liste tutar: hangi bölgeler hangi süreçlere ait, hangi bölgeler delik. Bir süreç geldiğinde onu alabilecek kadar büyük bir delik bulunur. Süreç deliğin bir ucuna yerleşir, artan kısım daha küçük bir delik olarak kalır. Süreç bittiğinde alanı deliğe döner ve komşu deliklerle hemen birleştirilir.

1024 K'lık bir bellekte ilk 128 K işletim sistemine ait olsun ve süreçler ilk uygun deliğe yerleşsin. Tablo 8.8 olayları sırayla izler.

D, A'nın bıraktığı 320 K'lık deliğe girer ve geriye 64 K'lık küçük bir delik kalır. B sonlanınca onun 224 K'lık alanı solundaki 64 K'lık delikle birleşir ve 288 K'lık tek bir delik oluşur. Bitişik delikler birleştirilmeseydi, 288 K'lık bir isteğe yer bulunamazdı. E bu deliğe girdikten sonra toplam boş alan 96 + 64 = 160 K'dır, ama iki parçaya dağılmıştır. 100 K'lık bir süreç gelse, toplam yer yetmesine karşın sığmaz.

8.5.3Yerleştirme algoritmaları

Gelen bir isteği alabilecek birden çok delik varsa hangisi seçilmeli? Bu sorunun klasik cevapları şunlardır.

İlk uyan (first fit)

Liste baştan taranır ve yeterince büyük ilk delikte durulur. Hızlıdır. Zamanla listenin başında küçük delikler birikir.

Sonraki uyan (next fit)

İlk uyanın bir türüdür; arama baştan değil, bir önceki aramanın kaldığı yerden sürer. Bays'in 1977'deki benzetimlerine göre ilk uyandan biraz kötü sonuç verir.

En iyi uyan (best fit)

Bütün liste taranır ve isteğe en yakın boydaki delik seçilir. Liste boyuna sıralı tutulmuyorsa yavaştır. Geriye işe yaramayacak kadar küçük delikler bırakır.

En kötü uyan (worst fit)

En büyük delik seçilir; amaç, artan parçanın başka bir istek için kullanılabilecek kadar büyük kalmasıdır. Benzetimlerde iyi sonuç vermez.

Hızlı uyan (quick fit)

Sık istenen boyutlar (4 K, 8 K, 12 K …) için ayrı listeler tutulur. Uygun deliği bulmak çok hızlıdır; ama serbest kalan bir bloğun komşularını bulup birleştirmek pahalıdır.

Bütün algoritmalar süreçler ve delikler için ayrı listeler tutularak hızlandırılabilir: arama yalnız delik listesinde yapılır. Bugünkü malloc gerçeklemeleri (jemalloc, tcmalloc) hızlı uyanın genelleştirilmiş bir biçimini, boyut sınıflarını kullanır. Silberschatz ve Knuth'un aktardığı benzetimlerin sonucu açıktır. Hem zaman hem bellek kullanımı açısından ilk uyan ve en iyi uyan, en kötü uyandan iyidir. İlk uyan genellikle daha hızlıdır.

8.5.4Kod izleme: en iyi uyan

Aşağıdaki fonksiyon, delik boylarını tutan bir dizide en iyi uyan aramasını yapar. Bulduğu deliği istek kadar küçültür ve deliğin indisini döndürür; yer yoksa −1 döndürür.

int en_iyi(int delik[], int n, int istek) {
  int en = -1;
  for (int i = 0; i < n; i++)
    if (delik[i] >= istek &&
        (en == -1 || delik[i] < delik[en]))
      en = i;
  if (en != -1) delik[en] -= istek;
  return en;
}
/* delik = 120, 450, 230, 300, 180 (K) */
/* en_iyi(delik, 5, 210); en_iyi(delik, 5, 160); */

en değişkeni o ana kadar bulunan en iyi adayın indisidir; −1 “henüz aday yok” demektir. Döngü her delik için iki koşula bakar. Birincisi deliğin isteğe yetmesidir (delik[i] >= istek). İkincisi ya henüz aday olmaması ya da bu deliğin mevcut adaydan küçük olmasıdır. İki koşul birlikte sağlanırsa aday değişir. Döngü bitince seçilen delik istek kadar küçültülür. Fonksiyon her çağrıda bütün listeyi gezer, yani n delik için O(n) zaman harcar.

İzleme en iyi uyanın tipik davranışını gösterir: her seferinde isteğe en yakın deliği seçtiği için geriye çok küçük artıklar kalır. Aynı iki istek ilk uyanla karşılansaydı ikisi de 450'lik deliğe girerdi: önce 240, sonra 80 K kalırdı. En kötü uyanla 210 K yine 450'ye girer (240 kalır), 160 K ise o an en büyük delik olan 300'e girerdi (140 kalır). Hangi artıkların gelecekte işe yarayacağı, sonraki isteklere bağlıdır.

8.5.5Dört algoritma aynı istek dizisinde

Silberschatz'ın klasik alıştırması, algoritmaların farkını tek bir örnekte gösterir.

Bu sonuç en iyi uyanın her zaman üstün olduğu anlamına gelmez. Örnek, büyük deliği bütün tutmanın işe yaradığı bir dizidir. Başka dizilerde sonuç değişir. Çalışma sorularındaki diziyi ele alalım: delikler 150, 400, 80, 250, 600 K; istekler 230, 120, 380, 90 K. Bu kez en kötü uyan 380 K'yı yerleştiremez. İlk uyan ve en iyi uyan ise dört isteği de karşılar. Aynı karşılaştırmayı farklı dizilerle denemek için Bellek Tahsisi Simülatörü kullanılabilir.

8.5.6İç ve dış parçalanma

Değişken bölümlemede ortaya çıkan ve önceki örneklerde gördüğümüz sorunun adı dış parçalanmadır.

Dış parçalanmanın büyüklüğünü Knuth'un %50 kuralı özetler. İlk uyanla çalışan bir sistemde N tahsisli blok varken, ortalamada yaklaşık 0,5 N blok parçalanma yüzünden boşa gider. Boşa giden blokların payı 0,5 N / (N + 0,5 N) = 1/3'tür; yani belleğin üçte biri kullanılamaz hâle gelebilir.

İç parçalanma ise sabit boyutlu bloklarla çalışan her düzende görülür: sabit bölümlemede, sayfalamada ve aşağıda anlatılan buddy sisteminde. Tanenbaum'un örneği ilginç bir nedeni de gösterir (Şekil 8.26). 18.464 baytlık bir delik varken 18.462 baytlık bir süreç gelirse, geriye 2 baytlık bir delik kalacaktır. Bu 2 baytı ayrı bir delik olarak listede izlemenin maliyeti, deliğin kendisinden büyüktür. Bu yüzden süreç 18.464 baytın tamamını alır ve 2 bayt bloğun içinde boşa gider.

Dış parçalanmanın iki çözümü vardır. Birincisi sıkıştırmadır: süreçler kaydırılıp delikler tek bir blokta toplanır. İkincisi daha köklüdür: bir sürecin adres alanının fiziksel bellekte bitişik olma zorunluluğunu kaldırmak. Sayfalama ve kesimleme bu ikinci yolu izler.

İç parçalanmanın iyi bilinen bir kaynağı, fiziksel çerçeveleri ayırmak için Linux'ta da kullanılan buddy (kardeş) sistemidir (buddy system). Bu düzende bloklar hep ikinin kuvveti boyundadır. Bir istek, ona yeten en küçük ikinin kuvvetine yuvarlanır. Uygun boyda boş blok yoksa daha büyük bir blok ikiye bölünür; oluşan iki yarıya birbirinin “kardeşi” denir. Bir blok serbest kalınca kardeşi de boşsa ikisi yeniden birleşir. Kardeşin adresi tek bir XOR işlemiyle bulunur: adres ⊕ boy.

8.5.7Sıkıştırma

Şekil 8.27 başlangıç durumunu gösterir. İşletim sistemi 0–128 K'dadır. P1 128'de (160 K), P2 384'te (192 K), P3 640'ta (128 K), P4 928'de (64 K) başlar. Aralarda 96, 64, 160 ve 32 K'lık dört delik vardır; toplam 352 K boş alan bulunduğu hâlde en büyük delik 160 K'dır.

Sıkıştırma süreçleri sırayla aşağı kaydırır. P1 zaten işletim sisteminin hemen üstündedir. P2, 384'ten 288'e (128 + 160) taşınır. P3, 640'tan 480'e (288 + 192), P4 de 928'den 608'e (480 + 128) taşınır. Sonunda 672 ile 1024 arasında tek bir 352 K'lık delik kalır (Şekil 8.28). Bu iş için 192 + 128 + 64 = 384 K kopyalanmıştır. Her taşınan sürecin taban yazmacı yeni adresle güncellenir.

Sıkıştırma yalnız yürütme zamanında bağlama kullanan sistemlerde mümkündür. Süreçteki adresler yükleme anında sabitlenmişse, süreç taşındıktan sonra yanlış yerleri gösterir. Taban yazmacı kullanan sistemde ise yalnız yazmacın değeri değişir.

Sıkıştırma pahalıdır. Tanenbaum'un hesabına göre 8 baytı 8 ns'de kopyalayan bir makine, yani saniyede 1 GB, 16 GB'lık belleği yaklaşık 16 s'de sıkıştırır. Bugünkü yaklaşık 20 GB/s'lik kopyalama hızıyla bile iş yaklaşık bir saniye sürer (16 / 20 = 0,8 s; 16 GiB için ≈ 0,86 s). Bu sırada süreçler durur. Sıkıştırma (compaction), veri sıkıştırma (compression) ile karıştırılmamalıdır. Amaç veriyi küçültmek değil, blokları bitiştirmektir.

Sıkıştırma tamamen tarihe karışmış da değildir. Linux, büyük sayfalar için bitişik fiziksel çerçeve üretmek amacıyla arka planda sayfa göçü yapar; bu işi kcompactd çekirdek iş parçacığı yürütür.

8.6Boş alan yönetimi

Yerleştirme algoritmalarının hepsi aynı bilgiye dayanır: hangi bölgeler boş? Bu bilginin nasıl tutulduğu, aramanın ve serbest bırakmanın ne kadar hızlı olacağını belirler. İki temel yapı vardır: biteşlem ve bağlı liste.

8.6.1Biteşlem ve bağlı liste

Bellek önce sabit boyutlu tahsis birimlerine bölünür; birim birkaç sözcük de olabilir, birkaç kilobayt da.

Şekil 8.29 aynı belleğin iki gösterimini verir. 32 birimlik bellekte A, B, C, D ve E süreçleri ile üç delik vardır. Biteşlemin ilk baytı 11111000'dır: 0–4 arası birimler A'ya ait, 5–7 boştur. Bağlı listede aynı bilgi “S 0 5, D 5 3, S 8 6, …” düğümleriyle tutulur.

Biteşlemin boyutu birim büyüklüğüne bağlıdır ve sabittir. Birim 4 bayt, yani 32 bit ise her 32 bitlik bellek için 1 bit harcanır; biteşlem belleğin 1/33'ünü kaplar. 16 GiB bellek 4 KiB'lık birimlere bölünürse 2³⁴ / 2¹² = 2²² birim olur. Biteşlem de 2²² bit, yani 512 KiB tutar. Birim küçüldükçe biteşlem büyür; birim büyüdükçe son birimdeki iç parçalanma artar.

8.6.2Kod izleme: biteşlemde boş alan arama

Biteşlemin zayıf yanı aramadır. k birimlik bir süreç için yer bulmak, dizide art arda k tane 0 bulmak demektir. Aşağıdaki fonksiyon bunu doğrusal bir taramayla yapar.

/* k ardışık boş (0) birim ara */
int bul(const char bit[], int n, int k) {
  int bas = 0, uz = 0;
  for (int i = 0; i < n; i++) {
    if (bit[i] == 0) {
      if (uz == 0) bas = i;  /* yeni koşu */
      if (++uz == k) return bas;
    } else
      uz = 0;                /* koşu bozuldu */
  }
  return -1;
}

uz o anda sürmekte olan sıfır koşusunun uzunluğunu, bas da koşunun başladığı indisi tutar. Bir 0 görülünce, koşu yeni başlıyorsa (uz == 0) başlangıç kaydedilir ve uzunluk bir artar. Uzunluk k'ye ulaşınca başlangıç döndürülür. Bir 1 görülünce koşu bozulur ve uz sıfırlanır. Tablo 8.11, 10 birimlik 1 1 0 0 1 0 0 0 1 1 biteşleminde k = 3 aramasını izler.

Fonksiyon 5 döndürür. Ayırıcı ardından 5, 6 ve 7 numaralı bitleri 1 yapar. Arama her seferinde dizinin başından başlar ve en kötü durumda bütün biteşlemi gezer: n birim için O(n). Büyük bir biteşlemde bu yavaştır. Gerçek gerçeklemeler biteşlemi sözcük sözcük tarayarak ve donanımın “ilk sıfır biti bul” komutlarını kullanarak hızlandırır, ama doğrusal yapı değişmez.

8.6.3Bağlı listede serbest bırakma

Bağlı listenin güçlü yanı serbest bırakmadır. Liste adrese göre sıralı tutulursa, sonlanan bir X sürecinin iki komşusu listede hemen önünde ve arkasındadır. Komşuların türüne göre dört durum vardır (Tablo 8.12).

Birleştirme yalnız komşulara bakarak, sabit zamanda yapılır. Son durumda önceki düğümü değiştirmek gerektiği için çift bağlı liste işi kolaylaştırır. Delikler ayrı bir listede, boyuta göre sıralı tutulursa en iyi uyan hızlanır. Liste baştan tarandığında ilk yeten delik zaten en küçük yetendir; ilk uyan en iyi uyana dönüşür. Ama bu kez serbest bırakma yavaşlar, çünkü komşu delikler artık listede yan yana değildir.

Bir ayrıntı daha önemlidir: delik listesini tutmak için ayrıca bellek gerekmez. Liste deliklerin kendi içinde saklanabilir. Her deliğin ilk sözcükleri o deliğin boyunu ve sonraki deliğin adresini tutar. Delik zaten boş olduğu için bu yer bedavadır.

8.6.4malloc'un içi: başlık ve gömülü boş liste

Aynı fikirler kullanıcı alanında da geçerlidir. C kütüphanesinin malloc ve free işlevleri, öbek denilen bölgeyi bir boş liste ile yönetir. Bunun için özel bir sorun çözülmelidir: boş listenin düğümleri için ayrı bir veri yapısı kurulamaz, çünkü o yapıya yer ayırmak için yine malloc çağırmak gerekir. Çözüm, düğümü boş parçanın kendi içine gömmektir.

Örnek ayırıcıda her parçanın başında 16 baytlık bir başlık vardır. Parça kullanımdaysa başlıkta boyu ve sabit bir sihirli sayı, boşsa boyu ve sonraki boş parçanın adresi bulunur. Tablo 8.13 4096 baytlık bir öbek üzerindeki işlemleri izler.

free işlevi boyut almaz; boyu, kendisine verilen adresin 16 bayt gerisindeki başlıktan okur. free(p2)'den sonra 100 baytlık bir boş parça vardır, ama 150 baytlık bir istek ona sığmaz: kullanıcı alanında da dış parçalanma oluşur. free(p1) ile p1'in parçası adres sırasındaki komşusu olan boş parçayla birleşir ve liste kısalır.

Sihirli sayı

Başlıktaki sabit desen bir tampon taşması, aynı işaretçinin iki kez serbest bırakılması ya da yanlış bir işaretçi yüzünden bozulabilir. Kütüphane bunu fark edip programı durdurabilir.

Gerçek istek

malloc(n) en az n + başlık kadar bayt tüketir. Ayrıca adresler hizalanmak zorunda olduğu için boy yukarı yuvarlanır; glibc'de hizalama 16 bayttır.

Sistem çağrısı mı?

Hayır, malloc bir kütüphane işlevidir. Öbekte yer bitince brk/sbrk sistem çağrılarıyla öbeği büyütür. Büyük istekleri (glibc'de 128 KiB ve üstü) doğrudan mmap ile alır.

8.7Sayfalama

Bitişik tahsisin bütün sorunları tek bir varsayımdan doğar: sürecin fiziksel bellekte tek parça durması. Sayfalama bu varsayımı kaldırır. Süreç küçük, eşit parçalara bölünür ve her parça belleğin boş olan herhangi bir yerine konabilir. Bugünkü bütün genel amaçlı işletim sistemleri sayfalama kullanır.

8.7.1Temel fikir

Bu düzenin sonuçları hemen görülür. Sürecin fiziksel bellekteki yeri bitişik olmak zorunda değildir; ardışık sayfalar birbirinden uzak çerçevelerde durabilir (Şekil 8.33). Bu yüzden dış parçalanma yoktur: her boş çerçeve, her sürecin her sayfası için uygundur. N sayfalık bir süreç için herhangi N boş çerçeve yeter. İç parçalanma ise yalnız sürecin son sayfasında kalır, çünkü süreç boyu sayfa boyunun tam katı olmayabilir.

İşletim sistemi hangi çerçevelerin boş olduğunu izler ve her sürecin sayfa tablosunu kurar. Takas için kullanılan yedekleme deposu da aynı boyda bloklara bölünür; böylece bir sayfa diskteki herhangi bir bloğa yazılıp herhangi bir çerçeveye geri okunabilir.

8.7.2Adresin (p, d) olarak bölünmesi

Sayfalamada işlemcinin ürettiği her mantıksal adres iki parçaya bölünür: sayfa numarası p ve sayfa içi konum d (offset). Mantıksal adres alanı 2^m bayt, sayfa boyutu 2ⁿ bayt ise adresin alt n biti konumu, üst m − n biti sayfa numarasını verir (Şekil 8.34).

Sayfa tablosu p'yi bir çerçeve numarası f'ye çevirir. Konum hiç değişmez. Fiziksel adres çerçevenin başlangıcına konumun eklenmesiyle bulunur:

p = ⌊a / sayfa boyu⌋,   d = a mod sayfa boyu,   fiziksel = f × sayfa boyu + d

Sayfa boyu ikinin bir kuvveti olduğu için bu bölme ve kalan, birer bit kaydırma ve maskeleme işlemidir. 4 KiB'lık sayfada p = a >> 12, d = a & 0xFFF'tir. Donanım bu işlemleri bedavaya yapar; ikinin kuvveti olmayan bir sayfa boyu gerçek bir bölücü devre gerektirirdi.

Onaltılık yazımda bölme özellikle kolaydır: her onaltılık hane 4 bittir, dolayısıyla 12 bitlik konum son üç hanedir. 0x12345678'in son üç hanesi 0x678 konumu, geri kalanı 0x12345 sayfa numarasını verir.

8.7.3Sayfa tablosuyla çeviri

Silberschatz'ın küçük örneği çeviriyi elle izlemeye uygundur. Sayfa boyu 4 bayt, fiziksel bellek 32 bayttır; yani 8 çerçeve vardır. Sürecin 16 baytlık mantıksal belleği a'dan p'ye kadar harflerle doludur ve dört sayfa kaplar. Sayfa tablosu 0 → 5, 1 → 6, 2 → 1, 3 → 2'dir.

Örnek iki önemli noktayı gösterir. Birincisi, sürecin harfleri fiziksel bellekte sırasını korumaz: i…l çerçeve 1'de, m…p çerçeve 2'de, a…d çerçeve 5'tedir. Program yine de belleğini a'dan p'ye ardışık görür. İkincisi, sayfa tablosu girdisinin indisi sayfa numarasıdır; sayfa numarası tabloda ayrıca saklanmaz. Tablonun 3. girdisine bakmak “sayfa 3 nerede?” sorusunun cevabıdır.

8.7.4MMU içinde çeviri

Tanenbaum'un örneğinde sanal adres 16 bittir (64 KiB, 16 sayfa), fiziksel bellek 32 KiB'tır (8 çerçeve). Sayfa boyu 4 KiB olduğu için sanal adresin üst 4 biti sayfa numarası, alt 12 biti konumdur. Çerçeve numarası 3 bittir. Aşağıdaki komutlar beş farklı adrese erişir; sayfa tablosu da yorumlarda verilmiştir.

/* 16 bit sanal adres, 4 KiB sayfa */
MOV REG, 0
MOV REG, 8192
MOV REG, 20500
MOV REG, 8196
MOV REG, 32780

/* sayfa tablosu (sayfa → çerçeve) */
/* 0→2 1→1 2→6 3→0 4→4 5→3 */
/* 9→5 11→7, diğerleri: yok */

MMU her adreste aynı işi yapar. Üst 4 biti tablo indisi olarak kullanır ve girdideki 3 bitlik çerçeve numarasını alır. Alt 12 biti hiç değiştirmeden bu numaraya ekler. Tablo 8.16 beş adresin çevirisini gösterir.

Son adres ilginçtir. 32780 = 8 × 4096 + 12'dir ve sayfa 8 eşlenmemiştir; tablodaki girdisinin mevcut/yok biti 0'dır. MMU fiziksel adres üretemez ve bir sayfa hatası (page fault) tuzağı oluşturur. Denetim işletim sistemine geçer. Sayfa diskteyse işletim sistemi onu bir çerçeveye getirip tabloyu günceller; sayfa hiç geçerli değilse süreci sonlandırır.

8.7.5Sayfa boyutu ve iç parçalanma

Sayfalamada iç parçalanma yalnız son sayfada oluşur, ama sayfa boyu seçimini etkileyecek kadar önemlidir.

En kötü durumda süreç bir sayfadan yalnız bir bayt taşar ve iç parçalanma bir sayfa eksi bir bayt olur. Süreç boyları rastgele dağılıyorsa ortalama iç parçalanma yarım sayfadır. Bu, küçük sayfa lehine bir gerekçedir. Buna karşılık küçük sayfa daha çok sayfa ve dolayısıyla daha büyük bir sayfa tablosu, daha çok TLB ıskası demektir. Büyük sayfa ise disk ile bellek arasında daha verimli aktarım ve daha az tablo girdisi sağlar.

Tanenbaum bu ödünleşimi basit bir modelle ölçer. Ortalama süreç boyu s bayt, bir tablo girdisinin boyu e bayt, sayfa boyu p olsun. Süreç başına yaklaşık s / p sayfa ve s·e / p bayt tablo gerekir; iç parçalanma da ortalama p / 2'dir. Toplam ek yük:

ek yük = s·e / p + p / 2

p küçülünce birinci terim, büyüyünce ikinci terim artar. Türev alınıp sıfıra eşitlenirse −s·e / p² + 1/2 = 0, yani p = √(2·s·e) bulunur. s = 1 MiB, e = 8 bayt için p = √(2 × 2²⁰ × 8) = √(2²⁴) = 2¹² = 4096 bayt çıkar (Şekil 8.37). Bu değerde ek yük 2048 + 2048 = 4096 bayttır; 2048 ve 8192 baytlık sayfalarda ise 5120 bayta çıkar.

Gerçek sistemler de bu civarda kalır. x86-64'te temel sayfa 4 KiB'tır; ayrıca 2 MiB ve 1 GiB'lık büyük sayfalar vardır. ARM64 4, 16 ya da 64 KiB'lık sayfa kullanabilir; Apple Silicon 16 KiB kullanır.

8.7.6Boş çerçeveler

Yeni bir süreç geldiğinde işletim sistemi boş çerçeve listesinden sürecin sayfa sayısı kadar çerçeve alır ve sayfa tablosunu doldurur. Şekil 8.38 örneğinde boş liste 14, 13, 18, 20, 15'tir. Dört sayfalık süreç listenin ilk dört çerçevesini alır: sayfa 0 → 14, 1 → 13, 2 → 18, 3 → 20. Listede yalnız 15 kalır.

İşletim sistemi bunun için bir çerçeve tablosu tutar: her fiziksel çerçeve için çerçevenin boş olup olmadığı, doluysa hangi sürecin hangi sayfasını tuttuğu. Bu tablo yalnız tahsiste değil, başka işlerde de gerekir. Örneğin bir süreç read sistem çağrısıyla bir tampon adresi verdiğinde bu adres mantıksaldır. Çekirdek veriyi oraya yazabilmek için adresi sürecin sayfa tablosuyla fiziksel adrese çevirir.

Her sürecin ayrı bir sayfa tablosu olduğu için bağlam değiştirmede donanıma yeni sürecin tablosunu göstermek gerekir. Dağıtıcı bunu bir yazmacı güncelleyerek yapar; x86'da bu yazmaç CR3'tür. Bu ek iş bağlam değiştirme süresini uzatır.

8.7.7Sayfa tablosu girdisi

Sayfa tablosu girdisi (page table entry, PTE) yalnız çerçeve numarasını tutmaz. Yanında, donanımın ve işletim sisteminin kullandığı bir dizi bit bulunur. Şekil 8.39 x86-64'ün 64 bitlik girdisini gösterir.

Erişildi ve değiştirildi bitleri işletim sistemine çok değerli bilgi verir. Donanım bir sayfaya her erişimde A'yı, her yazmada D'yi 1 yapar. İşletim sistemi A bitlerini periyodik olarak sıfırlayıp hangi sayfaların son zamanlarda kullanıldığını öğrenir. D biti ise bir sayfa bellekten çıkarılırken onu diske yazmanın gerekip gerekmediğini söyler: değişmemiş bir sayfanın diskteki kopyası zaten günceldir.

Önbellek bitleri, bellek eşlemeli giriş/çıkış için gereklidir. Bir aygıtın yazmacı bellek adresine eşlenmişse, o adresten okunan değer önbellekten değil aygıttan gelmelidir. Aksi hâlde program aygıtın eski durumunu okur.

Bir sayfa bellekte değilse diskteki yeri nerede tutulur? Disk adresi PTE'de tutulmaz; donanım onu kullanmaz. P biti 0 olan bir girdinin geri kalan bitleri tamamen işletim sistemine aittir. Linux takas alanındaki yeri bu bitlere kodlar.

8.7.8Geçerli / geçersiz biti

Sayfa tablosu, sürecin adres alanının tamamı için girdi içerir; ama süreç bu alanın hepsini kullanmaz. Kullanılmayan sayfaların girdileri geçersiz olarak işaretlenir. Silberschatz'ın örneğinde adres 14 bittir (0 … 16383), sayfa 2 KiB'tır, yani 8 sayfa vardır. Süreç yalnız 0 ile 10468 arasını kullanır: sayfa 0–5 geçerlidir ve 2, 3, 4, 7, 8, 9 numaralı çerçevelerdedir; sayfa 6 ve 7 geçersizdir.

Üçüncü satır sayfalamanın bir sınırını gösterir. Sürecin son adresi 10.468'dir; 12.000 programa ait değildir. Ama sayfa 5, 10.240 ile 12.287 arasını kapsar ve geçerli işaretlidir. Donanım koruması sayfa ayrıntı düzeyindedir: bir sayfanın içindeki her adres ya geçerlidir ya da hiçbiri geçerli değildir. Sürecin son sayfasındaki kullanılmayan kısım, iç parçalanmanın bir başka yüzüdür. 12.500 ise sayfa 6'dadır ve geçersiz girdi bir tuzak üretir. İşletim sistemi bu tuzağın bir programlama hatası mı (SIGSEGV), yoksa henüz belleğe getirilmemiş bir sayfaya erişim mi olduğuna karar verir.

Bütün tabloyu tutmak yerine bir sayfa tablosu uzunluk yazmacı (page-table length register, PTLR) da kullanılabilir. Bu yazmaç tablonun kaç girdi içerdiğini tutar; daha büyük bir sayfa numarası doğrudan tuzak üretir. Böylece kullanılmayan sayfaların girdileri için yer harcanmaz.

8.7.9Koruma bitleri

Sayfalamada koruma da sayfa düzeyinde yapılır. İzin bitleri her PTE'de ayrı tutulur ve her erişimde, TLB girdisiyle birlikte denetlenir.

Okuma / yazma (R/W)

Kod sayfaları salt okunur eşlenir; koda yazma girişimi koruma hatası üretir.

Kullanıcı / denetçi (U/S)

Çekirdek sayfalarına kullanıcı modunda erişilemez. Böylece aynı tabloda hem çekirdeğin hem sürecin eşlemeleri bulunabilir.

Çalıştırma yasağı (NX / XD)

Veri, yığın ve öbek sayfalarında kod çalıştırılamaz. İşletim sistemleri W^X kuralını uygular: bir sayfa ya yazılabilir ya çalıştırılabilirdir, ikisi birden olamaz. Böylece yığına yazılan saldırı kodu çalıştırılamaz.

SMEP / SMAP

Çekirdek modundayken kullanıcı sayfalarındaki kodun çalıştırılmasını (SMEP) ve kullanıcı verisine izinsiz erişimi (SMAP) engeller.

Koruma anahtarları (PKU)

PTE'deki 4 bitlik anahtar ve bir kullanıcı yazmacı (PKRU) ile, sistem çağrısı yapmadan bir sayfa grubunun iznini değiştirmeyi sağlar.

Geçerli / geçersiz

Erişim izninin en kaba biçimidir: sayfa adres alanında hiç yoksa her erişim tuzaktır.

8.7.10Paylaşımlı sayfalar

Sayfalamanın önemli bir kazancı, ortak kodun kolayca paylaşılabilmesidir. Yeniden girilir (reentrant), yani çalışırken kendini değiştirmeyen kod birçok süreç arasında paylaşılabilir. Üç kullanıcı aynı metin düzenleyicisini çalıştırırsa düzenleyicinin kod sayfaları bellekte yalnız bir kez bulunur. Her sürecin sayfa tablosu bu çerçeveleri gösterir; yalnız veri sayfaları her süreç için ayrıdır (Şekil 8.41).

Paylaşımlı kütüphaneler de bu yolla paylaşılır. Paylaşımın bir sonucu vardır: sayfanın “sahibi” olan süreç bittiğinde çerçeve hemen boşaltılamaz, çünkü başka süreçler onu kullanıyor olabilir. Bu yüzden her paylaşılan çerçeve için bir referans sayısı tutulur.

Bugünkü sistemlerde paylaşımın başka biçimleri de vardır. fork() çağrısında ebeveyn ve çocuk bütün sayfaları yazınca kopyala (copy-on-write, COW) yöntemiyle paylaşır. Sayfalar iki süreçte de salt okunur işaretlenir; süreçlerden biri bir sayfaya yazmaya çalışınca koruma hatası olur ve çekirdek yalnız o sayfanın kopyasını çıkarır. Bellek eşlemeli dosyalar (mmap) ve paylaşımlı bellek (shm_open) ise iki sürecin aynı çerçeveleri görmesini sağlar; süreçler veri kopyalamadan iletişim kurar.

8.8TLB

Sayfalama dış parçalanmayı ortadan kaldırır, ama bir bedeli vardır: her bellek erişimi önce bir tablo erişimi gerektirir. Bu kesim, bu bedelin nasıl neredeyse sıfıra indirildiğini anlatır.

8.8.1Sayfa tablosu nerede durur?

Sayfa tablosu küçük olsaydı işlemcinin içinde, özel yazmaçlarda tutulabilirdi. Ama 32 bit adres ve 4 KiB sayfada bir tablonun 2²⁰, yani bir milyondan fazla girdisi vardır. Bu kadar girdi yazmaçlara sığmaz. Tablo bu yüzden ana bellekte durur. Başlangıç adresini sayfa tablosu taban yazmacı (page-table base register, PTBR) tutar; bu yazmaç x86'da CR3, ARM'da TTBR0/TTBR1'dir. Bağlam değiştirmede yalnız bu yazmaç değişir.

Bu çözümün sorunu açıktır: her veri erişimi artık iki bellek erişimidir. Önce PTBR + p adresindeki girdi okunur, sonra veriye erişilir. Bellek erişim süresi iki katına çıkar. Çözüm, son kullanılan çevirileri tutan küçük bir donanım önbelleğidir.

Çeviri şöyle yürür (Şekil 8.42). İşlemci bir adres ürettiğinde sayfa numarası önce TLB'de aranır. Bulunursa (TLB isabeti) çerçeve numarası hemen alınır ve tablo erişimi yapılmaz. Bulunmazsa (TLB ıskası) PTBR üzerinden bellekteki tabloya gidilir, girdi okunur ve bir sonraki erişim için TLB'ye yüklenir. TLB doluysa bir girdi çıkarılır.

Bugünkü işlemcilerde tipik olarak her çekirdekte 64 girdilik bir L1 TLB ve 1–3 bin girdilik bir L2 TLB bulunur. TLB girdileri bir adres alanı kimliğiyle (address-space identifier, ASID; Intel'de PCID) etiketlenebilir. Böylece her girdi hangi sürece ait olduğunu bilir ve bağlam değiştirmede TLB'nin boşaltılması gerekmez.

8.8.2TLB isabet ve ıska izlemesi

Tanenbaum'un MMU örneğindeki sayfa tablosu (0 → 2, 2 → 6, 5 → 3, 9 → 5, 11 → 7) bu kez bir TLB ile kullanılsın. TLB 4 girdiliktir ve yer gerekince en uzun süredir kullanılmayan (LRU) girdiyi çıkarır. TLB başlangıçta boştur. Aşağıdaki sözde kod her erişimde yapılanları özetler.

p = adres / 4096;  d = adres % 4096;
if (p TLB'de) {           /* isabet */
  f = TLB[p];  p'yi en yeni yap;
} else {                  /* ıska */
  f = sayfa_tablosu[p];
  if (TLB dolu) en eski girdiyi çıkar;
  TLB'ye (p, f) ekle;
}
fiziksel = f * 4096 + d;

Sekiz erişimde yalnız 2 isabet vardır. İsabetlerde sayfa tablosuna hiç gidilmez. 0x0020 isabetinden sonra sayfa 0 “en yeni” konuma geçer. Ama 0xB004 geldiğinde TLB doludur ve en uzun süredir kullanılmayan girdi yine sayfa 0'dır, çünkü 0x0020'den sonra 5, 9 ve 2 kullanılmıştır. Hemen ardından gelen 0x0030 bu yüzden ıskalar. Kısa örneklerde oran düşük çıkar; gerçek programlarda ise yerellik sayesinde TLB isabet oranı %99'u aşar.

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

8.8.3Etkin erişim süresi

TLB'nin kazancı tek bir sayıyla ölçülür.

Formülün mantığı basittir. İsabette TLB'ye bakılır ve tek bir bellek erişimi yapılır: t + ε. Iskada TLB'ye bakılır, sonra tablo girdisi için bir, veri için bir bellek erişimi yapılır: 2t + ε. Ortalama, bu iki sürenin olasılıklarla ağırlıklı toplamıdır.

Çok seviyeli tablolarda ıska çok daha pahalıdır. x86-64'ün dört seviyeli tablosunda bir ıska dört tablo erişimi ve bir veri erişimi gerektirir: 20 + 4 × 100 + 100 = 520 ns. Bu durumda α = %98 için EES = 120 × 0,98 + 520 × 0,02 = 117,6 + 10,4 = 128 ns, α = %99 için 118,8 + 5,2 = 124 ns olur. Iska ne kadar pahalıysa isabet oranı o kadar önemlidir. Bu yüzden donanım tablo yürüyüşünün ara seviyelerini de ayrı bir önbellekte tutar (page walk cache). Gerçek bir ıska böylece çoğu zaman dört değil, bir ya da iki bellek erişimine iner.

TLB'nin etkisini bir döngü üzerinde saymak da öğreticidir.

dongu: movl $0,(%edi,%eax,4)  /* a[i] = 0 */
       incl %eax              /* i++      */
       cmpl $1000,%eax
       jne  dongu

8.8.4TLB yönetimi

TLB'nin nasıl doldurulduğu ve temizlendiği mimariden mimariye değişir. Tablo 8.20 başlıca konuları özetler.

ASID'nin değeri bağlam değiştirmede ortaya çıkar. Etiket yoksa, yeni süreç eski sürecin çevirilerini kullanmasın diye bütün TLB boşaltılmalıdır; yeni süreç de ilk erişimlerinde art arda ıskalar. ASID ile iki sürecin aynı sanal sayfası TLB'de yan yana durabilir (Şekil 8.44). TLB vurusu (TLB shootdown) ise çok çekirdekli sistemlerin sorunudur: bir çekirdek bir eşlemeyi değiştirdiğinde, aynı eşlemeyi TLB'sinde tutan öteki çekirdeklere haber vermek zorundadır. Bu iletişim pahalıdır ve büyük sistemlerde ölçeklenmeyi sınırlar.

8.9Sayfa tablosu yapıları

Tek seviyeli, doğrusal bir sayfa tablosu küçük adres alanlarında işe yarar. Adres alanı büyüdükçe tablonun kendisi bir bellek sorununa dönüşür. Bu kesim, tabloyu küçültmenin üç yolunu anlatır: hiyerarşik, hash ve ters tablolar.

8.9.1Hiyerarşik sayfa tablosu

32 bit adres ve 4 KiB sayfada tek seviyeli tablonun 2²⁰ girdisi vardır; girdi 4 bayt ise tablo 4 MiB tutar. Bu tablo her süreç için ayrı ve bellekte bitişik olmalıdır. 100 süreçlik bir sistemde yalnız sayfa tabloları 400 MiB eder. 64 bitte durum çok daha kötüdür. 4 KiB sayfa ve 8 baytlık girdiyle tek seviyeli tablo 2⁵² × 8 B = 32 PiB, yani yaklaşık 33,6 milyon GiB tutar. Adresin yalnız 48 biti kullanılsa bile 2³⁶ × 8 B = 512 GiB gerekir.

Çözüm, tablonun kendisini sayfalamaktır. Sanal adres iki indise ve bir konuma bölünür. 32 bit x86'da 10 bit üst tabloyu (sayfa dizini), 10 bit ikinci seviye tabloyu indisler, 12 bit konumdur (Şekil 8.45). Burada bölünen şey tablo girdisi değil, sanal adrestir.

Kazanç seyrek adres alanlarından gelir. Bir sürecin 4 MiB kod, 4 MiB veri ve 4 MiB yığın kullandığını düşünelim. Her ikinci seviye tablo 1024 sayfa × 4 KiB = 4 MiB'lık bir bölgeyi kapsar. Bu süreç için bir üst tablo ve üç alt tablo yeter: 4 × 4 KiB = 16 KiB. Tek seviyeli tablo 4 MiB tutardı. Kullanılmayan bölgelerin alt tabloları hiç oluşturulmaz; üst tablodaki girdileri yalnız “yok” olarak işaretlenir.

8.9.2İki seviyeli çeviri örneği

32 bit x86'da üst tablonun adresi CR3'tedir. İki seviyedeki tabloların her biri tam bir 4 KiB'lık sayfayı doldurur: 1024 girdi × 4 bayt. Bu seçim tesadüf değildir. Tablonun bir sayfaya tam sığması, alt tabloların da sıradan sayfalar gibi herhangi bir çerçeveye konmasını, gerekirse diske takas edilmesini sağlar.

8.9.3Kod izleme: iki seviyeli çeviri

MMU'nun yaptığı iş C ile şöyle yazılabilir:

/* 32 bit: 10 + 10 + 12 bit */
uint32_t cevir(uint32_t va) {
  uint32_t p1 = va >> 22;
  uint32_t p2 = (va >> 12) & 0x3FF;
  uint32_t d  = va & 0xFFF;
  pte_t e1 = ust[p1];
  if (!e1.p) sayfa_hatasi(va);
  pte_t e2 = e1.tablo[p2];
  if (!e2.p) sayfa_hatasi(va);
  return (e2.cerceve << 12) | d;
}

va >> 22 üst 10 biti alır. (va >> 12) & 0x3FF önce konumu atar, sonra alt 10 biti, yani orta indisi bırakır. va & 0xFFF konumdur. Fonksiyon üst tablonun girdisine, oradan ikinci seviye tablonun girdisine gider; iki adımda da mevcut biti 0 ise sayfa hatası üretir. Sonunda çerçeve numarasını 12 bit sola kaydırıp konumla birleştirir.

İlk adreste üçüncü bellek erişimi veriye yapılır. İkinci adres 20–24 MiB bölgesindedir. Bu bölge için ikinci seviye tablo hiç oluşturulmamıştır; MMU üst tabloda tuzak üretir. Tablo için bellek harcanmamış olması, hiyerarşik tablonun bütün kazancıdır.

8.9.4x86-64: dört ve beş seviyeli sayfalama

x86-64'te her sayfa tablosu 512 girdi × 8 bayt = 4 KiB'tır; yani yine tam bir sayfadır ve her seviye 9 bitlik bir indis kullanır. Dört seviye ve 12 bitlik konumla 4 × 9 + 12 = 48 bitlik sanal adres elde edilir; bu 256 TiB'lık bir adres alanıdır (Şekil 8.48). Seviyelerin adları üstten alta PML4, PDPT, PD ve PT'dir.

64 bitlik adresin üst 16 biti kullanılmaz ama rastgele de olamaz: hepsi bit 47'nin kopyası olmalıdır. Böyle adreslere kanonik adres denir. Sonuçta adres alanı ikiye ayrılır: alt yarı kullanıcıya, üst yarı çekirdeğe verilir. Beş seviyeli sayfalama (LA57) bir PML5 seviyesi ekler ve 57 bitlik, 128 PiB'lık sanal adres verir. Intel Ice Lake sunucu işlemcileri ve AMD Zen 4 ile sonrası bunu destekler; Linux 4.14'ten beri kullanabilir.

Hiyerarşik tablonun 64 bitte de işe yaramasının nedeni budur: 64 bitin hepsi kullanılmaz ve kullanılan adres alanı da seyrektir. Bugünkü x86-64 ve ARMv8 tam olarak hiyerarşik tablo kullanır. Bir orta seviye girdisinde PS biti 1 ise yürüyüş orada biter: PD seviyesinde 2 MiB'lık, PDPT seviyesinde 1 GiB'lık büyük bir sayfa bulunmuş olur.

8.9.5Dört seviyeli yürüyüş

8.9.6Büyük sayfalar

Büyük çalışma kümesiyle çalışan programlar, örneğin veritabanları, sanal makineler ve yapay zekâ iş yükleri, 4 KiB'lık sayfalarla sürekli TLB ıskası yaşar. Sorunun ölçüsü TLB erişim alanıdır (TLB reach): girdi sayısı × sayfa boyu. 1536 girdilik bir TLB, 4 KiB'lık sayfalarla yalnız 6 MiB'ı kapsar; 2 MiB'lık sayfalarla aynı TLB 3 GiB'ı kapsar (Şekil 8.50).

Tablo boyutu da küçülür. 1 GiB'ı 4 KiB'lık sayfalarla eşlemek 2³⁰ / 2¹² = 262.144 PTE, yani 2 MiB'lık tablo ister. 2 MiB'lık sayfalarla yalnız 512 PD girdisi, yani 4 KiB yeter.

Linux büyük sayfaları üç biçimde sunar. hugetlbfs, önceden ayrılmış 2 MiB ya da 1 GiB'lık sayfaları açıkça isteyen programlar içindir. Şeffaf büyük sayfalarda (transparent huge pages, THP) çekirdek uygun bölgeleri kendiliğinden büyük sayfalarla eşler. Son sürümlerdeki mTHP ise 16–64 KiB'lık ara boyutlar kullanır. Windows'ta aynı işi “large pages” görür.

Büyük sayfaların bedeli iki tanedir: iç parçalanma artar ve 2 MiB'lık bitişik bir fiziksel bölge bulmak gerekir. Bitişik bölge bulma sorunu, buddy ayırıcının ve sıkıştırmanın bugün hâlâ neden önemli olduğunu açıklar. ARMv8 bu soruna ara bir çözüm getirir: contiguous biti işaretli 16 komşu 4 KiB'lık girdi tek bir TLB girdisiyle, 64 KiB olarak tutulabilir.

8.9.7Hash sayfa tablosu

32 bitten büyük adres alanları için bir başka yaklaşım hash tablosudur.

Hash tablosunun boyutu kullanılan sayfa sayısıyla orantılıdır, adres alanının büyüklüğüyle değil. Bu, 64 bitlik seyrek adres alanları için çekici bir özelliktir. Kümelenmiş türünde her girdi tek bir sayfa yerine birden çok (örneğin 16) ardışık sayfanın çerçevelerini tutar. Bu tür, seyrek ama yer yer yoğun adres alanlarına uygundur.

8.9.8Ters sayfa tablosu

Şimdiye kadarki bütün tablolarda süreç başına bir tablo vardı ve tablonun boyu sanal adres alanına bağlıydı. Ters tablo bakış açısını tersine çevirir.

Çeviri bir arama işidir. (pid = 2, p = 5, d = 0x123) adresi için tablo baştan taranır. Girdi 0 (1, 0), girdi 1 (2, 3), girdi 2 (1, 5), girdi 3 (3, 1) eşleşmez. Girdi 4 (2, 5) eşleşir. İndisin kendisi çerçeve numarası olduğu için fiziksel adres 4 × 4096 + 0x123 = 0x4123'tür (Şekil 8.52).

Tablonun boyu fiziksel bellekle orantılıdır ve süreç sayısından bağımsızdır. 16 GiB RAM ve 4 KiB'lık çerçevelerle 4.194.304 girdi vardır; girdi başına 8 bayt ile tablo 32 MiB tutar. Bu bütün sistem için tek bir tablodur.

Bedeli üç tanedir. Birincisi aramadır: doğrusal tarama her erişimde kabul edilemeyecek kadar yavaştır. Gerçek sistemler bu yüzden (pid, p) çiftini hash'leyip doğrudan ilgili girdiye gider ve önüne bir TLB koyar. İkincisi paylaşımdır: bir çerçeve tek bir (pid, sayfa) çifti tutabildiği için paylaşımlı bellek zorlaşır. Üçüncüsü sayfa hatalarıdır: bellekte olmayan bir sayfanın diskteki yeri ters tabloda bulunmaz; bunun için süreç başına ayrı, dış bir tablo gerekir. PowerPC ve IBM POWER mimarileri hash'li ters tablo kullanır; IA-64 de bu yaklaşımı benimsemişti.

8.10Kesimleme

Sayfalama, programcıdan tamamen gizli bir mekanizmadır: adres alanı tek boyutlu bir bayt dizisidir ve sayfa sınırları programın mantıksal yapısıyla hiç ilgili değildir. Kesimleme ise adres alanını programın kendi parçalarına göre böler.

8.10.1Neden kesimleme?

Tanenbaum'un örneği bir derleyicidir. Derleyici çalışırken birçok tablo kurar: kaynak metin, sembol tablosu, sabitler tablosu, ayrıştırma ağacı ve çağrı yığını. Bu tabloların hepsi çalışma boyunca büyüyüp küçülür. Tek boyutlu bir adres alanında her tabloya ardışık bir bölge ayrılır. Bir tablo dolunca, komşusunda boş yer olsa bile ona çarpar (Şekil 8.53). Sembol tablosu kaynak metnin bölgesine taşar; derleyici ya durur ya da tabloları elle kaydırmak zorunda kalır.

Kesimleme programcının bakışına uyar. Programcı programını tek bir bayt dizisi olarak değil; ana program, fonksiyonlar, yığın, diziler ve sembol tablosu gibi ayrı birimler olarak düşünür. Kesimleme bu birimlerin her birine kendi adres alanını verir. Her kesim 0'dan başlar ve öteki kesimleri etkilemeden büyüyüp küçülebilir.

8.10.2Kesim tablosuyla çeviri

Çeviri bir kesim tablosu ile yapılır. Tablonun her girdisi bir kesimin tabanını (fiziksel başlangıç adresi) ve limitini (uzunluğunu) tutar. Tablonun bellekteki yerini kesim tablosu taban yazmacı (STBR), girdi sayısını kesim tablosu uzunluk yazmacı (STLR) tutar. (s, d) adresi için donanım önce d < limit[s] koşuluna bakar. Koşul sağlanırsa fiziksel adres taban[s] + d'dir; sağlanmazsa tuzak oluşur. Kesimleme aslında her kesim için ayrı bir taban-limit çiftidir.

Son satırda denetim olmasaydı adres 1.400 + 1.222 = 2.622 olurdu. Bu adres kesim 0'ın dışındadır; sürecin başka bir kesimine ya da başka bir sürecin belleğine ait olabilir. Limit denetimi tam olarak bunu engeller.

8.10.3Kesimi seçen bitler, aşağı büyüyen yığın

Kesim numarası adresin ayrı bir parçası olmak zorunda değildir; sanal adresin üst bitleri de kesimi seçebilir. OSTEP'tekine benzer bir örnekte sanal adres 14 bittir (16 KiB). Üst iki bit kesimi seçer: 00 kod, 01 öbek, 11 yığın. Kalan 12 bit konumdur, dolayısıyla bir kesim en çok 4 KiB olabilir. Kesim yazmaçları şöyledir:

Yığın kesiminin “yön” biti eksidir: yığın aşağı doğru büyür. Böyle bir kesimde konum negatif yorumlanır. Konumdan en büyük kesim boyu (4.096) çıkarılır; elde edilen negatif sayının mutlak değeri boydan büyük olmamalıdır. Fiziksel adres taban + negatif konumdur.

Koruma bitleri paylaşımı da mümkün kılar. r-x izinli bir kod kesimi birçok süreçte aynı fiziksel bölgeye eşlenebilir. Kesim salt okunur olduğu için süreçlerden biri ona yazmaya çalışırsa koruma hatası oluşur ve ötekiler etkilenmez.

8.10.4Kesimlemenin artıları ve eksileri

Kesimlemenin avantajları programın mantıksal yapısından gelir:

• Büyüyen ya da küçülen tablolar birbirini etkilemez.
• Kesimler ayrı ayrı derlenebilir. Bir fonksiyon kendi kesimindeyse, fonksiyon değişince öteki kesimlerin adresleri değişmez.
• Bir kütüphane ayrı bir kesime konup süreçler arasında paylaşılabilir.
• Koruma kesim başına ayarlanır: kod yalnız çalıştırılabilir, sabitler yalnız okunabilir, veri okunup yazılabilir.

Dezavantajları ise bitişik tahsisten tanıdıktır. Kesimler değişken uzunlukludur; bellekte yer değiştirdikçe aralarında delikler oluşur. Bu dış parçalanmaya, deseni yüzünden dama tahtası (checkerboarding) da denir (Şekil 8.56). Çaresi yine sıkıştırmadır. Ayrıca bir kesimin bütünüyle bellekte bulunması gerekir; çok büyük bir kesim belleğe sığmayabilir. Bu son sorunun çözümü kesimleri de sayfalamaktır; MULTICS ve Intel 386 bu yolu izledi.

8.10.5Sayfalama ile karşılaştırma

Tablo 8.24, Tanenbaum'un karşılaştırma tablosunu bugünkü donanıma uyarlayarak verir.

İki teknik farklı problemleri çözmek için doğdu. Sayfalama fiziksel bellekten büyük, tek bir doğrusal adres alanı sağlamak; kesimleme ise programı mantıksal parçalara ayırmak, bu parçaları ayrı korumak ve paylaşmak için icat edildi. Tarih sayfalamadan yana sonuçlandı: kesimlemenin koruma ve paylaşım avantajları sayfa bitleriyle elde edilebiliyor, sayfalamanın dış parçalanmadan kurtulma avantajı ise başka bir yolla elde edilemiyor.

8.11Gerçek mimariler ve uygulama

8.11.1x86: kesimleme, sayfalama ve düz model

x86 ailesi kesimlemenin bütün tarihini taşır. 8086'nın gerçek modunda fiziksel adres kesim × 16 + konum formülüyle hesaplanır. Sonuç 20 bittir, yani 1 MiB'lık bir adres alanı verir; koruma yoktur. 80386'nın korumalı modunda ise mantıksal adres bir seçici ile bir konumdan oluşur. 16 bitlik seçicinin 13 biti indis, bir biti tablo seçimi (GDT ya da LDT), iki biti istenen ayrıcalık düzeyidir (RPL). Seçici, tablodan 8 baytlık bir tanımlayıcı seçer; tanımlayıcıda kesimin tabanı ve limiti bulunur. Taban + konum doğrusal adresi verir. Doğrusal adres ardından iki seviyeli sayfalamadan geçerek fiziksel adrese çevrilir (Şekil 8.58). Bu, MULTICS'in “sayfalanmış kesimler” fikrinin donanımdaki karşılığıdır.

Donanım bu kadar zengin olmasına karşın Linux ve Windows, 32 bitte bile kesimlemeyi fiilen kapattı. Bütün kesimlerin tabanı 0, limiti 4 GiB yapıldı. Böylece doğrusal adres mantıksal adresle aynı olur; buna düz model denir. Koruma tamamen sayfa bitleriyle sağlandı. Bunun bir nedeni taşınabilirliktir: kesimleme yalnız x86'da vardı, sayfalama ise her mimaride.

x86-64'ün uzun modu bu durumu donanıma yansıttı. CS, DS, ES ve SS kesimlerinin tabanı donanımca 0 sayılır ve limit denetlenmez. Yalnız FS ve GS kesimlerinin tabanı hâlâ kullanılır: kullanıcı alanında iş parçacığına yerel depolamayı (TLS), çekirdekte çekirdek başına veriyi göstermek için. CS ise ayrıca o anki ayrıcalık düzeyini taşır.

8.11.2ARMv8-A ve RISC-V

Bugünkü öteki iki büyük mimari aynı fikirleri farklı alan adlarıyla uygular (Tablo 8.25).

İki mimaride de kesimleme yoktur. Sanal adres düzdür; çeviri çok seviyeli sayfa tablosu, TLB ve ASID ile yapılır. ARMv8'in iki tablo taban yazmacı, x86-64'ün kanonik adres bölünmesinin karşılığıdır: kullanıcı ve çekirdek adresleri ayrı tablolardan çevrilir. RISC-V'nin Sv39'u 3 × 9 + 12 = 39 bitlik, 512 GiB'lık bir adres alanı verir; daha büyük alanlar için Sv48 ve Sv57 vardır. Kısacası x86-64 ile aynı fikirler, farklı adlarla uygulanır.

8.11.3Politika ve mekanizma ayrımı

İşletim sistemi sayfalamaya dört anda katılır. Süreç oluşturulurken sayfa tablosu kurulur. Bağlam değiştirmede yeni sürecin tablosu etkinleştirilir ve TLB ayarlanır. Sayfa hatasında eksik sayfa getirilir. Süreç sonlanınca çerçeveler ve takas alanı bırakılır.

Bu işlerin bir kısmı makineye bağlıdır (MMU'nun tablo biçimi), bir kısmı değildir (hangi sayfanın ne zaman nereye konacağı). Mach çekirdeği bu ayrımı açıkça yaptı. Mekanizma çekirdekte kaldı: makineye bağlı bir MMU işleyicisi ve makineden bağımsız bir sayfa hatası işleyicisi. Politika ise kullanıcı alanında çalışan bir dış sayfalayıcıya verildi (Şekil 8.60). Sayfa hatası olunca çekirdekteki işleyici, gereken sayfayı dış sayfalayıcıdan ister. Sayfalayıcı sayfayı diskten okur ve geri verir. MMU işleyicisi de sayfayı sürecin adres alanına eşler.

Bu tasarım esneklik ve modülerlik kazandırır: farklı uygulamalar farklı sayfalama politikaları kullanabilir. Bedeli, her sayfa hatasında kullanıcı ve çekirdek sınırını birkaç kez geçmektir. Fikrin bugünkü karşılıkları da vardır. Linux'un userfaultfd düzeneği sayfa hatalarını kullanıcı alanındaki bir programa iletir; sanal makinelerin canlı göçü ve süreçlerin dondurulup başka makinede sürdürülmesi (CRIU) buna dayanır. seL4 ve Fuchsia gibi mikro çekirdeklerde ise sayfalayıcı zaten kullanıcı alanındadır.

8.12Özet

• İşlemci yalnız yazmaçlara ve ana belleğe doğrudan erişir. Bellek hiyerarşisinde önbellekleri donanım, ana belleği işletim sistemi yönetir. Önbellek 64 baytlık satırlarla çalışır ve zamansal ile uzamsal yerellik sayesinde işe yarar.
• Doğrudan eşlemeli önbellekte blok b, b mod K kümesine gider; aynı kümeye düşen bloklar birbirini kovar (çakışma ıskası). Ortalama erişim süresi T = s + m · T_alt formülüyle alttan yukarı hesaplanır; örnekte 3,8 ns, DRAM'den yaklaşık 21 kat hızlı.
• Adres alanı koruma ve yer değiştirme problemlerini çözer. Taban ve limit yazmaçlarıyla geçerli adresler taban … taban + limit − 1'dir; dışarısı tuzak üretir.
• Adres bağlama derleme, yükleme ya da yürütme zamanında yapılabilir. Bugünkü sistemler yürütme zamanında bağlar: işlemci mantıksal adres üretir, MMU onu fiziksel adrese çevirir.
• Dinamik yükleme (dlopen) kodu çağrılınca yükler. Dinamik bağlamada kütüphane kodu bir kez bellekte bulunur ve paylaşılır; ELF'te ilk çağrıda değişen kod değil, sürece özel GOT girdisidir. -fPIC konumdan bağımsız kod üretir.
• Standart takas bütün süreci taşır ve yavaştır; bugünkü sistemler soğuk sayfaları takas eder ve önce sıkıştırır.
• Bitişik tahsiste delik seçimi ilk uyan, sonraki uyan, en iyi uyan ya da en kötü uyanla yapılır. Dış parçalanmada toplam boş alan yeter ama bitişik değildir; %50 kuralına göre belleğin üçte biri kaybolabilir. İç parçalanma bloğun içindeki kullanılmayan kısımdır. Sıkıştırma delikleri birleştirir ama pahalıdır.
• Boş alan biteşlem (birim başına bir bit; k ardışık sıfır aramak doğrusal) ya da bağlı liste (adrese göre sıralıysa birleştirme sabit zamanda) ile izlenir. malloc boş listeyi boş parçaların içine gömer.
• Sayfalamada mantıksal bellek sayfalara, fiziksel bellek çerçevelere bölünür; adres (p, d) olur ve fiziksel = f × sayfa boyu + d. Dış parçalanma yoktur; iç parçalanma ortalama yarım sayfadır. Optimum sayfa boyu yaklaşık √(2se)'dir.
• Sayfa tablosu girdisi çerçeve numarasıyla birlikte P, R/W, U/S, NX, A, D ve G bitlerini tutar. Geçerli/geçersiz biti adres alanı dışını yakalar, ama koruma sayfa ayrıntı düzeyindedir.
• TLB son çevirileri tutar. Etkin erişim süresi EES = (t + ε) α + (2t + ε)(1 − α); ε = 20, t = 100 ns için α = %80'de 140 ns, %98'de 122 ns. Çok seviyeli tabloda ıska çok daha pahalıdır.
• Hiyerarşik tablo yalnız kullanılan bölgelerin alt tablolarını tutar; x86-64 dört (48 bit) ya da beş (57 bit) seviye, her seviyede 9 bit kullanır. Büyük sayfalar TLB erişim alanını büyütür. Hash tablonun boyu kullanılan sayfa sayısıyla, ters tablonunki fiziksel bellekle orantılıdır.
• Kesimleme adres alanını (kesim, konum) biçiminde mantıksal parçalara böler; her kesim bir taban-limit çiftidir ve dış parçalanmaya yol açar. x86-64'te kesimlemeden yalnız FS/GS tabanları kalmıştır; ARMv8 ve RISC-V'de kesimleme yoktur.

8.13Kavram listesi

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

• bellek yönetimi memory management
• önbellek, önbellek satırı cache, cache line
• isabet / ıska hit / miss
• taban ve limit yazmaçları base and limit registers
• yer değiştirme relocation
• mantıksal / fiziksel adres logical / physical address
• bellek yönetim birimi (MMU) memory management unit
• paylaşımlı kütüphane shared library
• takas swapping
• bitişik tahsis contiguous allocation
• iç / dış parçalanma internal / external fragmentation
• sıkıştırma compaction
• biteşlem bitmap
• buddy (kardeş) sistemi buddy system
• sayfalama, sayfa, çerçeve paging, page, frame
• sayfa tablosu, sayfa tablosu girdisi page table, page table entry
• geçerli / geçersiz biti valid–invalid bit
• TLB translation lookaside buffer
• etkin erişim süresi effective access time
• hiyerarşik sayfa tablosu hierarchical page table
• hash sayfa tablosu hashed page table
• ters sayfa tablosu inverted page table
• kesimleme segmentation

8.14Kendini Dene

1. 4 kümeli, 64 bayt satırlı, başlangıçta boş doğrudan eşlemeli bir önbellekte sırayla 16, 80, 40, 272 ve 20 adreslerine erişiliyor. Hangi erişimler isabettir?

   Cevap

   Bloklar 0, 1, 0, 4, 0; kümeler 0, 1, 0, 0, 0'dır. 16: ıska. 80: ıska. 40: blok 0 küme 0'da, isabet. 272: blok 4 blok 0'ı kovar, ıska. 20: blok 0 artık yok, ıska. Toplam 1 isabet, 4 ıska.

2. Bir sürecin taban yazmacı 5000, limit yazmacı 2000'dir. MMU önce limit denetimi yapıp sonra tabanı ekliyor. Mantıksal 1999 ve 2000 adresleri ne olur?

   Cevap

   1999 < 2000 olduğu için geçerlidir ve fiziksel 6999'a gider. 2000 limite eşittir; geçerli konumlar 0 … 1999 olduğu için tuzak oluşur.

3. Delikler adres sırasıyla 300, 120, 500 ve 200 K'dır. İstekler sırayla 180, 100 ve 450 K'dır. İlk uyan, en iyi uyan ve en kötü uyan hangisinde bir istek karşılanamaz?

   Cevap

   İlk uyan: 180 → 300 (120 kalır), 100 → aynı deliğin 120'lik artığı (20 kalır), 450 → 500 (50 kalır); hepsi yerleşir. En iyi uyan: 180 → 200 (20), 100 → 120 (20), 450 → 500 (50); hepsi yerleşir. En kötü uyan: 180 → 500 (320), 100 → 320 (220); 450 için en büyük delik 300'dür, istek karşılanamaz.

4. Sayfa boyu 1 KiB'tır ve sayfa 4, çerçeve 9'a eşlenmiştir. Mantıksal 5000 adresinin fiziksel karşılığı nedir?

   Cevap

   p = ⌊5000 / 1024⌋ = 4, d = 5000 − 4096 = 904. Fiziksel = 9 × 1024 + 904 = 9216 + 904 = 10120.

5. TLB araması 5 ns, bellek erişimi 100 ns, tablo tek seviyeli ve isabet oranı %90'dır. Etkin erişim süresi nedir? EES'nin 125 ns olması için isabet oranı kaç olmalıdır?

   Cevap

   İsabet 105 ns, ıska 205 ns. EES = 0,9 × 105 + 0,1 × 205 = 94,5 + 20,5 = 115 ns. 205 − 100α = 125 için α = 0,8, yani %80.

6. 32 bit x86 iki seviyeli sayfalamasında (10 + 10 + 12) sanal 0x00C05123 adresi için üst indis, alt indis ve konum nedir?

   Cevap

   Üst indis 0x00C05123 >> 22 = 3, alt indis (0x00C05123 >> 12) & 0x3FF = 0xC05 & 0x3FF = 5, konum 0x123'tür. Adres 12–16 MiB bölgesindedir.

7. 8 GiB RAM, 4 KiB çerçeve ve 8 baytlık girdiyle bir ters sayfa tablosu ne kadar yer kaplar? Sistemde 200 süreç olsaydı bu değer değişir miydi?

   Cevap

   2³³ / 2¹² = 2²¹ = 2.097.152 girdi; × 8 bayt = 16 MiB. Değişmezdi: ters tablo fiziksel bellekle orantılıdır ve sistemde tektir, süreç sayısına bağlı değildir.

8. Silberschatz'ın kesim tablosunda (kesim 2: limit 400, taban 4300; kesim 4: limit 1000, taban 4700) (4, 999) ve (2, 400) adresleri nereye gider?

   Cevap

   (4, 999): 999 < 1000, fiziksel 4700 + 999 = 5699. (2, 400): konum limite eşittir; geçerli konumlar 0 … 399 olduğu için tuzak.

9. 1024 K'lık bir buddy sisteminde 70 K'lık bir istek kaç K'lık blok alır ve ne kadar iç parçalanma oluşur?

   Cevap

   70 K'yı alan en küçük ikinin kuvveti 128 K'dır. Süreç 128 K'lık bloğu alır; iç parçalanma 128 − 70 = 58 K'dır.

10. Dinamik bağlanmış bir programda puts ilk kez çağrıldıktan sonra hangi sayfa değişir ve bu neden önemlidir?

    Cevap

    Yalnız sürece özel GOT sayfasındaki puts girdisi değişir; çözücü oraya gerçek adresi yazar. Programın ve libc'nin kod sayfaları değişmediği için salt okunur kalır ve bütün süreçler arasında paylaşılmaya devam eder.

8.15İleri okuma

• R. H. Arpaci-Dusseau ve A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, “Address Translation”, “Segmentation”, “Free-Space Management”, “Paging: Faster Translations (TLBs)” ve “Paging: Smaller Tables” bölümleri: kesim yazmaçları ve TLB konularını kısa, çalıştırılabilir benzetimlerle anlatır. Kitap ostep.org'da ücretsizdir.
• A. S. Tanenbaum ve H. Bos, Modern Operating Systems, Bölüm 3: yer değiştirme problemini, biteşlem ve bağlı listeyi, MMU ve çok seviyeli tablo örneklerini bu nottaki şekillerin özgün biçimleriyle anlatır.
• U. Drepper, “What Every Programmer Should Know About Memory”, 2007: önbellek, TLB ve NUMA'nın program performansına etkisini ölçümlerle gösteren uzun bir makaledir.
• Linux çekirdek belgeleri, “Transparent Hugepage Support”: şeffaf büyük sayfaların nasıl çalıştığını, ne zaman kazanç sağladığını ve nasıl ayarlandığını anlatır.

8.16Kaynaklar

1. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018 — Bölüm 9: Main Memory.
2. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı (2014) / 5. baskı (2023), Pearson — Bölüm 3: Memory Management (§3.1–3.3, 3.5–3.7).
3. R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), ostep.org — “Address Spaces”, “Address Translation”, “Segmentation”, “Free-Space Management”, “Paging”, “TLBs”, “Smaller Tables”.
4. D. E. Knuth, The Art of Computer Programming, Cilt 1, §2.5 Dynamic Storage Allocation (%50 kuralı).
5. Intel 64 and IA-32 Architectures Software Developer's Manual, Cilt 3A, Bölüm 4–5 (Paging, Protection); Arm Architecture Reference Manual for A-profile (VMSAv8-64); RISC-V Privileged Specification (Sv39/48/57).
6. U. Drepper, “How To Write Shared Libraries”, 2011; U. Drepper, “What Every Programmer Should Know About Memory”, 2007; Linux çekirdek belgeleri: mm/, “Transparent Hugepage Support”, userfaultfd.

İlgili sayfalar: Bölüm 8 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.