Deadlock

Deadlock ya da kilitlenme, iki ya da daha fazla eylemin devam etmek için birbirlerinin bitmesini beklemesi ve sonuçta ikisinin de devam edememesi durumu. Genellikle "yumurta mı tavuk mu önce gelir?" gibi paradokslarda görülür.

Bilgisayar biliminde, Coffman deadlock iki ya da daha fazla işlemin, diğerinin bir kaynağı bırakmasını beklediği ya da ikiden fazla işlemin döngüsel bir sırada birbirlerinden kaynak beklediği özel durumları belirtmek için kullanılır. Deadlock, birçok işlemin lock (kilit) olarak bilinen özel bir tür kaynağı paylaştığı çoklu işlemede sık karşılaşılan bir sorundur. Zaman-paylaşımı ya da gerçek-zaman pazarında kullanılan bilgisayarlar genellikle belirli bir zaman içinde tek bir işlem erişimini garanti eden donanımsal kilite sahiptir. Yazılım kaynaklı deadlocklardan kurtulmak için genel bir çözüm olmadığı için çoğunlukla her seferinde ayrıca çözülmesi gereken bir sorundur.

Bu durum, sadece bir kalem ve bir cetvelle diyagram çizen iki insana benzetilebilir. Eğer birisi kalemi, diğeri de cetveli alırsa bir deadlock oluşur. Kalemi alan kişi cetvele, cetveli alan da kaleme ihtiyaç duyar.

Deadlock, telekomünikasyon alanındaki tanımı Coffman'dan daha zayıftır, çünkü işlemler kaynaklardan farklı olarak mesajlar için bekleyebilir. Deadlock, uzun süreli bekleme yerine bozuk mesajlar ya da sinyaller sonucunda oluşabilir. Örneğin, yanlış bir bağlantıdan girdi bekleyen bir veri akışı elemanı, bu bağlantı Coffman döngüsünde yer almamasına rağmen, hiçbir zaman işlem yapamayacaktır.

İki tren bir makasta karşı karşıya geldiğinde ikisi de tamamen durmalı ve diğeri gitmeden hareket etmemelidir.

—Kansas Meclisi'nden geçen mantıksız bir kararname^[1]

Veritabanında oluşabilecek bir deadlock şöyle oluşabilir: veritabanı kullanan istemci uygulamaları tablolara özel erişim yetkisi alması gerektiğinde bir kilit için istekte bulunur. Eğer bir tablo için kilidi elinde tutan uygulama ikinci bir tablodaki kilidi almaya çalışır ve bu ikinci tablodaki kilit de ikinci bir uygulama tarafından tutuluyorsa, ikinci uygulama birinci tabloya erişmeye çalıştığında bir deadlock oluşacaktır. (Bu tip bir kilitlenme ya hep ya hiç tarzı bir kaynak sağlama algoritması ile önlenebilir.)

Bir Coffman deadlock'un oluşması için Coffman şartları olarak bilinen dört adet gerekli şart vardır:

1. Karşılıklı dışlama: Aynı zamanda birden fazla işlem tarafından kullanılamayan bir kaynak
2. Tut ve Bekle: Kaynakları elinde tutan işlemlerin yeni kaynaklar talep edebilmesi
3. İşlem üstünlüğü yok: Hiçbir kaynak onu tutan işlemden zorla alınamaz, kaynaklar sadece işlemlerin kendileri tarafından bırakılabilir.
4. Dairesel bekleme: İki ya da daha fazla işlem, her işlemin bir sonraki işlemin elindeki kaynakları bırakmasını beklediği döngüsel bir zincir oluşturur.

Bu şartlar herhangi birinin gerçekleşmemesi Coffman deadlock'u engellemek için yeterlidir. Fakat, bu şartların görülmesi de illâ ki bir deadlock anlamına gelmeyebilir.

• Karşılıklı dışlama şartını kaldırmak, hiçbir işlemin bir kaynağa tek başına erişemeyeceği anlamına gelir. Bu bekletilemeyen kaynaklar için mümkün değildir, kaynak bekletilebilir olsa dahi deadlock olmayacağı anlamına da gelmez.
• "Tut ve bekle" şartı, işlemlerin başlamadan önce ihtiyacı olan kaynakların hepsini birden talep etmesiyle önlenebilir. Ancak, bu durumda kaynaklar verimsiz bir şekilde kullanılmış olacaktır. Bir başka yöntem işlemlerin ihtiyacı olanlar almadan önce elindeki tüm kaynakları bırakması olabilir. Fakat bu yöntem de çoğunlukla kullanışsızdır.
• İşlem üstünlüğünün olmadığı durumun önlenmesi de, işlemin belirli bir zaman dilimi için kaynağı elinde tutma zorunluluğu ya da işlem sonucunun tutarsız oluşu gibi sebeplerden zordur.
• Dairesel bekleme durumunu engelleyen algoritmalar, "kritik bölümlerde kesici sinyalleri devre dışı bırakma" ve "kaynakların kısmî sıralamasına karar vermek için bir hiyerarşi uygulama" yöntemlerini içerir.

Kaynak paylaştırma işlemi öncesinde işlemler hakkında bazı bilgilere sahip olunduğunda deadlock'u engellemek mümkündür. Her bir kaynak talebi için, sistem önce bu talebin kendini deadlockla sonuçlanabilecek güvensiz bir duruma sokup sokmayacağını kontrol eder. Daha sonra sistem, sadece güvenli durumlarla sonuçlanacak talepleri karşılar. Sistemin bir sonraki durumunun güvenli mi güvensiz mi olacağını anlaması için, önceden boşta ve talep edilen tüm kaynakların sayısını ve türünü bilmesi gerekir. Deadlock engellemek için kullanılan algoritmalardan bilenen birisi de, önceden kaynak kullanım limitinin bilinmesini gerektiren Banker algoritmasıdır. Fakat, çoğu sistem için her işlemin kaynak taleplerini önceden kestirmek mümkün değildir.

Diğer iki algoritma; Bekle/Öl ve Yarala/Bekle'dir. İki algoritmada da bir adet eski işlem (E) ve bir adet yeni işlem (Y) bulunur. İşlemlerin yaşı, yaratılma anında oluşturulan zaman damgası sayesinde anlaşılır.

Çoğunlukla, deadlock'u önlemek ya da engellemek mümkün değildir. Bunun yerine, deadlock tespiti ve işlemlerin yeniden başlatılması uygulanır. Bunun için, kaynak dağıtımını ve işlem durumlarını takip eden ve deadlock'u kaldırmak için işlemleri geri alan ya da yeniden başlatan algoritmalar kullanılır. Gerçekleşen bir deadlock'un tespiti, işlemler tarafından kilitlenmiş ya da talep edilen kaynaklar işletim sistemi tarafından bilindiği için nispeten kolaydır.

Bir deadlock'un önceden bilinmesi ise çok daha zordur. Aslında bu durum çoğunlukla karar verilmez bir haldedir, çünkü sonlandırma sorunu da bir deadlock senaryosu olarak görülebilir. Bununla birlikte özellemiş çevrelerde, özelleşmiş kaynak kilitleri kullanarak, deadlock tespiti karar verilebilir hale getirilebilir.

Deadlock tespit yöntemleri, model karşılaştırmayı içerir. Bu yaklaşım, bir sonlu durum makinası oluşturarak, tüm muhtemel son durumları ortaya çıkaran bir işlem analizi gerçekleştirir.

Livelock, ilerleyemeyen işlemlerin durumlarının birbirine göre değişmesi dışında deadlock'a benzer bir durumdur.^[2] Livelock, kaynak açlığının özel bir durumudur. Genel tanım sadece özel bir işlem ilerleyemediğini belirtir.^[3]

Gerçek dünyada bir livelock örneği, bir insan dar bir koridorda karşılaştığında ve ikisi de kenara çekilerek birbirine yol verdiği durum olarak gösterilebilir. Daha sonra iki kişi de aynı anda ilerlemeye çalıştığında yine başlangıç durumu ortaya çıkacak ve tekrar birbirlerine yol vereceklerdir. Böylelikle ikisinin de ilerlemesi mümkün değildir.

Livelock, deadlockları tespit eden ve geri döndüren algoritmalar için bir risktir. Eğer birden fazla işlem eyleme geçerse, deadlock tespit algoritması tekrar tekrar başlatılacaktır. Bu durum, aynı zamanda tek bir işlemin eylemde olması sağlanarak engellenebilir.^[4]

• Banker algoritması
• Makarna yiyen düşünürler sorunu
• Donma
• Sonsuz döngü
• Deve kuşu algoritması
• Öncelik çevrimi
• Uyuyan berber sorunu
• Pat
• Senkronizasyon

• Kaveh, Nima; Emmerich, Wolfgang. "Deadlock Detection in Distributed Object Systems" (PDF). Londra: University College London. 3 Mart 2012 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 26 Aralık 2011. 
• Bensalem, Saddek; Fernandez, Jean-Claude; Havelund, Klaus; Mounier, Laurent (2006). "Confirmation of deadlock potentials detected by runtime analysis". Proceedings of the 2006 workshop on Parallel and distributed systems: Testing and debugging. ACM. ss. 41-50. doi:10.1145/1147403.1147412. 
• Coffman, Edward G., Jr.; Elphick, Michael J.; Shoshani, Arie (1971). "System Deadlocks" (PDF). ACM Computing Surveys. 3 (2). ss. 67-78. doi:10.1145/356586.356588. 27 Ocak 2012 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 26 Aralık 2011. 
• Mogul, Jeffrey C.; Ramakrishnan, K. K. (1997). "Eliminating receive livelock in an interrupt-driven kernel". ACM Transactions on Computer Systems. 15 (3). ss. 217-252. doi:10.1145/263326.263335. ISSN 0734-2071. 
• Havender, James W. (1968). "Avoiding deadlock in multitasking systems". IBM Systems Journal. 7 (2). s. 74. 24 Şubat 2012 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Aralık 2011. 
• Holliday, JoAnne L.; El Abbadi, Amr. "Distributed Deadlock Detection". Encyclopedia of Distributed Computing. Kluwer Academic Publishers. 2 Kasım 2015 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Aralık 2011. 
• Knapp, Edgar (1987). "Deadlock detection in distributed databases". ACM Computing Surveys. 19 (4). ss. 303-328. doi:10.1145/45075.46163. ISSN 0360-0300. 
• Ling, Yibei; Chen, Shigang; Chiang, Jason (2006). "On Optimal Deadlock Detection Scheduling". IEEE Transactions on Computers. 55 (9). ss. 1178-1187. 

• Advanced Synchronization in Java Threads11 Mart 2012 tarihinde Wayback Machine sitesinde arşivlendi., Scott Oaks ve Henry Wong
• Deadlock Tespit Ajanları
• ARCS - Deadlock sorununa web service yaklaşımı
• Non-Hard Locking Read-Write Locker18 Aralık 2011 tarihinde Wayback Machine sitesinde arşivlendi.