Úvod Mutexy Semafory Další synchronizační objekty Závěr Synchronizace a řízení přístupu ke zdrojům Tématicky zaměřený vývoj aplikací v jazyce C skupina Systémové programování – Linux Petr Velan Fakulta informatiky Masarykova univerzita velan@ics.muni.cz Brno, 28. října 2014 P. Velan 7 – Synchronizace 28. 10. 2014, Brno 1 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Úvod motivace, řízení přístupu ke zdrojům P. Velan 7 – Synchronizace 28. 10. 2014, Brno 2 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Motivace – Problém souběhu (race conditions) Problém zpracování/přístupu ke sdíleným datům/zdrojům (problém atomicity operací) Příklad – inkrementace sdíleného čitače int counter = 0; void *my_thread (void* p) { int i = 0; for (i = 0; i < 50000; i++) { counter++; } return NULL; } P. Velan 7 – Synchronizace 28. 10. 2014, Brno 3 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Motivace – Problém souběhu (race conditions) Problém zpracování/přístupu ke sdíleným datům/zdrojům (problém atomicity operací) Příklad – inkrementace sdíleného čitače int counter = 0; void *my_thread (void* p) { int i = 0; for (i = 0; i < 50000; i++) { counter++; } return NULL; } → řízení přístupu ke zdrojům Další profláknuté příklady Čtenáři a písaři Večeřící filosofové (cs.wikipedia.org/wiki/Problém_obědvajících_filosofů) P. Velan 7 – Synchronizace 28. 10. 2014, Brno 3 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Pojmy mutual exclusion – vzájemné vyloučení, když zdroj používá jedno vlákno, další k němu nesmí přistoupit (Alice a Bob mají psa a kočku a chtějí je pustit na dvorek) kritická sekce – část kódu, kterou nemůže vykonávat více vláken najednou futex – synchronizační objekt v jádře Linuxu, kterým jsou implementovány ostatní synchronizační mechanismy mutex – spinlock – semafor – bariéra – podmínková proměnná – P. Velan 7 – Synchronizace 28. 10. 2014, Brno 4 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Teorie řešení problému kritické sekce 3 podmínky řešení problému KS 1 vzájemné vyloučení 2 vyloučení uváznutí (deadlock) 3 vyloučení stárnutí (konečné čekání – starvation) Algoritmy vzájemného vyloučení Dekker Peterson P. Velan 7 – Synchronizace 28. 10. 2014, Brno 5 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Teorie řešení problému kritické sekce 3 podmínky řešení problému KS 1 vzájemné vyloučení 2 vyloučení uváznutí (deadlock) 3 vyloučení stárnutí (konečné čekání – starvation) Algoritmy vzájemného vyloučení Dekker Peterson Linux vám poskytne nástroje, ale správné použití je na vás. P. Velan 7 – Synchronizace 28. 10. 2014, Brno 5 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Mutexy práce s mutexy, atributy mutexů P. Velan 7 – Synchronizace 28. 10. 2014, Brno 6 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr mutex – Mutual Exclusion lock Zamknout mutex může pouze 1 vlákno Další vlákna pak při pokusu o zamčení čekájí na odemčení Atomicita zamykání mutexu je garantována jádrem #include int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr); pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; int pthread_mutex_destroy(pthread_mutex_t *mutex); int pthread_mutex_lock(pthread_mutex_t *mutex); int pthread_mutex_trylock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex); P. Velan 7 – Synchronizace 28. 10. 2014, Brno 7 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr úkol Projděte si soubeh.c z adresáře files/ P. Velan 7 – Synchronizace 28. 10. 2014, Brno 8 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr úkol Projděte si soubeh.c z adresáře files/ Vyřešte problém souběhu pomocí mutexu P. Velan 7 – Synchronizace 28. 10. 2014, Brno 8 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Problém uváznutí (deadlock) zapomenutý zamknutý mutex dvojnásobné zamčení mutexu P. Velan 7 – Synchronizace 28. 10. 2014, Brno 9 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Problém uváznutí (deadlock) zapomenutý zamknutý mutex dvojnásobné zamčení mutexu Typy mutexů rychlý mutex (defaultní v Linuxu) rekurzivní mutex – povoleno násobné zamykání, ale musí následovat stejný počet odemčení kontrolovaný mutex – jádro kontroluje zamykání a při pokusu o násobné zamčení vrací EDEADLK robustní mutex – vyrovná se se zamknutým mutexem při ukončení vlákna (Nepřenositelný!) P. Velan 7 – Synchronizace 28. 10. 2014, Brno 9 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Atributy mutexů nastavení vlastností mutexů – lze je ale nastavit pouze před vytvořením mutexu man -k pthread_mutexattr Použití 1 pthread_mutexattr_init() 2 pthread_mutexattr_set* 3 použítí ve funkci pthread_mutex_init() 4 pthread_mutexattr_destroy() Příklady pthread_mutexattr_settype(pthread_mutexattr_t *attr, int type) P. Velan 7 – Synchronizace 28. 10. 2014, Brno 10 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr spinlock – aktivní zámek aktivní čekání na odemčení zámku příliš se nepoužívá P. Velan 7 – Synchronizace 28. 10. 2014, Brno 11 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr spinlock – aktivní zámek aktivní čekání na odemčení zámku příliš se nepoužívá vhodný na vícejádrových systémech, když víte, že skutečně nebudete čekat dlouho #include int pthread_spin_init(pthread_spinlock_t *lock, int pshared); int pthread_spin_destroy(pthread_spinlock_t *lock); int pthread_spin_lock(pthread_spinlock_t *lock); int pthread_spin_unlock(pthread_spinlock_t *lock); P. Velan 7 – Synchronizace 28. 10. 2014, Brno 11 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Čtenáři a písaři občas je dobré mít různé zámky podle typu operace v kritické sekci nevadí, když více vláken data pouze čte – nikdo ale nesmí zapisovat když už někdo zapisuje, nesmí nikdo jiný ani číst, ani zapisovat #include int pthread_rwlock_destroy(pthread_rwlock_t *rwlock); int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock, const pthread_rwlockattr_t *restrict attr); int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock); int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock); int pthread_rwlock_unlock(pthread_rwlock_t *rwlock); P. Velan 7 – Synchronizace 28. 10. 2014, Brno 12 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Čtenáři a písaři občas je dobré mít různé zámky podle typu operace v kritické sekci nevadí, když více vláken data pouze čte – nikdo ale nesmí zapisovat když už někdo zapisuje, nesmí nikdo jiný ani číst, ani zapisovat #include int pthread_rwlock_destroy(pthread_rwlock_t *rwlock); int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock, const pthread_rwlockattr_t *restrict attr); int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock); int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock); int pthread_rwlock_unlock(pthread_rwlock_t *rwlock); K zámkům souborů se dostaneme v některé z příštích lekcí P. Velan 7 – Synchronizace 28. 10. 2014, Brno 12 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Semafory práce se semafory P. Velan 7 – Synchronizace 28. 10. 2014, Brno 13 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Semafor obecnější verze mutexu lze povolit vstup více vláken do kritické sekce původně součást System V IPC, my se budeme zabývat jednoduššími a přehlednějšími POSIX semafory úlohy typu Producent-Konzument problém omezeného bufferu Princip fungování v principu nezáporný čítač s počáteční hodnotou (počet vláken, které mohou vstoupit do kritické sekce) inkrement čítače funkcí sem_post dekrement čítače funkcí sem_wait, která je blokující v případě, že má čítač hodnotu 0 jádro garantuje atomicitu operací další informace: man 7 sem_overview P. Velan 7 – Synchronizace 28. 10. 2014, Brno 14 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Semafory – použití #include int sem_wait(sem_t *sem); int sem_post(sem_t *sem); int sem_trywait(sem_t *sem); int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout); int sem_getvalue(sem_t *sem, int *sval); Pojmenované semafory Dostupné přes virtuální filesystém v /dev/shm/ sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value); int sem_close(sem_t *sem); int sem_unlink(const char *name); Nepojmenované semafory Nutno alokovat paměť dostupnou všem vláknům (procesům1) int sem_init(sem_t *sem, int pshared, unsigned int value); int sem_destroy(sem_t *sem); 1 paměť sdílenou mezi procesy probereme později P. Velan 7 – Synchronizace 28. 10. 2014, Brno 15 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr úkol Upravte předchozí úlohu s mutexy tak, že fronta není naplněna na začátku, ale jedno vlákno funguje jako producent průběžně doplňující data do fronty. Ostatní vlákna pak tyto úlohy zpracovávají. P. Velan 7 – Synchronizace 28. 10. 2014, Brno 16 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Další synchronizační objekty bariéry a podmínkové proměnné P. Velan 7 – Synchronizace 28. 10. 2014, Brno 17 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Bariéra Zarážka – synchronizace vláken na konkrétní místo v programu. Dokud se na bariéře nezastaví specifikovaný počet vláken, jsou všechny blokovány, následně jsou všechny najednou probuzeny. #include int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned count); int pthread_barrier_wait(pthread_barrier_t *barrier); int pthread_barrier_destroy(pthread_barrier_t *barrier); P. Velan 7 – Synchronizace 28. 10. 2014, Brno 18 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Podmínkové proměnné Obdoba bariéry, ale nečeká se na určitý počet čekajících vláken, ale na splnění podmínky. Při splnění podmínky mohou být spušteny všechny vlákna, nebo jen jedno. Využívá pomocný mutex P. Velan 7 – Synchronizace 28. 10. 2014, Brno 19 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Podmínkové proměnné Obdoba bariéry, ale nečeká se na určitý počet čekajících vláken, ale na splnění podmínky. Při splnění podmínky mohou být spušteny všechny vlákna, nebo jen jedno. Využívá pomocný mutex Odstraňuje busy-waiting (condvar.c) P. Velan 7 – Synchronizace 28. 10. 2014, Brno 19 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Podmínkové proměnné – princip Postup – čekání na podmínku 1 vlákno zamkne mutex a přečte příznak (ověří podmínku) 2 je-li podmínka nastavena, odemkne mutex a provede práci 3 není-li podmínka nastavena, zavolá vlákno pthread_cond_wait, ta automaticky (a atomicky) odemkne mutex a uspí se 4 po probuzení se uzamkne mutex a znovu se kontroluje podmínka Postup – nastavení podmínky 1 vlákno zamkne mutex podmínkové proměnné 2 upraví příznak/podmínku 3 zavolá pthread_cond_signál nebo pthread_cond_broadcast, čímž probudí čekající vlákno (vlákna) 4 probuzené vlákno se pokusí zamknout mutex (znovu se uspí při čekání na odemknutí mutexu) 5 vlákno, které probouzelo ostatní, odemkne mutex a uvolní tak cestu čekajícímu vláknu P. Velan 7 – Synchronizace 28. 10. 2014, Brno 20 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Podmínkové proměnné – funkce #include int pthread_cond_init(pthread_cond_t *restrict cond, const pthread_condattr_t *restrict attr); pthread_cond_t cond = PTHREAD_COND_INITIALIZER; int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex); int pthread_cond_broadcast(pthread_cond_t *cond); int pthread_cond_signal(pthread_cond_t *cond); int pthread_cond_destroy(pthread_cond_t *cond); P. Velan 7 – Synchronizace 28. 10. 2014, Brno 21 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Podmínkové proměnné – příklad pthread_cond_init(&cond, NULL); pthread_mutex_lock(&mt); /* lock condition’s mutex */ while (mycond != 0) { /* test the condition */ /* automatically unlocks mutex and falls asleep */ /* automatically locks mutex on waking up */ pthread_cond_wait(&cond, &mt); } pthread_mutex_unlock(&mt); /* unlock the mutex */ ... /* waking up */ pthread_mutex_lock(&mt); /* lock condition’s mutex */ ... /* change the condition */ pthread_cond_signal(&cond); /* wake up another waiting thread */ pthread_mutex_unlock(&mt); P. Velan 7 – Synchronizace 28. 10. 2014, Brno 22 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr úkol Upravte condvar.c tak, aby nedocházelo k busy waitingu. P. Velan 7 – Synchronizace 28. 10. 2014, Brno 23 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Závěr shrnutí, domácí úkoly a zdroje P. Velan 7 – Synchronizace 28. 10. 2014, Brno 24 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Synchronizace mezi procesy Všechny zmíněné synchronizační mechanismy lze použít i pro synchronizaci procesů Některé nabízejí vlastní mechanismus (pojmenované semafory) U funkcí z pthread.h je třeba pomocí atributů deklarovat požutí mezi procesy Většinou je ale potřeba použít sdílenou paměť – příště. P. Velan 7 – Synchronizace 28. 10. 2014, Brno 25 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Domácí úkol Knihovna front implementujte knihovnu pro práci s frontami API podrobně v files/queues.h knihovna (všechny funkce) je thread-safe nezapomeňte ošetřit chybné použití (pořadí) funkcí volání enqueue/dequeue funkcí před inicializací/po ukončení vícenásobné volání inicializace . . . nezapomeňte, že dequeue je blokující, ale nesmí docházet k busy-waitingu před odevzdáním otestujte! P. Velan 7 – Synchronizace 28. 10. 2014, Brno 26 / 27 Úvod Mutexy Semafory Další synchronizační objekty Závěr Zdroje www.ibm.com/developerworks/aix/library/au-ipc/index.html computing.llnl.gov/tutorials/pthreads/ www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html www.csc.villanova.edu/∼mdamian/threads/posixsem.html Pro zájemce System V IPC Message Passing beej.us/guide/bgipc/output/html/multipage/mq.html POSIX Message Queues www.users.pjwstk.edu.pl/∼jms/qnx/help/watcom/clibref/mq_overview.html P. Velan 7 – Synchronizace 28. 10. 2014, Brno 27 / 27