Sanal Bellek

Eşzamanlılık konusu üç modeli aynı iş yükünde saydı ve üçü de tek bir şeyi sessizce varsaydı: bir sürecin dokunduğu her adres bellekte hazır duruyor. Bu varsayımın donanımda karşılığı yoktur. Bir sürecin adres uzayı, makinedeki fiziksel bellekten büyük olabilir; beş süreç aynı anda çalışıyorsa toplamları neredeyse her zaman büyüktür.

Bu ders aradaki farkı kapatan soyutlamayı kurar ve bedelini sayar. Bilgisayarlar Nasıl Çalışır kursundaki Bellek Düzeni dersi adres uzayını, yığıtı ve öbeği tanımlamıştı; o tanım burada tekrarlanmaz. Eklenen tek şey şudur: adres uzayı gerçek belleğe doğrudan oturmuyorsa her erişim bir çeviriden geçer, çevirinin karşılıksız kaldığı her yer bir sayfa hatası üretir ve sayfa hataları sayılabilir.

Sanal Sayfa ile Fiziksel Sayfa

Sanal bellek (virtual memory), sürecin gördüğü adres uzayı ile makinedeki fiziksel belleği ayıran soyutlamadır. Ayrım sabit boyutlu birimler üzerinden kurulur: adres uzayı eşit büyüklükte sanal sayfalara, fiziksel bellek aynı büyüklükte fiziksel sayfalara bölünür ve hangi sanal sayfanın hangi fiziksel sayfada durduğunu bir sayfa tablosu tutar. Bu düzenlemenin adı sayfalı bellektir (paging).

Soyutlamasız taban tek cümleyle söylenir: sanal sayfa sayısı kadar fiziksel sayfa varsa eşleme birebirdir, tablo aranmaz ve ilk yüklemeden sonra hiçbir erişim diske gitmez. Ortak tanımın iş yükünde adres uzayı 16 sanal sayfadır ve beş sürecin ürettiği erişim dizisi bu sayfaların 15’ine dokunur. Taban bu 15 sayfanın bir kez getirilmesidir.

• BD1 — Makine ortak tanımın modelidir: adres uzayı 16 sanal sayfa, iş yükü beş süreç ve tohum 20260218. Hiçbir gerçek işletim sistemi çağrılmaz.
• BD2 — Erişim dizisi süreçlerin hesap adımlarından zaman sırasına göre üretilir; bekleme adımları belleğe dokunmaz.
• BD3 — Bir sayfanın diskten getirilmesi bir bekleme adımıdır, yani 30 zaman birimi. Hesap adımı 1 zaman birimidir.
• BD4 — Sayfa tablosu araması modelde ücretsizdir; ölçülen tek şey hatadır. Gerçek bir makinede tablo aramasının da bir bedeli olurdu ve bu ders onu saymaz.

"""M01/K05 ortak tanim (kesit): is yuku ve sanal sayfa erisim dizisi."""
TOHUM = 20260218
SUREC_SAYISI = 5
ADIM_SAYISI = 12
BEKLEME_SURESI = 30
SANAL_SAYFA = 16


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def is_yuku(tohum=TOHUM):
    r = uretec(tohum)
    isler = []
    for i in range(SUREC_SAYISI):
        adimlar = []
        for _ in range(ADIM_SAYISI):
            if r(10) < 3:
                adimlar.append(("BEKLE", BEKLEME_SURESI))
            else:
                taban = (i * 3) % SANAL_SAYFA
                adimlar.append(("HESAP", (taban + r(4)) % SANAL_SAYFA))
        isler.append({"ad": f"S{i+1}", "adim": adimlar,
                      "oncelik": 1 + r(3), "varis": i * 4})
    return isler


def erisim_dizisi(isler):
    olay = []
    for i in isler:
        t = i["varis"]
        for tur, deger in i["adim"]:
            if tur == "HESAP":
                olay.append((t, deger))
                t += 1
            else:
                t += deger
    olay.sort(key=lambda o: o[0])
    return [s for _, s in olay]


DIZI = erisim_dizisi(is_yuku())
print("erisim:", len(DIZI), "| ayri sanal sayfa:", len(set(DIZI)))
print("dizi:", DIZI)
for pencere in (4, 8, 16):
    genis = [len(set(DIZI[i:i + pencere])) for i in range(len(DIZI) - pencere + 1)]
    print(f"pencere {pencere:2d} calisma kumesi ortalama {sum(genis)/len(genis):5.2f} "
          f"en genis {max(genis):2d}")

erisim: 39 | ayri sanal sayfa: 15
dizi: [6, 9, 11, 9, 11, 9, 12, 1, 3, 1, 6, 9, 7, 9, 0, 2, 0, 5, 2, 3, 0, 5, 2, 3, 5, 3, 8, 9, 6, 4, 13, 12, 15, 13, 8, 12, 14, 12, 7]
pencere  4 calisma kumesi ortalama  3.47 en genis  4
pencere  8 calisma kumesi ortalama  5.75 en genis  8
pencere 16 calisma kumesi ortalama  9.25 en genis 11

Son üç satır çalışma kümesini (working set) verir: bir pencere içinde dokunulan ayrı sayfa sayısı. Dört erişimlik pencerede ortalama 3,47 ayrı sayfa var, yani dört erişimin neredeyse hepsi başka bir sayfaya gidiyor. İşlemci Önbelleği dersinde tanımlanan yerellik burada doğrudan bir sayı üretiyor ve bu iş yükünün yerelliği zayıf: sekiz erişimlik pencerelerin en genişinde sekiz ayrı sayfa dokunuluyor, yani hiç tekrar yok. Zayıf yerellik, sayfa hatası sayısının fiziksel sayfa sayısına ne kadar duyarlı olacağını baştan belirler.

Adres Çevirisi

Bir sanal adres iki parçaya ayrılır: hangi sanal sayfada olduğu ve o sayfanın içinde kaçıncı bayt olduğu. İkincisine sayfa içi ofset (page offset) denir. Sayfa boyu 256 bayt ise çeviri iki bölmedir — sayfa numarası adresin 256’ya bölümü, ofset kalanıdır. Fiziksel adres, sayfa tablosunun verdiği fiziksel sayfa numarasıyla aynı ofsetin birleşimidir.

• BD5 — Sayfa boyu 256 bayt, fiziksel sayfa sayısı 4. Erişim dizisinin ilk on adımı kullanılır; her adımın sayfa içi ofseti kurgudur, sayfa numarası ortak tanımdan gelir.
• BD6 — Boş fiziksel sayfa kalmadığında ilk giren ilk çıkar kuralı uygulanır.

"""Adres cevirisi: sanal adres -> sanal sayfa + ofset -> fiziksel adres."""
SAYFA_BOYU = 256
FIZIKSEL = 4
ILK = [6, 9, 11, 9, 11, 9, 12, 1, 3, 1]      # erisim dizisinin ilk on adimi

tablo, sira = {}, []                          # sanal sayfa -> fiziksel sayfa
print("sanal adres  sanal sayfa  ofset  durum         fiziksel  fiziksel adres")
for k, sanal in enumerate(ILK):
    adres = sanal * SAYFA_BOYU + (k * 23) % SAYFA_BOYU
    sayfa, ofset = divmod(adres, SAYFA_BOYU)
    if sayfa in tablo:
        durum = "yerlesik"
    else:
        durum = "sayfa hatasi"
        if len(sira) == FIZIKSEL:
            tablo.pop(sira.pop(0))
        bos = min(set(range(FIZIKSEL)) - set(tablo.values()))
        tablo[sayfa] = bos
        sira.append(sayfa)
    print(f"{adres:11d}  {sayfa:11d}  {ofset:5d}  {durum:12s}  {tablo[sayfa]:8d}"
          f"  {tablo[sayfa] * SAYFA_BOYU + ofset:14d}")
print("sayfa tablosu:", dict(sorted(tablo.items())))

sanal adres  sanal sayfa  ofset  durum         fiziksel  fiziksel adres
       1536            6      0  sayfa hatasi         0               0
       2327            9     23  sayfa hatasi         1             279
       2862           11     46  sayfa hatasi         2             558
       2373            9     69  yerlesik             1             325
       2908           11     92  yerlesik             2             604
       2419            9    115  yerlesik             1             371
       3210           12    138  sayfa hatasi         3             906
        417            1    161  sayfa hatasi         0             161
        952            3    184  sayfa hatasi         1             440
        463            1    207  yerlesik             0             207
sayfa tablosu: {1: 0, 3: 1, 11: 2, 12: 3}

On erişimin altısı hata verdi. Dikkat edilecek iki nokta var. Birincisi, ofset çeviride hiç değişmiyor: 2327 adresinin ofseti 23’tü, fiziksel karşılığı 279 oldu ve 279 da 256’ya bölündüğünde 23 kalanını veriyor. Sayfa boyu ikinin kuvveti seçildiğinde bu bölme bir bit ayrımına iner ve bölme işlemi hiç yapılmaz. İkincisi, sekizinci satırda 6 numaralı sanal sayfa atıldı ve yerine 1 numaralı sayfa aynı fiziksel sayfaya yerleşti; sürecin gördüğü adres değişmedi, altındaki fiziksel yer değişti. Soyutlamanın sağladığı şey budur, ödettiği şey de o satırdaki hatadır.

Sayfa Tablosunun Kendi Bedeli

Sayfa tablosu bir eşleme tutuyorsa o eşleme de bir yerde durur, ve durduğu yer bellektir. Modeldeki tablo 16 girdilidir çünkü adres uzayı 16 sanal sayfadır. Girdi sayısı adres uzayının sayfa boyuna bölümüdür ve ikisi de ikinin kuvveti seçildiğinde bir çıkarma işlemine iner.

• BD7 — Bir tablo girdisinin 8 bayt tuttuğu varsayılır; girdi fiziksel sayfa numarasını, geçerlilik bitini ve erişim bayraklarını taşır.

"""Sayfa tablosunun kendi bedeli: girdi sayisi adres uzayiyla buyur."""
GIRDI_BAYT = 8                                # bir tablo girdisi kac bayt tutuluyor
print("adres biti  sayfa boyu  girdi sayisi  tek duzeyli tablo (bayt)")
for adres_biti, sayfa_biti in ((12, 8), (22, 12), (32, 12), (48, 12)):
    girdi = 2 ** (adres_biti - sayfa_biti)
    print(f"{adres_biti:10d}  {2 ** sayfa_biti:10d}  {girdi:12d}  {girdi * GIRDI_BAYT:23d}")

adres biti  sayfa boyu  girdi sayisi  tek duzeyli tablo (bayt)
        12         256            16                      128
        22        4096          1024                     8192
        32        4096       1048576                  8388608
        48        4096   68719476736             549755813888

İlk satır bu dersin modelidir: 12 bitlik adres uzayı, 256 baytlık sayfa, 16 girdi, 128 bayt tablo. Dördüncü satır soyutlamanın ölçekle nasıl davrandığını gösteriyor — 48 bitlik bir adres uzayında tek düzeyli tablo, temsil ettiği belleğin kendisinden büyük bir yer ister ve süreç başına bir tane gerekir. Uygulanan çözüm tabloyu katmanlara bölmektir: üst düzey tablo yalnız kullanılan aralıkları gösterir, kullanılmayan aralıklar için alt tablo hiç ayrılmaz. Bunun bedeli çeviri başına birden çok tablo okumasıdır, yani soyutlama bir kez daha adım ödetir.

Üç Yordam, Aynı Dizi

Fiziksel sayfa dolduğunda hangi sayfanın atılacağına bir sayfa değiştirme (page replacement) yordamı karar verir. Üç yordam ölçülür: ilk giren ilk çıkar, en az kullanılanı atmak ve ileriye bakan taban — sonuncusu bir sonraki kullanımı en uzak olan sayfayı atar, yani geleceği bilir.

"""Uc sayfa degistirme yordami ayni erisim dizisinde. Dizi 01. blogun ciktisidir."""
DIZI = [6, 9, 11, 9, 11, 9, 12, 1, 3, 1, 6, 9, 7, 9, 0, 2, 0, 5, 2, 3, 0,
        5, 2, 3, 5, 3, 8, 9, 6, 4, 13, 12, 15, 13, 8, 12, 14, 12, 7]
GETIRME = 30                                  # bir sayfa hatasi bir bekleme adimidir


def sayfa_hatasi(dizi, fiziksel, yordam="fifo"):
    """yordam: fifo | en_az | en_iyi (ileriyi goren taban)"""
    yerlesik, sira, hata = [], [], 0
    for k, s in enumerate(dizi):
        if s in yerlesik:
            if yordam == "en_az":
                sira.remove(s)
                sira.append(s)
            continue
        hata += 1
        if len(yerlesik) < fiziksel:
            yerlesik.append(s)
            sira.append(s)
            continue
        if yordam in ("fifo", "en_az"):
            cikan = sira.pop(0)
        else:
            uzaklik = {}
            for y in yerlesik:
                uzaklik[y] = dizi.index(y, k + 1) if y in dizi[k + 1:] else 10**9
            cikan = max(yerlesik, key=lambda y: uzaklik[y])
            sira.remove(cikan)
        yerlesik.remove(cikan)
        yerlesik.append(s)
        sira.append(s)
    return hata


zorunlu = len(set(DIZI))
print("erisim", len(DIZI), "| zorunlu hata:", zorunlu,
      "| tabanin suresi:", len(DIZI) + zorunlu * GETIRME)
print("fiziksel  fifo  en_az  en_iyi   fifo fazladan  fifo suresi")
for f in (2, 3, 4, 5, 6, 8, 15):
    a = sayfa_hatasi(DIZI, f, "fifo")
    b = sayfa_hatasi(DIZI, f, "en_az")
    c = sayfa_hatasi(DIZI, f, "en_iyi")
    print(f"  {f:6d}  {a:4d}  {b:5d}  {c:6d}   {a - zorunlu:13d}"
          f"  {len(DIZI) + a * GETIRME:11d}")

erisim 39 | zorunlu hata: 15 | tabanin suresi: 489
fiziksel  fifo  en_az  en_iyi   fifo fazladan  fifo suresi
       2    30     31      27              15          939
       3    28     28      23              13          879
       4    23     23      19               8          729
       5    23     22      18               8          729
       6    20     20      17               5          639
       8    19     17      15               4          609
      15    15     15      15               0          489

Üç sayı yan yana duruyor. Taban: 15 fiziksel sayfa, 15 zorunlu hata, 489 zaman birimi. Kurulum: 2 fiziksel sayfa, ilk giren ilk çıkar, 30 hata. Bedel: 15 fazladan hata ve 939 − 489 = 450 zaman birimi. Bu iş yükünde sanal bellek soyutlaması, belleği yedi buçuk kat küçültmenin karşılığında koşum süresini 1,92 katına çıkarıyor.

Bedelin nereden geldiği tabloda açık. Erişimlerin 30’u hatayla sonuçlanıyor, yani 39 erişimin yaklaşık dörtte üçü diske gidiyor ve makine hesap yapmaktan çok sayfa getiriyor. Bu duruma çırpınma (thrashing) denir: fiziksel sayfa sayısı çalışma kümesinin altına düştüğünde her yeni erişim, birazdan yeniden istenecek bir sayfayı atar. Çalışma kümesi ölçümü bunu önceden söylüyordu — dört erişimlik pencerede ortalama 3,47 ayrı sayfa varken iki fiziksel sayfayla çalışmak, pencerenin yarısını her turda yeniden getirmek demektir.

Daha Akıllı Yordam Her Zaman Kazandırmaz

En az kullanılanı atan yordam, ilk giren ilk çıkardan daha çok bilgi kullanır: hangi sayfaya en son ne zaman dokunulduğunu tutar. Buna karşın iki fiziksel sayfada 31 hata veriyor, ilk giren ilk çıkar ise 30. Daha çok bilgi kullanan yordam bu noktada bir hata daha üretiyor.

Bu farkın nasıl okunacağı önemlidir. Ortak tanımın çözünürlük kuralı şudur: 39 erişimde bir hatalık fark 0,0256’lık bir orandır ve ölçülmemiş sayılır; anlamlı fark en az üç hatadır. Yani “en az kullanılanı atmak daha kötüdür” cümlesi de yazılamaz. Tabloya bu ölçütle bakıldığında sonuç daha da nettir: iki yordam arasındaki fark hiçbir satırda üçe ulaşmıyor — en büyüğü sekiz fiziksel sayfadaki 19’a karşı 17, yani iki hata. Bu iş yükünde en az kullanılanı atmanın üstünlüğü ölçülmemiştir. Onu tercih eden bir gerçekleştirim, sayfa başına bir zaman damgası tutmanın bedelini karşılıksız ödemiş olur.

Aynı ölçüt fiziksel sayfa eklemeye de uygulanır. 3’ten 4’e çıkmak ilk giren ilk çıkarı 28’den 23’e indiriyor: beş hata, anlamlı. 4’ten 5’e çıkmak ise 23’te bırakıyor: sıfır. Bir fiziksel sayfa daha vermek burada hiçbir şey satın almıyor. 5’ten 6’ya çıkmak yeniden üç hata kazandırıyor. Kaynak eklemenin getirisi düzgün azalmıyor, basamaklı ilerliyor ve basamağın nerede olduğu iş yükünün erişim düzenine bağlı.

İleriye Bakan Taban Neden Ulaşılamaz

Üçüncü sütun her satırda diğer ikisinin altında: 2 sayfada 27, 8 sayfada 15. Sekiz fiziksel sayfada 15 hata, zorunlu hata sayısına eşittir — yani ileriye bakan yordam sekiz sayfayla hiçbir sayfayı iki kez getirmiyor.

Bu sütun bir yordam değil, bir alt sınırdır. Atılacak sayfayı seçmek için erişim dizisinin geri kalanını okuması gerekir; o dizi, henüz çalıştırılmamış programın üreteceği adreslerdir. Bir çizelgeleyicinin hangi süreci ne zaman kesmeye karar vereceği, bir kullanıcının hangi veriyi isteyeceği ve bir dalın hangi yöne gideceği çeviri anında bilinmez. Alt sınırın işlevi uygulanmak değil, ölçmektir: sekiz fiziksel sayfada ilk giren ilk çıkarın 19 hatası, alt sınırın 15’ine dört hata uzaktır ve iyileştirme için kalan bütün pay budur.

Özet

• Sanal bellek, sürecin gördüğü adres uzayı ile fiziksel belleği sabit boyutlu sayfalar üzerinden ayırır; her erişim sanal sayfa numarası ile sayfa içi ofsete bölünüp çevrilir.
• Ortak tanımın 39 erişimlik dizisi 15 ayrı sanal sayfaya dokunuyor; taban 15 zorunlu hata ve 489 zaman birimi, iki fiziksel sayfayla kurulum 30 hata ve 939 zaman birimi, bedel 450 zaman birimidir.
• Fiziksel sayfa sayısı çalışma kümesinin altına düştüğünde çırpınma başlar: 39 erişimin 30’u diske gider ve makine hesaptan çok sayfa getirir.
• En az kullanılanı atan yordam ile ilk giren ilk çıkar arasındaki fark hiçbir fiziksel sayfa sayısında üç hataya ulaşmıyor; bu iş yükünde ikisi arasında ölçülmüş bir üstünlük yoktur.
• Fiziksel sayfa eklemenin getirisi basamaklıdır: 3’ten 4’e geçiş beş hata kazandırırken 4’ten 5’e geçiş hiçbir şey kazandırmıyor.

Sonraki Adım

Bu ders belleği sabit boyutlu sayfalar hâlinde dağıttı ve her isteğin bir sayfaya sığdığını varsaydı. Bir sürecin öbeğinde durum böyle değildir: istekler farklı boyutlardadır, sırasız gelir ve sırasız bırakılır. Sonraki ders aynı makinede öbek yönetimini modeller ve iki ayırıcı yordamını aynı olay dizisinde karşılaştırır — biri bir isteği reddederken diğeri hepsini yerleştiriyor, ama geriye kullanılamaz bir kırıntı bırakıyor.