Çok Çekirdekte Eşzamanlılık

Buraya kadarki bütün ölçüler tek çekirdekte yapıldı. İş parçacıkları sırayla ilerledi; “aynı anda” sözü hep bir yaklaşımdı, çizelgeleyicinin hızlı geçişlerinin yarattığı bir görüntüydü. Bu ders o kısıtı kaldırır ve iki soruyu birlikte sorar.

Birincisi başarım sorusudur: çekirdek eklemek işi ne kadar hızlandırır ve nerede durur? İkincisi doğruluk sorusudur ve daha önemlidir: birinci dersteki dilim koruması çok çekirdekte ne olur? İki soru da aynı ortak tanımın üzerinde sayıyla yanıtlanır. Bu kurs tek makineyi modeller; ağ bedeli yoktur ve hiçbir ölçüye girmez.

Çekirdek Eklemek

Paralellik (parallelism), iki işin gerçekten aynı anda yürütülmesidir. Eşzamanlılıktan ayrılır: eşzamanlılık işlerin iç içe geçebilmesi, paralellik aynı anda ilerleyebilmesidir.

EZ21. Her çekirdek bir zaman biriminde en çok bir adım yürütür; çekirdekler özdeştir. EZ22. Bekleme adımı çekirdek tutmaz; bekleyen süreç hiçbir çekirdeği meşgul etmez. EZ23. Bir süreç aynı anda tek bir çekirdekte koşar; süreç içi bölünme modellenmez.

TOHUM = 20260218
SUREC_SAYISI = 5
ADIM_SAYISI = 12
BEKLEME_SURESI = 30      # bir girdi/cikti adimi kac zaman birimi surer
BAGLAM_BEDELI = 2        # bir baglam degistirmenin bedeli (zaman birimi)
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):
    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


SONSUZ = 10**9


def cizelgele(isler, yordam="sirayla", dilim=4, cekirdek=1,
              baglam_bedeli=BAGLAM_BEDELI):
    """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):
                    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}}


ISLER = is_yuku()
print("cekirdek  sure  baglam  bos cekirdek adimi  toplam is  ort.tamamlanma")
for c in (1, 2, 3, 4, 6, 8):
    m = cizelgele(ISLER, "dilimli", cekirdek=c)
    print(f"  {c:6d}  {m['sure']:4d}  {m['baglam']:5d}  {m['bos_cekirdek_adimi']:17d}"
          f"  {m['toplam_is']:9d}  {m['ortalama_tamamlanma']:14.2f}")

print()
print("her surecin kendi zinciri (hicbir paylasim yokken en erken bitis):")
for i in ISLER:
    h = sum(1 for tur, _ in i["adim"] if tur == "HESAP")
    b = ADIM_SAYISI - h
    print(f"  {i['ad']} varis {i['varis']:2d} hesap {h} bekleme {b}"
          f" -> en erken bitis {i['varis'] + h + BEKLEME_SURESI * b}")
print("  ulasilabilir alt sinir:",
      max(i["varis"] + sum(1 for t, _ in i["adim"] if t == "HESAP")
          + BEKLEME_SURESI * sum(1 for t, _ in i["adim"] if t == "BEKLE") for i in ISLER))

cekirdek  sure  baglam  bos cekirdek adimi  toplam is  ort.tamamlanma
       1   197     25                108         39          153.80
       2   180     21                279         39          142.40
       3   179     19                460         39          141.40
       4   179     19                639         39          141.40
       6   179     19                997         39          141.40
       8   179     19               1355         39          141.40

her surecin kendi zinciri (hicbir paylasim yokken en erken bitis):
  S1 varis  0 hesap 9 bekleme 3 -> en erken bitis 99
  S2 varis  4 hesap 9 bekleme 3 -> en erken bitis 103
  S3 varis  8 hesap 7 bekleme 5 -> en erken bitis 165
  S4 varis 12 hesap 7 bekleme 5 -> en erken bitis 169
  S5 varis 16 hesap 7 bekleme 5 -> en erken bitis 173
  ulasilabilir alt sinir: 173

İkinci çekirdek süreyi 197’den 180’e indiriyor: 17 zaman birimi, ölçüm bandının çok üstünde. Üçüncü çekirdek 179 veriyor. Dördüncü de 179. Altıncı, sekizinci de.

İki çekirdekten sonra hiçbir kazanç yok. 180 ile 179 arasındaki 1 zaman birimlik fark zaten ölçüm bandının altındadır ve ölçülmemiş sayılır; anlamlı fark en az bağlam bedeli kadar, yani 2 zaman birimidir.

Bedel Boş Çekirdek Adımında

Kazanç durdu, harcama durmadı. Boş çekirdek adımı 108’den 279’a, sonra 639’a, sekiz çekirdekte 1355’e çıkıyor. Toplam iş her satırda 39 — yapılan iş hiç değişmiyor.

Üç sayıyı yan yana koymak bu dersin ana tablosudur:

Ölçüt	Soyutlamasız taban	Soyutlamalı kurulum	Bedel
Süre	tek çekirdek, 197	dört çekirdek, 179	18 zaman birimi kazanç
Boş çekirdek adımı	108	639	531 ek boş adım
Toplam iş	39	39	değişmedi

Dördüncü çekirdek, üçüncüye göre 179’da hiçbir şey kazandırmıyor ama 179 ek boş çekirdek adımı harcıyor. Sekizinci çekirdeğe kadar gidildiğinde 1355 boş adım karşılığında kazanılan süre 0’dır. Kursun ikinci iddiası burada da ödeniyor: soyutlama bazen kötüleştirir — burada süreyi kötüleştirmiyor ama kaynağı ölçülebilir biçimde harcıyor.

İki sütun daha okunmalıdır. Bağlam değiştirme 25’ten 21’e, sonra 19’a iniyor: çekirdek eklendikçe çizelgeleyicinin süreçleri birbirinin yerine koyma ihtiyacı azalıyor. Ortalama tamamlanma süresi de 153,80’den 141,40‘a düşüyor; süre 179’da dururken tekil süreçlerin bitişi iyileşmeye devam ediyor. Süre tek başına bir çekirdek sayısı kararı vermeye yetmez.

Bir uyarı da buraya aittir. “İki çekirdek yeter” bu iş yükünün sonucudur, genel bir kural değildir. Bu iş yükü girdi/çıktı ağırlıklıdır; hesap ağırlıklı bir iş yükünde eğri başka yerde düzleşir. Tek iş yükünde ölçülmüş bir sıralama ölçülmemiş sayılır ve bu kursta öyle yazılır.

Neden 179’da Duruyor

Çıktının ikinci bölümü nedeni veriyor. Her sürecin kendi adım zinciri var ve bu zincir bölünemez: bir bekleme adımı bittikten sonra sıradaki hesap adımı gelir, tersi olmaz.

S5, 16. zaman biriminde varıyor, 7 hesap ve 5 bekleme adımı taşıyor. Beklemeler $5 \times 30 = 150$ zaman birimi tutuyor ve bu süre boyunca hiçbir çekirdek işe yaramıyor. En erken bitişi $16 + 7 + 150 = 173$.

173, sonsuz çekirdekle bile aşılamayacak alt sınırdır. Ölçülen 179, bu sınırın 6 zaman birimi üstünde. Aradaki fark bağlam değiştirmeden ve varış sıralamasından geliyor.

Buradan çıkan kural sayıya dayanır: iş girdi/çıktıya bağlıysa çekirdek eklemek onu değiştirmez. Bu iş yükünde 39 hesap adımına karşılık 21 bekleme adımı var; beklemeler 630 zaman birimi tutuyor, hesap yalnız 39. Hızlandırılacak şey zaten hesap değildi.

Bellek Görünürlüğü

Şimdi doğruluk sorusu. Birinci ders, çizelgeleyici dilimi kritik bölgeden büyük olduğunda erişilebilen serpiştirmenin 2’ye indiğini ve hiçbirinin yanlış olmadığını gösterdi. O koruma neye dayanıyordu? Tek bir şeye: iki iş parçacığının aynı anda ilerleyememesine.

EZ24. İki çekirdekte iki iş parçacığı ayrı çekirdeklere düşer; aralarında çizelgeleyici geçişi gerekmediği için dilim, bellek erişimlerinin sırasını kısıtlamaz.

def sayac_kosumu(desen: list[int], kilit: bool = False) -> int:
    if kilit:
        return 2
    sayac, yerel = 0, {0: None, 1: None}
    asama = {0: 0, 1: 0}
    for kim in desen:
        a = asama[kim]
        if a == 0:
            yerel[kim] = sayac
        elif a == 1:
            yerel[kim] = yerel[kim] + 1
        else:
            sayac = yerel[kim]
        asama[kim] = a + 1
    return sayac


def serpistirmeler(a: int, b: int) -> list[list[int]]:
    if a == 0:
        return [[1] * b]
    if b == 0:
        return [[0] * a]
    return ([[0] + s for s in serpistirmeler(a - 1, b)]
            + [[1] + s for s in serpistirmeler(a, b - 1)])


def dilimli_serpistirmeler(adim: int, dilim: int) -> list[list[int]]:
    sonuc = []

    def gez(kalan_a, kalan_b, kim, dizi):
        if not kalan_a and not kalan_b:
            sonuc.append(list(dizi))
            return
        for yeni in (0, 1):
            kalan = kalan_a if yeni == 0 else kalan_b
            if not kalan:
                continue
            n = min(dilim, kalan)
            dizi.extend([yeni] * n)
            gez(kalan_a - n if yeni == 0 else kalan_a,
                kalan_b - n if yeni == 1 else kalan_b, yeni, dizi)
            del dizi[len(dizi) - n:]
    gez(adim, adim, None, [])
    ayri = []
    for d in sonuc:
        if d not in ayri:
            ayri.append(d)
    return ayri


print("cekirdek  dilim  kilit  erisilebilen  yanlis  yanlis orani")
for cekirdek, dilim, kilit in ((1, 1, False), (1, 3, False), (2, 3, False),
                               (4, 3, False), (2, 3, True)):
    # iki cekirdekte iki is parcacigi ayri cekirdeklere duser: dilim kisiti kalkar
    kume = serpistirmeler(3, 3) if cekirdek > 1 else dilimli_serpistirmeler(3, dilim)
    yanlis = sum(1 for d in kume if sayac_kosumu(d, kilit) != 2)
    print(f"  {cekirdek:6d}  {dilim:5d}  {str(kilit):5s}  {len(kume):12d}  {yanlis:6d}"
          f"  {yanlis / len(kume):11.4f}")

cekirdek  dilim  kilit  erisilebilen  yanlis  yanlis orani
       1      1  False            20      18       0.9000
       1      3  False             2       0       0.0000
       2      3  False            20      18       0.9000
       4      3  False            20      18       0.9000
       2      3  True             20       0       0.0000

İkinci satır birinci dersin sonucudur: tek çekirdek, dilim 3, 2 erişilebilen serpiştirme, 0 yanlış. Üçüncü satır aynı dilimle, yalnız bir çekirdek fazlasıyla alınmıştır: erişilebilen serpiştirme 20, yanlış 18, oran 0,9000.

Dilim hâlâ 3. Program hâlâ aynı. Değişen tek şey çekirdek sayısı — ve birinci dersin “görünmez olmuş” hatası bir donanım değişikliğiyle geri gelmiştir. Birinci dersin cümlesi tam olarak bunun içindi: hata yok olmamıştı.

Bu, bellek görünürlüğü (memory visibility) sorununun en yalın biçimidir. Bir çekirdeğin yazdığı değerin öbür çekirdeğe ne zaman göründüğü, programın denetiminde değildir. Son satır tek çözümü gösteriyor: kritik bölge bölünemez kılındığında yirmi serpiştirmenin yirmisi de doğru sonuç verir.

Bunun pratik sonucu, birinci dersin örneklem ölçüsünü tamamlar. Orada koşum sayısının kanıt üretmediği gösterilmişti; burada koşum ortamının da kanıt üretmediği görülüyor. Tek çekirdekli bir ortamda binlerce kez temiz sonuç veren bir program, çekirdek sayısı arttığı anda bozulabilir — çünkü değişen şey programın kendisi değil, erişilebilen serpiştirme kümesidir. Bir eşzamanlılık güvencesi, üzerinde koşulan çekirdek sayısından bağımsız olmalıdır; bağımlıysa güvence değildir.

Önbellek Uyumu ve Atomik İşlem

Çekirdekler belleği paylaşırken her birinin kendi önbelleği olur. Bir çekirdeğin yazdığı satırın öbürlerinde geçersizleştirilmesi ve gerektiğinde aktarılması önbellek uyumu (cache coherence) düzeneğiyle sağlanır. Bu düzenek bedava değildir: paylaşılan bir değişkene sık yazmak, çekirdekler arasında sürekli aktarım üretir.

EZ25. Bu tanımda önbellek uyumu ve bellek veri yolu çekişmesi modellenmemiştir; dolayısıyla bu yöndeki bedel bu kursta ölçülmemiştir ve ölçülmemiş sayılır. Yukarıdaki 639 boş çekirdek adımı, uyum bedelini içermez.

Görünürlük sorununun tek adımlık çözümü atomik işlemdir: donanımın oku-artır-yaz üçlemesini bölünmez tek bir adım olarak yürütmesi. Kritik bölge bir adıma indiğinde çekişme de ortadan kalkar; önceki dersin süpürmesi bunu ölçmüştü — sekiz iş parçacığında kritik bölge 10 adımken süre 83 ve kullanım 0,2410 iken, kritik bölge tek adıma indiğinde süre 20 ve kullanım 1,0000 oluyordu.

Atomik işlemin sınırı da oradadır: yalnız tek bir konuma uygulanır. İki alanı birlikte tutarlı tutmak gerekiyorsa kritik bölge yeniden birden çok adım olur ve kilidin bedeli geri gelir.

Özet

• İkinci çekirdek süreyi 197’den 180’e indirir; üçüncüsü 179 verir ve sonrası hiçbir şey kazandırmaz — 180 ile 179 arasındaki 1 zaman birimlik fark ölçüm bandının altındadır.
• Boş çekirdek adımı 108’den 639’a, sekiz çekirdekte 1355’e çıkarken toplam iş 39’da sabit kalır; harcanan kaynağın karşılığı yoktur.
• Alt sınır 173’tür ve bekleme zincirlerinden gelir; iş girdi/çıktıya bağlı olduğunda çekirdek eklemek bunu değiştirmez.
• Gerçek paralellikte dilim koruması ortadan kalkar: dilim 3’te tek çekirdekte 2 olan erişilebilen serpiştirme, iki çekirdekte 20’ye çıkar ve 18’i yanlış olur.
• Önbellek uyumunun bedeli bu tanımda modellenmemiştir ve ölçülmemiş sayılır; atomik işlem kritik bölgeyi tek adıma indirir ama yalnız tek bir konum için geçerlidir.

Sonraki Adım

Üç ders boyunca tek bir eşzamanlılık modeli kullanıldı: paylaşılan belleğe erişen iş parçacıkları ve onları koruyan kilitler. Bu modelin bedeli artık sayılı — çekişme, kilitlenme riski, görünürlük sorunu. Sonraki ders paylaşılan belleğin zorunlu olmadığını gösterir ve üç modeli aynı iş yükünde karşılaştırır: iş parçacığı, olay döngüsü ve ileti geçişi. Ölçü iki ayrı iş yükünde yinelenir, çünkü tek iş yükünde ölçülmüş bir sıralama ölçülmemiş sayılır.