İşlemler ve İyimser Kilitleme

Önceki ders bir işlemin bütün anahtarlarının aynı düğümde toplanabildiğini gösterdi, ama toplandıktan sonra ne olacağını sormadı. Şube sınırını denetleyen bir ödünç işlemi şunu yapar: şubenin eşzamanlı ödünç sayacını okur, sınırı aşıp aşmadığına bakar, ancak öyle artırır. Okuma ile artırma arasında bir boşluk vardır ve o boşlukta başka bir görevli aynı sayacı değiştirmiş olabilir.

İyimser kilitleme kalıbı — sürüm karşılaştır, çakışırsa yeniden dene — İşlem Yönetimi kursunda kuruldu ve orada ölçüldü; burada tekrarlanmaz. Bu dersin konusu kalıbın bellek içi depodaki gerçekleşmesidir: depo tek iş parçacıklıdır, komutları sırayla işler ve bir işlem bloğu bölünmeden yürür. Bu iki özellik hem çakışmanın nasıl algılandığını hem de bedelinin kime ödetildiğini belirler.

İzleme, Düşünme, Gönderme

İstemci önce sayacı izlemeye alır, sonra okur. Okuduğu değerle sınırı karşılaştırması depo tarafında değil istemci tarafında olur; depo o sırada başka istemcilere hizmet eder. İstemci işlemi gönderdiğinde depo tek bir soruya bakar: izlenen anahtar, izleme kurulduğundan beri değişti mi. Değiştiyse işlem hiç yürümez ve istemci baştan başlar.

Çakışma penceresi tam olarak bu düşünme aralığıdır ve uzunluğu istemcinin elindedir. Deponun elinde olan şey ise başkadır: işlem bloğu yürürken hiçbir başka komut araya giremez. Bu, atomikliğin nereden geldiğini açıklar ve aynı zamanda bedelini de yazar — blok ne kadar uzunsa bütün istemciler o kadar bekler.

Düzenek

Düzenek bir modeldir: gerçek depo, ağ ya da istemci kurulmaz. Tik soyut bir adımdır ve depo her tikte tam olarak bir komut işler.

BK8 — düşünme aralığı 3 tik, işlem bloğu varsayılan olarak 4 komuttur. Gerekçe: okuma ile gönderme arasındaki hesap ile bloğun uzunluğu bağımsız iki ayardır ve ikisi ayrı ölçülür. BK9 — işlerin yüzde 55’i ödünç verme (+1), yüzde 45’i iadedir (−1) ve iş listesi şemadan bağımsız üretilir. Gerekçe: sayaç sınırın yakınında dolaşsın ve denetim gerçekten bağlasın; aynı iş listesi üç şemada da koşturulabilsin. BK10 — izlenen anahtar başına 48, sayaç başına 64, kilit anahtarı başına 64 bayt üstveri tutulur. Gerekçe: izleme kaydı anahtar bağını ve sürümü tutar; sayaç ile kilit birer giriştir.

// islem/model.mjs — TEK IS PARCACIKLI bellek ici deponun SUREC ICI MODELIDIR. Tik soyut bir
// adimdir: depo her tikte tam olarak bir komut isler, islem blogu ise bolunmeden blok tik tutar.
// Gercek depo, ag ya da istemci kurulmaz. Dusunme, istemcinin okuma ile gonderme arasindaki
// hesabidir; depo o sirada baskalarina hizmet eder ve cakisma penceresi tam olarak orasidir.
export const SAYAC_BAYT = 64, IZLEME_BAYT = 48, KILIT_BAYT = 64;

export function uretec(tohum) {  // dogrusal esleskli uretec; tohum gorunurdur
  let s = tohum >>> 0;
  return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; };
}

export function kosum({ sema, istemci, sube = 6, sinir = 20, isPay = 30, dusunme = 3,
                        blok = 4, tohum = 20260731 }) {
  const rnd = uretec(tohum);
  // Is listesi semadan bagimsiz uretilir: her is ya odunc verme (+1) ya iade (-1).
  const isler = [...Array(istemci)].map(() => [...Array(isPay)].map(() => rnd() < 0.55));
  const sayac = Array(sube).fill(10), surum = Array(sube).fill(0), kilit = Array(sube).fill(-1);
  const c = [...Array(istemci)].map((_, i) => ({ id: i, s: i % sube, i: 0, faz: 0, bekle: 0, gor: 0 }));
  let tik = 0, mesgul = 0, sira = 0, cakisma = 0, asim = 0, engel = 0, blokEngel = 0, tamam = 0;

  const uygula = (x) => {                                  // isin sayaca etkisi; sinir DENETLENIR
    const artir = isler[x.id][x.i];
    if (artir && sayac[x.s] < sinir) sayac[x.s] += 1;
    else if (!artir && sayac[x.s] > 0) sayac[x.s] -= 1;
    surum[x.s] += 1; x.i += 1; tamam += 1; x.faz = 0;
  };

  while (tamam < istemci * isPay && tik < 400000) {
    tik += 1;
    for (const x of c) if (x.bekle > 0) x.bekle -= 1;
    const hazir = c.filter((x) => (x.i < isPay || x.faz > 0) && x.bekle === 0);
    if (mesgul > 0) { mesgul -= 1; engel += hazir.length; blokEngel += hazir.length; continue; }
    if (hazir.length === 0) continue;
    const x = hazir[sira % hazir.length]; sira += 1;        // depo bir komuta hizmet eder
    engel += hazir.length - 1;
    if (sema === "atomik") {                                // tek atomik adim, kosul YOK
      const artir = isler[x.id][x.i];
      if (artir) { if (sayac[x.s] >= sinir) asim += 1; sayac[x.s] += 1; }
      else if (sayac[x.s] > 0) sayac[x.s] -= 1;
      surum[x.s] += 1; x.i += 1; tamam += 1;
    } else if (sema === "izleme") {
      if (x.faz === 0) { x.gor = surum[x.s]; x.faz = 1; }   // izle
      else if (x.faz === 1) { x.bekle = dusunme; x.faz = 2; }  // oku, sonra istemci hesaplar
      else if (surum[x.s] !== x.gor) { cakisma += 1; x.faz = 0; }  // izlenen anahtar degismis
      else { mesgul = blok - 1; uygula(x); }                // islem blogu BOLUNMEDEN yurur
    } else {                                                // kaba kilit: okuma-yazma arasi tutulur
      if (x.faz === 0) { if (kilit[x.s] === -1) { kilit[x.s] = x.id; x.faz = 1; } }
      else if (x.faz === 1) { x.bekle = dusunme; x.faz = 2; }
      else if (x.faz === 2) { uygula(x); x.faz = 3; }
      else { kilit[x.s] = -1; x.faz = 0; }
    }
  }
  const ustveri = sema === "izleme" ? istemci * IZLEME_BAYT : sema === "kilit" ? sube * KILIT_BAYT : 0;
  return { tik, cakisma, asim, engel, blokEngel, tamam, sayac,
           yeniden: cakisma / (istemci * isPay), bellek: sube * SAYAC_BAYT + ustveri, ustveri };
}

// islem/olc.mjs — ayni is: once eszamanlilik, sonra uc sema, sonra islem blogu boyu
import { kosum, SAYAC_BAYT, IZLEME_BAYT } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const yuz = (x, n = 7) => s((x * 100).toFixed(2) + "%", n);

console.log("6 sube, sube basina eszamanli odunc siniri 20. Her istemci 30 is yapar (%55 odunc,");
console.log("%45 iade; tohum 20260731). Dusunme 3 tik, islem blogu 4 komut. Izleme semasi:\n");
console.log("istemci |  is | cakisma | is basina yeniden deneme | toplam tik | engellenen istemci-tik");
console.log("--------|-----|---------|--------------------------|------------|-----------------------");
for (const n of [2, 4, 8, 16, 32]) {
  const r = kosum({ sema: "izleme", istemci: n });
  console.log(`${s(n, 7)} | ${s(n * 30, 3)} | ${s(r.cakisma, 7)} | ${s(r.yeniden.toFixed(3), 24)} | ` +
    `${s(r.tik, 10)} | ${s(r.engel, 22)}`);
}

console.log("\n16 istemci sabit; uc sema:");
console.log("sema    | toplam tik | cakisma | sinir asimi | engellenen | ustveri bayt | tutulan bayt");
console.log("--------|------------|---------|-------------|------------|--------------|-------------");
for (const sema of ["atomik", "izleme", "kilit"]) {
  const r = kosum({ sema, istemci: 16 });
  console.log(`${sema.padEnd(7)} | ${s(r.tik, 10)} | ${s(r.cakisma, 7)} | ${s(r.asim, 11)} | ` +
    `${s(r.engel, 10)} | ${s(r.ustveri, 12)} | ${s(r.bellek, 12)}`);
}

console.log("\n16 istemci, izleme semasi; islem blogu boyu degisiyor:");
console.log("blok | toplam tik | cakisma | blok yuzunden bekleyen | engellenen | bekleme payi");
console.log("-----|------------|---------|------------------------|------------|-------------");
for (const b of [1, 2, 4, 8, 16]) {
  const r = kosum({ sema: "izleme", istemci: 16, blok: b });
  console.log(`${s(b, 4)} | ${s(r.tik, 10)} | ${s(r.cakisma, 7)} | ${s(r.blokEngel, 22)} | ` +
    `${s(r.engel, 10)} | ${yuz(r.blokEngel / r.engel, 13)}`);
}

console.log("\nkosumdan bagimsiz nicelikler:");
console.log("  izleme ustverisi = istemci sayisi x " + IZLEME_BAYT + " bayt (izlenen anahtar basina)");
console.log("  istemci : " + [2, 4, 8, 16, 32].map((n) => s(n, 7)).join(""));
console.log("  bayt    : " + [2, 4, 8, 16, 32].map((n) => s(n * IZLEME_BAYT, 7)).join(""));
console.log("  sayac bellegi = 6 x " + SAYAC_BAYT + " = " + 6 * SAYAC_BAYT + " bayt (semadan bagimsiz)");
console.log("  bir islem blogu yururken bekleyen is <= (blok - 1) x hazir istemci sayisi");
console.log("  blok    : " + [1, 2, 4, 8, 16].map((n) => s(n, 7)).join(""));
console.log("  ust sinir (15 hazir istemci): " + [1, 2, 4, 8, 16].map((n) => s((n - 1) * 15, 7)).join(""));

6 sube, sube basina eszamanli odunc siniri 20. Her istemci 30 is yapar (%55 odunc,
%45 iade; tohum 20260731). Dusunme 3 tik, islem blogu 4 komut. Izleme semasi:

istemci |  is | cakisma | is basina yeniden deneme | toplam tik | engellenen istemci-tik
--------|-----|---------|--------------------------|------------|-----------------------
      2 |  60 |       0 |                    0.000 |        387 |                    470
      4 | 120 |       0 |                    0.000 |        717 |                   2244
      8 | 240 |      87 |                    0.362 |       1704 |                  10070
     16 | 480 |     475 |                    0.990 |       4314 |                  54181
     32 | 960 |    2201 |                    2.293 |      12372 |                 350407

16 istemci sabit; uc sema:
sema    | toplam tik | cakisma | sinir asimi | engellenen | ustveri bayt | tutulan bayt
--------|------------|---------|-------------|------------|--------------|-------------
atomik  |        480 |       0 |          86 |       7080 |            0 |          384
izleme  |       4314 |     475 |           0 |      54181 |          768 |         1152
kilit   |       4353 |       0 |           0 |      58883 |          384 |          768

16 istemci, izleme semasi; islem blogu boyu degisiyor:
blok | toplam tik | cakisma | blok yuzunden bekleyen | engellenen | bekleme payi
-----|------------|---------|------------------------|------------|-------------
   1 |       2965 |     506 |                      0 |      37476 |         0.00%
   2 |       3356 |     475 |                   6268 |      41303 |        15.18%
   4 |       4314 |     475 |                  19146 |      54181 |        35.34%
   8 |       6230 |     475 |                  44902 |      79937 |        56.17%
  16 |      10062 |     475 |                  96414 |     131449 |        73.35%

kosumdan bagimsiz nicelikler:
  izleme ustverisi = istemci sayisi x 48 bayt (izlenen anahtar basina)
  istemci :       2      4      8     16     32
  bayt    :      96    192    384    768   1536
  sayac bellegi = 6 x 64 = 384 bayt (semadan bagimsiz)
  bir islem blogu yururken bekleyen is <= (blok - 1) x hazir istemci sayisi
  blok    :       1      2      4      8     16
  ust sinir (15 hazir istemci):       0     15     45    105    225

Çakışma Doğrusal Değildir

İlk tablo eşzamanlılığı iki katına çıkarıyor ve çakışmayı sayıyor. İki ve dört istemcide tek bir çakışma yok: altı şubeye dağılan görevliler aynı sayaca aynı anda dokunmuyor. Sekiz istemcide 87 çakışma, on altıda 475, otuz ikide 2.201 çakışma ölçülüyor. İş sayısı iki katına çıkarken çakışma dört ile beş kat artıyor, çünkü çakışma istemci sayısıyla değil, aynı sayaca aynı pencerede dokunan istemci çiftleriyle orantılıdır.

İş başına yeniden deneme sütunu bunu doğrudan okunur kılıyor: 0,362’den 0,990’a, oradan 2,293’e. Otuz iki istemcide bir ödünç işlemi ortalama üç kez gönderiliyor ve ikisi boşa gidiyor. Toplam tik 1.704’ten 12.372’ye çıkıyor — iş dört katına çıkarken harcanan tik yedi katına.

Engellenen istemci-tik sütunu ise 10.070’ten 350.407’ye, otuz beş kat büyüyor. Bu sayı, hazır olduğu hâlde sırası gelmediği için bekleyen istemcilerin tik toplamıdır ve tek iş parçacıklı deponun asıl ölçüsüdür: iş yapılmıyorsa bile birileri bekliyordur.

Aynı İşin Üç Şeması

İkinci tablo on altı istemcide üç şemayı yan yana koyuyor. Koşulsuz atomik adım en hızlısıdır ve yanlıştır. 480 iş 480 tikte biter — komut başına bir tik, tek bir yeniden deneme yok. Sınır aşımı sütunu neyin satın alındığını yazıyor: 86 kez şube sınırının üstünde ödünç verilmiştir. Atomik artırma bir yarış koşulunu çözer ama bir koşulu yürütemez; sınırı okuyup karara bağlamak iki adım ister ve iki adım arasına başkası girer.

İzleme şeması doğrudur ve tikin dokuz katını harcar. 4.314 tik, 475 çakışma, sıfır sınır aşımı. Fark, doğruluğun fiyatıdır; ölçülen büyüklüğü de budur.

Kaba kilit aynı doğruluğu verir ve daha ucuz değildir. 4.353 tik ile izleme şemasının biraz üstünde, engellenen istemci-tik ise 58.883 ile açıkça üstünde kalıyor. Nedeni, kilidin istemcinin düşünme aralığı boyunca da tutulmasıdır: çakışma yok ama bekleyen var. İyimser denetimin buradaki üstünlüğü, çakışma olmadığında kimseyi bekletmemesidir.

Bellek sütunları kursun kuralını hatırlatıyor. İzleme üstverisi istemci sayısıyla büyür: on altı istemcide 768 bayt, otuz ikide 1.536 bayt. Korunan verinin kendisi ise altı sayaçtan ibarettir, 384 bayt. Sekiz istemciden sonra çakışma denetiminin defteri, koruduğu veriden büyüktür. Kilidin üstverisi ise şube başınadır ve istemci sayısından bağımsızdır: 384 bayt. İki yaklaşım arasındaki bellek farkı, üstverinin neye bağlandığından çıkar.

İşlem Bloğunun Uzunluğu

Üçüncü tablo tek iş parçacıklı deponun kendine özgü bedelini yalıtıyor. Blok 1’de bloktan doğan bekleme sıfırdır. Blok 16’da 96.414 istemci-tik yalnız blok yürürken birikir ve toplam beklemenin yüzde 73,35’ini oluşturur. Çakışma sayısı bu satırlarda neredeyse sabittir (475) — blok uzunluğu çakışmayı değiştirmez, çünkü çakışma penceresi düşünme aralığındadır.

Değişen şey, işlem yürürken başka hiç kimsenin hizmet alamamasıdır. Toplam tik 2.965’ten 10.062’ye çıkar. Koşumdan bağımsız üst sınır son satırdadır: on altılık blokta 15 hazır istemci için 225 istemci-tik, tek bir işlem başına. Bir işlem bloğuna komut eklemek, o komutu bütün istemcilerin faturasına yazar.

Özet

• Çakışma eşzamanlılıkla doğrusal büyümez: iki ve dört istemcide hiç çakışma olmadı, 8, 16 ve 32 istemcide 87, 475 ve 2.201 çakışma ölçüldü; iş başına yeniden deneme 0,362’den 2,293’e çıktı.
• Koşulsuz atomik adım 480 işi 480 tikte bitirdi ve hiç çakışmadı, ama şube sınırını 86 kez aştı: atomik artırma yarışı çözer, koşulu yürütmez.
• İzleme şeması sıfır sınır aşımıyla 4.314 tik harcadı; doğruluğun fiyatı bu dokuz kattır.
• Kaba kilit aynı doğruluğu 4.353 tikte verdi ama 58.883 istemci-tik engelledi (izlemede 54.181), çünkü kilit istemcinin düşünme aralığı boyunca da tutulur.
• İzleme üstverisi istemci başınadır (16 istemcide 768 bayt) ve altı sayacın 384 baytını aşar; kilit üstverisi şube başınadır ve istemci sayısıyla büyümez.
• İşlem bloğu 1’den 16’ya çıktığında toplam tik 2.965’ten 10.062’ye, bloktan doğan bekleme 0’dan 96.414 istemci-tike çıktı ve toplam beklemenin yüzde 73,35’i oldu; çakışma sayısı değişmedi.

Sonraki Adım

Bu ders bir yazmanın hangi koşullarda kabul edileceğini ölçtü, ama yazmanın kabul edildiğinden kimin haberi olacağını hiç sormadı. Ödünç sayacı sınıra dayandığında bekleme listesindeki okurun bilgilendirilmesi, bir kitap iade edildiğinde raf ekranının tazelenmesi, şube panosunun son etkinliği göstermesi — bunların hepsi aynı soruyu sorar: değişiklik, onu bekleyen taraflara nasıl ulaşır. Bu iş için anahtar okumak gerekmez; deponun kendisi bir iletiyi abonelerine dağıtabilir. Sonraki ders bu dağıtımın ne olduğunu ve daha önemlisi ne olmadığını ölçer: teslim güvencesi yoktur, abonesi olmayan ileti kaybolur ve yavaş bir abone deponun belleğinde bir tampon büyütür.