Öncelikli Kuyruk

Buraya kadarki bütün kuyruklarda tek bir iş türü vardı ve tüketiciler sıradaki işi ayırt etmeden aldı. Aynı sistemde kuyruğa giren işler birbirinin eşi değildir: taşıyıcının durum olayı alıcının takip sayfasında görünür ve gecikmesi doğrudan hissedilir; gün sonu ücretlendirme kaydının sabaha kadar zamanı vardır; satıcının rapor işi ikisinden de bekleyebilir. Önceki dersin 525.000 işlik birikmesi tek bir sıra olarak ele alındığında üçü de aynı üç saati bekler.

Bu ders sıranın kendisini bir karara çevirir. Öncelikli kuyruk (priority queue) burada bir hizmet düzeyi kararıdır: hangi işin hangisinin önüne geçeceğini iş sınıfına bakarak seçmek. Veri Yapıları müfredatında aynı İngilizce terimin karşılığı olan öncelik kuyruğu bir veri yapısıdır — anahtarına göre en küçüğü veren yığın tabanlı bir yapı; ikisi ayrı şeylerdir ve bu derste veri yapısı anlatılmaz, kararın kapasite karşılığı ölçülür.

Üç Sınıf ve Bir Kapasite

Ölçüm penceresi K01’in V10 varsayımıdır: dört saat. Pencereye üç sınıf girer ve üçünün de hızı K01’den gelir.

A — durum olayı. 97,22 iş/s (K01 tepe yazma hızı, V8 çarpanıyla). Hizmet düzeyi: alıcının takip sayfasında görünür, beklemesi kısa olmalı.

B — ücretlendirme kaydı. 833,33 iş/s (K01 toplu iş tarama hızı). Hizmet düzeyi: tek tek beklemesi önemsizdir, pencerenin sonunda bitmesi gerekir.

C — rapor işi. Yüz rapor, her biri 3000 kayıt — önceki derste K01’den türetilen boy. Hizmet düzeyi: gün içinde bitsin.

İş birimi bir kaydın işlenmesidir, dolayısıyla üç sınıf aynı birimle sayılır. Üçünün toplam gereksinimi 951,39 iş/s’dir. Kapasite bir varsayımdır:

K6 — ortak tüketici grubunun kapasitesi: 900 iş/s. Bu kursun kendi varsayımıdır ve K01’in tablosuna eklenmez. Gerekçe: grup gün sonu işinin gereksinimine (833,33 kayıt/s) küçük bir payla boyutlandırılmış, olay akışı ile rapor işleri sonradan aynı gruba verilmiştir. Duyarlılığı çıktının sonunda ölçülüyor.

Üç sınıfın tam çakışması en kötü durumdur; pencereleri ayırmak bu dersin ele aldığı sorunu ortadan kaldıran bir tasarım kararıdır ve ölçüm o kararın değerini de gösterir.

Karşılaştırılan üç politika şudur: tek sıra, işleri geliş sırasına göre alır; katı öncelik, kapasiteyi önce A’ya, kalanı B’ye, kalanı C’ye verir; pay ayırma, her sınıfa kapasitenin bir oranını ayırır (A 0,15, B 0,75, C 0,10) ve kullanılmayan payı sırayla ötekilere dağıtır. Dördüncü ve beşinci koşumlarda A’ya önceki dersin sıçraması eklenir: yirmi dakika boyunca dört kat.

// oncelik/sinif.mjs — uc is sinifinin ayni tuketici grubunu paylasmasi: tek sira, kati oncelik
// ve pay ayirma. MODEL: tur bir saniyedir, is birimi bir kayit islemedir.
// Sonuclar belirlenimlidir (hesap sinifi) ve makineden bagimsizdir.
const PENCERE = 4 * 3600;          // K01 varsayim V10: gun sonu isinin penceresi
const A_HIZ = (2_800_000 / 86_400) * 3;   // K01 + V8: tepe yazma olay/s
const B_HIZ = 833.3333;            // K01: toplu is tarama kayit/s
const C_ADET = 100, C_IS = 3000;   // rapor isleri: her biri 3000 kayit (02. ders)
const K6 = 900;                    // bu kursun varsayimi K6: grup kapasitesi (is/s)

class Sira {
  constructor() { this.b = []; this.bas = 0; this.uzunluk = 0; this.gelen = 0; }
  ekle(t, n) { if (n > 0) { this.b.push({ t, n }); this.uzunluk += n; this.gelen += n; } }
  bekleyenBas() { return this.bas < this.b.length ? this.b[this.bas].t : Infinity; }
  al(t, s) {
    let kalan = s;
    while (kalan > 1e-9 && this.bas < this.b.length) {
      const g = this.b[this.bas];
      const k = Math.min(kalan, g.n);
      g.n -= k; kalan -= k; this.uzunluk -= k;
      this.toplamBekleme = (this.toplamBekleme ?? 0) + k * (t - g.t);
      this.bitenIs = (this.bitenIs ?? 0) + k;
      if (t - g.t > (this.enUzun ?? 0)) this.enUzun = t - g.t;
      if (g.n <= 1e-9) this.bas += 1;
    }
    return s - kalan;
  }
}

function kosum(politika, kapasite, aCarpan) {
  const s = [new Sira(), new Sira(), new Sira()];
  const PAY = [0.15, 0.75, 0.10];
  for (let t = 0; t < PENCERE; t += 1) {
    const patlama = aCarpan > 1 && t >= 3600 && t < 3600 + 1200;
    s[0].ekle(t, A_HIZ * (patlama ? aCarpan : 1));
    s[1].ekle(t, B_HIZ);
    if (t % Math.floor(PENCERE / C_ADET) === 0) s[2].ekle(t, C_IS);
    let kalan = kapasite;
    if (politika === "tek-sira") {
      while (kalan > 1e-9) {
        const i = [0, 1, 2].reduce((a, b) => (s[b].bekleyenBas() < s[a].bekleyenBas() ? b : a), 0);
        if (s[i].bekleyenBas() === Infinity) break;
        kalan -= s[i].al(t, Math.min(kalan, s[i].b[s[i].bas].n));
      }
    } else if (politika === "kati-oncelik") {
      for (const i of [0, 1, 2]) kalan -= s[i].al(t, kalan);
    } else {
      for (const i of [0, 1, 2]) kalan -= s[i].al(t, Math.min(kalan, kapasite * PAY[i]));
      for (const i of [0, 1, 2]) kalan -= s[i].al(t, kalan);
    }
  }
  return s;
}

const AD = ["A durum olayi", "B ucretlendirme", "C rapor"];
console.log(`pencere ${PENCERE} s (V10), kapasite K6 = ${K6} is/s`);
console.log(`gereken hiz = ${((A_HIZ * PENCERE + B_HIZ * PENCERE + C_ADET * C_IS) / PENCERE).toFixed(2)} is/s\n`);
for (const [ad, pol, kap, carpan] of [["tek sira", "tek-sira", K6, 1], ["kati oncelik", "kati-oncelik", K6, 1],
  ["pay ayirma", "pay", K6, 1], ["kati oncelik + A patlamasi", "kati-oncelik", K6, 4],
  ["pay ayirma + A patlamasi", "pay", K6, 4]]) {
  console.log(`${ad} (kapasite ${kap})`);
  console.log("  sinif             gelen     biten   biten/gelen  ort. bekleme(dk)  en uzun(dk)  kalan birikme");
  const siralar = kosum(pol, kap, carpan);
  for (const [i, q] of siralar.entries()) {
    const biten = q.bitenIs ?? 0;
    console.log(`  ${AD[i].padEnd(16)} ${q.gelen.toFixed(0).padStart(8)} ${biten.toFixed(0).padStart(9)} ` +
      `${(biten / q.gelen).toFixed(3).padStart(13)} ${((q.toplamBekleme ?? 0) / Math.max(biten, 1) / 60).toFixed(1).padStart(17)} ` +
      `${((q.enUzun ?? 0) / 60).toFixed(1).padStart(12)} ${Math.max(0, q.uzunluk).toFixed(0).padStart(14)}`);
  }
  const toplam = siralar.reduce((a, q) => a + Math.max(0, q.uzunluk), 0);
  console.log(`  toplam kalan birikme: ${toplam.toFixed(0)}\n`);
}

const gereken = (A_HIZ * PENCERE + B_HIZ * PENCERE + C_ADET * C_IS) / PENCERE;
console.log(`acik = (${gereken.toFixed(2)} - ${K6}) x ${PENCERE} = ` +
  `${((gereken - K6) * PENCERE).toFixed(0)} is; her politikada ayni`);
console.log(`acigi kapatmak: kapasite ${K6} -> ${gereken.toFixed(2)} is/s (x${(gereken / K6).toFixed(3)}) ` +
  `ya da pencere 4.00 -> ${(4 * gereken / K6).toFixed(2)} saat (V10)`);
console.log("K6 duyarliligi (pay ayirma, toplam kalan birikme):");
for (const kap of [850, 900, 950]) {
  const toplam = kosum("pay", kap, 1).reduce((a, q) => a + Math.max(0, q.uzunluk), 0);
  console.log(`  kapasite ${kap} -> ${toplam.toFixed(0)}`);
}

pencere 14400 s (V10), kapasite K6 = 900 is/s
gereken hiz = 951.39 is/s

tek sira (kapasite 900)
  sinif             gelen     biten   biten/gelen  ort. bekleme(dk)  en uzun(dk)  kalan birikme
  A durum olayi     1400000   1324264         0.946               6.5         13.0          75736
  B ucretlendirme  12000000  11350736         0.946               6.5         13.0         649263
  C rapor            300000    285000         0.950               6.5         12.9          15000
  toplam kalan birikme: 740000

kati oncelik (kapasite 900)
  sinif             gelen     biten   biten/gelen  ort. bekleme(dk)  en uzun(dk)  kalan birikme
  A durum olayi     1400000   1400000         1.000               0.0          0.0              0
  B ucretlendirme  12000000  11560000         0.963               4.4          8.8         440000
  C rapor            300000         0         0.000               0.0          0.0         300000
  toplam kalan birikme: 740000

pay ayirma (kapasite 900)
  sinif             gelen     biten   biten/gelen  ort. bekleme(dk)  en uzun(dk)  kalan birikme
  A durum olayi     1400000   1400000         1.000               0.0          0.0              0
  B ucretlendirme  12000000  11260000         0.938               7.4         14.8         740000
  C rapor            300000    300000         1.000               0.3          0.6              0
  toplam kalan birikme: 740000

kati oncelik + A patlamasi (kapasite 900)
  sinif             gelen     biten   biten/gelen  ort. bekleme(dk)  en uzun(dk)  kalan birikme
  A durum olayi     1750000   1750000         1.000               0.0          0.0              0
  B ucretlendirme  12000000  11210000         0.934               9.5         15.8         790000
  C rapor            300000         0         0.000               0.0          0.0         300000
  toplam kalan birikme: 1090000

pay ayirma + A patlamasi (kapasite 900)
  sinif             gelen     biten   biten/gelen  ort. bekleme(dk)  en uzun(dk)  kalan birikme
  A durum olayi     1750000   1750000         1.000               3.5         18.1              0
  B ucretlendirme  12000000  10910000         0.909              12.0         21.8        1090000
  C rapor            300000    300000         1.000               0.3          0.6              0
  toplam kalan birikme: 1090000

acik = (951.39 - 900) x 14400 = 740000 is; her politikada ayni
acigi kapatmak: kapasite 900 -> 951.39 is/s (x1.057) ya da pencere 4.00 -> 4.23 saat (V10)
K6 duyarliligi (pay ayirma, toplam kalan birikme):
  kapasite 850 -> 1460000
  kapasite 900 -> 740000
  kapasite 950 -> 20000

Tek Sıra Adildir ve Yanlıştır

İlk blokta üç sınıfın sayıları neredeyse aynı: tamamlanma oranı 0,946 / 0,946 / 0,950, ortalama bekleme üçünde de 6,5 dakika, en uzun bekleme 13,0 dakika. Tek sıra eşit davranıyor.

Eşitliğin bedeli, sınıfların hizmet düzeylerinin eşit olmamasıdır. Alıcının takip sayfasında görünen durum olayı 6,5 dakika bekliyor; aynı 6,5 dakikayı, sabaha kadar zamanı olan ücretlendirme kaydı da bekliyor. Tek sıra hiçbir sınıfa zarar vermez ve hiçbirine yardım etmez; hizmet düzeyi kavramının bulunmadığı bir politikadır.

Katı Öncelik Açlık Üretir

İkinci blokta A’ya mutlak öncelik verildi. Sonuç A için kusursuz: 1.400.000 işin tamamı bitiyor, ortalama ve en uzun bekleme 0,0 dakika. B de iyileşiyor — bekleme 6,5’ten 4,4 dakikaya, tamamlanma 0,946’dan 0,963’e — çünkü kapasitenin A’dan artanı tamamen ona gidiyor.

C için sonuç başkadır: tamamlanan iş sıfır. Yüz raporun hiçbiri bitmedi; 300.000 işin tamamı pencerenin sonunda kuyrukta duruyor. Bu açlıktır (starvation): üst sınıfların toplam talebi kapasiteyi doldurduğu sürece alt sınıfa hiçbir şey kalmaz ve bekleme süresi bir sayıyla ifade edilemez, çünkü iş hiç başlamaz. Katı öncelik bir sıralama değil, koşullu bir iptaldir.

Pay Ayırma Açığı Yeniden Dağıtır

Üçüncü blokta her sınıfa bir pay ayrıldı. A yine kusursuz (0,0 dakika bekleme), çünkü ayrılan pay 135 iş/s ve ihtiyacı 97,22. C’nin tamamı bitiyor: 300.000 işin hepsi, ortalama bekleme 0,3 dakika.

Bedeli B ödüyor: tamamlanma 0,963’ten 0,938’e, kalan birikme 440.000’den 740.000’e çıkıyor. Fark tam olarak 300.000, yani C’nin iş hacminin kendisi. Politika değişimi hiçbir iş yaratmadı; C’nin işini B’nin sırtından aldı ve muhasebe kuruşuna kadar tutuyor.

Pay Bir Taban ve Bir Tavandır

Son iki blok aynı politikaları A’nın sıçraması altında gösteriyor. Katı öncelikte A yine etkilenmiyor: 1.750.000 işin tamamı, 0,0 dakika bekleme. Pay ayırmada A bekliyor: ortalama 3,5, en uzun 18,1 dakika. Nedeni doğrudandır — sıçrama sırasında A’nın hızı 388,9 iş/s’ye çıkıyor, ayrılan pay ise 135 iş/s. Kullanılmayan paylar A’ya aktarılıyor ama yetmiyor.

Bir pay, aynı anda bir taban ve bir tavandır. C’yi açlıktan kurtaran şey, A’yı sıçramada sınırlayan şeyle aynı mekanizmadır. Politika seçimi bu yüzden “hangisi daha iyi” sorusuna değil, “hangi sınıfın kötü gününde ne olmasını istiyoruz” sorusuna bakar. Katı öncelik en üst sınıfın kötü gününü öteki sınıflara ödetir; pay ayırma her sınıfın kötü gününü kendi payıyla sınırlar.

Hesaba Geri Dönüş

Son üç satır dersin sınırını çiziyor. Üç sınıfın toplam gereksinimi 951,39 iş/s, kapasite 900; açık dört saatlik pencerede 740.000 iştir. Bu sayı beş koşumun beşinde de aynıdır. Tek sırada 75.736 + 649.263 + 15.000, katı öncelikte 0 + 440.000 + 300.000, pay ayırmada 740.000 + 0 + 0. Politika açığın kime yazılacağını seçiyor, açığı küçültmüyor. Sıçramalı koşumlarda toplam 1.090.000’e çıkıyor ve fark eklenen 350.000 işin ta kendisidir.

Açığı kapatmanın iki yolu vardır ve ikisi de kuyruğun dışındadır: kapasiteyi 900’den 951,39 iş/s’ye çıkarmak (1,057 kat) ya da V10 penceresini 4,00 saatten 4,23 saate uzatmak. K6’nın duyarlılığı bunu doğruluyor: kapasite 850’de toplam kalan 1.460.000, 900’de 740.000, 950’de 20.000. Yüzde altılık bir kapasite artışı açığın yüzde 97’sini siliyor.

Buradan K01’e dönen sonuç şudur: V10’un dört saatlik penceresi, gün sonu işi tek başına koşarken geçerlidir. Aynı gruba başka bir akış girdiğinde pencere artık bir kısıt değil, üç sınıfın paylaştığı bir kaynaktır ve V10’un sağlanıp sağlanmadığı yalnız B’nin hızına bakarak söylenemez.

Özet

• Öncelikli kuyruk bir hizmet düzeyi kararıdır; Veri Yapıları müfredatındaki öncelik kuyruğu ise bir veri yapısıdır ve bu derste anlatılmaz.
• Tek sırada üç sınıf aynı sayıları alıyor — tamamlanma 0,946 / 0,946 / 0,950, bekleme 6,5 dakika — yani hizmet düzeyi kavramı yoktur.
• Katı öncelik en üst sınıfı kusursuz karşılıyor (0,0 dakika bekleme) ve en alt sınıfta açlık üretiyor: yüz raporun sıfırı bitti, 300.000 iş kuyrukta kaldı.
• Pay ayırma C’nin tamamını bitiriyor ve bedelini kuruşuna kadar B ödüyor: B’nin kalan birikmesi 440.000’den 740.000’e, tam 300.000 artıyor.
• Pay bir taban ve bir tavandır: A’nın sıçramasında katı öncelik A’yı hiç bekletmezken pay ayırma ortalama 3,5, en uzun 18,1 dakika bekletiyor.
• Toplam açık politikadan bağımsızdır: beş koşumun üçünde de 740.000 iş; kapatmanın yolu kapasiteyi 1,057 katına çıkarmak ya da V10 penceresini 4,23 saate uzatmaktır.

Sonraki Adım

Bu 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 burada 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ı birbirinin üstüne yazar; “aktarma merkezinden ayrıldı” ile “teslim edildi” ters sırayla işlenirse gönderi teslim edildikten sonra yeniden yolda görünür ve sonuç bozulur — üçüncü derste sekiz tüketicide 2279 gönderinin sırası bu yüzden bozulmuştu. Böyle işlerde sıra bir tercih değil bir kısıttır. Sonraki ders sıranın korunması gereken işleri ele alır ve kısıtın koşutlukla nasıl bir arada tutulacağını inceler.