Testování a nastavení- Test-and-set

V informatice se TSL instrukce je instrukce používá k zápisu (sada) 1 do paměti a vrátí se svou starou hodnotu jako jediná atomová (tj non-přerušitelné) provozu. Volající pak může výsledek „otestovat“, aby zjistil, zda nebyl stav hovorem změněn. Pokud ke stejnému umístění paměti může přistupovat více procesů a pokud proces aktuálně provádí test a sadu, žádný jiný proces nesmí zahájit další test a sadu, dokud se nedokončí test a sada prvního procesu. CPU může použít TSL instrukci nabízené jiným elektronických komponent, jako dual-port RAM ; CPU sám může také nabídnout instrukci test-and-set.

Zámek lze postavit pomocí instrukce atomového testu a nastavení následujícím způsobem:

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

Tento kód předpokládá, že umístění paměti bylo v určitém okamžiku před prvním testem a sadou inicializováno na 0. Proces volání získá zámek, pokud byla stará hodnota 0, jinak se smyčka while otáčí a čeká na získání zámku. Tomu se říká spinlock . V každém okamžiku může držitel zámku jednoduše nastavit umístění paměti zpět na 0, aby zámek uvolnil pro získání jiným-to nevyžaduje žádné zvláštní zacházení, protože držitel toto místo paměti „vlastní“. „ Test a test a nastavení “ je dalším příkladem.

Maurice Herlihy (1991) dokázal, že test-and-set (1bitové porovnání) má konečné konsensuální číslo a dokáže vyřešit problém bez konsensu bez čekání u nejvýše dvou souběžných procesů. Naproti tomu porovnávání a odkládání (32bitové porovnávání) nabízí obecnější řešení tohoto problému a v některých implementacích je pro rozšířené nástroje k dispozici také porovnání dvojité a odkládací (64bitové porovnání).

Hardwarová implementace test-and-set

Pokyny k testování a nastavení DPRAM mohou fungovat mnoha způsoby. Zde jsou dvě varianty, z nichž obě popisují DPRAM, který poskytuje přesně 2 porty, což umožňuje 2 samostatným elektronickým součástem (například 2 CPU) přístup ke každému umístění paměti na DPRAM.

Variace 1

Když CPU 1 vydá testovací a nastavenou instrukci, DPRAM nejprve provede „interní poznámku“ tím, že uloží adresu paměťového místa na zvláštní místo. Pokud v tomto okamžiku CPU 2 vydá testovací a nastavenou instrukci pro stejné umístění paměti, DPRAM nejprve zkontroluje svou „interní poznámku“, rozpozná situaci a vydá BUSY přerušení, které CPU 2 řekne, že musí počkejte a zkuste to znovu. Toto je implementace rušného čekání nebo spinlocku pomocí mechanismu přerušení. Vzhledem k tomu, že se to vše děje při hardwarových rychlostech, je čekání CPU 2 na výstup ze spinu velmi krátké.

Bez ohledu na to, zda se CPU 2 pokoušel získat přístup k umístění paměti, DPRAM provede test zadaný CPU 1. Pokud test proběhne úspěšně, DPRAM nastaví umístění paměti na hodnotu danou CPU 1. Poté DPRAM smaže své „interní“ poznámka "že tam psal CPU 1. V tomto okamžiku by CPU 2 mohl vydat test-and-set, což by uspělo.

Variace 2

CPU 1 vydá testovací a nastavenou instrukci pro zápis do "paměťového místa A". DPRAM okamžitě neuloží hodnotu do paměťového místa A, ale místo toho současně přesune aktuální hodnotu do speciálního registru, přičemž nastaví obsah paměťového umístění A na speciální „hodnotu příznaku“. Pokud v tomto okamžiku CPU 2 vydá testovací a nastavený do paměťového umístění A, DPRAM detekuje hodnotu speciálního příznaku a stejně jako ve variantě 1 vydá BUSY přerušení.

Bez ohledu na to, zda se CPU 2 pokoušel získat přístup k umístění paměti, DPRAM nyní provede test CPU 1. Pokud je test úspěšný, DPRAM nastaví paměťové místo A na hodnotu specifikovanou CPU 1. Pokud test selže, DPRAM zkopíruje hodnotu zpět ze speciálního registru do paměťového umístění A. Každá operace smaže hodnotu speciálního příznaku. Pokud CPU 2 nyní vydá testovací sadu, bude úspěšná.

Softwarová implementace test-and-set

Některé instrukční sady mají instrukci atomového testu a nastavení strojového jazyka. Mezi příklady patří x86 a IBM System/360 a jeho nástupci (včetně z/Architecture ). Ti, kteří tak neučiní, mohou stále implementovat atomový test a sadu pomocí instrukce pro čtení, úpravu, zápis nebo porovnání a výměnu .

Instrukce test a set, pokud je použita s booleovskými hodnotami, používá logiku podobnou té, která je znázorněna v následující funkci, s tím rozdílem, že funkce se musí spouštět atomicky . To znamená, že žádný jiný proces nesmí být schopen přerušit střední výkon funkce, a tím vidět stav, který existuje pouze při provádění funkce. To vyžaduje hardwarovou podporu; nelze jej implementovat, jak je ukázáno. Zobrazený kód nicméně pomáhá vysvětlit chování test-and-set. POZNÁMKA: V tomto příkladu se předpokládá, že „zámek“ je předán odkazem (nebo jménem), ale přiřazení „počátečního“ vytvoří novou hodnotu (nejen kopírování odkazu).

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

Nejen, že kód není zobrazen atomově, ve smyslu instrukce test-and-set, ale také se liší od výše uvedených popisů hardwarových testů a sad DPRAM. Zde jsou nastavovaná hodnota a test pevné a neměnné a hodnota je aktualizována bez ohledu na výsledek testu, zatímco pro test-a-sadu DPRAM je paměť nastavena pouze tehdy, když test proběhne úspěšně, a hodnota nastavit a testovací podmínky určuje CPU. Zde může být nastavená hodnota pouze 1, ale pokud jsou 0 a 1 považovány za jediné platné hodnoty pro umístění v paměti a „hodnota je nenulová“ je jediným povoleným testem, pak to odpovídá případu popsanému pro hardware DPRAM ( nebo konkrétněji případ DPRAM se na to za těchto omezení sníží). Z tohoto hlediska to lze správně nazvat „test-and-set“ v plném, konvenčním smyslu tohoto pojmu. Základním bodem, který je třeba poznamenat, je obecný záměr a princip test-and-set: hodnota je testována i nastavena v jedné atomové operaci tak, že žádné jiné vlákno programu nebo proces nemůže změnit cílové umístění paměti po testování, ale před ním je nastaven. (Důvodem je, že umístění musí být nastaveno pouze tehdy, pokud má aktuálně určitou hodnotu, nikoli pokud tuto hodnotu mělo někdy dříve.)

V programovacím jazyce C bude implementace vypadat takto:

#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;
}

Kód také ukazuje, že existují skutečně dvě operace: atomové čtení-úprava-zápis a test. Atomové musí být pouze čtení-úpravy-zápis. (To je pravda, protože zpoždění porovnání hodnot o jakoukoli dobu nezmění výsledek testu, jakmile bude získána hodnota pro test. Jakmile kód zapíše počáteční hodnotu, výsledek testu byl stanoven, i když dosud nebylo vypočítáno - např. operátorem ==.)

Vzájemné vyloučení pomocí test-and-set

Jedním ze způsobů, jak implementovat vzájemné vyloučení, je použití zámku založeného na testování a nastavení takto:

Pseudo-C implementace

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
}

Proměnná zámku je sdílená proměnná, tj. Mohou k ní přistupovat všechny procesory/vlákna. Všimněte si nestálého klíčového slova. Pokud chybí volatile, kompilátor a/nebo CPU mohou optimalizovat přístup k uzamčení a/nebo použít hodnoty uložené v mezipaměti, čímž způsobí, že výše uvedený kód bude chybný. Naopak, a bohužel, přítomnost volatile nezaručuje , že čtení a zápisy jsou potvrzeny do paměti. Některé kompilátory vydávají paměťové bariéry, aby zajistily, že se operace zaváží do paměti, ale protože sémantika volatile v C/C ++ je docela vágní, ne všechny kompilátory to udělají. Zjistěte v dokumentaci svého kompilátoru, zda ano.

Tuto funkci lze vyvolat více procesy, ale je zaručeno, že v kritické části bude současně pouze jeden proces . Zbytek procesů se bude točit, dokud nedostanou zámek. Je možné, že procesu není nikdy udělen zámek. V takovém případě bude smyčka nekonečně dlouhá. Toto je nevýhoda této implementace, protože nezajišťuje spravedlnost. Tyto problémy jsou dále rozpracovány v sekci výkonu .

Realizace montáže

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

Zde tslje atomová instrukce a flagje to proměnná zámku. Proces se nevrátí, pokud nezíská zámek.

Hodnocení výkonu zámků testovaných a nastavených

Čtyři hlavní hodnotící metriky pro zámky obecně jsou nekontrolovaná latence získávání zámků, provoz autobusů, spravedlnost a úložiště.

Skóre testů a setů je nízké na dvou z nich, konkrétně na vysoké autobusové dopravě a nespravedlnosti.

Když procesor P1 získá zámek a procesor P2 také čeká na zámek, P2 bude při pokusu o získání zámku pokračovat ve sběrnicových transakcích. Když procesor získá zámek, všechny ostatní procesory, které si také přejí získat stejný zámek, se stále pokoušejí získat zámek opakováním transakcí sběrnice, dokud zámek nezachytí. To výrazně zvyšuje požadavky na provoz autobusů test-and-set. To zpomaluje veškerý další provoz z chyb mezipaměti a soudržnosti . Zpomaluje celý úsek, protože provoz je nasycen neúspěšnými pokusy o získání zámku. Test-and-test-and-set je vylepšení oproti TSL, protože neprovádí nepřetržitě žádosti o získání zámku.

Když vezmeme v úvahu spravedlnost, vezmeme v úvahu, zda procesor dostane spravedlivou šanci získat zámek, když je uvolněn. V extrémní situaci může procesor hladovět, tj. Nemusí být schopen zámek získat na delší dobu, přestože se během této doby uvolnil.

Režie úložiště pro TSL je téměř nulová, protože je vyžadován pouze jeden zámek. Neomezená latence je také nízká, protože je zapotřebí pouze jedna atomová instrukce a větev.

Viz také

• Načíst a přidat
• Testujte a testujte a nastavujte
• Load-link/store-conditional
• Porovnávejte a vyměňujte

Reference

externí odkazy

• Popis z encyklopedie systémů citlivých na zpoždění
• „ Testování a nastavení bez čekání “ od Yehudy Afka
• int testandset (int *lock) - rutina s možností volání C napsaná v jazyce sestavení Sun SPARC
• Intel Developer Manual