Bilet kilidi - Ticket lock
İçinde bilgisayar Bilimi, bir bilet kilidi bir senkronizasyon mekanizmasıdır veya kilitleme algoritması bu bir tür spinlock hangisini kontrol etmek için "biletleri" kullanan Konu yürütmenin bir girmesine izin verilir kritik Bölüm.
Genel Bakış
Bilet kilidinin temel konsepti, bilet kuyruğu yönetim sistemine benzer. Bu, birçok fırın ve şarküterinin müşterilere geldikleri sıraya göre sıraya girmeden hizmet vermek için kullandıkları yöntemdir. Genel olarak, müşterilerin varışta sıralı olarak numaralandırılmış biletleri çektiği bir tür dağıtıcı vardır. Dağıtıcının genellikle üstünde veya yakınında "Lütfen bir numara alın" gibi bir işaret vardır. Ayrıca, şu anda sunulan bilet numarasını gösteren, genellikle dijital olan dinamik bir işaret de vardır. Bir sonraki bilet numarası (müşteri) hizmete hazır olduğu her seferinde, "Şimdi Sunuluyor" işareti artırılır ve numara çağrılır. Bu, tüm bekleyen müşterilerin kuyrukta veya sırada kaç kişinin hala önlerinde olduğunu bilmelerini sağlar.
Bu sistem gibi, bir bilet kilidi de bir ilk giren ilk çıkar (FIFO) kuyruk temelli mekanizma. Faydasını ekler adalet kilit edinimi ve aşağıdaki gibi çalışır; 0'dan başlayan iki tamsayı değeri vardır. İlk değer kuyruk bileti, ikincisi kuyruktan çıkarma biletidir. Kuyruk bileti, iş parçacığının kuyruktaki konumudur ve kuyruktan çıkarma bileti, artık kilide sahip olan bilet veya kuyruk konumudur (Şimdi Sunuluyor).
Bir iş parçacığı geldiğinde, kuyruk biletini atomik olarak alır ve ardından artırır. atomiklik Bu işlemin, iki iş parçacığının aynı anda aynı bilet numarasını almasını önlemek için gereklidir. Daha sonra artıştan önceki bilet değerini kuyruktan çıkarma biletinin değeriyle karşılaştırır. Aynı iseler, iş parçacığının kritik bölüme girmesine izin verilir. Aynı değillerse, kritik bölümde başka bir iş parçacığı zaten olmalı ve bu ileti dizisi meşgul bekle veya verim. Bir iş parçacığı kilit tarafından kontrol edilen kritik bölümü terk ettiğinde, kuyruktan çıkarma biletini atomik olarak artırır. Bu, sonraki sıralı bilet numarasına sahip olan bir sonraki bekleyen iş parçacığının kritik bölüme girmesine izin verir.[1]
Kilit ediniminin adaleti
Kavramı adalet kilit edinimi, iş parçacığının bir kilidi başarılı bir şekilde elde ettiği sıra için geçerlidir.[2] Bir tür adalet uygulanırsa, iş parçacığının aç diğer iş parçacıkları lehine bir kilit elde edilememesi nedeniyle uzun süre yürütme dışı. Hiçbir adalet garantisi olmadan, bir iş parçacığının (veya birden çok iş parçacığının) yürütülmesinin diğerlerine kıyasla orantısız bir şekilde uzun süre alabileceği bir durum ortaya çıkabilir. Şimdi, kilit edinimindeki adalet eksikliğinden dolayı bir iş parçacığının nasıl aşırı derecede gecikebileceğini göstermek için basit bir örnek sunulacaktır.
Her biri üç işlemciden birinde çalışan üç iş parçacığının, adaleti dikkate almadan bir kilit kullanan aşağıdaki sözde kodu çalıştırdığı bir durumu varsayın.
süre (1) { kilit { … kritik Bölüm … } Kilidini aç}Şimdi üç işlemcinin (P1, P2 ve P3) fiziksel düzenlemesinin bir tek tip olmayan bellek erişimi paylaşılan kilit değişkeninin konumu. Üç işlemci için kilit değişkenine erişim süresini artırma sırası P1
| Zaman | P1 | P2 | P3 |
|---|---|---|---|
| 1 | kilit denemesi (başarılı) | kilitlenme denemesi (başarısız) | kilitlenme denemesi (başarısız) |
| 2 | kritik Bölüm | çevirmek | çevirmek |
| 3 | serbest bırakma kilidi | kilit denemesi (başarılı) | kilitlenme denemesi (başarısız) |
| 4 | ... | kritik Bölüm | çevirmek |
| 5 | kilitlenme denemesi (başarısız) | ... | ... |
| 6 | kilit denemesi (başarılı) | serbest bırakma kilidi | kilitlenme denemesi (başarısız) |
| 7 | kritik Bölüm | çevirmek | çevirmek |
| ... | ... | ... | ... |
Başlangıçta kilit ücretsizdir ve üç işlemci de kilidi aynı anda almaya çalışır (Zaman 1). Kilide en hızlı erişim süresine sahip olan P1 sayesinde önce onu alır ve kritik bölüme girer. P2 ve P3 artık P1 kritik bölümdeyken dönüyor (Zaman 2). Kritik bölümden çıktıktan sonra (Zaman 3), P1 bir kilit açma işlemi gerçekleştirerek kilidi serbest bırakır. P2, kilide P3'ten daha hızlı erişime sahip olduğundan, daha sonra kilidi alır ve kritik bölüme (Zaman 4) girer. P2 kritik bölümdeyken, P1 bir kez daha kilidi almaya çalışır, ancak yapamaz (Süre 5), onu P3 ile birlikte dönmeye zorlar. P2 kritik bölümü bitirdiğinde ve bir kilit açma işlemi yaptığında, hem P1 hem de P3 aynı anda onu bir kez daha almaya çalışır (Süre 6). Ancak P1, daha hızlı erişim süresi ile tekrar kazanır ve böylece kritik bölüme (Süre 7) girer. Kilidi elde edemeyen bu P3 paterni, P1 veya P2 onu almaya çalışmayı bırakana kadar süresiz olarak devam edecektir.
Bu, belirli durumlarda kilit ediniminde bir miktar adalet sağlama ihtiyacını göstermektedir. Tüm kilitler, yukarıda gösterilene benzer durumlar için potansiyel bırakarak, herhangi bir adalet düzeyi sağlayan mekanizmalara sahip değildir. Bakın Kilitlerin karşılaştırılması herhangi bir adalet garantisini uygulamayan kilit örnekleri için aşağıdaki bölüm.
Bilet kilidinin uygulanması
İçinde Düzgün Olmayan Bellek Mimarisi (NUMA) sistem, bir seviyeyi garanti eden bir kilit uygulamasına sahip olmak önemlidir. kilit ediniminin adaleti. Bilet kilidi bir uygulamasıdır spinlock bu istenen özelliği ekler. Aşağıdaki sözde kod[1][3] kilidi başlatma, kilidi alma ve kilidi açma işlemlerini gösterir. TicketLock_acquire çağrısı kodun kritik bölümünden önce gelir ve ticketLock_release onu takip eder. Her işlemci, her işlemcinin my_ticket değeri aracılığıyla sırasını takip edecektir.
Yan Solihin'in sözde kod örneği aşağıdaki şemada listelenmiştir.[1]
1 ticketLock_init(int *next_ticket, int *now_serving) 2 { 3 *now_serving = *next_ticket = 0; 4 } 5 6 ticketLock_acquire(int *next_ticket, int *now_serving) 7 { 8 biletim = fetch_and_inc(next_ticket); 9 süre (*now_serving != biletim) {}10 }11 12 ticketLock_release(int *now_serving)13 {14 ++*now_serving;15 }Yukarıdaki sözde kodun yanı sıra, bir işlemcinin her defasında bir kilit almaya çalıştığını görebiliriz. ticketLock_acquire (), fetch_and_inc , next_ticket'in mevcut değerini özel my_ticket iş parçacığına döndürerek ve paylaşılan next_ticket'i artırarak çağrılır. Getirme ve artırmanın atomik olarak yapıldığına ve dolayısıyla eşzamanlı erişim girişimlerine izin verilmediğine dikkat etmek önemlidir. My_ticket alındıktan sonra, now_serving my_ticket'e eşit değilken, her iş parçacığı while döngüsü içinde dönecektir. Now_serving, belirli bir iş parçacığının my_ticket'ına eşit olduğunda, ticketLock_acquire () işlevinden dönmelerine ve kodun kritik bölümünü girmelerine izin verilir. Kodun kritik bölümünden sonra, iş parçacığı now_serving'i artıran ticketLock_release () işlemini gerçekleştirir. Bu, sıralı my_ticket ile iş parçacığının ticketLock_acquire () 'den çıkmasına ve kritik bölüme girmesine izin verir.[3] My_ticket değerleri, ipliğin kilide geliş sırasına göre elde edildiğinden, kilidin sonraki ediniminin de aynı sırada olması garanti edilir. Böylelikle, bir FIFO siparişi uygulayarak kilit ediniminde adalet sağlanır.
Aşağıdaki tablo, kritik bölüme erişim için rekabet eden dört işlemciye (P1, P2, P3, P4) sahip bir sistemde iş başında bilet kilidinin bir örneğini göstermektedir. "İşlem" sütunu ile birlikte, yukarıdaki sözde koda dayalı sonuç gözlemlenebilir. Her satır için, gösterilen değişken değerleri şunlardır: sonra belirtilen eylem (ler) tamamlandı. Örnekten dikkat edilmesi gereken en önemli nokta, dört işlemcinin tümünün kilidi edinmeye yönelik ilk girişimlerinin, yalnızca ilk varanın kilidi almasıyla sonuçlanmasıdır. Sonraki tüm girişimler, ilk hala kilidi tutarken, kritik bölümde sıralarını bekleyen işlemciler kuyruğunu oluşturmaya yarar. Bunu, her birinin sırayla kilidi alması takip eder ve bir önceki tutucu ayrılırken sıradaki bir sonraki kilidi elde etmesine izin verir. Ayrıca, başka bir işlemcinin diğer işlemciler tarafından kilit alma / bırakma dizisi sırasında herhangi bir zamanda gelebileceğini ve sırasını beklediğini unutmayın.
| Kürek çekmek | Aksiyon | next_ticket | now_serving | P1 biletim | P2 biletim | P3 biletim | P4 biletim |
|---|---|---|---|---|---|---|---|
| 1 | 0 olarak başlatıldı | 0 | 0 | - | - | - | - |
| 2 | P1 kilidi almaya çalışır (başarılı olur) | 1 | 0 | 0 | - | - | - |
| 3 | P3 kilidi almaya çalışır (başarısız + bekle) | 2 | 0 | 0 | - | 1 | - |
| 4 | P2 kilidi almaya çalışır (başarısız + bekleyin) | 3 | 0 | 0 | 2 | 1 | - |
| 5 | P1 kilidi serbest bırakır, P3 kilidi alır | 3 | 1 | 0 | 2 | 1 | - |
| 6 | P3 kilidi serbest bırakır, P2 kilidi alır | 3 | 2 | 0 | 2 | 1 | - |
| 7 | P4 kilidi almaya çalışır (başarısız + bekle) | 4 | 2 | 0 | 2 | 1 | 3 |
| 8 | P2 kilidi serbest bırakır, P4 kilidi alır | 4 | 3 | 0 | 2 | 1 | 3 |
| 9 | P4 kilidi serbest bırakır | 4 | 4 | 0 | 2 | 1 | 3 |
| 10 | ... | 4 | 4 | 0 | 2 | 1 | 3 |
Kilidin kullanımından önceki ilk adım, tüm kilit değişkenlerinin başlatılmasıdır (Satır 1). Next_ticket ve now_serving'in 0 olarak başlatılması, kilidi almaya çalışan ilk iş parçacığının 0 biletini almasını ve böylece now_serving bilet eşleşmesi nedeniyle kilidi almasını sağlar. Böylece P1 kilidi almaya çalıştığında, hemen başarılı olur ve next_ticket 1'e yükseltilir (2. Satır). P3 kilidi almaya çalıştığında, my_ticket için 1 alır, sonraki bilet 2'ye çıkarılır ve now_serving hala 0 olduğundan beklemesi gerekir (Satır 3). Daha sonra, P2 kilidi almaya çalıştığında, my_ticket için 2 alır, next_ticket 3'e çıkarılır ve ayrıca now_serving hala 0 olduğu için beklemesi gerekir (Satır 4). P1 şimdi now_serving'i 1'e yükselterek kilidi serbest bırakır, böylece P3'ün my_ticket değeri 1 (Satır 5) nedeniyle onu almasına izin verir. Şimdi P3 kilidi serbest bırakır, now_serving 2'ye yükseltir ve P2'nin onu almasına izin verir (Satır 6). P2 kilidi varken, P4 onu almaya çalışır, my_ticket değerini 3 olarak alır, next_ticket'i 4'e yükseltir ve now_serving hala 2 olduğu için beklemesi gerekir (Satır 7). P2 kilidi serbest bıraktığında, şimdi 3'e yükselir ve P4'ün onu almasına izin verir (Satır 8). Son olarak, P4 kilidi serbest bırakır ve now_serving'i 4'e yükseltir (Satır 9). Şu anda bekleyen hiçbir iş parçacığı bu bilet numarasına sahip değildir, bu nedenle gelecek iş parçacığı, bileti için 4 alır ve hemen kilidi alır.
Kilitlerin karşılaştırılması
Linux çekirdeği uygulama, daha basit olana göre daha düşük gecikme süresine sahip olabilir test et ve ayarla veya değiş tokuş modern makinelere dayalı spinlock algoritmaları. Çeşitli spin tabanlı kilit türlerini karşılaştırırken aşağıdaki tabloyu dikkate alın. Daha temel kilitleme mekanizmaları, gelişmiş kilitleme mekanizmalarından daha düşük devam etmeyen gecikmeye sahiptir.[1]
| Kriterler | test et ve ayarla | Test ve Test Et ve Ayarla | Yük bağlantısı / mağaza koşullu | Bilet | ABQL |
|---|---|---|---|---|---|
| Kesintisiz gecikme | En düşük | Daha düşük | Daha düşük | Daha yüksek | Daha yüksek |
| 1 Maksimum trafiği serbest bırakın | Ө (p) | Ө (p) | Ө (p) | Ө (p) | Ө (1) |
| Trafiği bekle | Yüksek | - | - | - | - |
| Depolama | Ө (1) | Ө (1) | Ө (1) | Ө (1) | Ө (p) |
| Adalet garantisi | Hayır | Hayır | Hayır | Evet | Evet |
Avantajlar
- Bilet kilidinin diğer spinlock algoritmalarına göre bir avantajı, adil olmasıdır. Bekleyen iş parçacıkları bir ilk giren ilk çıkar kuyruktan çıkarma bileti tamsayı arttıkça temel, böylece açlık.
- Bilet kilit algoritması ayrıca gürleyen sürü sorunu her seferinde yalnızca bir iş parçacığı kritik bölüme girmeye çalıştığı için meydana gelir.
- Depolamanın bir sorun olması gerekmez, çünkü tüm iş parçacıkları tek bir değişken üzerinde döner. dizi tabanlı kuyruk kilitleri (ABQL) bir dizinin tek tek öğeleri üzerinde dönen iş parçacıklarına sahip.[1]
Dezavantajları
- Bir dezavantaj, bir kilit serbest bırakılmadan önce tüm iş parçacıklarının dönmekte olduğu değeri okumak ve test etmek için gereken ekstra talimatlardan dolayı daha yüksek bir kesintisiz gecikme olmasıdır.[1]
- Bilet kilidinin diğer bir önemli dezavantajı, ölçeklendirilemez olmasıdır. Araştırmalar, işlemciler bir Bilet Kilit sistemine eklendikçe performansın katlanarak azaldığını gösterdi.[4]
- Diğer bir sorun, bir kilidi serbest bırakmaktan kaynaklanır. Tüm iş parçacıkları tek bir değişken üzerinde dönmektedir, bu nedenle kilit serbest bırakıldığında, Ө (p) geçersizlikler (ve ayrıca Ө (p) edinimleri) vardır. Bunun nedeni, tüm iş parçacıklarının bloklarını önbelleğe yeniden yüklemeleri ve kritik bölüme girişlerini belirlemek için bir test gerçekleştirmeleri gerektiğidir.[1]
Tarih
Bilet kilidi 1991'de Mellor-Crummey ve Scott tarafından tanıtıldı.[3] Bu algoritma, Linux çekirdeği 2008 yılında avantajları nedeniyle,[5] ama ihmal edildi sanallaştırılmış dezavantajları olduğu ortamlar.[6] Temmuz 2010 itibariyle[Güncelleme], paravirtualization'da bilet kilitlerinin kullanılmasına yönelik çalışmalar devam etmektedir.[7] Mart 2015 itibariyle, bu tür bir kilitleme şeması sistemlerinde Red Hat Enterprise Linux tarafından yeniden kullanılmıştır.[8]
Alakalı iş
- Lamport'un fırıncılık algoritması benzer bir "bilet" veya "sayaç" kavramı kullanır, ancak atomik donanım işlemlerini kullanmaz. Performanstan çok hata toleransı için tasarlanmıştır. Yayın sayacını sürekli olarak inceleyen tüm işlemcilerden ziyade, fırın kilidi, benzerlerinin biletlerini inceleyerek döner.[3]
- Sıraya dayalı döndürme kilitleri, bir garson kuyruğunu koruyarak ve kilit açma işlemi sırasında ilk garsona kilit vererek adaleti garanti eder.[9]
Ayrıca bakınız
- getir ve ekle, bir bilet kilidi uygulamak için getir ve artır yerine kullanılabilecek başka bir atom talimatı
Referanslar
- ^ a b c d e f g h Solihin, Yan (2009). Paralel bilgisayar mimarisinin temelleri: çok çipli ve çok çekirdekli sistemler. Solihin Pub. s. 262–269. ISBN 978-0-9841630-0-7.
- ^ Sottile, Matthew J .; Mattson, Timothy G .; Rasmussen, Craig E (28 Eyl 2009). Programlama Dillerinde Eş Zamanlılığa Giriş. Boca Raton, FL, ABD: CRC Press. s. 56. ISBN 978-1-4200-7214-3.
- ^ a b c d John M. Mellor-Crummey ve Michael L. Scott; et al. (Şubat 1991). "Paylaşılan Bellekli Çok İşlemcilerde Ölçeklenebilir Senkronizasyon için Algoritmalar". ACM TOCS.
- ^ Boyd-Wickizer, Silas, vd. "Ölçeklendirilemeyen kilitler tehlikelidir." Linux Sempozyumu Bildirileri. 2012. http://pdos.csail.mit.edu/papers/linux:lock.pdf
- ^ Jonathan Corbet, Bilet kilitleri, Linux Weekly News, 6 Şubat 2008. Erişim tarihi: 23 Temmuz 2010.
- ^ Jeremy Fitzhardinge, paravirt: bir "kilit bayt" spinlock uygulaması tanıtın, Linux çekirdeği, 7 Temmuz 2008
- ^ "Merge branch 'xen / pvticketlock' into xen / next"
- ^ "Ticket Spinlocks".
- ^ Michael L. Scott ve William N. Scherer III. Zaman Aşımına Sahip Ölçeklenebilir Sıraya Dayalı Döndürme Kilitleri Paralel programlama ilkeleri ve uygulamaları üzerine sekizinci ACM SIGPLAN sempozyumunun bildirileri, s. 44-52, 2001.