Kilitler, Dışlama Kilitleri ve Sayan Semaforlar

Önceki ders yarış koşulunu kurdu ve çözümün adını koydu: karşılıklı dışlama. Adı koymak bedava, uygulamak değil. Bu ders önce dışlamanın gerçekten işe yaradığını gösterir, sonra ne kadar tuttuğunu sayar.

Ölçünün eksenini baştan söylemek gerekir. Kilit, bir programı hızlandırmaz; hiçbir işi ortadan kaldırmaz, hiçbir adımı kısaltmaz. Yaptığı tek şey, bazı iş parçacıklarını bekletmektir. O hâlde bedeli de tek bir birimde ölçülür: bekleme adımı.

Kilit Neyi Güvence Altına Alıyor

Kilit (lock), bir kritik bölgeye giriş hakkını taşıyan nesnedir. Aynı anda tek bir iş parçacığına verilebilen kilide dışlama kilidi (mutex) denir; adı doğrudan sağladığı güvenceden gelir.

Ortak tanımın sayac_kosumu yordamı bu güvenceyi bir seçenekle taşır: kilit=True verildiğinde kritik bölge bölünemez sayılır. Aşağıdaki ölçü, önceki dersin 20 serpiştirmesini iki kez süpürüyor.

def sayac_kosumu(desen: list[int], kilit: bool = False) -> int:
    """kilit=True ise kritik bolge bolunemez sayilir."""
    if kilit:
        return 2
    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 serpistirmeler(a: int, b: int) -> list[list[int]]:
    if a == 0:
        return [[1] * b]
    if b == 0:
        return [[0] * a]
    return ([[0] + s for s in serpistirmeler(a - 1, b)]
            + [[1] + s for s in serpistirmeler(a, b - 1)])


hepsi = serpistirmeler(3, 3)
for kilit in (False, True):
    sonuc = [sayac_kosumu(d, kilit) for d in hepsi]
    yanlis = sum(1 for s in sonuc if s != 2)
    print(f"kilit {str(kilit):5s} | serpistirme {len(hepsi):2d} | ayri sonuc {sorted(set(sonuc))}"
          f" | yanlis {yanlis:2d} | yanlis orani {yanlis / len(hepsi):.4f}")

kilit False | serpistirme 20 | ayri sonuc [1, 2] | yanlis 18 | yanlis orani 0.9000
kilit True  | serpistirme 20 | ayri sonuc [2] | yanlis  0 | yanlis orani 0.0000

Fark, önceki dersteki dilim ayarının yaptığından türce başkadır. Dilim, erişilebilen serpiştirme kümesini 20’den 2’ye daraltıyordu; kilit kümeyi daraltmıyor, kümedeki yirmi serpiştirmenin yirmisini de doğru kılıyor. Ayrı sonuç kümesi [1, 2] iken [2] oluyor. Doğruluk artık çizelgeleyicinin ayarına bağlı değil.

Çekişmeyi Ölçmek

Kazanç sayıldı; şimdi bedel. Ortak tanımın kilitli_kosum yordamı, her biri bir kritik bölge ve bir kritik olmayan iş taşıyan iş parçacıklarını koşturur ve üç sayı döndürür: süre, bekleme adımı, işlemci kullanımı.

EZ7. Kilit edinme ve bırakma bedava sayılır; ölçülen yalnız bekleme adımıdır. EZ8. Her iş parçacığı 10 adım kritik bölge ve 10 adım kritik olmayan iş taşır. EZ9. Kritik olmayan iş tümüyle paraleldir; çekirdek sayısı burada sınırlayıcı değildir. EZ10. Bekleyen iş parçacığı çekirdeği tutmaz; bekleme adımı sayılır ama meşgul sayılmaz. EZ11. Kilit sırası adildir; hiçbir iş parçacığı süresiz dışarıda kalmaz.

Aynı kritik bölgeye giren iş parçacığı sayısının artmasına çekişme (contention) denir. Süpürme çekişmeyi 1’den 16’ya çıkarıyor.

def kilitli_kosum(is_parcacigi: int, kritik: int, kritik_disi: int, izin: int = 1) -> dict:
    """Her is parcacigi `kritik` uzunlukta bir kritik bolge ile `kritik_disi` adim
    kritik olmayan is yapar. izin=1 dislama kilidi , izin>1 sayan semafordur."""
    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"]:                             # kritik olmayan is paraleldir
                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("dislama kilidi (izin 1), kritik 10 , kritik disi 10")
print("  is parcacigi  sure  bekleme  kullanim  bekleme/(n*(n-1))")
for n in (1, 2, 3, 4, 6, 8, 12, 16):
    k = kilitli_kosum(n, 10, 10, 1)
    oran = "-" if n == 1 else f"{k['bekleme'] / (n * (n - 1)):.1f}"
    print(f"  {n:12d}  {k['sure']:4d}  {k['bekleme']:7d}  {k['kullanim']:8.4f}  {oran:>17s}")

dislama kilidi (izin 1), kritik 10 , kritik disi 10
  is parcacigi  sure  bekleme  kullanim  bekleme/(n*(n-1))
             1    20        0    1.0000                  -
             2    29        9    0.6897                4.5
             3    38       27    0.5263                4.5
             4    47       54    0.4255                4.5
             6    65      135    0.3077                4.5
             8    83      252    0.2410                4.5
            12   119      594    0.1681                4.5
            16   155     1080    0.1290                4.5

Tek iş parçacığı işini 20 zaman biriminde bitiriyor, bekleme adımı 0, kullanım 1,0000. İkincisi eklendiğinde süre 29 oluyor. Dördüncüde 47, sekizincide 83, on altıncıda 155.

Bu, kursun ikinci iddiasının en yalın hâlidir: ikinci iş parçacığı işi yavaşlatır. İki iş parçacığı toplamda 40 adımlık iş taşıyor ve tek iş parçacığının 20 adımını 29 zaman biriminde bitiriyor; kritik bölgeler sıraya girdiği için hiçbir hızlanma yok, yalnız 9 zaman birimlik gecikme var.

Süre Doğrusal, Bekleme İkinci Dereceden

İki sütunun büyüme hızı aynı değildir ve fark ölçülebilir.

Süre sütunu doğrusaldır: her iş parçacığı 9 zaman birimi ekliyor. Kritik bölgeler sıraya girdiği için toplam süre, sıralanan kritik bölgelerin toplamına yaklaşıyor.

Bekleme sütunu ikinci derecedendir. Son sütun bunu doğrudan gösteriyor: bekleme adımının $n(n-1)$’e oranı bütün satırlarda 4,5‘te sabit. Yani bekleme adımı yaklaşık $4{,}5 \cdot n^2$ ile büyüyor. İş parçacığı sayısını ikiye katlamak süreyi ikiye katlamıyor ama beklemeyi dörde katlıyor: 8 iş parçacığında 252, 16’da 1080.

Bunun sonucu, işlemci kullanımı sütununda okunuyor: 1,0000’den 0,1290’a düşüyor. On altı iş parçacığının on altı katlık gücü, kritik bölge yüzünden aslında kullanılamıyor.

Buradan çıkan tasarım kuralı sayıya dayanır: çekişmeyi düşürmenin yolu daha hızlı bir kilit değil, daha kısa bir kritik bölgedir. Bu iddia bedelsiz bırakılamaz; sayılması gerekir.

Kritik Bölgeyi Kısaltmanın Ölçüsü

Bir sonraki süpürme iş parçacığı sayısını 8’de sabitliyor ve kritik bölgenin toplam iş içindeki payını değiştiriyor.

EZ12. İş parçacığı başına toplam iş 20 adımda sabittir; değişen yalnız bu 20 adımın kaçının kritik bölgede olduğudur.

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)}


TOPLAM = 20
print("8 is parcacigi , is parcacigi basina toplam 20 adim , dislama kilidi")
print("  kritik  kritik disi  kritik pay  sure  bekleme  kullanim")
for kritik in (1, 2, 5, 10, 15, 20):
    k = kilitli_kosum(8, kritik, TOPLAM - kritik, 1)
    print(f"  {kritik:6d}  {TOPLAM - kritik:11d}  {kritik / TOPLAM:10.2f}"
          f"  {k['sure']:4d}  {k['bekleme']:7d}  {k['kullanim']:8.4f}")

8 is parcacigi , is parcacigi basina toplam 20 adim , dislama kilidi
  kritik  kritik disi  kritik pay  sure  bekleme  kullanim
       1           19        0.05    20        0    1.0000
       2           18        0.10    27       28    0.7407
       5           15        0.25    48      112    0.4167
      10           10        0.50    83      252    0.2410
      15            5        0.75   118      392    0.1695
      20            0        1.00   153      532    0.1307

Yapılan iş her satırda aynı: sekiz iş parçacığı, her biri 20 adım. Değişen tek şey bu adımların kaçının sıraya girmek zorunda olduğu.

Kritik pay 0,50 iken süre 83; pay 0,25’e inince 48. Kritik bölgeyi yarıya indirmek süreyi neredeyse yarıya indiriyor. Pay 0,05’e inince süre 20 oluyor — yani tek iş parçacığının süresi. Sekiz iş parçacığı, sekiz katlık gücünü ancak kritik bölge tek adıma indiğinde kullanabiliyor.

Ters yön de aynı ölçüde nettir. Payı 0,50’den 0,75’e çıkarmak süreyi 83’ten 118‘e, 1,00’e çıkarmak 153‘e taşıyor. Bekleme adımı 252’den 532’ye çıkıyor. Bütünüyle kritik bölgeden oluşan bir işte eşzamanlılık hiçbir şey kazandırmaz; yalnız bekleme üretir.

Tablonun ilk satırı sonraki derslerin de dayanağıdır: kritik bölgesi tek adım olan bir iş, çekişme üretmeyen iştir. Donanımın böyle bir adımı bölünmez biçimde yürütmesine atomik işlem (atomic operation) denir ve bedeli bu tabloda sıfırdır.

Sayan Semafor

Sayan semafor (semaphore), kritik bölgeye aynı anda birden çok iş parçacığı alabilen araçtır. Taşıdığı sayı, verilebilecek izin sayısıdır.

EZ13. İzin sayısı sabittir ve koşum boyunca değişmez.

def kilitli_kosum(is_parcacigi: int, kritik: int, kritik_disi: int, izin: int = 1) -> dict:
    """Her is parcacigi `kritik` uzunlukta bir kritik bolge ile `kritik_disi` adim
    kritik olmayan is yapar. izin=1 dislama kilidi , izin>1 sayan semafordur."""
    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("sayan semafor: izin sayisi degisiyor")
print("  is parcacigi  izin  sure  bekleme  kullanim")
for n in (2, 4, 8, 16):
    for izin in (1, 2, 4):
        k = kilitli_kosum(n, 10, 10, izin)
        print(f"  {n:12d}  {izin:4d}  {k['sure']:4d}  {k['bekleme']:7d}  {k['kullanim']:8.4f}")

sayan semafor: izin sayisi degisiyor
  is parcacigi  izin  sure  bekleme  kullanim
             2     1    29        9    0.6897
             2     2    20        0    1.0000
             2     4    20        0    1.0000
             4     1    47       54    0.4255
             4     2    29       18    0.6897
             4     4    20        0    1.0000
             8     1    83      252    0.2410
             8     2    47      108    0.4255
             8     4    29       36    0.6897
            16     1   155     1080    0.1290
            16     2    83      504    0.2410
            16     4    47      216    0.4255

İki izinli semafor, iki iş parçacığının süresini 29’dan 20’ye indiriyor ve beklemeyi 9’dan 0’a. Tablonun tamamında düzenli bir bağıntı var: izin sayısı çekişmeyi böler. Sekiz iş parçacığı iki izinle 47’de bitiyor, yani dört iş parçacığının bir izinli süresinde. On altı iş parçacığı dört izinle yine 47.

Bekleme adımı aynı biçimde bölünmüyor. Dört iş parçacığı bir izinle 54 bekleme adımı üretirken, sekiz iş parçacığı iki izinle 108, on altı iş parçacığı dört izinle 216 üretiyor. Süre eşit, bekleme dört katı: aynı süreyi daha çok iş parçacığıyla elde etmek bedavaya gelmiyor.

Semafor Karşılıklı Dışlama Sağlamaz

Tablodaki kazanç, kolay bir yanlış çıkarıma davet eder: izin sayısını artırınca hem korunuyoruz hem hızlanıyoruz. Bu yanlıştır.

İki izinli semafor, tanımı gereği iki iş parçacığını aynı anda kritik bölgeye alır. Önceki dersin sayacı bu koşulda korunmaz: iki iş parçacığı içerideyken oku-artır-yaz üçlemeleri yeniden serpişir ve 20 serpiştirmenin 18’i yeniden yanlış sonuç verir. Bu dersin ilk ölçüsünün kilit=False satırına geri dönülmüş olur.

O hâlde iki aracın işi başkadır. Dışlama kilidi bir doğruluk aracıdır; kritik bölgeyi korur. Sayan semafor bir kaynak aracıdır; aynı anda kaç iş parçacığının bir kaynak havuzunu kullanabileceğini sınırlar. Havuzda dört bağlantı varsa dört izinli semafor doğrudur; paylaşılan bir sayacın önünde iki izinli semafor hatadır.

Ortak tanımın dördüncü okuması bunu tek cümlede toplar: iki izinli semafor 29’u 20’ye indirir, ama bu karşılıklı dışlamayı gevşetmektir ve bedava değildir.

Bekleme Nasıl Beklenir

Bu ölçüde bekleyen iş parçacığı çekirdeği tutmuyor (EZ10). Beklemenin ikinci bir biçimi daha vardır: meşgul bekleme (busy waiting), yani kilidin boşalıp boşalmadığını sürekli yoklamak.

Ortak tanımın üçüncü okuması bu seçeneği tekrar ölçmeye gerek bırakmaz: yoklamalı model işlemci kullanımını 1,0000 yapar ve süreyi hiç değiştirmez. Yukarıdaki tabloya uygulandığında 16 iş parçacığının kullanımı 0,1290 yerine 1,0000 görünürdü ve süre yine 155 olurdu. Kullanım burada bir vekil ölçüttür ve yanıltır.

Üç Sayı

Ölçüt	Soyutlamasız taban	Soyutlamalı kurulum	Bedel
Süre	tek iş parçacığı, 20	sekiz iş parçacığı, dışlama kilidi, 83	63 zaman birimi
Bekleme adımı	0	252	252 adım
İşlemci kullanımı	1,0000	0,2410	0,7590 düşüş
Yanlış serpiştirme	18 (korumasız)	0	doğruluk kazanıldı

Son satır, ilk üç satırın neden ödendiğini söyler. Bedel yüksek görünüyorsa karşılığı da yüksektir: koruma olmadan sekiz iş parçacığı 20 zaman biriminde biterdi ve sonucun doğru olacağına dair hiçbir güvence bulunmazdı.

Özet

• Dışlama kilidi, erişilebilen serpiştirme kümesini daraltmaz; kümedeki her serpiştirmeyi doğru kılar — ayrı sonuç kümesi [1, 2]’den [2]’ye iner.
• Çekişme arttıkça süre doğrusal büyür: her iş parçacığı 9 zaman birimi ekler; 1’den 16’ya giderken süre 20’den 155’e çıkar.
• Bekleme adımı ikinci dereceden büyür; $n(n-1)$’e oranı bütün satırlarda 4,5’tir. İş parçacığı sayısını ikiye katlamak beklemeyi dörde katlar.
• Sayan semafor çekişmeyi izin sayısına böler ve süreyi düşürür, ama karşılıklı dışlamayı gevşetir; paylaşılan bir sayacın önünde bir doğruluk aracı değildir.
• Çekişmeyi düşürmenin yolu daha hızlı bir kilit değil, daha kısa bir kritik bölgedir: sekiz iş parçacığında kritik pay 0,50’den 0,25’e inince süre 83’ten 48’e, 0,05’e inince 20’ye düşer.

Sonraki Adım

Bu ders tek bir kilidin bedelini ölçtü. Gerçek programlar tek kilit kullanmaz: her paylaşılan yapının kendi kilidi olur ve bir iş parçacığı ikisini birden isteyebilir. Sonraki ders bu durumun iki yeni arızasını ele alır — bir iş parçacığı grubunun birbirini süresiz beklediği kilitlenme ve bir iş parçacığının sırasının hiç gelmediği açlık. Bekleme ilişkisi bir çizgeye dönüştürülecek, Veri Yapıları kursunun döngü tespiti aynen çağrılacak ve sıralı edinimin kilitlenmeyi yapısal olarak ortadan kaldırdığı 648 durumun taranmasıyla gösterilecek.