Bölüm 6: Senkronizasyon

6.1Yarış durumu

Süreçler ve iş parçacıkları tek başlarına çalıştıklarında davranışları kolay öngörülür: aynı girdiyle aynı sonucu üretirler. Ortak bir veriyi paylaştıklarında bu kolaylık kaybolur. Sonuç artık yalnız koda değil, iki akışın komutlarının hangi sırayla iç içe geçtiğine de bağlıdır. Bu kesim sorunun nereden çıktığını üç örnekle gösterir: çekirdekteki bir sayaç, bir yazıcı kuyruğu ve tek satırlık bir count++.

6.1.1Neden senkronizasyon?

Bir süreç, komutlarının herhangi birinin ardından kesilebilir. Zamanlayıcı kesmesi gelir, çizelgeleyici başka bir süreci seçer ve kesilen süreç yaptığı güncellemeyi yarıda bırakır. Yarım kalmış güncellemeyi bu sırada başka bir süreç okursa tutarsız bir değer görür. Çok çekirdekli sistemlerde kesme bile gerekmez: iki çekirdek gerçekten aynı anda aynı bellek sözcüğüne yazabilir. Şekil 6.1 bu durumu gösterir. İki iş parçacığı aynı count değişkeni üzerinde “oku, değiştir, yaz” adımlarını yürütür; araya giren bir bağlam değiştirme güncellemeyi yarıda bırakır.

Senkronizasyon hatalarının belirtileri çeşitlidir:

• Tutarsız veri ve kayıp güncelleme. İki artırmadan biri kaybolur; bağlı listenin bir düğümü listeden kopar.
• Ezilen ortak tampon. Ortak bir statik tampon kullanan, yani yeniden girilemeyen (non-reentrant) bir fonksiyon iki iş parçacığından çağrılınca biri ötekinin sonucunu ezer.
• Kilitlenme. İki iş parçacığı birbirinin bıraktığını beklerken sonsuza dek bekler.
• Açlık. Bir iş parçacığına hiç sıra gelmez; ötekiler hep önüne geçer.

Bu hataların ortak özelliği ara sıra ortaya çıkmalarıdır. Program yüz kez doğru çalışır, yüz birincide yanlış sonuç verir. Hata ayıklayıcıyla adım adım yürütmek zamanlamayı değiştirdiği için hata çoğu zaman kaybolur. Bu yüzden senkronizasyon hataları test ederek değil, kodu baştan doğru kurarak önlenir.

6.1.2Çekirdekte bir yarış: fork() ve pid

Yarışlar yalnız kullanıcı programlarında görülmez; çekirdeğin kendisi de paylaşılan verilerle doludur. Silberschatz'ın örneğinde çekirdek, sıradaki boş süreç kimliğini next_available_pid adlı bir değişkende tutar. Değer 2615'tir. P0 ve P1 süreçleri neredeyse aynı anda fork() çağırır. Her çağrıda çekirdek kodu üç iş yapar: değeri okur, çocuğa verir ve bir artırıp geri yazar.

1. P0 okur. P0'ın çekirdek kodu next_available_pid değerini okur: 2615. Artırıp yazmadan önce kesilir.
2. P1 okur ve yazar. P1 de 2615 okur, çocuğuna 2615 verir ve değişkene 2616 yazar.
3. P0 sürer. P0 kaldığı yerden devam eder. Elindeki eski değerle çocuğuna yine 2615 verir ve o da 2616 yazar.

Sonuçta iki farklı sürece aynı kimlik verilmiştir ve sayaç iki yerine bir artmıştır (Şekil 6.2). İşlemler başka bir sırayla yürüseydi, örneğin P0 kesilmeden üç adımını bitirseydi, çocuklar 2615 ve 2616 kimliklerini alacaktı. Sonucun işlemlerin sırasına bağlı olması bu bölümün temel kavramının ta kendisidir.

6.1.3Yazıcı biriktirme dizini

Tanenbaum aynı sorunu bir yazıcı kuyruğuyla anlatır. Yazdırılacak dosyaların adları bir biriktirme dizinindeki (spooler directory) numaralı yuvalara sırayla yazılır. Yazıcı süreci dizini tarar ve dosyaları yazdırır. Paylaşılan iki değişken vardır: out, sıradaki yazdırılacak yuvayı; in, ilk boş yuvayı gösterir. Başlangıçta 4, 5 ve 6 numaralı yuvalar doludur; out = 4, in = 7'dir.

A ve B süreçleri birer dosya yazdırmak ister. Her biri in'i yerel bir next_free değişkenine okur, dosya adını o yuvaya yazar ve in'i bir artırır. Şekil 6.3 şu ara yerleştirmeyi gösterir:

1. A, in'i okur ve next_free = 7 yapar. Tam o anda zaman dilimi biter.
2. B de in'i okur: yine 7.
3. B, b.txt adını 7. yuvaya yazar ve in = 8 yapar.
4. A kaldığı yerden devam eder. Yerel değişkeni hâlâ 7 olduğu için a.txt'yi 7. yuvaya yazar, B'nin girdisini ezer ve in = 8 yapar.

Dizin dışarıdan bakınca tutarlıdır: in = 8 ve yuvaların hepsi dolu. Yazıcı süreci hiçbir tutarsızlık fark etmez. Ama B'nin çıktısı kaybolmuştur ve B kullanıcısı yazıcının başında boşuna bekler.

6.1.4Tek satır, üç komut: count++

Yarış durumu için uzun bir kod gerekmez. C dilindeki tek bir count++ satırı, makine düzeyinde üç komuta derlenir:

1. reg = count: değeri bellekten bir yazmaca yükle,
2. reg = reg + 1: yazmacı artır,
3. count = reg: yazmacı belleğe geri yaz.

count-- da aynı üç adımdan oluşur; yalnız ortadaki işlem çıkarmadır. Her iş parçacığının kendi yazmaç kümesi vardır. Bir iş parçacığı kesildiğinde yazmaçları PCB'sine kaydedilir; yazmaçtaki ara değer belleğe yansımaz.

Burada geçen ara yerleştirme (interleaving), eş zamanlı akışların komutlarının, her akışın kendi içindeki sırası korunarak tek bir sıraya dizilmesidir. Tek çekirdekte bu sırayı çizelgeleyici belirler. Çok çekirdekte ise farklı çekirdeklerdeki komutların belleğe ulaşma sırası belirler. m ve n komutluk iki akış için olası ara yerleştirme sayısı C(m + n, m)'dir; üçer komutluk iki akış için C(6, 3) = 20'dir. Bu sayı akışlar uzadıkça çok hızlı büyür ve hepsini elle denemek olanaksızlaşır.

Yarışın bir başka yüzü, aynı programın her çalıştırmada farklı sonuç üretmesidir. Aşağıdaki iki süreç n adlı ortak bir sayaç kullanır: birinci süreç sürekli n'i artırır, ikinci süreç ara sıra n'i yazdırıp sıfırlar. Amaç belli bir sürede kaç olay sayıldığını raporlamaktır.

/* Süreç 1 */     /* Süreç 2 */
repeat           repeat
  n = n + 1;       print(n);
                   n = 0;

n = 5 iken iki sürecin adımları üç farklı biçimde iç içe geçebilir:

• n = n + 1; print(n); n = 0 → ekrana 6 yazılır, sayaç 0 olur. Doğru davranış budur.
• print(n); n = 0; n = n + 1 → 5 yazılır, sayaç 1 olur. Bu da doğrudur: artış bir sonraki rapora kalmıştır.
• print(n); n = n + 1; n = 0 → 5 yazılır ve sayaç 0 olur. Artış hiçbir raporda görünmez: kaybolmuştur.

Bu tür bir yürütmeye tekrarlanamaz (non-reproducible) yürütme denir. Hatalı sonuç ancak belli bir zamanlamada ortaya çıkar ve aynı girdiyle yeniden çalıştırmak onu çoğu zaman yinelemez.

Aynı yarışı gerçek bir makinede görmek kolaydır. Aşağıdaki Java programında iki iş parçacığı korumasız bir sayacı 100 000'er kez artırır. Doğru sonuç 200 000'dir.

public class Yaris {
  static int sayac = 0;                 /* korumasız */
  public static void main(String[] a) throws InterruptedException {
    Runnable is = () -> { for (int n = 0; n < 100_000; n++) sayac++; };
    Thread t1 = new Thread(is), t2 = new Thread(is);
    t1.start(); t2.start(); t1.join(); t2.join();
    System.out.println("sayac = " + sayac);
  }
}

Program JDK 21 ile aynı makinede üç kez çalıştırıldığında şu çıktıları verdi:

sayac = 170429
sayac = 150258
sayac = 135129

Bu sayılar her çalıştırmada değişir; başka bir makinede, başka bir yük altında çok farklı değerler çıkabilir. Değişmeyen tek şey, sonucun hemen hiçbir zaman 200 000 olmamasıdır. Kaybolan her artış, Tablo 6.1'deki gibi bir ara yerleştirmenin sonucudur.

6.2Kritik bölge problemi

Yarış durumlarının ortak bir yapısı vardır: her süreç kodunun belli bir parçasında paylaşılan veriye dokunur. Sorunu çözmek için bütün programı korumak gerekmez; yalnız bu parçaların aynı anda çalışmasını engellemek yeter. Bu kesim o parçayı ve bir çözümden beklenenleri tanımlar.

6.2.1Giriş, kritik, çıkış ve kalan bölüm

Sistemde n süreç olsun: {P₀, P₁, …, P_n−1}. Her birinin kodunda paylaşılan veriye eriştiği bir bölüm vardır: bir global değişkene yazmak, bir tabloyu güncellemek, bir dosyaya yazmak gibi.

Bir süreç kritik bölgesine girmeden önce izin ister; bu isteği yapan koda giriş bölümü (entry section) denir. Kritik bölgeden çıkarken başkalarına bunu duyurur; bu da çıkış bölümüdür (exit section). Kodun geri kalanı kalan bölümdür (remainder section). Tipik bir süreç bu dört parçayı bir döngü içinde tekrarlar (Şekil 6.4):

while (true) {
    /* giriş bölümü  (entry)     */
        /* kritik bölge          */
    /* çıkış bölümü  (exit)      */
        /* kalan bölüm (remainder) */
}

Kritik bölge problemi, süreçlerin işbirliği yapmasını sağlayacak bir giriş ve çıkış protokolü tasarlamaktır. Kritik bölgenin ve kalan bölümün içeriği protokolü ilgilendirmez. Önemli olan, giriş ve çıkış bölümlerinin hangi zamanlamada olursa olsun doğru çalışmasıdır.

6.2.2Bir çözümün üç koşulu

Karşılıklı dışlama tek başına yetmez. Hiç kimseyi kritik bölgeye sokmayan bir protokol de dışlamayı “sağlar” ama işe yaramaz. Bu yüzden Silberschatz bir çözümden üç koşul ister.

Birinci koşul bir güvenlik (safety) özelliğidir: “kötü bir şey asla olmaz”. İkinci ve üçüncü koşul canlılık (liveness) özellikleridir: “iyi bir şey sonunda olur”. İlerleme koşulu sistemin bütün olarak takılmamasını, sınırlı bekleme ise tek tek her sürecin sonunda sıra almasını güvenceye alır. Sınırlı bekleme sağlanırsa hiçbir süreç açlığa (starvation) düşmez.

Her üç koşul da süreçlerin hızı hakkında bir varsayım yapmaz. Yalnız her sürecin sıfırdan büyük bir hızla ilerlediği kabul edilir; süreçlerin birbirine göre göreli hızları bilinmez. Tanenbaum aynı gereksinimleri dört madde olarak yazar. Tablo 6.2 bu maddelerin üç koşulla eşleşmesini verir.

6.2.3Kritik bölge zaman çizelgesi

İyi bir çözümün davranışı Tanenbaum'un zaman çizelgesinde açıkça görülür (Şekil 6.5):

1. T1. A kritik bölgesine girer.
2. T2. B de girmek ister. Bölge dolu olduğu için B bloke olur ya da meşgul bekler.
3. T3. A çıkar ve bekleyen B hemen girer.
4. T4. B çıkar.

Çizelgede hiçbir anda iki süreç birlikte kritik bölgede değildir. İyi bir çözüm bu davranışı yalnız bu zamanlamada değil, olası bütün zamanlamalarda garanti etmelidir. Üç koşuldan birini bozan tek bir ara yerleştirme, bir çözümü geçersiz kılmaya yeter.

6.3Yazılım yaklaşımları

İlk çözüm denemeleri özel bir donanım desteği kullanmaz; yalnız sıradan okuma ve yazma komutlarıyla kurulur. Bu denemelerin çoğu başarısızdır, ama neden başarısız olduklarını görmek üç koşulu anlamanın en iyi yoludur. Kesim, işletim sistemine özgü bir yolla, kesmeleri kapatmakla başlar ve Peterson algoritmasıyla biter.

6.3.1Kesmeleri kapatmak

Tek çekirdekli bir makinede bir süreç ancak bir kesme yüzünden işlemciyi kaybeder. Süreç kritik bölgeye girmeden önce kesmeleri kapatır ve çıkınca yeniden açarsa zamanlayıcı kesmesi gelmez, bağlam değiştirme de olmaz. x86'da bu iş cli (kesmeleri temizle) ve sti (kesmeleri kur) komutlarıyla yapılır. Fikir basittir ama kullanıcı programları için uygun değildir:

• Kesmeleri açmayı unutan ya da kritik bölgede sonsuz döngüye giren bir süreç bütün sistemi kilitler. İşletim sistemi denetimi bir daha geri alamaz.
• Kesmeler kapalıyken G/Ç tamamlanma ve zamanlayıcı kesmeleri bekler. Uzun bir kritik bölge sistemi tepkisiz bırakır.
• Çok çekirdekli makinede işe yaramaz. cli yalnız onu yürüten çekirdeğin kesmelerini kapatır; öteki çekirdekler paylaşılan veriye erişmeyi sürdürür (Şekil 6.6).
• cli ve sti ayrıcalıklı komutlardır. Kullanıcı modundaki bir program bunları çalıştıramaz; çalıştırmaya kalkarsa işlemci bir tuzak üretir.

Yöntem çekirdeğin içinde ise yaygındır; ama kısa süreli ve yerel olarak kullanılır. Linux'ta local_irq_save() yerel çekirdeğin kesmelerini kapatır ve eski durumu saklar. Bir kesme işleyicisiyle paylaşılan veride spin_lock_irqsave() hem kesmeleri kapatır hem de öteki çekirdeklere karşı bir spinlock alır. İki önlem birlikte gerekir: kesme kapatma aynı çekirdekteki işleyiciye, spinlock öteki çekirdeklere karşı korur.

6.3.2Kilit değişkeni

İlk akla gelen yazılım çözümü paylaşılan bir kilit değişkenidir. lock değeri 0 ise bölge boştur, 1 ise biri içeridedir. Giren süreç değer 0 olana kadar bekler, sonra 1 yazar; çıkarken yeniden 0 yazar.

int lock = 0;           /* paylaşılan */

void gir(void) {
  while (lock != 0)
    ;                   /* meşgul bekle */
  lock = 1;
}
void cik(void) {
  lock = 0;
}

/* her süreç:  gir(); kritik_bolge(); cik(); */

Kodun hatası, “test et” ile “ata” adımlarının ayrı olmasıdır. Satır 4'teki sınama ile satır 6'daki atama arasında süreç kesilebilir. Şu ara yerleştirme karşılıklı dışlamayı bozar:

1. Başlangıç. lock = 0; bölge boştur.
2. P0 sınar. P0 lock'u okur: 0. Döngüden çıkar.
3. P0 kesilir. P0, satır 6'daki lock = 1 atamasını yapmadan önce kesilir. P1 çalışır ve o da 0 okur.
4. P1 girer. P1 kilidi 1 yapar ve kritik bölgeye girer.
5. P0 girer. P0 kaldığı yerden devam eder. Sınamayı zaten yaptığı için değeri yeniden okumaz; o da 1 yazar ve girer.

Durum uzayının tamamı bir programla gezildiğinde aynı sonuç çıkar: iki sürecin aynı anda kritik bölgede olduğu bir durum erişilebilirdir. Sorun özünde döngüseldir. Kilidin kendisi paylaşılan bir değişkendir ve onu güvenle sınayıp değiştirmek için yine bir kilide ihtiyaç duyulur. Bu yüzden sıradan okuma ve yazmayla kurulan bir kilit değişkeni tek başına yetmez. Çözüm, sınama ve atamayı tek bir bölünmez komutta birleştirmektir; bu komutu donanım sağlar. Yalnız okuma ve yazmayla daha ileri gidilebildiğini ise katı sıra ve Peterson algoritması gösterir.

6.3.3Katı sırayla değişim

İkinci deneme kilit yerine bir sıra değişkeni kullanır. Paylaşılan turn değişkeni kritik bölgeye sıranın kimde olduğunu gösterir. P0 ancak turn == 0 iken, P1 ancak turn == 1 iken girer. Çıkan süreç sırayı ötekine verir.

/* P0 */
while (true) {
  while (turn != 0) ;  /* bekle */
  kritik_bolge();
  turn = 1;
  kritik_disi();
}

/* P1 */
while (true) {
  while (turn != 1) ;  /* bekle */
  kritik_bolge();
  turn = 0;
  kritik_disi();
}

Bu çözüm karşılıklı dışlamayı sağlar: turn aynı anda hem 0 hem 1 olamaz ve yalnız kritik bölgeden çıkan süreç onu değiştirir. Sınırlı bekleme de sağlanır: sıra her çıkışta öteki sürece geçer, bu yüzden bir süreç en fazla bir giriş bekler. Sorun ilerleme koşulundadır. Şu senaryoda bu açıkça görülür (Şekil 6.8):

1. turn = 0 iken P0 girer; P1 meşgul bekler.
2. P0 çıkarken turn = 1 yapar; P1 girer.
3. P1 çıkarken turn = 0 yapar ve uzun bir kritik dışı işe başlar. P0 bir kez daha girip çıkar ve turn = 1 yapar.
4. P0 yeniden girmek ister ama sıra P1'dedir. Bölge boştur, P1 de kritik bölgeye ilgi göstermez; buna rağmen P0 giremez.

Katı sıra süreçleri zorla dönüşümlü çalıştırır. Hızları farklı iki süreçten hızlı olanı, yavaş olanın kalan bölümünü bitirmesini beklemek zorunda kalır. Kalan bölümünde takılan ya da hiç geri dönmeyen bir süreç, ötekini sonsuza dek dışarıda bırakır. Ayrıca bekleyen süreç while (turn != i) ; döngüsünde boşuna işlemci harcar.

6.3.4Peterson algoritması

G. L. Peterson 1981'de, yalnız okuma ve yazmayla iki süreç için doğru çalışan kısa bir çözüm verdi. Algoritma kilit değişkeni fikriyle katı sıra fikrini birleştirir. Her sürecin bir flag bayrağı vardır: flag[i] = true, “P_i girmek istiyor” demektir. Ortak turn değişkeni ise iki süreç birlikte istediğinde kimin önce gireceğini belirler.

/* paylaşılan */
bool flag[2] = { false, false };
int  turn;

/* P_i  (j = 1 - i) */
while (true) {
  flag[i] = true;    /* girmek istiyorum */
  turn = j;          /* önce sen buyur  */
  while (flag[j] && turn == j)
    ;                /* meşgul bekle    */
  /* kritik bölge */
  flag[i] = false;
  /* kalan bölüm */
}

Giriş bölümü iki satırdır. Süreç önce niyetini bildirir (flag[i] = true), sonra nezaket gösterip sırayı ötekine verir (turn = j, yani “önce sen buyur”). Ardından öteki süreç girmek istediği ve sıra onda olduğu sürece bekler. Çıkışta yalnız kendi bayrağını indirir.

Algoritmanın üç koşulu nasıl sağladığı birkaç cümleyle gösterilebilir:

• Karşılıklı dışlama. İki süreç birden kritik bölgedeyse flag[0] ve flag[1] ikisi de true olmalıdır. Bu durumda her biri döngüden ancak turn kendi lehine olduğunda çıkabilir. Ama turn aynı anda hem 0 hem 1 olamaz. turn'e son yazan süreç sırayı ötekine bırakmıştır ve beklemek ona düşer.
• İlerleme. P_j girmek istemiyorsa flag[j] = false'tur ve P_i'nin döngü koşulu hemen yanlış olur: P_i beklemeden girer. Kalan bölümdeki bir süreç ötekini engellemez.
• Sınırlı bekleme. P_i beklerken P_j çıkar ve hemen yeniden girmek isterse, giriş bölümünde turn = i yazmak zorundadır. Bu atama P_i'nin önünü açar. P_i en fazla bir giriş bekler.

Peterson algoritması yalnız iki süreç içindir. n süreç için Lamport'un fırıncı (bakery) algoritması vardır: her süreç bir sıra numarası alır ve en küçük numaralı süreç girer. Bu algoritmaların iki önemli bedeli vardır. Birincisi meşgul beklemedir; bekleyen süreç işlemci yakar. İkincisi daha önemlidir: doğruluk kanıtı, bütün işlemcilerin bellek işlemlerini tek bir ortak sırada gördüğünü varsayar. Bu varsayıma sıralı tutarlılık denir ve modern donanım onu kendiliğinden sağlamaz.

6.3.5Kod izleme: Peterson

Algoritmanın davranışını en iyi bir ara yerleştirmeyi adım adım izlemek gösterir. Aşağıdaki kod giriş ve çıkış bölümlerini gir(i) ve cik(i) fonksiyonlarına ayırır. Bellek sıralı tutarlı varsayılır: her yazma hemen bütün süreçlere görünür.

bool flag[2] = { false, false };
int turn;
void gir(int i) {
  int j = 1 - i;
  flag[i] = true;   /* istiyorum */
  turn = j;         /* sen buyur */
  while (flag[j] && turn == j)
    ;               /* meşgul bekle */
}
void cik(int i) {
  flag[i] = false;
}

Tablo 6.3 iki sürecin neredeyse aynı anda girmek istediği bir senaryoyu izler. Her satır bir adımın ardından paylaşılan değişkenleri ve süreçlerin durumunu verir. “Giriyor” giriş bölümünde olmayı, “dönüyor” bekleme döngüsünde olmayı, KB ise kritik bölgede olmayı gösterir.

Adım 4 ve 5 izlemenin kilit noktasıdır. İki süreç de sırayı ötekine verir; ama turn tek bir değişkendir ve son yazanın değeri kalır. P1 en son yazdığı için turn = 0 olur ve beklemek P1'e düşer. Adım 6'da P0'ın koşulu flag[1] && turn == 1, yani true && false olur; P0 girer. Adım 7'de P1'in koşulu flag[0] && turn == 0 doğrudur ve P1 döner. Karşılıklı dışlama korunur.

Adım 8'de P0 çıkar ve bayrağını indirir. P1'in koşulu yanlışa döner ve P1 girer (adım 9): ilerleme sağlanır. Adım 10'da P0 yeniden girmek ister; bu kez turn'e son yazan P0'dır ve beklemek ona düşer. P1 çıkınca (adım 12) P0 girer. P1 hemen yeniden isteseydi turn = 0 yazıp bekleyecekti. Böylece P0 en fazla bir giriş bekler: sınırlı bekleme de sağlanır.

Bu izleme tek bir ara yerleştirmedir; doğruluk ise hepsi için geçerli olmalıdır. İki süreçlik Peterson'un küçük durum uzayı bir programla tamamen gezildi. Sıralı tutarlı bellekte ne dışlama ihlali ne de kilitlenme bulundu.

6.4Bellek modeli

Peterson algoritmasının kanıtı, bir süreç bir değişkene yazdığında bu yazmanın hemen ve aynı sırayla herkese göründüğünü varsayar. Modern bir çok çekirdekli işlemcide bu varsayım doğru değildir. Hem işlemci hem derleyici, tek iş parçacığının sonucunu değiştirmediği sürece bellek erişimlerinin sırasını değiştirebilir. Bu kesim, bu yeniden sıralamanın Peterson'u nasıl bozduğunu ve nasıl önlendiğini anlatır.

6.4.1Peterson modern işlemcide neden bozulur?

Her çekirdeğin bir yazma tamponu (store buffer) vardır. Çekirdek bir yazma komutu yürüttüğünde değer önce bu tampona gider. Çekirdek yazmanın belleğe ulaşmasını beklemeden sonraki komutlara geçer; tampon arka planda belleğe boşaltılır. Bu düzen yazmaları çok hızlandırır. Aynı çekirdek sonra o adresi okursa değeri kendi tamponundan alır. Öteki çekirdekler ise tampon boşalana kadar eski değeri görür.

/* P_i  (i = 0 ya da 1, j = 1 - i) */
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
  ;
/* kritik bölge */
flag[i] = false;

Peterson'un giriş bölümünde her süreç önce iki yazma (flag[i] ve turn), sonra bir okuma (flag[j]) yapar. Yazma tamponu varken şu yürütme mümkündür (Şekil 6.10):

1. Başlangıç. Bellekte iki bayrak da false'tur.
2. P0 yazar. P0 flag[0] = true ve turn = 1 yazar. İki yazma da Çekirdek 0'ın tamponunda bekler; bellekte henüz görünmez.
3. P1 yazar. P1 de aynısını yapar; yazmaları Çekirdek 1'in tamponundadır.
4. P0 okur. P0, flag[1]'i bellekten okur: false. Döngüden çıkar ve kritik bölgeye girer.
5. P1 okur. P1 de flag[0]'ı bellekten false okur ve girer. İki süreç birden kritik bölgededir.
6. Tamponlar boşalır. Bellek sonunda flag[0] = flag[1] = true olur. Ama iş işten geçmiştir.

Burada hiçbir komut “yanlış” çalışmamıştır. Her çekirdek kendi bakış açısından programı sırasıyla yürütmüştür. Sorun, bir çekirdeğin yazmasının öteki çekirdeğe, o çekirdeğin sonraki okumasından sonra ulaşmasıdır. Dışarıdan bakan için etki, “yazma, sonraki okumadan sonraya kaydı” gibidir. Derleyici de aynı etkiyi yaratabilir: flag[j] okumasını yazmaların önüne alabilir ya da döngüde değişmeyen bir değeri bir kez okuyup yazmaçta tutabilir. Bu not için yazma tamponlarıyla kurulan modelde Peterson'un bütün yürütmeleri gezildi. Bariyersiz sürümde iki sürecin birlikte girdiği bir yürütme bulundu; tam bariyerli sürümde bulunmadı.

6.4.2Bellek modelleri ve yeniden sıralama

Bir işlemcinin hangi yeniden sıralamalara izin verdiğini onun bellek modeli belirler. Farkı en kısa yoldan gösteren deney, “yazma tamponu testi” (store-buffer litmus test) olarak anılır:

/* x = y = 0 */
/* T1 */        /* T2 */
x = 1;          y = 1;
r1 = y;         r2 = x;

/* r1 == 0 && r2 == 0 ?  */

x86'nın modeline toplam yazma sırası (total store order, TSO) denir. Bu model SC'ye oldukça yakındır; yazma tamponundan doğan tek bir gevşemeye izin verir. Peterson'u bozan da tam olarak bu gevşemedir. ARM ve RISC-V gibi zayıf modellerde daha çok yeniden sıralama mümkündür. Örneğin iki yazma, başka bir çekirdeğe yazıldıkları sıranın tersiyle görünebilir.

Bu farklar yüzünden eş zamanlı kod “işlemci ne yapar” sorusuna göre değil, dilin bellek modeline göre yazılır. C'deki volatile anahtar sözcüğü bu iş için bir araç değildir. volatile yalnız derleyicinin o değişkene her erişimi gerçekten yapmasını ister. İş parçacıkları için ne atomiklik ne de sıralama sağlar. Doğru araçlar C11'in <stdatomic.h> başlığı, Java'nın volatile alanları ve java.util.concurrent paketi ile kilitlerdir.

6.4.3Bellek bariyerleri

Silberschatz'ın örneğinde iki iş parçacığı bir bayrakla haberleşir. İş parçacığı 2 önce x = 100, sonra flag = true yazar. İş parçacığı 1, flag doğru olana kadar bekler ve sonra x'i yazdırır. Programcının beklentisi 100 yazılmasıdır. Zayıf bir bellek modelinde iki şey bu beklentiyi bozar (Şekil 6.11):

• Yazmalar yer değiştirir. İş parçacığı 2'nin yazmaları öteki çekirdeğe ters sırayla ulaşır. İş parçacığı 1 flag'i true görür ama x hâlâ 0'dır.
• Okumalar yer değiştirir. İş parçacığı 1'in kendisi x'i flag'den önce okuyabilir. Döngüden çıktığında elindeki x eski değerdir.

Örnekte iş parçacığı 2 iki yazmanın arasına bir bariyer koyar: x'in yazılması kesinlikle flag'den önce görünür. İş parçacığı 1 de döngüden sonra bir bariyer koyar: x okuması kesinlikle flag okumasından sonra yapılır. İki bariyer birlikte çıktının 100 olmasını garanti eder. Gerçek kodda bariyerin adı platforma göre değişir: x86'da mfence, ARM'da dmb, Linux çekirdeğinde smp_mb(), C11'de atomic_thread_fence.

Tam bariyer pahalı bir komuttur, çünkü yazma tamponunun boşalmasını bekler. Çoğu durumda daha hafif bir garanti yeter. Yazan taraf flag'i release anlamıyla yazar: önceki bütün erişimler bu yazmadan önce görünür. Okuyan taraf flag'i acquire anlamıyla okur: sonraki erişimler bu okumadan önce yapılmaz. Kilit ve semafor gerçeklemeleri bu bariyerleri zaten içerir. Bu yüzden kilitle korunan kodda ayrıca bariyer yazmak gerekmez. Bariyerler, kilitleri ve atomik değişkenleri yazanların aracıdır.

6.4.4Peterson'un Java'da doğru yazılışı

Java bellek modelinde volatile alanlara yapılan okuma ve yazmalar sıralı tutarlıdır. Derleyici ve JVM bu erişimlerin sırasını korumak için gereken bariyerleri kendisi ekler. Bu yüzden Peterson algoritması ayrı volatile alanlarla Java'da doğru çalışır:

public class Peterson {
  static volatile boolean flag0, flag1;
  static volatile int turn;
  static int sayac = 0;

  static void kilitle(int i) {
    if (i == 0) { flag0 = true; turn = 1;
      while (flag1 && turn == 1) Thread.onSpinWait(); }
    else        { flag1 = true; turn = 0;
      while (flag0 && turn == 0) Thread.onSpinWait(); }
  }
  static void birak(int i) {
    if (i == 0) flag0 = false; else flag1 = false;
  }
  /* main: i = 0 ve i = 1 için iki iş parçacığı,
     her biri 100_000 kez: kilitle(i); sayac++; birak(i);
     ikisi join edilir, sayac yazdırılır */
}

Kodda iki bayrak ayrı alanlardır ve turn de volatile'dır. Thread.onSpinWait() (Java 9 ve sonrası) işlemciye “meşgul bekliyorum” ipucu verir; x86'da pause komutuna dönüşür. Bu komut döngünün güç tüketimini ve aynı çekirdeği paylaşan donanım iş parçacığına verdiği zararı azaltır. Sunumdaki kodun main kısmı yorum olarak özetlenmişti; çalıştırılabilir tam hâli şöyledir:

public class Peterson {
  static volatile boolean flag0, flag1;
  static volatile int turn;
  static int sayac = 0;

  static void kilitle(int i) {
    if (i == 0) { flag0 = true; turn = 1;
      while (flag1 && turn == 1) Thread.onSpinWait(); }
    else        { flag1 = true; turn = 0;
      while (flag0 && turn == 0) Thread.onSpinWait(); }
  }
  static void birak(int i) {
    if (i == 0) flag0 = false; else flag1 = false;
  }
  public static void main(String[] a) throws InterruptedException {
    Thread[] t = new Thread[2];
    for (int k = 0; k < 2; k++) {
      final int i = k;
      t[k] = new Thread(() -> {
        for (int n = 0; n < 100_000; n++) { kilitle(i); sayac++; birak(i); }
      });
    }
    for (Thread x : t) x.start();
    for (Thread x : t) x.join();
    System.out.println("sayac = " + sayac);
  }
}

Program JDK 21 ile üç kez çalıştırıldı ve her seferinde şu çıktıyı verdi:

sayac = 200000
sayac = 200000
sayac = 200000

Sayaç bu kez her çalıştırmada 200 000'dir: kritik bölge korunmuştur. Aynı sayacın korumasız sürümü ise her çalıştırmada farklı ve daha küçük değerler veriyordu. Bu programın tek bir zamanlamada doğru çalışması kanıt değildir; doğruluğun güvencesi Java bellek modelinin volatile için verdiği sıralı tutarlılık garantisidir.

6.4.5Senkronizasyon bariyeri

“Bariyer” sözcüğü senkronizasyonda iki farklı kavramın adıdır. Bellek bariyeri, tek bir çekirdeğin bellek erişimlerinin sırasını zorlar. Senkronizasyon bariyeri (barrier) ise bir süreç grubunu belli bir noktada buluşturur.

Fazlara bölünmüş paralel hesaplar bu buluşmaya ihtiyaç duyar. Bir ızgara simülasyonunda her süreç ızgaranın bir dilimini hesaplar. Bir sonraki faz, komşu dilimlerin bu fazdaki değerlerini kullanır. Bu yüzden hiçbir süreç, ötekiler bu fazı bitirmeden sonraki faza geçmemelidir. Fazı bitiren süreç barrier_wait() çağırır ve bloke olur. N'inci süreç geldiğinde bariyer açılır ve hepsi sonraki faza birlikte geçer (Şekil 6.12).

POSIX'te bu iş için pthread_barrier_wait, Java'da CyclicBarrier vardır. Aşağıdaki Java parçasında üç iş parçacığı iki faz hesaplar. Bariyere verilen ikinci argüman bir eylemdir; son iş parçacığı geldiğinde, bariyer açılmadan önce bir kez çalışır.

var b = new CyclicBarrier(3,
  () -> System.out.println(
          "faz " + faz[0]++ + " tamam"));
/* 3 iş parçacığı, her biri:
   for (f = 0; f < 2; f++) {
     hesapla(f); b.await();
   } */

Tam program her iş parçacığına fazlar arasında rastgele süre uyutarak JDK 21 ile çalıştırıldı:

import java.util.concurrent.CyclicBarrier;
public class Bariyer {
  public static void main(String[] a) throws Exception {
    int[] faz = {0};
    var b = new CyclicBarrier(3,
      () -> System.out.println(
              "faz " + faz[0]++ + " tamam"));
    Thread[] t = new Thread[3];
    for (int k = 0; k < 3; k++) {
      t[k] = new Thread(() -> {
        try { for (int f = 0; f < 2; f++) { Thread.sleep((long) (Math.random() * 20)); b.await(); } }
        catch (Exception e) { }
      });
      t[k].start();
    }
    for (Thread x : t) x.join();
  }
}

Çıktı her çalıştırmada aynıdır, çünkü eylem her fazda tam bir kez ve yalnız bütün iş parçacıkları geldikten sonra çalışır:

faz 0 tamam
faz 1 tamam

İş parçacıklarının bariyere hangi sırayla vardığı ise her çalıştırmada değişir. Programın çıktısı bu sıraya bağlı olmadığı için değişkenlik dışarıdan görünmez.

6.5Donanım desteği

Yazılım çözümlerinin ortak sorunu, bir değeri okumak ile ona yazmanın iki ayrı adım olmasıdır. Arada her şey olabilir. Donanım bu boşluğu kapatmak için bir bellek sözcüğünü kesintisiz olarak sınayıp değiştiren komutlar sunar. Bu komutlar bütün kilitlerin, semaforların ve kilitsiz veri yapılarının temelidir.

6.5.1Atomik donanım komutları

Silberschatz bu komutların davranışını C benzeri bir fonksiyonla tanımlar. Aşağıdaki test_and_set fonksiyonunun üç satırı gerçekte tek bir makine komutudur:

/* tümü TEK atomik komuttur */
bool test_and_set(bool *hedef) {
  bool eski = *hedef;
  *hedef = true;
  return eski;
}

/* kullanım: basit spinlock */
bool lock = false;
while (test_and_set(&lock))
  ;            /* meşgul bekle */
/* kritik bölge */
lock = false;

Fonksiyon hedefin eski değerini döndürür ve hedefe her durumda true yazar. Kilit boşsa (false) çağıran false alır ve kilit artık true'dur: kilit alınmıştır. Kilit doluysa çağıran true alır ve hiçbir şey değişmez: döngü yeniden dener. Kilit değişkenindeki “sınama ile atama arası” pencere ortadan kalkmıştır.

Atomiklik çok çekirdekte de geçerlidir. Eski işlemciler komut boyunca bellek veriyolunu kilitlerdi. Bugün önbellek tutarlılığı protokolü, ilgili önbellek satırını komut süresince tek bir çekirdeğe ayırır; öteki çekirdekler bu sürede o satıra erişemez. Tablo 6.5 yaygın mimarilerdeki karşılıkları verir.

ARM ve RISC-V'deki LL/SC çifti farklı bir yoldan aynı sonuca varır. LDXR (load-linked) değeri okur ve adresi izlemeye alır. STXR (store-conditional) ancak araya başka bir yazma girmemişse yazar; girmişse başarısız olur ve kod yeniden dener.

6.5.2TSL ile kritik bölge

Tanenbaum aynı fikri TSL (test and set lock) adlı bir komutla anlatır. TSL REGISTER,LOCK, LOCK sözcüğünü yazmaca okur ve LOCK'a 1 yazar; ikisini tek bölünmez adımda yapar. Kritik bölgeye giriş ve çıkış birkaç satırlık bir assembly koduyla yazılır:

enter_region:
  TSL REGISTER,LOCK  | R = LOCK; LOCK = 1
  CMP REGISTER,#0    | LOCK 0 mıydı?
  JNE enter_region   | değilse: tekrar dene
  RET                | kritik bölgeye girildi

leave_region:
  MOVE LOCK,#0       | LOCK = 0
  RET

enter_region, LOCK'un eski değerini sınar. Değer 0 idiyse kilit boştu ve artık bu çekirdeğe aittir; fonksiyon döner. Değer 0 değilse kilit doludur ve döngü baştan dener. leave_region kilidi sıradan bir yazmayla 0 yapar. Tablo 6.6 iki işlemcinin aynı anda girmeye çalıştığı bir senaryoyu izler.

Üçüncü adım önemlidir. CPU 1'in TSL'i de LOCK'a 1 yazar; ama değer zaten 1 olduğu için bir şey değişmez. CPU 1'in yazmacına gelen 1, “kilit doluydu” bilgisidir. İki işlemci hiçbir an birlikte içeride değildir. TSL çok çekirdekte de çalışır: kesme kapatmanın aksine öteki işlemcilerin o sözcüğe erişimini de engeller (Tanenbaum MOS Şekil 2-25).

6.5.3XCHG komutu

XCHG iki işlenenin içeriğini tek adımda takas eder. Yazmaca önce 1 konur, sonra yazmaç LOCK ile takas edilir. Takastan sonra LOCK her durumda 1'dir ve yazmaçta LOCK'un eski değeri vardır (Şekil 6.13). Etki TSL ile aynıdır.

enter_region:
  MOVE REGISTER,#1    | yazmaca 1 koy
  XCHG REGISTER,LOCK  | yazmaç ile LOCK'u takas et
  CMP REGISTER,#0     | LOCK 0 mıydı?
  JNE enter_region    | değilse: döngü
  RET                 | kritik bölgeye girildi
leave_region:
  MOVE LOCK,#0        | LOCK = 0
  RET

Intel x86 işlemcilerinde kilitleme için kullanılan temel komut budur. Bellek işlenenli XCHG örtük olarak LOCK önekli sayılır, yani her zaman atomiktir. C11'deki karşılığı atomic_exchange(&lock, 1) çağrısıdır.

6.5.4compare_and_swap ile kilit

En esnek atomik komut karşılaştır ve değiştirdir (compare-and-swap, CAS). Komut üç işlenen alır: bir adres, beklenen değer ve yeni değer. Adresteki değer beklenene eşitse yeni değeri yazar. Her durumda adresteki eski değeri döndürür.

int compare_and_swap(int *v, int bekl, int yeni) {
  int eski = *v;          /* üç satır birlikte */
  if (eski == bekl)       /* TEK atomik komut  */
    *v = yeni;
  return eski;
}

int lock = 0;
void gir(void) {
  while (compare_and_swap(&lock, 0, 1) != 0)
    ;                     /* meşgul bekle */
}
void cik(void) { lock = 0; }

Kilit olarak kullanıldığında beklenen değer 0, yeni değer 1'dir. Kilit boşsa CAS 1 yazar ve 0 döndürür: döngü biter. Kilit doluysa CAS hiçbir şey yazmaz ve 1 döndürür: döngü sürer. İzleme şöyle ilerler:

1. Kilit boş. lock = 0.
2. T0 kazanır. T0'ın CAS'ı lock'u 0 bulur, 1 yazar ve 0 döndürür. T0 döngüden çıkar ve kritik bölgeye girer.
3. T1 kaybeder. T1'in CAS'ı 1 bulur. Bu beklenen değer değildir; hiçbir şey yazmaz ve 1 döndürür.
4. T1 bekler. T1 meşgul bekler; her deneme bellek sözcüğünü değiştirmeden döner.
5. T0 çıkar. T0 kilidi 0 yapar. Gerçek kodda bu yazma release sıralamalı yapılır.
6. T1 girer. T1'in sıradaki CAS'ı başarılı olur.

x86'da CAS'ın karşılığı LOCK CMPXCHG'dir. C11'de atomic_compare_exchange_strong, Java'da AtomicInteger.compareAndSet aynı işi yapar (Silberschatz 10e §6.4.2).

6.5.5CAS ile atomik artırma

CAS kilit kurmanın ötesinde, kilit kullanmadan güncelleme yapmayı da sağlar. Paylaşılan bir sayacı artırmak için iş parçacığı önce değeri okur. Sonra CAS ile “değer hâlâ okuduğum gibiyse bir fazlasını yaz” der. Arada başka biri değeri değiştirdiyse CAS başarısız olur ve döngü güncel değerle yeniden dener.

void artir(atomic_int *v) {
  int temp;
  do {
    temp = *v;              /* oku              */
  } while (temp != compare_and_swap(v, temp, temp + 1));
}                           /* değişmediyse yaz */

/* C11 tek satır: atomic_fetch_add(v, 1); */

Bu “oku → hesapla → CAS → başarısızsa yeniden dene” döngüsü, kilitsiz veri yapılarının temel kalıbıdır. C11 aynı artırmayı tek satırla yapar: atomic_fetch_add(v, 1). x86 bunu döngüsüz tek bir LOCK XADD komutuyla yürütür.

6.5.6Sınırlı beklemeli CAS kilidi

Basit CAS kilidinin eksiği sınırlı beklemeydi. Silberschatz bu eksiği bir waiting[n] dizisiyle giderir. Bekleyen her süreç kendi bayrağını kaldırır. Kritik bölgeden çıkan süreç kilidi doğrudan bırakmaz; önce süreçleri halka sırasıyla, kendinden sonrakinden başlayarak tarar. İlk bekleyeni bulursa kilidi ona devreder.

while (true) {
  waiting[i] = true;
  key = 1;
  while (waiting[i] && key == 1)
    key = compare_and_swap(&lock, 0, 1);
  waiting[i] = false;
  /* kritik bölge */
  j = (i + 1) % n;
  while ((j != i) && !waiting[j])
    j = (j + 1) % n;
  if (j == i)
    lock = 0;            /* bekleyen yok */
  else
    waiting[j] = false;  /* sırayı devret */
  /* kalan bölüm */
}

Kodun en ince yeri devretme adımıdır. Çıkan süreç bekleyen P_j'yi bulunca lock'a dokunmaz; yalnız waiting[j] = false yapar. P_j'nin döngü koşulu waiting[j] && key == 1 olduğu için P_j döngüden çıkar ve girer. Kilit bu sırada hep 1'de kalır, yani araya başka biri giremez. Kilit ancak bekleyen kimse yoksa gerçekten bırakılır (lock = 0).

Halka taraması sınırlı beklemeyi garanti eder. Bekleyen bir süreç, kendisinden önce taranacak en fazla n − 1 süreç kadar giriş bekler. Tablo 6.8 dört süreçlik bir senaryoyu izler. Bu kodda satır numaraları şöyledir: 2 bayrak kaldırma, 3–4 bekleme döngüsü, 5 bayrak indirme, 7–9 tarama, 10–13 bırakma ya da devretme.

/* P_i; n = 4 süreç */
waiting[i] = true; key = 1;
while (waiting[i] && key == 1)
  key = compare_and_swap(&lock, 0, 1);
waiting[i] = false;
/* kritik bölge */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
  j = (j + 1) % n;
if (j == i)
  lock = 0;            /* bekleyen yok */
else
  waiting[j] = false;  /* sırayı devret */

Dokuzuncu adım ilginçtir. P0, P3'ten önce gelmişti ama halka sırası P3'ü önce seçti. Bu kilit gelme sırasına göre (FIFO) çalışmaz; yalnız bekleyişin bir üst sınırı olmasını sağlar. P2 çıkarken tarama kendinden sonraki j = 3'ten başladığı için P3 öne geçmiştir. Yine de P0 en fazla n − 1 = 3 giriş bekler. Kilidin gerçekten boşaldığı tek an 11. adımdır.

6.6Kilitler

Atomik komutlar kendi başlarına kullanışsızdır; programcılar onları doğrudan değil, üzerlerine kurulmuş araçlar aracılığıyla kullanır. Bu kesim bu araçların en temel olanlarını ele alır: atomik değişkenler, spinlock ve mutex. Ardından kilit kullanan veri yapılarının nasıl ölçeklendirildiğine bakar.

6.6.1Atomik değişkenler

Dil ve kütüphaneler atomik komutları atomik değişkenler olarak sunar. C11'de _Atomic türündeki bir değişkene yapılan her erişim atomiktir ve varsayılan olarak sıralı tutarlıdır (seq_cst). Bu türde sayac++ ifadesi bile atomiktir; x86'da lock xadd, ARMv8.1'de ldadd komutuna derlenir.

class="kw">#include <stdatomic.h>
atomic_int sayac = 0;     /* _Atomic int */

void *is(void *arg) {
  for (int n = 0; n < 100000; n++)
    atomic_fetch_add(&sayac, 1);
  return NULL;
}
/* 2 iş parçacığı + join → 200000 */

Java'nın karşılığı java.util.concurrent.atomic paketidir. AtomicInteger.incrementAndGet() atomik artırma, compareAndSet(beklenen, yeni) ise doğrudan CAS'tır:

static AtomicInteger atom = new AtomicInteger();
/* iki iş parçacığı, her biri 100_000 kez: */
atom.incrementAndGet();

var v = new AtomicInteger(5);
v.compareAndSet(5, 6);   /* true,  v = 6 */
v.compareAndSet(5, 7);   /* false, v = 6 */

Sunumdaki parçalar tek bir programda birleştirildi. Program aynı sayacı ayrıca synchronized bir metotla da artırır:

import java.util.concurrent.atomic.AtomicInteger;
public class Atom {
  static AtomicInteger atom = new AtomicInteger();
  static int duz = 0;
  static synchronized void artir() { duz++; }
  public static void main(String[] a) throws InterruptedException {
    Runnable is = () -> { for (int n = 0; n < 100_000; n++) { atom.incrementAndGet(); artir(); } };
    Thread t1 = new Thread(is), t2 = new Thread(is);
    t1.start(); t2.start(); t1.join(); t2.join();
    System.out.println("AtomicInteger = " + atom.get());
    System.out.println("synchronized  = " + duz);
    var v = new AtomicInteger(5);
    System.out.println(v.compareAndSet(5, 6) + " " + v.get());
    System.out.println(v.compareAndSet(5, 7) + " " + v.get());
  }
}

JDK 21 ile üç kez çalıştırıldığında her seferinde aynı çıktıyı verdi:

AtomicInteger = 200000
synchronized  = 200000
true 6
false 6

İki yöntem de 200 000 sonucunu verir. compareAndSet(5, 6) değer 5 olduğu için başarılıdır. compareAndSet(5, 7) ise değer artık 6 olduğu için başarısızdır ve v 6'da kalır.

6.6.2Spinlock ve mutex

Bir kilit doluyken bekleyen iş parçacığının ne yapacağı iki ayrı kilit türü doğurur. Spinlock meşgul bekler: işlemciyi bırakmaz, kilidi sürekli sınar. Kilit boşalır boşalmaz bağlam değiştirme olmadan girer. Uyuyan mutex ise bekleyeni bloke eder; çekirdek işlemciyi başka bir iş parçacığına verir. Kilit boşalınca bekleyen uyandırılır.

Seçim, beklemenin ne kadar süreceğine bağlıdır. Kritik bölge iki bağlam değiştirmeden kısaysa dönmek uyumaktan ucuzdur. Kritik bölge uzunsa ya da içinde bloke olunabiliyorsa (örneğin disk okuması), dönmek işlemciyi boşa yakar. Tek çekirdekli bir makinede spinlock anlamsızdır: kilidi tutan iş parçacığı çalışamaz, çünkü işlemciyi dönen iş parçacığı kullanır. Bekleyen bütün dilimini yakar ve kilit ancak bir sonraki bağlam değiştirmede boşalabilir.

Gerçek mutex gerçeklemelerinin çoğu iki yöntemi birleştirir. Önce kısa bir süre döner, kilit bu sürede boşalmazsa uyur.

6.6.3Mutex nasıl yazılır: yield ve futex

Tanenbaum, kullanıcı düzeyi iş parçacıkları için TSL ile bir mutex yazar. Kod, TSL'li enter_region'a çok benzer. Tek farkı, kilit doluysa döngüye dönmek yerine thread_yield çağırmasıdır:

mutex_lock:
  TSL REGISTER,MUTEX | eskisini al, 1 yap
  CMP REGISTER,#0    | boş muydu?
  JZE ok             | evet: alındı
  CALL thread_yield  | hayır: CPU'yu ver
  JMP mutex_lock     | sonra yine dene
ok: RET
mutex_unlock:
  MOVE MUTEX,#0
  RET

Kullanıcı düzeyi iş parçacıklarında zamanlayıcı kesmesiyle iş parçacığı değiştirilmez. Meşgul bekleyen bir iş parçacığı işlemciyi hiç bırakmaz ve kilidi tutan iş parçacığı hiç çalışamaz. thread_yield işlemciyi aynı süreçteki öteki iş parçacıklarına verir; kilidin sahibi çalışıp kilidi bırakabilir (Tanenbaum Şekil 2-29).

Linux'taki çözüm futex'tir (fast userspace mutex). Kilit, kullanıcı alanında bir tamsayı sözcüğüdür. Çekişme yoksa kilit yalnız bir atomik komutla alınıp bırakılır; çekirdeğe hiç girilmez. Çekirdek ancak bir iş parçacığının gerçekten uyuması gerektiğinde devreye girer. glibc'nin pthread_mutex'i, Java kilitleri ve Go'nun eş zamanlılık araçları bu mekanizmanın üstüne kuruludur. Ulrich Drepper'ın “Futexes Are Tricky” makalesindeki yaygın tasarımda sözcüğün üç değeri vardır: 0 boş, 1 kilitli ve bekleyen yok, 2 kilitli ve bekleyen olabilir.

1. Çekişme yok. T1 sözcüğü tek bir CAS ile 0'dan 1'e çevirir. Sistem çağrısı yapılmaz.
2. T2 gelir. T2 kilidi dolu bulur, değeri 2 (“bekleyen var”) yapar ve futex_wait sistem çağrısıyla çekirdekteki bekleme kuyruğunda uyur.
3. T1 bırakır. T1 sözcüğü 0 yapar. Eski değer 2 olduğu için futex_wake çağırır.
4. T2 uyanır. T2 sözcüğü atomik takasla (xchg) yine 2 yapar. Takasın döndürdüğü eski değer 0 olduğu için kilit artık T2'nindir. T2 başka bekleyen olup olmadığını bilemez; bu yüzden değeri temkinli olarak 1 değil 2 yapar.

Değer 1 ile 2'nin ayrılmasının nedeni, gereksiz futex_wake çağrılarından kaçınmaktır. Değer 1 ise kimse uyumuyordur ve bırakan iş parçacığı çekirdeğe hiç girmez. Uyanan iş parçacığının değeri 2 yapması ise bazen gereksiz bir futex_wake çağrısına yol açar; ama hiçbir bekleyenin unutulmamasını güvenceye alır. Böylece çekişmesiz durumda alma ve bırakma birer atomik komuttan ibarettir.

6.6.4Ölçeklenebilir sayaç

Tek bir kilitle korunan bir sayaç doğrudur ama ölçeklenmez. Her artış aynı kilit için yarışır ve aynı önbellek satırı çekirdekler arasında sürekli taşınır. Çekirdek sayısı arttıkça toplam süre kısalmaz, uzar. Arpaci-Dusseau'ların yaklaşık sayacı bu sorunu çekirdek başına sayımla çözer. Her çekirdeğin kendi yerel sayacı ve kendi kilidi vardır. Yerel sayaç bir S eşiğine ulaşınca değeri genel sayaca aktarılır.

typedef struct {
  int global;      pthread_mutex_t gkilit;
  int yerel[NCPU]; pthread_mutex_t ykilit[NCPU];
  int S;                     /* aktarma eşiği */
} ycount_t;

void ekle(ycount_t *c, int cpu) {
  pthread_mutex_lock(&c->ykilit[cpu]);
  c->yerel[cpu]++;
  if (c->yerel[cpu] >= c->S) {        /* aktar */
    pthread_mutex_lock(&c->gkilit);
    c->global += c->yerel[cpu];
    pthread_mutex_unlock(&c->gkilit);
    c->yerel[cpu] = 0;
  }
  pthread_mutex_unlock(&c->ykilit[cpu]);
}
int oku(ycount_t *c) {             /* yaklaşık */
  pthread_mutex_lock(&c->gkilit);
  int v = c->global;
  pthread_mutex_unlock(&c->gkilit);
  return v;
}

ekle yalnız çağıran çekirdeğin yerel kilidini alır. Farklı çekirdekler farklı kilitler kullandığı için birbirlerini beklemez. Genel kilit yalnız aktarma sırasında, yani her S artışta bir alınır. oku yalnız genel sayacı döndürür; bu yüzden sonuç yaklaşıktır.

En kötü durumda her yerel sayaç S − 1'de durur ve hiç aktarılmamıştır. Bu yüzden oku() gerçek değerden en fazla NCPU × (S − 1) kadar geride kalabilir; örnekte 4 × 3 = 12'dir. S, doğruluk ile ölçeklenme arasındaki ödünleşimi belirler. Büyük S genel kilide seyrek gider ve iyi ölçeklenir ama okunan değer daha geride kalır. S = 1'de her artış genel sayaca gider: sonuç kesindir ama sayaç tek kilitli sayaç kadar yavaştır. Linux çekirdeğindeki percpu_counter aynı fikre dayanır.

6.6.5Eş zamanlı veri yapılarında kilit düzeni

Bir veri yapısını iş parçacığı güvenli yapmanın en kolay yolu, her işlemi tek bir kilitle sarmaktır. Bu yol doğrudur ama bütün işlemleri sıraya sokar. Kilidi bölmek paralelliği artırabilir; Tablo 6.11 yaygın düzenleri özetler.

Michael ve Scott'ın 1996'da yayımladığı iki kilitli kuyruk, kilit bölmenin güzel bir örneğidir. Kuyruğun başında her zaman bir kukla düğüm bulunur. Başlangıçta baş da kuyruk ucu da bu kuklayı gösterir. ekle yalnız kuyrukKilit'i alır ve kuyruk ucunu ilerletir. çıkar yalnız başKilit'i alır: eski kuklayı serbest bırakır, ilk gerçek düğümün değerini döndürür ve o düğüm yeni kukla olur (Şekil 6.18). Kukla düğüm sayesinde iki işlem hiçbir zaman aynı düğümü değiştirmez.

Pratik kural şudur: kod önce tek kilitle doğru yazılır. Ölçüm kilidin gerçekten darboğaz olduğunu gösterirse kilit bölünür. Daha çok kilit her zaman daha hızlı demek değildir. Her kilit ek bir atomik komut ve kilitlenme riski getirir.

6.7Semaforlar

Mutex yalnız “bir kişi girsin” der. Pek çok eşgüdüm sorunu ise daha fazlasını ister: N özdeş kaynaktan birini almak ya da bir olay gerçekleşene kadar beklemek gibi. Dijkstra'nın semaforu bu iki ihtiyacı da tek bir araçla karşılar.

6.7.1Semafor

Semaforun değeri, kullanılabilir kaynak sayısı gibi düşünülebilir. Değer 3 ise üç süreç daha beklemeden geçebilir. P ve V harfleri Dijkstra'nın Felemenkçe sözcüklerinden gelir; Tanenbaum down ve up, Silberschatz wait ve signal adlarını kullanır.

wait ve signal'ın kendileri de birer kısa kritik bölgedir: değeri okuyup değiştirirler. İşletim sistemi bu iki işlemi tek çekirdekte kesmeleri kapatarak, çok çekirdekte bir spinlock ile korur. Meşgul bekleme böylece tamamen ortadan kalkmaz; ama uygulamanın uzun kritik bölgesinden semafor işleminin birkaç komutuna iner. Değer 0 iken down çağıran süreç gerçek sistemlerde uyur. Kitaplarda görülen meşgul bekleyen sürüm yalnız kavramsal ilk tanımdır.

6.7.2Bekleme kuyruklu semafor

Silberschatz'ın gerçeklemesinde semafor bir değer ve bekleyen süreçlerin listesinden oluşur:

typedef struct {
  int value;
  struct process *list;
} semaphore;

void wait(semaphore *S) {     /* P / down */
  S->value--;
  if (S->value < 0) {
    ekle(S->list, bu_surec);
    sleep();                   /* bloke ol */
  }
}
void signal(semaphore *S) {   /* V / up */
  S->value++;
  if (S->value <= 0) {
    P = cikar(S->list);        /* FIFO */
    wakeup(P);
  }
}

Bu gerçeklemede wait önce değeri azaltır, sonra sınar. Bu yüzden değer negatif olabilir. Değer −k ise k süreç kuyrukta bekliyordur (Şekil 6.19). signal değeri artırır; sonuç hâlâ 0 ya da negatifse kuyrukta bekleyen vardır ve baştaki uyandırılır.

Kuyruğun sırası semaforun tanımında belirtilmez. FIFO kuyruk kullanılırsa her bekleyen sonunda sıra alır ve bekleme sınırlıdır. Başka bir sıra (örneğin LIFO ya da önceliğe göre) açlığa yol açabilir. Tanenbaum'un tanımında ise değer hiç negatif olmaz: up, uyuyan biri varsa değeri artırmadan doğrudan birini uyandırır. İki tanım dışarıdan aynı davranışı verir; yalnız iç değerin okunuşu farklıdır.

6.7.3Kullanım kalıpları

Semaforun başlangıç değeri, onun hangi iş için kullanıldığını belirler:

• İkili semafor (mutex gibi). Başlangıç 1'dir. Her süreç wait … kritik bölge … signal yapar.
• Sayma semaforu. Başlangıç N'dir ve N özdeş kaynağı temsil eder: bir bağlantı havuzunun bağlantıları ya da bir tamponun boş yuvaları gibi. Örneğin bir veritabanına en fazla 5 bağlantı açılabiliyorsa semafor 5 ile başlar; altıncı istek bloke olur.
• Sinyal ya da sıralama. Başlangıç 0'dır ve bir olay gerçekleşene kadar beklemek için kullanılır. P2'nin S2 deyimi, P1'in S1 deyiminden sonra çalışmalıysa P1 S1'den sonra signal(synch), P2 S2'den önce wait(synch) yapar (Şekil 6.20).

Sıralama kalıbında olayın önce gerçekleşmesi sorun değildir. P1 önce signal yaparsa değer 1 olur; P2 sonra wait yaptığında beklemeden geçer. Semafor uyandırmayı bir sayaç olarak saklar ve hiçbir sinyal kaybolmaz. Bu özellik semaforu koşul değişkeninden ayıran en önemli farktır.

Semafor güçlü ama yapısal olmayan bir araçtır: doğruluk, her wait/signal çiftinin doğru yazılmasına bağlıdır. Tablo 6.13 tipik hataları listeler. Tek bir unutulmuş satır, derleyicinin hiç uyarmadığı ve testte nadiren görülen bir hata yaratır.

6.7.4Kod izleme: semaforla bariyer

Senkronizasyon bariyeri iki semafor ve bir sayaçla kurulabilir. mutex sayacı korur. turnike 0 ile başlar, yani kapalıdır. Son gelen iş parçacığı turnikeyi açar. Turnikeden geçen her iş parçacığı arkasındakini geçirir:

#define N 3
semaphore mutex = 1, turnike = 0;
int sayac = 0;
void bariyer(void) {
  down(&mutex);
  sayac = sayac + 1;
  if (sayac == N) up(&turnike); /* son */
  up(&mutex);
  down(&turnike);  /* turnikeden geç */
  up(&turnike);    /* arkadakini geçir */
}

Aşağıdaki izlemede Tanenbaum'un semafor anlamı kullanılır: up, uyuyan biri varsa değeri artırmadan onu uyandırır. Üç iş parçacığı A, B ve C sırayla bariyere gelir.

Altıncı adımda C turnikeyi açar ama bekleyen olduğu için değer artmaz; A uyandırılır. C de hemen arkasından turnikede uyur (adım 7), çünkü turnikeden ancak biri onu geçirirse geçebilir. Turnike bir kişilik döner kapı gibi çalışır: her geçen, arkadakini geçirir. Son geçen C'nin up'ı kimseyi bulamaz ve değer 1 olur.

Üç iş parçacığının bütün ara yerleştirmeleri bir programla gezildi. Her yürütmede iş parçacıkları turnikeden ancak sayac = 3 olduktan sonra geçti ve hiçbir yürütme kilitlenmedi. Bu bariyer tek kullanımlıktır: sonunda turnike 1'de kalır ve sayaç 3'tür. Döngü içinde yeniden kullanmak için turnikenin yeniden kapatılması gerekir. Tekrar kullanılabilir sürüm iki turnike ister; Downey'nin kitabı bu sürümü ayrıntılı işler.

6.8Klasik problemler

Senkronizasyon araçları, gerçek sistemlerdeki pek çok durumun modeli olan birkaç klasik problemle sınanır. Yeni bir eşgüdüm mekanizması önerildiğinde bu problemleri ne kadar sade çözebildiğine bakılır.

6.8.1Üretici-tüketici problemi

İki süreç sabit boyutlu (N yuvalı) bir tamponu paylaşır. Üretici tampona öğe yazar, tüketici tampondan öğe okur. Tampon doluysa üretici, boşsa tüketici beklemelidir. Bu düzene sınırlı tampon (bounded buffer) denir. Tampon sınırsız olsaydı yalnız tüketici beklerdi. Tampon dairesel bir dizidir: in üreticinin yazacağı, out tüketicinin okuyacağı yuvayı gösterir ve ikisi de (i + 1) % N ile ilerler.

Örnekte üretici önce A, B ve C'yi 0, 1 ve 2 numaralı yuvalara koyar; in = 3 olur. Tüketici A'yı alır: out = 1, count = 2. Üretici D…I öğelerini 3–7 ve 0 numaralı yuvalara koyar; in başa sarıp 1 olur ve count = 8 = N'dir. Tüketici B ile C'yi alınca out = 3, count = 6 olur ve üretici yeniden yazabilir.

6.8.2Ölümcül yarış: kayıp uyandırma

İlk akla gelen çözüm, ortak bir count sayacı ile sleep ve wakeup çağrılarını kullanır. sleep() çağıranı bloke eder; wakeup(p) uyuyan p'yi hazır yapar. Tanenbaum'un kodu şöyledir:

#define N 100
int count = 0;
void producer(void) {
    while (TRUE) {
        item = produce_item();
        if (count == N) sleep();
        insert_item(item);
        count = count + 1;
        if (count == 1) wakeup(consumer);
    }
}
void consumer(void) {
    while (TRUE) {
        if (count == 0) sleep();
        item = remove_item();
        count = count - 1;
        if (count == N - 1) wakeup(producer);
        consume_item(item);
    }
}

Kod masum görünür ama ölümcül bir yarış içerir. Aşağıdaki sırada iki süreç de sonsuza dek uyur:

1. Tampon boştur. Tüketici count'u okur: 0. Tam sleep() çağıracakken kesilir.
2. Üretici bir öğe üretir ve tampona koyar; count 1 olur.
3. count == 1 olduğu için üretici tüketicinin uyuduğunu varsayar ve wakeup(consumer) gönderir. Tüketici henüz uyumadığı için sinyal kaybolur.
4. Tüketici kaldığı yerden sürer. Eski kararına göre sleep() çağırır ve uyur.
5. Üretici tamponu doldurur; tüketici uyuduğu için kimse okumaz. count == N olunca üretici de uyur.

Sorun, count sınaması ile sleep çağrısının bölünmez olmamasıdır. Arada gelen uyandırma, uyuyan kimse olmadığı için iz bırakmadan kaybolur. Semafor bu sorunu çözer: uyandırmayı bir sayaç olarak sakladığı için, önce gelen bir up sonraki down'u beklemeden geçirir (Tanenbaum MOS Şekil 2-27).

6.8.3Semaforlarla sınırlı tampon

Doğru çözüm üç semafor kullanır:

#define N 100
semaphore mutex = 1;  /* tampona erişim     */
semaphore empty = N;  /* boş yuva sayısı    */
semaphore full  = 0;  /* dolu yuva sayısı   */

void producer(void) {
  while (true) {
    item = produce_item();
    down(&empty);   /* boş yuva bekle   */
    down(&mutex);   /* KB'ye gir        */
    insert_item(item);
    up(&mutex);     /* KB'den çık       */
    up(&full);      /* dolu sayısı + 1  */
  }
}

void consumer(void) {
  while (true) {
    down(&full);    /* dolu yuva bekle  */
    down(&mutex);
    item = remove_item();
    up(&mutex);
    up(&empty);     /* boş sayısı + 1   */
    consume_item(item);
  }
}

• mutex = 1 tampona erişimi karşılıklı dışlar. 0 ile başlasaydı hiç kimse giremezdi.
• empty = N boş yuvaları sayar. Tampon doluyken üretici down(&empty)'de bloke olur.
• full = 0 dolu yuvaları sayar. Tampon boşken tüketici down(&full)'de bloke olur.

mutex dışlama, empty ve full ise sıralama (senkronizasyon) görevi görür. İki görev ayrı semaforlarla yapılır.

Dört öğeli bir senaryonun bütün ara yerleştirmeleri bir programla gezildi: öğeler hep A, B, C, D sırasıyla alındı, tampon hiç taşmadı ve kilitlenme olmadı.

6.8.4down sırası değişirse

Çözümün doğruluğu iki down'ın sırasına bağlıdır. Üreticide sıra ters çevrilirse ne olur?

void producer(void) {
  while (true) {
    item = produce_item();
    down(&mutex);  /* ← önce */
    down(&empty);  /* ← sonra */
    insert_item(item);
    up(&mutex);
    up(&full);
  }
}

1. Tampon tamamen doludur: empty = 0.
2. Üretici önce mutex'i alır, sonra down(&empty)'de uyur. Mutex hâlâ elindedir.
3. Tüketici down(&full)'ü geçer ama down(&mutex)'te uyur. Oysa up(&empty) yapacak olan oydu.
4. Herkes ötekini bekler: kilitlenme.

Programla yapılan durum uzayı taramasında da kilitlenen bir durum bulunur: mutex = 0, empty = 0 ve tamponda iki öğe. Kural şudur: önce sayma semaforu, sonra mutex beklenir; mutex tutulurken uyunmaz. up'ların sırası ise önemsizdir, çünkü up hiçbir zaman bloke olmaz.

6.8.5Okur-yazar problemi

Bir veritabanını birçok süreç paylaşır. Okurlar veriyi yalnız okur, yazarlar değiştirir. Okurlar birbirini dışlamak zorunda değildir: on okur aynı anda okuyabilir. Ama bir yazar yazarken ne başka bir yazar ne de bir okur içeride olmalıdır. Tanenbaum'un çözümü iki semafor ve bir sayaç kullanır:

semaphore mutex = 1;  /* rc'yi korur        */
semaphore db = 1;     /* veritabanını korur */
int rc = 0;           /* okuyan sayısı      */

void writer(void) {
  while (true) {
    think_up_data();
    down(&db);  write_data_base();  up(&db);
  }
}
void reader(void) {
  while (true) {
    down(&mutex);
    if (++rc == 1) down(&db);  /* ilk okur  */
    up(&mutex);
    read_data_base();
    down(&mutex);
    if (--rc == 0) up(&db);    /* son okur  */
    up(&mutex);
    use_data_read();
  }
}

rc içerideki okur sayısıdır ve mutex onu korur. db veritabanını korur. Yazar doğrudan db'yi alır. Okurlardan yalnız ilk giren db'yi alır (++rc == 1) ve yalnız son çıkan bırakır (--rc == 0). Aradaki okurlar db'ye hiç dokunmadan girip çıkar.

Çözüm dışlamayı doğru sağlar. İki okur ve bir yazarın bütün ara yerleştirmeleri gezildiğinde yazar ile bir okurun birlikte içeride olduğu bir durum çıkmadı; iki okur ise birlikte okuyabildi. Ama çözümün ciddi bir zayıflığı vardır (Şekil 6.24):

1. R1 girer ve db'yi alır.
2. Bir yazar gelir ve down(&db)'de bekler.
3. Yeni okur R2 db'ye dokunmadan girer: rc = 2.
4. R1 çıkarken R3 gelir. rc 1'e inip yeniden 2 olur; hiç 0 olmaz.
5. Okur akışı örtüşerek sürdükçe up(&db) hiç çağrılmaz ve yazar süresiz bekler.

Bu çözüm okur önceliklidir ve yazar açlığına açıktır. Problemin varyantları farklı öncelikleri seçer (Tablo 6.16). Downey'nin açlıksız çözümünde gelen herkes önce bir turnikeden geçer. Bekleyen yazar turnikeyi tutar ve arkasından yeni okur giremez:

/* Downey: açlıksız çözüm */
/* yazar */
wait(turnike);
wait(odaBos);
  yaz();
signal(turnike);
signal(odaBos);

/* okur */
wait(turnike); signal(turnike);
/* ilk okur odaBos'u alır,
   son okur bırakır (rc ile) */
  oku();

6.8.6Yemek yiyen filozoflar

Dijkstra 1965'te şu problemi ortaya koydu. Yuvarlak bir masada beş filozof oturur; aralarında beş çatal vardır. Her filozof düşünür, acıkınca sağındaki ve solundaki iki çatalı alıp yer. Problem, sınırlı kaynakların süreçler arasında kilitlenmesiz ve açlıksız paylaştırılmasının modelidir. Naif çözüm her çatalı bir semaforla korur:

semaphore catal[5];        /* hepsi 1 */

void filozof(int i) {
  while (true) {
    dusun();
    wait(&catal[i]);             /* sol */
    wait(&catal[(i + 1) % 5]);   /* sağ */
    ye();
    signal(&catal[(i + 1) % 5]);
    signal(&catal[i]);
  }
}

Hepsi aynı anda acıkır ve sol çatalını alırsa her filozof sağ çatalı bekler ve kimse bırakmaz: kilitlenme (Şekil 6.25). Her çatal semaforla korunsa bile çözüm yanlıştır. Beş filozofun bütün ara yerleştirmeleri gezildiğinde tam bu durum bulunur: beşi de ilk wait'i geçmiş, bütün çatal semaforları 0'dır.

Dört çözüm yolu vardır:

• Masaya en fazla dört. Başlangıcı 4 olan bir oda semaforu, aynı anda en fazla dört filozofun çatal almaya çalışmasına izin verir. Beş çatal dört kişiye dağıldığında en az biri iki çatala ulaşır ve döngüsel bekleme kırılır.
• Kaynak sıralaması (asimetri). Her filozof önce numarası küçük çatalı alır. F4'ün çatalları 4 ve 0'dır; F4 önce 0'ı ister. Genel kural: kilitler hep aynı global sırayla alınır.
• İki çatalı birlikte almak. Tanenbaum'un çözümü bir durum dizisi ve filozof başına bir semafor kullanır. Filozof ancak iki komşusu da yemiyorsa yemeye geçer.
• Monitör. Silberschatz'ın çözümü pickup(i) ve putdown(i) prosedürleri ile filozof başına bir koşul değişkeni (self[i]) kullanır; mantığı Tanenbaum'unkiyle aynıdır.

Tanenbaum'un çözümü aşağıdadır. Her filozofun durumu THINKING, HUNGRY ya da EATING olabilir. s[i] semaforları 0 ile başlar; LEFT ve RIGHT komşuların numaralarıdır.

void take_forks(int i) {
  down(&mutex);
  state[i] = HUNGRY;
  test(i);
  up(&mutex);
  down(&s[i]);    /* çatal yoksa bloke */
}
void put_forks(int i) {
  down(&mutex);
  state[i] = THINKING;
  test(LEFT);     /* (i+4) % 5 */
  test(RIGHT);    /* (i+1) % 5 */
  up(&mutex);
}
void test(int i) {
  if (state[i] == HUNGRY && state[LEFT] != EATING
                         && state[RIGHT] != EATING) {
    state[i] = EATING;
    up(&s[i]);
  }
}

take_forks durumu HUNGRY yapar ve test(i) çağırır. Komşular yemiyorsa test durumu EATING yapar ve up(&s[i]) ile filozofa izin verir; sonraki down(&s[i]) hemen geçer. Komşulardan biri yiyorsa izin verilmez ve filozof down(&s[i])'de uyur. put_forks durumu THINKING yapar ve iki komşuyu sınar: bekleyen bir komşu artık yiyebiliyorsa onu uyandırır.

Beş filozofun bütün ara yerleştirmeleri bir programla gezildi. Hiçbir yürütmede kilitlenme olmadı, iki komşu hiçbir zaman birlikte yemedi ve aynı anda en fazla iki filozof yedi. İki sayısı rastgele değildir: yiyen her filozof iki çatal tutar ve yan yana iki filozof aynı anda yiyemez. n filozoflu bir masada aynı anda en fazla ⌊n/2⌋ filozof yiyebilir; beş için 2, yedi için 3'tür.

6.9Monitörler

Semaforla yazılan kodun doğruluğu her wait/signal çiftine bağlıdır ve iki down'ın yerini değiştirmek bile kilitlenme yaratır. Monitör, bu hata sınıfını programlama dili düzeyinde azaltmak için geliştirildi.

6.9.1Monitör

monitor ornek
  integer i;
  condition c;
  procedure uretici(); … end;
  procedure tuketici(); … end;
end monitor;

Süreçler monitörün prosedürlerini çağırabilir ama iç verisine doğrudan erişemez. Karşılıklı dışlamayı programcı değil derleyici sağlar: her prosedürün başına ve sonuna giriş kilidini derleyici ekler. Programcı kilidi almayı ya da bırakmayı unutamaz. Monitör doluysa çağıran süreç bir giriş kuyruğunda bekler (Şekil 6.27).

6.9.2Koşul değişkenleri

Dışlama yetmez; monitörün içindeki süreç bazen bir koşulun sağlanmasını beklemek zorundadır. Örneğin tüketici tamponu boş bulmuştur. Monitörü tutarak beklerse üretici hiç giremez. Bu yüzden monitörler koşul değişkenleri sunar.

1. P monitördedir; tampon boş olduğu için devam edemez. Q giriş kuyruğundadır.
2. P x.wait() çağırır: monitörü bırakır ve x kuyruğunda uyur. Böylece Q girebilir.
3. Q koşulu sağlar ve x.signal() çağırır; x kuyruğundan bir süreç uyanır. Kimin hemen çalışacağı ise anlamsal bir seçimdir.
4. x kuyruğunda kimse yokken x.signal() etkisizdir ve hiçbir iz bırakmaz.

Son adım, koşul değişkeni ile semafor arasındaki temel farktır. Semaforun signal'ı değeri artırır ve sonraki wait bu artışı kullanır; sinyal hatırlanır. Koşul değişkeninin ise değeri yoktur; yalnız bir kuyruktur. Bekleyen yoksa sinyal kaybolur. Bu yüzden beklenen koşul (örneğin count > 0) her zaman paylaşılan veride ayrıca tutulur ve beklemeden önce sınanır.

6.9.3Hoare ve Mesa anlamı

Q, x.signal() ile P'yi uyandırdığında monitörde iki süreç çalışmaya hazırdır. Ama içeride yalnız biri etkin olabilir. Hangisinin süreceği monitörün anlamını belirler:

• Signal-and-wait (Hoare). Uyanan P hemen çalışır; Q bir “acil” kuyrukta bekler. P, uyandığı anda koşulun doğru olduğundan emindir: beklemeyi bir if ile yazmak yeter.
• Signal-and-continue (Mesa, 1980). Q devam eder; P yalnız “hazır” olur ve monitörü yeniden almak için bekler. P çalışana kadar başka bir süreç koşulu bozabilir. P uyandığında koşulu yeniden sınamak zorundadır.

Gerçek sistemlerin neredeyse hepsi Mesa anlamını kullanır. Mesa anlamında ise signal yalnız bir “ipucudur”: koşul belki doğrudur, uyanan bunu kendisi sınar.

6.9.4Neden if değil while?

Mesa anlamında beklemenin if ile yazılması bir hatadır:

/* YANLIŞ (Mesa'da) */
lock(&m);
if (count == 0)
  cond_wait(&dolu, &m);
x = al();        /* boş olabilir */
unlock(&m);

/* DOĞRU */
lock(&m);
while (count == 0)
  cond_wait(&dolu, &m);
x = al();        /* count > 0 kesin */
unlock(&m);

Hatanın oluşma yolu şöyledir (Şekil 6.30):

1. Tampon boştur. Tüketici T1 dolu koşul değişkeninde bekler.
2. Üretici bir öğe koyar, count = 1 yapar ve signal çağırır. T1 uyanır ama önce kilidi geri alması gerekir; yalnız hazır olur.
3. Bu arada yeni gelen tüketici T2 kilidi önce kapar (barging) ve öğeyi alır: count = 0.
4. T1 sonunda kilidi alır. if ile yazıldıysa koşulu yeniden sınamadan boş tampondan okur: hata.
5. while ile yazıldıysa T1 koşulu yeniden sınar, count == 0 görür ve tekrar bekler.

Mesa anlamlı bir monitörün modeliyle bütün ara yerleştirmeler gezildiğinde, if'li sürümde boş tampondan okunan bir yürütme bulunur. while'lı sürümde böyle bir yürütme yoktur. POSIX ayrıca sahte uyanmalara (spurious wakeup) izin verir: pthread_cond_wait, hiç signal gelmeden de dönebilir. Bu yüzden while her durumda zorunludur.

6.9.5Tek koşul değişkeni yetmez

while gerekli ama yeterli değildir. Arpaci-Dusseau'ların örneğinde tampon tek yuvalıdır; iki tüketici (T1, T2) ve bir üretici (Ü) vardır. Hepsi aynı c koşul değişkenini kullanır:

/* YANLIŞ: tek koşul c */
T: while (count == 0) wait(&c, &m);
   x = al();  signal(&c);
Ü: while (count == 1) wait(&c, &m);
   koy(x);    signal(&c);

1. Tampon boştur; T1 ve T2 c'de uyur.
2. Ü bir öğe koyar ve signal(c) ile T1'i uyandırır.
3. Ü yeniden dener; tampon dolu olduğu için o da c'de uyur. Artık c'de T2 ve Ü bekler.
4. T1 öğeyi alır ve signal(c) yapar. Hangi bekleyenin uyanacağı belli değildir; bu kez T2 uyanır.
5. T2 tamponu boş bulur ve yeniden uyur. T1 de bir sonraki turda uyur. Üreticiyi uyandıracak kimse kalmamıştır: program durur.

Hata, tüketicilerle üreticinin aynı kuyrukta beklemesidir. Tüketici yalnız üreticiyi, üretici yalnız tüketiciyi uyandırmalıdır. Çözüm iki koşul değişkenidir:

/* DOĞRU: iki koşul */
T: while (count == 0) wait(&dolu, &m);
   x = al();  signal(&bos);
Ü: while (count == 1) wait(&bos, &m);
   koy(x);    signal(&dolu);

Modelle yapılan taramada tek koşullu sürümde, while'a rağmen üç iş parçacığının da uyuduğu bir durum erişilebilir. İki koşullu sürümde böyle bir durum yoktur.

6.9.6signal ve broadcast

Bazen hangi bekleyenin ilerleyebileceği bilinemez. Bir bellek ayırıcıda iş parçacıkları farklı miktarlarda bellek ister:

int bos = 0;            /* boş bayt */

void *bellek_al(int n) {
  lock(&m);
  while (bos < n)
    wait(&c, &m);
  bos -= n;  /* ... ayır */
  unlock(&m);
}
void bellek_ver(int n) {
  lock(&m);
  bos += n;
  broadcast(&c); /* signal yetmez */
  unlock(&m);
}

Bellek tükenmiştir. Ta 100, Tb 10 bayt ister; ikisi de while döngüsünde uyur. Tc 50 bayt bırakır. signal yalnız birini uyandırır. Bu Ta olursa, 50 < 100 olduğu için yine uyur; Tb ilerleyebilecekken uyumaya devam eder. broadcast ise herkesi uyandırır. Her biri koşulunu yeniden sınar: Tb 10 baytı alır ve bos 40 olur; Ta 40 < 100 görüp yeniden uyur.

Kural şudur: hangi bekleyenin ilerleyebileceği bilinmiyorsa pthread_cond_broadcast (Java'da notifyAll) kullanılır. Bu kalıba kapsayan koşul (covering condition) denir. Bedeli gereksiz uyanmalardır. Bekleyenler ayrı koşullara bölünebiliyorsa signal daha ucuzdur. Her iki durumda da bekleme while içinde yapılır.

6.9.7Monitörle üretici-tüketici

Tanenbaum'un Pidgin Pascal ile yazdığı monitör, sınırlı tamponu iki koşul değişkeniyle çözer:

monitor ProducerConsumer
  condition full, empty;
  integer count;

  procedure insert(item: integer);
  begin
    if count = N then wait(full);
    insert_item(item);
    count := count + 1;
    if count = 1 then signal(empty)
  end;

  function remove: integer;
  begin
    if count = 0 then wait(empty);
    remove := remove_item;
    count := count - 1;
    if count = N - 1 then signal(full)
  end;

  count := 0;
end monitor;

count'a erişim monitör sayesinde zaten karşılıklı dışlanır. Tampon doluysa üretici wait(full) ile bloke olur ve monitörü bırakır. Tüketici bir öğe alınca count = N − 1 olur ve signal(full) üreticiyi uyandırır. Üreticiyi bloke eden wait'tir; signal yalnız uyandırır. Burada if yeterlidir, çünkü Tanenbaum Brinch Hansen anlamını varsayar: signal prosedürün son komutudur ve sinyal veren hemen çıkar. Pthreads ya da Java'da aynı kod while ile yazılmalıdır. Kayıp uyandırma da olmaz: sınama ile wait aynı monitör içinde, bölünmeden yapılır.

6.10POSIX ve Java

Ders kitabı monitörleri bir dil özelliğidir ve C'de yoktur. Gerçek programlarda aynı yapı bir mutex ile koşul değişkenlerinin birlikte kullanılmasıyla kurulur. Bu kesim POSIX iş parçacıkları (Pthreads) ve Java'daki araçları özetler.

6.10.1Pthreads: mutex ve koşul değişkeni

Kural: pthread_cond_wait her zaman mutex tutulurken ve bir while döngüsü içinde çağrılır. Mutex'in atomik olarak bırakılıp uyunması, kayıp uyandırma penceresini kapatır. Statik başlatma için PTHREAD_MUTEX_INITIALIZER ve PTHREAD_COND_INITIALIZER vardır. Mutex türleri NORMAL, ERRORCHECK ve RECURSIVE'dir; öncelik kalıtımı PTHREAD_PRIO_INHERIT özniteliğiyle açılır. Ek arayüzler arasında pthread_rwlock_*, pthread_spin_*, pthread_barrier_* ve C11'in mtx_t/cnd_t türleri bulunur.

Tanenbaum ve Bos'un Pthreads ile yazdığı üretici-tüketici programında tampon tek bir tamsayıdır (0 boş demektir). Üretici 1 ve 2 değerlerini koyar, tüketici onları yazdırır:

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condc = PTHREAD_COND_INITIALIZER,
               condp = PTHREAD_COND_INITIALIZER;
int buffer = 0;                    /* 0 = boş */

void *producer(void *p) {
  for (int i = 1; i <= MAX; i++) {  /* MAX = 2 */
    pthread_mutex_lock(&m);
    while (buffer != 0) pthread_cond_wait(&condp, &m);
    buffer = i;
    pthread_cond_signal(&condc);
    pthread_mutex_unlock(&m);
  } return NULL;
}
void *consumer(void *p) {
  for (int i = 1; i <= MAX; i++) {
    pthread_mutex_lock(&m);
    while (buffer == 0) pthread_cond_wait(&condc, &m);
    printf("%d\n", buffer); buffer = 0;
    pthread_cond_signal(&condp);
    pthread_mutex_unlock(&m);
  } return NULL;
}

1. Tüketici önce çalışır ve mutex'i alır. Tampon boştur; cond_wait mutex'i atomik olarak bırakır ve uyur.
2. Üretici mutex'i alır. Tampon boş olduğu için döngüyü atlar ve 1 yazar. signal tüketiciyi uyandırır; ama tüketici mutex'i geri almadan dönemez (Mesa).
3. Üretici yarışı kazanıp mutex'i yeniden almış olabilir. i = 2 için tamponu dolu bulur, condp'de bekler ve mutex'i bırakır.
4. Tüketici mutex'i alır, while koşulunu yeniden sınar (1 ≠ 0), 1'i yazdırır ve tamponu boşaltır.
5. Tüketici condp'ye sinyal verir. Üretici uyanır, tamponu boş bulur ve 2 yazar. İkinci turda tüketici 2'yi yazdırır.

Mutex ve koşul değişkeninin Mesa anlamlı modeliyle bütün ara yerleştirmeler gezildi. Her yürütmede çıktı “1, 2” oldu ve hiçbiri kilitlenmedi. Sıra değişse de çıktı değişmez; değişen yalnız kimin ne zaman uyuduğudur.

6.10.2POSIX semaforları

class="kw">#include <semaphore.h>

/* adsız: aynı sürecin iş parçacıkları */
sem_t bos, dolu;
sem_init(&bos,  0, N);   /* 0: süreç içi */
sem_init(&dolu, 0, 0);
sem_wait(&bos);   /* … koy … */   sem_post(&dolu);
sem_destroy(&bos);

/* adlandırılmış: ilgisiz süreçler arası */
sem_t *s = sem_open("/os06", O_CREAT, 0644, 1);
sem_wait(s);  /* KB */  sem_post(s);
sem_close(s);
sem_unlink("/os06");

POSIX iki tür semafor sunar. Adsız semafor sem_init ile bir değişken olarak oluşturulur. İkinci argüman 0 ise semafor aynı sürecin iş parçacıkları arasında kullanılır. 1 ise süreçler arasında paylaşılır; o zaman semafor paylaşımlı bellekte durmalıdır. Adlandırılmış semafor sem_open ile bir adla açılır ve ilgisiz süreçler aynı adı kullanarak ona erişir. sem_wait P, sem_post V işlemidir. sem_post bir sinyal işleyicisinden de güvenle çağrılabilir. sem_trywait beklemeden, sem_timedwait süre sınırıyla dener; sem_getvalue anlık değeri yalnız bilgi amacıyla verir.

macOS adsız semaforları desteklemez; orada sem_init kullanımdan kaldırılmıştır. Adlandırılmış semafor ya da dispatch_semaphore kullanılır. Java'nın karşılığı java.util.concurrent.Semaphore'dur: acquire(), release() ve isteğe bağlı adil mod.

6.10.3Java: synchronized, wait ve notify

Java'da her nesne bir monitördür: bir içsel kilidi ve tek bir bekleme kümesi (wait set) vardır. synchronized metot ya da blok bu kilidi alır ve çıkışta, istisna fırlatılsa bile, bırakır. Kilit yeniden girilebilir: sahibi aynı kilidi ikinci kez alabilir. wait() kilidi bırakıp uyur; notify() bekleyenlerden birini, notifyAll() hepsini uyandırır. Anlam Mesa'dır; bekleme while içinde yapılır.

public class TekYuva {
  private int yuva = 0;            /* 0 = boş */

  synchronized void koy(int x) throws InterruptedException {
    while (yuva != 0) wait();      /* kilidi bırakır */
    yuva = x;
    notifyAll();
  }
  synchronized int al() throws InterruptedException {
    while (yuva == 0) wait();
    int x = yuva;
    yuva = 0;
    notifyAll();
    return x;
  }
  /* main: üretici 10, 20, 30, 40 koyar;
     main dört kez al() ile okuyup yazdırır */
}

Sunumdaki main açıklaması çalıştırılabilir bir programa dönüştürüldü:

public class TekYuva {
  private int yuva = 0;            /* 0 = boş */

  synchronized void koy(int x) throws InterruptedException {
    while (yuva != 0) wait();      /* kilidi bırakır */
    yuva = x;
    notifyAll();
  }
  synchronized int al() throws InterruptedException {
    while (yuva == 0) wait();
    int x = yuva;
    yuva = 0;
    notifyAll();
    return x;
  }
  public static void main(String[] a) throws InterruptedException {
    TekYuva t = new TekYuva();
    Thread u = new Thread(() -> {
      try { for (int x = 10; x <= 40; x += 10) t.koy(x); } catch (InterruptedException e) { }
    });
    u.start();
    for (int k = 0; k < 4; k++) System.out.println("alındı " + t.al());
    u.join();
  }
}

Program JDK 21 ile her çalıştırmada aynı çıktıyı verdi:

alındı 10
alındı 20
alındı 30
alındı 40

Üretici ve tüketici aynı bekleme kümesini paylaşır. Bu yüzden notify yerine notifyAll daha güvenlidir: notify yanlış türden bir bekleyeni uyandırabilir ve tek koşul değişkeniyle görülen kilitlenme yaşanabilir.

6.10.4Java: ReentrantLock ve Condition

java.util.concurrent.locks paketi daha esnek bir kilit sunar. Bir ReentrantLock'a birden çok Condition bağlanabilir. Böylece üreticiler ve tüketiciler ayrı kuyruklarda bekler ve signal doğru grubu uyandırır. Kilit ayrıca tryLock(), süre sınırlı ve kesilebilir kilitleme ile isteğe bağlı adil mod sunar. unlock() mutlaka finally içinde çağrılır; yoksa bir istisna kilidi sonsuza dek tutulu bırakır.

class Tampon {
  private final int[] buf = new int[2];
  private int bas = 0, son = 0, adet = 0;
  private final ReentrantLock kilit = new ReentrantLock();
  private final Condition bosYer = kilit.newCondition();
  private final Condition dolu   = kilit.newCondition();

  void koy(int x) throws InterruptedException {
    kilit.lock();
    try {
      while (adet == buf.length) bosYer.await();
      buf[son] = x; son = (son + 1) % buf.length; adet++;
      dolu.signal();
    } finally { kilit.unlock(); }
  }
  /* al(): while (adet == 0) dolu.await(); …
           bosYer.signal();                     */
}
/* üretici 1..5 koyar; main 5 kez al() */

Sunumdaki sınıf al() metodu tamamlanarak çalıştırıldı:

import java.util.concurrent.locks.*;
class Tampon {
  private final int[] buf = new int[2];
  private int bas = 0, son = 0, adet = 0;
  private final ReentrantLock kilit = new ReentrantLock();
  private final Condition bosYer = kilit.newCondition();
  private final Condition dolu   = kilit.newCondition();

  void koy(int x) throws InterruptedException {
    kilit.lock();
    try {
      while (adet == buf.length) bosYer.await();
      buf[son] = x; son = (son + 1) % buf.length; adet++;
      dolu.signal();
    } finally { kilit.unlock(); }
  }
  int al() throws InterruptedException {
    kilit.lock();
    try {
      while (adet == 0) dolu.await();
      int x = buf[bas]; bas = (bas + 1) % buf.length; adet--;
      bosYer.signal();
      return x;
    } finally { kilit.unlock(); }
  }
  public static void main(String[] a) throws InterruptedException {
    Tampon t = new Tampon();
    Thread u = new Thread(() -> {
      try { for (int x = 1; x <= 5; x++) t.koy(x); } catch (InterruptedException e) { }
    });
    u.start();
    int toplam = 0; StringBuilder sb = new StringBuilder();
    for (int k = 0; k < 5; k++) { int x = t.al(); toplam += x; sb.append(x).append(' '); }
    u.join();
    System.out.println(sb + "| toplam = " + toplam);
  }
}

JDK 21 ile üç çalıştırmanın üçü de aynı çıktıyı verdi:

1 2 3 4 5 | toplam = 15
1 2 3 4 5 | toplam = 15
1 2 3 4 5 | toplam = 15

İki yuvalı tamponda üretici tüketiciden en fazla iki öğe önde olabilir; tampon dolunca bosYer'de bekler. Öğeler ise hep konduğu sırayla alınır. İş parçacıklarının ne zaman uyuduğu çalıştırmadan çalıştırmaya değişir, çıktı değişmez. Sanal iş parçacıkları için bir not: Java 21'de sanal bir iş parçacığı synchronized içinde bloke olunca onu taşıyan platform iş parçacığını “sabitliyordu” (pinning). Bu yüzden o sürümde ReentrantLock önerilirdi. JDK 24'te JEP 491 bu sorunu giderdi.

6.11Canlılık

Doğru bir senkronizasyon önce güvenliği sağlar: veri bozulmaz. Ama sistemin ilerlemesi de gerekir. Bu kesim, dışlama doğru olsa bile ortaya çıkabilen canlılık sorunlarını ele alır.

6.11.1Öncelik terslemesi

Öncelikli çizelgelemede yüksek öncelikli bir görev hazır olduğu an çalışır. Kilitler bu kuralı beklenmedik biçimde bozabilir. Üç görev düşünelim: yüksek öncelikli H, orta öncelikli M ve düşük öncelikli L. H ile L paylaşılan bir R kaynağını kullanır; M'nin R ile ilgisi yoktur. Tek bir işlemci vardır ve süreler milisaniyedir.

1. t = 0. L, R'nin kilidini alır. Kritik bölgesi toplam 4 ms sürecektir.
2. t = 2. H gelir ve L'yi keser. t = 3'te R'yi ister ve bloke olur. Kısa bir bekleme beklenir: L kalan 2 ms'yi bitirince H girer.
3. t = 4. M gelir. M, L'den önceliklidir; L'yi keser ve t = 10'a kadar çalışır. L ancak t = 10'da yeniden çalışır ve R'yi t = 11'de bırakır.

H, R için 8 ms beklemiştir; bu sürenin 6 ms'si M'nin çalışmasıdır. En yüksek öncelikli görev, kendisiyle hiçbir ilgisi olmayan orta öncelikli bir görevi bekler. M uzadıkça H'nin beklemesi de sınırsız uzar.

Öncelik terslemesi bir çözüm değil, sorundur. Öncelik kalıtımında H, R'yi beklerken L geçici olarak H'nin önceliğini alır. M gelse de L'yi kesemez. L t = 3'ten t = 5'e kadar çalışıp R'yi bırakır ve eski önceliğine döner. H hemen çalışır ve yalnız 2 ms bekler (Şekil 6.34). Bir başka çözüm öncelik tavanıdır (priority ceiling): kilidi alan görev, o kilidi kullanabilecek en yüksek öncelikli görevin önceliğine hemen yükseltilir.

Bu iki senaryo, kesmeli öncelikli bir tek işlemci çizelgeleyicisinin küçük bir modeliyle birim birim yeniden çalıştırıldı. Kalıtımsız durumda H'nin kilit beklemesi 8, kalıtımlı durumda 2 birim çıktı. Kilidi spinlock ile bekleyen H ise tek çekirdekte daha kötü bir sonuç doğurur. H işlemciyi hiç bırakmadığı için L hiç çalışamaz ve kilidi hiç bırakamaz: sistem kilitlenir.

6.11.2Mars Pathfinder (1997)

Öncelik terslemesinin en ünlü örneği Mars'ta yaşandı. Temmuz 1997'de Mars yüzeyindeki Pathfinder aracı, VxWorks gerçek zamanlı işletim sistemi altında çalışırken tekrar tekrar kendini sıfırladı. Düşük öncelikli meteoroloji görevi, bilgi veriyolunu koruyan bir mutex'i tutuyordu. Yüksek öncelikli veriyolu yönetim görevi bu mutex'te bloke oldu. Bu sırada orta öncelikli ve uzun süren iletişim görevi araya girdi (Şekil 6.35).

Veriyolu yönetim görevi zamanında çalışamayınca bir bekçi zamanlayıcı (watchdog) “sistem asılı kaldı” sonucuna vardı ve tam bir sıfırlama yaptı. JPL mühendisleri hatayı yerdeki kopya üzerinde yeniden üretti. Mutex'in öncelik kalıtımı seçeneği VxWorks'te vardı ama kapalıydı; uzaktan yüklenen küçük bir yamayla açıldı ve sıfırlamalar durdu. Bugün aynı mekanizma POSIX'te PTHREAD_PRIO_INHERIT özniteliği, Linux'ta öncelik kalıtımlı futex'ler ve rt_mutex olarak bulunur. Linux 6.12'de ana dala giren PREEMPT_RT gerçek zamanlı yaması da bu mekanizmaya dayanır.

6.11.3Kilitlenme, canlı kilit ve açlık

Üç canlılık sorunu sık karıştırılır (Şekil 6.36):

Canlı kilidin tipik örneği iki “kibar” iş parçacığıdır. Her biri iki kilit ister. İkinci kilidi trylock ile alamayan, elindekini bırakır ve hep aynı süre sonra yeniden dener. İki iş parçacığı tam aynı ritimde çalışırsa sonsuza dek birbirine yol verir. Çare, rastgele (genellikle üstel artan) bir süre geri çekilmektir; Ethernet çarpışmalarında kullanılan yöntem budur. Açlığın çaresi ise FIFO kuyruklar, adil kilitler ve yaşlandırmadır.

6.12Kilitsiz yapılara giriş

Kilit kullanan her yapı bir zayıflık taşır: kilidi tutan iş parçacığı kesilir, bir sayfa hatası bekler ya da çökerse herkes durur. Kilitsiz (lock-free) yapılar kilit yerine doğrudan CAS gibi atomik komutları kullanır. İlerleme garantileri üç düzeyde tanımlanır:

En basit kilitsiz yapı Treiber yığınıdır. Yığının tepesi tek bir atomik işaretçidir. push yeni düğümü hazırlar, düğümün next alanını mevcut tepeye bağlar ve tepeyi CAS ile değiştirmeye çalışır:

void push(node_t *n) {
  node_t *eski = atomic_load(&top);
  do {
    n->next = eski;
  } while (!atomic_compare_exchange_weak(
               &top, &eski, n));
}  /* başarısızsa eski = güncel top */

Kilitsiz programlamanın ünlü tuzağı ABA sorunudur. CAS yalnız değerin eşitliğine bakar; değerin arada değişip geri dönüp dönmediğini bilemez. pop sırasında T1, top = A ve A.next = B okuyup kesilsin. Bu arada T2, A'yı ve B'yi çıkarır, B'yi serbest bırakır ve A'yı yeniden ekler. top yeniden A olmuştur. T1'in CAS(top, A, B) çağrısı başarılı olur ve tepeye artık yığında olmayan, belleği serbest bırakılmış B düğümünü koyar. Çare, işaretçiyle birlikte her değişiklikte artan bir sürüm sayacını karşılaştırmak ya da serbest bırakılan düğümleri güvenli bellek geri kazanımıyla (hazard pointer, epoch) geciktirmektir.

6.13Özet

• Yarış durumu, paylaşılan veriye erişen süreçlerin sonucunun yürütme sırasına bağlı olmasıdır. Tek bir count++ bile makinede oku-değiştir-yaz dizisidir ve arasında kesilebilir. Bu tür hatalar ara sıra ortaya çıkar ve testle yakalanması zordur.
• Kritik bölge paylaşılan veriye erişen koddur. Bir çözüm üç koşulu sağlamalıdır: karşılıklı dışlama (güvenlik), ilerleme ve sınırlı bekleme (canlılık).
• Kesme kapatma çok çekirdekte işe yaramaz ve kullanıcıya açık değildir. Kilit değişkeni dışlamayı, katı sıra ilerlemeyi bozar. Peterson algoritması iki süreç için üç koşulu yalnız okuma ve yazmayla sağlar; ama sıralı tutarlı bellek varsayar.
• Modern işlemcilerde yazma tamponu ve derleyici yeniden sıralaması Peterson'u bozar. x86 (TSO) yalnız “yazma → sonraki okuma” yeniden sıralamasına izin verir. Bellek bariyeri ya da sıralı tutarlı atomikler (C11 _Atomic, Java volatile) doğru sırayı geri getirir; C'deki volatile getirmez.
• Donanım atomik komutlar sunar: test_and_set/TSL, XCHG ve CAS. Basit atomik spinlock sınırlı beklemeyi garanti etmez; waiting[] dizisi ve döngüsel devretme bunu sağlar. CAS döngüsü kilitsiz güncellemenin temelidir.
• Spinlock meşgul bekler ve kısa kritik bölgeler için çok çekirdekte uygundur. Mutex bekleyeni uyutur. Linux'ta mutex'ler futex ile kurulur: çekişme yoksa çekirdeğe girilmez. Çekirdek başına sayaç, doğruluktan biraz ödün vererek ölçeklenir.
• Semafor wait/signal ile kullanılan bir sayaçtır. Başlangıç değeri 1 ise dışlama, N ise kaynak sayma, 0 ise sıralama kalıbıdır. Semafor uyandırmayı saklar; sinyal kaybolmaz.
• Sınırlı tampon mutex, empty ve full semaforlarıyla çözülür; down sırası ters olursa kilitlenme olur. Okur öncelikli okur-yazar çözümü yazar açlığına açıktır. Yemek yiyen filozofların naif çözümü kilitlenir; oda semaforu, kaynak sıralaması ya da durum dizisiyle çözülür.
• Monitör dışlamayı dil düzeyinde sağlar; koşul değişkeni değeri olmayan bir bekleme kuyruğudur. Gerçek sistemler Mesa anlamını kullanır: bekleme her zaman while içindedir, ayrı gruplar için ayrı koşul değişkenleri kullanılır, hangi bekleyenin ilerleyeceği bilinmiyorsa broadcast yapılır.
• Pthreads'te pthread_cond_wait mutex'i atomik olarak bırakıp uyur. Java'da her nesne bir monitördür (synchronized, wait, notifyAll); ReentrantLock birden çok Condition sunar.
• Öncelik terslemesi yüksek öncelikli görevin dolaylı olarak orta öncelikliyi beklemesidir; öncelik kalıtımı ya da tavanı ile çözülür (Mars Pathfinder). Kilitlenme, canlı kilit ve açlık farklı canlılık sorunlarıdır.
• Kilitsiz yapılar CAS döngüsüyle çalışır ve kilidi tutanın durmasından etkilenmez; ama ABA sorununa karşı sürüm sayacı ya da güvenli bellek geri kazanımı gerekir.

6.14Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• senkronizasyon synchronization
• yarış durumu race condition
• kritik bölge critical section
• karşılıklı dışlama mutual exclusion
• sınırlı bekleme bounded waiting
• meşgul bekleme busy waiting
• Peterson algoritması Peterson's algorithm
• bellek bariyeri memory barrier
• atomik komut atomic instruction
• spinlock spinlock
• mutex mutex
• semafor semaphore
• üretici-tüketici problemi producer–consumer problem
• okur-yazar problemi readers–writers problem
• yemek yiyen filozoflar problemi dining philosophers problem
• monitör monitor
• koşul değişkeni condition variable
• öncelik terslemesi priority inversion
• öncelik kalıtımı priority inheritance
• kilitlenme deadlock
• canlı kilit livelock
• açlık starvation

6.15Kendini Dene

1. Paylaşılan count = 10'dur. T1 count = count + 3, T2 count = count − 1 yürütür; her biri LOAD, ADD, STORE olmak üzere üç komuttur. Olası bütün son değerler nelerdir?

   Cevap

   12, 13 ve 9. Biri ötekinin okumasından önce bitirirse 12 çıkar. T2'nin güncellemesi kaybolursa 13, T1'inki kaybolursa 9 çıkar. 20 ara yerleştirmenin hepsi bu üç değerden birini verir.

2. Peterson algoritmasının çıkış bölümündeki flag[i] = false satırı unutulursa üç koşuldan hangisi bozulur? P0 bir kez girip çıktıktan sonra kalan bölümde kalırsa P1'e ne olur?

   Cevap

   İlerleme bozulur. flag[0] sonsuza dek true kalır. P1 girmek isteyince turn = 0 yazar; koşulu flag[0] && turn == 0 doğru olur ve P1 döner. P0 kalan bölümde dururken P1'in önünü açacak tek şey P0'ın yeniden girmek isteyip turn = 1 yazmasıdır. Kritik bölge boş olduğu hâlde kalan bölümdeki bir süreç ötekini engeller.

3. Başlangıç değeri 3 olan bir semaforda (Silberschatz gerçeklemesi, FIFO kuyruk) P1–P5 sırayla wait, ardından iki signal yapılıyor. Beş wait'ten sonra ve iki signal'dan sonra değer ve kuyruk nedir?

   Cevap

   Beş wait'ten sonra değer 3 − 5 = −2'dir; P1, P2, P3 geçmiştir, P4 ve P5 kuyruktadır. İlk signal değeri −1 yapar ve P4'ü, ikincisi 0 yapar ve P5'i uyandırır. Son durumda değer 0 ve kuyruk boştur.

4. Semaforlu sınırlı tampon çözümünde N = 3'tür ve tüketici hiç çalışmıyor. Üretici beş öğe koymaya çalışırsa kaç öğe konur, empty ve full kaç olur, üretici hangi öğede uyur?

   Cevap

   Üç öğe konur. Her konuşta empty bir azalır, full bir artar: sonunda empty = 0, full = 3'tür. Dördüncü öğe için down(&empty) değeri 0 bulur ve üretici uyur. Tampon taşmaz.

5. Semaforla bariyer kodunda turnikeden geçtikten sonraki up(&turnike) satırı silinirse, N = 3 iken kaç iş parçacığı bariyeri geçer?

   Cevap

   Yalnız biri. Son gelen iş parçacığının up'ı turnikedeki tek bir iş parçacığını geçirir. Geçen arkadakini geçirmediği için öteki ikisi turnikede sonsuza dek uyur. Bütün ara yerleştirmeler gezildiğinde kilitlenen her yürütmede geçen sayısı 1'dir.

6. v = 0 iken üç iş parçacığı CAS döngüsüyle (artir) birer kez artırma yapıyor. Son değer kaçtır? Toplam CAS çağrısı en az ve en çok kaç olabilir?

   Cevap

   Son değer her zaman 3'tür. En az 3 CAS yapılır: her biri ötekiler okumadan önce bitirirse hiç başarısızlık olmaz. En çok 3 + 2 + 1 = 6 CAS yapılır. Üçü de aynı değeri okursa biri başarılı olur ve ikisi yeniden dener. Sonraki turda yine biri başarılı, biri başarısız olur.

7. Tek CPU'da H > M > L'dir. L t = 0'da kilidi alır ve kritik bölgesi 3 birimdir. H t = 1'de gelir ve hemen aynı kilidi ister; kilidi alınca 1 birim çalışır. M t = 2'de gelir ve 4 birim çalışır, kilit kullanmaz. Öncelik kalıtımı yokken ve varken H kaç birim bekler, ne zaman biter?

   Cevap

   Kalıtım yokken çizelge L(0–1), L(1–2), M(2–6), L(6–7), H(7–8)'dir. H 1'den 7'ye kadar 6 birim bekler ve t = 8'de biter. Kalıtımla L, H'nin önceliğiyle 1–3 arası çalışır ve kilidi bırakır; H 3–4 arası çalışır. H 2 birim bekler ve t = 4'te biter; M 4–8 arası çalışır.

8. İki çekirdekli makinede eşik S = 5 olan yaklaşık sayaç kullanılıyor. Çekirdek 0 on iki, çekirdek 1 yedi kez ekle() çağırıyor. Sonunda oku() kaçı verir? Gerçek değer kaçtır? En kötü durumda fark en fazla kaç olabilir?

   Cevap

   Çekirdek 0 iki kez 5 aktarır ve yerelde 2 kalır; çekirdek 1 bir kez 5 aktarır ve yerelde 2 kalır. oku() = G = 15, gerçek değer 19'dur. En kötü durumda fark 2 × (5 − 1) = 8'dir.

9. Altı filozoflu masada aynı anda en fazla kaç filozof yiyebilir? Naif çözüm (önce sol, sonra sağ çatal) altı filozofta da kilitlenir mi?

   Cevap

   ⌊6/2⌋ = 3: örneğin F0, F2 ve F4 birlikte yiyebilir. Naif çözüm filozof sayısından bağımsız olarak kilitlenir: hepsi sol çatalını alırsa döngüsel bekleme oluşur.

10. Yazma tamponu testinde T1 x = 1; r1 = y;, T2 y = 1; r2 = x; yürütür. Tam bellek bariyeri yalnız T1'de, yazma ile okuma arasına konuyor. x86 (TSO) üzerinde r1 = r2 = 0 hâlâ gözlenebilir mi?

    Cevap

    Evet. T1'in bariyeri yalnız T1'in kendi yazmasının okumasından önce görünmesini sağlar. T2'nin y = 1 yazması tamponda beklerken T2 x'i bellekten 0 okuyabilir; T1 de y'yi bellekten 0 okuyabilir. Yazma tamponlu modelde bütün yürütmeler gezildiğinde (0, 0) yine çıkar. Bariyer iki tarafa da konmalıdır.

6.16İleri okuma

• R. H. Arpaci-Dusseau ve A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, “Locks”, “Condition Variables”, “Semaphores” ve “Common Concurrency Problems” bölümleri: kilitlerin donanımdan nasıl kurulduğunu, yaklaşık sayacı ve koşul değişkenlerindeki tuzakları kısa ve ölçümlü örneklerle anlatır.
• A. B. Downey, The Little Book of Semaphores: turnikeli bariyerden açlıksız okur-yazara kadar onlarca problemi semaforlarla çözer; her çözümden önce okurun kendisinin denemesine yer bırakır. Kitap ücretsizdir.
• A. Silberschatz, P. B. Galvin ve G. Gagne, Operating System Concepts (10. baskı), Bölüm 6 ve 7: kritik bölge koşullarını, donanım desteğini ve gerçek sistemlerdeki araçları ayrıntılı işler.
• B. Goetz ve arkadaşları, Java Concurrency in Practice: Java bellek modelini, volatile'ın anlamını ve java.util.concurrent araçlarının doğru kullanımını uygulamalı olarak anlatır.

6.17Kaynaklar

1. R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), ostep.org — “Locks”, “Condition Variables”, “Semaphores”, “Common Concurrency Problems”.
2. A. B. Downey, The Little Book of Semaphores, 2. baskı, Green Tea Press.
3. B. Goetz ve ark., Java Concurrency in Practice, Addison-Wesley, 2006; Java SE 21 API: java.util.concurrent; JEP 491.
4. U. Drepper, “Futexes Are Tricky”, Red Hat teknik raporu, sürüm 1.6, 2011 (ilk sürüm 2004), akkadia.org/drepper/futex.pdf.
5. M. Jones, “What really happened on Mars?”, 1997.
6. M. M. Michael, M. L. Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”, Proceedings of the 15th ACM Symposium on Principles of Distributed Computing (PODC '96), ss. 267–275, 1996, doi:10.1145/248052.248106.
7. G. L. Peterson, “Myths About the Mutual Exclusion Problem”, Information Processing Letters, 1981.
8. POSIX.1-2017 (IEEE Std 1003.1): pthread_mutex_lock, pthread_cond_wait, sem_overview(7); Linux futex(2) kılavuz sayfası.
9. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018 — Bölüm 6: Synchronization Tools, Bölüm 7: Synchronization Examples.
10. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı, Pearson, 2014 (5. baskı 2023) — §2.3 Interprocess Communication, §2.5 Classical IPC Problems.

İlgili sayfalar: Bölüm 6 sunumu · Çalışma soruları · Senkronizasyon laboratuvarı · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.