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[1]
A işlemi R1 kaynağını, B işlemi de R2 kaynağını tuttuğu halde, A'nın R2'yi, B'nin de R1'i almaya çalışması durumu.

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

Gerekli şartlar

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.

Önlemler

Engellemek

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.

Bekle/Öl Yarala/Bekle
E, Y tarafından tutulan bir kaynağa ihtiyaç duyar E bekler Y ölür
Y, E tarafından tutulan bir kaynağa ihtiyaç duyar Y ölür Y bekler

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.[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]

Ayrıca bakınız

Kaynakça

  1. ↑ A Treasury of Railroad Folklore, B.A. Botkin & A.F. Harlow, p. 381
  2. ↑ Mogul, Jeffrey C.; K. K. Ramakrishnan (1996). "Eliminating receive livelock in an interrupt-driven kernel". 19 Temmuz 2008 tarihinde kaynağından arşivlendi. http://web.archive.org/web/20080719113425/http://citeseer.ist.psu.edu/326777.html.
  3. ↑ Anderson, James H.; Yong-jik Kim (2001). "Shared-memory mutual exclusion: Major research trends since 1986". 30 Nisan 2008 tarihinde kaynağından arşivlendi. http://web.archive.org/web/20080430000030/http://citeseer.ist.psu.edu:80/anderson01sharedmemory.html.
  4. ↑ Zöbel, Dieter (October 1983). "The Deadlock problem: a classifying bibliography". ACM SIGOPS Operating Systems Review 17 (4): 6–15. DOI:10.1145/850752.850753. ISSN 0163-5980.

Daha fazla bilgi için

Dış bağlantılar

This article is issued from Vikipedi - version of the 9/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.