Mutual Exclusion Teorisi: Critical Section, Peterson Algoritması, Semaphore ve Monitor

Sürüm notu: Bu yazıdaki kodlar .NET 10 (C# 14) ile derlenip denenmiştir; testler xUnit v3 4.0.3 ile yazıldı. Çıktılar ARM64 (Arm'ın 64-bit işlemci mimarisi) üzerinde alınmıştır; x64 için söylenenler .NET memory model spec'ine ve Intel dokümanlarına dayanır.

Önce Tahmin Et

Sitedeki serilerin ortak örnek uygulaması Bookstore'da (bir online kitapçı) iki thread aynı sayacı artırıyor. Lock, Interlocked ya da herhangi bir hazır senkronizasyon tipi kullanmadan, yalnız ortak değişkenleri okuyup yazarak iki thread'in aynı anda critical section'a girmesini engelleyebilir misin? Ders kitaplarındaki Peterson algoritması tam bunu yapıyor ve ispatı da var. Her erişimi Volatile.Read ve Volatile.Write ile yaparsak, bu algoritma ARM64'te 40 milyon girişte kaç kez iki thread'i birlikte içeri alır?

İkinci soru: kargo hazırlama kuyruğunu bekleyen dört consumer thread var. Kuyruk boşsa if (count == 0) Monitor.Wait(...) ile bekliyorlar, uyandıklarında da paketi alıyorlar. 200.000 paketin işlendiği bir koşuda, boş kuyruktan paket almaya kaç kez çalışırlar? Önceki yazıda race'lerin ortak çözümünün "kontrol ile eylemi başka thread'lerin göremeyeceği tek bir adıma indirmek" olduğunu görmüştük. Bu yazıda o adımı mümkün kılan teoriye bakıyoruz.

Critical Section Probleminin Üç Şartı

Critical section, paylaşılan veriye dokunan ve aynı anda yalnız bir thread tarafından çalıştırılması gereken kod bölgesidir. Problemi ilk kez Edsger Dijkstra 1965'teki "Cooperating Sequential Processes" notlarında ve aynı yıl yayımladığı kısa makalede bugünkü hâliyle ortaya koydu. İşletim sistemi ders kitaplarının klasik formülasyonunda doğru bir çözüm üç şartı sağlamalı:

• Mutual exclusion: bir thread critical section'dayken başka hiçbir thread orada olamaz.
• Progress: critical section boşsa ve içeri girmek isteyenler varsa, kimin gireceği sonsuza kadar ertelenemez; girmek istemeyen bir thread bu kararı engelleyemez.
• Bounded waiting: bir thread girmek istediğini bildirdikten sonra, diğer thread'lerin onun önüne geçme sayısının bir üst sınırı vardır; kimse sonsuza kadar beklemez.

Birinci şart güvenlik, diğer ikisi ilerleme ile ilgili. Yalnız birincisini sağlamak kolaydır: kimseyi içeri almayan bir kilit mutual exclusion'ı mükemmel sağlar ama işe yaramaz. Zor olan, üçünü birlikte ve hiçbir atomik donanım talimatı varsaymadan sağlamak.

Yalnız Okuma ve Yazmayla: İlk Denemeler

İlk akla gelen fikir, her thread'in bir "girmek istiyorum" bayrağı tutması: diğerinin bayrağı inikse kendi bayrağını kaldırıp içeri gir.

// Deneme 1: önce diğerinin bayrağına bak, sonra kendininkini kaldır (kontrol ve yazma ayrı adımlar)
public sealed class FlagOnlyLock : ITwoThreadLock
{
    private readonly int[] _wants = new int[2];

    public void Enter(int me)
    {
        while (Volatile.Read(ref _wants[1 - me]) == 1) { }
        Volatile.Write(ref _wants[me], 1);
    }

    public void Exit(int me) => Volatile.Write(ref _wants[me], 0);
}

Bu, önceki yazıdaki check-then-act'in kendisi: iki thread de diğerinin bayrağını inik görüp aynı anda içeri girebilir. Bunu ölçmek için her thread critical section içinde sıradan bir counter++ yapıyor; kaybolan her artış, iki thread'in aynı anda içeride olduğunun kanıtı (gerçek ihlal sayısı bundan da fazla olabilir).

İkinci klasik deneme strict alternation: ortak bir turn değişkeni sırayı söyler ve thread'ler dönüşümlü girer. Mutual exclusion'ı sağlar ama progress'i bozar: sıra sendeyse ve sen hiç girmek istemiyorsan, diğer thread kritik bölge boş olduğu hâlde bekler. Kargo servisi saniyede bir paket üretirken rapor thread'i saatte bir giriyorsa, kargo servisi her seferinde raporu bekler.

Peterson Algoritması ve ARM64'teki Gerçeği

Gary Peterson 1981'de iki fikri birleştiren kısa bir çözüm yayımladı: hem bayrak hem sıra. Thread önce girmek istediğini bildirir, sonra sırayı kibarca karşı tarafa verir ve yalnız "karşı taraf da istiyor ve sıra onda" iken bekler:

// Peterson (1981): bayrağı kaldır, sırayı karşıya ver, karşı taraf istiyor ve sıra ondaysa bekle
public sealed class PetersonLock(bool fullFence) : ITwoThreadLock
{
    private readonly int[] _wants = new int[2];
    private int _turn;

    public void Enter(int me)
    {
        int other = 1 - me;
        Volatile.Write(ref _wants[me], 1);
        Volatile.Write(ref _turn, other);
        if (fullFence)
            Interlocked.MemoryBarrier(); // algoritmanın varsaydığı store-load sırası
        while (Volatile.Read(ref _wants[other]) == 1 && Volatile.Read(ref _turn) == other) { }
    }

    public void Exit(int me) => Volatile.Write(ref _wants[me], 0);
}

Kâğıt üzerindeki ispat şöyle: iki thread de içerideyse ikisi de bekleme koşulunu yanlış bulmuş olmalı. _turn'e son yazan thread, karşı tarafın bayrağını kaldırdığını ve sıranın karşıda olduğunu görecek ve bekleyecektir. Üç şart da sağlanır. İspatın gizli varsayımı ise şu: bir thread'in yazdıkları, kendisinden sonraki okumalarından önce diğer thread'e görünür. Yani her işlem program sırasında ve herkes için aynı sırada olur. Buna sequential consistency deniyor ve modern işlemciler bunu varsayılan olarak vermiyor:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- mutex-attempts 20000000

flag only                lost updates:   281,354 of 40,000,000  (313 ms)
Peterson, volatile only  lost updates:        99 of 40,000,000  (4779 ms)
Peterson + full fence    lost updates:         0 of 40,000,000  (4654 ms)

Bayrak denemesi beklendiği gibi bozuk. Asıl ilginç satır ikincisi: ispatı olan Peterson algoritması 40 milyon girişte 99 artış kaybetti, yani mutual exclusion ARM64'te ihlal edildi. İkinci koşuda bu sayı 1.213 oldu. JIT'in (kodu çalışma anında makine koduna çeviren compiler) ürettiği koda DOTNET_JitDisasm ile baktığımda Volatile.Write'ın stlr (release store), Volatile.Read'in ldapr (acquire load) talimatına dönüştüğünü gördüm. Release yazma kendinden önceki işlemlerin önüne geçmez, acquire okuma kendinden sonrakilerin arkasına düşmez; ama bir release yazmadan sonra gelen acquire okuma, o yazma diğer core'a görünmeden önce çalışabilir. Peterson'ın tam da yasak saydığı sıra bu: "bayrağımı kaldırdım" yazısı henüz görünmeden "karşının bayrağı inik" okuması yapılıyor.

Interlocked.MemoryBarrier() bir full fence'tir: öncesindeki bütün yazmalar, sonrasındaki okumalardan önce tamamlanır. ARM64'te dmb ish talimatına dönüştü ve ihlal sıfıra indi. Bu ARM64'e özgü bir durum değil: Intel'in yazılım geliştirici kılavuzunun memory ordering bölümüne göre x64 da bir load'un kendinden önceki, farklı adrese yapılan bir store'un önüne geçmesine izin verir. x64'te volatile okuma ve yazma sıradan talimatlardır ve bu yeniden sıralamayı engellemez; yani fence olmadan Peterson x64'te de bozulur. Bu farkların donanım tarafını beşinci yazıda, .NET'in volatile ve fence kurallarını altıncı yazıda ayrıntılı anlatacağız.

Peterson'ın üretimde bir yeri yok. Yalnız iki thread için çalışır, fence ile bile lock'tan yavaştır ve doğruluğu memory model'e bağlı. Değeri öğretici: "ispatlı bir algoritmanın bile varsayımları vardır" dersini bundan daha net veren bir örnek bilmiyorum.

Donanım Desteği: Test-and-Set ve Compare-and-Swap

Yalnız okuma ve yazmayla uğraşmak yerine donanım, okuma ve yazmayı tek atomik adımda yapan talimatlar sunar. Test-and-set bir konuma 1 yazar ve eski değeri döndürür. Fetch-and-add bir değeri atomik olarak artırır ve eskisini döndürür. Compare-and-swap (CAS) "değer hâlâ beklediğim gibiyse yenisini yaz" der ve bir öncekilerin hepsini taklit edebilecek kadar güçlüdür. .NET'te bunlar sırasıyla Interlocked.Exchange, Interlocked.Add ve Interlocked.CompareExchange olarak karşımıza çıkar. Test-and-set ile bir spinlock:

// Atomik exchange üzerine kurulu test-and-set
public sealed class TasLock
{
    private int _held;

    public void Enter()
    {
        while (Interlocked.Exchange(ref _held, 1) == 1)
        {
            // test-and-test-and-set: düz okumayla bekle, boş görünce atomik işlemi tekrar dene
            while (Volatile.Read(ref _held) == 1)
                Thread.SpinWait(20);
        }
    }

    public void Exit() => Volatile.Write(ref _held, 0);
}

İçteki döngü önemli bir mühendislik detayı. Atomik talimat cache line'ın sahipliğini ister; her bekleyen thread durmadan Exchange yaparsa, line core'lar arasında sürekli el değiştirir ve kilidi tutan thread bile yavaşlar. Düz okuma ise line'ın paylaşılan bir kopyası üzerinde çalışır; yalnız kilit boş görününce atomik işlem denenir. Cache line'ın core'lar arasındaki trafiğini Bilgisayar Nasıl Çalışır serisinin false sharing yazısında ölçmüştük. Testimiz dört thread'in bu kilitle bir milyon artışı kayıpsız yaptığını doğruluyor; ama bu kilit bounded waiting'i sağlamaz, şanssız bir thread sürekli yarışı kaybedebilir.

Spinlock'ın bekleme şekli CPU yakar; blocking lock ise thread'i uyutur ve OS'in onu tekrar uyandırması mikrosaniyeler sürer. Kritik bölge kısaysa spin daha ucuz, uzunsa bloklamak daha ucuz. Pratik çözüm ikisinin karışımı: önce kısa bir süre spin, sonra blokla. .NET'in SpinWait tipi bu karışımı hazır sunar ve dokümanına göre tek işlemcili makinede hiç busy wait yapmadan doğrudan yield eder. ManualResetEventSlim'in SpinCount property'si de kernel'de beklemeye geçmeden önce kaç kez spin edileceğini söyler. Uygulama kodunda kendi spinlock'unu yazmak neredeyse hiç doğru değil; lock ve Lock tipinin kullanımını C# Asenkron Programlama serisinin senkronizasyon yazısında anlatmıştık.

Semaphore: Dijkstra'nın P ve V'si

Dijkstra aynı 1965 çalışmasında semaphore'u tanımladı: negatif olamayan bir sayaç ve iki atomik işlem. P (Hollandaca kökenli adıyla, bugünkü karşılığı wait) sayaç sıfırsa bekler, değilse bir azaltır. V (signal) sayacı bir artırır ve bekleyen varsa birini uyandırır. Başlangıç değeri 1 olan semaphore bir mutex gibi davranır; N olan semaphore aynı anda en fazla N thread'in bir kaynağı kullanmasına izin verir. Bookstore'da dış kargo API'sine aynı anda en fazla 4 istek göndermek bunun tipik örneği; .NET'teki karşılığı SemaphoreSlim.

Semaphore'un gücü, sayacın "kaç kaynak boşta" bilgisini taşıması. Zayıflığı ise disiplin gerektirmesi: wait ve signal çağrıları kodun farklı yerlerine dağılır, birini unutmak ya da sırasını karıştırmak derleyicinin yakalayamayacağı hatalar üretir. Monitor bu sorunu çözmek için ortaya çıktı.

Monitor ve Condition Variable: Hoare, Brinch Hansen ve Mesa

Monitor fikri Per Brinch Hansen ve Tony Hoare'un 1970'lerin başındaki çalışmalarından gelir; Hoare'un 1974'te yayımladığı "Monitors: An Operating System Structuring Concept" makalesi bugünkü tanımın temeli. Monitor, paylaşılan veriyi ve onu değiştiren işlemleri tek bir yapıda toplar; yapıya aynı anda yalnız bir thread girebilir. Kilit otomatik alınıp bırakıldığı için semaphore'daki dağınıklık ortadan kalkar.

Kilit tek başına yetmez; bazen bir thread monitor'ün içindeyken bir koşulun gerçekleşmesini beklemek zorundadır: "kuyruk boş, paket gelene kadar bekle". Condition variable bunu sağlar: wait, kilidi bırakıp thread'i uyutur ve uyanınca kilidi tekrar alır; signal ise bekleyenlerden birini uyandırır. Burada iki farklı anlam var. Hoare semantiğinde signal veren thread hemen kenara çekilir ve uyandırılan thread kilidi doğrudan alır; uyandığında koşulun hâlâ doğru olduğu garantidir. Butler Lampson ve David Redell'in 1980'de Xerox'un Mesa dilindeki deneyimlerini anlattığı makaleden adını alan Mesa semantiğinde ise signal yalnız bir ipucudur: uyandırılan thread hazır kuyruğuna geçer ve kilidi alana kadar başka bir thread araya girip koşulu yeniden bozabilir.

Bugünkü sistemlerin neredeyse hepsi Mesa semantiğini kullanır. .NET'in Monitor.Wait/Pulse çifti de böyle: dokümanına göre Pulse bekleyen thread'i hazır kuyruğuna taşır ve kilit bırakıldığında onu alan thread, uyandırılan thread olmak zorunda değildir. POSIX'in (Unix benzeri sistemler için ortak API standardı) condition variable'ları ise ek olarak hiçbir sinyal yokken uyanmaya (spurious wakeup) izin verir. Sonuç tek bir kural: koşulu if ile değil, while ile bekle; uyandığında koşula yeniden bak.

Senaryo: Kargo Hazırlama Kuyruğu

Depoda sipariş paketlerini hazırlayan iki producer ve onları kargo firmasına teslim eden dört consumer var. Paketlerin konduğu raf 4 paket alıyor: raf doluysa producer, boşsa consumer bekliyor. Bu klasik bounded buffer problemi ve monitor ile iki koşulla (raf dolu değil, raf boş değil) kuruluyor:

// Monitor olarak bounded buffer: tek lock, iki koşul (dolu değil, boş değil)
public sealed class ShippingQueue(int capacity, bool recheckWithWhile)
{
    private readonly Queue<Parcel> _parcels = new();
    private readonly object _monitor = new();

    public void Put(Parcel parcel)
    {
        lock (_monitor)
        {
            while (_parcels.Count == capacity)
                Monitor.Wait(_monitor);
            _parcels.Enqueue(parcel);
            Monitor.PulseAll(_monitor);
        }
    }

    public Parcel Take()
    {
        lock (_monitor)
        {
            if (recheckWithWhile)
            {
                while (_parcels.Count == 0)
                    Monitor.Wait(_monitor);
            }
            else if (_parcels.Count == 0)
            {
                Monitor.Wait(_monitor); // uyandığımızda koşul yine yanlış olabilir
            }
            Parcel parcel = _parcels.Dequeue();
            Monitor.PulseAll(_monitor);
            return parcel;
        }
    }
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- shipping-queue

if    delivered=200,000 Take() on empty queue=54,234
while delivered=200,000 Take() on empty queue=0

if sürümünde consumer'lar 54.234 kez boş kuyruktan paket almaya çalıştı ve InvalidOperationException aldı (deney bunu yakalayıp sayıyor). Senaryo şöyle: raf boşken üç consumer bekliyor, bir paket geliyor ve PulseAll üçünü de uyandırıyor. İlki paketi alıyor, diğer ikisi kilidi sırayla aldığında raf yine boş ama if koşula bir daha bakmıyor. while sürümünde aynı koşuda hiç hata yok. Burada PulseAll kullanmamın sebebi tek bir monitor'de iki farklı koşulun beklenmesi: Pulse yalnız bir thread uyandırır ve o thread yanlış koşulu bekleyen biri olursa (consumer'ı uyandırmak isterken bir producer'ı uyandırmak) sinyal kaybolur ve sistem durabilir.

Pratikte bu sınıfı kendin yazmazsın: bounded Channel<T> aynı işi async olarak ve backpressure ile yapar, C# Asenkron Programlama serisinin Channels yazısında anlatmıştık. Ama Channels'ın içinde ne olduğunu bilmek, kendi koşullu bekleyişini yazdığın her yerde (cache dolumu, bağlantı havuzu, rate limiter) aynı hatayı yapmamanı sağlar.

Üretimde Dikkat

Lock'un içinde I/O yapma. Kilit tutulurken yapılan bir veritabanı çağrısı ya da HTTP isteği, critical section'ı milisaniyelerce uzatır ve bütün bekleyen thread'leri seri hâle getirir; ilk yazıdaki Amdahl hesabında bu doğrudan seri kısmı büyütür. Önce veriyi hazırla, kilidi yalnız paylaşılan durumu değiştirmek için al, I/O'yu kilidin dışında yap.

Lock granularity bir trade-off'tur. Bütün stoğu tek bir kilitle korumak (coarse-grained) basittir ve deadlock riski yoktur ama her rezervasyon diğerini bekler. Her kitaba ayrı kilit (fine-grained) paralelliği artırır ama iki kitabı birlikte değiştiren bir işlem iki kilit alır ve bir sonraki yazının konusu olan deadlock kapısını açar. Ölçmeden fine-grained'e geçme; contention gerçekten kilitteyse geç.

Kilit contention'ını izle. .NET 9 ile gelen System.Runtime meter'ındaki dotnet.monitor.lock_contentions metriği, process başladığından beri bir monitor kilidi alınmaya çalışılırken kaç kez başka bir thread'in onu tuttuğunu sayar; aynı değeri koddan Monitor.LockContentionCount ile de okuyabilirsin. Bu sayının yük ile birlikte hızla artması, kilidin darboğaz olduğunun ilk işaretidir.

Sık Düşülen Tuzaklar

if ile beklemek. Deneyde 200.000 paketlik koşuda 54.234 hata üretti. Mesa semantiğinde uyanmak, koşulun doğru olduğu anlamına gelmez; her zaman while.

volatile'ın her sırayı koruduğunu sanmak. Peterson'ın volatile sürümü ARM64'te bozuldu, x64'te de bozulur. Volatile acquire/release sağlar, store'dan sonra gelen load'un sırasını sağlamaz. Bunu sağlayan full fence'tir ve lock ile Interlocked zaten içerir.

Pulse'un hatırlandığını sanmak. Dokümana göre Monitor pulse'u saklamaz; bekleyen yokken çağrılan Pulse kaybolur. Koşulu bir alanda tut ve beklemeden önce o alana bak; sinyale değil, duruma güven.

Kendi kilidini yazmak. Bu yazıdaki kilitlerin hepsi öğretici. Üretimde lock/Lock, SemaphoreSlim ve Channel<T> yıllarca test edilmiş, memory model'i doğru kullanan ve fairness ile spin dengesini düşünmüş araçlardır.

Küçük Bir Deneme

★☆☆ mutex-attempts komutunu birkaç kez çalıştır ve volatile Peterson'ın kaybettiği artış sayısını not et. Sayı neden koşudan koşuya bu kadar değişiyor?

★★☆ ShippingQueue'da PulseAll yerine Pulse kullan ve while sürümünü birkaç kez çalıştır. Program takılırsa thread'lerin hangi koşulu beklediğini açıkla. Sonra Pulse'un neden güvenli olduğu bir durumu açıkla: kapasite sınırı olmayan bir kuyrukta yalnız consumer'lar bekliyorsa ne değişir?

★★★ TasLock'a bounded waiting ekle: ticket lock yaz. İki int sayaç kullan; giren thread Interlocked.Increment ile bir numara alsın ve "şu an hizmet edilen numara" kendi numarası olana kadar beklesin. Dört thread ile her thread'in kaç kez girdiğini sayarak fairness'ı TasLock ile karşılaştır.

Bu yazıda bir thread'in kilit beklerken ilerleyememesini kabul ettik. Peki iki thread birbirinin tuttuğu kilidi beklerse? Bir sonraki yazıda deadlock'u Coffman'ın dört koşuluyla tanımlıyor, Bookstore'un iki deposu arasındaki stok transferinde gerçekten kilitleniyor, lock ordering ile çözüyor ve livelock, starvation ve Mars Pathfinder'ı durduran priority inversion'a bakıyoruz.