I IB109 Návrh a implementace paralelních systémů Programování v prostředí se sdílenou pamětí Jiří Barnat Rizika spojená se sdílenou pamětí IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 2/30 Race condition Pozorování • Paralelní programy mohou při opakovaném spouštění zdánlivě náhodně vykazovat různá chování. 9 Výsledek provedení programu může záviset na absolutním pořadí provedení instrukcí programu, tj. na proložení instrukcí zúčastněných procesů/vláken. Race condition • Nedokonalost paralelního programu, která se projevuje takovýmto nedeterministickým chováním se označuje jako race condition, (zkráceně race). IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 3/30 Race condition - příklad Příklad *myStructure p; PO { p = new myStructure; p -> data = 1; cout «(p->data)«endl; p = new myStructure; p -> data = 2; cout «(p->data)«endl; IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 4/30 Atomicita operací Pozorování • Jednoduchý příkaz ve vyšším programovacím jazyce neodpovídá nutně jedné instrukci procesoru. o V moderních operačních systémech je každé vlákno podrobeno plánovacímu procesu. • Vykonání posloupnosti instrukcí procesoru odpovídající jednomu příkazu vyššího programovacího jazyka může být přerušeno a proloženo vykonáním instrukcí jiného vlákna. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 5/30 Atomicita operací Příklad 9 Přičtení čísla do proměnné efektivně může znamenat načtení proměnné do registru, provedení aritmetické operace, a uložení výsledku do paměti. • Při vhodném souběhu následujících procesů, se může efekt jednoho přiřazení do sdílené globální proměnné zcela vytratit volatile int a=0; • Demonstrujte proložení instrukcí, které vyústí v jinou hodnotu, než 30. PO { Pl { a = a + 10; a = a + 20; } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 6/30 Relativní rychlost výpočtu Pozorování o Nelze spoléhat na současný souběh vláken, potažmo relativní rychlost výpočtu jednotlivých vláken. Příklad volatile int a=0; PO { usleep 200; a = 0; } Pl { a = 1; usleep 200; } o Po skončení obou vláken (současně spuštěných) bude mít sdílená proměnná ve většině případů hodnotu 0. Není to však ničím garantováno, tj. může nastat situace, kdy bude mít hodnotu 1. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 7/30 Uváznutí (Deadlock) • Pokud mají vlákna inkrementální požadavky na unikátní sdílené zdroje, může dojít k tzv. uváznutí, tj. nemožnosti pokračování ve výpočtu. Příklad PO { Pl { zamkni A; zamkni B; zamkni B; zamkni A; • • • • • • } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 8/30 Hladovění Hladovění, Stárnutí, Neprogrese (Livelock) • Jev, kdy alespoň jedno vlákno není schopné vzhledem k paralelnímu souběhu s jiným vláknem pokročit ve výpočtu za danou hranici. Příklad volatile int a=0; po { while (true) {; a++; a—; }••• } pí { while (a == 0) { }; } • Vlákno Pl může na vyznačeném řádku strávit mnoho času IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 9/30 Thread-safe a re-entrantní procedury Thread-safe procedura o Označení procedury či programu, jejíž kód je bezpečné provádět (vzhledem k sémantice výstupu a stabilitě výpočtu) souběžné několika vlákny bez nutnosti vzájemné domluvy/synchronizace. • Knihovní funkce nemusí být thread-safe! • rand() -> rand_r() Re-entrantní procedura • Procedura, jejíž provádění může být v rámci jednoho vlákna přerušeno, kód kompletně vykonán od začátku do konce v rámci téže úlohy, a poté obnoveno/dokončeno přerušené vykonávání kódu. • Termím pochází z dob, kdy nebyly multitaskingové operační systémy. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 10/30 Vztah thread-safe a re-entrantnřch procedur Neporovnatelné • Re-entrantní procedura nemusí být thread-safe. viz http://en.wikipedia.org/wiki/Reentrancy_(computing) • Thread-safe procedura nemusí být re-entrantní. (Problémem je například používání globálních zámků.) Příklad 9 Thread-safe procedura, která není re-entrantní: WC { je-li odemčeno, vejdi a zamkni, jinak čekej • • • odemkni a opusť onu místnost } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 11/30 Thread-safe a re-entrantní procedury Nebezpečné akce vzhledem k paralelnímu zpracování 9 Nekontrolovaný přístup ke globálním proměnným a haldě, o Uchovávání stavu procedury do globálních proměnných. • Alokace, dealokace zdrojů globálního rozsahu (soubory, . ..). • Nepřímý přístup k datům skrze odkazy nebo ukazatele. o Viditelný vedlejší efekt (modifikace nestálých proměnných). Bezpečná strategie • Přístup pouze k lokálním proměnným (zásobník). • Kód je závislý pouze na argumentech dané funkce. o Veškeré volané podprocedury a funkce jsou thread-safe. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 12/30 Procedura, která není thread-safe *myStructure p; *myStructure functionO { p=new myStructure; return p; } PO { Pl { ♦myStructure x; *myStructure x; x=functionO ; x=functionO ; } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 13/30 Přístup ke sdíleným proměnným Pozorování • Přístup ke sdíleným proměnným je „kořenem všeho zla". • Přístup a použití sdílených proměnných se musí provádět kontrolovane. Zamykání a kritické sekce • Část kódu, jehož provedení je neproložitelné instrukcemi jiného vlákna. • Problém realizace kritické sekce musí být řešen způsobem, který je odolný vůči plánování. Jednoduché řešení 9 Sdílená atomicky přistupovaná bitová proměnná, jejíž hodnota indikuje přítomnost procesu/vlákna v přidružené kritické sekci. 9 Manipulována při vstupu a výstupu do/z kritické sekce. 9 Vyžaduje podporu HW pro atomickou manipulaci. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 14/30 Zamykaní a související pojmy Petersonův algoritmus (spinlock, user-space) • Algoritmus pro vzájemné vyloučení. • Nezpůsobuje stárnutí ani uváznutí. • Pozor na implementaci a provádění instrukcí mimo pořadí. Uspávání • Procesy/vlákna se po neúspěchu vstoupit do kritické sekce sami vzdají procesorového kvanta (uspí se). • Jsou buzeny buď po vypršení časového limitu nebo explicitně jiným běžícím vláknem. Spinlock o Vlákna opakovaně zkouší vstoupit do kritické sekce. o Pro krátké čekací dobyje efektivnější, než přepínání kontextů vláken, natož pak procesů. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 15/30 Výkonostní rizika Přístup ke sdíleným globálním proměnným • Veškeré modifikace a neatomická čtení globálních proměnných musí být serializovány, tj. prováděny po získání odpovídajícího zámku na danou operaci. o Získání zámku vynucuje vylití cache pamětí. • Mnoho přístupů k zamykaným proměnným může být úzkým místem výkonu aplikace. Lokální data vláken (Thread-private data) 9 Vlákna mají své lokální proměnné. 9 Data mohou uloženy v globální sdílené struktuře, pokud odpovídající část datové struktury je přistupována pouze daným vláknem. • Typicky pole indexovaná unikátním identifikátorem vlákna. • Riziko falešného sdílení. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 16/30 POSIX Thread API IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 17/30 Historie a POSIX standard Historie • SMP systémy 9 Vlákna implementována jednotlivými výrobci HW o IEEE POSIX 1003.1c standard IEEE POSIX 1003.1c • Programátorský model semaforů a provádění operací v kritické sekci a Rozhraní pro C • POSIX threads, PThreads Jiné normy • Operační systémy: NT Threads (Win32), Solaris threads, . .. • Programovací jazyky: Java threads, C++11 threading, ... IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 18/30 Základní dělení funkcionality Správa vláken • Vytváření, oddělování a spojování vláken • Funkce na nastavenia zjištění stavu vlákna Vzájemná vyloučení (mutexes) • Vytváření, ničení, zamykania odemykání mutexů 9 Funkce na nastavenia zjištění atributů spojených s mutexy Podmínkové/podmíněné proměnné (conditional variable) • Slouží pro komunikaci/synchronizaci vláken o Funkce na vytváření, ničení, "čekání na" a "signalizování při" specifické hodnotě podmínkové proměnné o Funkce na nastavenia zjištění atributů proměnných IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 19/30 POSIX standard Přes 60 API funkcí 9 #include • Překlad s volbou -pthread Mnemotechnické předpony funkcí 9 pthread_, pthread_attr_ • pthread_mutex_, pthread_mutexattr_ o pthread_cond_, pthread_condattr_ • pthread_key_ Pracuje se skrytými objekty (Opaque objects) • Objekty v paměti, o jejichž podobě programátor nic neví o Přistupovány výhradně pomocí odkazu (handle) Nedostupné objekty a neplatné (dangling) reference IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 20/30 Idea o Vlastnosti všech vláken, mutexů i podmínkových proměnných nastavovány speciálními objekty • Některé vlastnosti entity musí být specifikovány již v době vzniku entity Typy atributových objektů • Vlákna: pthread_attr_t a Mutexy: pthread_mutexattr_t Podmínkové proměnné: pthread_condattr_t Vznik a destrukce 9 Funkce _init a _destroy s odpovídající předponou o Parametr odkaz na odpovídající atributový objekt IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí Vytváření vlákna 9 Každý program má jedno hlavní vlákno • Další vlákna musí být explicitně vytvořena programem 9 Každé vlákno (i vytvořené) může dále vytvářet další vlákna o Vlákno vytvářeno funkcí pthreacLcreate o Vytvářené vlákno je ihned připraveno k provádění • Může být plánovačem spuštěno dříve, než se dokončí volání vytvářecí funkce • Veškerá data potřebná při spuštění vlákna, musí být připravena před voláním vytvářecí funkce • Maximální počet vláken je závislý na implementaci IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 22/30 int pthreacLcreate ( pthreacLt *thread_handle, const pthread_attr_t *attribute, void * (*thread_function) (void *), void *arg); • thread-handle odkaz na vytvořené vlákno o attribute odkaz na atributy vytvořeného vlákna (NULL pro přednastavené nastavení atributů) • thread_function ukazatel na funkci nového vlákna o arg ukazatel na parametry funkce thread_function o Při úspěšném vytvoření vlákna vrací 0 IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 23/30 Ukončení vlákna nastává • Volaním funkce pthreacLexit 9 Pokud skončí hlavní funkce rodičovského vlákna jinak než voláním pthreacLexit 9 Je-li zrušeno jiným vláknem pomocí pthreacLcancel • Rodičovský proces je ukončen (násilně nebo voláním exit) void pthreacLexit (void *value) 9 Ukončuje běh vlákna • Odkazy na prostředky procesu (soubory IPC, mutexy ...) otevřené v rámci vlákna se nezavírají • Data patřící vláknu musí být uvolněna před ukončením vlákna (systém provede uvolnění prostředků až po skončení rodičovského procesu) • Ukazatel value předán při spojení vláken IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 24/30 Správa vláken - příklad 1 #include 2 #include 3 #define NUM_THREADS 5 4 5 void *PrintHello(void *threadid) 6 { printf ('7„d: Hello World!\n", threadid) ; 7 pthread_exit (NULL) ; 8 } 9 10 int main (int argc, char *argv[]) 11 { pthread_t threads [NUM_THREADS] ; 12 for (int t=0; t