Engellemeyen algoritma - Non-blocking algorithm

Engellemeyen G/Ç ile karıştırılmamalıdır .

Gelen bilgisayar bilimleri , bir algoritma denir engellenmeyen eğer başarısızlık veya süspansiyon herhangi parçacığı olamaz başarısızlık veya başka bir iş parçacığı askıya nedeni; bazı işlemler için bu algoritmalar, geleneksel engelleme uygulamalarına yararlı bir alternatif sağlar . Engellemeyen bir algoritma, sistem genelinde garantili ilerleme varsa kilitsizdir ve iş parçacığı başına garantili ilerleme varsa beklemesizdir . "Engellemesiz", 2003 yılında engelleme serbestliğinin tanıtılmasına kadar literatürde "kilitsiz" ile eşanlamlı olarak kullanılmıştır.

Kelime "engellenmeyen" geleneksel tanımlamak için kullanılmıştır telekomünikasyon ağları röleleri bir dizi üzerinden yol bir bağlantı "mevcut çağrıları gerek kalmadan-re düzenlemek" olabilir (bkz Clos ağı ). Ayrıca, telefon santrali "arızalı değilse, bağlantıyı her zaman yapabilir" (bkz. blokajsız minimum yayılma anahtarı ).

Motivasyon

Ana madde: Kilitlerin dezavantajları

Çok iş parçacıklı programlamaya geleneksel yaklaşım , paylaşılan kaynaklara erişimi senkronize etmek için kilitleri kullanmaktır . Muteksler , semaforlar ve kritik bölümler gibi senkronizasyon temel öğelerinin tümü, bir programcının, paylaşılan bellek yapılarını bozacaksa, belirli kod bölümlerinin aynı anda yürütülmemesini sağlayabileceği mekanizmalardır. Bir iş parçacığı, başka bir iş parçacığı tarafından tutulan bir kilidi almaya çalışırsa, iş parçacığı, kilit serbest kalana kadar engellenir.

Bir iş parçacığının engellenmesi birçok nedenden dolayı istenmeyebilir. Bunun bariz bir nedeni, iş parçacığı engellenirken hiçbir şey başaramamasıdır: engellenen iş parçacığı yüksek öncelikli veya gerçek zamanlı bir görev gerçekleştirmiş olsaydı, ilerlemesini durdurmak son derece istenmeyen olurdu.

Diğer sorunlar daha az belirgindir. Örneğin, kilitler arasındaki belirli etkileşimler, kilitlenme , canlı kilit ve öncelikli ters çevirme gibi hata koşullarına yol açabilir . Kilitleri kullanmak, paralellik fırsatlarını önemli ölçüde azaltabilen kaba taneli kilitleme ile daha dikkatli tasarım gerektiren, kilitleme yükünü artıran ve hatalara daha yatkın olan ince taneli kilitleme arasında bir dengeyi de içerir .

Engelleme algoritmalarından farklı olarak, engellenmeyen algoritmalar bu dezavantajlardan etkilenmez ve ayrıca kesme işleyicilerinde kullanım için güvenlidir : önceden alınan iş parçacığı devam ettirilemese bile , onsuz ilerleme hala mümkündür. Buna karşılık, karşılıklı dışlama ile korunan global veri yapılarına, bir kesme işleyicisinde güvenli bir şekilde erişilemez, çünkü önceden alınan iş parçacığı kilidi tutan iş parçacığı olabilir - ancak bu, kritik bölüm sırasında kesme isteğini maskeleyerek kolayca düzeltilebilir.

Performansı artırmak için kilitsiz bir veri yapısı kullanılabilir. Kilitsiz bir veri yapısı, seri yürütme yerine paralel yürütmede harcanan süreyi artırarak çok çekirdekli bir işlemcide performansı artırır , çünkü tutarlı kalmak için paylaşılan veri yapısına erişimin serileştirilmesine gerek yoktur.

uygulama

Birkaç istisna dışında, engelleme yapmayan algoritmalar , donanımın sağlaması gereken atomik okuma-değiştirme-yazma temel öğelerini kullanır; bunların en dikkate değer olanı, karşılaştırma ve takas (CAS) . Kritik bölümler neredeyse her zaman bu temel öğeler üzerinde standart arabirimler kullanılarak uygulanır (genel durumda, bu temel öğelerle uygulandığında bile kritik bölümler engellenir). 1990'larda, kabul edilebilir bir performans elde etmek için tüm engellemesiz algoritmaların temeldeki ilkellerle "doğal olarak" yazılması gerekiyordu. Bununla birlikte, yazılım işlemsel belleğinin gelişmekte olan alanı, verimli, engellemeyen kod yazmak için standart soyutlamalar vaat ediyor.

Yığınlar , kuyruklar , kümeler ve karma tablolar gibi temel veri yapılarının sağlanması konusunda da pek çok araştırma yapılmıştır . Bunlar, programların iş parçacıkları arasında eşzamansız olarak kolayca veri alışverişi yapmasına izin verir.

Ek olarak, bazı bloke olmayan veri yapıları, özel atomik temeller olmadan uygulanabilecek kadar zayıftır. Bu istisnalar şunları içerir:

  • mevcut işaretsiz tamsayı türlerinden birinin taşmasını eşit olarak bölen bir boyuta sahip tek okuyuculu tek yazarlı halka arabelleği FIFO , yalnızca bir bellek bariyeri kullanılarak koşulsuz olarak güvenli bir şekilde uygulanabilir
  • Tek bir yazar ve herhangi bir sayıda okuyucu ile okuma-kopyalama-güncelleme . (Okuyucular beklemez; yazar genellikle hafızasını geri kazanması gerekene kadar kilitlenmez).
  • Birden çok yazar ve herhangi bir sayıda okuyucu ile okuma-kopyalama-güncelleme. (Okuyucular beklemez; birden çok yazar genellikle bir kilitle seri hale getirir ve engelsiz değildir).

Birkaç kitaplık dahili olarak kilitsiz teknikler kullanır, ancak doğru olan kilitsiz kod yazmak zordur.

bekleme özgürlüğü

Bekleme özgürlüğü, sistem genelinde garanti edilen verimi açlık özgürlüğü ile birleştiren en güçlü, engellenmeyen ilerleme garantisidir . Her işlemin, işlem tamamlanmadan önce algoritmanın atacağı adım sayısıyla ilgili bir sınırı varsa, bir algoritma beklemesizdir. Bu özellik, gerçek zamanlı sistemler için kritik öneme sahiptir ve performans maliyeti çok yüksek olmadığı sürece her zaman güzeldir.

1980'lerde tüm algoritmaların beklemesiz olarak uygulanabileceği gösterildi ve evrensel yapılar olarak adlandırılan seri koddan birçok dönüşüm gösterildi. Bununla birlikte, ortaya çıkan performans, genel olarak saf bloklama tasarımlarıyla bile eşleşmez. O zamandan beri birçok makale evrensel yapıların performansını iyileştirdi, ancak yine de performansları engelleyici tasarımların çok altında.

Birkaç makale, beklemesiz algoritmalar oluşturmanın zorluğunu araştırdı. Örneğin, yaygın olarak bulunan atomik koşullu ilkellerin, CAS ve LL/SC'nin , iş parçacığı sayısında doğrusal olarak artan bellek maliyetleri olmadan, birçok yaygın veri yapısının açlıktan kurtulmuş uygulamalarını sağlayamayacağı gösterilmiştir.

Ancak uygulamada bu alt sınırlar, paylaşılan bellekte iş parçacığı başına bir önbellek satırı veya özel rezervasyon granülü (ARM'de 2 KB'ye kadar) harcamak pratik sistemler için çok maliyetli olmadığı için gerçek bir engel oluşturmaz (tipik olarak mantıksal olarak gerekli depolama bir kelimedir, ancak aynı önbellek satırındaki fiziksel CAS işlemleri çarpışır ve aynı özel rezervasyon granülündeki LL/SC işlemleri çarpışır, bu nedenle fiziksel olarak gereken mağaza miktarı daha fazladır).

Beklemesiz algoritmalar 2011 yılına kadar hem araştırmada hem de uygulamada nadirdi. Ancak, 2011'de Kogan ve Petrank , CAS ilkelinde , genellikle ortak donanımda bulunan, beklemesiz bir kuyruk oluşturmayı sundu . Yapıları, uygulamada sıklıkla kullanılan verimli bir kuyruk olan Michael ve Scott'ın kilitsiz kuyruğunu genişletti. Kogan ve Petrank tarafından hazırlanan bir takip makalesi, beklemesiz algoritmaları hızlı hale getirmek için bir yöntem sağladı ve bu yöntemi, beklemesiz kuyruğu pratik olarak kilitsiz muadili kadar hızlı yapmak için kullandı. Timnat ve Petrank'ın müteakip bir makalesi, kilitsiz olanlardan beklemesiz veri yapıları oluşturmak için otomatik bir mekanizma sağladı. Bu nedenle, artık birçok veri yapısı için beklemesiz uygulamalar mevcuttur.

Kilit-özgürlük

Kilit serbestliği, bireysel iş parçacıklarının aç kalmasına izin verir, ancak sistem genelinde verimi garanti eder. Program iş parçacıkları yeterince uzun bir süre çalıştırıldığında, iş parçacıklarından en az biri ilerleme gösteriyorsa (bazı mantıklı ilerleme tanımları için) bir algoritma kilitsizdir. Tüm beklemesiz algoritmalar kilitsizdir.

Özellikle, bir iş parçacığı askıya alınırsa, kilitsiz bir algoritma, kalan iş parçacıklarının hala ilerleme kaydetmesini garanti eder. Bu nedenle, iki iş parçacığı aynı muteks kilidi veya döndürme kilidi için rekabet edebiliyorsa, algoritma kilitsiz değildir . (Kilidi tutan bir ipliği askıya alırsak, ikinci iplik bloke olur.)

Bazı işlemciler tarafından sonsuz sıklıkta işlem sonlu sayıda adımda başarılı olacaksa, bir algoritma kilitsizdir. Örneğin, N işlemci bir işlemi yürütmeye çalışıyorsa, N işlemin bazıları işlemi sonlu sayıda adımda tamamlamayı başarır ve diğerleri başarısız olur ve başarısızlık durumunda yeniden denenebilir. Beklemesiz ve kilitsiz arasındaki fark, diğer işlemcilerden bağımsız olarak, her işlem tarafından beklemesiz işlemin sınırlı sayıda adımda başarılı olmasının garanti edilmesidir.

Genel olarak, kilitsiz bir algoritma dört aşamada çalışabilir: kişinin kendi operasyonunu tamamlaması, bir engelleme operasyonuna yardım etmesi, bir engelleme operasyonunu iptal etmesi ve beklemesi. Kişinin kendi operasyonunu tamamlaması, eşzamanlı yardım ve kürtaj olasılığı nedeniyle karmaşıktır, ancak her zaman tamamlamaya giden en hızlı yoldur.

Bir engelle karşılaşıldığında ne zaman yardım edileceğine, iptal edileceğine veya bekleneceğine ilişkin karar, bir çekişme yöneticisinin sorumluluğundadır . Bu çok basit olabilir (yüksek öncelikli işlemlere yardımcı olun, düşük öncelikli işlemleri iptal edin) veya daha iyi verim elde etmek veya öncelikli işlemlerin gecikmesini azaltmak için daha optimize edilebilir.

Doğru eşzamanlı yardım, tipik olarak, kilitsiz bir algoritmanın en karmaşık parçasıdır ve genellikle yürütülmesi çok maliyetlidir: yalnızca yardımcı iş parçacığı yavaşlamakla kalmaz, paylaşılan bellek mekaniği sayesinde, yardım edilen iş parçacığı da yavaşlar. , eğer hala çalışıyorsa.

engel-özgürlük

Engelleme özgürlüğü, en zayıf doğal engelleyici olmayan ilerleme garantisidir. Bir algoritma, herhangi bir noktada, sınırlı sayıda adım için yalıtılmış olarak yürütülen tek bir iş parçacığı (yani, tüm engelleyici iş parçacıkları askıya alınmış olarak) işlemini tamamlayacaksa engelsizdir. Tüm kilitsiz algoritmalar engelsizdir.

Engelleme özgürlüğü, yalnızca kısmen tamamlanmış herhangi bir işlemin iptal edilmesini ve yapılan değişikliklerin geri alınmasını gerektirir. Eşzamanlı yardımı bırakmak, çoğu zaman doğrulaması daha kolay olan çok daha basit algoritmalarla sonuçlanabilir. Sistemin sürekli olarak canlı kilitlenmesini önlemek , bir çekişme yöneticisinin görevidir.

Bazı engelsiz algoritmalar, veri yapısında bir çift "tutarlılık işareti" kullanır. Veri yapısını okuyan işlemler önce bir tutarlılık işaretçisini okur, ardından ilgili verileri dahili bir arabelleğe okur, ardından diğer işaretleyiciyi okur ve ardından işaretleri karşılaştırır. İki belirteç aynıysa veriler tutarlıdır. Okuma, veri yapısını güncelleyen başka bir işlem tarafından kesintiye uğratıldığında, işaretleyiciler aynı olmayabilir. Böyle bir durumda, işlem dahili arabellekteki verileri atar ve yeniden dener.

Ayrıca bakınız

Referanslar

Dış bağlantılar