Güvenli anlambilim - Safe semantics

Güvenli anlambilim bir bilgisayar donanımı tutarlılık modeli. Bir garanti türünü açıklar: veri kaydı birkaç kişi tarafından paylaşıldığında işlemciler içinde paralel bilgisayar veya birlikte çalışan bir bilgisayar ağında.

Tarih

Güvenli anlambilim ilk olarak şu şekilde tanımlanmıştır: Leslie Lamport 1985'te.[1] Resmi olarak 1986'da Lamport'un "İşlemler Arası İletişim Üzerine" adlı eserinde tanımlanmıştır.[2]

Güvenli kayıt, birçok dağıtılmış sistemde uygulanmıştır.

Açıklama

Güvenli anlambilim, tek yazarlı ancak birden çok okuyuculu (SWMR) bir değişken için tanımlanır. Her bir okuma işlemi şu özellikleri karşılıyorsa bir SWMR kaydı güvenlidir:

Güvenli kayıt - örtüşme yok
  1. Herhangi bir yazma işlemiyle eşzamanlı olmayan bir okuma işlemi, en son yazma işlemi tarafından yazılan değeri döndürür.
  2. Bir yazma işlemiyle eşzamanlı olan bir okuma işlemi, yazmacın izin verilen değer aralığı içinde herhangi bir değer döndürebilir (örneğin, 0,1,2, ...).
    güvenli kayıt çakışması

Özellikle, bir okuma ve bir yazma işleminin eşzamanlılığı verildiğinde, okuma, yazma tarafından yazılmamış bir değeri döndürebilir. Dönüş değeri yalnızca kayıt alanına ait olmalıdır.

Bir ikili güvenli kayıt, biraz titreyen modelleme olarak görülebilir. Kaydın önceki değeri ne olursa olsun, değeri yazma bitene kadar titreyebilir. Bu nedenle, bir yazmayla çakışan okuma 0 veya 1 döndürebilir.

Çalkalama dağıtılmış bir sisteme sunucuların giriş ve çıkışlarını ifade eder. Baldoni vd. hiçbir kaydın daha güçlü özelliğe sahip olamayacağını gösterin düzenli anlambilim içinde senkron sistem sürekli karmaşa altında.[3] Ancak, senkronize olmayan bir sistemde sürekli karmaşa altında güvenli bir kayıt uygulanabilir.[4] Sakin olmayan karmaşa altında bir depolama belleği türünü (Güvenli Kayıt) modellemek ve uygulamak, istemci ve sunucu sistemleri gibi bazı sistem modellerini gerektirir.[4] İstemci sistemleri, sunucu sistemini okumaktan ve yazmaktan sorumlu olan sonlu, keyfi sayıda süreç içerir. Bununla birlikte, sunucu sistemi okuma ve yazma işlemlerinin doğru şekilde gerçekleşmesini sağlamalıdır.

Uygulama

Güvenli kayıt uygulaması şunları içerir:

Güvenli kayıt, aktif sunucular kümesi tarafından korunur.

Müşteriler kayıt bilgisi tutmaz.

Sonunda senkronize sistem

Quora (sunucu veya istemci sistemleri kümesi)

Quora = n - f - J üzerinde yürütülen Okuma ve Yazma işleminin boyutu (n sunucu sayısıdır, J giriş ve çıkış yapan sunucu sayısıdır ve f sayısıdır. Bizans başarısızlıkları.

Birleştirme, okuma ve yazma gibi algoritmalar.[4]

Katılmak

Bir sunucu (si) bir sunucu sistemine girmek isteyen, diğer sunuculara girişini bildirmek için bir sorgu mesajı yayınlar, si, kayıt defterinin geçerli bir değerini ister. Diğer sunucu bu sorguyu aldıktan sonra si'ye cevap mesajları gönderir. Si, diğer sunuculardan yeterince yanıt aldıktan sonra, yanıtları toplar ve bir yanıt kümesine kaydeder. Si, diğer sunuculardan yeterli yanıt (n-f-j) alana kadar bekler ve ardından en sık alınan değeri seçer. Si ayrıca:

  • Kayıt defterinin yerel kopyasını günceller
  • Aktif hale gelir
  • Cevap setindeki süreçlere cevaplar
  • Aktif hale gelirse, diğer sunuculara cevap mesajları gönderir. Aksi takdirde soruları saklar, aktif olduğunda cevap verir.
  • Diğer sunuculardan yanıt aldığında, yanıt kümesine yeni yanıtı ekler ve eski değeri atar.
  • Yanıt veren sunucunun değeri si'nin değerinden büyükse, si yeni değeri korur.

Okuyun

Okuma algoritması, birleştirmenin temel bir sürümüdür. Fark, okuma işlemi tarafından kullanılan yayın mekanizmasıdır. Müşteri (cw) sisteme bir mesaj yayınlar ve bir sunucu sorguyu aldıktan sonra istemciye bir cevap mesajı gönderir. Müşteri yeterli yanıt aldığında (n-f-j) sorgu göndermeyi durdurur.

okuma işlemi

Yazmak

Müşteri (cw) sisteme farklı turlarda bir sorgu gönderir ve iki onay alana kadar bekler. (sn = sıra numarası)

yazma işlemi
yazma işlemi

İki alındı ​​bildirimi almanın nedeni, bir sistemde tehlikeden kaçınmaktır. Bir işlem bir alındı ​​bildirimi gönderdiğinde (ack), bir milisaniye sonra ölebilir. Bu nedenle, müşteri tarafından herhangi bir onay alınmaz.

Güvenli kaydın geçerliliği (Bir okuma herhangi bir yazma ile eşzamanlı değilse, yazılan son değeri döndür) çekirdek sistemine göre kanıtlanmıştır.[4] İki çekirdek sistemi (Qw, Qr) verildiğinde, Qw en son değeri bilen sunucuları, Qr ise okunan yanıtların değerlerini belirtir. Her bir çoğunluğun boyutu n-f-j'ye eşittir.[4] Güvenli kaydın geçerliliğini kanıtlamak, kanıtlamayı gerektirir

-di B Bizans başarısızlıklarının sayısıdır.

İspat: Kırmızı bölge (Qw∩Qr) B'yi ve mavi bölge Qr∩B'yi gösterir. Varsayımdan, her bir çekirdeğin boyutu n-f-j'dir, bu nedenle kırmızı bölgede n-3f-2j etkin sunucuları vardır. Bu nedenle,

kesinlikle f'den büyüktür.

geçerlilik

Notlar

  1. ^ Lamport, Leslie (Haziran 1986). "Süreçler arası iletişim hakkında: Bölüm I: Temel biçimcilik" (PDF). Dağıtık Hesaplama. 1 (2): 77–85. doi:10.1007 / BF01786227. ISSN  0178-2770.
  2. ^ Lamport, Leslie (Haziran 1986). "İşlemler arası iletişim hakkında: Bölüm I: Temel biçimcilik". Dağıtık Hesaplama. 1 (2): 77–85. doi:10.1007 / BF01786227. ISSN  0178-2770.
  3. ^ Baldoni, Roberto; Bonomi, Silvia; Raynal, Michel (Ocak 2012). "Sürekli Karışmaya Eğilimli Sonunda Eşzamanlı Dağıtılmış Bir Sisteme Düzenli Kayıt Uygulama". Paralel ve Dağıtık Sistemlerde IEEE İşlemleri. 23 (1): 102–109. doi:10.1109 / TPDS.2011.97. ISSN  1045-9219.
  4. ^ a b c d e Baldoni, Roberto; Bonomi, Silvia; Nezhad, Amir Soltani (Kasım 2013). "Karmaşa eğilimli dağıtılmış sistemlerde Bizans depolamasını uygulamaya yönelik bir protokol". Teorik Bilgisayar Bilimleri. 512: 28–40. doi:10.1016 / j.tcs.2013.04.005.

Ayrıca bakınız