Zámek lístku - Ticket lock

v počítačová věda, a zámek lístku je synchronizační mechanismus, nebo blokovací algoritmus, to je typ spinlock který používá "lístky" k ovládání toho vlákno exekuce je dovoleno vstoupit a kritická sekce.

Přehled

Příklad lístku a značky „Nyní slouží“ použité v systému správy front lístků.

Základní koncept zámku lístku je podobný systému správy front lístků. Jedná se o metodu, kterou mnoho pekáren a lahůdek používá k poskytování služeb zákazníkům v pořadí, v jakém dorazí, aniž by je přimělo stát v řadě. Obecně existuje nějaký typ výdejního automatu, ze kterého zákazníci po příjezdu vytáhnou postupně očíslované lístky. Na stojanu je obvykle nad nebo v jeho blízkosti cedule s nápisem „Vezměte prosím číslo“. K dispozici je také obvykle dynamický znak, obvykle digitální, který zobrazuje číslo lístku, který se nyní podává. Pokaždé, když je připraveno obsloužit další číslo tiketu (zákazník), zvýší se značka „Nyní slouží“ a číslo se vyvolá. To umožňuje všem čekajícím zákazníkům vědět, kolik lidí je ještě před nimi ve frontě nebo řadě.

Stejně jako tento systém je zámek lístku a první dovnitř první ven (FIFO) mechanismus založený na frontě. Přidává to výhodu spravedlnost získávání zámku a funguje následovně; existují dvě celočíselné hodnoty, které začínají na 0. První hodnotou je lístek fronty, druhou lístek dequeue. Fronta lístku je pozice vlákna ve frontě a lístek dequeue je lístek nebo pozice fronty, která má nyní zámek (Nyní slouží).

Když vlákno přijde, atomicky získá a poté zvýší lístek fronty. The atomicita této operace je vyžadováno, aby se zabránilo dvěma vláknům současně být schopny získat stejné číslo tiketu. Poté porovná svou hodnotu tiketu před přírůstkem s hodnotou tiketu vyřazení. Pokud jsou stejné, vlákno má povolený vstup do kritické sekce. Pokud nejsou stejné, pak již musí být v kritické sekci jiné vlákno a toto vlákno musí být zaneprázdněn nebo výnos. Když vlákno opustí kritickou část ovládanou zámkem, atomicky zvýší lístek dequeue. To umožňuje dalšímu čekajícímu vláknu, které má další pořadové číslo lístku, vstoupit do kritické sekce.^[1]

Spravedlivost získávání zámku

Pojem spravedlnost při získávání zámku se vztahuje na pořadí, ve kterém vlákna úspěšně získají zámek.^[2] Pokud je implementován nějaký typ spravedlnosti, zabrání tomu, aby vlákno bylo hladověl z provádění po dlouhou dobu z důvodu neschopnosti získat zámek ve prospěch jiných vláken. Bez záruk spravedlnosti může nastat situace, kdy spuštění vlákna (nebo více vláken) může trvat nepoměrně dlouho ve srovnání s ostatními. Nyní bude představen jednoduchý příklad, který ukazuje, jak by mohlo být vlákno nadměrně zpožděno kvůli nedostatečné spravedlnosti při získávání zámku.

Předpokládejme případ, kdy tři podprocesy, z nichž každé se provádí na jednom ze tří procesorů, provádějí následující pseudokód, který používá zámek bez ohledu na spravedlnost.

zatímco (1) {    zámek {        …        kritický sekce        …    }    odemknout}

Nyní dále předpokládejme, že fyzické uspořádání tří procesorů, P1, P2 a P3, má za následek a nejednotný přístup do paměti čas do umístění proměnné sdíleného zámku. Pořadí zvyšování doby přístupu k proměnné zámku pro tři procesory je P1 hladovění vláken při absenci spravedlnosti se záruka zobrazuje na následujícím obrázku provedení výše uvedeného pseudokódu těmito třemi procesory.

Zpočátku je zámek volný a všechny tři procesory se pokusí zámek získat současně (čas 1). Vzhledem k tomu, že P1 má nejrychlejší přístupovou dobu k zámku, získá ji jako první a vstoupí do kritické sekce. P2 a P3 se nyní točí, zatímco P1 je v kritické sekci (čas 2). Po opuštění kritické sekce (čas 3) provede P1 odemknutí a uvolnění zámku. Protože P2 má rychlejší přístup k zámku než P3, získá zámek dále a vstoupí do kritické sekce (čas 4). Když je P2 v kritické sekci, P1 se znovu pokusí získat zámek, ale nemůže (čas 5), nutit jej, aby točil, počkat spolu s P3. Jakmile P2 dokončí kritickou část a provede odblokování, P1 a P3 se ji současně pokusí znovu získat (čas 6). Ale P1 s rychlejším přístupovým časem opět vyhrává, čímž vstupuje do kritické sekce (čas 7). Tento vzor P3, který není schopen získat zámek, bude pokračovat neomezeně dlouho, dokud se P1 nebo P2 nepřestanou pokoušet o jeho získání.

To ilustruje potřebu zajistit za určitých okolností určitou úroveň spravedlnosti při získávání zámku. Ne všechny zámky mají mechanismy, které zajišťují jakoukoli úroveň spravedlnosti a ponechávají potenciál pro situace podobné těm, které jsou znázorněny výše. Viz Porovnání zámků v části níže naleznete příklady zámků, které neimplementují žádné záruky spravedlnosti.

Implementace zámku vstupenek

V Neuniformní architektura paměti (NUMA) systému je důležité mít implementaci zámku, která zaručuje určitou úroveň spravedlivost získávání zámku. Zámek lístku je implementací spinlock který přidává tento požadovaný atribut. Následující pseudokód^[1][3] ukazuje operace pro inicializaci zámku, získání zámku a uvolnění zámku. Volání ticketLock_acquire by předcházelo kritické části kódu a ticketLock_release by ji následovalo. Každý procesor bude sledovat svůj tah prostřednictvím hodnoty my_ticket každého procesoru.

Příklad pseudokódu Yana Solihina je uveden v následujícím diagramu.^[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     my_ticket = fetch_and_inc(next_ticket); 9     zatímco (*now_serving != my_ticket) {}10 }11 12 ticketLock_release(int *now_serving)13 {14     ++*now_serving;15 }

V návaznosti na výše uvedený pseudokód vidíme, že pokaždé, když se procesor pokusí získat zámek s ticketLock_acquire (), fetch_and_inc je volána, vrací aktuální hodnotu next_ticket do vlákna private my_ticket a zvyšuje sdílený next_ticket. Je důležité si uvědomit, že načítání a přírůstek se provádí atomicky, což neumožňuje žádné další souběžné pokusy o přístup. Po obdržení my_ticket se každé vlákno bude točit ve smyčce while, zatímco now_serving se nerovná jeho my_ticket. Jakmile se now_serving stane rovným my_ticket daného vlákna, mohou se vrátit z ticketLock_acquire () a vstoupit do kritické části kódu. Po kritické části kódu provede vlákno ticketLock_release (), které zvýší now_serving. To umožňuje vláknu s dalším sekvenčním my_ticket ukončit z ticketLock_acquire () a vstoupit do kritické sekce.^[3] Vzhledem k tomu, že hodnoty my_ticket jsou získávány v pořadí příjezdu vlákna na zámek, je zaručeno, že následné získání zámku bude také v tomto stejném pořadí. Je tak zajištěna spravedlnost získání zámku, vynucení objednávky FIFO.

Následující tabulka ukazuje příklad zámku vstupenek v akci v systému se čtyřmi procesory (P1, P2, P3, P4) soutěžícími o přístup do kritické sekce. Spolu se sloupcem „Akce“ lze sledovat výsledek založený na výše uvedeném pseudokódu. Pro každý řádek jsou zobrazené hodnoty proměnných po označené akce byly dokončeny. Klíčovým bodem, který je třeba si všimnout z příkladu, je, že počáteční pokusy všech čtyř procesorů o získání zámku vedou k tomu, že se k získání zámku dostane pouze ten první. Všechny následující pokusy, zatímco první stále drží zámek, slouží k vytvoření fronty procesorů čekajících na svůj tah v kritické sekci. Poté následuje každé získání zámku v pořadí, což dalšímu v řadě umožní získat jej při odchodu předchozího držitele. Všimněte si také, že jiný procesor může dorazit kdykoli během sekvence získávání / uvolňování zámku jinými procesory a jednoduše čeká na svůj tah.

Prvním krokem, před použitím zámku, je inicializace všech proměnných zámku (řádek 1). Inicializace next_ticket a now_serving na 0 zajistí, že první vlákno, které se pokusí získat zámek, získá lístek 0, čímž získá zámek kvůli jeho shodnému lístku now_serving. Takže když se P1 pokusí získat zámek, okamžitě uspěje a next_ticket se zvýší na 1 (řádek 2). Když se P3 pokusí získat zámek, dostane 1 pro svou my_ticket, další lístek se zvýší na 2 a musí počkat, protože now_serving je stále 0 (řádek 3). Dále, když se P2 pokusí získat zámek, dostane 2 pro svou my_ticket, next_ticket se zvýší na 3 a musí také počkat kvůli tomu, že now_serving je stále 0 (řádek 4). P1 nyní uvolní zámek zvýšením now_serving na 1, což umožňuje P3 jej získat díky jeho hodnotě my_ticket 1 (řádek 5). Nyní P3 uvolní zámek, zvýší now_serving na 2, což umožní P2, aby ho získal (řádek 6). Zatímco P2 má zámek, P4 se pokusí jej získat, získá hodnotu my_ticket 3, zvýší next_ticket na 4 a musí počkat, protože now_serving je stále 2 (řádek 7). Když P2 uvolní zámek, zvýší se now_serving na 3, což umožní P4 získat (řádek 8). Nakonec P4 uvolní zámek a zvýší now_serving na 4 (řádek 9). Žádné aktuálně čekající vlákna nemají toto číslo lístku, takže další vlákno, které dorazí, dostane za svůj lístek 4 a okamžitě získá zámek.

Porovnání zámků

The Linuxové jádro implementace může mít nižší latenci než jednodušší testovat a nastavit nebo výměna založené na spinlockových algoritmech na moderních strojích. Při porovnávání různých typů zámků založených na odstřeďování zvažte níže uvedenou tabulku. Základní blokovací mechanismy mají nižší nekontrolovanou latenci než pokročilé blokovací mechanismy.^[1]

Výhody

• Jednou z výhod zámku vstupenek oproti jiným algoritmům spinlock je, že je spravedlivý. Čekající vlákna jsou zpracována v a first-in first-out jak se zvyšuje celé číslo lístku na vyřazení, čímž se zabrání hladovění.
• Algoritmus zámku lístku také brání hromový stádový problém dochází, protože do kritické sekce se pokouší vstoupit pouze jedno vlákno najednou.
• Úložiště nemusí být nutně problém, protože se na rozdíl od všech vláken točí na jedné proměnné řadové zámky založené na poli (ABQL), kteří mají vlákna se točí na jednotlivých prvcích pole.^[1]

Nevýhody

• Jednou nevýhodou je, že existuje vyšší nekontrolovaná latence kvůli zvláštním instrukcím potřebným ke čtení a testování hodnoty, na které se točí všechna vlákna před uvolněním zámku.^[1]
• Další hlavní nevýhodou zámku lístku je, že je neškálovatelný. Výzkum ukázal, že jakmile se do systému Ticket Lock přidají procesory, zdá se, že výkon exponenciálně klesá.^[4]
• Další problém pochází z uvolnění zámku. Všechna vlákna se točí na jedné proměnné, takže po uvolnění zámku dojde k zneplatnění Ө (p) (stejně jako Ө (p) akvizice). Je to proto, že všechna vlákna musí znovu načíst svůj blok do mezipaměti a provést test, který určí jejich přijetí do kritické sekce.^[1]

Dějiny

Zámek na lístek představili Mellor-Crummey a Scott v roce 1991.^[3] Tento algoritmus byl zaveden do Linuxové jádro v roce 2008 díky svým výhodám,^[5] ale byl vynechán paravirtualizováno prostředí, kde to mělo nevýhody.^[6] Od července 2010^{[Aktualizace]}, probíhají práce umožňující použití zámků lístků v paravirtualizaci.^[7] Od března 2015 Red Hat Enterprise Linux ve svém systému tento typ uzamykacího schématu znovu nasadil.^[8]

Související práce

• Lamportův pekárenský algoritmus používá podobný koncept „lístku“ nebo „čítače“, ale nevyužívá atomové hardwarové operace. Byl navržen spíše na odolnost proti chybám než na výkon. Spíše než všechny procesory průběžně zkoumající počitadlo uvolnění se zámek pekárny otáčí při zkoumání lístků svých vrstevníků.^[3]
• Zámky rotace založené na frontách zaručují spravedlnost udržováním fronty číšníků a přidělením zámku prvnímu číšníkovi během operace odemčení.^[9]

Viz také

• načíst a přidat, další atomová instrukce, kterou lze použít místo načítání a přírůstku k implementaci zámku lístku

Reference