Hakkında Künye

Ölümcül Kilitlenme

Bu kadar korkunç bir başlıktan sonra, “yepyeni sayımızla karşınızdayız sevgili e-bergi severler” diye başlasam sanırım havayı biraz olsun ısıtabilirim. :) Bu ay sizlere, bilgisayarlarımızın ve bizim korkulu rüyamız olan kilitlenmeden bahsedeceğim. Dilimizde tam karşılığı hala oturmayan bu terim, yani “deadlock”, Türkçe'de “ölümcül kilitlenme” veya kısaca “kilitlenme” olarak kullanılmakta. Yalnız kilitlenme demişken, bilgisayarımızın isteklerimize her cevapsız kalmasını, yani her ekran donmasını diyelim, günlük hayatta kullandığımız gibi “aaa bilgisayarım kilitlendi!” olarak düşünmemekte yarar var.

Kilitlenme Nedir?

Dediğim gibi, bilgisayarın her cevapsızlığını kilitlenme olarak algılamamalıyız. Bunu daha iyi anlayabilmek için kilitlenmeyi tanımlamamız gerek; ancak bundan önce değinmek istediğim birkaç nokta var. İlki, kısaca işlem ve işlemcik konseptleri. İşlemi (process), çalışmakta olan herhangi bir program olarak tanımlayabiliriz. Mesela, Linux konsolunda “ps -aux” komutunu verdiğimizde, gördüğümüz bütün satırlar birer işlem bilgisini gösterir, böylece bilgisayarımızda o an çalışmakta olan bütün programların listesine ulaşabiliriz. İşlemcik (thread) ise, bir işlemin daha verimli yapılmasını sağlayacak biçimde parçalanmasıyla ortaya çıkan birbirinden bağımsız küçük işlemler olarak görülebilir. İşlemlerle işlemcikleri birbirinden ayıran en önemli özelliklerden biri, işlemlerin hepsinin kendine özel hafıza alanları (adres alanı) ve işletim sistemi kaynakları varken; işlemcikler parçası olduğu işlemin bu bölümlerinden faydalanırlar, yani paylaşırlar. Biraz fazla terim yükledim sanırım; ama basitçe, adres alanını bir programın her şeyiyle hafızada kapladığı alan olarak düşünebiliriz. İşletim sistemi kaynakları ise programın kullandığı açık dosyalar, soketler ve giriş çıkış aygıtları gibi yapılardır. Değinmek istediğim ikinci nokta ise, bu yapıların işletim sisteminin üstlerindeki etkisine göre boşaltılabilir ve boşaltılamaz olarak ikiye ayrılması. Örneğin; yazıcı bir yazma işlemindeyken, işletim sistemi yazıcıyı bu işlemden alıp başka bir işleme veremeyeceği için yazıcı boşaltılamaz bir işletim sistemi kaynağıdır. Öte yandan, işlemcinin (CPU) işlemler arasında kullanımına işletim sistemi karar verebildiğinden, CPU boşaltılabilir bir kaynaktır.

Trafik Gelelim kilitlenmeye. Kısaca; bir işlem veya işlemcik, bir işletim sistemi kaynağını kullanırken, başka bir kaynağa ihtiyaç duyuyorsa ve o kaynak da başka bir işlem veya işlemcik tarafından kullanılırken, kullanan işlem ilk kaynağa ihtiyaç duyuyorsa, iki işlem de devam edemeyeceğinden kilitlenme meydana gelir. Biraz karışık anlattım sanırım, başka bir deyişle, iki işlem veya işlemciğin birbirinin kaynaklarını beklemesinden kilitlenme oluşur. Resimdeki gibi, tek şeritli yolun iki araç tarafından da kullanılmak istenmesi sonucunda yolun tıkanması gibi :)
Yalnız hemen bir ekleme yapmak istiyorum; bir işlem ihtiyacı olan kaynağın tam kapasiteyle kullanılmasından dolayı ilerleme gösteremiyorsa, buna kilitlenme değil, açlık (starvation) denir. Kilitlenmeyle karıştırılması dışında konumuzla alakası yoktur :)

Kilitlenmenin Koşulları

Ölümcül kilitlenmenin ortaya çıkması için dört koşul var. Bu dördü birden aynı anda olmadıkça, kilitlenme gibi bir sorunumuz olmuyor.

1) Karşılıklı Dışlama (mutual exclusion)
Bir an bilgisayar biliminden dışarı çıkalım. Hepimizin bildiği gibi, iki nesnenin fiziksel olarak aynı anda aynı yerde olması nasıl mümkün değildir. Bu yüzden bir boşluğa, ya da alana, moleküler düzeyde de olsa iki şey aynı anda sahipr olamaz. Geri dönersek, karşılıklı dışlama, iki işlemin aynı anda bir kaynağın bir örneğini kullanamamasından başka bir şey değildir.

2) Çoklu Bağımsız İstekler (multiple independent requests)
Kilitlenmenin tanımında da söylediğim gibi, bir işlem bir kaynağa sahipken başka bir kaynak talebinde bulunduğunda, yani birden çok kaynak isteğinde bulunduğunda bu koşul sağlanır. İşlemin bir kaynağı tutup beklemesi olarak da düşünebiliriz.

3) Boşaltılamazlık (no preemption)
İşletim sistemi kaynaklarını anlatırken bahsettiğim boşaltılamaz kaynakların kilitlenmeye neden olması sonucunda, kilitlenmeye bir adım daha yaklaşır işlem :) Çoklu bağımsız istekler koşulundaki ilk kaynağı düşünelim, eğer işletim sistemi bu kaynağı bu işlemden alıp kilitlenmeye sebep olmayacak başka bir işleme verebilseydi, kilitlenme olmazdı. Bu yüzden boşaltılamaz kaynakların tutulup beklenmesi kilitlenmeye sebep oluyor.

4) Çembersel Bekleme (circular wait)
Sanırım kavramlar yavaş yavaş yerine oturmaya başladı. Evet tahmin edebileceğiniz gibi, kilitlenmenin olması için birden çok işlem veya işlemciğin olması gerek; çünkü demin de söz ettiğim gibi tek işlemin kendi kendine beklemesi açlık. Yani çember yoksa kilitlenme yok. Verdiğim örnekler hep iki işlemi içeriyor; fakat yeri gelmişken söyleyeyim, kilitlenme tam iki işlemle olmak zorunda değil. Çembersel olarak birbirini bekleyen en az iki işlemle kilitlenme ortaya çıkıyor. Bu yüzden, kilitlenme varsa mutlaka çembersel bir bekleme var diyebiliriz; ancak tersi kesin doğru değil. Çünkü çembersel bekleme varsa mutlaka kilitlenme olur diyemeyiz: bir kaynağın birden çok örneği varsa, bu örnekler farklı işlemler tarafından kullanılabilir ve çember olmasına rağmen kilitlenme oluşmaz.

Yemek Yiyen Filozoflar Problemi

Çatal kullansak?! :P

Bu ay başlıklarla aramız iyi :) Ama bu bilgisayar biliminde, kilitlenmeyi en iyi anlatan problem olan “the dining philosophers problem” den başka bir şey değil. Kısaca sevgili filozoflarımızın sorunu şu: Resimde de görüldüğü gibi, beş tane filozofumuz yemek yemek istiyor; fakat yemeği sopalarla yiyorlar. Maalesef her filozofa bir sopa düşüyor ve yemeğe hepsi aynı anda başlıyorlar. Bu yüzden hepsinin elinde birer tane sopa olmasına rağmen, hepsi diğer sopayı bekliyor ve hiçbiri yemek yiyemiyorlar. Böylece sonsuza kadar aç kalıyorlar!

Sorunu incelersek, tipik bir kilitlenme olduğunu anlayabiliriz. Bir sopayı iki filozofun aynı anda kullanamaması karşılıklı dışlama koşulumuz. Elinde bir sopa olması ve onu bırakmayıp diğer sopayı istemekte ısrar etmesi de çoklu bağımsız istekleri yerine getiriyor. Boşaltılamazlığı da, dışarıdan benim gidip, herhangi bir filozoftan sopasını alıp başka bir filozofa vermememle örnekleyebilirim sanırım. Son olarak çembersel bekleme de, bariz bir şekilde masanın etrafında filozofların oluşturduğu çember :)

Kilitlenmeden Kurtulma Yolları

Tabi ki kilitlenmeyi yenmemiz, hatta çözmemiz için bu dört koşulu yenmemiz gerek. Bu koşulları tek tek ortadan kaldırmayı filozoflarımız üstünde göstermek istiyorum.
Karşılıklı dışlamayla ilgili sanırım kimsenin yapabilecek bir şeyi yok :) Nitekim filozof da olsalar fizik kurallarına karşı gelemezler. Sadece sopa sayısını arttırmak, yani kaynağın kullanılabilen örnek sayısını arttırmak bu koşula bir çözüm olarak getirilebilir. O yüzden çoklu bağımsız isteklere geçelim. Bir an düşünün ki bu filozoflar o kadar eşzamanlı ki, aynı anda iki sopayı birden alabiliyor. Yani sopayı eline alma işlemini atomik olarak görürsek, böylece en az bir filozof iki sopasını birden eline alır ve yemeğini bitirdikten sonra sopaları diğerlerine bırakır. Yani kilitlenme çoklu isteklerin atomik olarak gerçekleştirilmesiyle çözülür. Fakat gerçek hayatta düşündüğümüzde, bu bir işlemin kullanacağı tüm kaynakları atomik olarak bir anda alması demektir, ki gereksiz şeylerle birlikte çok büyük yük getirdiğinden bu iyi bir çözüm yolu değildir (Örneğin, kelime işlemci açtığımızda direk yazıcıyı da almış oluyoruz. Ama yazıcı kullanımının, toplam kelime işlemci programının kullanımının sıklığından kat kat az olmasına rağmen, bu kaynağı boşuna elimizde tutmuş oluyoruz). Boşaltılamazlık koşuluna geçersek, masaya bir misafirin geldiğini düşünelim ve filozofların bu haline acıyıp birindeki sopayı alıp bekleyen birine versin. Yine sorun çözülür. Ancak sisteme bir yabancıyı katmadan da bu koşulu yenebiliriz. Akıllı filozoflarımız sağdaki sopayı alsalar, sonra baktılar ki soldakini alamıyorlar, o zaman sağdakini bıraksalar, yine kilitlenmeyi boşaltılamazlık koşulunu kırarak çözmüş oluruz. Çembersel bekleme sorununu çözmek içinse olaya biraz daha işlemsel bakalım. Sopaları numaralayalım ve filozofların bunları önem sırasıyla aldıklarını düşünelim. Yani hepsi ilk olarak solundakini (ya da sağındakini) almak yerine, 0 1 2 3 şeklinde önem sırasına göre artarak sopaları almayı deneyecekler ve bir tanesi solundakini değil de sağındakini almaya çalıştığında sorun çözülmüş olacak. Fakat burada yine ufak iki dezavantajımız var. Birincisi, bu önem sıralamasını tutmamız için ayrıca bir bölümümüz olması gerekiyor. Bu da fazladan hafıza tüketimi demek ve pek tercih ettiğimiz bir durum değil. İkincisi ise, diyelim ki önem sırasında beşinci kaynak birinci kaynağa bağımlı ve o olmadan çalışmıyor; ama önem sıralamasına göre aldığımız için beşinci elimizdeyken birinciyi istememiz yasak. Peki şimdi?! Kilitlenmeye neden olan bu koşulları tek tek ele almak dışında, bir seçeneğimiz daha var; ama pek de insancıl değil :) Bu da kilitlenme olduğunu fark edip, kilitlenmeye sebep olan işlemlerden birini durdurmak. Yani filozoflardan birini öldürmek.

never give up ;)

Yürütme Zamanında Kilitlenmeyi Önleme

Kilitlenmeden kurtulmak yerine, kilitlenmeye karşı önlemler almak daha mantıklı bir çözüm olabiliyor. Mesela, A, B, C ve D işlemlerinin bir K kaynağına ihtiyaçları olduğunu düşünelim. A maksimum 6 birim K ile, B 5, C 4 ve D maksimum 7 birim K ile sonlansın. Elimizde de 10 birim K olsun. İşletim sistemi bu 10 birim K'yı hangi işleme verip hangi işleme vermemesi gerektiğini bilirse, asla kilitlenme durumu oluşmaz. Bu yüzden sürekli elinde yedek K'larla dolaşması gerekir. Yani, mesela A'ya 1, B'ye 1, C'ye 2, D'ye de 4 birim K verdiğinde, elimizde 2 birim K kalır. Bu duruma bakıp, maksimum ihtiyaçlardan elimizde olanları çıkardığımızda kalan ihtiyaçlarla bütün işlemleri bitirebiliyorsa, bu güvenli bir durumdur (safe condition). Elimizde kalan 2 K yı C ye verdiğimizde C biter, 4 K'sını geri verir, o 4'ü B'ye veririz, B bitirip 5 geri verir, 5'i A'ya ve A bitince dönenlerden 3'ünü D'ye verdiğimizde, C->B->A->D sırasıyla işlemlerimiz sonlanır. Bu da ilk baştaki durumumuzun güvenli olduğunu sonucuna varmamızı sağlar. Peki diyelim ilk durumda B'nin 1 değil 2 K'sı vardı. O zaman işlemleri belli ve kesin bir şekilde bitirme olanağımız olmadığından bu durum güvenli olmayan bir durum olurdu (unsafe condition).
Bu algoritma bizi “kilitlenme bölgesi”ne girebileceğimiz “güvenli olmayan bölge”ye bile girmekten korur. Ancak, sadece teoride uygulanabilir bir algoritma olarak kalmakta. Çünkü:

1) İşlem sayımız bu örnekte sabit olmasına rağmen, normalde bilgisayardaki işlemleri ve işlemcikleri düşünürsek bu sayının sabit olmadığını dolayısıyla güvenli ortamların belirlenmesinin mümkün olmadığını görürüz.

2) Örnekte işlemlerin sonlanması için gereken maksimum kaynak sayısını bildiğimizi varsaydık ve dağıtımları ona göre yaptık; ancak bu maksimum ihtiyaçları bilemiyor olabiliriz. O zaman da dağıtımı yapacağımız parametreler ortadan kalkmış olur.

3) Birinci ve ikinciyi bildiğimizi ve sabit olduğunu varsaysak bile, bütün bu bildilerin düzenli ve güvenli bir şekilde hafızada tablolar halinde saklanması gerekir. Ve tabi ki bu pek kolay bir şey değil.

Canlı Kilitlenme

Bu ayki son ilginç başlığım da bu sanırım :) Ölümcül kilitlenme dışında bir de canlı kilitlenme var. Canlı kilitlenme, daha çok veri tabanlarıyla uğraşırken, ölümcül kilitlenme riskini en aza indirmeye çalışırken karşımıza çıkan bir kilitlenme. Veri tabanı kullanırken, demin söz ettiğim algoritmayı kullanmak yerine, geri beslemeleri kullanıyoruz. Yani bir şekilde ölümcül kilitlenmeyi geri alıyoruz da diyebiliriz. Bu gibi durumlarda canlı kilitlenme karşımıza çıktığında, ilk ölümcül kilitlenme resminde tek şeritli yolu tıkayan araçların ikisinin de yolun geniş bölgelerine geçip birbirlerinin geçmesi için beklediğini hayal edebiliriz :)

Bundan sonra bilgisayarımız kilitlendiğinde artık daha şefkatli oluruz sanırım. Tabi umarım bütün bilgisayarlar ne ölümcül ne canlı kilitlenmezler ve filozoflarımız sonsuza kadar mutlu yaşarlar =) Bir ay daha böylece biterken, gelecek sayımızda görüşmek dileğiyle, e-bergisiz kalmayın ;)

Kaynaklar:



İlke Demir
- 2 -