Sıralı Konvoy

Önceki ders sırayı bir tercih olarak ele aldı: öncelikli kuyruk, işleri hangi sırayla alacağımızı seçmenin bir yoluydu ve hızlı olanı yavaş olanın önüne geçiriyordu. Bir işin beklemesi orada bir hizmet düzeyi kararıydı, bir doğruluk sorunu değil. Bazı işlerde ise sıra seçilebilir bir şey değildir. Aynı gönderinin durum olayları — kabul, aktarma, dağıtıma çıkış, teslim — birbirinin üstüne yazar; ters sırayla işlenirse gönderi teslim edildikten sonra yeniden aktarmada görünür.

Sıralı konvoy (sequential convoy), sıra kısıtı taşıyan işleri bir anahtara göre tek şeride sokan, şeritler arasında ise koşutluğu koruyan yerleşimdir. Kuyruk mekaniği, teslim garantileri ve sıra ihlalinin ters çiftle sayılması Önbellekleme, Kuyruklar ve Eşzamansız İşleme kursunda kurulmuştu; burada teslim garantisi hiç tartışılmaz. Bu dersin sorusu bir kapasite sorusudur: sırayı korumak koşutluktan ne kadarını geri veriyor ve bu kısıttan kaçmanın bir yolu var mı.

Sıra Kısıtı Taşıyan Olay

Bir gönderinin bütün olayları sıra istemez. “Bölgeye vardı” bilgisi bir durum geçişidir; “tarayıcıdan geçti” kaydı ise durumun üstüne yazmaz, yalnız geçmişe eklenir. Ayrımın ölçütü tek cümleyle söylenebilir: olay bir alanın önceki değerini siliyorsa sıra kısıtı taşır.

Model bu ayrımı bir durum makinesiyle kurar. Dört adım sıralıdır ve her olay bir adım numarası taşır. Üç düzen aynı olay kümesinde koşturulur: olayları hiçbir kısıt olmadan dağıtan serbest düzen, anahtar başına şerit açan konvoy düzeni ve olayları serbest bırakıp işleyicide adım numarasına bakan sürüm damgası düzeni. Dördüncü sütun konvoyun anahtarını gönderiden hatta kaydırır.

// konvoy/olay.mjs — belirlenimli durum olayi kumesi ve uc duzenin surec ici modeli.
// Tur soyut bir adimdir; sure model parametresidir, olculmus bir sure degildir.
export const ADIM = { kabul: 1, aktarma: 2, dagitim: 3, teslim: 4 };
export const OLAY = [            // [takip no, hat, durum, sure]
  ["TR-4821", "H1", "kabul", 1], ["TR-9007", "H1", "kabul", 3],
  ["TR-4821", "H1", "aktarma", 4], ["TR-5533", "H2", "kabul", 1],
  ["TR-4821", "H1", "dagitim", 1], ["TR-9007", "H1", "aktarma", 1],
  ["TR-2214", "H2", "kabul", 2], ["TR-4821", "H1", "teslim", 1],
  ["TR-5533", "H2", "aktarma", 3], ["TR-9007", "H1", "dagitim", 1],
  ["TR-7788", "H3", "kabul", 1], ["TR-5533", "H2", "dagitim", 1],
  ["TR-2214", "H2", "aktarma", 4], ["TR-9007", "H1", "teslim", 1],
  ["TR-5533", "H2", "teslim", 1], ["TR-7788", "H3", "aktarma", 2],
  ["TR-2214", "H2", "dagitim", 1], ["TR-7788", "H3", "dagitim", 1],
  ["TR-2214", "H2", "teslim", 1], ["TR-7788", "H3", "teslim", 1],
];

// Olaylar tuketicilere dagitilir; bir tuketici bosaldiginda siradaki isi alir.
// serit: konvoy anahtarina gore serit adi, null ise sira kisiti yoktur.
function kosum(isler, tuketici, serit) {
  const bos = new Array(tuketici).fill(0);   // her tuketicinin bosalacagi tur
  const seritBos = new Map();                // her seridin bosalacagi tur
  return isler.map((o) => {
    const t = bos.indexOf(Math.min(...bos));
    const s = serit ? serit(o) : null;
    const basla = Math.max(bos[t], s === null ? 0 : (seritBos.get(s) ?? 0));
    const bitis = basla + o.sure;
    bos[t] = bitis;
    if (s !== null) seritBos.set(s, bitis);
    return { ...o, tuketici: t, bitis, serit: s };
  });
}

// Bitis sirasina gore uygulanan olaylar: son yazan kazanir ya da surum damgasi.
function uygula(bitmis, damga) {
  const durum = new Map(), s = { geriyeYazma: 0, atlanan: 0 };
  for (const o of [...bitmis].sort((a, b) => a.bitis - b.bitis || a.sira - b.sira)) {
    const simdi = durum.get(o.takipNo) ?? 0;
    if (ADIM[o.durum] < simdi) {
      s.geriyeYazma += 1;
      if (damga) { s.atlanan += 1; continue; }   // damga geriye yazmayi reddeder
    }
    durum.set(o.takipNo, ADIM[o.durum]);
  }
  const yanlis = [...durum.entries()].filter(([, a]) => a !== ADIM.teslim).map(([n]) => n);
  return { ...s, yanlisSonDurum: yanlis.length, yanlis, tur: Math.max(...bitmis.map((o) => o.bitis)) };
}

export function duzen(ad, tuketici) {
  const isler = OLAY.map(([takipNo, hat, durum, sure], sira) => ({ takipNo, hat, durum, sure, sira }));
  const SERIT = { serbest: null, konvoy: (o) => o.takipNo, "konvoy-hat": (o) => o.hat,
    "surum-damgasi": null };
  const bitmis = kosum(isler, tuketici, SERIT[ad]);
  const r = uygula(bitmis, ad === "surum-damgasi");
  const yuk = new Map();
  for (const o of bitmis) if (o.serit !== null) yuk.set(o.serit, (yuk.get(o.serit) ?? 0) + o.sure);
  return { ...r, serit: yuk.size, enYuklu: yuk.size ? Math.max(...yuk.values()) : 0,
    isYuku: OLAY.reduce((t, o) => t + o[3], 0) };
}

// konvoy/olc.mjs — dort duzen ayni olay kumesinde: sira bozulmasi, tur ve serit yuku
import { duzen, OLAY } from "./olay.mjs";

const TUKETICI = 4;
const ALAN = [["geriyeYazma", "geriye yazma"], ["yanlisSonDurum", "yanlis son durum"],
  ["atlanan", "atlanan olay"], ["tur", "tur"], ["serit", "serit"], ["enYuklu", "en yuklu serit"]];
const D = ["serbest", "konvoy", "konvoy-hat", "surum-damgasi"].map((a) => [a, duzen(a, TUKETICI)]);

console.log(`${OLAY.length} durum olayi, ${new Set(OLAY.map((o) => o[0])).size} gonderi, ` +
  `${TUKETICI} tuketici, toplam is yuku ${D[0][1].isYuku} tur`);
console.log();
console.log(`${"olcu".padEnd(18)}${D.map(([a]) => a.padStart(15)).join("")}`);
for (const [k, ad] of ALAN)
  console.log(`${ad.padEnd(18)}${D.map(([, r]) => String(r[k]).padStart(15)).join("")}`);

const [serbest, konvoy, hat, damga] = D.map(([, r]) => r);
console.log(`\nserbest duzende yanlis son duruma dusen gonderiler = ${serbest.yanlis.join(", ")}`);
console.log(`konvoy / serbest tur orani = ${(konvoy.tur / serbest.tur).toFixed(3)}, ` +
  `hat konvoyu / serbest = ${(hat.tur / serbest.tur).toFixed(3)}`);
console.log(`etkin kosutluk = is yuku / tur: serbest ${(serbest.isYuku / serbest.tur).toFixed(2)}, ` +
  `konvoy ${(konvoy.isYuku / konvoy.tur).toFixed(2)}, hat konvoyu ${(hat.isYuku / hat.tur).toFixed(2)}`);
console.log(`damga duzeninde durum gecmisinde eksik kalan adim = ${damga.atlanan}`);

console.log(`\n${"tuketici".padEnd(10)}${["serbest", "konvoy", "konvoy-hat"].map((a) => a.padStart(12)).join("")}`);
for (const t of [1, 2, 4, 8]) {
  const satir = ["serbest", "konvoy", "konvoy-hat"].map((a) => String(duzen(a, t).tur).padStart(12));
  console.log(`${String(t).padEnd(10)}${satir.join("")}`);
}

20 durum olayi, 5 gonderi, 4 tuketici, toplam is yuku 32 tur

olcu                      serbest         konvoy     konvoy-hat  surum-damgasi
geriye yazma                    5              0              0              5
yanlis son durum                1              0              0              0
atlanan olay                    0              0              0              5
tur                             8             13             19              8
serit                           0              5              3              0
en yuklu serit                  0              8             14              0

serbest duzende yanlis son duruma dusen gonderiler = TR-4821
konvoy / serbest tur orani = 1.625, hat konvoyu / serbest = 2.375
etkin kosutluk = is yuku / tur: serbest 4.00, konvoy 2.46, hat konvoyu 1.68
damga duzeninde durum gecmisinde eksik kalan adim = 5

tuketici       serbest      konvoy  konvoy-hat
1                   32          32          32
2                   16          17          23
4                    8          13          19
8                    5           9          14

Sayıların Okunması

İlk iki satır birbirine karıştırılmaması gereken iki sayıyı ayırıyor. Serbest düzende 20 olayın 5’i kendinden ileri bir adımın üstüne yazdı, ama yalnız bir gönderi yanlış son duruma düştü. Aradaki fark, geriye yazmaların çoğunun kendiliğinden kapanmasıdır: sonra gelen doğru bir olay yanlış değeri siler. Bozuk kalan yalnız en son uygulanan geriye yazmadır. Ölçüm bunu adıyla söylüyor: bozulan gönderi TR-4821. Sıra bozulmasını yalnız ihlal sayısıyla raporlayan bir düzenek, hasarı beş kat büyük gösterir; yalnız son durumu denetleyen bir düzenek ise sorunun beş kez yaşandığını görmez.

Konvoy sütunu iki sayıyı da sıfıra indiriyor ve bedeli tek bir yerde topluyor: tur sayısı 8’den 13’e, etkin koşutluk 4,00’ten 2,46’ya iniyor. Oran 1,625 — sıra kısıtı, koşutluğun yaklaşık beşte ikisini geri alıyor. Bu, kalıbın ödediği doğrudan bedeldir ve kaçınılmaz değil, anahtara bağlıdır.

Dördüncü sütun kısıttan kaçmanın yolunu gösteriyor. Sürüm damgalı işleyici olayları serbest bırakır ve tur sayısı 8’de, koşutluk 4,00’te kalır; geriye yazmalar yine 5’tir ama işleyici onları reddettiği için yanlış son durum 0’dır. Bedel yeni bir satırda görünüyor: 5 atlanan olay. Bu gönderilerin durum geçmişinde beş adım eksik kalır — son durum doğrudur, yol eksiktir. İki düzen aynı doğruluğu ayrı bir para birimiyle satın alıyor: konvoy verimle, sürüm damgası geçmişle.

Şeridin İnceliği Tavanı Belirler

Üçüncü ve dördüncü sütunun farkı yalnız anahtardır. Konvoy anahtarı takip numarası olduğunda 5 şerit açılıyor ve en yüklü şerit 8 tur iş taşıyor; anahtar hat olduğunda şerit 3’e iniyor ve en yüklü şerit 14 tur taşıyor. Tur sayısı 13’ten 19’a, koşutluk 2,46’dan 1,68’e düşüyor. Kaba anahtar, ilgisiz gönderileri aynı şeride sokar: TR-2214 numaralı gönderinin dağıtım olayı, TR-5533 numaralı gönderinin dört turluk aktarma olayının arkasında bekler. Aralarında hiçbir sıra ilişkisi yoktur.

Alttaki tablo bunun neden bir kapasite sorusu olduğunu gösteriyor. Tüketici sayısı 1’den 8’e çıktığında serbest düzen 32 turdan 5 tura iniyor. Konvoy 9 turda, hat konvoyu 14 turda duruyor — ikisi de en yüklü şeridin yükünde. Şerit yükü verimin tavanıdır ve tüketici eklemek o tavanı aşmaz. Sıralı konvoy tasarlanırken sorulacak asıl soru tüketici sayısı değil, en yüklü şeridin ne taşıdığıdır.

Hesaba Dönüş

Modelin 20 olayı bir hacim sayısı değildir. Ölçülen şey orandır ve oran K01’in tepe yazma hızına uygulanır: saniyede 97,22 durum olayı, Kabaca Büyüklük Hesabı dersinden gelen bir hesaptır. Bu derse özgü tek varsayım şudur.

KK1 — sıra kısıtı taşıyan durum olayı oranı 4/7. Gerekçesi K01’in V4 satırında yazılıdır: gönderi başına yedi olay “kabul, aktarma, dağıtıma çıkış, teslim ve ara durumlar” diye gerekçelendirilmişti; dördü adlandırılmış durum geçişidir, üçü ara kayıttır. Bu sayı K01’in varsayım tablosuna eklenmez; duyarlılığı aşağıda 5/7 ile birlikte hesaplanır.

// konvoy/hesap.mjs — modelin kosutluk maliyetini K01'in tepe yazma hizina uygular
import { duzen } from "./olay.mjs";

const TEPE_YAZMA = 97.22;          // K01 Kabaca Buyukluk Hesabi, hesap sinifi
const T = 4;
const kosutluk = (a) => duzen(a, T).isYuku / duzen(a, T).tur;
const maliyet = { konvoy: kosutluk("serbest") / kosutluk("konvoy"),
  "konvoy-hat": kosutluk("serbest") / kosutluk("konvoy-hat") };

console.log(`${"KK1".padStart(5)}${"kisitli olay/s".padStart(16)}${"kisitsiz olay/s".padStart(17)}` +
  `${"konvoy x".padStart(11)}${"hat konvoyu x".padStart(15)}`);
for (const KK1 of [4 / 7, 5 / 7]) {          // KK1: sira kisiti tasiyan durum olayi orani
  const kisitli = TEPE_YAZMA * KK1, kisitsiz = TEPE_YAZMA - kisitli;
  const secici = (ad) => KK1 * maliyet[ad] + (1 - KK1);
  console.log(`${KK1.toFixed(3).padStart(5)}${kisitli.toFixed(2).padStart(16)}` +
    `${kisitsiz.toFixed(2).padStart(17)}${secici("konvoy").toFixed(3).padStart(11)}` +
    `${secici("konvoy-hat").toFixed(3).padStart(15)}`);
}
console.log(`\ntum akis konvoya sokulursa: konvoy x${maliyet.konvoy.toFixed(3)}, ` +
  `hat konvoyu x${maliyet["konvoy-hat"].toFixed(3)}`);
console.log(`serit yuku tavani (8 tuketici): konvoy ${duzen("konvoy", 8).tur} tur, ` +
  `hat konvoyu ${duzen("konvoy-hat", 8).tur} tur, serbest ${duzen("serbest", 8).tur} tur`);

  KK1  kisitli olay/s  kisitsiz olay/s   konvoy x  hat konvoyu x
0.571           55.55            41.67      1.357          1.786
0.714           69.44            27.78      1.446          1.982

tum akis konvoya sokulursa: konvoy x1.625, hat konvoyu x2.375
serit yuku tavani (8 tuketici): konvoy 9 tur, hat konvoyu 14 tur, serbest 5 tur

Tepe yazma hızının 55,55 olay/s’lik bölümü sıra kısıtı taşıyor, 41,67 olay/s’lik bölümü taşımıyor. Bütün yazma akışı konvoya sokulursa aynı tamamlanma hızı için gereken tüketici sayısı 1,625 katına çıkar. Kısıtı yalnız taşıyan olaylara uygulamak — seçici konvoy — çarpanı 1,357’ye indirir; hat anahtarında 2,375 yerine 1,786 olur. KK1 5/7’ye çıkarsa çarpanlar 1,446 ve 1,982’ye yükselir: seçici konvoyun kazancı, sıra kısıtı taşımayan olayların oranı kadardır ve o oran daralırsa kazanç da daralır.

Karar üç seçenek arasındadır ve üçü de aynı olay kümesinde ölçüldü. Sürüm damgalı işleyici verimden hiçbir şey vermez ama durum geçmişinde boşluk bırakır; taşıyıcı geçmişi sözleşme uyuşmazlığında kullanıldığı için bu boşluk ücretsiz değildir. Gönderi anahtarlı seçici konvoy geçmişi eksiksiz tutar ve 1,357 çarpan öder. Hat anahtarlı konvoy hiçbir ek doğruluk vermez, yalnız şerit sayısını azaltır ve çarpanı 1,786’ya çıkarır — kaba anahtar, karşılığı olmayan bir maliyettir.

Özet

• Sıra bir tercih değil kısıttır: olay bir alanın önceki değerini siliyorsa o olayın sırası korunmak zorundadır; gönderi başına yedi olayın dördü bu sınıftadır.
• Geriye yazma ile yanlış son durum ayrı sayılardır: serbest düzende 5 geriye yazma oluştu ama yalnız 1 gönderi yanlış son duruma düştü, çünkü sonraki doğru olaylar çoğunu kapattı.
• Sıralı konvoy iki sayıyı da sıfırlar ve bedeli verimden alır: tur 8’den 13’e, etkin koşutluk 4,00’ten 2,46’ya iner (oran 1,625).
• Sürüm damgalı işleyici koşutluğu 4,00’te tutar ve yanlış son durumu sıfırlar, ama 5 olayı atlar; durum geçmişinde beş adım eksik kalır.
• Şerit yükü verimin tavanıdır: sekiz tüketiciyle serbest düzen 5 tura inerken konvoy 9, hat konvoyu 14 turda durur — ikisi de en yüklü şeridin yükünde.
• K01’e dönüş: tepe yazmanın 55,55 olay/s’i kısıtlıdır; seçici konvoy tüketici gereksinimini 1,357 katına çıkarır, tüm akış konvoya sokulursa 1,625, kaba anahtarla 1,786 olur.

Sonraki Adım

Bu dersin bütün olayları tek adımlıydı: bir durum yazılır ve iş biter. Gün sonu ücretlendirmesi böyle değildir. Bir satıcının bir günü için tarife hesaplanır, indirim uygulanır, fatura satırı üretilir ve bildirim gönderilir; dört adım birbirini bekler ve her adım ayrı bir servistedir. Böyle bir işin sırası burada olduğu gibi bir anahtarla korunamaz, çünkü sorun aynı anahtara iki yazma değil, tek bir işin dört ayrı yerde yürümesidir. Sonraki ders bu işi iki ayrı biçimde kurar — adımların birbirini olaylarla tetiklediği düzen ile tek bir yürütücünün adımları sırayla çağırdığı düzen — ve ikisini adım sayısı, ileti sayısı, telafi edilen adım ve yarım kalan iş cinsinden ölçer.