Bellek Ayırma

Sanal bellek dersinde her istek aynı boyuttaydı: bir sayfa. Sabit boyut, yerleştirme sorununu ortadan kaldırır — boş bir fiziksel sayfa varsa her sanal sayfa oraya sığar ve hangi boşluğun seçildiği sonucu değiştirmez. Bir sürecin öbeğinde durum böyle değildir. İstekler farklı boyutlardadır, sırasız gelir, sırasız bırakılır ve hangi boşluğa yerleştirildikleri sonraki isteklerin yerleşip yerleşmeyeceğini belirler.

Bilgisayarlar Nasıl Çalışır kursundaki Bellek Düzeni dersi öbeği, ayırıcıyı ve parçalanmayı tanımlamıştı; bu ders o tanımları tekrarlamaz. Eklediği tek şey ölçümdür: iki yerleştirme yordamı aynı olay dizisinde koşturulur ve aralarındaki fark yerleşen istek, boşta kalan bayt ve kullanılamaz kırıntı cinsinden sayılır.

Taban, Kurulum ve Ölçülecek Olan

Soyutlamasız taban bir ayırıcı değildir: öbekte tek bir sınır değişkeni tutulur, her istek sınırı kendi boyutu kadar ileri iter ve bırakma diye bir işlem yoktur. Bu düzenin yönetim maliyeti bir toplama işlemidir; karşılığında bırakılan bellek geri alınmaz.

Kurulum, bırakmayı ve yeniden kullanmayı ekler. Öbek bölümlere ayrılır, her bölüm ya bir ada aittir ya boştur, bırakılan bölüm boşa döner ve komşu boşluklar birleştirilir. Ölçülecek olan şudur: bu defterin tutulması kaç isteği kurtarıyor ve geriye ne bırakıyor.

• BD8 — Öbek 1024 bayttır ve tek parçadır. Ayırıcı istenen bayt sayısını tam olarak verir; hizalama ya da başlık payı yoktur, dolayısıyla bu derste iç parçalanma sıfırdır.
• BD9 — Olay dizisi ortak tanımdan gelir: altı ayırma, iki bırakma, iki ayırma daha. Toplam istenen 1254 bayttır, yani öbekten büyüktür; bırakma olmadan hepsi yerleşemez.
• BD10 — İki yerleştirme yordamı ölçülür. İlk uyan (first fit) listedeki ilk yeterli bölümü seçer; en iyi uyan (best fit) yeterli bölümlerin en küçüğünü seçer.
• BD11 — Bırakma anında yalnız komşu boşluklar birleşir; uzaktaki iki boşluk ayrı kalır. Taşıma ya da sıkıştırma yapılmaz.

"""M01/K05 ortak tanim (kesit): ayirici , dis parcalanma ve uc uca taban."""
OBEK = 1024
OLAY = [("A", "a", 200), ("A", "b", 150), ("A", "c", 200), ("A", "d", 100),
        ("A", "e", 200), ("A", "f", 174),
        ("B", "b"), ("B", "d"),                  # 150 ve 100 baytlik iki bosluk
        ("A", "g", 90), ("A", "h", 140)]


def ayir(olaylar, boyut=OBEK, yordam="ilk_uyan"):
    """olaylar: ("A", ad, boyut) ayir , ("B", ad) birak."""
    bolum = [{"ad": None, "bas": 0, "boy": boyut}]      # ad None ise bos
    yerlesen = reddedilen = 0
    for olay in olaylar:
        if olay[0] == "A":
            _, ad, iste = olay
            adaylar = [b for b in bolum if b["ad"] is None and b["boy"] >= iste]
            if not adaylar:
                reddedilen += 1
                continue
            sec = adaylar[0] if yordam == "ilk_uyan" else min(adaylar, key=lambda b: b["boy"])
            k = bolum.index(sec)
            kalan = sec["boy"] - iste
            bolum[k] = {"ad": ad, "bas": sec["bas"], "boy": iste}
            if kalan:
                bolum.insert(k + 1, {"ad": None, "bas": sec["bas"] + iste, "boy": kalan})
            yerlesen += 1
        else:
            for b in bolum:
                if b["ad"] == olay[1]:
                    b["ad"] = None
            k = 0                                        # komsu bosluklar birlesir
            while k < len(bolum) - 1:
                if bolum[k]["ad"] is None and bolum[k + 1]["ad"] is None:
                    bolum[k]["boy"] += bolum[k + 1]["boy"]
                    bolum.pop(k + 1)
                else:
                    k += 1
    bosluk = [b["boy"] for b in bolum if b["ad"] is None]
    return {"yerlesen": yerlesen, "reddedilen": reddedilen, "bos": sum(bosluk),
            "en_buyuk_bosluk": max(bosluk) if bosluk else 0, "parca": len(bosluk),
            "yerlesim": [(b["ad"] or "-", b["bas"], b["boy"]) for b in bolum]}


def uc_uca(olaylar, boyut=OBEK):
    """Soyutlamasiz taban: birakma yok , yalnizca ileri kayan bir sinir."""
    sinir, yerlesen, reddedilen = 0, 0, 0
    for olay in olaylar:
        if olay[0] == "A":
            if sinir + olay[2] <= boyut:
                sinir, yerlesen = sinir + olay[2], yerlesen + 1
            else:
                reddedilen += 1
    return yerlesen, reddedilen


def uretec(tohum):
    d = tohum

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


def uzun_dizi(tohum, adet=200):
    """Uzun olay dizisi: her adimda ya ayirma ya rastgele bir birakma."""
    r = uretec(tohum)
    olaylar, canli, sayac = [], [], 0
    for _ in range(adet):
        if canli and r(10) < 5:
            olaylar.append(("B", canli.pop(r(len(canli)))))
        else:
            ad = f"n{sayac}"
            sayac += 1
            olaylar.append(("A", ad, 16 + r(8) * 16))
            canli.append(ad)
    return olaylar


print("obek", OBEK, "bayt | istek", sum(1 for o in OLAY if o[0] == "A"),
      "| toplam istenen", sum(o[2] for o in OLAY if o[0] == "A"))
print("taban (uc uca , birakma yok): yerlesen %d reddedilen %d" % uc_uca(OLAY))
print("yordam        yerlesen  reddedilen  bos  en buyuk bosluk  parca")
for y in ("ilk_uyan", "en_iyi_uyan"):
    a = ayir(OLAY, OBEK, y)
    print(f"  {y:12s} {a['yerlesen']:5d} {a['reddedilen']:10d} {a['bos']:5d}"
          f" {a['en_buyuk_bosluk']:14d} {a['parca']:6d}")
    print("   ", " ".join(f"{ad}@{bas}+{boy}" for ad, bas, boy in a["yerlesim"]))
print()
print("uzun dizi (200 olay)   ayirma  ilk uyan  en iyi uyan")
for tohum in (20260218, 20260219):
    U = uzun_dizi(tohum)
    istek = sum(1 for o in U if o[0] == "A")
    i = ayir(U, OBEK, "ilk_uyan")
    e = ayir(U, OBEK, "en_iyi_uyan")
    print(f"  tohum {tohum}    {istek:4d}  {i['yerlesen']:8d}  {e['yerlesen']:11d}")

obek 1024 bayt | istek 8 | toplam istenen 1254
taban (uc uca , birakma yok): yerlesen 6 reddedilen 2
yordam        yerlesen  reddedilen  bos  en buyuk bosluk  parca
  ilk_uyan         7          1   160            100      2
    a@0+200 g@200+90 -@290+60 c@350+200 -@550+100 e@650+200 f@850+174
  en_iyi_uyan      8          0    20             10      2
    a@0+200 h@200+140 -@340+10 c@350+200 g@550+90 -@640+10 e@650+200 f@850+174

uzun dizi (200 olay)   ayirma  ilk uyan  en iyi uyan
  tohum 20260218     119        96           98
  tohum 20260219     114       100           99

Üç sayı yan yana. Taban: uç uca ayırma, 6 yerleşen, 2 reddedilen ve tek bir sınır değişkeni. Kurulum: bölüm listesi tutan ayırıcı, en iyi uyan ile 8 yerleşen. Bedel: her istekte taranan bir bölüm listesi, sekiz bölüme bölünmüş bir öbek ve geriye kalan iki boşluk.

Bırakmanın kazandırdığı açık: taban 1024 baytı bir kez dağıtıp bitiriyor, ayırıcı ise bırakılan 250 baytı yeniden kullanarak iki isteği daha karşılayabiliyor. Kazancın tamamı alınmıyor ama — ilk uyan yordamı sekiz isteğin yalnız yedisini yerleştiriyor.

Dış Parçalanma Bir Red Sebebidir

b ve d bırakıldığında öbekte 150 ve 100 baytlık iki boşluk oluşuyor. İkisi komşu olmadığı için birleştirme hiç devreye girmiyor; toplam 250 bayt boş, ama tek parça hâlinde en fazla 150 bayt var. Bu duruma dış parçalanma (external fragmentation) denir: boş belleğin toplamı yeterlidir, tek bir parça hâlinde yeterli değildir.

Sonucu son iki istekte görünüyor. İlk uyan, 90 baytlık g isteğini listedeki ilk yeterli boşluğa — 150 baytlığa — koyuyor ve geriye 60 bayt bırakıyor. Ardından gelen 140 baytlık h isteği için elde 60 ve 100 baytlık iki boşluk kalıyor; toplam 160, yani yeter, ama hiçbiri tek başına yetmez.

"""Dis parcalanma: bos toplam yeter , tek parca yetmez. Yerlesimler 01. blogun ciktisidir."""
YERLESIM = {
    "ilk_uyan": [("a", 200), ("g", 90), ("-", 60), ("c", 200),
                 ("-", 100), ("e", 200), ("f", 174)],
    "en_iyi_uyan": [("a", 200), ("h", 140), ("-", 10), ("c", 200), ("g", 90),
                    ("-", 10), ("e", 200), ("f", 174)],
}
for ad, yerlesim in YERLESIM.items():
    bosluk = sorted((b for n, b in yerlesim if n == "-"), reverse=True)
    bos, en_buyuk = sum(bosluk), bosluk[0]
    print(f"{ad:12s} bos {bos:4d}  en buyuk {en_buyuk:4d}  parca {len(bosluk)}"
          f"  dis parcalanma orani {1 - en_buyuk / bos:.4f}")
    for iste in (10, 60, 90, 140):
        print(f"    {iste:4d} baytlik istek: bos yeterli {bos >= iste}"
              f" , tek parca yeterli {en_buyuk >= iste}")

ilk_uyan     bos  160  en buyuk  100  parca 2  dis parcalanma orani 0.3750
      10 baytlik istek: bos yeterli True , tek parca yeterli True
      60 baytlik istek: bos yeterli True , tek parca yeterli True
      90 baytlik istek: bos yeterli True , tek parca yeterli True
     140 baytlik istek: bos yeterli True , tek parca yeterli False
en_iyi_uyan  bos   20  en buyuk   10  parca 2  dis parcalanma orani 0.5000
      10 baytlik istek: bos yeterli True , tek parca yeterli True
      60 baytlik istek: bos yeterli False , tek parca yeterli False
      90 baytlik istek: bos yeterli False , tek parca yeterli False
     140 baytlik istek: bos yeterli False , tek parca yeterli False

İlk uyanın reddi bir bellek yetersizliği değildir; 160 bayt boş dururken 140 baytlık istek geri çevriliyor. Dış parçalanma oranı — boş belleğin en büyük parçanın dışında kalan payı — burada 0,3750’dir.

En iyi uyan aynı iki isteği de yerleştiriyor. 90 baytlık g isteğini 100 baytlık boşluğa koyup 10 bayt bırakıyor, 140 baytlık h isteğini 150 baytlık boşluğa koyup yine 10 bayt bırakıyor. Sekiz istek de yerleşti, reddedilen yok. Fakat geriye kalan iki boşluk 10’ar bayttır ve dış parçalanma oranı 0,5000’e çıkmıştır: 20 bayt boş görünüyor, 11 baytlık tek bir istek bile karşılanamıyor. Kullanılamaz bellek, kullanılmayan bellekten farklı bir kalemdir ve yalnız boş bayt toplamına bakan bir ölçüt onu göstermez.

En İyi Uyan Her Zaman Kazandırmaz

Sekiz istekten yedisi ile sekizi arasındaki fark, en iyi uyanı genel bir kural gibi okumaya yol açar. Çıktının son bloğu bunu sınıyor: aynı ayırıcı, 200 olaylık iki ayrı dizide.

İlk iş yükünde 119 ayırma isteğinden ilk uyan 96’sını, en iyi uyan 98’ini yerleştiriyor. Yani en iyi uyan iki istek önde. İkinci iş yükünde 114 istekten ilk uyan 100’ünü, en iyi uyan 99’unu yerleştiriyor; bu kez ilk uyan bir istek önde. Sıralama iş yüküyle birlikte dönüyor. Farkların büyüklüğü de küçüktür: iki ve bir istek, yaklaşık yüz isteğin üzerinde yüzde iki mertebesinde bir oynama.

Bu iki gözlem birlikte tek bir sonuç verir: bu ölçümde iki yordam arasında bir üstünlük kurulmamıştır. Kurulan tek şey, sekiz olaylık dizide en iyi uyanın bir isteği daha yerleştirdiği ve karşılığında daha kullanılamaz bir kalıntı bıraktığıdır. Bir yordamın seçimi, iş yükünün boyut dağılımına ve bırakma düzenine bağlıdır; tek dizide ölçülmüş bir sıralama ölçülmemiş sayılır.

Bir de bu modelin saymadığı bir bedel var. Buradaki gerçekleştirim her istekte bölüm listesinin tamamını tarıyor, bu yüzden iki yordamın arama maliyeti eşit çıkıyor. Gerçek bir ilk uyan gerçekleştirimi ilk yeterli bölümü bulunca durabilir; en iyi uyan duramaz, çünkü daha küçük bir yeterli bölüm olup olmadığını ancak listeyi bitirince bilir. Bu fark bu derste ölçülmedi ve ölçülmediği için de bir üstünlük gerekçesi olarak yazılmıyor.

Sıkıştırma Neden Bedava Değil

Dış parçalanmanın kesin bir çözümü vardır: yerleşik bölümleri öbeğin başına doğru kaydırıp bütün boşlukları tek parçada toplamak. Buna sıkıştırma (compaction) denir ve ilk uyanın reddettiği isteği kurtarır.

• BD12 — Sıkıştırma yalnız bir ölçüm olarak yapılır; bir bloğun taşınması, o bloğun baytlarının yeni yerine kopyalanması sayılır.

"""Sikistirmanin bedeli: bosluklari tek parcaya toplamak kac bayt tasitir."""
YERLESIM = [("a", 0, 200), ("g", 200, 90), ("-", 290, 60), ("c", 350, 200),
            ("-", 550, 100), ("e", 650, 200), ("f", 850, 174)]     # ilk uyan sonucu

sinir, tasinan, tasinan_blok = 0, 0, 0
for ad, bas, boy in YERLESIM:
    if ad == "-":
        continue
    if bas != sinir:
        tasinan += boy
        tasinan_blok += 1
    sinir += boy
print("yerlesik bayt:", sinir, "| tek parcaya inen bosluk:", 1024 - sinir)
print("tasinan blok:", tasinan_blok, "| tasinan bayt:", tasinan)
print("140 baytlik istek sikistirmadan sonra yerlesir mi:", 1024 - sinir >= 140)

yerlesik bayt: 864 | tek parcaya inen bosluk: 160
tasinan blok: 3 | tasinan bayt: 574
140 baytlik istek sikistirmadan sonra yerlesir mi: True

Reddedilen istek kurtuluyor, ama bedeli 574 baytın kopyalanmasıdır — öbekte yerleşik duran 864 baytın üçte ikisi. Bu, ayırmanın kendisiyle kıyaslanamayacak kadar büyük bir iştir ve tek bir istek için ödenir.

İkinci ve daha ağır bedel kopyalama değildir. Taşınan her bloğun adresi değişir, dolayısıyla o bloğu gösteren her başvurunun da değişmesi gerekir. Adreslerin doğrudan sayı olarak tutulduğu bir düzende hangi sayının bir işaretçi hangisinin veri olduğu bilinemez, bu yüzden sıkıştırma uygulanamaz. Uygulanabildiği düzenlerde ise bloğa doğrudan değil bir dolaylı tablo üzerinden erişilir; o zaman taşıma tabloda tek satır değiştirmeye iner, ama bu kez her erişim bir tablo okuması daha ödemeye başlar. Soyutlamanın ödettiği adım yine ortadan kalkmıyor, yalnız yer değiştiriyor.

İç Parçalanma Buraya Girmiyor

Ayırıcı istenen bayt sayısını tam veriyor: 90 istendiğinde 90 bayt ayrılıyor. Bu yüzden bu derste iç parçalanma sıfırdır ve tabloda böyle bir sütun yoktur. Sabit boyutlu birimlerle çalışan her düzende ise vardır — sanal bellek dersinde bir sayfanın son baytına kadar dolmaması iç parçalanmadır, dosya sisteminde bir bloğun yarısının boş kalması da öyle. Bu iki parçalanma birbirinin karşılığıdır: sabit boyut dış parçalanmayı ortadan kaldırır ve yerine iç parçalanma koyar; değişken boyut iç parçalanmayı ortadan kaldırır ve yerine dış parçalanma koyar. Dördüncü ders bu ödünleşimin diğer ucunu bayt cinsinden ölçecek.

Özet

• Uç uca ayıran taban 8 isteğin 6’sını yerleştiriyor ve bırakmayı hiç kullanmıyor; bölüm listesi tutan ayırıcı bırakılan 250 baytı yeniden kullanarak bir ya da iki isteği daha karşılıyor.
• İlk uyan 7 istek yerleştirip birini reddediyor: 160 bayt boş dururken 140 baytlık istek geri çevriliyor, çünkü en büyük tek parça 100 bayttır. Dış parçalanma budur.
• En iyi uyan 8 isteğin hepsini yerleştiriyor ama geriye 10’ar baytlık iki boşluk bırakıyor; dış parçalanma oranı 0,3750’den 0,5000’e çıkıyor ve kalan 20 bayt kullanılamaz.
• İki yüz olaylık iki ayrı dizide sıralama dönüyor: ilk iş yükünde en iyi uyan iki istek önde, ikincisinde ilk uyan bir istek önde. İki yordam arasında bir üstünlük ölçülmemiştir.
• Bu modelde iki yordam da bölüm listesinin tamamını tarıyor; arama maliyeti farkı ölçülmedi ve gerekçe olarak kullanılmıyor.

Sonraki Adım

Bu derste bırakma işlemini programın kendisi yaptı: b ve d bırakıldı, yerleri geri alındı. Bırakmayı unutan bir program belleği sızdırır, erken bırakan bir program serbest bırakılmış adresi kullanır. Sonraki ders bu kararı programdan alıp çalışma zamanına devreden düzeni modeller: erişilebilirlik ölçütüyle çalışan bir toplayıcı, 40 nesnenin hangilerini yaşattığını belirler ve bunun bedeli bir duraklatmadır. Ölçülecek soru şudur — duraklatmanın uzunluğu toplanan çöple mi, yoksa yaşayan nesneyle mi orantılıdır.