Çizelgeleme Algoritmaları

Önceki dört ders yürütme birimlerinin nasıl kurulduğunu ölçtü: kaç adres uzayı, kaç kopyalanan sayfa, kaç etkilenen birim. Kurulum bittiğinde geriye her zaman biriminde yeniden sorulan tek bir soru kalır — hazır birimlerden hangisi koşacak.

Bu kararı veren bileşen çizelgeleyicidir (scheduler) ve kararın nasıl verildiği ölçülebilir bir farktır. Bu ders aynı beş süreçlik iş yükünü dört ayrı yordamla koşturur, sonra aynı karşılaştırmayı ikinci bir iş yükünde yineler. Dersin sonucu tek bir yordamın seçilmesi değildir; hiçbir yordamın her iş yükünde en iyi olmadığının gösterilmesidir.

• SR31. Çizelgeleyici her zaman biriminde hazır birimlerden birini seçer. Hazır olmayan birim, bekleme adımındadır ve seçilemez.
• SR32. Önalımsız sıra, bir süreci bitene ya da bir bekleme adımına girene kadar bırakmaz; hazır olanlar arasında en erken hazır olanı seçer.
• SR33. Dilimli yordam önalımlıdır: bir süreç en çok 4 zaman birimi koşar, sonra çekirdeği bırakır. Bu süreye zaman dilimi, kısaca dilim denir.
• SR34. Öncelikli yordam en yüksek öncelikli hazır süreci seçer; öncelikler iş yükünün parçasıdır ve ikinci iş yükünde farklıdır.
• SR35. Adil paylaşımlı yordam, o ana kadar en az çekirdek kullanmış hazır süreci seçer.
• SR36. Ölçülen büyüklükler: süre (bütün işin bitmesine kadar geçen zaman birimi), bağlam değiştirme sayısı, boş çekirdek adımı, ortalama tamamlanma süresi (varıştan bitişe) ve ortalama bekleme (hazır ama koşamadığı zaman birimi).
• SR37. İkinci iş yükü tohumu 20260219’dur. Aynı beş süreç yapısı, farklı adım bileşimi ve farklı öncelikler verir.
• SR38. Çözünürlük 2 zaman birimidir. İki yordam arasındaki 1 birimlik fark ölçülmemiş sayılır ve sıralamaya girmez.

İki İş Yükü

İki tohum aynı yapıyı üretir ama farklı bir bileşim verir. Fark, hesap adımı ile bekleme adımı arasındaki dağılımdadır ve çizelgeleyicilerin davranışını belirleyen şey tam olarak budur.

# Bu makine bir BENZETICIDIR. Hicbir gercek cizelgeleyici cagrilmaz; butun
# sureler modeldeki zaman birimidir.
TOHUM = 20260218
IKINCI_TOHUM = 20260219
SUREC_SAYISI = 5
ADIM_SAYISI = 12
BEKLEME_SURESI = 30
BAGLAM_BEDELI = 2
SANAL_SAYFA = 16


def uretec(tohum):
    """Belirlenimci sozde-rastgele uretec. Ayni tohum ayni diziyi verir."""
    d = tohum

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


def is_yuku(tohum=TOHUM):
    """Bir adim ya ("HESAP", sanal_sayfa) ya da ("BEKLE", sure)."""
    r = uretec(tohum)
    isler = []
    for i in range(SUREC_SAYISI):
        adimlar = []
        for _ in range(ADIM_SAYISI):
            if r(10) < 3:
                adimlar.append(("BEKLE", BEKLEME_SURESI))
            else:
                taban = (i * 3) % SANAL_SAYFA
                adimlar.append(("HESAP", (taban + r(4)) % SANAL_SAYFA))
        isler.append({"ad": f"S{i+1}", "adim": adimlar,
                      "oncelik": 1 + r(3), "varis": i * 4})
    return isler


ISLER = is_yuku()
print("is yuku  hesap adimi  bekleme adimi  oncelikler")
for tohum in (TOHUM, IKINCI_TOHUM):
    y = is_yuku(tohum)
    h = sum(1 for i in y for t, _ in i["adim"] if t == "HESAP")
    print(f"{tohum}  {h:10d}  {SUREC_SAYISI * ADIM_SAYISI - h:13d}"
          f"  {[i['oncelik'] for i in y]}")

is yuku  hesap adimi  bekleme adimi  oncelikler
20260218          39             21  [3, 2, 1, 3, 2]
20260219          46             14  [1, 2, 3, 1, 1]

İkinci iş yükü daha hesap ağırlıklıdır: 60 adımın 46’sı çekirdeği tutar, ilkinde bu sayı 39’du. Bu, çizelgeleyici için daha zor bir iştir, çünkü çekirdek için çekişen süreç sayısı artmıştır. Öncelikler de değişmiştir ve tek bir sürecin önceliği 3’tür.

Dört Yordam, Aynı İş Yükü

Aşağıdaki gerçeklenim dört yordamı tek gövdede toplar. Aralarındaki tek fark iki satırdır: hazır kümesinden hangisinin seçildiği ve bir sürecin dilimini doldurup doldurmadığına bakılıp bakılmadığı.

# Ilk blogun uzerine: ISLER ve BAGLAM_BEDELI oradan gelir.
SONSUZ = 10**9


def cizelgele(isler, yordam="sirayla", dilim=4, cekirdek=1,
              baglam_bedeli=BAGLAM_BEDELI):
    """yordam: sirayla (onalimsiz) | dilimli | oncelikli | adil
    Her zaman biriminde her cekirdek en cok bir adim yurutur."""
    durum = [{"ad": i["ad"], "adim": list(i["adim"]), "yer": 0, "varis": i["varis"],
              "hazir": i["varis"], "kullanim": 0, "bitis": None,
              "oncelik": i["oncelik"]} for i in isler]
    pay_siniri = SONSUZ if yordam == "sirayla" else dilim
    cekirdekler = [{"surec": None, "onceki": None, "pay": 0, "engel": 0}
                   for _ in range(cekirdek)]
    t, baglam, bos_adim = 0, 0, 0

    def bitmedi(d):
        return d["yer"] < len(d["adim"])

    while any(bitmedi(d) for d in durum) or any(d["bitis"] is None or d["bitis"] > t
                                               for d in durum):
        for c in cekirdekler:                       # birakma
            d = c["surec"]
            if d is not None and (not bitmedi(d) or d["hazir"] > t or c["pay"] >= pay_siniri):
                c["surec"] = None
        for c in cekirdekler:                       # atama
            if c["engel"] or c["surec"] is not None:
                continue
            tutulan = [x["surec"] for x in cekirdekler if x["surec"] is not None]
            hazir = [d for d in durum if bitmedi(d) and d["hazir"] <= t and d not in tutulan]
            if not hazir:
                continue
            if yordam == "oncelikli":
                sec = min(hazir, key=lambda d: (-d["oncelik"], d["hazir"], d["ad"]))
            elif yordam == "adil":
                sec = min(hazir, key=lambda d: (d["kullanim"], d["hazir"], d["ad"]))
            else:
                sec = min(hazir, key=lambda d: (d["hazir"], d["ad"]))
            if c["onceki"] is not None and c["onceki"] is not sec:
                baglam += 1
                c["engel"] = baglam_bedeli
            c["surec"] = sec
            c["onceki"] = sec
            c["pay"] = 0
        for c in cekirdekler:                       # yurutme
            if c["engel"]:
                c["engel"] -= 1
                continue
            d = c["surec"]
            if d is None:
                bos_adim += 1
                continue
            tur, deger = d["adim"][d["yer"]]
            if tur == "BEKLE":
                d["yer"] += 1
                d["hazir"] = t + deger
                c["surec"] = None
                bos_adim += 1
                if not bitmedi(d):                  # son adim beklemeyse is o zaman biter
                    d["bitis"] = t + deger
            else:
                d["yer"] += 1
                d["kullanim"] += 1
                d["hazir"] = t + 1
                c["pay"] += 1
                if not bitmedi(d):
                    d["bitis"] = t + 1
                    c["surec"] = None
        t += 1
    for d, i in zip(durum, isler):
        gc = sum(v for tur, v in i["adim"] if tur == "BEKLE")
        d["bekleme"] = d["bitis"] - d["varis"] - d["kullanim"] - gc
    return {"sure": t, "baglam": baglam, "bos_cekirdek_adimi": bos_adim,
            "toplam_is": sum(d["kullanim"] for d in durum),
            "ortalama_tamamlanma": round(sum(d["bitis"] - d["varis"] for d in durum) / len(durum), 2),
            "ortalama_bekleme": round(sum(d["bekleme"] for d in durum) / len(durum), 2),
            "bitis": {d["ad"]: d["bitis"] for d in durum}}


YORDAM = ("sirayla", "dilimli", "oncelikli", "adil")
print("cizelgeleyici  sure  baglam  bos.cek  ort.tamamlanma  ort.bekleme")
for y in YORDAM:
    s = cizelgele(ISLER, y)
    print(f"  {y:12s} {s['sure']:4d}  {s['baglam']:5d}  {s['bos_cekirdek_adimi']:6d}"
          f"  {s['ortalama_tamamlanma']:13.2f}  {s['ortalama_bekleme']:10.2f}")
print()
print("dilim supurmesi (dilimli)")
print("dilim  sure  baglam  ort.bekleme")
for d in (1, 2, 4, 8, 16):
    s = cizelgele(ISLER, "dilimli", dilim=d)
    print(f"{d:5d}  {s['sure']:4d}  {s['baglam']:5d}  {s['ortalama_bekleme']:11.2f}")

cizelgeleyici  sure  baglam  bos.cek  ort.tamamlanma  ort.bekleme
  sirayla       194     22     111         148.40       14.60
  dilimli       197     25     108         153.80       20.00
  oncelikli     195     21     114         149.00       15.20
  adil          192     25     103         153.00       19.20

dilim supurmesi (dilimli)
dilim  sure  baglam  ort.bekleme
    1   206     36        33.00
    2   202     29        26.60
    4   197     25        20.00
    8   194     22        14.60
   16   194     22        14.60

Dört yordamın süreleri 192 ile 197 arasındadır; aralarındaki en büyük fark 5 zaman birimidir, yani toplam sürenin yüzde 2,6’sı. Bu, önemli bir okumadır: çizelgeleyici seçimi bu iş yükünde büyük bir kaldıraç değildir. Asıl belirleyici, iş yükünün kendi bekleme adımlarıdır ve onlar 630 zaman birimi tutar.

Önalımlı yordam, önalımsız sıradan 3 zaman birimi daha uzun sürer ve 3 bağlam değiştirme fazla yapar. Ortalama bekleme 14,60’tan 20,00’a çıkar. Dilimlemenin sağladığı şey — hiçbir sürecin çekirdeği uzun süre tutamaması — süreyle ödenir.

Dilim Küçüldükçe Kötüleşir

Süpürme bu ödemenin doğrudan ölçüsüdür. Dilim 4’ten 1’e indiğinde süre 197’den 206‘ya, bağlam değiştirme 25’ten 36‘ya, ortalama bekleme 20,00’dan 33,00‘a çıkar. Her adımda çekirdeği bırakmak, adımların kendisinden çok bağlam değiştirmeye zaman harcamak demektir: 36 geçiş 72 zaman birimi tutar ve iş yükünün toplam hesap adımı 39’dur.

Öteki uçta süpürme durur. Dilim 8 ile dilim 16 tıpatıp aynı sonucu verir: 194, 22, 14,60. Bunun nedeni açıktır — bu iş yükünde hiçbir süreç art arda sekizden fazla hesap adımı yürütmez, dolayısıyla dilim 8’in üstünde önalım hiç tetiklenmez. Bu iş yükünün çözünürlüğü dilim 8’de tükenir; daha büyük dilimlerle yapılan bir karşılaştırma yeni bilgi vermez. Dilim 8’deki 194 ve 22, önalımsız sıranın sayılarının tıpatıp aynısıdır ve olması gereken de budur: önalımın hiç tetiklenmediği bir dilimli yordam, önalımsız yordamdır.

Toplam Süre Neyi Gizler

Toplam süre tek başına bakıldığında dört yordam birbirine yakın durur. Yordamların birbirinden ayrıldığı yer toplam değil, dağılımdır: aynı 192 ile 197 arasındaki süre, süreçler arasında çok farklı biçimlerde bölüşülebilir.

# Onceki bloklarin uzerine: ISLER, cizelgele ve YORDAM.
print("cizelgeleyici  S1   S2   S3   S4   S5   en genis fark")
for y in YORDAM:
    s = cizelgele(ISLER, y)
    t = [s["bitis"][i["ad"]] - i["varis"] for i in ISLER]
    print(f"  {y:12s} " + " ".join(f"{x:4d}" for x in t) + f" {max(t) - min(t):13d}")
print()
print("oncelik 3 olan surecler:", [i["ad"] for i in ISLER if i["oncelik"] == 3])
print("oncelik 1 olan surecler:", [i["ad"] for i in ISLER if i["oncelik"] == 1])
for y in ("sirayla", "oncelikli"):
    s = cizelgele(ISLER, y)
    yuksek = [s["bitis"][i["ad"]] - i["varis"] for i in ISLER if i["oncelik"] == 3]
    dusuk = [s["bitis"][i["ad"]] - i["varis"] for i in ISLER if i["oncelik"] == 1]
    print(f"{y:10s} yuksek oncelik ort. {sum(yuksek) / len(yuksek):6.2f}"
          f" | dusuk oncelik ort. {sum(dusuk) / len(dusuk):6.2f}")

cizelgeleyici  S1   S2   S3   S4   S5   en genis fark
  sirayla       103  112  176  173  178            75
  dilimli       111  120  175  185  178            74
  oncelikli     103  112  187  169  174            84
  adil          127  115  170  180  173            65

oncelik 3 olan surecler: ['S1', 'S4']
oncelik 1 olan surecler: ['S3']
sirayla    yuksek oncelik ort. 138.00 | dusuk oncelik ort. 176.00
oncelikli  yuksek oncelik ort. 136.00 | dusuk oncelik ort. 187.00

Son sütun adil paylaşımlı yordamın ne yaptığını gösterir: en hızlı ve en yavaş sürecin tamamlanma süreleri arasındaki fark 65 zaman birimidir, dört yordamın en darı. Öncelikli yordamda aynı fark 84’tür, en genişi. Adaletin ölçüsü toplam süre değil bu farktır ve adil paylaşımlı yordam onu 19 birim daraltır.

Öncelikli yordamın kime ne kazandırdığı ayrıca sayılabilir. Önceliği 3 olan iki süreç, önalımsız sırada ortalama 138,00 zaman biriminde biterken öncelikli yordamda 136,00’da biter: 2 zaman birimi, yani çözünürlüğün tam sınırında bir kazanç. Önceliği 1 olan süreç ise 176,00’dan 187,00’a geriler — 11 zaman birimi kayıp. Öncelik vermek, kayırılanlara ölçülemeyecek kadar az kazandırıp kayırılmayana ölçülebilir bir bedel ödetir.

Sıralama İkinci İş Yükünde Ayakta Kalıyor mu

Tek bir iş yükünde ölçülmüş bir sıralama, o iş yüküne ait bir olgudur. Sonucun bir kural olabilmesi için ikinci bir iş yükünde de sınanması gerekir.

# Onceki bloklarin uzerine: is_yuku, cizelgele, YORDAM ve IKINCI_TOHUM.
SONUC = {y: [cizelgele(is_yuku(t), y)["sure"] for t in (TOHUM, IKINCI_TOHUM)]
         for y in YORDAM}
EN_IYI = [min(SONUC[y][k] for y in YORDAM) for k in (0, 1)]
print("cizelgeleyici  20260218  fark  20260219  fark")
for y in YORDAM:
    a, b = SONUC[y]
    print(f"  {y:12s} {a:8d} {a - EN_IYI[0]:5d} {b:9d} {b - EN_IYI[1]:5d}")
print()
for k, tohum in enumerate((TOHUM, IKINCI_TOHUM)):
    en_iyi = [y for y in YORDAM if SONUC[y][k] == EN_IYI[k]]
    en_kotu = [y for y in YORDAM if SONUC[y][k] == max(SONUC[z][k] for z in YORDAM)]
    print(f"{tohum}: en iyi {en_iyi} | en kotu {en_kotu}")
print("iki is yukunde de en iyi olan:",
      [y for y in YORDAM if SONUC[y][0] == EN_IYI[0] and SONUC[y][1] == EN_IYI[1]])
print("cozunurluk altinda kalan cift (fark < 2):",
      [(y, z, k) for k in (0, 1) for i, y in enumerate(YORDAM)
       for z in YORDAM[i + 1:] if abs(SONUC[y][k] - SONUC[z][k]) < 2])

cizelgeleyici  20260218  fark  20260219  fark
  sirayla           194     2       189     0
  dilimli           197     5       202    13
  oncelikli         195     3       196     7
  adil              192     0       195     6

20260218: en iyi ['adil'] | en kotu ['dilimli']
20260219: en iyi ['sirayla'] | en kotu ['dilimli']
iki is yukunde de en iyi olan: []
cozunurluk altinda kalan cift (fark < 2): [('sirayla', 'oncelikli', 0), ('oncelikli', 'adil', 1)]

Hangi Sonuç Ayakta Kalır

Çıktının son dört satırı bu dersin bütün iddialarını sınırlar.

Ayakta kalan sonuç: dilimleme adaleti süreyle ödetir. Dilimli yordam iki iş yükünde de en kötüdür — ilkinde en iyiden 5, ikincisinde 13 zaman birimi geride. İkinci iş yükünde fark üç katına çıkar, çünkü hesap ağırlıklı bir iş yükünde önalım daha sık tetiklenir. Bu sonuç iki ölçümde de aynı yönde durur ve yazılabilir.

Ayakta kalmayan sonuç: adil paylaşımın üstünlüğü. Adil paylaşımlı yordam ilk iş yükünde en iyidir, ikincisinde en iyiden 6 zaman birimi geridedir. Aynı yordam bir iş yükünde birinci, ötekinde değildir; dolayısıyla “adil paylaşım en iyisidir” cümlesi ölçülmemiş bir iddiadır ve kurulamaz.

İki iş yükünde de en iyi olan yordam listesi boştur. Bu, dersin ana sonucudur: bir çizelgeleyicinin üstünlüğü kendisinin değil, iş yükünün bileşiminin özelliğidir. Önalımsız sıra hesap ağırlıklı ikinci iş yükünde birinciye çıkar, çünkü orada süreçlerin bekleme adımı azdır ve bölmeden koşturmak toplamı kısaltır.

Son satır çözünürlüğün nasıl çalıştığını gösterir. İlk iş yükünde önalımsız sıra (194) ile öncelikli (195) arasındaki 1 birim, ikinci iş yükünde öncelikli (196) ile adil paylaşımlı (195) arasındaki 1 birim çözünürlüğün altındadır. Bu çiftler ayrılmaz; aralarında bir sıralama yazmak, ölçülmemiş bir farkı ölçülmüş gibi sunmak olur.

Özet

• Çizelgeleyici, her zaman biriminde hazır birimlerden hangisinin koşacağına karar verir; dört yordam bu kararı önalım ve seçim ölçütü bakımından farklı verir.
• Aynı iş yükünde dört yordamın süresi 192 ile 197 arasındadır; en büyük fark 5 zaman birimi, yani yüzde 2,6’dır. Çizelgeleyici seçimi bu iş yükünde büyük bir kaldıraç değildir.
• Dilim küçüldükçe kötüleşir: dilim 1’de süre 206, bağlam değiştirme 36, ortalama bekleme 33,00 olur. Dilim 8 ile 16 aynı sonucu verir; bu iş yükünün çözünürlüğü dilim 8’de tükenir.
• Dilimli yordam iki iş yükünde de en kötüdür (197 ve 202); dilimleme adaleti süreyle ödetir ve bu sonuç iki ölçümde de ayaktadır.
• İki iş yükünde de en iyi olan yordam yoktur: adil paylaşımlı ilkinde birinci, önalımsız sıra ikincisinde birincidir. Üstünlük yordamın değil, iş yükünün bileşiminin özelliğidir.
• Çözünürlük altındaki 1 birimlik farklar ölçülmemiş sayılır; iki çift bu nedenle ayrılmaz kalır ve aralarına sıralama yazılmaz.

Sonraki Adım

Bu konu boyunca birimler birbirinden ayrı sayıldı: her biri kendi adımlarını yürütüyor, çizelgeleyici aralarında gidip geliyordu. Bir varsayım hiç sınanmadı — bir birimin adımı bölündüğünde sonucun değişmeyeceği varsayımı. Kursun sonraki konusu bu varsayımı bozar ve tek bir cümleyi kanıtlar: aynı programın iki birimi aynı veriye dokunduğunda doğru çıktı doğru program demek değildir.