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, 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 (kilit) olarak bilinen özel bir tür kaynağı paylaştığı çoklu işlemede sık karşılaşılan bir sorundur. ya da 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.)
Gerekli şartlar
Bir Coffman deadlock'un oluşması için Coffman şartları olarak bilinen dört adet gerekli şart vardır:
- Karşılıklı dışlama: Aynı zamanda birden fazla işlem tarafından kullanılamayan bir kaynak
- Tut ve Bekle: Kaynakları elinde tutan işlemlerin yeni kaynaklar talep edebilmesi
- İşlem üstünlüğü yok: Hiçbir kaynak onu tutan işlemden zorla alınamaz, kaynaklar sadece işlemlerin kendileri tarafından bırakılabilir.
- 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
- 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.
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 . 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ü 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, ö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.
Ayrıca bakınız
Kaynakça
- ^ A Treasury of Railroad Folklore, B.A. Botkin & A.F. Harlow, p. 381
- ^ Mogul, Jeffrey C. (1996). . 19 Temmuz 2008 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Aralık 2011.
- ^ Anderson, James H. (2001). "Shared-memory mutual exclusion: Major research trends since 1986". 30 Nisan 2008 tarihinde kaynağından . Erişim tarihi: 26 Aralık 2011.
- ^ Zöbel, Dieter (Ekim 1983). "The Deadlock problem: a classifying bibliography". ACM SIGOPS Operating Systems Review. 17 (4). ss. 6-15. doi:10.1145/850752.850753. ISSN 0163-5980.
Konuyla ilgili yayınlar
- Kaveh, Nima; Emmerich, Wolfgang. "Deadlock Detection in Distributed Object Systems" (PDF). Londra: University College London. 3 Mart 2012 tarihinde kaynağından (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 (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). . 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. . 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.
Dış bağlantılar
- Advanced Synchronization in Java Threads11 Mart 2012 tarihinde Wayback Machine sitesinde ., Scott Oaks ve Henry Wong
- Non-Hard Locking Read-Write Locker18 Aralık 2011 tarihinde Wayback Machine sitesinde .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Deadlock ya da kilitlenme iki ya da daha fazla eylemin devam etmek icin birbirlerinin bitmesini beklemesi ve sonucta ikisinin de devam edememesi durumu Genellikle yumurta mi tavuk mu once gelir gibi paradokslarda gorulur Bilgisayar biliminde deadlock iki ya da daha fazla islemin digerinin bir kaynagi birakmasini bekledigi ya da ikiden fazla islemin dongusel bir sirada birbirlerinden kaynak bekledigi ozel durumlari belirtmek icin kullanilir Deadlock bircok islemin kilit olarak bilinen ozel bir tur kaynagi paylastigi coklu islemede sik karsilasilan bir sorundur ya da pazarinda kullanilan bilgisayarlar genellikle belirli bir zaman icinde tek bir islem erisimini garanti eden donanimsal kilite sahiptir Yazilim kaynakli deadlocklardan kurtulmak icin genel bir cozum olmadigi icin cogunlukla her seferinde ayrica cozulmesi gereken bir sorundur Bu durum sadece bir kalem ve bir cetvelle diyagram cizen iki insana benzetilebilir Eger birisi kalemi digeri de cetveli alirsa bir deadlock olusur Kalemi alan kisi cetvele cetveli alan da kaleme ihtiyac duyar Deadlock telekomunikasyon alanindaki tanimi Coffman dan daha zayiftir cunku islemler kaynaklardan farkli olarak mesajlar icin bekleyebilir Deadlock uzun sureli bekleme yerine bozuk mesajlar ya da sinyaller sonucunda olusabilir Ornegin yanlis bir baglantidan girdi bekleyen bir veri akisi elemani bu baglanti Coffman dongusunde yer almamasina ragmen hicbir zaman islem yapamayacaktir OrneklerIki tren bir makasta karsi karsiya geldiginde ikisi de tamamen durmali ve digeri gitmeden hareket etmemelidir Kansas Meclisi nden gecen mantiksiz bir kararname A islemi R1 kaynagini B islemi de R2 kaynagini tuttugu halde A nin R2 yi B nin de R1 i almaya calismasi durumu Veritabaninda olusabilecek bir deadlock soyle olusabilir veritabani kullanan istemci uygulamalari tablolara ozel erisim yetkisi almasi gerektiginde bir kilit icin istekte bulunur Eger bir tablo icin kilidi elinde tutan uygulama ikinci bir tablodaki kilidi almaya calisir ve bu ikinci tablodaki kilit de ikinci bir uygulama tarafindan tutuluyorsa ikinci uygulama birinci tabloya erismeye calistiginda bir deadlock olusacaktir Bu tip bir kilitlenme ya hep ya hic tarzi bir kaynak saglama algoritmasi ile onlenebilir Gerekli sartlar Bir Coffman deadlock un olusmasi icin Coffman sartlari olarak bilinen dort adet gerekli sart vardir Karsilikli dislama Ayni zamanda birden fazla islem tarafindan kullanilamayan bir kaynak Tut ve Bekle Kaynaklari elinde tutan islemlerin yeni kaynaklar talep edebilmesi Islem ustunlugu yok Hicbir kaynak onu tutan islemden zorla alinamaz kaynaklar sadece islemlerin kendileri tarafindan birakilabilir Dairesel bekleme Iki ya da daha fazla islem her islemin bir sonraki islemin elindeki kaynaklari birakmasini bekledigi dongusel bir zincir olusturur Bu sartlar herhangi birinin gerceklesmemesi Coffman deadlock u engellemek icin yeterlidir Fakat bu sartlarin gorulmesi de illa ki bir deadlock anlamina gelmeyebilir Onlemler Karsilikli dislama sartini kaldirmak hicbir islemin bir kaynaga tek basina erisemeyecegi anlamina gelir Bu bekletilemeyen kaynaklar icin mumkun degildir kaynak bekletilebilir olsa dahi deadlock olmayacagi anlamina da gelmez Tut ve bekle sarti islemlerin baslamadan once ihtiyaci olan kaynaklarin hepsini birden talep etmesiyle onlenebilir Ancak bu durumda kaynaklar verimsiz bir sekilde kullanilmis olacaktir Bir baska yontem islemlerin ihtiyaci olanlar almadan once elindeki tum kaynaklari birakmasi olabilir Fakat bu yontem de cogunlukla kullanissizdir Islem ustunlugunun olmadigi durumun onlenmesi de islemin belirli bir zaman dilimi icin kaynagi elinde tutma zorunlulugu ya da islem sonucunun tutarsiz olusu gibi sebeplerden zordur Dairesel bekleme durumunu engelleyen algoritmalar kritik bolumlerde kesici sinyalleri devre disi birakma ve kaynaklarin kismi siralamasina karar vermek icin bir hiyerarsi uygulama yontemlerini icerir Engellemek Kaynak paylastirma islemi oncesinde islemler hakkinda bazi bilgilere sahip olundugunda deadlock u engellemek mumkundur Her bir kaynak talebi icin sistem once bu talebin kendini deadlockla sonuclanabilecek guvensiz bir duruma sokup sokmayacagini kontrol eder Daha sonra sistem sadece guvenli durumlarla sonuclanacak talepleri karsilar Sistemin bir sonraki durumunun guvenli mi guvensiz mi olacagini anlamasi icin onceden bosta ve talep edilen tum kaynaklarin sayisini ve turunu bilmesi gerekir Deadlock engellemek icin kullanilan algoritmalardan bilenen birisi de onceden kaynak kullanim limitinin bilinmesini gerektiren Fakat cogu sistem icin her islemin kaynak taleplerini onceden kestirmek mumkun degildir Diger iki algoritma Bekle Ol ve Yarala Bekle dir Iki algoritmada da bir adet eski islem E ve bir adet yeni islem Y bulunur Islemlerin yasi yaratilma aninda olusturulan zaman damgasi sayesinde anlasilir Bekle Ol Yarala BekleE Y tarafindan tutulan bir kaynaga ihtiyac duyar E bekler Y olurY E tarafindan tutulan bir kaynaga ihtiyac duyar Y olur Y beklerTespit etme Cogunlukla deadlock u onlemek ya da engellemek mumkun degildir Bunun yerine deadlock tespiti ve islemlerin yeniden baslatilmasi uygulanir Bunun icin kaynak dagitimini ve islem durumlarini takip eden ve deadlock u kaldirmak icin islemleri geri alan ya da yeniden baslatan algoritmalar kullanilir Gerceklesen bir deadlock un tespiti islemler tarafindan kilitlenmis ya da talep edilen kaynaklar isletim sistemi tarafindan bilindigi icin nispeten kolaydir Bir deadlock un onceden bilinmesi ise cok daha zordur Aslinda bu durum cogunlukla karar verilmez bir haldedir cunku da bir deadlock senaryosu olarak gorulebilir Bununla birlikte ozellemis cevrelerde ozellesmis kaynak kilitleri kullanarak deadlock tespiti karar verilebilir hale getirilebilir Deadlock tespit yontemleri model karsilastirmayi icerir Bu yaklasim bir sonlu durum makinasi olusturarak tum muhtemel son durumlari ortaya cikaran bir islem analizi gerceklestirir LivelockLivelock ilerleyemeyen islemlerin durumlarinin birbirine gore degismesi disinda deadlock a benzer bir durumdur Livelock ozel bir durumudur Genel tanim sadece ozel bir islem ilerleyemedigini belirtir Gercek dunyada bir livelock ornegi bir insan dar bir koridorda karsilastiginda ve ikisi de kenara cekilerek birbirine yol verdigi durum olarak gosterilebilir Daha sonra iki kisi de ayni anda ilerlemeye calistiginda yine baslangic durumu ortaya cikacak ve tekrar birbirlerine yol vereceklerdir Boylelikle ikisinin de ilerlemesi mumkun degildir Livelock deadlocklari tespit eden ve geri donduren algoritmalar icin bir risktir Eger birden fazla islem eyleme gecerse deadlock tespit algoritmasi tekrar tekrar baslatilacaktir Bu durum ayni zamanda tek bir islemin eylemde olmasi saglanarak engellenebilir Ayrica bakinizMakarna yiyen dusunurler sorunu Sonsuz dongu Deve kusu algoritmasi Uyuyan berber sorunu PatKaynakca A Treasury of Railroad Folklore B A Botkin amp A F Harlow p 381 Mogul Jeffrey C 1996 19 Temmuz 2008 tarihinde kaynagindan arsivlendi Erisim tarihi 26 Aralik 2011 Anderson James H 2001 Shared memory mutual exclusion Major research trends since 1986 30 Nisan 2008 tarihinde kaynagindan Erisim tarihi 26 Aralik 2011 Zobel Dieter Ekim 1983 The Deadlock problem a classifying bibliography ACM SIGOPS Operating Systems Review 17 4 ss 6 15 doi 10 1145 850752 850753 ISSN 0163 5980 Konuyla ilgili yayinlarKaveh Nima Emmerich Wolfgang Deadlock Detection in Distributed Object Systems PDF Londra University College London 3 Mart 2012 tarihinde kaynagindan PDF Erisim tarihi 26 Aralik 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 kaynagindan PDF Erisim tarihi 26 Aralik 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 IBM Systems Journal 7 2 s 74 24 Subat 2012 tarihinde kaynagindan arsivlendi Erisim tarihi 26 Aralik 2011 Holliday JoAnne L El Abbadi Amr Encyclopedia of Distributed Computing Kluwer Academic Publishers 2 Kasim 2015 tarihinde kaynagindan arsivlendi Erisim tarihi 26 Aralik 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 Dis baglantilarAdvanced Synchronization in Java Threads11 Mart 2012 tarihinde Wayback Machine sitesinde Scott Oaks ve Henry Wong Non Hard Locking Read Write Locker18 Aralik 2011 tarihinde Wayback Machine sitesinde