Süreç Kavramı

Algoritmalar kursu, bir çözümün maliyetini kendi adım sayısıyla ölçerek kapandı: karşılaştırma sayısı, gezilen kenar, taranan karakter. Bu ölçünün sessiz bir varsayımı vardı — algoritma makineyi tek başına kullanıyor. Üretimde bu varsayım tutmaz. Aynı algoritma, aynı makinede başka işlerle birlikte koşar; işlemciyi, belleği ve diski onlarla paylaşır.

Bu kursun ölçtüğü şey paylaşımın kendisidir. Bir soyutlamanın sayısı sağladığı kolaylık değil, ödettiği adımdır; bedeli sayılmayan soyutlama ölçülmemiş sayılır. İlk soyutlama süreçtir ve ilk bedel, bir işlemcinin birden çok süreç arasında gidip gelirken harcadığı adımdır.

• SR1. Makine ders içinde modellenir. Aşağıdaki kod bir benzeticidir: hiçbir gerçek süreç yaratılmaz, hiçbir çekirdek çağrısı yapılmaz, hiçbir gerçek zaman ölçülmez.
• SR2. Bütün süreler zaman birimidir. Saniye değildir ve saniyeye çevrilmez.
• SR3. İş yükü beş süreçtir; her süreç on iki adımlıdır. Bir adım ya bir hesap adımıdır (bir zaman birimi sürer, bir sanal sayfaya dokunur) ya da bir bekleme adımıdır (30 zaman birimi sürer, çekirdeği kullanmaz).
• SR4. Tohum 20260218’dir. Aynı tohum aynı iş yükünü verir; buradaki her sayı yeniden üretilebilir.
• SR5. Makinede tek çekirdek vardır. Her zaman biriminde çekirdek en çok bir adım yürütür.
• SR6. Bağlam değiştirmenin bedeli 2 zaman birimidir. Çekirdek bu iki birimde hiçbir sürecin adımını yürütmez.
• SR7. Adres uzayı, yığıt ve öbek Bilgisayarlar Nasıl Çalışır kursunun bellek düzeni dersinde kurulmuştu; burada yeniden tanımlanmaz, yalnız sayılır.
• SR8. Ölçünün çözünürlüğü 2 zaman birimidir. İki kurulum arasındaki 1 birimlik fark ölçülmemiş sayılır.

Süreç: Yürütülmekte Olan Program

Program diskte duran bir bayt dizisidir; süreç (process), o programın yürütülmekte olan bir örneğidir. Aradaki fark, sürecin programda bulunmayan bir şeye sahip olmasıdır: durum. Bir sürecin durumu, kaldığı adımın sayacını, yığıtının o anki içeriğini, açık tuttuğu tanıtıcıları ve kendi adres uzayını kapsar.

Bu durum bir yerde tutulmak zorundadır, çünkü işlemci bir süreci bırakıp başkasına geçtiğinde geri döndüğünde tam bıraktığı yerden devam etmelidir. Durumun tutulduğu yapı süreç tablosudur (process table): her süreç için bir girdi, her girdide sürecin yeniden başlatılabilmesi için gereken alanlar.

Aynı programdan iki süreç çalıştırıldığında ortaya çıkan şey iki ayrı durumdur. İkisi aynı komutları yürütür, ama farklı adımlarda, farklı verilerle ve birbirinin belleğine dokunmadan. Bu ayrılık yalıtımdır (isolation) ve bu kursun sonraki derslerinde bedeli sayılacaktır.

Bir çok görevli işletim sistemi, tek çekirdekli bir makinede bile birden çok sürecin aynı anda ilerlediği izlenimini verir. İzlenimin kaynağı, çekirdeğin süreçler arasında yeterince sık gidip gelmesidir. Sürecin bakış açısından bu geçişler görünmez: süreç kendi adımlarını kesintisiz yürütüyormuş gibi yazılır. Ölçüm bu izlenimi bozar, çünkü geçişlerin her biri çekirdekte yer kaplar ve toplam süreye eklenir.

Modellenen İş Yükü

İlk blok iş yükünü kurar. Bir süreç, adım listesi olarak temsil edilir; hesap adımları çekirdeği tutar, bekleme adımları tutmaz.

# 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  bekleme  tek basina sure")
for i in ISLER:
    h = sum(1 for t, _ in i["adim"] if t == "HESAP")
    b = ADIM_SAYISI - h
    print(f"  {i['ad']:4s} {i['varis']:5d} {i['oncelik']:8d} {h:6d} {b:8d}"
          f" {h + b * BEKLEME_SURESI:15d}")
print("toplam hesap adimi:", sum(1 for i in ISLER for t, _ in i["adim"] if t == "HESAP"))

surec  varis  oncelik  hesap  bekleme  tek basina sure
  S1       0        3      9        3              99
  S2       4        2      9        3              99
  S3       8        1      7        5             157
  S4      12        3      7        5             157
  S5      16        2      7        5             157
toplam hesap adimi: 39

Son sütun tabandır: bir süreç makinede yalnız olsaydı ne kadar sürerdi. S1 için bu $9 + 3 \times 30 = 99$ zaman birimidir. Sayı, sürecin kendi adımlarının toplamıdır ve başka hiçbir şeye bağlı değildir. Algoritmalar kursunun ölçüsü tam olarak budur.

Paylaşımın Kendisi Bir İş

Beş süreç aynı çekirdeği kullandığında çekirdek bir seçim yapmak zorundadır: hangisi koşacak. Bu seçimi yapan bileşen çizelgeleyicidir (scheduler). Aşağıdaki gerçeklenim bu kursun bütün çizelgeleme ölçümlerinde kullanılacak; burada yalnız önalımsız sıra kipiyle koşar, yani bir süreç ya bitene ya da bir bekleme adımına girene kadar çekirdeği bırakmaz.

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


TEK = [cizelgele([dict(i, varis=0)], "sirayla") for i in ISLER]
PAY = cizelgele(ISLER, "sirayla")
print("taban  (bes surec pesi sira, hic paylasim yok):",
      sum(s["sure"] for s in TEK), "zaman birimi,",
      sum(s["baglam"] for s in TEK), "baglam degistirme")
print("kurulum(bes surec ayni makineyi paylasiyor)   :",
      PAY["sure"], "zaman birimi,", PAY["baglam"], "baglam degistirme")
print()
print("surec  tek basina  paylasimli  fark")
for i, s in zip(ISLER, TEK):
    p = PAY["bitis"][i["ad"]] - i["varis"]
    print(f"  {i['ad']:4s} {s['sure']:10d} {p:11d} {p - s['sure']:5d}")
print("ortalama tamamlanma:", PAY["ortalama_tamamlanma"],
      "| ortalama bekleme:", PAY["ortalama_bekleme"])

taban  (bes surec pesi sira, hic paylasim yok): 669 zaman birimi, 0 baglam degistirme
kurulum(bes surec ayni makineyi paylasiyor)   : 194 zaman birimi, 22 baglam degistirme

surec  tek basina  paylasimli  fark
  S1           99         103     4
  S2           99         112    13
  S3          157         176    19
  S4          157         173    16
  S5          157         178    21
ortalama tamamlanma: 148.4 | ortalama bekleme: 14.6

İki sayı aynı anda doğrudur ve ters yöne bakar. Toplam süre düşer: beş süreci peş peşe, hiç iç içe geçirmeden koşturmak 669 zaman birimi alırken paylaşımlı koşum 194’te biter. Kazanç, bir süreç beklerken çekirdeğin bir başkasına verilmesinden gelir. Tekil süre yükselir: hiçbir süreç kendi tabanına ulaşamaz; S5 için 157 olan taban 178’e çıkar. Fark, süreç başına ortalama 14,60 zaman birimidir ve bu, sürecin kendi işiyle değil, başkalarının işiyle geçirdiği süredir.

Bir Sürecin Üç Durumu

Yukarıdaki fark sütunu bir soru bırakır: bir süreç, kendi işini yapmadığı o fazladan zaman birimlerinde ne yapıyor. Yanıt, sürecin her an üç durumdan birinde olmasıdır. Çalışıyor, çekirdeği o an sürecin tuttuğu durumdur. Engellenmiş, sürecin bir bekleme adımında olduğu ve çekirdek boşta olsa bile koşamayacağı durumdur. Hazır, sürecin koşabilecek durumda olduğu ama çekirdeğin bir başkasında olduğu durumdur.

# Onceki bloklarin uzerine: ISLER, PAY ve BEKLEME_SURESI oradan gelir.
print("surec  calisiyor  engellenmis  hazir(kuyrukta)  tamamlanma")
toplam_hazir = 0
for i in ISLER:
    calisiyor = sum(1 for t, _ in i["adim"] if t == "HESAP")
    engellenmis = sum(v for t, v in i["adim"] if t == "BEKLE")
    tamamlanma = PAY["bitis"][i["ad"]] - i["varis"]
    hazir = tamamlanma - calisiyor - engellenmis
    toplam_hazir += hazir
    print(f"  {i['ad']:4s} {calisiyor:10d} {engellenmis:12d} {hazir:16d} {tamamlanma:11d}")
print("ortalama hazir sure:", round(toplam_hazir / len(ISLER), 2))

surec  calisiyor  engellenmis  hazir(kuyrukta)  tamamlanma
  S1            9           90                4         103
  S2            9           90               13         112
  S3            7          150               19         176
  S4            7          150               16         173
  S5            7          150               21         178
ortalama hazir sure: 14.6

İlk iki sütun tabana aittir ve paylaşımdan etkilenmez: bir sürecin hesap adımı sayısı da bekleme süresi de kendi programının özelliğidir. Paylaşımın ürettiği sütun üçüncüsüdür. Hazır süre, tek başına koşan bir süreçte tanım gereği sıfırdır; beş süreç paylaşınca 4 ile 21 arasında bir değere çıkar ve ortalaması 14,60 zaman birimi olur.

Bu, süreç soyutlamasının ödettiği adımın süreç tarafından görülen biçimidir. Sürecin kendisi ne bağlam değiştirmeyi görür ne de süreç tablosunu; gördüğü tek şey, yürütülmesinin arada bir durup beklemesidir. S1’in hazır süresi 4, S5’inki 21; aradaki fark varış sırasından gelir ve erken gelen az bekler. Bu sıranın bir seçim olduğu ve farklı seçimlerin farklı hazır süreler ürettiği, konunun çizelgeleme dersinde ölçülecek.

194 Zaman Biriminin Dağılımı

Bedelin nerede olduğunu görmek için toplam süreyi bileşenlerine ayırmak gerekir. Süreç tablosunun kendisi de burada sayılır; tanımı Bilgisayarlar Nasıl Çalışır kursuna aittir, buradaki soru kaç alan taşındığıdır.

# Ilk iki blogun uzerine: ISLER, PAY ve BAGLAM_BEDELI oradan gelir.
ALAN = ("ad", "adim", "yer", "varis", "hazir", "kullanim", "bitis", "oncelik", "bekleme")
print("surec tablosu:", len(ISLER), "girdi x", len(ALAN), "alan =",
      len(ISLER) * len(ALAN), "alan")
print()
is_adimi = PAY["toplam_is"]
baglam_adimi = PAY["baglam"] * BAGLAM_BEDELI
print("194 zaman biriminin dagilimi")
print("  hesap adimi        :", is_adimi)
print("  baglam degistirme  :", baglam_adimi, f"({PAY['baglam']} x {BAGLAM_BEDELI})")
print("  bos cekirdek adimi :", PAY["bos_cekirdek_adimi"])
print("  toplam             :", is_adimi + baglam_adimi + PAY["bos_cekirdek_adimi"])
print("  baglam / hesap orani:", round(baglam_adimi / is_adimi, 4))

surec tablosu: 5 girdi x 9 alan = 45 alan

194 zaman biriminin dagilimi
  hesap adimi        : 39
  baglam degistirme  : 44 (22 x 2)
  bos cekirdek adimi : 111
  toplam             : 194
  baglam / hesap orani: 1.1282

Bu dersin en önemli satırı sondan ikincisidir. Beş sürecin gerçek işi 39 zaman birimidir; bu işi yaptırabilmek için harcanan bağlam değiştirme 44 zaman birimidir. Soyutlamanın ödettiği adım, soyutlamanın taşıdığı adımdan daha büyüktür — oran 1,1282.

Kalan 111 birim boş çekirdek adımıdır: bütün süreçler bekleme adımındayken çekirdeğin yapacak işi yoktur. Bu, çizelgeleyicinin kusuru değildir; iş yükünün 21 bekleme adımı toplam 630 zaman birimi tutar ve bunların yalnız bir bölümü iç içe geçirilebilir. Boş adımı düşürmenin yolu daha iyi bir çizelgeleyici değil, daha çok süreçtir — ve her yeni süreç bağlam değiştirme sayısını da artırır.

Süreç tablosunun 45 alanı, bağlam değiştirmenin neden bedava olmadığının nedenidir: her geçişte bir girdinin alanları saklanır, bir başkasınınki geri yüklenir. Bu kursun sayacı, o iki işi 2 zaman birimi olarak modeller.

Özet

• Süreç, bir programın yürütülmekte olan örneğidir; programdan farkı taşıdığı durumdur ve bu durum süreç tablosunda tutulur.
• Bu iş yükünde tek başına koşan bir süreç kendi adımı kadar sürer: S1 için 99, S3 için 157 zaman birimi. Bu tabandır.
• Beş süreç aynı makineyi paylaştığında toplam süre 669’dan 194 zaman birimine iner, ama hiçbir sürecin tekil süresi tabanına ulaşmaz; ortalama bekleme 14,60 zaman birimidir.
• Paylaşımın bedeli 22 bağlam değiştirmedir ve bu 44 zaman birimi tutar; iş yükünün gerçek işi olan 39 zaman biriminden fazladır.
• Bir süreç her an çalışıyor, engellenmiş ya da hazır durumdadır; paylaşımın ürettiği tek yeni durum hazırdır ve bu iş yükünde ortalama 14,60 zaman birimi tutar.
• 194 zaman birimi tam olarak 39 hesap adımı, 44 bağlam adımı ve 111 boş çekirdek adımına ayrışır; her soyutlamanın bedeli bu ayrışmada görünür.

Sonraki Adım

Bu derste beş süreç hazır verildi. Gerçek bir makinede süreçler yoktan var olmaz: her biri başka bir süreç tarafından yaratılır ve yaratılırken yaratıcısından bir şeyler devralır. Sonraki ders çatallamayı ele alacak ve tek bir soruyu sayacak: yeni bir süreç kurmak, kaç sayfanın kopyalanması demektir.