Test et ve ayarla - Test-and-set

Olarak bilgisayar biliminin , test ve ayar kullanıcı bir bellek konumu bir yazma (dizi) için kullanılan kullanıcı 1 'dir ve tek bir şekilde eski değerini geri atom (yani, kesintisiz) işlem. Arayan, daha sonra, durumun çağrı tarafından değiştirilip değiştirilmediğini görmek için sonucu "test edebilir". Birden fazla işlem aynı bellek konumuna erişebiliyorsa ve bir işlem şu anda bir test et ve ayarla işlemi gerçekleştiriyorsa, ilk işlemin test ve ayarlama işlemi bitene kadar başka hiçbir işlem başka bir test ve ayarla başlatamaz. Bir CPU , çift ​​bağlantı noktalı RAM gibi başka bir elektronik bileşen tarafından sunulan bir test ve ayarla talimatını kullanabilir ; bir CPU'nun kendisi de bir test ve ayarla talimatı sunabilir.

Atomik bir test ve ayar talimatı kullanılarak aşağıdaki gibi bir kilit oluşturulabilir: 

function Lock(boolean *lock) { 
    while (test_and_set(lock) == 1); 
}

Bu kod, bellek konumunun ilk test ve ayar işleminden önce bir noktada 0 olarak başlatıldığını varsayar. Çağırma işlemi, eski değer 0 ise kilidi alır, aksi halde while döngüsü kilidi almayı bekleyen döner. Buna spinlock denir . Herhangi bir noktada, kilidin sahibi, kilidi bir başkası tarafından almak üzere serbest bırakmak için bellek konumunu 0'a geri ayarlayabilir - bu, tutucu bu bellek konumunun "sahibi" olduğu için herhangi bir özel işlem gerektirmez. " Test et ve test et ve ayarla " başka bir örnektir.

Maurice Herlihy (1991), test ve kümenin (1 bit karşılaştırma) sonlu bir fikir birliği sayısına sahip olduğunu ve en fazla iki eşzamanlı süreç için beklemesiz fikir birliği sorununu çözebileceğini kanıtladı . Buna karşılık, karşılaştır ve değiştir (32-bit karşılaştırma) bu soruna daha genel bir çözüm sunar ve bazı uygulamalarda, genişletilmiş yardımcı program için karşılaştır-çift-ve-değiştir (64-bit karşılaştırma) da mevcuttur.

Test ve setin donanım uygulaması

DPRAM test et ve ayarla yönergeleri birçok şekilde çalışabilir. Burada, her ikisi de tam olarak 2 bağlantı noktası sağlayan ve 2 ayrı elektronik bileşenin (2 CPU gibi) DPRAM üzerindeki her bellek konumuna erişmesine izin veren bir DPRAM'i tanımlayan iki varyasyon vardır.

Varyasyon 1

CPU 1 bir test ve ayarla talimatı verdiğinde, DPRAM önce bellek konumunun adresini özel bir yerde saklayarak bunun bir "dahili notunu" alır. Bu noktada CPU 2, aynı bellek konumu için bir test ve ayarla talimatı yayınlarsa, DPRAM önce "dahili notunu" kontrol eder, durumu tanır ve CPU 2'ye yapması gerektiğini söyleyen bir BUSY kesmesi yayınlar. bekleyin ve tekrar deneyin. Bu, kesme mekanizmasını kullanan yoğun bir bekleme veya döndürme kilidi uygulamasıdır . Tüm bunlar donanım hızlarında gerçekleştiğinden, CPU 2'nin dönüş kilidinden çıkmak için bekleme süresi çok kısadır.

CPU 2, bellek konumuna erişmeye çalışıyor olsun veya olmasın, DPRAM, CPU 1 tarafından verilen testi gerçekleştirir. Test başarılı olursa, DPRAM, bellek konumunu CPU 1 tarafından verilen değere ayarlar. not "CPU 1 orada yazıyor. Bu noktada CPU 2, başarılı olacak bir test ve ayar yapabilir.

Varyasyon 2

CPU 1, "hafıza konumu A"ya yazmak için bir test ve ayarla talimatı verir. DPRAM, değeri hemen bellek konumu A'da saklamaz, bunun yerine, bellek konumu A'nın içeriğini özel bir "bayrak değerine" ayarlarken, aynı anda mevcut değeri özel bir kayıt defterine taşır. Bu noktada CPU 2, bellek konumu A'ya bir test ve ayar gönderirse, DPRAM özel bayrak değerini algılar ve Varyasyon 1'de olduğu gibi bir BUSY interrupt'ı verir.

CPU 2, bellek konumuna erişmeye çalışsa da çalışmasa da, DPRAM şimdi CPU 1'in testini gerçekleştirir. Test başarılı olursa, DPRAM bellek konumu A'yı CPU 1 tarafından belirtilen değere ayarlar. Test başarısız olursa, DPRAM değeri özel kayıttan bellek konumu A'ya geri kopyalar. Her iki işlem de özel bayrak değerini siler. CPU 2 şimdi bir test ve ayar yaparsa, başarılı olacaktır.

Test ve setin yazılım uygulaması

Bazı komut setleri, atomik bir test ve set makine dili talimatına sahiptir. Örnekler arasında x86 ve IBM System/360 ve ardılları ( z/Architecture dahil ) sayılabilir . Hala bir atomik test ve ayarla uygulayamayanlar, bir oku-değiştir-yaz veya karşılaştır ve değiştir talimatı kullanarak.

Test ve set komutu, boole değerleriyle kullanıldığında, işlevin atomik olarak yürütülmesi gerekmesi dışında, aşağıdaki işlevde gösterilene benzer bir mantık kullanır . Diğer bir deyişle, başka hiçbir işlem, yürütmenin ortasında işlevi kesintiye uğratmamalı, böylece yalnızca işlev yürütülürken var olan bir durumu görmemelidir. Bu donanım desteği gerektirir; gösterildiği gibi uygulanamaz. Yine de gösterilen kod, test et ve ayarla davranışını açıklamaya yardımcı olur. NOT: Bu örnekte, 'kilit'in referansla (veya ada göre) iletildiği varsayılır, ancak 'initial' ataması yeni bir değer oluşturur (yalnızca bir referansı kopyalamakla kalmaz). 

function TestAndSet(boolean_ref lock) {
    boolean initial = lock;
    lock = true;
    return initial;
}

Gösterilen kod yalnızca test et ve kur talimatı anlamında atomik olmamakla kalmaz, aynı zamanda yukarıdaki DPRAM donanım test ve kurulum açıklamalarından da farklıdır. Burada, ayarlanan değer ve test sabit ve değişmezdir ve testin sonucundan bağımsız olarak değer güncellenir, oysa DPRAM test ve ayarlama için bellek yalnızca test başarılı olduğunda ayarlanır ve değer ayarlamak için ve test koşulu CPU tarafından belirlenir. Burada, ayarlanacak değer yalnızca 1 olabilir, ancak bellek konumu için yalnızca 0 ve 1 geçerli değerler olarak kabul edilirse ve "değer sıfırdan farklıysa" izin verilen tek test ise, bu, DPRAM donanımı için açıklanan duruma eşittir ( veya daha spesifik olarak, DPRAM durumu bu kısıtlamalar altında buna indirgenir). Bu bakış açısından, bu, doğru bir şekilde, terimin tam, geleneksel anlamında "test-ve-set" olarak adlandırılabilir. Unutulmaması gereken temel nokta, test et ve ayarla'nın genel amacı ve ilkesidir: bir değer, test edildikten sonra ancak ondan önce hedef bellek konumunu başka hiçbir program dizisi veya işlemi değiştiremeyecek şekilde tek bir atomik işlemde hem test edilir hem de ayarlanır. ayarlanır. (Bunun nedeni, konumun yalnızca o anda belirli bir değere sahip olması durumunda ayarlanması gerektiğidir, bu değere daha önce sahip olması durumunda değil.)

In C programlama dili , uygulama gibi olacaktır: 

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

Kod ayrıca gerçekten iki işlem olduğunu gösterir: atomik bir okuma-değiştirme-yazma ve bir test. Yalnızca okuma-değiştirme-yazma işleminin atomik olması gerekir. (Bu doğrudur, çünkü değer karşılaştırmasını herhangi bir süre geciktirmek, test edilecek değer elde edildikten sonra testin sonucunu değiştirmeyecektir. Kod ilk değeri yazdıktan sonra, henüz hesaplanmadı - örneğin, == operatörü tarafından.)

Test ve set kullanarak karşılıklı dışlama

Karşılıklı dışlamayı uygulamanın bir yolu , aşağıdaki gibi test ve ayarla tabanlı bir kilit kullanmaktır:

Sözde C uygulaması

volatile int lock = 0;

void critical() {
    while (test_and_set(&lock) == 1);
    critical section  // only one process can be in this section at a time
    lock = 0;  // release lock when finished with the critical section
}

Kilit değişkeni paylaşılan bir değişkendir, yani tüm işlemciler/iş parçacığı tarafından erişilebilir. Not uçucu anahtar kelime. Geçici olmaması durumunda, derleyici ve/veya CPU(lar) kilitleme erişimini optimize edebilir ve/veya önbelleğe alınmış değerleri kullanabilir, böylece yukarıdaki kodu hatalı hale getirebilir. Tersine, ve ne yazık ki, varlığı uçucu yok değil garanti okuma ve yazma belleğine kararlıyız. Bazı derleyiciler , işlemlerin belleğe bağlanmasını sağlamak için bellek engelleri yayınlar , ancak C/C++'da volatile'ın anlamı oldukça belirsiz olduğundan, tüm derleyiciler bunu yapmaz. Olup olmadığını belirlemek için derleyicinizin belgelerine bakın.

Bu işlev birden fazla işlem tarafından çağrılabilir, ancak aynı anda kritik bölümde yalnızca bir işlemin olacağı garanti edilir . İşlemlerin geri kalanı, kilidi alana kadar dönmeye devam edecektir. Bir sürece asla kilit verilmemesi mümkündür. Böyle bir durumda sonsuz döngüye girer. Bu, adaleti sağlamadığı için bu uygulamanın bir dezavantajıdır. Bu konular performans bölümünde daha ayrıntılı olarak açıklanmıştır .

Montaj uygulaması

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

İşte tslbir atomik talimat ve flagkilit değişkenidir. Kilidi almadığı sürece süreç geri dönmez.

Test et ve ayarla kilitlerin performans değerlendirmesi

Genel olarak kilitler için dört ana değerlendirme metriği, rakipsiz kilit edinme gecikmesi, veri yolu trafiği, adalet ve depolamadır.

Test ve set puanları ikisinde düşük, yani yüksek otobüs trafiği ve adaletsizlik.

P1 işlemcisi bir kilit aldığında ve P2 işlemcisi de kilidi beklediğinde, P2 kilidi elde etme girişimlerinde gerçekleşen veri yolu işlemlerini sürdürecektir. Bir işlemci bir kilit elde ettiğinde, aynı kilidi elde etmek isteyen diğer tüm işlemciler, kilidi ele geçirene kadar tekrar tekrar bus işlemleri başlatarak kilidi elde etmeye çalışırlar. Bu, test et ve ayarla otobüs trafiği gereksinimini önemli ölçüde artırır. Bu, önbellekten gelen diğer tüm trafiği yavaşlatır ve tutarlılık kayıplarını azaltır. Trafik, başarısız kilit alma girişimleriyle doyduğundan, genel bölümü yavaşlatır. Test-ve-test-ve-set , sürekli olarak kilit alma isteklerini başlatmadığından TSL'ye göre bir gelişmedir.

Adaleti düşündüğümüzde, bir işlemcinin serbest bırakıldığında kilidi elde etme konusunda adil bir şansa sahip olup olmadığını düşünürüz. Aşırı bir durumda işlemci aç kalabilir, yani bu süre içinde serbest kalmasına rağmen uzun bir süre kilidi alamayabilir.

Yalnızca bir kilit gerektiğinden, TSL için depolama yükü neredeyse sıfırdır. Yalnızca bir atomik talimat ve dal gerektiğinden, tartışmasız gecikme de düşüktür.

Ayrıca bakınız

Referanslar

  1. ^ Anderson, TE (1990-01-01). "Paylaşımlı para çoklu işlemciler için döndürme kilidi alternatiflerinin performansı". Paralel ve Dağıtık Sistemlerde IEEE İşlemleri . 1 (1): 6-16. doi : 10.1109/71.80120 . ISSN  1045-9219 .
  2. ^ Herlihy, Maurice (Ocak 1991). "Beklemesiz senkronizasyon" (PDF) . ACM Trans. Program. Lang. Sist . 13 (1): 124–149. CiteSeerX  10.1.1.56.5659 . doi : 10.1145/114005.10208 . 2007-05-20 alındı .
  3. ^ "BTS—Bit Testi ve Ayarlama" . www.felixcloutier.com . 2016-11-21 alındı .
  4. ^ "IBM Bilgi Merkezi" . www.ibm.com . 2016-11-21 alındı .
  5. ^ Remzi H. Arpaci-Dusseau ve Andrea C. Arpaci-Dusseau (2015). İşletim Sistemleri: Üç Kolay Parça (0.91 ed.). Arpaci-Dusseau Kitapları – http://www.ostep.org/ aracılığıyla .
  6. ^ Solihin, Yan (2009). Paralel bilgisayar mimarisinin temelleri: çok çipli ve çok çekirdekli sistemler . P. 252. ISBN 9780984163007.
  7. ^ Solihin, Yan (2016). Paralel Mimarinin Temelleri . Boca Raton, FL: CRC Basın. ISBN'si 978-1-4822-1118-4.

Dış bağlantılar