Kilitlenme ve Açlık

Önceki ders tek bir kilidin bedelini ölçtü ve sonucu tek bir eksende topladı: bekleme adımı. O eksende kötü bir sayı, yavaş bir programdır. Bu derste ikinci bir arıza türü çıkıyor ve o eksende hiç sayı üretmiyor: kilitlenen bir iş parçacığı yavaşlamaz, durur.

İki kilit yetiyor. Bir iş parçacığı birinci kilidi tutup ikincisini isterken, başka bir iş parçacığı ikinciyi tutup birinciyi isterse ikisi de bir daha ilerlemez. Bu derste bu durumun ne zaman oluştuğu sayılacak, önlemenin yapısal biçimi kurulacak ve önlemenin bedeli ölçülecek.

Dört Koşul

Kilitlenme (deadlock) rastgele oluşmaz. Dört koşul aynı anda sağlandığında oluşur ve herhangi birinin kırılması onu imkânsız kılar.

Karşılıklı dışlama. Kaynak paylaşılamıyor; bir anda tek iş parçacığı tutabiliyor. Bu koşul kaldırılırsa önceki dersin doğruluk güvencesi de gider.

Tut ve bekle. Bir iş parçacığı elindekini bırakmadan yenisini istiyor.

Önalımsızlık. Kilit zorla geri alınamıyor; ancak tutan bırakabiliyor.

Dairesel bekleme. Bekleme ilişkisi bir halka oluşturuyor.

EZ14. Bekleme çizgesinin düğümleri iş parçacıkları, kenarları “tutulan bir kilidi bekleme” ilişkisidir. EZ15. Bir kilidi aynı anda tek iş parçacığı tutar; istenen kilit boştaysa kenar yoktur. EZ16. Her iş parçacığı bir kilit tutar ve başka bir kilit ister; kilit bırakma zorlanamaz, tespit sonrası kurtarma modellenmez.

İlk üç koşul çoğu programda tasarım gereği vardır. Kalan tek hedef dairesel beklemedir ve bu, çizge diliyle tam olarak döngüdür.

Döngü Tespiti Yeni Bir Yordam Değildir

Veri Yapıları kursunun derine arama dersi yönlü çizgede döngü tespitini kurdu ve oradaki ayrım burada aynen geçerlidir: “ziyaret edildi” ile “hâlâ açık” karıştırılmamalıdır. Ortak tanımın dongu_var yordamı bunu üç renkle taşır — 0 hiç görülmedi, 1 hâlâ açık, 2 dalı bitti. Yordam tekrar kurulmaz, doğrudan çağrılır.

Aşağıdaki ölçü önce beş bekleme çizgesini sınıyor, sonra bir durum uzayını tarıyor.

from itertools import permutations, product


def dongu_var(bekleme: dict[str, list[str]]) -> bool:
    """Yonlu cizgede dongu sinamasi. renk 1 = hala acik , renk 2 = dal bitti."""
    renk = {d: 0 for d in bekleme}

    def gez(d):
        renk[d] = 1
        for h in bekleme.get(d, []):
            if renk.get(h, 0) == 1:
                return True
            if renk.get(h, 0) == 0 and gez(h):
                return True
        renk[d] = 2
        return False
    return any(renk[d] == 0 and gez(d) for d in list(bekleme))


for ad, cizge in (("kimse beklemiyor", {"T1": [], "T2": []}),
                  ("zincir T1 -> T2", {"T1": ["T2"], "T2": []}),
                  ("iki dal ortak hedef", {"T1": ["T3"], "T2": ["T3"], "T3": []}),
                  ("halka T1 -> T2 -> T1", {"T1": ["T2"], "T2": ["T1"]}),
                  ("halka T1 -> T2 -> T3", {"T1": ["T2"], "T2": ["T3"], "T3": ["T1"]})):
    print(f"  {ad:22s} kilitlenme {dongu_var(cizge)}")


def tara(kilit_sayisi: int, is_parcacigi: int, sirali: bool) -> tuple[int, int]:
    """Her is parcacigi bir kilidi tutar , baska bir kilidi ister. Butun durumlar."""
    kilitler = list(range(1, kilit_sayisi + 1))
    durum = kilitlenen = 0
    for tutulan in permutations(kilitler, is_parcacigi):
        for istenen in product(kilitler, repeat=is_parcacigi):
            if any(t == i for t, i in zip(tutulan, istenen)):
                continue                        # kendi tuttugu kilidi istemez
            if sirali and any(i < t for t, i in zip(tutulan, istenen)):
                continue                        # sirali edinim: yalniz buyuk numara istenir
            sahip = {k: f"T{j+1}" for j, k in enumerate(tutulan)}
            cizge = {f"T{j+1}": [] for j in range(is_parcacigi)}
            for j, i in enumerate(istenen):
                if i in sahip:                  # istenen kilit bostaysa kenar yoktur
                    cizge[f"T{j+1}"].append(sahip[i])
            durum += 1
            if dongu_var(cizge):
                kilitlenen += 1
    return durum, kilitlenen


print()
print("4 kilit , her is parcacigi bir kilit tutup baska bir kilit istiyor")
print("  is parcacigi  edinim     durum  kilitlenen  kilitlenme orani")
for n in (2, 3, 4):
    for sirali in (False, True):
        d, k = tara(4, n, sirali)
        ad = "sirali " if sirali else "serbest"
        oran = f"{k / d:.4f}" if d else "durum yok"
        print(f"  {n:12d}  {ad}  {d:8d}  {k:10d}  {oran:>16s}")

  kimse beklemiyor       kilitlenme False
  zincir T1 -> T2        kilitlenme False
  iki dal ortak hedef    kilitlenme False
  halka T1 -> T2 -> T1   kilitlenme True
  halka T1 -> T2 -> T3   kilitlenme True

4 kilit , her is parcacigi bir kilit tutup baska bir kilit istiyor
  is parcacigi  edinim     durum  kilitlenen  kilitlenme orani
             2  serbest       108          12            0.1111
             2  sirali         22           0            0.0000
             3  serbest       648         264            0.4074
             3  sirali         36           0            0.0000
             4  serbest      1944        1944            1.0000
             4  sirali          0           0         durum yok

Üçüncü satır ölçünün özüdür: dört kilit ve üç iş parçacığıyla 648 ayrı bekleme durumu kurulabiliyor ve bunların 264’ü kilitli. Oran 0,4074. İkinci dal önemlidir: iki iş parçacığında oran 0,1111 iken üçte 0,4074, dörtte 1,0000 oluyor. Kilitlenme, iş parçacığı eklendikçe istisna olmaktan çıkıp kural hâline geliyor.

Dört iş parçacığının dört kilidi tuttuğu satırdaki 1,0000 rastlantı değil. Her iş parçacığı bir kilit tutup başkasını istediğinde, “kimin kilidini bekliyorum” ilişkisi düğüm başına tek çıkışlı bir çizge kurar; sonlu ve çıkışsız düğüm içermeyen böyle bir çizge her zaman bir halka barındırır.

Tespit ile Önleme Aynı Şey Değildir

Yukarıdaki tarama bir tespit yordamıdır: durum verildiğinde kilitlenmiş olup olmadığını söyler. Çalışan bir sistemde bunu kullanmak üç şey ister. Bekleme çizgesinin sürekli güncel tutulması, çizgenin düzenli aralıklarla taranması ve döngü bulunduğunda bir iş parçacığının geri alınması. Tarama maliyeti Veri Yapıları kursunda ölçüldü ve $O(V + E)$’dir; burada tekrarlanmaz.

Üçüncü adım en pahalısıdır. Geri almak, tutulan kilidi zorla söküp o iş parçacığının yaptığı işi iptal etmek demektir; yani önalımsızlık koşulunun kırılmasıdır ve iptal edilen iş yeniden yapılır. Bu ders o kurtarmayı modellemez (EZ16).

Önleme ise koşum sırasında hiçbir şey ölçmez ve hiçbir şey taramaz. Bedelini tasarım anında öder: kilitlere bir sıra verilir ve bu sıraya her yerde uyulur.

Sıralı Edinim

Tabloda sirali satırlarının hepsinde kilitlenen 0. Bu bir iyileştirme değil, yapısal bir imkânsızlıktır ve gerekçesi tek cümleyle verilebilir.

EZ17. Kilitler sabit bir tam sıraya konur; her iş parçacığı kilitleri yalnız artan numara sırasında ister.

Bir halka olduğunu varsayalım. Halkadaki her iş parçacığı, tuttuğundan büyük numaralı bir kilidi bekliyor demektir. Halka boyunca yürünürse numaralar sürekli artar; ama halka başladığı yere döner ve bir sayı kendinden büyük olamaz. Çelişki. Yani halka yoktur.

Tablo bunu iki ayrı biçimde gösteriyor. Üç iş parçacığında durum uzayı 648’den 36’ya iniyor ve kalan 36 durumun hiçbiri kilitli değil. Dört iş parçacığında sıralı edinim altında hiç durum kalmıyor — o durum kurulamıyor bile.

Buradaki 648’den 36’ya iniş, önlemenin bedelinin nerede olduğunu da söylüyor: ortadan kaldırılan durumların çoğu kilitli değildi. Sıralı edinim yalnız halkaları değil, birçok zararsız bekleme biçimini de yasaklar.

Önlemenin Bedeli

Yasaklanan zararsız durumlar bir yerde ödenir. İkinci kilidi isteyen bir iş parçacığı, sıraya uymak için birinci kilidi erken almak ve elinde tutmak zorundadır; iki ayrı kritik bölge tek bir bölgeye kaynar.

EZ18. Serbest edinimde iki kaynağın iki ayrı kilidi vardır ve aynı anda iki iş parçacığı kritik bölgede olabilir; bu iki izinli bir sayan semaforla aynı sayıyı verir. Sıralı edinimde iki kilit iç içe tutulduğu için kritik bölge tektir.

def kilitli_kosum(is_parcacigi: int, kritik: int, kritik_disi: int, izin: int = 1) -> dict:
    kalan = [{"kritik": kritik, "disi": kritik_disi} for _ in range(is_parcacigi)]
    icerde, t, bekleme, mesgul = [], 0, 0, 0
    while any(k["kritik"] or k["disi"] for k in kalan):
        calisan = 0
        for j, k in enumerate(kalan):
            if k["disi"]:
                k["disi"] -= 1
                calisan += 1
                continue
            if not k["kritik"]:
                continue
            if j in icerde or len(icerde) < izin:
                if j not in icerde:
                    icerde.append(j)
                k["kritik"] -= 1
                calisan += 1
                if not k["kritik"]:
                    icerde.remove(j)
            else:
                bekleme += 1
        mesgul += calisan
        t += 1
    return {"sure": t, "bekleme": bekleme, "mesgul": mesgul,
            "kullanim": round(mesgul / (t * is_parcacigi), 4)}


print("iki kilit , kritik bolge toplam 10 adim , kritik disi 10 adim")
print("  is parcacigi  edinim   izin  sure  bekleme  kullanim")
for n in (2, 4, 8):
    for ad, izin in (("serbest", 2), ("sirali ", 1)):
        k = kilitli_kosum(n, 10, 10, izin)
        print(f"  {n:12d}  {ad}  {izin:4d}  {k['sure']:4d}  {k['bekleme']:7d}"
              f"  {k['kullanim']:8.4f}")
print()
for n in (2, 4, 8):
    s = kilitli_kosum(n, 10, 10, 1)["sure"] - kilitli_kosum(n, 10, 10, 2)["sure"]
    b = kilitli_kosum(n, 10, 10, 1)["bekleme"] - kilitli_kosum(n, 10, 10, 2)["bekleme"]
    print(f"  {n} is parcacigi -> sirali edinimin bedeli: sure +{s} , bekleme +{b}")

iki kilit , kritik bolge toplam 10 adim , kritik disi 10 adim
  is parcacigi  edinim   izin  sure  bekleme  kullanim
             2  serbest     2    20        0    1.0000
             2  sirali      1    29        9    0.6897
             4  serbest     2    29       18    0.6897
             4  sirali      1    47       54    0.4255
             8  serbest     2    47      108    0.4255
             8  sirali      1    83      252    0.2410

  2 is parcacigi -> sirali edinimin bedeli: sure +9 , bekleme +9
  4 is parcacigi -> sirali edinimin bedeli: sure +18 , bekleme +36
  8 is parcacigi -> sirali edinimin bedeli: sure +36 , bekleme +144

Dört iş parçacığında sıralı edinim süreyi 29’dan 47’ye, bekleme adımını 18’den 54’e çıkarıyor. Sekiz iş parçacığında fark daha da açılıyor: süre 47’den 83’e, bekleme 108’den 252’ye. Bedel iş parçacığı sayısıyla büyüyor — +9, +18, +36.

Bu sayılar takas edilecek şeyi net kılar. Sıralı edinim kilitlenme olasılığını 0,4074’ten 0,0000’a indiriyor; karşılığında sekiz iş parçacığında 144 fazla bekleme adımı ödeniyor. Sıfır kilitlenme bir başarım kaybı karşılığında alınır ve bu takas sayılmadan savunulamaz.

Açlık

Kilitlenme, iş parçacıklarının birlikte durmasıdır. Açlık (starvation) ise bir iş parçacığının, sistem çalışmaya devam ederken sırasının hiç gelmemesidir. Kilitlenmenin aksine bekleme çizgesinde döngü yoktur; kilit sürekli veriliyordur, yalnız hep aynılara.

EZ19. İş parçacıkları kritik bölgeyi sürekli ister; kritik olmayan işi bitirir bitirmez yeniden sıraya girer. EZ20. Kilit boşaldığında bekleyenlerden biri seçilir; seçim kuralı ya en küçük numaralı bekleyeni ya da en uzun bekleyeni alır.

def surekli_kosum(is_parcacigi: int, kritik: int, kritik_disi: int,
                  sure: int, adil: bool) -> dict:
    """Kritik bolgeyi surekli isteyen is parcaciklari. Kilit , adil ise en uzun
    bekleyene , degilse en kucuk numarali bekleyene verilir."""
    kalan = [0] * is_parcacigi                 # kritik bolgede kalan adim
    disi = [0] * is_parcacigi                  # kritik olmayan iste kalan adim
    istek = [0] * is_parcacigi                 # ne zamandir bekliyor
    tur = [0] * is_parcacigi                   # kac kez kritik bolgeye girdi
    icerde = None
    for t in range(sure):
        for j in range(is_parcacigi):
            if disi[j]:
                disi[j] -= 1
            elif icerde != j:
                istek[j] += 1
        if icerde is None:
            bekleyen = [j for j in range(is_parcacigi) if not disi[j]]
            if bekleyen:
                sec = max(bekleyen, key=lambda j: istek[j]) if adil else min(bekleyen)
                icerde, kalan[sec], istek[sec] = sec, kritik, 0
                tur[sec] += 1
        if icerde is not None:
            kalan[icerde] -= 1
            if not kalan[icerde]:
                disi[icerde] = kritik_disi
                icerde = None
    return {"tur": tur, "acikta": istek}   # acikta: son istekten beri beklenen adim


print("4 is parcacigi , kritik 10 , kritik disi 10")
print("  sure  secim kurali  tur dagilimi          toplam tur  acikta beklenen")
for sure in (400, 4000):
    for adil in (False, True):
        s = surekli_kosum(4, 10, 10, sure, adil)
        ad = "adil    " if adil else "en kucuk"
        print(f"  {sure:4d}  {ad}      {str(s['tur']):20s}  {sum(s['tur']):10d}"
              f"  {s['acikta']}")

4 is parcacigi , kritik 10 , kritik disi 10
  sure  secim kurali  tur dagilimi          toplam tur  acikta beklenen
   400  en kucuk      [20, 20, 0, 0]                40  [0, 0, 400, 400]
   400  adil          [10, 10, 10, 10]              40  [20, 10, 0, 0]
  4000  en kucuk      [200, 200, 0, 0]             400  [0, 0, 4000, 4000]
  4000  adil          [100, 100, 100, 100]         400  [20, 10, 0, 0]

Dört yüz zaman biriminde kritik bölgeye toplam 40 giriş oluyor — her iki seçim kuralında da. Verim aynı. Dağılım aynı değil: en küçük numaralı bekleyeni seçen kural girişleri [20, 20, 0, 0] biçiminde dağıtıyor. Üçüncü ve dördüncü iş parçacıkları hiç girmiyor ve 400 adım boyunca açıkta bekliyor.

Süre on katına çıkarıldığında sonuç değişmiyor: [200, 200, 0, 0]. Açıkta beklenen adım 400’den 4000’e çıkıyor. Bu, kilitlenmeden farklı bir arızadır ve beklemekle geçmez; sınırı yoktur, süreyle büyür.

Adil seçim kuralı aynı 40 girişi [10, 10, 10, 10] biçiminde dağıtıyor. Toplam verim değişmiyor, yani adalet burada bedava geliyor. Bedava gelmesinin nedeni kritik bölgenin zaten sıralanmış olmasıdır; ödenen bedel önceki derste çoktan ödendi.

Bu ölçünün asıl uyarısı şudur: verim ölçütü açlığı göremez. Toplam tur sayısı iki kuralda da 40’tır; arızayı gören tek şey dağılımdır.

Üç Sayı

Ölçüt	Soyutlamasız taban	Soyutlamalı kurulum	Bedel
Kilitlenen durum	tek kilit, 0	dört kilit, üç iş parçacığı, 264/648	oran 0,4074
Sıralı edinim sonrası	—	0/36	süre +18, bekleme +36
Açlık	tek iş parçacığı, 0	dört iş parçacığı, adaletsiz seçim	2 iş parçacığı, 4000 adım açıkta

Tablonun ikinci satırı kursun kuralını taşır: kilitlenmenin ortadan kalkması bir kazanç değil, bir takastır. Dört iş parçacığında 0,4074’lük kilitlenme oranı sıfırlanıyor ve karşılığında her iş parçacığı daha uzun bekliyor.

Özet

• Kilitlenme dört koşulun aynı anda sağlanmasıyla oluşur; pratikte kırılabilen tek koşul dairesel beklemedir ve bu, bekleme çizgesindeki döngüdür.
• Döngü tespiti yeni bir yordam değildir; Veri Yapıları kursunun derine arama dersinde kurulan üç renkli sınama aynen çağrılır.
• Dört kilit ve üç iş parçacığında 648 bekleme durumunun 264‘ü kilitlidir (0,4074); iş parçacığı sayısı arttıkça oran 0,1111’den 1,0000’e çıkar.
• Sıralı edinim halkayı yapısal olarak imkânsız kılar — durum uzayı 648’den 36’ya iner ve kilitlenen sayısı 0 olur; bedeli sekiz iş parçacığında 144 fazla bekleme adımıdır.
• Açlıkta döngü yoktur ve verim düşmez: 400 zaman biriminde toplam 40 giriş her iki seçim kuralında da aynıdır; arıza yalnız dağılımda görünür.

Sonraki Adım

Buraya kadar ölçülen her şey tek çekirdekte oldu; iş parçacıkları hiçbir zaman gerçekten aynı anda ilerlemedi. Sonraki ders bu kısıtı kaldırır. Çekirdek eklendiğinde süre 197’den 180’e iniyor, ama dördüncü çekirdek 179’da kalıyor ve boş çekirdek adımı 108’den 1355’e çıkıyor. Aynı derste birinci dersin dilim korumasının ne olduğu da görülecek: gerçek paralellikte erişilebilen serpiştirme yeniden 20’ye çıkar ve 18’i yanlış olur.