Süreç Çatallama

Önceki derste beş süreç hazır verilmişti; makine açıldığında orada duruyorlardı. Gerçek bir makinede hiçbir süreç böyle doğmaz. Her süreç, çalışmakta olan bir başka süreç tarafından yaratılır ve yaratıldığı anda yaratıcısından bir şeyler devralır. Bu türetme işlemine çatallama (fork) denir.

Sorunun ölçülebilir biçimi şudur: bir sürecin kopyası çıkarılırken kaç sanal sayfanın kopyalanması gerekir. Süreç soyutlamasının yalıtım güvencesi tam olarak burada bedelini ister, çünkü iki sürecin birbirinin belleğine dokunamaması ancak iki ayrı adres uzayı varsa sağlanır.

• SR9. Çatallama, var olan bir süreçten yeni bir süreç türetir. Türeten ebeveyn, türeyen çocuktur; ilişki bir ağaç kurar.
• SR10. Bu derste ağaç sabittir: S1 çatallayarak S2 ve S3’ü, S2 çatallayarak S4 ve S5’i üretir. Toplam dört çatallama vardır.
• SR11. Bir sürecin adres uzayı 16 sanal sayfadır (ortak tanımın SANAL_SAYFA değeri). Bir sayfanın kopyalanması 1 zaman birimi tutar.
• SR12. Bir sayfayı salt okunur işaretlemek bir bit çevirmektir ve bu modelde 0 zaman birimi tutar. Bu bir seçimdir ve sonuç ona duyarlıdır; duyarlılık ders içinde süpürülür.
• SR13. Çocuğun dokunduğu sayfa kümesi, iş yükünün hesap adımlarından okunur. Her dokunuş yazma sayılır; bu, yazarken kopyalama için kötümser üst sınırdır.
• SR14. Alt süreç çalıştırma, boru hattı ve iş denetimi Kabuk Programlama kursunda kullanım düzeyinde ele alındı; burada tekrarlanmaz. Bu ders yalnız çatallamanın kalıtımını ve maliyetini sayar.
• SR15. Ölçünün çözünürlüğü 2 zaman birimidir. Bunun altındaki fark ölçülmemiş sayılır ve öyle yazılır.

Çatallamanın Üç Ayrı Davranışı

Çatallama tek bir işlem gibi görünür ama sürecin durumunu üç ayrı biçimde ele alır ve bu üç biçim birbiriyle karıştırılmamalıdır.

Kopyalama. Adres uzayı çocuğa aittir. Ebeveyn kopyaladıktan sonra bir sayfayı değiştirirse çocuk bunu görmez, çocuk değiştirirse ebeveyn görmez. Yalıtımı sağlayan davranış budur ve tek bedelli olan da budur.

Kalıtım. Bazı alanlar çocuğa değeriyle geçer: öncelik, çalışma dizini, kaynak sınırları. Çocuk bunları sonradan değiştirebilir ve değişiklik ebeveyni etkilemez, ama başlangıç değeri ebeveynden gelir.

Paylaşım. Bazı yapılar tek nesne olarak kalır ve iki süreç aynı nesneyi görür. Açık dosya tanıtıcısının (file descriptor) işaret ettiği okuma konumu böyledir: ebeveyn okuyup ilerlediğinde çocuk kaldığı yerden okur. Paylaşımın bedeli sıfırdır, ama yalıtımı da yoktur.

Üçünün ayrı tutulması gerekir, çünkü bir hata ararken sorulacak soru her birinde farklıdır. Kopyalanan bir alanda ebeveynin sonraki değişikliği çocuğa hiçbir zaman ulaşmaz; kalıtılan bir alanda çocuğun başlangıç değeri ebeveyninkidir ama sonrası bağımsızdır; paylaşılan bir nesnede iki sürecin her işlemi diğerini etkiler. Çatallama sonrası beklenmedik bir davranış görüldüğünde ilk iş, ilgili durumun bu üç kümeden hangisine düştüğünü belirlemektir.

Çocuk, ebeveyninden bağımsız bir süreçtir; ebeveyn önce bitse bile çocuk koşmayı sürdürür. Süreç tablosundaki girdisi kendisine aittir ve önceki dersteki dokuz alanı taşır. Bu yüzden çatallamanın bedeli iki kalemdir: bir süreç tablosu girdisi ve bir adres uzayı. Girdi sabit ve küçüktür; adres uzayı sabit değildir ve bu dersin ölçtüğü şey odur.

İş Yükü ve Çatallama Ağacı

İlk blok, önceki derste kurulan iş yükünü aynen yeniden kurar. İkinci blok çatallamayı modeller ve iki kopyalama yordamını sayar.

# Bu makine bir BENZETICIDIR. Hicbir gercek surec, cekirdek cagrisi ya da
# zaman olcumu yoktur; butun sureler modeldeki zaman birimidir.
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):
    """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("surec  varis  oncelik  hesap adimi")
for i in ISLER:
    h = sum(1 for t, _ in i["adim"] if t == "HESAP")
    print(f"  {i['ad']:4s} {i['varis']:5d} {i['oncelik']:8d} {h:12d}")

surec  varis  oncelik  hesap adimi
  S1       0        3            9
  S2       4        2            9
  S3       8        1            7
  S4      12        3            7
  S5      16        2            7

Neyi Kopyalar, Neyi Kalıtır, Neyi Paylaşır

Aşağıdaki catalla yordamı çocuğun süreç tablosu girdisini üretir. Alanların yanındaki yorumlar üç davranışın hangisinin işlediğini gösterir; son satır paylaşımı nesne kimliğiyle kanıtlar.

# Ilk blogun uzerine: ISLER, SANAL_SAYFA ve ADIM_SAYISI oradan gelir.
KOPYA_BEDELI = 1                 # bir sanal sayfayi kopyalamak kac zaman birimi surer
TANITICI = [0, 1, 2]             # her surecin acilista tuttugu tanitici listesi
AGAC = [("S2", "S1"), ("S3", "S1"), ("S4", "S2"), ("S5", "S2")]
TABLO = {i["ad"]: dict(i, tanitici=list(TANITICI)) for i in ISLER}
DOKUNUS = {i["ad"]: sorted({v for t, v in i["adim"] if t == "HESAP"}) for i in ISLER}


def catalla(ad, ebeveyn_ad, yordam="hevesli"):
    """Cocugun surec tablosu girdisini uretir ve kopyalanan sayfayi sayar."""
    e = TABLO[ebeveyn_ad]
    cocuk = {"ad": ad,                          # yeni: cocugun kendi kimligi
             "varis": TABLO[ad]["varis"],       # yeni
             "adim": list(TABLO[ad]["adim"]),   # cocugun catallamadan sonraki adimlari
             "oncelik": e["oncelik"],           # kalitim: ebeveynden gelir
             "tanitici": e["tanitici"]}         # paylasim: ayni liste nesnesi
    sayfa = SANAL_SAYFA if yordam == "hevesli" else len(DOKUNUS[ad])
    return cocuk, sayfa


for yordam in ("hevesli", "yazarken"):
    sayfa = sum(catalla(ad, eb, yordam)[1] for ad, eb in AGAC)
    print(f"{yordam:9s} kopyalama: {len(AGAC)} catallama, {sayfa:2d} sayfa,"
          f" {sayfa * KOPYA_BEDELI:2d} zaman birimi")
print()
print("cocuk  dokundugu sayfa      adet  hevesli  yazarken  bosa kopyalanan")
for ad, eb in AGAC:
    d = len(DOKUNUS[ad])
    print(f"  {ad:4s} {str(DOKUNUS[ad]):20s} {d:4d} {SANAL_SAYFA:8d} {d:9d}"
          f" {SANAL_SAYFA - d:16d}")
print("toplam bosa kopyalanan sayfa:",
      sum(SANAL_SAYFA - len(DOKUNUS[ad]) for ad, _ in AGAC))
print()
c, _ = catalla("S2", "S1")
print("kalitim  : oncelik", TABLO["S1"]["oncelik"], "->", c["oncelik"])
print("paylasim : tanitici listesi ayni nesne mi:", c["tanitici"] is TABLO["S1"]["tanitici"])
print("yenilenen: ad", c["ad"], "| varis", c["varis"])

hevesli   kopyalama: 4 catallama, 64 sayfa, 64 zaman birimi
yazarken  kopyalama: 4 catallama, 15 sayfa, 15 zaman birimi

cocuk  dokundugu sayfa      adet  hevesli  yazarken  bosa kopyalanan
  S2   [3, 4, 5, 6]            4       16         4               12
  S3   [6, 7, 8, 9]            4       16         4               12
  S4   [9, 11, 12]             3       16         3               13
  S5   [12, 13, 14, 15]        4       16         4               12
toplam bosa kopyalanan sayfa: 49

kalitim  : oncelik 3 -> 3
paylasim : tanitici listesi ayni nesne mi: True
yenilenen: ad S2 | varis 4

Hevesli kopyalama, çatallama anında adres uzayının tamamını çıkarır: dört çatallama için $4 \times 16 = 64$ sayfa. Yazarken kopyalama (copy-on-write) ise çatallama anında hiçbir sayfayı kopyalamaz; bütün sayfaları salt okunur işaretler ve bir sayfaya ilk yazma denendiğinde yalnız o sayfayı çıkarır. Bu iş yükünde dört çocuk toplam 15 ayrı sayfaya dokunur, dolayısıyla kopyalanan sayfa 64’ten 15’e iner.

Aradaki 49 sayfa boşa kopyalanmış sayfadır: hevesli yordam onları çıkarır, çocuk hiçbirine dokunmaz. Oran süreç başına belirgindir — S4 kendi adres uzayının 16 sayfasından yalnız 3’üne dokunur, geri kalan 13’ü kopyalanır ve okunmadan atılır.

Kalıtım Zincir Boyunca İşler

Çatallama bir ağaç kurduğu için kalıtım tek adımda kalmaz. S4, S2’den türer ve S2 de S1’den türemiştir; dolayısıyla S4’ün başlangıç önceliği S1’e kadar geri gider. Ağacın tamamı kurulduğunda bunun ne yaptığı sayılabilir.

# Onceki bloklarin uzerine: ISLER, AGAC, TABLO ve catalla.
EBEVEYN = dict(AGAC)


def agaci_kur(yordam="hevesli"):
    """Kok S1'den baslayarak butun agaci catallar; oncelik zincir boyunca kalitilir."""
    kurulu, sayfa = {"S1": dict(TABLO["S1"])}, 0
    for ad, eb in AGAC:
        c, s = catalla(ad, eb, yordam)
        c["oncelik"] = kurulu[eb]["oncelik"]          # kalitim zinciri
        kurulu[ad] = c
        sayfa += s
    return kurulu, sayfa


KURULU, SAYFA = agaci_kur()
DERINLIK = {"S1": 0}
print("surec  ebeveyn  derinlik  kendi onceligi  kalitilan oncelik")
for i in ISLER:
    ad = i["ad"]
    if ad in EBEVEYN:
        DERINLIK[ad] = DERINLIK[EBEVEYN[ad]] + 1
    print(f"  {ad:4s} {EBEVEYN.get(ad, '-'):>8s} {DERINLIK[ad]:9d}"
          f" {TABLO[ad]['oncelik']:15d} {KURULU[ad]['oncelik']:18d}")
print("agac derinligi:", max(DERINLIK.values()),
      "| yaprak:", sum(1 for a in DERINLIK if a not in EBEVEYN.values()))
print("kendi onceliklerinde ayri deger:", len({TABLO[a]["oncelik"] for a in DERINLIK}),
      "| kalitilanlarda:", len({KURULU[a]["oncelik"] for a in DERINLIK}))

surec  ebeveyn  derinlik  kendi onceligi  kalitilan oncelik
  S1          -         0               3                  3
  S2         S1         1               2                  3
  S3         S1         1               1                  3
  S4         S2         2               3                  3
  S5         S2         2               2                  3
agac derinligi: 2 | yaprak: 3
kendi onceliklerinde ayri deger: 3 | kalitilanlarda: 1

Son satır kalıtımın sessiz sonucudur. İş yükünün kendi öncelik değerleri üç ayrı düzey taşır; ağaç çatallamayla kurulduğunda hepsi kökün değerine, yani 3’e iner ve ayrı düzey sayısı 1’e düşer. Öncelik bakan bir çizelgeleyici için bu, bütün süreçlerin ayırt edilemez hâle gelmesi demektir; kalıtımın maliyeti sayfa cinsinden sıfırdır ama bilgi cinsinden değildir. Çocuk kendi önceliğini sonradan açıkça kurmak zorundadır; kurmazsa ebeveyninkiyle koşar.

Ağacın derinliği bu kurulumda 2, yaprak sayısı 3’tür. Derinlik önemlidir çünkü kalıtım zincirinin uzunluğunu verir: derinliği $d$ olan bir çocuğun başlangıç değerleri, $d$ adım öteden gelmiş olabilir ve bunu görmenin tek yolu ağacı geri yürümektir.

Kopyalama, İşin Kendisiyle Karşılaştırıldığında

Bu sayıların büyük olup olmadığı, ancak iş yükünün gerçek işiyle yan yana konunca anlaşılır. Aynı beş sürecin toplam hesap adımı 39 zaman birimidir.

# Onceki bloklarin uzerine: ISLER, AGAC, DOKUNUS, SANAL_SAYFA, KOPYA_BEDELI.
ISARET_BEDELI = 0        # bir sayfayi salt okunur isaretlemek bir bit cevirmektir
HESAP = sum(1 for i in ISLER for t, _ in i["adim"] if t == "HESAP")
SAYFA = sum(len(DOKUNUS[ad]) for ad, _ in AGAC)
HEVESLI = len(AGAC) * SANAL_SAYFA
print("is yukunun toplam hesap adimi        :", HESAP)
print("hevesli kopyalama / hesap adimi orani:", round(HEVESLI / HESAP, 4))
print("yazarken kopyalama / hesap adimi     :", round(SAYFA / HESAP, 4))
print()
print("sayfa hatasi bedeli  hevesli  yazarken  kazanan")
for hata in range(7):
    h = HEVESLI * KOPYA_BEDELI
    y = HEVESLI * ISARET_BEDELI + SAYFA * (hata + KOPYA_BEDELI)
    if abs(h - y) < 2:
        kazanan = "olculemez"
    else:
        kazanan = "yazarken" if y < h else "hevesli"
    print(f"{hata:19d} {h:8d} {y:9d}  {kazanan}")

is yukunun toplam hesap adimi        : 39
hevesli kopyalama / hesap adimi orani: 1.641
yazarken kopyalama / hesap adimi     : 0.3846

sayfa hatasi bedeli  hevesli  yazarken  kazanan
                  0       64        15  yazarken
                  1       64        30  yazarken
                  2       64        45  yazarken
                  3       64        60  yazarken
                  4       64        75  hevesli
                  5       64        90  hevesli
                  6       64       105  hevesli

İlk oran, bu dersin en sert sayısıdır: hevesli çatallama, beş sürecin bütün hesap işinden 1,641 kat pahalıdır. Yeni süreç kurmanın maliyeti, o süreçlerin yapacağı işten büyüktür. Yazarken kopyalamada oran 0,3846’ya iner, yani kopyalama işin üçte birinden azını tutar.

Bu oran iş yüküne bağlıdır ve öyle yazılmalıdır: süreç başına on iki adım yerine yüz iki adım olsaydı payda büyür, oran düşerdi. Ölçülen şey çatallamanın mutlak pahalılığı değil, kısa ömürlü süreçlerde kurulum bedelinin işi geçtiğidir.

Yazarken Kopyalama Ne Zaman Kaybeder

Yazarken kopyalama bedava değildir; kopyalamayı ertelemekle birlikte iki yeni kalem ekler. Birincisi, çatallama anında 64 sayfanın salt okunur işaretlenmesidir. İkincisi, ertelenen her kopyanın bir sayfa hatasıyla başlamasıdır: yazma denemesi yakalanır, denetim çekirdeğe geçer, sayfa çıkarılır ve komut yeniden yürütülür. Sayfa hatası bu kursun bellek ve depolama konusunda kendi başına ölçülür; burada yalnız bir bedel parametresidir.

Süpürme, üstünlüğün mutlak olmadığını gösterir. Sayfa hatası 3 zaman birimine kadar yazarken kopyalama önde; 4 zaman biriminde hevesli kopyalama öne geçer ve fark açılarak sürer. Sonuç, kursun ikinci iddiasının bu dersteki karşılığıdır: soyutlama bazen kötüleştirir. Yazarken kopyalamanın kazanması, çocuğun az sayıda sayfaya dokunmasına ve yakalamanın ucuz olmasına birlikte bağlıdır; ikisinden biri bozulunca kazanç yok olur.

Tablonun 3 satırı ayrıca çözünürlüğün nasıl okunacağını gösterir. Orada hevesli 64, yazarken 60 verir; aradaki 4 zaman birimi çözünürlüğün (2 zaman birimi) üstündedir ve sayılır. Fark 1 olsaydı satır ölçülemez yazılırdı, çünkü bu modelde 1 zaman birimlik bir üstünlük bir sonucu değil bir yuvarlamayı ifade eder.

İki uç durum bu bağımlılığı keskinleştirir. Çocuk çatallamadan hemen sonra kendi programını yükleyip adres uzayını tümüyle değiştirirse, hevesli yordamın kopyaladığı 64 sayfanın 64’ü boşa gider. Tersine, çocuk bütün 16 sayfaya yazarsa yazarken kopyalama 64 sayfayı yine kopyalar ve üstüne 64 sayfa hatası ödetir; bu iş yükünde 64 yerine 128 zaman birimi eder.

Özet

• Çatallama, var olan bir süreçten yeni bir süreç türetir ve sürecin durumunu üçe ayırır: kopyalanan adres uzayı, kalıtılan değerler, paylaşılan nesneler.
• Bedeli olan tek davranış kopyalamadır; kalıtım bir değer atamasıdır, paylaşım ise aynı nesneyi göstermektir ve sıfır sayfa tutar.
• Bu ağaçta dört çatallama hevesli yordamla 64 sanal sayfa, yazarken kopyalamayla 15 sanal sayfa taşır; aradaki 49 sayfa boşa kopyalanmıştır.
• Hevesli çatallama, beş sürecin toplam hesap işinin 1,641 katıdır; süreç kurmak, süreçlerin yapacağı işten pahalı olabilir.
• Kalıtım ağaç boyunca zincirlenir: bu ağaçta beş sürecin üç ayrı öncelik düzeyi, kalıtım sonrası tek düzeye iner ve öncelik bakan bir çizelgeleyici için ayırt edilemez olur.
• Sayfa hatası bedeli 4 zaman birimine çıktığında yazarken kopyalama üstünlüğünü yitirir; ertelenmiş kopyalama her koşulda daha ucuz değildir.

Sonraki Adım

Çatallamanın bedeli, yalıtımın bedelidir: iki süreç birbirinin belleğine dokunamasın diye sayfalar çoğaltılır. Yalıtımdan vazgeçilirse bu bedel de ortadan kalkar. Sonraki ders, aynı adres uzayını paylaşan ama kendi yığıtlarını tutan yürütme birimlerini ele alacak ve iki sayıyı karşılaştıracak: aynı işi süreçle ve iş parçacığıyla yapmanın kopyalanan sayfa ve bağlam değiştirme farkı.