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.

Örnekler

İ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
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.)

Tespit etme

Ç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

Livelock, ilerleyemeyen işlemlerin durumlarının birbirine göre değişmesi dışında deadlock'a benzer bir durumdur. Livelock, kaynak açlığının özel bir durumudur. Genel tanım sadece özel bir işlem ilerleyemediğini belirtir.
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.