Yarış Koşulları

Önceki ders çizelgeleyicinin bedelini süreyle ölçtü: dilim küçüldükçe bağlam değiştirme artıyor, süre uzuyordu. Orada dilim bir başarım ayarıydı. Bu derste aynı ayarın ikinci bir yüzü çıkıyor — dilim, iki iş parçacığının adımlarının hangi sıralarda birbirine girebileceğini de belirler, dolayısıyla programın doğru sonuç verip vermeyeceğini de belirler.

Kurs bu noktada kendi en değerli iddiasını ödemek zorundadır: doğru çıktı doğru program demek değildir. Aşağıdaki ölçü bunu bir kez ve sayıyla gösteriyor. Ölçülen makine yine ortak tanımın makinesidir; hiçbir gerçek iş parçacığı yaratılmaz, gerçek zaman ölçülmez.

Bir Artırma Üç Adımdır

Paylaşılan bir sayacı bir artırmak, kaynak metinde tek satırdır. Yürütmede tek adım değildir: değer okunur, bir artırılır, geri yazılır. Üç adımın arasında çizelgeleyici başka bir iş parçacığına geçebilir.

EZ1. Sayaç artırımı üç ayrı adımdır; adımların arası bölünebilir. EZ2. İki iş parçacığı vardır, her biri sayacı bir kez artırır; beklenen sonuç 2’dir. EZ3. Okuma ve yazma anlıktır; iki adım aynı zaman biriminde çakışmaz. Yürütme her zaman bir serpiştirme (interleaving) ile, yani iki adım dizisinin tek bir sıralamasıyla tarif edilebilir.

Ortak tanımın sayac_kosumu yordamı bir serpiştirmeyi alır ve o serpiştirmenin ürettiği sayacı döndürür. Serpiştirme, hangi adımda hangi iş parçacığının ilerlediğini gösteren bir 0/1 dizisidir.

def sayac_kosumu(desen: list[int]) -> int:
    """Iki is parcacigi birer kez oku-artir-yaz yapar. desen: hangi adimda kim ilerledi."""
    sayac, yerel = 0, {0: None, 1: None}
    asama = {0: 0, 1: 0}
    for kim in desen:
        a = asama[kim]
        if a == 0:
            yerel[kim] = sayac              # oku
        elif a == 1:
            yerel[kim] = yerel[kim] + 1     # artir
        else:
            sayac = yerel[kim]              # yaz
        asama[kim] = a + 1
    return sayac


def serpistirmeler(a: int, b: int) -> list[list[int]]:
    """a ve b adimlik iki dizinin butun serpistirmeleri."""
    if a == 0:
        return [[1] * b]
    if b == 0:
        return [[0] * a]
    sol = [[0] + s for s in serpistirmeler(a - 1, b)]
    sag = [[1] + s for s in serpistirmeler(a, b - 1)]
    return sol + sag


for ad, desen in (("sirali", [0, 0, 0, 1, 1, 1]),
                  ("tam serpisik", [0, 1, 0, 1, 0, 1]),
                  ("kismi", [0, 0, 1, 1, 1, 0])):
    print(f"{ad:13s} {desen} -> sayac {sayac_kosumu(desen)}")

hepsi = serpistirmeler(3, 3)
dogru = [d for d in hepsi if sayac_kosumu(d) == 2]
yanlis = len(hepsi) - len(dogru)
print()
print(f"serpistirme {len(hepsi)} | dogru {len(dogru)} | yanlis {yanlis} "
      f"| yanlis orani {yanlis / len(hepsi):.4f}")
print("dogru olanlar:", dogru)

sirali        [0, 0, 0, 1, 1, 1] -> sayac 2
tam serpisik  [0, 1, 0, 1, 0, 1] -> sayac 1
kismi         [0, 0, 1, 1, 1, 0] -> sayac 1

serpistirme 20 | dogru 2 | yanlis 18 | yanlis orani 0.9000
dogru olanlar: [[0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 0]]

Üç adımlık iki dizinin 20 serpiştirmesi var. Bunların yalnız 2’si beklenen sonucu üretiyor; 18‘i, yani yürütme sıralarının yüzde doksanı, sayacı 1’de bırakıyor. Doğru sonucu veren iki serpiştirme de zaten aynı şeyi söylüyor: biri tümüyle bitmeden diğeri başlamamış.

Kayıp Nerede Oluşuyor

[0, 1, 0, 1, 0, 1] serpiştirmesini adım adım izlemek yeter. Birinci iş parçacığı sayacı okur ve 0 görür. İkinci iş parçacığı da okur ve yine 0 görür — birincinin yazması henüz olmadı. İkisi de kendi yerel kopyasını 1 yapar. Birinci yazar, sayaç 1 olur; ikinci yazar, sayaç yine 1 olur. İkinci yazma, birincinin sonucunu üzerine yazdı.

Buna yarış koşulu (race condition) denir: sonucun, işin kendisine değil adımların sırasına bağlı olması. Adımların sırasını program yazan seçmez; çizelgeleyici seçer. Bu nedenle yarış koşulu, kaynak metne bakarak görülemeyen bir hatadır — kaynak metinde yalnızca bir artırma satırı vardır ve o satır doğrudur.

Sayacın bozulduğu bölge, kritik bölge (critical section) olarak adlandırılır: iki iş parçacığının aynı anda içinde bulunmaması gereken adım dizisi. Burada kritik bölge üç adımdır.

İki Ayrı Kusur

Yukarıdaki durum iki kusuru üst üste taşır ve ikisi karıştırılmamalıdır.

Veri yarışı (data race), aynı bellek konumuna iki erişimin sıralanmamış olması ve en az birinin yazma olmasıdır. Yapısal bir özelliktir: erişimlere bakarak, sonuca bakmadan saptanır. Yarış koşulu ise sonucun adım sırasına bağlı olmasıdır; bir doğruluk özelliğidir.

Sayaç örneğinde ikisi birden var. Ama biri diğerini gerektirmez. Bir kap her erişimde kilitleniyorsa veri yarışı yoktur; buna karşın “boş mu diye bak, boş değilse bir eleman al” dizisi iki ayrı kilitli işlemden oluşuyorsa, ikisinin arasında başka bir iş parçacığı son elemanı alabilir ve sonuç yine sıraya bağlı kalır. Veri yarışı ortadan kalkmış, yarış koşulu durmaktadır.

Bu ayrımın pratik sonucu şudur: her erişimi ayrı ayrı korumak yetmez. Korunması gereken şey erişim değil, değişmezin ihlal edildiği aralıktır — yani kritik bölgenin sınırını program yazan çizer, araç değil.

Dilim Serpiştirmeyi Kısıtlar

Önceki dersin çizelgeleyicisi iş parçacıklarını her adımda değiştirmez; dilim boyunca tutar, dilim dolunca bırakır. O hâlde 20 serpiştirmenin hepsi erişilebilir değildir.

EZ4. Çizelgeleyici yalnız dilim sınırında geçiş yapar; dilim içinde önalım yoktur. EZ5. Ölçülen şey bir olasılık değil, bir serpiştirmenin erişilebilir olup olmadığıdır: o serpiştirme ya bu çizelgeleyiciyle üretilebilir ya da üretilemez.

Ortak tanımın dilimli_serpistirmeler yordamı, verilen dilimle üretilebilen serpiştirmeleri sayar.

def sayac_kosumu(desen: list[int]) -> int:
    sayac, yerel = 0, {0: None, 1: None}
    asama = {0: 0, 1: 0}
    for kim in desen:
        a = asama[kim]
        if a == 0:
            yerel[kim] = sayac
        elif a == 1:
            yerel[kim] = yerel[kim] + 1
        else:
            sayac = yerel[kim]
        asama[kim] = a + 1
    return sayac


def dilimli_serpistirmeler(adim: int, dilim: int) -> list[list[int]]:
    """Cizelgeleyici ancak `dilim` adimda bir gecis yapiyorsa erisilebilen serpistirmeler."""
    sonuc = []

    def gez(kalan_a, kalan_b, kim, dizi):
        if not kalan_a and not kalan_b:
            sonuc.append(list(dizi))
            return
        for yeni in (0, 1):
            kalan = kalan_a if yeni == 0 else kalan_b
            if not kalan:
                continue
            n = min(dilim, kalan) if yeni != kim else min(dilim, kalan)
            dizi.extend([yeni] * n)
            gez(kalan_a - n if yeni == 0 else kalan_a,
                kalan_b - n if yeni == 1 else kalan_b, yeni, dizi)
            del dizi[len(dizi) - n:]
    gez(adim, adim, None, [])
    ayri = []
    for d in sonuc:
        if d not in ayri:
            ayri.append(d)
    return ayri


print("dilim  erisilebilen  yanlis  yanlis orani")
for dilim in (1, 2, 3, 4, 5):
    erisilebilen = dilimli_serpistirmeler(3, dilim)
    yanlis = sum(1 for d in erisilebilen if sayac_kosumu(d) != 2)
    print(f"  {dilim:3d}  {len(erisilebilen):11d}  {yanlis:6d}  "
          f"{yanlis / len(erisilebilen):11.4f}")
print()
print("dilim 2 erisilebilenler:")
for d in dilimli_serpistirmeler(3, 2):
    print("  ", d, "-> sayac", sayac_kosumu(d))
print("dilim 3 erisilebilenler:")
for d in dilimli_serpistirmeler(3, 3):
    print("  ", d, "-> sayac", sayac_kosumu(d))

dilim  erisilebilen  yanlis  yanlis orani
    1           20      18       0.9000
    2            6       4       0.6667
    3            2       0       0.0000
    4            2       0       0.0000
    5            2       0       0.0000

dilim 2 erisilebilenler:
   [0, 0, 0, 1, 1, 1] -> sayac 2
   [0, 0, 1, 1, 0, 1] -> sayac 1
   [0, 0, 1, 1, 1, 0] -> sayac 1
   [1, 1, 0, 0, 0, 1] -> sayac 1
   [1, 1, 0, 0, 1, 0] -> sayac 1
   [1, 1, 1, 0, 0, 0] -> sayac 2
dilim 3 erisilebilenler:
   [0, 0, 0, 1, 1, 1] -> sayac 2
   [1, 1, 1, 0, 0, 0] -> sayac 2

Dilim 1’de çizelgeleyici her adımda geçiş yapabiliyor ve 20 serpiştirmenin tamamı erişilebilir; yanlış oran 0,9000. Dilim 2’de erişilebilen serpiştirme 6‘ya iniyor, yanlış 4, oran 0,6667. Dilim 3’te erişilebilen serpiştirme 2’ye iniyor ve hiçbiri yanlış değil.

Hata Yok Olmadı, Görünmez Oldu

Dilim 3’te kalan iki serpiştirme, [0, 0, 0, 1, 1, 1] ile [1, 1, 1, 0, 0, 0]. İkisi de bir iş parçacığının üç adımını kesintisiz yürütüyor. Dilim, kritik bölgeden büyük ya da eşit olduğu için hiçbir geçiş kritik bölgenin ortasına düşemiyor.

Bu sonucun okunma biçimi kursun ayırt edici noktasıdır. Program değişmedi: sayaç hâlâ korumasız, artırma hâlâ üç adım, kritik bölge hâlâ açık. Değişen tek şey çizelgeleyicinin ayarı. Dilim 3 ile bin kez koşulsa bin kez 2 yazacaktı; bu koşumlar programın doğru olduğuna dair hiçbir kanıt üretmez, yalnız hatanın o ayarda erişilemez olduğunu gösterir.

Ayar bir güvence değildir. Dilim 2’ye inildiğinde yanlış sonuç anında geri gelir: 6 serpiştirmenin 4’ü bozuktur. Kritik bölge üç adımdan dörde çıktığında dilim 3 de yetmez. Ve bir sonraki dersin konusu olan çekirdek eklendiğinde dilim koruması tümüyle ortadan kalkar — çünkü iki iş parçacığı gerçekten aynı anda ilerler.

Buradan çıkan kural şudur: bir eşzamanlılık hatasının varlığı çıktıyla değil, erişilebilen serpiştirme kümesiyle sınanır. Çıktı bir örneklemdir; küme bir kanıttır.

Koşum Sayısı Kanıt Değildir

Dilim, geçişi yasaklamanın tek yolu değil; seyrekleştirmek de aynı sonucu üretir. Gerçek bir kritik bölge birkaç adımdır, gerçek bir dilim ise binlerce adım; geçişin tam o birkaç adıma denk gelme olasılığı küçüktür. Küçük olması yok olması değildir, ama gözlemi yok eder.

EZ6. Geçiş olasılığı adım başınadır ve koşum boyunca sabittir; örneklem, erişilebilen kümeyi değil o kümenin ziyaret sıklığını değiştirir.

Aşağıdaki ölçü bunu sayar. Çizelgeleyici her adımda belirli bir olasılıkla öbür iş parçacığına geçiyor; iki bin koşum yapılıyor ve yanlış sonuç sayılıyor. Üreteç ortak tanımın üreteci, tohum aynı tohumdur; sonuç belirlenimcidir.

TOHUM = 20260218


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 sayac_kosumu(desen: list[int]) -> int:
    sayac, yerel = 0, {0: None, 1: None}
    asama = {0: 0, 1: 0}
    for kim in desen:
        a = asama[kim]
        if a == 0:
            yerel[kim] = sayac
        elif a == 1:
            yerel[kim] = yerel[kim] + 1
        else:
            sayac = yerel[kim]
        asama[kim] = a + 1
    return sayac


def ornek_kosum(r, onbinde: int) -> list[int]:
    """Cizelgeleyici her adimda `onbinde` olasilikla obur is parcacigina gecer."""
    kalan, kim, desen = {0: 3, 1: 3}, 0, []
    while kalan[0] or kalan[1]:
        if not kalan[kim] or (kalan[1 - kim] and r(10000) < onbinde):
            kim = 1 - kim
        desen.append(kim)
        kalan[kim] -= 1
    return desen


print("gecis olasiligi  kosum  yanlis  gozlenen yanlis orani")
for onbinde in (5000, 1000, 100, 10, 1):
    r = uretec(TOHUM)
    yanlis = sum(1 for _ in range(2000) if sayac_kosumu(ornek_kosum(r, onbinde)) != 2)
    print(f"  onbinde {onbinde:6d}   2000  {yanlis:6d}  {yanlis / 2000:21.4f}")

gecis olasiligi  kosum  yanlis  gozlenen yanlis orani
  onbinde   5000   2000    1519                 0.7595
  onbinde   1000   2000     346                 0.1730
  onbinde    100   2000      40                 0.0200
  onbinde     10   2000       1                 0.0005
  onbinde      1   2000       0                 0.0000

Son satır dersin cümlesidir: iki bin koşumun iki bininde sayaç 2 çıkıyor ve program yanlış. Aradaki satırlar da aynı derecede öğreticidir — on binde on olasılıkta iki bin koşumda yalnız 1 yanlış görülüyor. Bu tek gözlemi yakalayan bir sınama, tekrar çalıştırıldığında büyük olasılıkla temiz sonuç verecek ve hata “düzeldi” sayılacaktır.

Erişilebilen serpiştirme kümesi bu beş satırın hiçbirinde değişmedi: 20 serpiştirme, 18’i yanlış. Değişen yalnız örneklemin bu kümeyi ne sıklıkla ziyaret ettiğidir. Koşum sayısını artırmak bir çözüm değildir; on binde bir olasılıkta hatayı beklenen değerle görmek için yüz binlerce koşum gerekir ve o sayı da kanıt üretmez, yalnız gözlem üretir.

Üç Sayı

Ölçüt	Soyutlamasız taban	Soyutlamalı kurulum	Bedel
Yürütme sırası	tek iş parçacığı, 1 sıra	iki iş parçacığı, 20 serpiştirme	19 ek sıra
Yanlış sonuç	0	18	18 bozuk yürütme
Yanlış oranı	0,0000	0,9000	—

Dördüncü bir satır, dilim ayarının ne yaptığını gösterir: dilim 3’te erişilebilen serpiştirme 2, yanlış 0, oran 0,0000. Bu satır tabloya düzeltme olarak değil, görünürlük ölçüsü olarak girer. Hatanın kendisi hâlâ 18 serpiştirmede duruyor; yalnız o serpiştirmelere bu ayarla ulaşılamıyor.

Doğru Çözüm Ayar Değil, Dışlama

Yarış koşulunu ortadan kaldıran şey çizelgeleyicinin nasıl ayarlandığı olamaz, çünkü çizelgeleyici programın denetimi altında değildir. Ortadan kaldıran şey karşılıklı dışlamadır (mutual exclusion): kritik bölgenin, herhangi bir anda en çok bir iş parçacığını içine alacak biçimde korunması.

Ortak tanımın sayac_kosumu yordamı bunu bir seçenekle taşır: kilit=True verildiğinde kritik bölge bölünemez sayılır ve yordam serpiştirmeden bağımsız olarak 2 döndürür. Yirmi serpiştirmenin yirmisi de doğru olur. Kazanılan şey, erişilebilen serpiştirme kümesini daraltmak değil, kümedeki her serpiştirmeyi doğru kılmaktır.

Bunun bir bedeli vardır ve o bedel sonraki dersin ölçüsüdür: kritik bölge sıraya girdiğinde iş parçacıkları birbirini bekler, bekleme adımı birikir ve işlemci kullanımı düşer.

Özet

• Paylaşılan bir sayacın artırılması oku-artır-yaz olmak üzere üç adımdır; adımların arası bölünebilir ve bölündüğünde bir yazma diğerinin üzerine yazar.
• İki iş parçacığının üçer adımının 20 serpiştirmesi vardır; 18’i yanlış sonuç verir, yanlış oranı 0,9000.
• Çizelgeleyici dilimi erişilebilen serpiştirme kümesini daraltır: dilim 1’de 20, dilim 2’de 6, dilim 3’te 2 serpiştirme erişilebilir.
• Dilim kritik bölgeden büyük ya da eşitken erişilebilen serpiştirmelerin hiçbiri yanlış değildir; program değişmemiştir, yalnız hata erişilemez olmuştur.
• Bir eşzamanlılık hatası çıktıyla sınanamaz; sınama, erişilebilen serpiştirme kümesi üzerinden yapılır.

Sonraki Adım

Bu ders sorunu kurdu ve çözümün adını koydu: karşılıklı dışlama. Sonraki ders çözümü kurar ve bedelini sayar. Kritik bölgesi 10, kritik olmayan işi 10 adım olan iş parçacıkları dışlama kilidi altında koşturulacak; tek iş parçacığının 20 zaman birimi, ikincisiyle 29, dördüncüsüyle 47, sekizincisiyle 83 olduğu ve bekleme adımının sıfırdan 252’ye çıktığı gösterilecek. Sayan semaforun bu sayıyı nasıl düşürdüğü ve düşürürken neyi gevşettiği de aynı tabloda durur.