Paradigmata programování 4 (Paralelní programování) - Seznam přednášek (sylabus)
-
Paralelní program
Paralelní programování, stav a historie paralelního programu, atomické akce, atomičnost
složených akcí, synchronizace,
charakteristiky paralelního programu.
-
Základy programové logiky
Dokazování v sekvenčním a paralelním programu, atomicita a charakteristiky stroje, synchronizace, techniky vyloučení interference (invarianty, pomocné proměnné), problém producenta a
konzumenta, bankovní systém, vlastnosti bezpečnosti a živosti (férovosti plánování).
-
Kritické sekce
Hrubá a jemná synchronizace, implementace kritických sekcí: zámek (spin lock), prolomení remízy (Petersonův algoritmus Tie-Breaker),
tahání lístků (Ticket), pekařský
algoritmus (Bakery). Dokazování kritických sekcí: vzájemné vyloučení, vyloučení uváznutí,
vyloučení zbytečného
čekání a záruka vstupu. Aktivní a pasivní
čekání.
-
Bariéry a datově paralelní algoritmy
Bariéry a jejich
implementace: sdílený čítač, vlajky a koordinátor, stromově kombinované a symetrické bariéry. Použití bariér. Problémy řešitelné datově paralelními algoritmy: prefixy pole, konec seznamu.
-
Semafory
Semafory, operace nad nimi a jejich použití. Typické úlohy paralelního programování řešené semafory: kritická sekce, bariéra, producent a
konzument, omezený buffer, večeřící
filozofové, čtenáři a písaři. Technika předávání peška (bassing the baton). Implementace semaforů.
-
Synchronizace v operačních systémech
Paralelizace a synchronizace v OS: kritické sekce, synchronizační primitiva (spin lock, read-write zámek, semafor). Synchronizace jader M$ Windows XP a Linux. API pro synchronizaci procesů a vláken v OS M$ Windows a GNU/Linux (UNIX).