Test-and-set

Test-and-set (TSL, též Test-and-set lock) je v informatice jednoduchá atomická operace, která slouží k vytváření synchronizačních zámků. Operace TSL funguje tak, že nastaví hodnotu typu boolean na pravdu (true) a vrátí její předchozí hodnotu. Zajistí tak, že ze soutěžících procesů je pouze jednomu dovoleno vstoupit do kritické sekce a při nežádoucím souběhu nedojde k poškození dat v kritické oblasti současným zápisem. Další proces se dostane do kritické sekce až poté, co z ní předchozí vystoupí a hodnotu zámku nastaví na nepravdu (false), přičemž čekající proces provádí pokusy o vstup ve smyčce (tzv. aktivní čekání).

Charakteristika

TSL je velmi jednoduchá metoda vytváření zámku, která může být snadno implementována jako instrukce procesoru. Většina současných procesorů nějakou formu instrukce TSL obsahuje.^[1] TSL může být implementováno i softwarově, avšak pak je nutné zajistit její atomicitu.

Negativem metody využívající TSL je aktivní čekání (busy waiting, též spinlock), takže se hodí jen pro ochranu krátkých úseků kódu kritické sekce. Může však být základem pro řešení využívajících semaforů a fronty, která aktivní čekání odstraňuje. Operace TSL může být strojová instrukce v procesoru, může být též implementována softwarově nebo poskytována jiným obvodem (DPRAM).

Maurice Herlihy v roce 1991 dokázal, že TSL má konečnou dobu čekání při řešení souběžného přístupu na rozdíl od metody compare-and-swap (porovnej a vyměň), avšak ne pro více, než dva procesy.^[2]

Použití

Instrukce TSL je používána před vstupem do kritické sekce. Instrukce při svém vyvolání nastaví proměnnou Lock na pravdu (zamčeno) a vrátí předchozí stav této proměnné. Proto ji můžeme umístit do čekací smyčky (tzv. aktivní čekání), která bude řešit vstup do kritické sekce. Po výstupu z kritické sekce je proměnná Lock nastavena na nepravdu (odemčeno).

while TestAndSet(Lock) do { nothing } ;
   ...kód kritické sekce...
Lock:=false;

Hardwarová implementace TSL

Instrukce TSL implementované pomocí DPRAM (anglicky Dual Port RAM) může pracovat mnoha způsoby. Zde jsou popsány dvě varianty, které popisují DPRAM se dvěma porty, které dovolují dvěma odděleným elektronickým komponentám (například dva procesory) přístup do celé paměti v DPRAM.

Varianta 1

Pokud procesor 1 zpracovává TSL instrukci, DPRAM si o tomto nejdříve udělá "vnitřní poznámku" uložením adresy umístění v paměti na speciální místo. Pokud v tomto okamžiku procesor 2 také spustí zpracování instrukce TSL pro stejné umístění v paměti, DPRAM nejdříve zkontroluje "vnitřní poznámku" tohoto místa paměti, rozpoznává hrozící kolizi a oznámí procesoru 2, že musí počkat a zkusit to znovu. Toto je implementace techniky nazývané „busy waiting“ nebo „spinlock“. Protože se toto odehrává na hardwarové úrovni, čekání procesoru 2 je velmi krátké.

Ať se procesor 2 pokoušel nebo nepokoušel přistupovat na adresu, DPRAM umožní procesoru 1 provedení svou operaci TSL. Pokud TSL procesoru 1 uspěje, DPRAM nastaví adresu paměti na hodnotu danou procesorem 1. Potom DPRAM vymaže jeho "vnitřní poznámku" kterou procesor 1 svou TSL instrukcí zapsal. Následně procesor 2 neúspěšně dokončí svou TSL instrukci.

Varianta 2

Procesor 1 zpracovává TSL instrukci na adrese A. DPRAM neukládá ihned požadovaná data, místo toho přesune původní data do speciálního registru a změní obsah paměti A na hodnotu, která má význam příznaku TSL instrukce na této adrese. Pokud v tento okamžik procesor 2 spustí zpracování TSL instrukce na stejné adrese, pak DPRAM detekuje hodnotu s významem již probíhající TSL instrukce a podobně jako ve variantě jedna oznámí procesoru 2, že musí čekat.

Ať se procesor 2 pokoušel nebo nepokoušel přistupovat na adresu, DPRAM umožní procesoru 1 provedení svou operaci TSL. Pokud TSL procesoru 1 uspěje, DPRAM nastaví adresu paměti na hodnotu danou procesorem 1. Pokud TSL neuspěje, DPRAM vrací zpět do paměti hodnotu uloženou ve speciálním registru. Obě operace odstraní z paměti hodnotu s významem probíhající instrukce TSL. Pokud v tomto okamžiku spustí TSL, pak uspěje.

Softwarové realizace TSL

Mnoho procesorů má ve svém instrukčním souboru TSL instrukce. Procesory, které tyto instrukce nemají, používají atomické (nepřerušitelné) výměny nebo jiné atomické instrukce pro načtení, modifikaci zpětné uložení.

TLS instrukce s využitím logické proměnné se chová podle níže uvedeného kódu funkce. Velmi důležitou vlastností této funkce je, že žádný proces ji nemůže přerušit během jejího provádění a proto se chová tak, jak se očekává. Tento kód je určen jen pro pochopení funkce TSL, atomista (nepřerušitelnost) vyžaduje určitou hardwarovou podporu a z toho důvodu nemůže být takto jednoduše implementována.

Pozn. v tomto příkladu je lock předán referencí, ale přiřazení do initial vytváří novou hodnotu.

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

Výše uvedený kód není atomický ve smyslu TSL instrukce. Také se liší od výše uvedeného popisu DPRAM a hardwarové realizace TSL, kdy v kódu není provedeno nastavení paměti na základě testu oproti DPRAM hw realizaci TSL, kdy testovanou hodnotu a v případě úspěchu vkládanou hodnotu definuje procesor.

V dalším příkladě může být hodnota nastavena pouze na 1. Ale pokud je 0 a 1 považována za platný obsah definovaného místa adresy a test je prováděn na nenulovou hodnotu, pak je toto rovnocenné případu popisovaném pro hw implementaci v DPRAM (resp. případu DPRAM omezené těmito podmínkami).

Z tohoto pohledu, lze toto korektně nazvat TSL v plném smyslu tohoto významu. Důležitým bodem k povšimnutí je účel a princip TSL, kdy je hodnota je testována a nastavena v jedné atomické operaci tak že žádné jiný programové vlákno nesmí způsobit změnu cílové paměti po jejím testu, ale jen před jejím nastavením, což by mohlo porušit logický požadavek že paměť bude nastavena jen pokud má určitou hodnotu.

Příklad realizace v  programovacím jazyce C:

#define LOCKED 1
int TestAndSet(int* lockPtr) {
    int oldValue;
    oldValue = SwapAtomic(lockPtr, LOCKED);
    return oldValue == LOCKED;
}

Kde SwapAtomic atomicky nejdříve čte aktuální hodnotu přes ukazatel lockPtr a pak uloží 1 do umístění (pozn. překladatele: prostě prohodí *lockPtr a s konstantou 1, některé procesory mají pro toto strojovou instrukci).

Kód také ukazuje, že TSL je opravdu složena ze dvou operací: atomická výměna a test. Jen výměna musí být atomická. (Je to pravda, protože podržení hodnoty pro porovnání již nezmění výsledek testu, jakmile je hodnota pro test získána).

Realizace vzájemných vyloučení s TSL

Jedna možnost realizace vzájemného vyloučení používajících TSL je následující:

boolean lock = false
function Critical(){
    while TestAndSet(lock) 
    skip //přeskočit dokud je zámek vyžadován
    critical section //pouze jeden proces může být v této sekci
    lock = false //uvolnit zámek, když proces skončí s kritickou sekcí
}

V pseudoprogramovacím jazyce C by to mohlo být:

volatile int lock = 0;
void Critical() {
    while (TestAndSet(&lock) == 1);
    critical section //pouze jeden proces může být v této sekci
    lock = 0 //uvolnit zámek, když proces skončí s kritickou sekcí
}

Všiměte si modifikátoru volatile. Pokud by nebyl použit, pak kompilátor optimalizoval přístup k proměnné použitím dočasné lokální proměnné, vygenerovaný kód by pak byl nefunkční.

Naopak přítomnost volatile nezajišťuje, že čtení a zápis jsou prováděny přímo v paměti. Některé překladače používají tzv. paměťové bariéry k zajištění přímého provádění čtení a zápisu paměti. Protože je v tomto bodě C/C++ poněkud vágně definováno, ne všechny kompilátory to tak dělají. Proto nahlédněte do dokumentace ke svému kompilátoru.

Jiná varianta implementace vzájemného vyloučení je známa jako „Test and Test-and-set“, je daleko efektivnější na víceprocesorových počítačích. Používá stejné Test and Set instrukce, jako výše popsaná metoda, ale vylepšuje koherenci vyrovnávacích pamětí.

Implementace semaforů pomoci TSL

Test and set je možné použít pro implementaci tzv. semaforů. V jednoprocesorových systémech není tato technika potřeba (kromě případů, kdy více procesů přistupuje ke stejným datům), při implementaci semaforu je postačující zakázat přerušení před přístupem k semaforu. Avšak u víceprocesorových strojů je nevhodné, ne-li nemožné zakázat přerušení na všech procesorech ve stejný čas. Bez zakázaného přerušení tedy může dva nebo více procesorů přistupovat k paměti semaforů ve stejný čas. V tomto případě může být použito test-and-set instrukcí.

Reference

Související články

• Souběh
• Kritická sekce