İş Parçacıkları

Önceki ders, çatallamanın bedelinin yalıtımın bedeli olduğunu ölçtü: iki süreç birbirinin belleğine dokunamasın diye sayfalar çoğaltılıyordu. Bu, doğal bir soruyu açar. Aynı programın parçaları birbirinin belleğine dokunmak istiyorsa kopyalamaya ne gerek var.

Bu sorunun yanıtı iş parçacığıdır (thread): adres uzayını paylaşan ama kendi yığıtını tutan bir yürütme birimi. Bu ders, önceki iki dersteki aynı iş yükünü iki kurulumla koşturur ve iki sayıyı yan yana koyar — kopyalanan sayfa ve bağlam değiştirmenin ödettiği zaman birimi.

• SR16. İş parçacığı, bir sürecin içindeki bir yürütme birimidir. Adres uzayını süreçteki öteki iş parçacıklarıyla paylaşır, kendi yığıtını ayrı tutar.
• SR17. Her yeni iş parçacığı yığıtı için 1 sanal sayfa ister. Bu bir seçimdir; sayfa sayısı büyürse iş parçacığının ek maliyeti de büyür.
• SR18. Bir süreç bağlam değiştirmesi adres uzayını da değiştirir ve 2 zaman birimi tutar (ortak tanımın BAGLAM_BEDELI değeri).
• SR19. Bir iş parçacığı bağlam değiştirmesinde adres uzayı aynı kalır; bu modelde bedeli 1 zaman birimidir. Sonuç bu seçime duyarlıdır ve duyarlılık ders içinde süpürülür.
• SR20. İş yükü, tohumu ve çizelgeleyici önceki iki dersteki ile aynıdır. Değişen tek şey birimlerin nasıl kurulduğudur; iş aynı iştir.
• SR21. Paylaşılan adres uzayının doğruluk sonuçları bu derste ölçülmez. Yarış koşulu ve karşılıklı dışlama, kursun eşzamanlılık konusunun işidir.
• SR22. Ölçünün çözünürlüğü 2 zaman birimidir.

Aynı İş, İki Kurulum

Beş yürütme birimi aynı işi yapacak. Süreç kurulumunda her birim kendi adres uzayında koşar ve önceki dersteki çatallama bedelini öder. İş parçacığı kurulumunda beş birim tek adres uzayında koşar; kopyalanacak sayfa yoktur, ama her birim kendi yığıtını ister.

# Bu makine bir BENZETICIDIR. Hicbir gercek is parcacigi, kilit ya da
# eszamanlilik kitapligi cagrilmaz; butun sureler modeldeki zaman birimidir.
TOHUM = 20260218
SUREC_SAYISI = 5
ADIM_SAYISI = 12
BEKLEME_SURESI = 30
BAGLAM_BEDELI = 2        # surec baglam degistirmesi: adres uzayi da degisir
IP_BAGLAM_BEDELI = 1     # is parcacigi baglam degistirmesi: adres uzayi ayni kalir
SANAL_SAYFA = 16
YIGIT_SAYFASI = 1        # her is parcacigi kendi yigiti icin bir sanal sayfa ister


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()
DOKUNUS = {i["ad"]: {v for t, v in i["adim"] if t == "HESAP"} for i in ISLER}
YENI = [i["ad"] for i in ISLER[1:]]          # ilk birim disindaki dort birim
SUREC_HEVESLI = len(YENI) * SANAL_SAYFA
SUREC_YAZARKEN = sum(len(DOKUNUS[a]) for a in YENI)
IS_PARCACIGI = len(YENI) * YIGIT_SAYFASI
print("ayni is, uc kurulum:", len(ISLER), "yurutme birimi,",
      len(set().union(*DOKUNUS.values())), "ayri sanal sayfa")
print()
print("kurulum            adres uzayi  kopyalanan sayfa  ek yigit sayfasi  toplam ek sayfa")
print(f"  surec (hevesli)  {len(ISLER):11d} {SUREC_HEVESLI:17d} {0:17d} {SUREC_HEVESLI:16d}")
print(f"  surec (yazarken) {len(ISLER):11d} {SUREC_YAZARKEN:17d} {0:17d} {SUREC_YAZARKEN:16d}")
print(f"  is parcacigi     {1:11d} {0:17d} {IS_PARCACIGI:17d} {IS_PARCACIGI:16d}")

ayni is, uc kurulum: 5 yurutme birimi, 15 ayri sanal sayfa

kurulum            adres uzayi  kopyalanan sayfa  ek yigit sayfasi  toplam ek sayfa
  surec (hevesli)            5                64                 0               64
  surec (yazarken)           5                15                 0               15
  is parcacigi               1                 0                 4                4

Bellek tarafındaki fark keskindir. Beş süreç, en iyi durumda bile 15 ek sanal sayfa ister; beş iş parçacığı 4 ister ve bunlar da adres uzayının kopyaları değil, yığıt sayfalarıdır. Ortak veriye ulaşmak için hiçbir kopya yapılmaz: 15 sanal sayfalık ortak alan tek nüsha olarak durur ve beş birim de aynı nüshayı görür.

Neyi Ayrı Tutar, Neyi Ortaklaşır

Bir iş parçacığının bağlam değiştirmesinin neden daha ucuz olduğu, taşınan durumun sayılmasıyla görülür. Bu kursun ilk dersinde süreç tablosunun dokuz alan taşıdığı sayılmıştı. O dokuz alanın hepsi yürütme birimine özgü değildir: bir bölümü birimin kendi ilerlemesini, bir bölümü ise içinde bulunduğu adres uzayını anlatır.

# Ilk blogun uzerine: ISLER oradan gelir.
OZEL = ("ad", "yer", "hazir", "kullanim", "bitis", "bekleme")   # birime ozel
ORTAK = ("adim", "varis", "oncelik")                            # adres uzayi duzeyinde
n = len(ISLER)
surec_alan = n * (len(OZEL) + len(ORTAK))
ip_alan = n * len(OZEL) + len(ORTAK)
print("birime ozel alan :", OZEL)
print("ortak alan       :", ORTAK)
print()
print(f"surec kurulumu       : {n} girdi x {len(OZEL) + len(ORTAK)} alan = {surec_alan} alan")
print(f"is parcacigi kurulumu: {n} x {len(OZEL)} + {len(ORTAK)} = {ip_alan} alan")
print("baglam degistirmede tasinan alan farki:", surec_alan - ip_alan,
      f"| yuzde {round(100 * (surec_alan - ip_alan) / surec_alan, 2)} azalma")

birime ozel alan : ('ad', 'yer', 'hazir', 'kullanim', 'bitis', 'bekleme')
ortak alan       : ('adim', 'varis', 'oncelik')

surec kurulumu       : 5 girdi x 9 alan = 45 alan
is parcacigi kurulumu: 5 x 6 + 3 = 33 alan
baglam degistirmede tasinan alan farki: 12 | yuzde 26.67 azalma

Dokuz alanın altısı birime özeldir: adı, kaldığı adım, ne zaman koşmaya hazır olduğu, ne kadar çekirdek kullandığı, ne zaman bittiği. Üçü adres uzayı düzeyindedir ve tek nüsha yeter. Süreç kurulumu bu üç alanı beş kez tutar, iş parçacığı kurulumu bir kez; toplam 45 alandan 33 alana, yüzde 26,67 azalmayla iner.

Bu, bir sonraki bölümdeki zaman farkının nedenidir. Bağlam değiştirmenin bedeli, saklanan ve geri yüklenen durumun büyüklüğüyle orantılıdır; iş parçacığı geçişinde adres uzayı düzeyindeki alanlar hiç dokunulmadan yerinde kalır.

Bağlam Değiştirmenin İki Fiyatı

Zaman tarafı bellek tarafı kadar keskin değildir ve bu, dersin ölçmesi gereken asıl şeydir. Çizelgeleyici iki kurulumda aynı kararları verir; iş yükü değişmediği için hangi birimin ne zaman koşacağı da değişmez. Değişen tek şey bir geçişin fiyatıdır.

# Ilk blogun uzerine: ISLER, BAGLAM_BEDELI, IP_BAGLAM_BEDELI,
# SUREC_YAZARKEN ve IS_PARCACIGI 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}}


KURULUM = (("surec", BAGLAM_BEDELI, SUREC_YAZARKEN),
           ("is parcacigi", IP_BAGLAM_BEDELI, IS_PARCACIGI),
           ("bedelsiz taban", 0, 0))
OLCUM = {ad: cizelgele(ISLER, "sirayla", baglam_bedeli=b) for ad, b, _ in KURULUM}
print("kurulum          baglam bedeli  baglam  sure  ort.tamamlanma  ek sayfa")
for ad, b, sayfa in KURULUM:
    s = OLCUM[ad]
    print(f"  {ad:15s} {b:13d} {s['baglam']:7d} {s['sure']:5d}"
          f" {s['ortalama_tamamlanma']:15.2f} {sayfa:9d}")
p, ip = OLCUM["surec"], OLCUM["is parcacigi"]
print()
print("surecten is parcacigina gecis")
print("  ek sayfa :", SUREC_YAZARKEN, "->", IS_PARCACIGI,
      f"| yuzde {round(100 * (SUREC_YAZARKEN - IS_PARCACIGI) / SUREC_YAZARKEN, 2)} azalma")
print("  sure     :", p["sure"], "->", ip["sure"],
      f"| yuzde {round(100 * (p['sure'] - ip['sure']) / p['sure'], 2)} azalma")
print("  baglam   :", p["baglam"], "->", ip["baglam"], "| degismedi")
print()
print("baglam bedeli duyarliligi")
print("bedel  sure  ort.bekleme")
for b in range(5):
    s = cizelgele(ISLER, "sirayla", baglam_bedeli=b)
    print(f"{b:5d} {s['sure']:5d} {s['ortalama_bekleme']:12.2f}")

kurulum          baglam bedeli  baglam  sure  ort.tamamlanma  ek sayfa
  surec                       2      22   194          148.40        15
  is parcacigi                1      22   186          142.80         4
  bedelsiz taban              0      22   178          137.20         0

surecten is parcacigina gecis
  ek sayfa : 15 -> 4 | yuzde 73.33 azalma
  sure     : 194 -> 186 | yuzde 4.12 azalma
  baglam   : 22 -> 22 | degismedi

baglam bedeli duyarliligi
bedel  sure  ort.bekleme
    0   178         3.40
    1   186         9.00
    2   194        14.60
    3   202        20.20
    4   211        26.80

Kazanç Nerede, Nerede Değil

Üçüncü satır tabandır: bağlam değiştirme bedava olsaydı bu iş yükü 178 zaman biriminde biterdi. 194 ile 178 arasındaki 16 birim, süreç kurulumunda paylaşımın ödettiği adımdır ve tam olarak $22 \times 2$’dir. İş parçacığı kurulumu bu kalemi yarıya indirir: 186, yani $22 \times 1$ fazlasıyla taban.

Bağlam değiştirme sayısı değişmez. Her iki kurulumda da 22 geçiş olur, çünkü geçiş kararını iş yükü verir, birimin türü değil. İş parçacığı geçişleri azaltmaz; her geçişi ucuzlatır.

Kazancın büyüklüğü iki tarafta çok farklıdır. Bellekte ek sayfa 15’ten 4’e, yani yüzde 73,33 azalır. Zamanda süre 194’ten 186’ya, yani yüzde 4,12 azalır. Sekiz zaman birimi çözünürlüğün (2 birim) üstündedir, dolayısıyla ölçülmüştür ve gerçektir — ama bellekteki kazanç yanında küçüktür. İş parçacığının bu iş yükündeki kazancı zamanda değil, bellektedir. Zaman kazancı ancak bağlam değiştirme oranı yükseldikçe büyür; süpürme bunu gösterir, bedel 4’e çıktığında aynı iş yükü 211 zaman birimi sürer.

Kurulum anındaki fark, koşum sırasındaki farktan büyüktür. Önceki dersin bedel ölçüsüyle — bir sanal sayfanın kopyalanması 1 zaman birimi — dört süreç kurmak hevesli yordamla 64, yazarken kopyalamayla 15 zaman birimi tutar; dört iş parçacığı kurmak 4 yığıt sayfası, yani 4 zaman birimi tutar. Kısa ömürlü birimlerde toplam maliyeti belirleyen kalem koşum değil kurulumdur ve orada oran 15’e 4’tür.

Kazancın küçük kalmasının nedeni iş yükünün bileşimidir: 60 adımın 21’i bekleme adımıdır ve bekleme adımları 630 zaman birimi tutar. Bağlam değiştirmeye giden 44 birim, bu büyüklüğün yanında küçük kalır. Hesap ağırlıklı bir iş yükünde oran tersine döner ve iş parçacığının zaman kazancı belirginleşir.

Paylaşımın İkinci Yüzü

Tabloda görünmeyen bir kalem var ve dersin dürüst olması için yazılması gerekir. Süreç kurulumunda beş birim birbirinin belleğini göremez; iş parçacığı kurulumunda beşi de 15 sanal sayfalık ortak alanın tamamını görür ve değiştirebilir. Kopyalamadan kaçınmanın yolu, kopyayı gereksiz kılmaktan geçer — yani yalıtımı kaldırmaktan.

Yığıtların ayrı olması bu görünürlüğü sınırlamaz. Yığıt ayrımı, iki birimin birbirinin yerel değişkenlerini kazara ezmesini engeller; ortak alandaki veriyi korumaz. Ortak alan zaten paylaşılsın diye oradadır ve iş parçacığı kurulumunun bütün kazancı ondan gelir; korunması gereken şeyle kazancın kaynağı aynı 15 sayfadır.

Bu, ek bir sayfa maliyeti değildir; bir doğruluk maliyetidir ve sayfa cinsinden ölçülemez. İki birim aynı sayfaya aynı anda yazdığında ortaya çıkan sorun, bu kursun eşzamanlılık konusunda kendi ölçüsüyle ele alınır. Bu konunun sonraki dersi ise ödünleşimin öteki ucunu sayar: paylaşılan durumu bozan tek bir adımın kaç birimi etkilediğini.

Özet

• İş parçacığı, adres uzayını süreçteki öteki iş parçacıklarıyla paylaşan, kendi yığıtını ayrı tutan bir yürütme birimidir.
• Aynı beş birimlik iş, süreçle kurulduğunda yazarken kopyalamayla bile 15 ek sanal sayfa ister; iş parçacığıyla 4 yığıt sayfası yeter, azalma yüzde 73,33’tür.
• Bağlam değiştirme sayısı iki kurulumda da 22’dir; birimin türü geçiş sayısını değil, geçişin fiyatını değiştirir.
• Süre 194’ten 186 zaman birimine iner. Fark 8 birimdir, çözünürlüğün üstündedir ve ölçülmüştür; ama yüzde 4,12’dir ve bellekteki kazanç yanında küçüktür.
• Bedel süpürmesi sonucun bir seçime bağlı olduğunu gösterir: bağlam bedeli 0’da süre 178, 4’te 211 olur.
• Paylaşımın sayfa cinsinden ölçülemeyen bir bedeli vardır: beş iş parçacığı ortak alanın tamamını görür ve yalıtım ortadan kalkar.

Sonraki Adım

Elde iki kurulum ve iki sayı var: iş parçacığı daha az sayfa ve biraz daha az zaman istiyor, süreç ise yalıtım veriyor. Bir seçim yapmak için yalıtımın da bir sayısı olmalı. Sonraki ders bu sayıyı üretecek: paylaşılan durumu bozan tek bir adımın kaç yürütme birimine yayıldığını ölçecek ve yalıtımın kaç sayfaya mal olduğunu bunun karşısına koyacak.