Süreç ve İş Parçacığı Seçimi

Önceki ders iki kurulumu yan yana koydu ve iş parçacığının ucuz olduğunu ölçtü: 15 ek sanal sayfa yerine 4, 194 zaman birimi yerine 186. Bu sayılara bakıp iş parçacığını seçmek, tabloda olmayan bir sütunu görmezden gelmek olur. Süreç kurulumunun karşılığında verdiği şey yalıtımdı ve yalıtımın da bir sayısı olmadan seçim yapılamaz.

Bu ders o sayıyı üretir. Soru şudur: paylaşılan durumu bozan tek bir adım, kaç yürütme birimini etkiler. Yanıt, iki kurulumda birbirinden beş kat farklıdır ve bu, kursun ikinci iddiasının bu konudaki karşılığıdır — soyutlama bazen kötüleştirir, çünkü paylaşımın ucuzluğu bozulmanın da ucuzca yayılması demektir.

• SR23. Beş yürütme birimi, önceki iki derste kullanılan aynı iş yükünü koşar. Her birim belirli sanal sayfalara dokunur; dokunma kümesi iş yükünün hesap adımlarından okunur.
• SR24. Bozulma, bir birimin bir sayfaya hatalı değer yazmasıdır. Tek adımdır ve ölçüm boyunca bir kez olur.
• SR25. Doğrudan etki, bozulan sayfaya dokunan birimlerin sayısıdır.
• SR26. Yayılan etki, bozulmanın ortak sayfalar üzerinden ulaştığı birimlerin sayısıdır: bozuk veriyi okuyan birim kendi sayfalarına da bozuk değer yazar. Bu bir modelleme seçimidir ve kötümser yöndedir.
• SR27. Aynı adres uzayındaki birimler, ortak sayfa üzerinden birbirine bağlı sayılır. Yayılan etki, bu çizgenin bağlantılı bileşenidir.
• SR28. Ayrı adres uzayındaki birimler arasında kenar yoktur. Yalıtımın tanımı budur: bir sürecin yazması bir başkasının sayfasına ulaşamaz.
• SR29. Bileşen hesabı Veri Yapıları kursunun derine arama dersinde kurulan gezinmeyi doğrudan kullanır; yordam burada yeniden anlatılmaz.
• SR30. Bu derste zaman ölçülmez. Ölçülen iki büyüklük etkilenen birim ve kopyalanan sayfadır.

Ödünleşimin İki Ucu

Bir uçta tam paylaşım vardır: beş birim tek adres uzayında koşar, hiçbir sayfa kopyalanmaz, her birim her sayfayı görür. Öteki uçta tam yalıtım vardır: beş ayrı adres uzayı, dört çatallama, kopyalanan sayfalar ve birbirinin belleğine dokunamayan birimler.

Bu iki ucun arasında sürekli bir aralık yoktur; adres uzayı sayısı bir tam sayıdır ve seçim, birimlerin kaç adres uzayına bölüştürüleceğidir. Beş birim tek uzayda, iki uzayda, üç uzayda ya da beş uzayda kurulabilir. Her bölüşüm iki sayı üretir ve bu iki sayı ters yönde hareket eder.

Ödünleşim terimi burada gevşek kullanılmaz. İki büyüklük aynı nedenden doğar: kopyalamaktan kaçınmak, kopyanın verdiği ayrımdan da kaçınmaktır. Bir kurulumda ikisini birden kazanmanın yolu yoktur ve bu dersin bütün sayıları o kısıtın içinde okunur.

Paylaşılan Sayfa Haritası

Ölçüm, hangi birimin hangi sayfaya dokunduğunun bilinmesini gerektirir. İş yükü bunu zaten belirler; ilk blok haritayı çıkarır.

# Bu makine bir BENZETICIDIR. Hicbir gercek surec ya da is parcacigi yaratilmaz;
# butun sayilar modelin icinde uretilir.
TOHUM = 20260218
SUREC_SAYISI = 5
ADIM_SAYISI = 12
BEKLEME_SURESI = 30
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()
ADLAR = [i["ad"] for i in ISLER]
DOKUNUS = {i["ad"]: {v for t, v in i["adim"] if t == "HESAP"} for i in ISLER}
print("birim  dokundugu sanal sayfa  adet")
for a in ADLAR:
    print(f"  {a:4s} {str(sorted(DOKUNUS[a])):22s} {len(DOKUNUS[a]):4d}")
print("ayri sayfa:", len(set().union(*DOKUNUS.values())))
print()
print("sayfa  dokunan birim")
for s in range(SANAL_SAYFA):
    dokunan = [a for a in ADLAR if s in DOKUNUS[a]]
    if len(dokunan) >= 2:
        print(f"{s:5d}  {' '.join(dokunan)}")

birim  dokundugu sanal sayfa  adet
  S1   [0, 1, 2, 3]              4
  S2   [3, 4, 5, 6]              4
  S3   [6, 7, 8, 9]              4
  S4   [9, 11, 12]               3
  S5   [12, 13, 14, 15]          4
ayri sayfa: 15

sayfa  dokunan birim
    3  S1 S2
    6  S2 S3
    9  S3 S4
   12  S4 S5

Harita dar görünür: 15 sayfanın yalnız dördü birden çok birim tarafından kullanılır ve hiçbiri ikiden fazlası tarafından kullanılmaz. Doğrudan etkiye bakılırsa paylaşımın riski küçük durur — en kötü durumda iki birim.

Bozulma Nereye Kadar Yayılır

Doğrudan etki yanıltıcıdır, çünkü bozulma orada durmaz. S1 ile S2 sayfa 3’ü paylaşır, S2 ile S3 sayfa 6’yı, S3 ile S4 sayfa 9’u, S4 ile S5 sayfa 12’yi. Dört ortak sayfa, beş birimi uçtan uca bağlayan bir zincir kurar.

# Ilk blogun uzerine: ADLAR, DOKUNUS ve SANAL_SAYFA oradan gelir.


def bilesen(grup):
    """Ayni adres uzayindaki birimler, ortak sayfa uzerinden birbirine baglidir.
    Bozulmanin yayildigi kume, bu cizgenin baglantili bilesenidir."""
    komsu = {a: [b for b in grup if b != a and DOKUNUS[a] & DOKUNUS[b]] for a in grup}
    goruldu, bilesenler = set(), []
    for a in grup:
        if a in goruldu:
            continue
        yigit, kume = [a], []
        while yigit:                                  # derine arama
            d = yigit.pop()
            if d in goruldu:
                continue
            goruldu.add(d)
            kume.append(d)
            yigit.extend(komsu[d])
        bilesenler.append(sorted(kume))
    return bilesenler


def kurulum(gruplar):
    """gruplar: her biri bir adres uzayini paylasan birim adlari."""
    bs = [b for g in gruplar for b in bilesen(g)]
    hevesli = (len(gruplar) - 1) * SANAL_SAYFA
    yazarken = sum(len(set().union(*(DOKUNUS[a] for a in g))) for g in gruplar[1:])
    return {"adres_uzayi": len(gruplar), "bilesen": len(bs),
            "en_buyuk_bilesen": max(len(b) for b in bs),
            "hevesli": hevesli, "yazarken": yazarken}


BOLUSUM = [[ADLAR], [ADLAR[:3], ADLAR[3:]], [ADLAR[:2], ADLAR[2:4], ADLAR[4:]],
           [[a] for a in ADLAR]]
print("adres uzayi  bilesen  en buyuk bilesen  hevesli kopya  yazarken kopya")
for g in BOLUSUM:
    k = kurulum(g)
    print(f"{k['adres_uzayi']:11d} {k['bilesen']:8d} {k['en_buyuk_bilesen']:17d}"
          f" {k['hevesli']:14d} {k['yazarken']:15d}")
print("tek adres uzayinda bilesen:", bilesen(ADLAR))

adres uzayi  bilesen  en buyuk bilesen  hevesli kopya  yazarken kopya
          1        1                 5              0               0
          2        2                 3             16               6
          3        3                 2             32              10
          5        5                 1             64              15
tek adres uzayinda bilesen: [['S1', 'S2', 'S3', 'S4', 'S5']]

Son satır dersin çekirdeğidir. Tek adres uzayında beş birim tek bileşen oluşturur; hiçbir birim çiftinin doğrudan ortak sayfası olmasa bile, zincir üzerinden hepsi birbirine bağlıdır. S1 ile S5’in ortak hiçbir sayfası yoktur, ama S1’in bozduğu bir değer S2 üzerinden S3’e, S3 üzerinden S4’e, oradan S5’e ulaşır.

Tek Adımın Etkisi

Yayılmayı sayfa sayfa saymak, doğrudan etki ile yayılan etki arasındaki farkı görünür kılar.

# Onceki bloklarin uzerine: ADLAR, DOKUNUS, SANAL_SAYFA ve bilesen.
YAYILAN = {a: b for b in bilesen(ADLAR) for a in b}
print("bozulan sayfa  surec modeli  is parcacigi dogrudan  is parcacigi yayilan")
toplam = [0, 0, 0]
for s in sorted(set().union(*DOKUNUS.values())):
    dokunan = [a for a in ADLAR if s in DOKUNUS[a]]
    yayilan = len({b for a in dokunan for b in YAYILAN[a]})
    toplam = [toplam[0] + 1, toplam[1] + len(dokunan), toplam[2] + yayilan]
    print(f"{s:13d} {1:13d} {len(dokunan):22d} {yayilan:21d}")
print("15 sayfanin toplami:", toplam[0], "|", toplam[1], "|", toplam[2])
print("yayilan / surec modeli orani:", round(toplam[2] / toplam[0], 4))

bozulan sayfa  surec modeli  is parcacigi dogrudan  is parcacigi yayilan
            0             1                      1                     5
            1             1                      1                     5
            2             1                      1                     5
            3             1                      2                     5
            4             1                      1                     5
            5             1                      1                     5
            6             1                      2                     5
            7             1                      1                     5
            8             1                      1                     5
            9             1                      2                     5
           11             1                      1                     5
           12             1                      2                     5
           13             1                      1                     5
           14             1                      1                     5
           15             1                      1                     5
15 sayfanin toplami: 15 | 19 | 75
yayilan / surec modeli orani: 5.0

Son sütun hangi sayfa bozulursa bozulsun 5’tir. Bozulmanın nerede başladığı önemli değildir; tek adres uzayında her yol her yere çıkar. Süreç modelinde aynı sütun sabit 1’dir, çünkü kenar yoktur. Yayılma oranı 5,0’dır ve bu, tam olarak birim sayısıdır.

Doğrudan etkinin toplamı 19’dur, yayılan etkinin toplamı 75. Aradaki 56 birim-sayfa, yalnız haritanın dar görünmesine bakan bir çözümlemenin kaçıracağı risktir. Paylaşılan sayfa sayısını azaltmak bu farkı kapatmaz; zinciri kesmek gerekir ve zinciri kesmenin tek yolu ayrı bir adres uzayıdır.

Çökme bu tablonun uç durumudur. Bir iş parçacığı adres uzayını kullanılamaz hâle getirirse etkilenen birim doğrudan 5 olur; ara adım yoktur. Bir süreç aynı şeyi yaparsa 1 olur ve kalan dört birim koşmayı sürdürür. Yalıtımın satın aldığı şey, tam olarak bu farktır: beş birimlik bir kurulumda dört birimin ayakta kalması ile hiçbirinin kalmaması arasındaki fark.

Yalıtımı Kısmi Almak

Bölüşüm tablosunun iki sütunu ters yönde hareket eder ve bir eğri kurar. Adres uzayı sayısı 1’den 5’e çıkarken en büyük bileşen 5’ten 1’e iner; kopyalanan sayfa ise 0’dan 15’e çıkar (hevesli yordamla 0’dan 64’e). Ara noktalar bu değiş tokuşun tümden geçmek zorunda olmadığını gösterir: iki adres uzayı, 6 kopyalanan sayfayla en büyük bileşeni 5’ten 3’e indirir. İlk kopyalanan 6 sayfa yayılmayı iki birim azaltır; son kopyalanan 5 sayfa yalnız bir birim azaltır. Yalıtımın ilk birimi son biriminden ucuzdur.

Bu, seçimin “hepsi ya da hiçbiri” olmadığı anlamına gelir. Bir grup birim birbirine güvenip tek adres uzayını paylaşabilir, güvenilmeyen bir grup ayrı bir adres uzayına konabilir. Bölüşümün nereden geçeceğine karar veren şey, ortak sayfa haritası değil, hangi bozulmanın kabul edilebilir olduğudur.

Zinciri Ucuza Kesmek

Bölüşüm tablosu adres uzayı sayısını değiştirir. Daha ucuz bir yol daha var: adres uzayı tek kalsın, yalnız ortak sayfalar çoğaltılsın. Zinciri kuran şey dört sayfa olduğuna göre, onları kesmek yeter mi.

# Onceki bloklarin uzerine: ADLAR, DOKUNUS ve SANAL_SAYFA.
ORTAK = [s for s in range(SANAL_SAYFA) if sum(1 for a in ADLAR if s in DOKUNUS[a]) >= 2]


def kesilmis_bilesen(kesilen):
    """Kesilen sayfa her birime ozel kopyalanir; artik kenar kurmaz."""
    kalan = {a: DOKUNUS[a] - set(kesilen) for a in ADLAR}
    komsu = {a: [b for b in ADLAR if b != a and kalan[a] & kalan[b]] for a in ADLAR}
    goruldu, kumeler = set(), []
    for a in ADLAR:
        if a in goruldu:
            continue
        yigit, kume = [a], []
        while yigit:
            d = yigit.pop()
            if d in goruldu:
                continue
            goruldu.add(d)
            kume.append(d)
            yigit.extend(komsu[d])
        kumeler.append(sorted(kume))
    return kumeler


print("ortak sayfa:", ORTAK)
print()
print("kesilen sayfa  ek kopya  bilesen  en buyuk bilesen")
for k in range(len(ORTAK) + 1):
    b = kesilmis_bilesen(ORTAK[:k])
    print(f"{str(ORTAK[:k]):14s} {k:9d} {len(b):8d} {max(len(x) for x in b):17d}")
print()
print("ayni sonuc icin ayri adres uzayi bedeli:",
      sum(len(DOKUNUS[a]) for a in ADLAR[1:]), "kopyalanan sayfa")

ortak sayfa: [3, 6, 9, 12]

kesilen sayfa  ek kopya  bilesen  en buyuk bilesen
[]                     0        1                 5
[3]                    1        2                 4
[3, 6]                 2        3                 3
[3, 6, 9]              3        4                 2
[3, 6, 9, 12]          4        5                 1

ayni sonuc icin ayri adres uzayi bedeli: 15 kopyalanan sayfa

Sayı çarpıcıdır: 4 kopyalanan sayfa, ayrı adres uzaylarının 15 sayfayla vardığı sonuca varır. Her kesilen sayfa en büyük bileşeni tam bir birim küçültür ve dördüncüsünde bileşen sayısı 5’e çıkar.

Bu ucuzluğun üç koşulu vardır ve üçü de yazılmalıdır. Birincisi, harita önceden bilinmelidir; hangi sayfanın paylaşıldığı ancak bütün iş yükü tanındığında söylenebilir. İkincisi, kesme donanım tarafından zorlanmaz; bir birim yanlışlıkla kesilmemiş bir sayfaya yazarsa zincir geri döner. Üçüncüsü, kesilen sayfa artık paylaşılmıyordur — ortak veriyle iletişim kuran bir tasarımda kesme, işi bozar.

Ayrı adres uzayının 15 sayfası tam da bu üç koşulu satın alır: harita gerekmez, kural donanım tarafından zorlanır ve yanlışlıkla bozulamaz. Yalıtımın 11 fazla sayfası, bilgiye ve dikkate değil mekanizmaya ödenmiş fiyattır.

Seçim Kuralı

Üç sayı yan yana konduğunda kural kendini yazar. Taban, tek birim ve tek adres uzayıdır: 0 kopyalanan sayfa, 1 etkilenen birim, yayılma yok. Kurulum, beş birimin tek adres uzayında koşmasıdır: yine 0 kopyalanan sayfa, ama bileşen 1 ve yayılma 5. Bedel, bu yayılmayı 1’e indirmek için ödenen 15 kopyalanan sayfadır — hevesli yordamla 64.

Karar, işin doğasına bakar. Birimler aynı veriyi sürekli paylaşıyorsa ayrı adres uzayları paylaşımı da keser ve iş yapılamaz hâle gelir; bu durumda iş parçacığı kaçınılmazdır ve korunma başka bir katmanda aranır. Birimler birbirinden bağımsız işler yapıyorsa 15 sayfa, yayılmayı beşte bire indirmenin ucuz bir fiyatıdır. Önceki dersin zaman kazancı olan 8 zaman birimi, bu tabloda küçük bir kalemdir; iş parçacığını hızı için seçmek, ölçülen en zayıf gerekçedir.

Özet

• Yalıtım ile paylaşım arasındaki seçim, birimlerin kaç adres uzayına bölüştürüleceği sorusudur ve iki sayı üretir: kopyalanan sayfa ve etkilenen birim.
• Bu iş yükünde 15 sanal sayfanın yalnız dördü birden çok birim tarafından kullanılır; doğrudan etki en kötü durumda 2’dir.
• Dört ortak sayfa beş birimi zincirler: tek adres uzayında bileşen sayısı 1’dir ve hangi sayfa bozulursa bozulsun yayılan etki 5’tir. Yayılma oranı 5,0.
• Süreç kurulumunda aynı bozulma 1 birimde kalır; yalıtımın satın aldığı fark budur ve bedeli 15 kopyalanan sayfadır (hevesli yordamla 64).
• Kısmi yalıtım işe yarar ve doğrusal değildir: iki adres uzayı 6 sayfayla en büyük bileşeni 5’ten 3’e indirir, son 5 sayfa ise yalnız 1 birim kazandırır.
• İş parçacığının zaman kazancı olan 8 zaman birimi, bu ödünleşimin yanında küçüktür; seçim hız üzerinden savunulamaz.

Sonraki Adım

Buraya kadar birimlerin nasıl kurulduğu soruldu: kaç adres uzayı, kaç kopyalanan sayfa, kaç etkilenen birim. Kurulum bittiğinde geriye bir soru kalır ve onu her zaman birimi yeniden sormak gerekir: hazır birimlerden hangisi koşacak. Sonraki ders bu kararı veren çizelgeleyiciyi ele alacak, aynı iş yükünü dört ayrı yordamla koşturacak ve hiçbirinin her iş yükünde en iyi olmadığını gösterecek.