Bölüm 7: Kilitlenme

7.1Kilitlenme ve kaynaklar

Eş zamanlı çalışan süreçler kaynakları paylaşır: bir yazıcıyı, bir dosyayı, bir veritabanı kaydını, bellekteki bir veri yapısını koruyan kilidi. Paylaşımı düzenlemenin olağan yolu, kaynağı kullanan süreç işini bitirene kadar ötekileri bekletmektir. Bekletmek çoğu zaman sorunsuzdur; bekleyen süreç sırası gelince devam eder. Ama bekleme bir halka oluşturursa sıra hiç gelmez. Bu kesim kilitlenmenin tanımını, ilgili kaynak türlerini ve en küçük kilitlenme örneğini verir.

7.1.1Kilitlenme nedir?

En basit durumu düşünelim. S1 süreci K1 kaynağını tutuyor ve K2'yi bekliyor. S2 süreci de K2'yi tutuyor ve K1'i bekliyor. S1, K2'yi alamadığı için ilerleyemez ve K1'i bırakmaz. S2 de aynı nedenle K2'yi bırakmaz. İki süreç de bloke olmuştur. Onları uyandıracak tek olay ötekinin kaynağı bırakmasıdır; o olay da hiç gerçekleşmeyecektir.

Tanımdaki “yalnız kümedeki başka bir süreç” ifadesi önemlidir. Bekleyen süreci dışarıdan biri kurtarabiliyorsa, örneğin kaynağı tutan süreç kümenin dışındaysa ve bir gün işini bitirecekse, ortada kilitlenme yoktur; yalnızca uzun bir bekleme vardır. Kilitlenmede ise kurtarıcı kümenin içindedir ve kümedeki herkes beklediği için kurtarıcı hiç çalışmaz.

Gündelik hayatta da benzer durumlar vardır. Dört aracın aynı anda girdiği bir kavşakta her araç sağındakinin önünü keser; hiçbiri ilerleyemez (gridlock). Tek hatlı bir rayda karşılıklı gelen iki tren de birbirini bekler. Şekil 7.1 kavşak örneğini gösterir.

Kilitlenen süreçler işlemci harcamaz, çünkü bloke durumdadırlar. Asıl zarar, tuttukları kaynakların sonsuza dek kullanılamamasıdır. O kaynakları isteyen başka süreçler de zamanla beklemeye başlar ve kilitlenme yayılır. Konu yalnız işletim sistemine özgü değildir: veritabanı işlemleri, çok iş parçacıklı uygulamalar ve dağıtık sistemler de kilitlenir. Bu notta “süreç” sözcüğü iş parçacığını da kapsar; anlatılan her şey iki durumda da geçerlidir.

7.1.2Kesilebilir ve kesilemez kaynaklar

Kilitlenmenin konusu kaynaklardır. Kaynak, bir sürecin kullanmak için edinmesi gereken her şeydir: bir donanım aygıtı, bir bellek bölgesi, bir dosya, bir kilit, bir veritabanı kaydı. Kaynakları kilitlenme açısından ikiye ayırmak gerekir.

İşlemci kesilebilir bir kaynaktır. Çizelgeleyici çalışan süreci durdurur, yazmaçlarını kaydeder ve işlemciyi başka sürece verir; süreç sonra kaldığı yerden devam eder. Ana bellek de kesilebilir: bir sayfa diske yazılıp çerçeve başka sürece verilebilir, sayfa gerektiğinde geri yüklenir. Bu tür kaynaklarda bekleme halkası oluşsa bile işletim sistemi kaynağı yeniden dağıtarak halkayı kırabilir.

Yarısı yazılmış bir Blu-ray diski kesilemez: yazma işini yarıda kesip sürücüyü başka sürece vermek diski bozar. Yazıcıda basılmakta olan bir iş de böyledir; başka bir işin sayfaları araya girer. Bir mutex ya da semafor ile korunan veri, kilit zorla alınırsa tutarsız bir ara durumda kalır. Kilitlenmeler bu tür kesilemez kaynaklarla ilgilidir. Tablo 7.1 yaygın kaynakları türlerine göre sıralar.

Tablodaki “örnek sayısı” sütunu da önemlidir. Bir kaynak türünün birden çok özdeş örneği (instance) olabilir. Sistemde iki teyp sürücüsü varsa ve bir süreç “bir teyp sürücüsü” istiyorsa, iki sürücüden hangisinin verildiği fark etmez. Bir istek o türün herhangi bir örneğiyle karşılanabiliyorsa örnekler özdeştir. Genel olarak R_i kaynak türünün W_i tane örneği vardır. Örnek sayısı, kilitlenmenin nasıl tespit edileceğini doğrudan etkiler.

7.1.3Kaynak kullanım döngüsü

Bir süreç bir kaynağı her zaman aynı üç adımla kullanır:

1. İste (request). Kaynak boştaysa sürece verilir. Boş değilse süreç bloke olur ve kaynak boşalınca uyandırılır. Bazı sistemlerde süreç bloke olmak yerine bir hata kodu alır ve biraz sonra yeniden dener.
2. Kullan (use). Süreç kaynak üzerinde işlem yapar: yazıcıya basar, dosyaya yazar, korunan veriyi günceller.
3. Bırak (release). Kaynak serbest kalır; onu bekleyen süreçlerden biri uyandırılır.

İşletim sistemi bir tabloda hangi kaynağın kime verildiğini ve kimin hangi kaynağı beklediğini tutar. Kilitlenme tespiti bu tablodaki bilgiyle yapılır. İsteme ve bırakma işlemleri çoğu zaman sistem çağrılarıdır ya da kütüphane fonksiyonlarıdır; Tablo 7.2 en bilinen çiftleri gösterir.

7.1.4Aynı sıra ve ters sıra

Kullanıcı süreçlerinin kendi kaynaklarını semaforlarla koruduğunu varsayalım. Her kaynağa bir ikili semafor karşılık gelsin: kaynağa erişmeden önce down, iş bitince up yapılır. Tek süreç ya da tek kaynak varken sorun çıkmaz. İki süreç ve iki kaynak olunca sonucu kaynakların alınma sırası belirler. Aşağıdaki iki süreç kaynakları aynı sırada alır:

void process_A(void) {
  down(&resource_1);
  down(&resource_2);
  use_both_resources();
  up(&resource_2);
  up(&resource_1);
}
void process_B(void) {
  down(&resource_1);
  down(&resource_2);
  use_both_resources();
  up(&resource_2);
  up(&resource_1);
}

Bu kod kilitlenmez. İki süreç de önce resource_1'i ister. Biri onu alır, öteki bekler. resource_1'i alan süreç resource_2'yi de rahatça alır, çünkü onu isteyebilecek tek öteki süreç hâlâ resource_1'in önünde bekler. İşini bitirip iki kaynağı bırakınca bekleyen süreç devam eder.

Şimdi B'nin sırasını ters çevirelim:

void process_A(void) {
  down(&resource_1);
  down(&resource_2);
  use_both_resources();
  up(&resource_2);
  up(&resource_1);
}
void process_B(void) {
  down(&resource_2);  /* ters sıra */
  down(&resource_1);
  use_both_resources();
  up(&resource_1);
  up(&resource_2);
}

Bu sürümde kilitlenme mümkündür. A resource_1'i, B de resource_2'yi alırsa her biri ötekinin elindekini bekler. Bırakma sırasının bir önemi yoktur; belirleyici olan edinme, yani down sırasıdır. Programcının gözünden iki sürüm neredeyse aynıdır. İki satırın yerini değiştirmek, hiç kilitlenmeyen bir programı ara sıra kilitlenen bir programa dönüştürür.

7.1.5Kod izleme: ters sırada edinim

Ters sıralı kodun kısaltılmış hâli aşağıdadır. İki ikili semafor 1 ile başlar; yani iki kaynak da boştur.

semaphore r1 = 1, r2 = 1;
void A(void) {
  down(&r1);
  down(&r2);
  use_both();
  up(&r2); up(&r1);
}
void B(void) {
  down(&r2);
  down(&r1);
  use_both();
  up(&r1); up(&r2);
}

Tek bir işlemcide çizelgeleyicinin şu sırayı seçtiğini düşünelim: A'nın ilk down'ı, B'nin ilk down'ı, A'nın ikinci down'ı, B'nin ikinci down'ı. Tablo 7.3 her adımda semaforların ve süreçlerin durumunu, Şekil 7.3 de aynı adımların çizgesini gösterir. Çizgede daire süreci, kare kaynağı gösterir. Kaynaktan sürece giden düz ok “bu kaynak bu sürecindir”, süreçten kaynağa giden kesikli ok “bu süreç bu kaynağı bekliyor” anlamına gelir.

Dördüncü adımdan sonra iki süreç de bloke durumdadır ve up satırlarına hiçbiri ulaşamaz. Çizgedeki döngü kilitlenmenin görsel işaretidir. Kilitlenme her çalıştırmada oluşmaz. A iki down'ı da B başlamadan bitirirse B ilk down'ında bekler ve A işini bitirince devam eder. Kilitlenme yalnız iki süreç de ilk down'ını ötekinin ikinci down'ından önce yaparsa oluşur. Bu pencere dar olduğu için hata testlerde nadiren görülür, sistem yük altındayken ortaya çıkar.

7.2Kilitlenmenin dört koşulu

Ters sıralı örnekte kilitlenmeyi mümkün kılan neydi? Kaynaklar paylaşılamıyordu, süreçler bir kaynağı tutarken ötekini bekliyordu, kimse kaynağı zorla geri alamıyordu ve bekleme bir halka oluşturuyordu. 1971'de Coffman, Elphick ve Shoshani bu dört özelliğin kilitlenme için gerekli olduğunu gösterdi.

7.2.1Coffman koşulları

Koşulların “birlikte gerekli” olması, birinin bile eksik olduğu bir sistemde kilitlenmenin imkânsız olduğu anlamına gelir. Kaynak paylaşılabiliyorsa kimse onu beklemez. Hiçbir süreç kaynak tutarken beklemiyorsa halka kurulamaz. Kaynaklar geri alınabiliyorsa halka kırılabilir. Halka hiç oluşmuyorsa da bekleyen her süreç sonunda sırasını alır. Kilitlenmeyi önleme stratejisi tam olarak bu gözleme dayanır: dört koşuldan birini yapısal olarak imkânsız kılmak.

Dört koşulun doğası aynı değildir. İlk üçü sistemin politikasıdır: kaynakların paylaşılıp paylaşılmadığı, süreçlerin nasıl kaynak istediği, kaynakların geri alınıp alınamadığı tasarımda belirlenir. Bu üç politika geçerli olduğunda kilitlenme olabilir, ama olmak zorunda değildir. Dördüncü koşul ise sistemin o anki durumudur: süreçlerin belirli bir sırayla kaynak istemesi sonucunda halka ya oluşur ya oluşmaz. Her kaynak türünden yalnız bir örnek varsa dört koşul aynı zamanda yeterlidir: dördü de sağlanıyorsa sistem kilitlenmiştir. Çok örnekli kaynaklarda bu yeterlilik ortadan kalkar: döngüdeki bir kaynağın başka bir örneği döngü dışındaki bir süreçte olabilir.

7.2.2Kavşak örneği

Dört koşulu somutlaştırmak için kavşağa dönelim. Kavşağın dört karesi dört kesilemez kaynaktır, araçlar da süreçlerdir. Şekil 7.5 koşulları sırayla işaretler.

1. Karşılıklı dışlama. İki araç aynı kareye sığmaz. Bir kare ya boştur ya tek bir araca aittir.
2. Tut ve bekle. Her araç girdiği kareyi tutar ve ilerlemek için önündeki kareyi bekler.
3. Kesme yok. Araçların arkasında kuyruk vardır; hiçbiri geri çekilip kareyi boşaltamaz.
4. Döngüsel bekleme. A, B'nin karesini; B, C'ninkini; C, D'ninkini; D de A'nınkini bekler. Halka kapanmıştır ve trafik kilitlenir.

Trafikteki çözümler de koşullardan birini kırar. Trafik polisi bir aracı geri çektirirse kesme yok koşulu kırılır. “Kavşak boşalmadan girme” kuralı, aracın bir kareyi tutarken başka kareyi beklemesini engeller; böylece tut ve bekle ortadan kalkar. Trafik ışığı ise yönlere sıra verir ve halkanın kurulmasını önler. Bilgisayar sistemlerindeki önleme yöntemleri de bu üç fikrin karşılığıdır.

7.3Kilitlenmenin modellenmesi

Kilitlenmeyi konuşmak için kimin neyi tuttuğunu ve kimin neyi beklediğini bir bakışta gösteren bir araca ihtiyaç vardır. Holt'un 1972'de önerdiği kaynak tahsis çizgesi bu işi görür. Çizge hem kilitlenmenin nasıl oluştuğunu anlamayı kolaylaştırır hem de tespit algoritmalarının çalıştığı veri yapısıdır.

7.3.1Kaynak tahsis çizgesi

Bir istek karşılandığında istek kenarı atama kenarına dönüşür, yani okun yönü ters çevrilir. Kaynak bırakıldığında atama kenarı silinir. Çok örnekli bir kaynak türünde karenin içine her örnek için bir nokta konur. Atama kenarı bu noktalardan birinden çıkar; istek kenarı ise karenin kendisine gider, çünkü süreç belirli bir örneği değil, türün herhangi bir örneğini bekler. Bu notta istek kenarları kesikli ve turuncu çizilir.

Tanenbaum aynı modeli süreç düğümleriyle çizer. Silberschatz ise düğümleri iş parçacığı olarak adlandırır ve T harfiyle gösterir. İki gösterim arasında anlam farkı yoktur. Bu notta örnekler hangi kaynaktan alındıysa o kaynağın adlandırması korunur.

7.3.2Kilitlenme nasıl oluşur?

Üç süreç (A, B, C) ve üç kaynak (R, S, T) düşünelim. Her süreç iki kaynak ister ve ikisini de bırakır:

A        B        C
R iste   S iste   T iste
S iste   T iste   R iste
R bırak  S bırak  T bırak
S bırak  T bırak  R bırak

İşletim sistemi süreçleri sıralı (round-robin) çizelgeliyor ve istekleri geldikleri sırayla karşılıyor olsun. Süreçlerin ilk istekleri sırayla gelir ve üç kaynak da boş olduğu için hepsi karşılanır. İkinci istekler geldiğinde her süreç bir sonrakinin elindeki kaynağı ister. Şekil 7.7 altı isteğin ardından çizgeyi adım adım gösterir.

1. A, R'yi ister. R boştur; atama kenarı R → A eklenir.
2. B, S'yi ister. S boştur; S → B eklenir.
3. C, T'yi ister. T boştur; T → C eklenir.
4. A, S'yi ister. S, B'dedir. A bloke olur; istek kenarı A → S eklenir.
5. B, T'yi ister. T, C'dedir. B bloke olur; B → T eklenir.
6. C, R'yi ister. R, A'dadır. C bloke olur; C → R eklenir. Çizgede A → S → B → T → C → R → A döngüsü vardır ve üç süreç de kilitlenmiştir.

Bu sonuç kaçınılmaz değildi. Çizelgeleyici başka bir sıra seçebilirdi. Örneğin A'yı iki isteğini de yapıp kaynaklarını bırakana kadar çalıştırsaydı, ardından B'yi, sonra C'yi çalıştırsaydı hiçbir istek beklemezdi. Paralellik kaybolurdu ama kilitlenme olmazdı. Kilitlenme, isteklerin sırasına bağlıdır.

7.3.3Kilitlenme nasıl önlenebilir?

İşletim sistemi bir isteği vermenin kilitlenmeye yol açacağını önceden bilseydi, tehlikeli isteği bekleterek kilitlenmeyi önleyebilirdi. Aynı örnekte işletim sisteminin B'nin isteklerini bir süre askıya aldığını, yani B'yi çizelgelemediğini varsayalım. Yalnız A ve C çalışır. Şekil 7.8 bu sıralamayı izler.

1. A, R'yi alır; C, T'yi alır. İki kaynak da boştur.
2. A, S'yi alır. S boştur, çünkü B henüz onu istememiştir.
3. C, R'yi ister. R, A'dadır; C bloke olur. Çizgede bir istek kenarı vardır ama döngü yoktur. A'nın beklediği hiçbir şey yoktur, ilerleyebilir.
4. A, R'yi bırakır. R, bekleyen C'ye verilir ve C ilerler.
5. A, S'yi bırakıp biter. Şimdi B çalıştırılır. B, S'yi alır; T'yi de C bitince alır. Kilitlenme olmaz.

İşletim sisteminin burada yaptığı şey kaçınma stratejisinin özüdür: hangi istek ertelenmeli? Ertelenecek isteği seçmek için her sürecin ne kadar kaynak isteyebileceğini bilmek gerekir. Bankacı algoritması bu bilgiyi kullanır.

7.3.4Çok örnekli kaynaklar

Şimdiye kadarki örneklerde her kaynak türünden tek örnek vardı. Silberschatz'ın klasik örneği çok örnekli türleri de içerir. Kaynak kümeleri şöyledir: R1 bir örnekli, R2 iki örnekli, R3 bir örnekli, R4 üç örnekli. Üç iş parçacığının durumu da şöyledir:

• T1, bir R2 örneğini tutar ve R1'i bekler.
• T2, R1'i ve bir R2 örneğini tutar, R3'ü bekler.
• T3, R3'ü tutar.

Çizgede döngü yoktur. T3 hiçbir şey beklemediği için işini bitirip R3'ü bırakır. R3, T2'ye verilir; T2 de biter ve R1 ile R2 örneğini bırakır. R1, T1'e verilir ve T1 de biter. Bitiş sırası T3, T2, T1'dir. Döngü yoksa kilitlenme de yoktur; bu kural örnek sayısından bağımsızdır.

7.3.5Döngü ve kilitlenme

Aynı duruma tek bir istek ekleyelim: T3, bir R2 örneği istesin. R2'nin iki örneği de doludur (biri T1'de, biri T2'de); T3 bloke olur. Bu tek istek kenarı çizgede iki döngü oluşturur:

• Döngü 1: T1 → R1 → T2 → R3 → T3 → R2 → T1.
• Döngü 2: T2 → R3 → T3 → R2 → T2.

Bu durumda kurtarıcı yoktur. T3, R2 örneklerinden birinin bırakılmasını bekler; ama iki örneğin sahibi de (T1 ve T2) döngüdedir. T2, T3'ün R3'ünü; T1, T2'nin R1'ini bekler. Döngüdeki her süreç döngüdeki başka bir süreci bekler ve dışarıdan kaynak bırakacak kimse yoktur. Üç iş parçacığı da kilitlenmiştir.

7.3.6Döngü var, kilitlenme yok

Çok örnekli kaynaklarda döngü her zaman kilitlenme demek değildir. Silberschatz'ın ikinci örneğinde R1 ve R2 ikişer örneklidir. R1'in iki örneği T2 ve T3'te, R2'nin iki örneği T1 ve T4'tedir. T1 bir R1 örneği, T3 de bir R2 örneği ister. Çizgede T1 → R1 → T3 → R2 → T1 döngüsü vardır.

Fark döngünün dışındaki süreçlerdedir. T2 ve T4 hiçbir şey beklemez; işlerini bitirip örneklerini bırakırlar. T4'ün bıraktığı R2 örneği T3'e verilir, döngü kırılır. T2'nin bıraktığı R1 örneği de T1'e verilebilir. Sonunda herkes biter; sistem hiç kilitlenmemiştir.

7.3.7Döngü kuralı

Örneklerden çıkan sonuç Tablo 7.4'de özetlenmiştir. Döngü yoksa kilitlenme hiçbir durumda yoktur. Döngü varsa sonuç örnek sayısına bağlıdır.

Tek örnekli kaynaklarda döngüyü bulmak için derinlik öncelikli arama yeterlidir ve maliyeti O(V + E)'dir (V düğüm, E kenar sayısı). Çok örnekli kaynaklarda döngü yalnız bir uyarıdır. Kesin karar için tahsis ve istek matrisleriyle “herkes bir sırayla bitebilir mi?” sorusu sorulur. Teorem dört koşulla da tutarlıdır: döngüsel bekleme, döngü içeren çizgenin karşılığıdır.

7.3.8Bekleme çizgesi

Her kaynak türünün tek örneği varsa tahsis çizgesi daha da sadeleştirilebilir. Kaynağın tek bir sahibi olduğu için “P_i, R'yi bekliyor ve R, P_j'de” bilgisi kısaca “P_i, P_j'yi bekliyor” demektir.

Şekil 7.12 dönüşümü dört süreçli bir örnekte gösterir. P1, R1'i tutar ve R2'yi ister. P2, R2'yi tutar ve R3'ü ister. P3, R3'ü tutar ve R1'i ister. P4 de R4'ü tutar ve R2'yi ister.

Kenarlar şöyle çıkar: P1, R2'yi bekler ve R2, P2'dedir; dolayısıyla P1 → P2. Aynı yolla P2 → P3, P3 → P1 ve P4 → P2 bulunur. Bekleme çizgesinde döngü ancak ve ancak kilitlenme varsa oluşur. İşletim sistemi bu çizgeyi tutar ve döngü arayan algoritmayı belirli aralıklarla çalıştırır. Silberschatz bu taramanın maliyetini O(n²) olarak verir (n: süreç sayısı).

Bekleme çizgesi yalnız her türden tek örnek olduğunda kullanılabilir; çok örnekli bir türde “R'nin sahibi” tek bir süreç değildir. Veritabanları bu yöntemi yaygın olarak kullanır: PostgreSQL ve MySQL InnoDB, satır kilitleri için bir bekleme çizgesi tutar ve döngü bulduğunda işlemlerden birini iptal eder.

7.4Başa çıkma stratejileri

Kilitlenmeyle başa çıkmanın dört yolu vardır. Yollar birbirinden şu sorularla ayrılır: Sistem kilitlenmeye hiç izin verir mi? Karar ne zaman verilir, tasarımda mı, çalışma anında mı, kilitlenme olduktan sonra mı? Karar için hangi bilgi gerekir?

7.4.1Dört strateji

1. Görmezden gelme. “Devekuşu algoritması” da denir. Kilitlenme nadirse ve önleme maliyeti yüksekse sorun yok sayılır; kilitlenme olursa sistem ya da süreç yeniden başlatılır.
2. Tespit ve kurtarma. Tepkisel bir yaklaşımdır. Kilitlenmeye izin verilir; sistem belirli aralıklarla kilitlenme olup olmadığını denetler ve bulursa kaynak kesme, geri sarma ya da sonlandırma ile çözer.
3. Dinamik kaçınma. Önleyicidir ve çalışma anında karar verir. Sistemi güvensiz bir duruma sokacak istek ertelenir. Bankacı algoritması bu yaklaşımın örneğidir. Her sürecin azami ihtiyacının önceden bilinmesini gerektirir.
4. Önleme. Önleyicidir ve kararı tasarımda verir. Dört koşuldan en az biri yapısal olarak imkânsız kılınır; kilit sıralaması en bilinen örnektir.

Listede “kurtarma” ayrı bir strateji olarak geçmez, çünkü kurtarma tespitin ikinci yarısıdır. Önce kilitlenme bulunur, sonra çözülür. Kaçınma ile önleme arasındaki fark da sık karıştırılır. Önleme, kilitlenmenin koşullarından birini sistemden tümüyle kaldırır; koşullar zaten sağlanamadığı için kilitlenme imkânsızdır. Kaçınma ise dört koşulun hepsine izin verir, ama her istekte durumun gidişatını hesaplar ve tehlikeli istekleri bekletir.

7.4.2Devekuşu algoritması

En basit strateji hiçbir şey yapmamaktır. Adını, tehlike karşısında başını kuma gömdüğüne inanılan devekuşundan alır. Kilitlenme olursa kullanıcı ya da yönetici takılan süreci öldürür, gerekirse sistemi yeniden başlatır.

İlk bakışta sorumsuz görünse de bu seçim bir mühendislik dengesidir. Kilitlenme yılda bir kez oluyorsa, buna karşılık çökmeler ve donanım hataları çok daha sık görülüyorsa, pahalı ve kısıtlayıcı önlemler değmez. Her istekte çalışan bir kaçınma algoritması bütün sistemi yavaşlatır; kaynak isteklerine konan kurallar da programcının işini zorlaştırır.

Linux, Windows ve macOS gibi genel amaçlı işletim sistemleri kullanıcı süreçlerinin kilitleri, dosya kilitleri ve boru beklemeleri için bu yaklaşımı uygular. Sorumluluk uygulama geliştiricisindedir. Ama işletim sistemi kendi içinde kilitlenmeye karşı önlem alır: çekirdekteki kilitler belgelenmiş bir sırayla alınır ve Linux'taki lockdep aracı bu sırayı denetler. Gerçek zamanlı ve güvenlik açısından kritik sistemlerde devekuşu yaklaşımı kabul edilemez; bir uçuş denetim yazılımı “ara sıra yeniden başlatılır” diye tasarlanamaz.

Devekuşu yaklaşımı tespit ile kaçınma arasında bir orta yol değildir. Ne tespit ne kaçınma yapar; yalnızca kilitlenmenin olasılığını ve maliyetini önlemin maliyetiyle karşılaştırır.

7.5Tespit ve kurtarma

Tespit ve kurtarma stratejisinde sistem kaynak isteklerine kısıt koymaz. İstekler geldikçe karşılanır, kaynak boş değilse süreç bekletilir. Sistem zaman zaman bir algoritma çalıştırarak kilitlenme olup olmadığını denetler. Algoritma kaynak türlerinin tek ya da çok örnekli olmasına göre değişir.

7.5.1Her türden tek kaynak

Her kaynak türünün tek örneği varsa kilitlenme, tahsis çizgesindeki döngüyle aynı şeydir. Tanenbaum'un örneğinde yedi süreç (A–G) ve altı kaynak (R–W) vardır:

• A, R'yi tutar ve S'yi ister.
• B hiçbir şey tutmaz ama T'yi ister.
• C hiçbir şey tutmaz ama S'yi ister.
• D, U'yu tutar; S'yi ve T'yi ister.
• E, T'yi tutar ve V'yi ister.
• F, W'yi tutar ve S'yi ister.
• G, V'yi tutar ve U'yu ister.

Soru şudur: sistem kilitlenmiş mi, kilitlendiyse hangi süreçler? Çizge çizildikten sonra cevap göz ile bulunabilir. D → T → E → V → G → U → D bir döngüdür; D, E ve G kilitlenmiştir. A, C ve F kilitli değildir. S boştadır; üçünden biri S'yi alır, işini bitirip bırakır, sonra öteki alır. B'nin durumu ise farklıdır: B döngüde değildir ama döngüdeki T'yi beklediği için o da ilerleyemez. Bu küçük çizgede göz yeter. Yüzlerce düğümlü bir çizgede ise sistematik bir algoritma gerekir.

7.5.2Döngü arama algoritması

Tanenbaum'un verdiği algoritma çizgedeki her düğümü sırayla başlangıç noktası yapar ve o düğümden derinlik öncelikli ilerler. Gidilen yol bir L listesinde tutulur. Bir düğüm L'ye ikinci kez eklenirse döngü bulunmuştur.

1. Çizgedeki her N düğümü için 2–6. adımları N'den başlayarak uygula.
2. L'yi boş liste yap; bütün kenarları işaretsiz say.
3. Geçerli düğümü L'nin sonuna ekle. Düğüm L'de iki kez geçiyorsa çizgede döngü vardır: L'deki döngüyü raporla ve dur.
4. Geçerli düğümden çıkan işaretsiz bir kenar var mı? Varsa 5. adıma, yoksa 6. adıma git.
5. İşaretsiz kenarlardan birini seç, işaretle ve gösterdiği düğüme geç; 3. adıma dön.
6. Başlangıç düğümündeysek N'den erişilebilen bir döngü yoktur. Değilsek çıkmaz sokaktayız: düğümü L'den çıkar, önceki düğüme dön ve 4. adımdan devam et.

Algoritmanın özü her düğümden başlayan bir derinlik öncelikli aramadır (depth-first search, DFS); yığın görevini L listesi görür. Bu basit sürüm her düğümden yeniden başladığı için en kötü durumda O(V · (V + E)) zaman alır. Düğümleri üç renge boyayan sürüm ise tek geçişte O(V + E)'de çalışır. Çıktıda L'nin tekrar eden düğümden sonraki kısmı döngüdür ve içindeki süreçler kilitlenmiştir.

Altıncı adımda “önceki düğüme dön” denildiğinde o düğüm zaten L'dedir. Bu yüzden 3. adıma değil 4. adıma gidilir; 3. adıma gidilseydi düğüm ikinci kez eklenir ve sahte bir döngü raporlanırdı. Tanenbaum'un metni bu adımda kısaca “3. adıma git” der; anlamı, düğümü yeniden eklemeden çıkış kenarlarına bakmaktır.

7.5.3Döngü arama adım adım

Algoritmayı Şekil 7.14'teki çizgede çalıştıralım. Başlangıç düğümleri şekildeki sırayla, yani soldan sağa ve yukarıdan aşağı seçilir: R, A, B, C, S, D, T, E, F, U, V, W, G. Bir düğümden birden çok kenar çıkıyorsa seçim keyfidir; burada D'den önce S'ye, sonra T'ye giden kenar seçilir. Tablo 7.5 L'nin her adımdaki hâlini verir.

Algoritma B'den başlayan aramada durur. L = [B, T, E, V, G, U, D, T] listesinde T iki kez geçer. Tekrar eden düğümün ilk geçişinden sonraki kısım, yani T, E, V, G, U, D döngüdür. Döngüdeki süreçler D, E ve G'dir; bunlar kilitlenmiştir. B listenin başındadır ama döngüde değildir: döngüye giden bir yolun üzerindedir. Çizgeyi göz ile incelerken bulduğumuz sonucun aynısı çıkar. Bu sonuçlar Python'da aynı algoritmanın yeniden çalıştırılmasıyla doğrulanmıştır.

7.5.4Kod izleme: renkli derinlik öncelikli arama

Her düğümden yeniden başlamak gereksiz iş yapar. Renkli DFS her düğüme bir renk verir. Beyaz düğüm henüz ziyaret edilmemiştir. Gri düğüm şu an yığındadır, yani gidilen yolun üzerindedir. Siyah düğümün ise bütün komşuları işlenmiş ve düğüm bitmiştir. Gri bir düğüme giden kenara geri kenar denir ve döngü olduğunu gösterir. Aşağıdaki kod bekleme çizgesini bekler[u][v] komşuluk matrisiyle tutar: bekler[u][v] 1 ise u, v'yi bekliyordur.

enum { BEYAZ, GRI, SIYAH };
int renk[N];          /* hepsi BEYAZ */
bool dongu(int u) {
  renk[u] = GRI;      /* yolda */
  for (int v = 0; v < N; v++) {
    if (!bekler[u][v]) continue;
    if (renk[v] == GRI)
      return true;    /* geri kenar */
    if (renk[v] == BEYAZ && dongu(v))
      return true;
  }
  renk[u] = SIYAH;    /* bitti */
  return false;
}

Kodun mantığı şöyledir. dongu(u) çağrıldığında u griye boyanır. Ardından u'nun beklediği her v denenir. v griyse yol kendi üstüne dönmüştür ve true döner. v beyazsa dongu(v) özyinelemeli olarak çağrılır. O çağrı döngü bulursa true yukarı taşınır. Siyah komşular atlanır, çünkü onlardan döngü çıkmadığı zaten bilinir. Bütün komşular bitince u siyaha boyanır ve false döner. Her düğüm en çok bir kez griye boyanır ve her kenar bir kez incelenir; maliyet O(V + E)'dir. Komşuluk matrisiyle kenarları bulmak her düğümde N adım sürdüğü için bu kodun gerçek maliyeti O(N²)'dir.

Çizgede beş süreç vardır ve kenarlar şunlardır: P1 → P2, P2 → P3, P2 → P4, P4 → P5 ve P5 → P2. Arama P1'den başlar. for döngüsü komşuları numara sırasıyla denediği için P2'den önce P3'e, sonra P4'e gidilir. Tablo 7.6 her adımdaki renkleri, Şekil 7.16 de önemli anları gösterir.

Döngü P2 → P4 → P5 → P2'dir ve bu üç süreç kilitlenmiştir. Gri düğümler o anda yığındaki yolu oluşturur; döngü, geri kenarın gösterdiği gri düğümden (P2) yığının tepesine (P5) kadar olan kısımdır. P1 de gridir, ama geri kenar P1'e değil P2'ye gittiği için P1 döngüde değildir. P1, P2'yi beklediği için yine de ilerleyemez.

7.5.5Her türden çok kaynak: vektörler ve matrisler

Kaynak türlerinin birden çok örneği varsa döngü aramak yetmez. Bunun yerine tahsis ve istek bilgisi matrislerle tutulur ve “herkes bir sırayla bitebilir mi?” sorusu sorulur. n süreç ve m kaynak türü olsun. Algoritma dört veri yapısı kullanır.

• E (var olan kaynaklar): E_j, j türünden sistemde toplam kaç örnek olduğudur.
• A (boştaki kaynaklar): A_j, j türünden şu an boşta kaç örnek olduğudur.
• C (tahsis matrisi): C'nin i. satırı P_i'nin şu an tuttuğu kaynaklardır.
• R (istek matrisi): R'nin i. satırı P_i'nin şu an istediği ve beklediği kaynaklardır.

Bu yapılar arasında değişmeyen bir bağıntı vardır: her j türü için Σ_i C_ij + A_j = E_j. Bir kaynak örneği ya bir sürecin elindedir ya da boştadır. Silberschatz aynı yapıları Available, Allocation ve Request adlarıyla verir.

Algoritma satırları vektör olarak karşılaştırır. İki vektör için X ≤ Y ancak ve ancak her j için X_j ≤ Y_j ise doğrudur. Örneğin (1 0 1 0) ≤ (2 1 0 0) yanlıştır: ilk iki bileşen uyar ama üçüncü bileşende 1 > 0'dır. Vektörlerde “küçük” kavramı her bileşende ayrı ayrı sağlanmalıdır; toplamları karşılaştırmak yanlış sonuç verir.

7.5.6Tespit algoritması

Algoritmanın fikri basittir. İsteği şu anki boş kaynaklarla karşılanabilen bir süreç çalışıp bitebilir. Bitince tuttuğu bütün kaynakları boş havuza geri verir; havuz büyüdüğü için başka bir sürecin isteği de karşılanabilir hâle gelebilir. Bu, hiçbir süreç kalmayana ya da kalanların hiçbiri karşılanamayana kadar tekrarlanır.

A ← boş kaynak vektörü
tüm Pi işaretsiz
tekrarla:
  Ri ≤ A olan işaretsiz bir Pi bul
  bulunamazsa: çık
  A ← A + Ci   /* Pi biter, bırakır */
  Pi'yi işaretle
işaretsiz Pi'ler kilitlenmiştir

“A ← A + C_i” satırı, biten sürecin tuttuğu kaynakların boş havuza döndüğünü ifade eder. Algoritma sonunda işaretsiz kalan süreçler kilitlenmiştir. Bu sonuç iyimser bir varsayıma dayanır: isteği karşılanan süreç ek kaynak istemeden bitecek sayılır. Süreç gerçekte bitmeden yeni bir istek yaparsa ve o istek kilitlenmeye yol açarsa, durum algoritmanın bir sonraki çalıştırılmasında yakalanır.

Maliyet şöyle hesaplanır. Her turda en çok n satır taranır ve her satır karşılaştırması m bileşenlidir. Her başarılı turda bir süreç işaretlendiği için en çok n tur olur. Toplam maliyet O(m · n²)'dir.

7.5.7Tespit örneği

Örnekte her işaretlemeden sonra tarama baştan başlar. Bu yüzden toplam altı karşılaştırma yapılır: ilk turda üç, ikinci turda iki, üçüncü turda bir. Bulunan sıra, algoritmanın satırları hangi sırayla taradığına bağlıdır; ama kilitlenme kararı değişmez. Bir sürecin bitmesi boş havuzu yalnızca büyütür, hiçbir zaman küçültmez. Bu yüzden bir aşamada karşılanabilen bir istek sonraki aşamalarda da karşılanabilir. Hangi sırayla taranırsa taransın, işaretlenebilen bütün süreçler sonunda işaretlenir. Tablo 7.7 A vektörünün değişimini özetler; bütün değerler Python'da algoritmanın kendisiyle yeniden hesaplanmıştır.

7.5.8Bir istek fazlası: kilitlenme

Aynı durumda tek bir hücreyi değiştirelim. P3 iki teyp ve bir çiziciye ek olarak bir CD de istesin: R₃ = (2 1 0 1). Boş vektör yine A = (2 1 0 0)'dır.

1. P1 ✗. CD gerekir, boşta CD yoktur.
2. P2 ✗. Tarayıcı gerekir, boşta tarayıcı yoktur.
3. P3 ✗. CD gerekir. Tek CD P2'dedir ve P2 bitemediği için hiç boşalmayacaktır.

İlk turda hiçbir satır karşılanamaz ve algoritma hemen biter. Üç süreç de işaretsiz kalır; üçü de kilitlenmiştir. Tek bir hücrenin değişmesi sonucu tümüyle değiştirmiştir. Algoritma döngü aramaz, ama kilitlenmiş süreçleri doğrudan verir; bu süreçler arasındaki bekleme ilişkisi kendiliğinden bir döngü oluşturur. P3, P2'deki CD'yi; P2, P1'deki tarayıcıyı ya da P3'teki tarayıcıları; P1 de P2'deki CD'yi bekler.

7.5.9Tespit ne zaman çalıştırılır?

Tespit algoritmasının ne sıklıkla çalıştırılacağı ayrı bir tasarım kararıdır. Üç seçenek vardır:

• Her istekte. Bekletilen her istekten sonra algoritma çalıştırılır. Kilitlenme oluştuğu anda, onu tetikleyen istekle birlikte bulunur. Ama işlemci maliyeti yüksektir.
• Periyodik. Algoritma her k dakikada bir çalışır. Ucuzdur; ama kilitlenme bir süre fark edilmeden kalır ve o sürede döngüye başka süreçler de takılabilir.
• Belirtiye göre. İşlemci kullanımı belirli bir eşiğin altına düştüğünde ya da bir kilit beklemesi uzadığında çalışır. Kilitlenen süreçler işlemci kullanmadığı için düşük kullanım iyi bir belirtidir.

Doğru sıklık, kilitlenmenin ne kadar olası olduğuna ve oluştuğunda kaç sürecin etkileneceğine bağlıdır. Tespitin yükü ihmal edilemez ve çalıştırma sıklığıyla doğru orantılıdır. Kurtarmanın maliyeti, yani kaybolan iş de hesaba katılır. PostgreSQL ara bir yol seçer: bir işlem bir kilidi deadlock_timeout kadar (varsayılan 1 saniye) beklemişse bekleme çizgesini tarar. Döngü bulursa işlemlerden birini iptal eder ve istemciye ERROR: deadlock detected iletisini döndürür. Böylece kısa sürede kendiliğinden biten beklemeler için tarama yapılmaz.

7.5.10Kilitlenmeden kurtarma

Kilitlenme bulunduktan sonra döngü bir şekilde kırılmalıdır. Kırmanın üç yolu vardır ve hiçbiri bedelsiz değildir.

• Kaynak kesme. Bir kaynak sahibinden geçici olarak alınıp başka sürece verilir. Örneğin bir yazıcının basmakta olduğu iş kenara alınır, basılmış kâğıtlar ayrılır ve yazıcı başka işe verilir. Bu yöntem kaynağın doğasına bağlıdır; çoğu zaman elle yapılır ya da hiç mümkün değildir.
• Geri sarma (rollback). Süreçler belirli aralıklarla denetim noktası (checkpoint) kaydeder: belleklerini ve kaynak durumlarını bir dosyaya yazar. Kurban, çekişilen kaynağı almadan önceki son denetim noktasına döndürülür ve kaynak bırakılmış olur. O noktadan sonra yapılan iş kaybolur. Veritabanlarında işlemin iptal edilmesi (abort) bunun karşılığıdır.
• Sonlandırma. En kaba yöntemdir. Ya döngüdeki bütün süreçler öldürülür ya da döngü kırılana kadar teker teker öldürülür. İkinci seçenekte her öldürmeden sonra tespit algoritması yeniden çalışır. Döngünün dışından bir süreç de seçilebilir; yeter ki bıraktığı kaynaklar döngüyü kırsın.

Kurban seçiminde amaç en düşük maliyettir. Maliyete katılan ilk etkenler sürecin önceliği, ne kadar süredir çalıştığı ve bitmesine ne kadar kaldığıdır. Tuttuğu kaynak sayısı ve bitmek için kaç kaynak daha istediği de hesaba girer. Sürecin etkileşimli mi yoksa toplu iş mi olduğuna ve güvenle yeniden başlatılıp başlatılamayacağına da bakılır. Bir derleme yeniden başlatılabilir; yarım kalmış bir veritabanı güncellemesi ise dikkat ister. Aynı süreç her seferinde kurban seçilirse hiç bitemez ve açlık oluşur. Bunu önlemek için sürecin kaç kez geri sarıldığı maliyete eklenir.

Önleme ve tespit kurtarma yöntemi değildir. Hiçbir kurtarma kesintisiz de değildir: her kurtarma yöntemi kaybedilen bir iş ya da yeniden çalıştırma maliyeti getirir.

7.5.11Kurtarma adım adım

Dört süreçli bir örnekte tespit algoritması P1 → R2 → P2 → R3 → P3 → R1 → P1 döngüsünü bulmuş olsun. P4 de R2'yi beklediği için takılıdır. Şekil 7.22 teker teker sonlandırmayla kurtarmayı gösterir.

1. Kurban seçimi. En az iş kaybettirecek süreç P3'tür. P3 sonlandırılır ya da denetim noktasına geri sarılır; tuttuğu R3 serbest kalır.
2. Tespit yeniden. P3'ün kenarları silindikten sonra çizgede döngü kalmamıştır.
3. Zincirleme ilerleme. R3, onu bekleyen P2'ye verilir. P2 işini bitirip R2 ile R3'ü bırakır. R2 sıradaki bekleyene, P1'e verilir; P1 bitince P4 de R2'yi alır.
4. Kurbanın yeniden çalışması. P3 baştan ya da son denetim noktasından yeniden başlatılır. Kaybedilen iş, P3'ün o noktadan sonra yaptığı iştir.

Teker teker sonlandırmada her kurbandan sonra tespit algoritması yeniden çalışır ve döngü kırılınca durulur. Bu örnekte tek kurban yetmiştir.

7.6Kilitlenmeden kaçınma

Tespit stratejisi kilitlenmeye izin verir ve sonra bedelini öder. Kaçınma stratejisi ise kilitlenmeye hiç izin vermez. Sistem her kaynak isteğinde “bu isteği verirsem ileride kilitlenme kaçınılmaz olur mu?” diye sorar ve cevap evetse isteği erteler. Bu soruyu cevaplamak için her sürecin en fazla ne kadar kaynak isteyebileceği önceden bilinmelidir.

7.6.1Kaynak yörüngeleri

Kaçınmanın fikri en açık biçimde iki süreçli bir çizimde görülür. Bu gösterim Dijkstra'ya dayanır. A ve B süreçleri bir yazıcı ve bir çizici kullanıyor olsun. A, I1 ile I3 komutları arasında yazıcıyı, I2 ile I4 arasında çiziciyi kullanır. B ise I5 ile I7 arasında çiziciyi, I6 ile I8 arasında yazıcıyı kullanır.

Yatay eksen A'nın, dikey eksen B'nin yürüttüğü komutları gösterir. Sistemin her anı düzlemde bir noktadır. Tek işlemci olduğu için yörünge yalnızca sağa (A çalışıyor) ya da yukarı (B çalışıyor) ilerler; çapraz gidemez. İki taralı bölge, iki sürecin aynı kaynağı aynı anda kullanacağı noktalardır. Karşılıklı dışlama nedeniyle bu bölgelere girilemez.

Yörüngeyi izleyelim. p → q arasında A çalışır; q → r arasında B çalışır. r → s arasında A yine çalışır ve I1'de yazıcıyı alır. s → t arasında B ilerler ve I5'te çiziciyi isteyecektir. Kırmızı kutu, A'nın yazıcıyı, B'nin de çiziciyi tuttuğu bölgedir. Yörünge bu kutuya girerse iki süreç de sağa ya da yukarı ilerlemek için taralı bölgelerden birine girmek zorunda kalır. Bu imkânsız olduğu için kilitlenme kaçınılmazdır. Kutunun içinde henüz kimse bloke değildir, ama sonuç kesindir. Bu yüzden bu bölgeye güvensiz denir.

Kaçınma, yörüngeyi güvensiz bölgeye sokacak isteği ertelemektir. t noktasında işletim sistemi B'nin çizici isteğini bekletir. A, I4'e kadar çalışıp iki kaynağı da bırakır; ardından B devam eder ve kilitlenme olmaz. Burada kritik olan, işletim sisteminin A'nın ileride çiziciyi isteyeceğini bilmesidir. Bu bilgi olmadan t'deki istek zararsız görünürdü.

7.6.2Güvenli ve güvensiz durumlar

Yörünge çizimi iki süreç ve iki kaynakla sınırlıdır. Genel durumda kaçınma, sistemin durumuna bakar. Durum, var olan kaynaklar E, boştakiler A, tahsis matrisi C ve her sürecin azami ihtiyacı (Max) ile belirlenir.

Tanımın mantığı tespit algoritmasınınkiyle aynıdır, tek fark bakılan satırdır. Tespitte süreçlerin şu anki istekleri karşılanabiliyor mu diye bakılır. Kaçınmada ise en kötü durum varsayılır: her süreç azamisine kadar isteyecek sayılır ve kalan ihtiyacı karşılanabiliyor mu diye bakılır. Dizideki ilk süreç kalan ihtiyacını boştaki kaynaklarla karşılar, biter ve her şeyi bırakır. İkinci süreç bu büyümüş havuzla karşılanır ve zincir böyle sürer.

Güvensiz durum kilitlenmiş durum değildir. Güvensiz durumda henüz kimse kalıcı olarak bloke değildir. Süreçler azami isteklerini yapmazsa, örneğin biri ek isteğini yapmadan bir kaynağı bırakırsa, her şey yolunda gidebilir. Fark şudur: güvenli durumda sistem herkesin bitmesini garanti edebilir; güvensiz durumda bu garanti yoktur. Kaçınma algoritması sistemi her zaman güvenli durumda tutar ve güvensiz duruma götürecek her isteği erteler.

7.6.3Güvenli durum örneği

Tek kaynak türünden 10 örnek olsun. Tablolarda “Has” sürecin şu an tuttuğu, “Max” bitene kadar gerekecek en çok örnek sayısıdır. Kalan ihtiyaç Max − Has'tir. Kaçınmada işletim sistemi isteklerin sırasını kendisi seçebilecek konumdadır: güvenli bir dizi varsa süreçleri o diziye göre bitirebilir.

7.6.4Güvensiz durum örneği

Aynı başlangıçtan çıkalım; fark tek bir karardadır. A bir örnek daha ister ve işletim sistemi bunu verir.

Burada henüz kilitlenme yoktur. A ek isteğini yapmadan bir örneği bırakırsa sorun çıkmayabilir. Ama işletim sistemi en kötü durumu varsayar: herkes azami isteğini yaparsa bitiş garanti değildir. Kaçınma, bu garantiyi kaybettiren isteği vermez.

7.6.5Bankacı algoritması: tek kaynak türü

Dijkstra 1965'te kaçınma algoritmasını bir banka benzetmesiyle anlattı. Bir küçük kasaba bankacısı müşterilerine kredi limitleri açar. Limitlerin toplamı kasadaki paradan fazladır, çünkü bütün müşteriler aynı anda limitlerinin tamamını istemez. Bankacı her istekte “bu krediyi verirsem bütün müşterilerimin limitlerini sonunda karşılayabilir miyim?” diye sorar.

Güvenlik sınaması şöyle yapılır: kalan ihtiyacı kasadaki parayla karşılanabilen bir müşteri bulunur; bu müşteri bitmiş sayılır ve kredisi kasaya eklenir. Bu işlem bütün müşteriler bitene kadar ya da kimse karşılanamayana kadar tekrarlanır.

Durum, yalnız bir sürecin değil bütün süreçlerin bir sırayla bitebildiği zaman güvenlidir. Bankacı algoritması kilitlenmeyi sonradan çözmez; sistemi hiç kilitlenmeye sokmaz. Bedeli de bellidir: (c) durumunda kasada fiilen para varken B bekletilir.

7.6.6Bankacı algoritması: çok kaynak türü

Algoritma çok kaynak türüne doğrudan genellenir. n süreç ve m kaynak türü için Silberschatz'ın adlandırmasıyla dört veri yapısı tutulur:

• Available[m]: her türden boştaki örnek sayısı.
• Max[n][m]: her sürecin önceden bildirdiği azami istek.
• Allocation[n][m]: her sürecin şu an tuttuğu örnekler.
• Need[n][m] = Max − Allocation: kalan ihtiyaç.

Algoritmanın iki parçası vardır. Güvenlik algoritması bir durumun güvenli olup olmadığını söyler:

/* güvenlik algoritması */
Work ← Available
Finish[i] ← false  (tüm i)
while Finish[i] = false ve
      Need[i] ≤ Work olan i var:
  Work ← Work + Allocation[i]
  Finish[i] ← true
tüm i için Finish[i] ise GÜVENLİ

Work, sınama sırasında boş havuzu temsil eden geçici bir vektördür; Available'ın kendisi değiştirilmez. Finish[i], i. sürecin bitmiş sayılıp sayılmadığını tutar. Kalan ihtiyacı Work ile karşılanabilen bitmemiş bir süreç bulundukça o süreç bitmiş sayılır ve tuttukları Work'e eklenir. Sonunda bütün Finish değerleri doğruysa durum güvenlidir.

İstek algoritması ise bir süreç Request[i] istediğinde çalışır:

/* Ti, Request[i] isterse */
if Request[i] > Need[i]:
  hata  /* Max aşıldı */
if Request[i] > Available:
  Ti bekler  /* kaynak yok */
/* varmış gibi yap: */
Available  -= Request[i]
Allocation[i] += Request[i]
Need[i]    -= Request[i]
if güvenli: isteği ver
else: geri al, Ti bekler

İlk sınama bir hata denetimidir: süreç bildirdiği azamiden fazlasını isteyemez. İkinci sınama kaynakların şu an fiilen boşta olup olmadığına bakar; değilse süreç zaten beklemek zorundadır. İki sınama da geçerse algoritma isteği verilmiş gibi yapar: üç yapıyı günceller ve yeni durumda güvenlik algoritmasını çalıştırır. Durum güvenliyse değişiklikler kalıcı olur. Güvensizse üç değişiklik geri alınır ve süreç bekletilir.

Güvenlik algoritmasının maliyeti tespit algoritmasınınkiyle aynıdır: O(m · n²). Fark, bu sınamanın her istekte çalışmasıdır.

7.6.7Güvenlik algoritması: örnek

Silberschatz'ın klasik örneğinde beş iş parçacığı (T0–T4) ve üç kaynak türü vardır: A türünden 10, B türünden 5, C türünden 7 örnek. Tahsis ve azami istekler şöyledir:

Tahsislerin sütun toplamı (7 2 5)'tir; Available = (10 5 7) − (7 2 5) = (3 3 2). Need sütunu Max − Allocation ile hesaplanmıştır. Güvenlik algoritması Work = (3 3 2) ile başlar ve satırları T0'dan başlayarak kaldığı yerden döngüsel olarak tarar.

Work ← Available
Finish[i] ← false
for i = T0 … T4 (tekrar tekrar):
  if Finish[i] = false and
     Need[i] ≤ Work:
    Work ← Work + Allocation[i]
    Finish[i] ← true
if tüm Finish[i]: GÜVENLİ

Bütün Finish değerleri doğrudur ve sonunda Work = (10 5 7), yani bütün kaynaklardır. Durum güvenlidir; bulunan güvenli dizi ⟨T1, T3, T4, T0, T2⟩'dir. Güvenli dizi tek değildir. Bütün sıralar denendiğinde bu durum için 16 güvenli dizi bulunur; ⟨T1, T3, T4, T2, T0⟩ de bunlardan biridir. Hepsinin ortak noktası ilk sürecin T1 ya da T3 olmasıdır, çünkü başlangıçtaki (3 3 2) ile yalnız bu ikisi karşılanabilir.

7.6.8İstek kabulü

Aynı durumda T1, Request₁ = (1 0 2) istesin. İstek algoritması üç adımda karar verir.

Güvenlik testi “varmış gibi” durumda yapılır. Durum güvensiz çıksaydı üç değişiklik de geri alınırdı ve T1 bekletilirdi.

7.6.9İstek reddi

T1'in isteği verildikten sonra iki yeni istek gelsin. Bu iki istek, bir sürecin bekletilmesinin iki farklı nedenini gösterir.

Birinci nedende kaynak yoktur; ikincide kaynak vardır, ama vermek durumu güvensiz yapar. Kaçınmanın bedeli ikinci nedendir: kaynaklar bazen boşta beklerken istekler ertelenir ve kaynak kullanım oranı düşer.

7.6.10Kod izleme: bankacı istek algoritması

İstek ve güvenlik algoritmalarını birlikte izlemek için başlangıç durumuna dönelim: Available = (3 3 2). Bu kez T3, Request = (0 1 1) istiyor. Kod iki algoritmayı bir arada verir:

/* Ti, Request isterse */
if Request > Need[i]: hata /* Max aşıldı */
if Request > Available: Ti bekler
Available -= Request  /* varmış gibi */
Allocation[i] += Request
Need[i] -= Request
if guvenli(): isteği VER
else: geri al, Ti bekler
guvenli():
  Work ← Available; Finish ← false
  for i = T0 … T4 (tekrar tekrar):
    if !Finish[i] and Need[i] ≤ Work:
      Work ← Work + Allocation[i]
      Finish[i] ← true
  return tüm Finish[i]

İzlemede dikkat çeken nokta, T1'in ilk turda bitememesidir. Başlangıç durumunda T1 hemen bitebiliyordu. Ama T3'e bir B ve bir C verildiği için Work = (3 2 1) olmuştur; T1'in C ihtiyacı ise 2 > 1'dir. T3'ün kalan ihtiyacı (0 0 0)'a indiği için T3 hemen biter ve tuttuğu (2 2 2)'yi geri verir; bundan sonra zincir kurulur. Bütün değerler Python'da istek ve güvenlik algoritmalarının kendisiyle yeniden hesaplanmıştır.

7.6.11İkinci örnek

Tanenbaum'un çok kaynaklı örneğinde beş süreç (A–E) ve dört kaynak türü vardır: teyp (Tp), çizici (Pl), yazıcı (Yz) ve CD. Var olan kaynaklar E = (6 3 4 2), atanmış kaynakların toplamı P = (5 3 2 2)'dir. Boştakiler A = E − P = (1 0 2 0)'dır.

“Her satırda ≤ A olan satırı ara” adımları burada güvenlik testidir. Aynı mantık tespit algoritmasında istek matrisiyle, kaçınmada kalan ihtiyaç matrisiyle kullanılır. İki algoritmanın kodu neredeyse aynıdır; değişen yalnızca karşılaştırılan satırın anlamıdır.

7.6.12Bankacı algoritması pratikte

Bankacı algoritması zarif bir fikirdir, ama dört varsayıma dayanır:

• Her süreç azami ihtiyacını önceden bildirir.
• Süreç sayısı sabittir.
• Kaynak sayısı değişmez; örneğin bir aygıt bozulmaz.
• Süreçler kaynakları sonlu bir sürede bırakır.

Bu varsayımlar genel amaçlı işletim sistemlerinde tutmaz. Bir kelime işlemcinin ne kadar bellek ya da kaç dosya kilidi isteyeceği önceden bilinmez; süreçler sürekli doğar ve ölür; bir disk bozulabilir. Bu yüzden algoritma gerçek işletim sistemlerinde neredeyse hiç kullanılmaz. Benzer bir “kabul denetimi” fikri ise yaygındır. Gerçek zamanlı çizelgelemede yeni görevin öteki görevlerin zaman garantilerini bozup bozmadığına bakılır. Bulut sistemlerinde kotalar, bağlantı havuzlarında da üst sınırlar konur.

Kaçınma, her istekte O(m · n²) maliyetli bir test ve gereksiz ertelemeler yüzünden tespit ve kurtarmadan genellikle daha pahalıdır. Avantajı kurtarma gerektirmemesidir. Algoritma arka planda sürekli çalışmaz: test yalnız bir istek geldiğinde ve bir kaynak bırakıldığında bekleyen istekler için yapılır.

Kilitlenme ve bankacı algoritması simülatörü, Allocation, Max, Need ve Available tablolarıyla güvenli dizi aramayı ve istek denetimini adım adım çalıştırır. Bu kesimdeki örnekler simülatörde de denenebilir.

7.7Kilitlenmeyi önleme

Kaçınma, süreçlerin gelecekteki isteklerini bilmeyi gerektirir ve bu bilgi pratikte yoktur. Önleme ise daha kökten bir yol izler: dört koşul birlikte gerekli olduğuna göre, birini sistemden tümüyle kaldırmak kilitlenmeyi imkânsız kılar. Karar çalışma anında değil, tasarımda verilir.

7.7.1Koşullara saldırmak

Tablo 7.11 her koşul için kullanılan yöntemi ve bedelini özetler.

İki yanlış anlama sık görülür. Karşılıklı dışlamayı kaldırmak “her seferinde yalnız bir süreç kaynak isteyebilir” demek değildir; bu, dışlamanın kendisidir. “Kesme yok” koşulunu kaldırmak da “süreç bitene kadar kaynakları tutsun” demek değildir; tersine, kaynakların sahibinden geri alınabilmesi demektir.

7.7.2Karşılıklı dışlamaya saldırı

Bir kaynak aynı anda birden çok sürece verilebiliyorsa kimse onu beklemez ve kilitlenmeye katılamaz. Yazıcı bunun klasik örneğidir.

Süreçler açısından yazıcı artık paylaşılabilir: herkes aynı anda iş bırakabilir, gerçek aygıtı tek bir süreç kullanır. Yazıcı için çekişme kalkar. Başka örnekler de vardır. Salt okunur dosyalar ve programların kod sayfaları aynı anda paylaşılır. Okur kilitleri birbirini dışlamaz; yalnız yazar kilidi dışlar. Kilitsiz (lock-free) veri yapıları karşılaştır ve değiştir (compare-and-swap, CAS) komutuyla ilerler; kilit olmadığı için kilitlenme de olmaz, ama açlık hâlâ mümkündür.

Yöntemin bir sınırı vardır: biriktirme diski de bir kaynaktır. Tanenbaum'un verdiği örnekte birçok süreç çıktısının yarısını diske yazmış ve disk dolmuştur. Hiçbir çıktı tamamlanmadığı için arka plan süreci basmaya başlamaz, süreçler de yer bekler: yine kilitlenme. Genel ilke şudur: bir kaynak gerçekten gerekmedikçe atanmaz ve onu isteyebilecek süreçlerin sayısı en aza indirilir.

7.7.3Tut ve beklemeye saldırı

Hiçbir süreç bir kaynağı tutarken başka bir kaynak beklemezse halka kurulamaz. Bunu sağlamanın iki protokolü vardır:

1. Protokol 1. Süreç ihtiyaç duyacağı bütün kaynakları çalışmaya başlamadan önce tek bir istekte alır: hepsi ya da hiçbiri.
2. Protokol 2. Süreç yalnız elinde hiçbir kaynak yokken istek yapabilir. Yeni bir kaynak istemeden önce tuttuklarının hepsini bırakır.

Silberschatz'ın örneğinde bir süreç DVD'deki veriyi diske kopyalar, diskteki dosyayı sıralar ve sonucu yazıcıya basar. Protokol 1'de süreç DVD sürücüsünü, disk dosyasını ve yazıcıyı başta alır. Yazıcı yalnız en sonda gerektiği hâlde baştan sona tutulur ve kimse kullanamaz. Protokol 2'de süreç önce DVD ile diski alır, kopyalar ve ikisini bırakır; sonra diski ve yazıcıyı alır. Kullanım artar ama başka sorunlar çıkar: süreç ikinci kez diski istediğinde başka biri dosyayı değiştirmiş olabilir.

İki protokolün ortak sorunları vardır. Kaynak kullanımı düşer, çünkü kaynaklar gerekmediği zamanlarda da tutulur. Çok sayıda popüler kaynak isteyen bir süreç, hepsi aynı anda boş olmadığı için hiç başlayamayabilir; bu da açlıktır. Ayrıca ihtiyaçlar çoğu zaman önceden bilinmez. Pratikte bu fikir iki yerde yaşar: pthread_mutex_trylock ile “ya hepsi ya hiçbiri” edinimi ve veritabanlarında bütün kilitleri baştan alan muhafazakâr iki aşamalı kilitleme.

7.7.4Kesme yok koşuluna saldırı

Kaynaklar zorla geri alınabiliyorsa bekleme halkası kırılabilir. Silberschatz şu geri alma protokolünü verir: kaynak tutan bir süreç hemen karşılanamayan bir istek yaparsa, tuttuğu bütün kaynaklar örtük olarak bırakılır. Süreç, eski kaynaklarını ve yeni istediğini birlikte alabildiğinde yeniden başlar.

Bu protokol yalnız durumu kaydedilip geri yüklenebilen kaynaklara uygundur: işlemci yazmaçları, bellek, veritabanı işlemleri. Yarıda kesilen bir yazıcı işi ya da bir mutex ile korunan veri yapısı bu yolla geri alınamaz. Bazı kaynaklar sanallaştırılarak kesilebilir hâle getirilir: yazıcı biriktirilir, bellek sayfalanır.

Mutex için uygulanabilir bir yol zaman aşımlı denemedir. İkinci kilidi belirli bir süre içinde alamayan iş parçacığı elindeki kilidi kendisi bırakır ve rastgele bir süre sonra yeniden dener. Kaynak zorla alınmaz, ama sahibi onu gönüllü olarak bırakır; sonuç aynıdır, halka kırılır.

7.7.5Kod izleme: tryLock ile geri alma

Java'da ReentrantLock.tryLock(süre, birim) kilidi en çok verilen süre kadar bekler; alırsa true, alamazsa false döndürür. Aşağıdaki yöntem bir hesaptan ötekine para aktarır. Her hesabın kendi kilidi vardır.

boolean dene(Hesap k, Hesap h, int m)
        throws InterruptedException {
  if (!k.kilit.tryLock(50, MILLISECONDS))
    return false;
  try {
    if (!h.kilit.tryLock(50, MILLISECONDS))
      return false;  /* k'yi de bırak */
    try { k.bakiye -= m; h.bakiye += m;
          return true; }
    finally { h.kilit.unlock(); }
  } finally { k.kilit.unlock(); }
}
/* çağıran: while (!dene(x, y, 1))
              Thread.sleep(rastgele); */

Yöntem önce kaynak hesabın (k) kilidini en çok 50 ms bekler. Alamazsa hemen false döner. Alırsa hedef hesabın (h) kilidini de 50 ms bekler. İkinci kilit alınamazsa return false çalışır; ama dıştaki finally bloğu dönüşten önce k'nin kilidini bırakır. Yani “k'yi de bırak” yorumunun gerçekleşmesini finally sağlar. İki kilit de alınırsa aktarım yapılır ve kilitler ters sırada bırakılır. Çağıran taraf yöntem başarılı olana kadar rastgele sürelerle uyuyup yeniden dener.

İki iş parçacığı ters yönde aktarım yapsın: T1 x'ten y'ye, T2 y'den x'e 1 birim. İki hesapta da başlangıçta 1000 birim vardır. Tablo 7.12 bir kötü zamanlamayı izler.

Adım 2'de döngüsel bekleme gerçekten oluşur, ama süresiz değildir. 52. milisaniyede T1 vazgeçip x'i bırakır; kesme yok koşulu gönüllü olarak kırılmıştır. Düz lock() kullanılsaydı kilitlenme t = 2 ms anında kesinleşirdi. Program JDK 21 ile 2 iş parçacığı ve 1000'er ters yönlü aktarımla çalıştırıldı: sonuç x=1000 y=1000 toplam=2000'dir ve program her seferinde bitmiştir.

Rastgele bekleme önemlidir. İki iş parçacığı hep aynı süre bekleyip aynı anda yeniden denerse aynı çakışma tekrar tekrar yaşanabilir. Süreçler bloke olmaz ama hiçbiri ilerlemez; bu duruma canlı kilit denir.

7.7.6Döngüsel beklemeye saldırı

Pratikte en çok kullanılan önleme yöntemi döngüsel beklemeyi kırmaktır. Her kaynak türüne bir numara verilir ve süreçlerin kaynakları yalnız artan numara sırasıyla istemesine izin verilir.

Yazıcı ve teyp gereken bir süreç önce 2'yi, sonra 4'ü ister. Teybi tuttuktan sonra yazıcıyı isteyemez.

Kuralın bir çeşidi de vardır: süreç K_j'yi isteyecekse elindeki bütün K_i (i ≥ j) kaynaklarını önce bırakır. Bu yöntemin en zor kısmı, bütün programların uyacağı uygun bir sıralamayı bulmaktır. Bir süreç işinin doğal akışında teybi yazıcıdan önce kullanıyorsa, kurala uymak için yazıcıyı gereğinden önce almak zorunda kalır.

7.7.7Kilit sıralaması pratikte

Kaynak numaralandırmanın yazılımdaki karşılığı kilit sıralamasıdır. Ters yönlü aktarım örneğine dönelim. T1 x'ten y'ye, T2 y'den x'e aktarıyor. “Doğal” sıra, yani önce kaynak hesabı, sonra hedef hesabı kilitlemek, iki iş parçacığında terstir ve kilitlenmeye açıktır. Çözüm, kilitleri hesapların kimlik numarasına göre almaktır; bu sıra bütün iş parçacıkları için ortaktır.

void transfer(Hesap k, Hesap h, int m) {
  Hesap ilk = k.id < h.id ? k : h;
  Hesap ikinci = k.id < h.id ? h : k;
  ilk.kilit.lock();
  try {
    ikinci.kilit.lock();
    try { k.bakiye -= m; h.bakiye += m; }
    finally { ikinci.kilit.unlock(); }
  } finally { ilk.kilit.unlock(); }
}
/* T1: transfer(x, y, 1)   x.id = 1
   T2: transfer(y, x, 1)   y.id = 2 */

ilk her zaman numarası küçük olan hesaptır, ikinci numarası büyük olan. Hangi yönde aktarım yapılırsa yapılsın kilitler aynı sırayla alınır. Aktarım satırı ise k ve h üzerinden yazıldığı için yön korunur. Şekil 7.38 iki iş parçacığının izini gösterir.

1. T1, transfer(x, y, 1) çağırır. x.id = 1 < y.id = 2 olduğu için ilk = x'tir. T1 x'i alır.
2. T2, transfer(y, x, 1) çağırır. k = y'dir ama ilk yine x'tir (id 1). T2 x'i bekler. Önemli olan, T2'nin beklerken elinde hiçbir kilit tutmamasıdır.
3. T1, y'yi de alır; y'yi kimse tutmuyordur. Aktarımı yapar.
4. T1 kilitleri bırakır. T2 x'i, sonra y'yi alır ve kendi aktarımını yapar.

Program JDK 21 ile her iş parçacığı 100 000 ters yönlü aktarım yaparak çalıştırıldı; sonuç x=1000 y=1000'dir ve kilitlenme olmamıştır. Linux çekirdeği de aynı yöntemi kullanır: aynı türden iki kilidi bellekteki adres sırasıyla alır. Çizelgeleyicinin iki çalışma kuyruğunu birlikte kilitleyen double_rq_lock fonksiyonu buna örnektir. Çekirdekteki kilit sırası belgelenir ve lockdep ile denetlenir.

7.8Diğer sorunlar

Kilitlenme, eş zamanlı programların tek sorunu değildir. Veritabanlarının kilitleme protokolü, iletilerle haberleşen süreçler, sürekli deneyen ama ilerlemeyen süreçler ve hiç sırası gelmeyen süreçler benzer ama farklı sorunlar doğurur. Bu kesim onları kilitlenmeden ayırır.

7.8.1İki aşamalı kilitleme

2PL'nin amacı kilitlenmeyi önlemek değil, serileştirilebilirliktir: eş zamanlı çalışan işlemlerin sonucu, işlemler sanki sırayla çalışmış gibi olur. Düz 2PL kilitlenebilir. T1 a kaydını, T2 b kaydını kilitler; sonra T1 b'yi, T2 a'yı ister. İki işlem de büyüme evresindedir ve birbirini bekler.

Tanenbaum bir çeşidini anlatır: birinci evrede işlem bütün kayıtları kilitlemeyi dener. Kayıtlardan birini başka bir işlem kilitlemişse elindekilerin hepsini bırakır ve baştan başlar. Bu çeşit tut ve beklemeyi kaldırır, çünkü işlem hiçbir zaman kilit tutarken beklemez. Günümüz veritabanlarında yaygın olan katı (strict) 2PL'de ise kilitler işlem sonunda, onaylama ya da iptal anında bırakılır. Bu çeşit de kilitlenebilir; veritabanı yönetim sistemi kilitlenmeyi bekleme çizgesiyle tespit eder ve işlemlerden birini geri sarar.

7.8.2İletişim kilitlenmeleri

Şimdiye kadarki kilitlenmelerin hepsi kaynak kilitlenmesiydi. İletilerle haberleşen süreçlerde kaynak olmadan da kilitlenme olabilir. A, B'ye bir istek gönderir ve yanıt bekler. İstek ağda kaybolursa A yanıtı, B de isteği sonsuza dek bekler. Her süreç yalnız ötekinin tetikleyebileceği bir olayı beklediği için bu bir kilitlenmedir; ama ortada tutulan bir kaynak yoktur.

Bu tür iletişim kilitlenmesinde kaynak sıralaması ya da kaçınma işe yaramaz, çünkü sıralanacak ya da hesaplanacak kaynak yoktur. Çözüm zaman aşımıdır: gönderen belirli bir süre yanıt alamazsa iletiyi yeniden gönderir. Bu da yeni bir sorun doğurur: asıl ileti kaybolmamış, yalnız gecikmişse alıcı aynı isteği iki kez alır. Yinelenen iletileri ayırt etmek için protokolde sıra numarası gerekir.

Ağ donanımında ise tamponlar gerçek kaynaktır. Şekil 7.40 dört yönlendiricinin halka biçiminde bağlandığı bir ağı gösterir.

Bu kez kilitlenme bir kaynak kilitlenmesidir ve döngüsel bekleme açıkça görülür. Çözümler de önleme fikirlerine dayanır: zaman aşımıyla paket düşürmek (kesme), sanal kanallar kullanmak ve kredi tabanlı akış denetimiyle tamponların dolmasını baştan engellemek.

7.8.3Canlı kilit

Dar bir koridorda karşılaşan iki kişi düşünelim. İkisi de kibar davranıp aynı anda sağa kayar, sonra aynı anda sola kayar. Kimse duvara çarpmaz, ikisi de sürekli hareket eder, ama kimse geçemez.

Tanenbaum'un örneğinde süreçler kaynakları meşgul beklemeyle alır. enter_region kilidi alamazsa döngüde dönmeye devam eder:

void process_A(void) {
  enter_region(&resource_1);
  enter_region(&resource_2);
  use_both_resources();
  leave_region(&resource_2);
  leave_region(&resource_1);
}  /* B: önce resource_2, sonra 1 */

B, kaynakları ters sırada alırsa A resource_1'i, B resource_2'yi alır. Sonra ikisi de ötekini alamadığı için sonsuza dek döner. Süreçler bloke değildir ve işlemci harcarlar; yine de ilerlemezler. Daha tipik bir canlı kilit, tryLock ile geri çekilen iki iş parçacığında görülür:

1. A r1'i, B r2'yi alır. A r2'yi dener, B r1'i dener; iki deneme de başarısız olur.
2. İkisi de kibar davranır: elindekini bırakır ve aynı süre sonra yeniden dener.
3. Aynı şey tekrarlanır. Süreçler bloke değildir, işlemci harcarlar ve durumları sürekli değişir; ama hiçbiri ilerlemez.

Çözüm ritmi bozmaktır. Rastgele ve her başarısızlıkta artan (exponential backoff) bir bekleme süresi, iki sürecin aynı anda yeniden denemesini olasılıksız kılar. Öncelik ya da sıra numarası vermek ve kilit sıralaması kullanmak da canlı kilidi önler. Ethernet'in CSMA/CD protokolündeki üstel geri çekilme aynı fikre dayanır: çarpışan iki istasyon rastgele sürelerle bekler.

7.8.4Açlık

Açlık, kaynak dağıtım politikasının sonucudur. Örneğin yazıcıyı her seferinde en küçük dosyaya vermek ortalama bekleme süresini azaltır. Ama sürekli yeni küçük işler geliyorsa 100 MB'lık büyük dosyaya hiç sıra gelmez.

Başka açlık örnekleri de vardır: katı öncelikli çizelgelemede düşük öncelikli bir iş, okur öncelikli okur-yazar kilidinde bir yazar, kurtarmada her seferinde kurban seçilen bir süreç. Çözüm ya ilk gelen ilk hizmet alır (FIFO) politikasıdır ya da bekledikçe sürecin önceliğini artıran yaşlandırmadır (aging). Tablo 7.14 üç sorunu karşılaştırır.

7.8.5Kilitlenme dışı hatalar: atomiklik ve sıra

Eş zamanlılık hatası denince akla ilk kilitlenme gelir, ama en yaygın hata kilitlenme değildir. Lu ve arkadaşları 2008'de MySQL, Apache, Mozilla ve OpenOffice'te 105 eş zamanlılık hatası incelemiştir. Bunların 74'ü kilitlenme dışıdır ve neredeyse hepsi iki kalıba uyar.

Atomiklik ihlali. Birlikte atomik olması gereken iki erişimin arasına başka bir iş parçacığı girer.

/* T1 */
if (oturum->ad != NULL)
    puts(oturum->ad);  /* artık NULL? */
/* T2 */
oturum->ad = NULL;

T1 önce oturum->ad'ın NULL olmadığını sınar, sonra onu yazdırır. İki satır arasında T2 alanı NULL yaparsa puts boş bir işaretçiyle çağrılır ve program çöker. Çare, sınama ile kullanımı ve T2'nin yazmasını aynı mutex altına almaktır.

Sıra ihlali. “A, B'den önce olur” diye varsayılır, ama bu sıra hiçbir şeyle zorlanmaz.

/* T1: baslat() */
isci = thread_olustur(govde);
/* T2: govde(), yeni iş parçacığı */
d = isci->durum;  /* isci atandı mı? */

T1, yeni iş parçacığını oluşturur ve tanıtıcısını isci değişkenine atar. Yeni iş parçacığı (T2) ise ilk satırında isci->durum'a erişir. Programcı atamanın önce yapılacağını varsaymıştır; ama yeni iş parçacığı, thread_olustur dönüp atama yapılmadan önce çalışmaya başlayabilir. O zaman isci henüz atanmamıştır. Çare, bir hazir bayrağı ve bir koşul değişkenidir: T2 while (!hazir) wait ile bekler, T1 atamadan sonra hazir = 1 yapıp signal gönderir. Sıfırdan başlayan bir semafor da aynı işi görür.

7.9Pratikte kilitlenme

Genel amaçlı işletim sistemleri kullanıcı programlarının kilitlenmesiyle ilgilenmez; sorumluluk programcıdadır. Bu kesim kilitlenmenin günlük kodda nasıl ortaya çıktığını, kapsüllemenin onu nasıl gizlediğini ve hangi araçlarla bulunduğunu Java ve Linux örnekleriyle anlatır. Bu kesimdeki Java programları JDK 21 ile derlenip çalıştırılmıştır.

7.9.1Java'da kilitlenme

Java'da her nesnenin bir monitörü vardır. synchronized (a) { … } bloğu a'nın monitörünü alır ve blok bitince bırakır. Monitör aynı anda tek bir iş parçacığına ait olabilir; bu, karşılıklı dışlamadır. Aşağıdaki iki iş parçacığı iki monitörü ters sırada alır:

Object a = new Object(), b = new Object();

Thread t1 = new Thread(() -> {
  synchronized (a) {
    uyu(10);   /* pencereyi büyüt */
    synchronized (b) { isle(); }
  }
}, "T1");
Thread t2 = new Thread(() -> {
  synchronized (b) {
    uyu(10);
    synchronized (a) { isle(); }
  }
}, "T2");
t1.start(); t2.start();

uyu(10), Thread.sleep(10)'u çağıran yardımcı bir yöntemdir; ilk kilit alındıktan sonra kilitlenme penceresini büyütür. isle() ise iki kilit altında yapılan işi temsil eder. Java iş parçacıklarının durumları da kilitlenmeyi izlemeye yardım eder: RUNNABLE çalışmaya hazır ya da çalışıyor, TIMED_WAITING süreli uykuda, BLOCKED ise bir monitörü bekliyor demektir.

JVM monitörleri kesilemez; bekleyen bir synchronized bloğunu kesmenin, zaman aşımı koymanın ya da kilidi geri almanın yolu yoktur. Program asla bitmez. uyu(10) kilitlenmeyi çok olası kılar, ama garanti etmez: bir iş parçacığı ikinci kilidi öteki daha başlamadan alırsa program normal biter. Bu notun doğrulamasında program JDK 21 ile çalıştırıldı ve beş çalıştırmanın beşinde de iki iş parçacığı BLOCKED kaldı. 10 ms yerine 50 ms uyuyan sürüm de sekiz saniyelik zaman aşımıyla durdurulana kadar hiçbir şey yazmadı. İki ilk kilit alınana kadar iş parçacıklarını bir CountDownLatch ile bekleten sürüm ise her çalıştırmada kilitlenir, çünkü zamanlamaya hiç yer bırakmaz.

7.9.2Kapsülleme kilit sırasını gizler

Ters sıralı kilitler her zaman kodda açıkça görünmez. Collections.synchronizedList bir listeyi sarar ve her yöntemini listenin kendi kilidiyle korur. a.addAll(b) çağrısı içeride önce a'nın kilidini alır. Sonra argümanın elemanlarını kopyalamak için b.toArray()'i çağırır; o da b'nin kilidini alır.

var a = Collections.synchronizedList(
          new ArrayList<Integer>());
var b = Collections.synchronizedList(
          new ArrayList<Integer>());
/* a.addAll(b) içeride:             */
/* synchronized (a) { b.toArray() }  */
/*   → synchronized (b) { ... }      */
new Thread(() -> a.addAll(b)).start();
new Thread(() -> b.addAll(a)).start();

/* Düzeltme: kopyayı kilit dışında al */
Integer[] k = b.toArray(new Integer[0]);
a.addAll(Arrays.asList(k));

İki iş parçacığı aynı anda a.addAll(b) ve b.addAll(a) çağırırsa ters sıralı edinim kendiliğinden oluşur: biri a → b, öteki b → a sırasıyla kilitler. Kodu yazan kişi hiçbir kilit görmez. Düzeltme, kopyayı kilit dışında almaktır: b.toArray() önce ayrı bir çağrıyla yapılır ve kendi kilidini bırakır; ardından a.addAll yalnız a'nın kilidini alır. Hiçbir an iki kilit birlikte tutulmaz.

Tablodaki ilginç satır Vector'dür. JDK 8'de Vector.addAll kendi kilidini tutarken argümanın toArray()'ini çağırır ve kilitlenir. JDK 21'de ise argümanın toArray()'ini kendi kilidini almadan önce çağırır; bu yüzden kilitlenmez. Aynı kaynak kod, kütüphanenin iç ayrıntısı değiştiği için farklı davranır. Kural şudur: kilit tutulurken yabancı bir yöntem, yani iç kilitlemesi bilinmeyen bir yöntem çağrılmaz. Bu notun doğrulamasında aynı deney yeniden yapıldı: JDK 8'de Vector ve synchronizedList 10 denemenin 10'unda kilitlendi. JDK 21'de synchronizedList 10 denemenin 9'unda kilitlendi, Vector hiç kilitlenmedi. Düzeltilmiş kod iki sürümde de hiç kilitlenmedi. Kilitlenme olasılığa bağlı olduğu için 9 ile 10 arasındaki fark beklenen bir oynamadır.

7.9.3Kilitlenmeyi bulmak: jstack

Kilitlenen bir Java programı hata iletisi vermez; yalnız durur. JDK ile gelen jstack aracı çalışan bir JVM'deki bütün iş parçacıklarının yığınlarını yazdırır ve kilitlenme varsa bunu raporun sonunda ayrıca belirtir:

$ jstack <pid>
Found one Java-level deadlock:
=============================
"T1":
  waiting to lock monitor 0x… (object 0x…, a java.lang.Object),
  which is held by "T2"
"T2":
  waiting to lock monitor 0x… (object 0x…, a java.lang.Object),
  which is held by "T1"

Java stack information for the threads listed above:
"T1":
        at Asili.calis(Asili.java:7)
        - waiting to lock <0x…d0> (a java.lang.Object)
        - locked <0x…c0> (a java.lang.Object)
…
Found 1 deadlock.

Rapor kimin hangi monitörü beklediğini ve o monitörün kimde olduğunu söyler: T1, T2'nin tuttuğu monitörü; T2 de T1'in tuttuğu monitörü bekler. Yığın bilgisi de kilitlenmenin kodun hangi satırında oluştuğunu gösterir. Bu notun doğrulamasında kilitlenen program JDK 21'de çalışırken jstack çalıştırıldı ve rapor aynı biçimde geldi: “Found one Java-level deadlock”, iki iş parçacığı için “waiting to lock” ve “which is held by” satırları, sonda da “Found 1 deadlock.”. Aynı rapor jcmd <pid> Thread.print ile de alınır; JConsole ve VisualVM gibi görsel araçlarda “Detect Deadlock” düğmesi aynı işi yapar.

Program kendi kilitlenmesini de bulabilir. ThreadMXBean arayüzü JVM'in iş parçacığı bilgisini verir:

ThreadMXBean mx =
    ManagementFactory.getThreadMXBean();
long[] ids = mx.findDeadlockedThreads();
if (ids != null)
  for (ThreadInfo ti : mx.getThreadInfo(ids))
    System.out.println(ti.getThreadName()
      + " bekliyor, kilit sahibi "
      + ti.getLockOwnerName());

findDeadlockedThreads(), kilitlenmiş iş parçacıklarının kimliklerini döndürür; kilitlenme yoksa null döndürür. Kilitlenen programda bu kod şu çıktıyı verir:

T1 bekliyor, kilit sahibi T2
T2 bekliyor, kilit sahibi T1

JVM, monitör ve ReentrantLock sahipliğinden bir bekleme çizgesi kurar ve döngü arar; yani tek örnekli kaynaklar için tespit algoritmasını çalıştırır. Ama yalnız tespit eder, kurtarmaz. JVM bir iş parçacığını öldürüp monitörünü başkasına veremez, çünkü korunan veri tutarsız kalabilir. Kilitlenen süreci yeniden başlatmak gerekir.

7.9.4lockdep ve öteki araçlar

Her ortamın kilitlenme için kendi araçları vardır. Tablo 7.17 başlıcalarını listeler.

Linux çekirdeğindeki lockdep farklı bir fikre dayanır. Her kilidi bir sınıfa bağlar; aynı türdeki bütün kilit örnekleri aynı sınıftır. Bir görev A sınıfından bir kilidi tutarken B sınıfından bir kilit alınca çizgeye “A → B” kenarı eklenir. Başka bir kod yolunda B tutulurken A alınırsa çizgede döngü oluşur ve lockdep “possible circular locking dependency” uyarısı verir.

İki kod yolu hiç aynı anda çalışmamış olabilir; lockdep yine de uyarır. Araçlar bu bakımdan ikiye ayrılır. lockdep ve ThreadSanitizer olası kilitlenmeyi, yani kilit sırası ihlalini bulur; kilitlenme hiç gerçekleşmemiş olsa bile. jstack ve Go çalışma zamanı ise gerçekleşmiş kilitlenmeyi raporlar. Birinci grup önleme, ikinci grup tespit stratejisinin araçlarıdır.

7.10Özet

• Kilitlenme, bir süreç kümesindeki her sürecin yalnız kümedeki başka bir sürecin tetikleyebileceği bir olayı beklemesidir. Kilitlenmeler kesilemez kaynaklarla ilgilidir; işlemci ve bellek gibi kesilebilir kaynaklar yeniden dağıtılabilir.
• Süreç kaynağı ister, kullanır, bırakır. İki kaynağı ters sırada almak, hiç kilitlenmeyen bir programı ara sıra kilitlenen bir programa dönüştürür.
• Dört koşul birlikte gereklidir: karşılıklı dışlama, tut ve bekle, kesme yok, döngüsel bekleme. İlk üçü politikadır, dördüncüsü o anki durumdur.
• Kaynak tahsis çizgesinde döngü yoksa kilitlenme yoktur. Tek örnekli kaynaklarda döngü ⇔ kilitlenme; çok örnekli kaynaklarda döngü gerekli ama yeterli değildir. Tek örnekli durumda bekleme çizgesi kullanılır.
• Dört strateji vardır: görmezden gelme (devekuşu), tespit ve kurtarma, kaçınma, önleme. Genel amaçlı işletim sistemleri kullanıcı süreçleri için devekuşu yaklaşımını seçer.
• Tek örnekli kaynaklarda tespit, döngü aramadır; renkli DFS O(V + E)'de çalışır. Çok örnekli kaynaklarda E, A, C, R yapılarıyla “isteği boştakilerle karşılanan süreç biter ve tuttuklarını bırakır” döngüsü çalıştırılır; maliyeti O(m · n²)'dir.
• Kurtarma kaynak kesme, geri sarma ya da sonlandırmayla yapılır ve her zaman bir iş kaybı getirir. Kurban seçiminde aynı süreç hep seçilirse açlık oluşur.
• Güvenli durumda herkesin azami isteğini yapması hâlinde bile bütün süreçleri bitiren bir dizi vardır. Güvensiz durum kilitlenme değildir, ama bitiş garantisi yoktur.
• Bankacı algoritması her isteği verilmiş gibi yapar ve yeni durum güvenliyse verir. Süreç iki nedenle bekletilir: kaynak yoktur ya da vermek durumu güvensiz yapar. Azami ihtiyaçların önceden bilinmesini gerektirdiği için pratikte nadiren kullanılır.
• Önleme koşullardan birini kırar. En etkili yöntem kilit sıralamasıdır: kilitler herkes için ortak bir sırayla alınırsa döngü oluşamaz. tryLock ile geri çekilme kesme yok koşulunu kırar, ama rastgele bekleme olmazsa canlı kilide yol açabilir.
• 2PL serileştirilebilirlik içindir ve kilitlenebilir. Açlık politikanın sonucudur ve yaşlandırmayla çözülür. En yaygın eş zamanlılık hataları ise kilitlenme değil, atomiklik ve sıra ihlalleridir.
• Java'da kilitlenme jstack ya da ThreadMXBean ile bulunur ama çözülmez. lockdep ve ThreadSanitizer olası kilitlenmeyi, kilitlenme yaşanmadan bildirir.

7.11Kavram listesi

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

• kilitlenme deadlock
• kesilebilir / kesilemez kaynak preemptable / nonpreemptable resource
• kilitlenmenin dört koşulu Coffman conditions
• karşılıklı dışlama mutual exclusion
• tut ve bekle hold and wait
• kesme yok no preemption
• döngüsel bekleme circular wait
• kaynak tahsis çizgesi resource allocation graph
• bekleme çizgesi wait-for graph
• kilitlenme tespiti deadlock detection
• kilitlenmeden kurtarma deadlock recovery
• denetim noktası checkpoint
• kilitlenmeden kaçınma deadlock avoidance
• güvenli / güvensiz durum safe / unsafe state
• bankacı algoritması banker's algorithm
• kilitlenmeyi önleme deadlock prevention
• biriktirme spooling
• mutex mutex
• semafor semaphore
• monitör monitor
• meşgul bekleme busy waiting
• iki aşamalı kilitleme two-phase locking (2PL)
• canlı kilit livelock
• açlık starvation
• yaşlandırma aging
• atomik komut atomic instruction
• yemek yiyen filozoflar problemi dining philosophers problem

7.12Kendini Dene

1. Bir sistemde süreçler kilitleri trylock ile alıyor. İkinci kilidi alamayan süreç elindeki kilidi bırakıyor ve hep tam 5 ms bekleyip yeniden deniyor. Hangi kilitlenme koşulu kırılmıştır? Bu tasarımda hangi yeni sorun ortaya çıkabilir ve nasıl giderilir?

   Cevap

   Süreç beklemek yerine elindeki kaynağı kendisi bırakır; kaynak sahibinden geri alınmış olur. Bu, kesme yok koşulunun gönüllü olarak kırılmasıdır. İki süreç aynı ritimde alıp bırakırsa hiçbiri ilerlemez: canlı kilit. Süreçler bloke değildir, işlemci harcarlar. Çare, bekleme süresini rastgele yapmak ve her başarısızlıkta artırmak (üstel geri çekilme) ya da kilitleri ortak bir sırayla almaktır.

2. Bekleme çizgesinde kenarlar P1 → P2, P2 → P3, P2 → P4, P4 → P5 ve P5 → P3'tür. Renkli DFS P1'den başlayıp komşuları numara sırasıyla deniyor. Döngü bulunur mu? Düğümler hangi sırayla siyaha boyanır?

   Cevap

   P1, P2, P3 sırayla griye boyanır. P3'ün komşusu yoktur; ilk siyah P3'tür. P2'nin sıradaki komşusu P4 beyazdır; P4 ve ardından P5 gri olur. P5'in tek komşusu P3 siyahtır; siyah düğüme giden kenar döngü değildir. P5 siyah olur, ardından P4, P2 ve P1. Siyaha boyanma sırası P3, P5, P4, P2, P1'dir ve dongu false döner: döngü yoktur. P5 → P3 kenarı yalnız iki yolun P3'te birleştiğini gösterir.

3. Üç kaynak türü vardır ve E = (3 2 2)'dir. Tahsisler P1 (1 0 1), P2 (1 1 0), P3 (0 1 1); istekler P1 (1 1 0), P2 (0 0 1), P3 (1 0 0)'dır. Tespit algoritması her işaretlemeden sonra baştan taranarak çalıştırılırsa sistem kilitlenmiş çıkar mı? P3'ün isteği (1 0 1) olsaydı ne olurdu?

   Cevap

   Tahsislerin toplamı (2 2 2)'dir; A = (1 0 0). P1 (1 1 0) ikinci türden ister, boşta yok. P2 (0 0 1) üçüncü türden ister, boşta yok. P3 (1 0 0) ≤ (1 0 0) ✓; P3 biter ve A = (1 1 1) olur. Baştan: P1 (1 1 0) ≤ (1 1 1) ✓, A = (2 1 2). P2 (0 0 1) ✓, A = (3 2 2) = E. Sıra P3, P1, P2'dir; kilitlenme yoktur. P3'ün isteği (1 0 1) olsaydı A = (1 0 0) iken üç satırın hiçbiri karşılanamazdı ve üç süreç de kilitlenmiş olurdu.

4. Tek türden 12 birim kaynak var. A 5 birim tutuyor (en çok 10), B 2 (en çok 4), C 2 (en çok 9). Durum güvenli mi? Güvenli diziler hangileridir? Bu durumda C bir birim daha isterse istek verilmeli mi?

   Cevap

   Boşta 12 − 9 = 3 birim vardır. Kalan ihtiyaçlar A 5, B 2, C 7'dir. Yalnız B karşılanabilir (2 ≤ 3); B biter, boş 5 olur. Sonra yalnız A karşılanabilir (5 ≤ 5); A biter, boş 10 olur. Son olarak C (7 ≤ 10) biter. Tek güvenli dizi ⟨B, A, C⟩'dir; durum güvenlidir. C'ye 1 birim verilirse boş 2, ihtiyaçlar A 5, B 2, C 6 olur. B biter ve boş 4'e çıkar; ama A'nın 5'i de C'nin 6'sı da karşılanamaz. Durum güvensizdir; istek reddedilir ve C bekletilir.

5. Beş süreç aynı türden kaynakları teker teker istiyor; her biri aynı anda en çok 3 örnek kullanıyor ve işi bitince hepsini bırakıyor. Kilitlenmenin hiç oluşmaması için en az kaç örnek gerekir? Bir eksiği kilitlenmeye nasıl yol açar?

   Cevap

   En kötü durumda her süreç 2 örnek tutup üçüncüyü bekler: 5 · 2 = 10 örnek. Bir örnek daha varsa süreçlerden biri üçüncüsünü alır, biter ve 3 örneği bırakır; ötekiler de sırayla biter. En az 5 · 2 + 1 = 11 örnek gerekir. 10 örnekte beş sürecin her biri ikişer örnek tutabilir; boşta örnek kalmaz ve herkes üçüncüyü bekler: kilitlenme.

6. Silberschatz örneğinin başlangıç durumunda (Available = (3 3 2)) T4, (3 3 0) istiyor. Bankacı algoritması ne karar verir? Aynı başlangıç durumunda T0, (0 2 0) isteseydi karar ne olurdu?

   Cevap

   T4: (3 3 0) ≤ Need₄ = (4 3 1) ve ≤ (3 3 2); iki denetim de geçer. Varmış gibi Available = (0 0 2), Need₄ = (1 0 1) olur. T0 (7 4 3), T1 (1 2 2), T2 (6 0 0), T3 (0 1 1) ve T4 (1 0 1) satırlarının hiçbiri (0 0 2) ile karşılanamaz: durum güvensizdir, istek reddedilir. T0: varmış gibi Available = (3 1 2), Need₀ = (7 2 3) olur. T3 (0 1 1) biter → (5 2 3); T1 (1 2 2) → (7 2 3); T2 (6 0 0) → (10 2 5); T0 (7 2 3) → (10 5 5); T4 (4 3 1) → (10 5 7). Güvenli dizi ⟨T3, T1, T2, T0, T4⟩ vardır; istek verilir. Aynı istek T1'in (1 0 2) isteğinden sonra reddediliyordu: karar isteğin kendisine değil, durumun tamamına bağlıdır.

7. Bir programda transfer(k, h) fonksiyonu kilitleri hesap numarası sırasıyla alıyor. Aynı programdaki rapor(h1, h2) fonksiyonu ise iki hesabın kilidini her zaman önce h1, sonra h2 sırasıyla alıyor. Program kilitlenebilir mi? Neden?

   Cevap

   Kilitlenebilir. Kilit sıralaması yalnız kilitlerin alındığı her yerde uygulanırsa döngüyü önler. rapor(y, x) çağrısı y'yi tutup x'i isteyebilir. Aynı anda transfer numara sırasıyla x'i tutup y'yi isterse döngü oluşur. Çare, rapor'u da aynı sıraya uydurmaktır. lockdep ya da ThreadSanitizer gibi araçlar bu ters sırayı kilitlenme hiç yaşanmadan bildirir.

8. Bir Java sunucusunda iki iş parçacığı canlı kilide girmiş, başka bir sunucuda iki iş parçacığı kilitlenmiştir. jstack hangisini “Found one Java-level deadlock” olarak raporlar? İşlemci kullanımı iki durumda nasıl görünür?

   Cevap

   jstack yalnız kilitlenmeyi raporlar: kilitlenen iş parçacıkları BLOCKED durumdadır ve monitör sahipliğinden kurulan bekleme çizgesinde döngü vardır. Canlı kilitteki iş parçacıkları RUNNABLE ya da kısa uykularda TIMED_WAITING görünür. Kilitleri sürekli alıp bıraktıkları için çizgede kalıcı bir döngü yoktur ve rapor çıkmaz. Kilitlenmede işlemci kullanımı düşer, çünkü iş parçacıkları uyur. Canlı kilitte ise işlemci meşgul görünür ama iş ilerlemez.

7.13İleri okuma

• A. S. Tanenbaum ve H. Bos, Modern Operating Systems (4. baskı), Bölüm 6: kaynak tahsis çizgesini, döngü arama ve matris tabanlı tespit algoritmalarını, kaynak yörüngelerini ve bankacı algoritmasını bu nottaki örneklerle ayrıntılı işler.
• A. Silberschatz, P. B. Galvin ve G. Gagne, Operating System Concepts (10. baskı, 2018), Bölüm 8: dört koşulu, önleme protokollerini ve bankacı algoritmasının güvenlik ve istek parçalarını sözde kodla verir; Linux lockdep aracını da tanıtır.
• R. H. Arpaci-Dusseau ve A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, “Common Concurrency Problems” bölümü: atomiklik ve sıra ihlallerini, kilitlenmenin dört koşulunu ve kilit sıralamasını gerçek sistemlerden alınmış hatalarla anlatır. Kitap çevrimiçi ve ücretsizdir.
• S. Lu, S. Park, E. Seo ve Y. Zhou, “Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics”, ASPLOS 2008: dört büyük açık kaynak projedeki 105 eş zamanlılık hatasını sınıflandıran ve kilitlenme dışı hataların ağırlığını gösteren çalışmadır.

7.14Kaynaklar

1. R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, Arpaci-Dusseau Books, ostep.org — “Common Concurrency Problems”.
2. E. G. Coffman, M. J. Elphick, A. Shoshani, “System Deadlocks”, ACM Computing Surveys 3(2), 1971.
3. E. W. Dijkstra, “Cooperating Sequential Processes”, EWD-123, 1965.
4. R. C. Holt, “Some Deadlock Properties of Computer Systems”, ACM Computing Surveys 4(3), 1972.
5. Linux çekirdek belgeleri: Documentation/locking/lockdep-design.rst.
6. S. Lu, S. Park, E. Seo, Y. Zhou, “Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics”, ASPLOS 2008.
7. Java SE 21 API belgeleri: java.lang.management.ThreadMXBean, java.util.concurrent.locks.ReentrantLock; jstack kılavuzu.
8. PostgreSQL belgeleri: “Explicit Locking — Deadlocks”, deadlock_timeout.
9. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018 — Bölüm 8: Deadlocks.
10. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı, Pearson, 2014 (5. baskı 2023) — Bölüm 6: Deadlocks.

İlgili sayfalar: Bölüm 7 sunumu · Çalışma soruları · Kilitlenme ve bankacı algoritması simülatörü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.