İçeriğe atla

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

  • 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 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/ÖlYarala/Bekle
E, Y tarafından tutulan bir kaynağa ihtiyaç duyarE beklerY ölür
Y, E tarafından tutulan bir kaynağa ihtiyaç duyarY ölürY 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. (1996). "Eliminating receive livelock in an interrupt-driven kernel". 19 Temmuz 2008 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Aralık 2011. 
  3. ^ Anderson, James H. (2001). "Shared-memory mutual exclusion: Major research trends since 1986". 30 Nisan 2008 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Aralık 2011. 
  4. ^ 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

Dış bağlantılar

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Turing Ödülü</span> bilgisayar bilimi ödülü

ACM A.M. Turing Ödülü, modern bilgisayar biliminin kurucularından sayılan Alan Turing anısına, 1966'dan beri her yıl Association for Computing Machinery (ACM) tarafından bilişim dünyasına katkıda bulunanlara verilen bir ödüldür. Ödüle değer görülen katkılarda "kalıcı olma ve bilgisayar bilimi dünyasına önemli bir etki yapma" koşulu aranmaktadır. Bilişim konulu en önemli ödül olduğu düşünülen Turing Ödülü bilgisayar dünyasının Nobel Ödülü olarak da anılmaktadır.

<span class="mw-page-title-main">AES</span> Şifreleme standartı

AES, elektronik verinin şifrelenmesi için sunulan bir standarttır. Amerikan hükûmeti tarafından kabul edilen AES, uluslararası alanda da defacto şifreleme (kripto) standardı olarak kullanılmaktadır. DES'in yerini almıştır. AES ile tanımlanan şifreleme algoritması, hem şifreleme hem de şifreli metni çözmede kullanılan anahtarların birbiriyle ilişkili olduğu, simetrik-anahtarlı bir algoritmadır. AES için şifreleme ve şifre çözme anahtarları aynıdır.

<span class="mw-page-title-main">Sıralama algoritması</span>

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar.

<span class="mw-page-title-main">CSMA\CD</span>

CSMA\CD, bilgisayar ağında bir ağ protokolüdür.

Dizi eşleme algoritmaları olarak da adlandırılan dizi arama algoritmaları, bir ya da birkaç dizinin (örüntü) daha büyük bir dizi ya da metin içindeki yerinin bulunmasını konu edinen önemli bir dizi algoritması sınıfıdır.

Distance-vector Routing Protocol paket-anahtarlamalı ağlarla ilgili bilgisayar Iletişim(computer communication) kuramında yer alan iki ana sınıftan biridir. Diğeriyse bağlantı-durum (link-state) protokolüdür. Distance-vector yönlendirme protokolü yolların hesaplanmasında Bellman-Ford algoritmasını kullanır.

Ağ katmanının ana görevi, kaynak makineden hedef makineye paketleri göndermektir. Gönderilen bu paketler, hedef makineye ulaşana kadar, değişik algoritmalar yardımıyla birçok düğümden geçerler. Verinin iletim ortamından hedefe ulaşmasını sağlayan bu yönlendirme algoritmalarından hangisinin kullanılacağına ağ katmanı karar verir. Bir yönlendirme protokolü, yönlendirme tablosunu yol bilgisi ile doldurur. Yönlendirme tablolarında, ağ katmanında tanımlanan yönlendirilmiş protokol IP, IPX gibi paketlerin bilgileri saklanır. Seçilen yönlendirme protokolü bu yönlendirme tablolarını kullanarak paketleri hedefine ulaştırır. Bir yönlendirme protokolü aşağıdakileri sağlamalıdır:

<span class="mw-page-title-main">Hesaplamalı fizik</span>

Hesaplamalı fizik, fizik sorunlarını çözebilmek için sayısal algoritmaların üretilmesi ve gerçeklenmesini içerir. Genelde kuramsal fizikin bir alt dalı olarak değerlendirilir ancak bazen de kuramsal ve deneysel fizik arasında orta bir dal olarak da düşünülür.

Bilgisayar mimarisinde, buyruk ön yüklemesi bekleme durumlarını azaltarak bir programın mikroişlemcide ki yürütmesinin hızlanmasını sağlayan bir tekniktir.

<span class="mw-page-title-main">Saldırı tespit sistemleri</span>

Saldırı Tespit Sistemleri (STS) (İngilizce: Intrusion Detection Systems (IDS)), ağlara veya sistemlere karşı yapılan kötü niyetli aktiviteleri ya da politika ihlallerini izlemeye yarayan cihaz ya da yazılımlardır. Tespit edilen herhangi bir aktivite veya ihlal, ya bir yöneticiye bildirilir ya da bir güvenlik bilgi ve olay yönetimi (SIEM) sistemi kullanılarak merkezi olarak toplanır. SIEM sistemi, çeşitli kaynaklardan gelen çıktıları birleştirir ve kötü niyetli alarmı yanlış alarmlardan ayırmak için alarm filtreleme teknikleri kullanır.

Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, loga(b) ifadesi, ax = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, gx = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

Öneri sistemi ya da tavsiye sistemi bir kullanıcının bir öğeye vereceği 'değerlendirme' ya da 'tercih' miktarının öngörülmesini hedefleyen bir bilgi filtreleme sistemidir.

Kriptografide, scrypt, Colin Percival tarafından Tarsnap çevrimiçi yedekleme hizmeti için oluşturulan bir parola tabanlı anahtar türetme fonksiyonudur. Bu algoritma, büyük miktarda bellek gerektirerek büyük ölçekli özel donanım saldırılarını gerçekleştirmeyi pahalı hale getirmek için özel olarak tasarlanmıştır. 2016 yılında, scrypt algoritması IETF tarafından RFC 7914 olarak yayınlandı. Scrypt algoritmasının, ArtForz kullanıcı adına sahip ve gerçek adı bilinmeyen bir programcı tarafından implemente edilmiş, basitleştirilmiş bir sürümü, önce Tenebrix'te ve ardından Fairbrix ve Litecoin olmak üzere bir dizi kripto para birimi tarafından iş kanıtı şeması olarak kullanıldı.

Boyce – Codd normal formu, veritabanı normalleştirmesinde kullanılan normal bir formdur. Üçüncü normal formun (3NF) biraz daha güçlü bir versiyonudur. BCNF, 1974 yılında Raymond F. Boyce ve Edgar F. Codd tarafından, başlangıçta tanımlandığı şekliyle 3NF tarafından ele alınmayan belirli anormallik türlerini ele almak için geliştirilmiştir.

Nesne tespiti bilgisayarla görü ve görüntü işleme ile ilgili bilgisayar teknolojisi

Nesne tespiti, dijital görüntülerde ve videolarda belirli bir sınıftaki anlamsal nesnelerin örneklerini algılamakla ilgilenen, bilgisayarla görme ve görüntü işleme ile ilgili bir bilgisayar teknolojisidir. Nesne tespiti, bilgisayarla görme ve görüntü işlemeden farklı olarak algılanan nesnenin görüntü üzerinde koordinatlarının bulunmasını içerir. Bulunan koordinatlar ile nesnenin bir çerçeve ile içine alınacağı alan da tespit edilmiş olur. Nesne tespiti, gerçek zamanlı (anlık) ve gerçek zamanlı olmayan olarak ikiye ayrılır. Üzerinde iyi araştırma yapılmış alanlar yüz tespiti, yaya tespiti ve araç tespitidir. Nesne tespiti, görüntü alma ve video gözetimi dahil olmak üzere bilgisayarla görmenin birçok alanında uygulamaya sahiptir.

Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır. Çok sayıda verinin girilmesi ve iyi bir sezgisel fonksiyon verildiğinde, probleme yeterince iyi bir çözüm bulmaya çalışmaktadır. Bilgisayar bilimlerinde aktif olarak kullanılmakta olan arama algoritmalarından birisidir. İki boyutlu bir grafikte en düşük noktaları arama esnasında yapmış olduğu hareket tepe tırmanmaya benzemesinden dolayı bu isimi almıştır.

Veri analizinde, anomali tespiti, verilerin çoğunluğundan önemli ölçüde farklılaşarak şüphe uyandıran nadir öğelerin, olayların veya gözlemlerin tanımlanmasıdır. Tipik olarak anormal öğeler, banka dolandırıcılığı, yapısal bir kusur, tıbbi sorunlar veya bir metindeki hatalar gibi bir tür soruna dönüşecektir. Anormallikler ayrıca aykırı değerler, yenilikler, gürültü, sapmalar ve istisnalar olarak da adlandırılmaktadır.

Deve kuşu algoritması, bilgisayar bilimlerinde ortaya çıkması muhtemel problemlerin, nadiren gerçekleştikleri takdirde görmezden gelinmesi stratejisidir. Adını deve kuşlarının kafalarını toprağa gömüp hiçbir sorun yokmuş gibi davranmasından almıştır. Sorunun ortaya çıkmasına izin vermenin, önlemeye çalışmaktan daha düşük maliyetli olduğu durumlarda kullanılır.

<span class="mw-page-title-main">Anna Karlin</span> Amerikalı bilgisayar bilimcisi

Anna R. Karlin, Washington Üniversitesi'nde Microsoft Bilgisayar Bilimi ve Mühendisliği Profesörü olan Amerikalı bir bilgisayar bilimcidir.

<span class="mw-page-title-main">Otomatik makine öğrenimi</span>

Otomatik makine öğrenimi (AutoML), makine öğrenimini gerçek dünya sorunlarına uygulanmasını otomatikleştirme sürecidir.