IB109 Návrh a implementace paralelních systémů Programování v prostředí se sdílenou pamětí Jiří Barnat Sekce 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/34 Race condition Pozorování Paralelní programy mohou při opakovaném spouštění zdánlivě náhodně vykazovat různá chování. 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/34 Race condition – příklad Příklad *myStructure p; P0 { P1 { p = new myStructure; p = new myStructure; p -> data = 1; p -> data = 2; cout <<(p->data)<data)< 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/34 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 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/34 Thread-safe a re-entrantní procedury Nebezpečné akce vzhledem k paralelnímu zpracování Nekontrolovaný přístup ke globálním proměnným a haldě. 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. 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. 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/34 Procedura, která není thread-safe *myStructure p; *myStructure function() { p=new myStructure; return p; } P0 { P1 { *myStructure x; *myStructure x; x=function(); x=function(); } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 13/34 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“. Veškeré modifikace a neatomická čtení globálních proměnných musí být serializovány. Kritická sekce Část kódu, jehož provedení je neproložitelné instrukcemi jiného vlákna. Realizace kritické sekce musí být odolná vůči plánování. Zamykání Vlákno vstupující do volné kritické sekce, svým vstupem znemožní přístup ostatním vláknům (sekci tzv. zamkne). Ostatní vlákna čekají před vstupem do kritické sekce. Při odchodu z kritické sekce, je zámek uvolněn, získá ho náhodně jedno z čekajících vláken. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 14/34 Zamykání a související pojmy Jednoduché řešení zámku Sdílená atomicky přistupovaná bitová proměnná, jejíž hodnota indikuje přítomnost procesu/vlákna v přidružené kritické sekci. Manipulována při vstupu a výstupu z/do kritické sekce. Vyžaduje podporu HW pro atomickou manipulaci. Aktivní čekání – spinlock Dokud neuspěje, vlákno opakovaně zkouší vstoupit do kritické sekce (tj. po tuto dobu neustále provádí tentýž kód). 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. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 15/34 Rizika zamykání Rizika Uváznutí, stárnutí, snížení výkonnosti. Přístup ke sdíleným globálním proměnným Manipulace se zámkem 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, z principu nelze odstranit. Petersonův algoritmus (spinlock, user-space) Spravedlivý algoritmus pro řízení vzájemného vyloučení. Nezpůsobuje stárnutí ani uváznutí. Vyžaduje atomické zápisy do proměnných. Citlivý na provádění instrukcí mimo pořadí. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 16/34 Sekce POSIX Thread API IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 17/34 Historie a POSIX standard Historie SMP systémy Vlákna implementována jednotlivými výrobci HW IEEE POSIX 1003.1c standard IEEE POSIX 1003.1c Programátorský model semaforů a provádění operací v kritické sekci 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/34 Základní dělení funkcionality Správa vláken Vytváření, oddělování a spojování vláken Funkce na nastavení a zjištění stavu vlákna Vzájemná vyloučení (mutexes) Vytváření, ničení, zamykání a odemykání mutexů Funkce na nastavení a zjištění atributů spojených s mutexy Podmínkové/podmíněné proměnné (conditional variable) Slouží pro komunikaci/synchronizaci vláken Funkce na vytváření, ničení, “čekání na” a “signalizování při” specifické hodnotě podmínkové proměnné Funkce na nastavení a 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/34 POSIX standard Přes 60 API funkcí #include Překlad s volbou -pthread Mnemotechnické předpony funkcí pthread_, pthread_attr_ pthread_mutex_, pthread_mutexattr_ pthread_cond_, pthread_condattr_ pthread_key_ Pracuje se skrytými objekty (Opaque objects) Objekty v paměti, o jejichž podobě programátor nic neví. 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/34 Atributy objektů Idea 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 Mutexy: pthread_mutexattr_t Podmínkové proměnné: pthread_condattr_t Vznik a destrukce Funkce _init a _destroy s odpovídající předponou 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í str. 21/34 Správa vláken Vytváření vlákna Každý program má jedno hlavní vlákno Další vlákna musí být explicitně vytvořena programem Každé vlákno (i vytvořené) může dále vytvářet další vlákna Vlákno vytvářeno funkcí pthread_create 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/34 Správa vláken int pthread_create ( pthread_t *thread_handle, const pthread_attr_t *attribute, void * (*thread_function)(void *), void *arg); thread_handle odkaz na vytvořené vlákno attribute odkaz na atributy vytvořeného vlákna (NULL pro přednastavené nastavení atributů) thread_function ukazatel na funkci nového vlákna arg ukazatel na parametry funkce thread_function 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/34 Správa vláken Ukončení vlákna nastává Voláním funkce pthread_exit Pokud skončí hlavní funkce rodičovského vlákna jinak než voláním pthread_exit Je-li zrušeno jiným vláknem pomocí pthread_cancel Rodičovský proces je ukončen (násilně nebo voláním exit) void pthread_exit (void *value) 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/34 Správa vláken – příklad 1 #include 2 #include 3 #define NUM_THREADS 5 4 5 void *PrintHello(void *threadid) 6 { printf("%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