Bellek Sınırı ve Tahliye Politikaları

Kalıcılık kararı, çökmeden sonra ne olacağını çözer. Çökmeden önce gelen bir sınır ise bu konuda hiç ele alınmadı: bellek biter. Buraya kadarki bütün ölçümlerde depo serbestçe büyüdü; 19.040 ödünç girişi 1.593.100 bayt tuttu ve kimse durdurmadı. Gerçek bir kurulumda depoya bir üst sınır verilir ve sınıra ulaşıldığında her yeni giriş bir eskisinin yerine geçer.

Bu dersin sorusu, hangi eskisinin gideceğidir. Tahliye politikalarının tanımları ve isabet oranı aritmetiği önceki kurslarda kuruldu; burada tekrarlanmaz. Ölçülen şey, aynı ödünç erişim izinde dört politikanın aynı bayt bütçesiyle ne satın aldığıdır.

Bütçe Giriş Sayısı Değil, Bayttır

Sınır giriş sayısıyla verilirse politikaların maliyeti görünmez olur. Her politika kendi kararını verebilmek için girişe bir şeyler ekler ve o ek, sınırın içinden yenir.

KB6. Politika üstverileri: en az kullanılan, erişim sırasındaki yerini tutmak için iki bağ (16 bayt); en az sık kullanılan, bir sayaç ve sıklık kovasındaki bağ (24 bayt); rastgele, yalnız örnekleme dizisindeki yeri (8 bayt); süreye göre, süre sonu damgası ve sıra bilgisi (16 bayt). Giriş gövdesinin maliyeti önceki derslerdeki gibidir: anahtar, değer ve 48 bayt.

KB7. Erişim izi kütüphanenin ödünç örüntüsüdür: dört dönem boyunca isteklerin yüzde 60’ı o dönemin iki yüz kitaplık ders listesine, yüzde 25’i hiç değişmeyen bin kitaplık popüler kesime, yüzde 15’i yirmi bin kitaplık katalogun geri kalanına gider. Dönem değiştiğinde ders listesi tümüyle yenilenir.

KB8. Katalog girişleri üç bin erişimlik bir tazelik penceresiyle konur; bu pencere yalnız süreye göre politikayı ilgilendirir.

// politika.mjs — aynı bayt bütçesinde dört tahliye politikası
export const TEMEL = 48, OMUR = 3000;            // KB1: giriş üstverisi, KB8: tazelik penceresi

export function uretec(t0) {
  let a = t0 >>> 0;
  return () => { a = (a + 0x6d2b79f5) >>> 0; let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}

// Ödünç izi: dört dönem; her dönemde 200 kitaplık ders listesi değişir.
export function izUret(uzunluk, tohum, katalog = 20000) {
  const r = uretec(tohum), iz = [], donem = uzunluk / 4;
  for (let i = 0; i < uzunluk; i++) {
    const d = Math.floor(i / donem), p = r();
    let k;
    if (p < 0.60) k = d * 200 + Math.floor(r() * 200);        // dönemin ders listesi
    else if (p < 0.85) k = 1000 + Math.floor(r() * 1000);     // kalıcı popüler kitaplar
    else k = Math.floor(r() * katalog);                       // katalogun geri kalanı
    iz.push('kitap:' + String(k).padStart(5, '0'));
  }
  return iz;
}
export const deger = (a) => {
  const k = Number(a.slice(6));
  return `sube=${1 + (k % 8)};raf=${String.fromCharCode(65 + (k % 26))}${String(k % 100).padStart(2, '0')}`;
};

class Onbellek {
  constructor(butce, ustveri) {
    this.butce = butce; this.ust = ustveri; this.g = new Map();
    this.bayt = 0; this.isabet = 0; this.iska = 0; this.dusen = 0; this.saat = 0;
  }
  maliyet(a) { return Buffer.byteLength(a) + Buffer.byteLength(deger(a)) + TEMEL + this.ust; }
  eris(a) {
    this.saat++;
    if (this.g.has(a) && this.gecerli(a)) { this.isabet++; this.dokun(a); return; }
    if (this.g.has(a)) { this.dusen++; this.sil(a); }
    this.iska++;
    while (this.bayt + this.maliyet(a) > this.butce) this.sil(this.kurban());
    this.g.set(a, deger(a)); this.bayt += this.maliyet(a); this.eklendi(a);
  }
  sil(a) { this.bayt -= this.maliyet(a); this.g.delete(a); this.silindi(a); }
  gecerli() { return true; }
  dokun() {} eklendi() {} silindi() {}
  get ustveriBayt() { return this.g.size * this.ust; }
}

export class AzKullanilan extends Onbellek {      // en az kullanılan: erişim sırası bağı, 16 bayt
  constructor(b) { super(b, 16); }
  dokun(a) { const d = this.g.get(a); this.g.delete(a); this.g.set(a, d); }
  kurban() { return this.g.keys().next().value; }
}

export class AzSik extends Onbellek {             // en az sık kullanılan: sayaç + kova bağı, 24 bayt
  constructor(b) { super(b, 24); this.sayac = new Map(); this.kova = new Map(); this.enAz = 1; }
  #tasi(a, eski, yeni) {
    if (eski) { const s = this.kova.get(eski); s.delete(a); if (s.size === 0 && this.enAz === eski) this.enAz = yeni; }
    if (yeni) { if (!this.kova.has(yeni)) this.kova.set(yeni, new Set()); this.kova.get(yeni).add(a); }
  }
  dokun(a) { const c = this.sayac.get(a); this.sayac.set(a, c + 1); this.#tasi(a, c, c + 1); }
  eklendi(a) { this.sayac.set(a, 1); this.#tasi(a, 0, 1); this.enAz = 1; }
  silindi(a) { this.#tasi(a, this.sayac.get(a), 0); this.sayac.delete(a); }
  kurban() {
    while (!this.kova.get(this.enAz) || this.kova.get(this.enAz).size === 0) this.enAz++;
    return this.kova.get(this.enAz).values().next().value;
  }
}

export class Rastgele extends Onbellek {          // rastgele: yalnız anahtar dizisi, 8 bayt
  constructor(b, tohum) { super(b, 8); this.dizi = []; this.yer = new Map(); this.r = uretec(tohum); }
  eklendi(a) { this.yer.set(a, this.dizi.length); this.dizi.push(a); }
  silindi(a) {
    const i = this.yer.get(a), son = this.dizi.pop();
    if (i < this.dizi.length) { this.dizi[i] = son; this.yer.set(son, i); }
    this.yer.delete(a);
  }
  kurban() { return this.dizi[Math.floor(this.r() * this.dizi.length)]; }
}

export class SureyeGore extends Onbellek {        // süreye göre: süre sonu damgası + sıra, 16 bayt
  constructor(b) { super(b, 16); this.sonu = new Map(); }
  gecerli(a) { return this.sonu.get(a) > this.saat; }
  eklendi(a) { this.sonu.set(a, this.saat + OMUR); }
  silindi(a) { this.sonu.delete(a); }
  kurban() { return this.g.keys().next().value; }   // sabit ömürde en yakın süre sonu = en eski giriş
  get dolmus() {                                    // süresi dolmuş ama hâlâ tutulan girişler
    let sayi = 0, bayt = 0;
    for (const a of this.g.keys()) if (this.sonu.get(a) <= this.saat) { sayi++; bayt += this.maliyet(a); }
    return { sayi, bayt };
  }
}

Süreye göre politikanın kurban seçimi bir sadeleştirme taşır ve açıkça söylenmesi gerekir: bütün girişler aynı ömürle konduğu için “süre sonu en yakın olan”, “en eski eklenen” ile aynı girişi işaret eder. Bu yüzden kurban, erişimde yeri değişmeyen ekleme sırasının başındadır.

Aynı İzde Dört Politika

// olcum.mjs — dört politikanın aynı bütçedeki giriş sayısı ve isabet oranı
import { AzKullanilan, AzSik, Rastgele, SureyeGore, izUret, deger, TEMEL } from './politika.mjs';

const IZ = izUret(200000, 20260731);
const kur = { 'en az kullanılan': (b) => new AzKullanilan(b), 'en az sık kullanılan': (b) => new AzSik(b),
  'rastgele': (b) => new Rastgele(b, 4242), 'süreye göre': (b) => new SureyeGore(b) };
const BUTCE = [200000, 400000, 800000];
const ornek = 'kitap:01234';
console.log('iz: 200000 erişim, 20000 kitap, dört dönem, tohum 20260731');
console.log('giriş gövdesi:', Buffer.byteLength(ornek) + Buffer.byteLength(deger(ornek)) + TEMEL, 'bayt');
console.log('politika              üstveri  giriş/bayt  400000 baytta giriş  üstveri payı');
for (const [ad, f] of Object.entries(kur)) {
  const o = f(400000);
  for (const a of IZ) o.eris(a);
  console.log(ad.padEnd(21), String(o.ust).padStart(7), String(o.maliyet(ornek)).padStart(11),
    String(o.g.size).padStart(20),
    ('%' + ((o.ustveriBayt / o.bayt) * 100).toFixed(1)).padStart(13));
}

console.log('\nisabet oranı (aynı iz, üç bütçe)');
console.log('politika              200000 bayt  400000 bayt  800000 bayt  düşen giriş');
for (const [ad, f] of Object.entries(kur)) {
  const satir = [], dusen = [];
  for (const b of BUTCE) {
    const o = f(b);
    for (const a of IZ) o.eris(a);
    satir.push(('%' + ((o.isabet / IZ.length) * 100).toFixed(1)).padStart(12));
    dusen.push(o.dusen);
  }
  console.log(ad.padEnd(21), satir.join(' '), String(dusen[1]).padStart(12));
}

console.log('\nsüreye göre: bütçe artınca ne değişti');
console.log('bütçe    isabet  tutulan giriş  süresi dolmuş  ölü bayt');
for (const b of BUTCE) {
  const o = new SureyeGore(b);
  for (const a of IZ) o.eris(a);
  const d = o.dolmus;
  console.log(String(b).padStart(6), String(o.isabet).padStart(9), String(o.g.size).padStart(14),
    String(d.sayi).padStart(14), String(d.bayt).padStart(9));
}

iz: 200000 erişim, 20000 kitap, dört dönem, tohum 20260731
giriş gövdesi: 73 bayt
politika              üstveri  giriş/bayt  400000 baytta giriş  üstveri payı
en az kullanılan           16          89                 4494         %18.0
en az sık kullanılan       24          97                 4123         %24.7
rastgele                    8          81                 4938          %9.9
süreye göre                16          89                 4494         %18.0

isabet oranı (aynı iz, üç bütçe)
politika              200000 bayt  400000 bayt  800000 bayt  düşen giriş
en az kullanılan             %83.0        %87.4        %90.0            0
en az sık kullanılan         %78.6        %87.1        %89.6            0
rastgele                     %78.5        %85.0        %89.9            0
süreye göre                  %65.5        %65.5        %65.5        43746

süreye göre: bütçe artınca ne değişti
bütçe    isabet  tutulan giriş  süresi dolmuş  ölü bayt
200000    130965           2247           1228    109292
400000    130965           4494           3475    309275
800000    130965           8988           7969    709241

Üstverinin Payı

İlk tablo, politika seçiminin bir bellek kararı olduğunu gösterir. Giriş gövdesi 73 bayttır; politikanın eklediği 8 ile 24 bayt arasındaki fark, aynı 400.000 baytlık bütçede tutulabilen giriş sayısını 4.123 ile 4.938 arasında oynatır. En az sık kullanılan politikanın sayaçları ve kova bağları bütçenin yüzde 24,7’sini, yani dörtte birini alır; rastgele politikada bu pay yüzde 9,9’dur. Aynı bütçeyle rastgele politika, en az sık kullanılandan yüzde 20 daha fazla kitap tutar.

Bu, politika karşılaştırmasını giriş sayısı üzerinden yapmanın neden yanıltıcı olduğunu gösterir: sabit giriş sayısıyla ölçülen bir karşılaştırma, ucuz üstverili politikayı kazandığı yerde cezalandırmadan bırakır.

İsabet Oranının Okunması

En az kullanılan politika üç bütçede de öndedir. Beklenen sonuç budur, çünkü izin ana kaynağı dönemin ders listesidir ve o listeye erişim yakın geçmişte yoğunlaşır.

En az sık kullanılan politika dar bütçede belirgin biçimde geride kalır: yüzde 78,6 karşısında yüzde 83,0. Nedeni izin yapısındadır. Dönem değiştiğinde eski ders listesinin girişleri yüksek sayaçlarla oturmayı sürdürür; yeni listenin kitapları ise sayaç bir ile girer ve bir sonraki tahliyede ilk sırada yer alır. Politika, geçmişte doğru olanı bugün de doğru sayar. Bütçe 800.000 bayta çıktığında iki politikanın farkı 0,4 puana iner, çünkü bütçe eski listeyi de yeni listeyi de aynı anda taşıyabilecek kadar geniştir.

Rastgele politikanın sonucu daha ilginçtir. 400.000 baytta en az kullanılanın 2,4 puan gerisindedir; 800.000 baytta fark 0,1 puana düşer. Rastgele seçim, atacağı girişi hiç düşünmeden seçer, ama iki avantajı vardır: üstverisi en ucuzdur, dolayısıyla aynı bütçede en çok girişi tutar, ve bütçe çalışma kümesini rahatça aldığında hangi girişin atıldığı sonucu değiştirmez. Dar bütçede politika 4,5 puan fark eder; geniş bütçede fark ölçüm gürültüsüne yaklaşır.

Karar bundan çıkar: politika tartışması yalnız bütçe çalışma kümesinden küçükken anlamlıdır. Bütçe rahatsa, tahliye politikasını değiştirmek için harcanan emek, aynı emeğin bellek üstverisini azaltmaya harcanmasından daha az getirir.

Süreye Göre Tahliye Belleği Korumaz

Son tablo, dört politikadan birinin aslında farklı bir işi yaptığını gösterir. Süreye göre politika üç bütçede de aynı isabet oranını verir: yüzde 65,5. Bu bir yuvarlama değildir — isabet sayısı üç koşumda da tam olarak 130.965’tir. Bütçe dört katına çıkarıldığında isabet hiç değişmemiştir.

Değişen tek şey ölü ağırlıktır. Bütçe 200.000 baytken depo 2.247 giriş tutar ve bunların 1.228’i süresi dolmuş girişlerdir; 800.000 baytta 8.988 girişin 7.969’u süresi dolmuştur ve 709.241 bayt kaplar. Yani bütçenin dörtte üçünden fazlası, hiçbir isabet üretmeyecek girişlere gider.

Bunun nedeni politikanın kendi mantığıdır. Süresi dolmuş bir giriş, bellekte dursa da erişildiğinde ıska sayılır ve düşer: dört yüz bin baytlık koşumda 43.746 giriş bu yolla düştü. Tahliye ise en eski girişi atar ve sabit ömürde en eski giriş zaten süresi dolmuş olandır. Sonuç olarak tahliye hiçbir zaman yaşayan bir girişi atmaz; fazladan bellek yalnız daha fazla ölü girişin bekletilmesine yarar.

Süre sonu bir tazelik aracıdır, bellek aracı değildir. Kütüphanenin katalog girişlerinin üç bin erişimde bir yenilenmesi bir doğruluk kararıdır ve yerindedir; ama bellek sınırını karşılamak için ayrıca bir tahliye politikası gerekir. İkisi birbirinin yerine geçmez.

Özet

• Bellek sınırı giriş sayısıyla değil baytla verilir, çünkü her politikanın girişe eklediği üstveri bütçenin içinden yenir: pay yüzde 9,9 ile yüzde 24,7 arasında değişti.
• Aynı 400.000 baytta rastgele politika 4.938, en az sık kullanılan 4.123 giriş tuttu; ucuz üstveri, zayıf kararı kısmen telafi eder.
• En az kullanılan politika üç bütçede de öndedir; en az sık kullanılan dar bütçede 4,4 puan geride kaldı, çünkü dönem değişince eski ders listesinin yüksek sayaçları yerini korudu.
• Bütçe genişledikçe politikalar arasındaki fark kapanır: 800.000 baytta en az kullanılan ile rastgele arasında 0,1 puan kaldı.
• Süreye göre tahliye üç bütçede de aynı 130.965 isabeti verdi; fazladan bellek yalnız ölü girişleri büyüttü (109.292 bayttan 709.241 bayta). Süre sonu tazeliği korur, belleği değil.

Sonraki Adım

Son ölçüm bir soruyu açıkta bıraktı: süresi dolmuş 7.969 giriş, kimse onlara dokunmadığı için bellekte durdu. Bir girişin süresi dolduğu anda silinmesini sağlayan bir mekanizma yoksa, tazelik penceresi yalnız okuma sonucunu düzeltir, tutulan baytı düzeltmez. Sonraki ders bu boşluğu ele alır: girişi yalnız erişildiğinde temizleyen tembel yöntem, ile arka planda örnekleyerek tarayan etkin yöntem. Ölçülecek olan, süresi dolmuş girişlerin bellekte ne kadar yer tuttuğu, tembel temizlemede bu yerin ne kadar geç boşaldığı ve etkin temizlemenin örnekleme turu başına neye mal olduğudur.