Synchronization Primitives

Moduly SEMPHR a MUTEX - semafory a mutexy
Moduly jsou určeny pro práci se semafory a mutexy. Mutexy jsou
implementovány jako binární semafory (tzn. jsou inicializovány na hodnotu
1, hodnota na mutexu může být pouze 0 nebo 1).
U každé funkce pro semafory je uveden její případný ekvivalent pro mutexy.
Pozn: Pokud je definována preprocesorová konstanta DEBUG_MUTEX a její
hodnota je > 0, mutexy hlídají, jestli jsou odemykány týmž vláknem, které
je zamklo.

struct semaphore {
	int value;
	thread_t head, tail;
	thread_t owner;
}
typedef struct semaphore semaphore_t;
typedef struct semaphore mutex_t;

int value 	- aktuální hodnota na semaforu / mutexu
thread_t head	- pointer na první prvek ve frontě vláken zablokovaných na
		  semaforu / mutexu
thread_t tail	- pointer na poslední prvek ve frontě vláken zablokovaných
		  na semaforu / mutexu
thread_t owner	- pointer na vlákno, které zamklo mutex, v semaphore_t je
		  tato položka jen tehdy, pokud je definována
		  preprocesorová konstanta DEBUG_MUTEX


Interface

void sem_init(semaphore_t *sem, int value)
void mutex_init(mutex_t *mtx)
	Funkce inicializující semafor.

void sem_destroy(semaphore_t *sem)
void mutex_destroy(mutex_t *mtx)
	Funkce používaná pro destrukci semaforu.
	Protože semafory jsou vytvářeny jako statické proměnné a
	nepoužívají žádnou dynamicky alokovanou paměť, funkce sem_destroy()
	pouze otestuje, zda je fronta vláken zablokovaných na semaforu při
	destrukci neprázdná. Pokud tomu tak není, volá se (dle zadání)
	funkce panic().

void sem_down(semaphore_t *sem)
void mutex_lock(mutex_t *mtx)
	Funkce snižující hodnotu na semaforu (hodnota se sníží vždy o 1).
	Při zakázaných přerušeních se zjistí, zda hodnota na semaforu je
	nenulová, tzn. lze snížit (v daném případě se zároveň zvýší počet
	resources, které volající vlákno drží). Pokud tomu tak není, vlákno
	volající sem_down se přidá do fronty vláken čekajících na semaforu
	a zablokuje se.
	Pozn: při definované preprocesorové konstantě DEBUG_MUTEX se u
	mutexové varianty uloží pointer na vlákno zamykající mutex.

void sem_up(semaphore_t *sem)
void mutex_unlock(mutex_t *mtx)
	Funkce zvyšující hodnotu na semaforu (hodnota se zvýší vždy o 1).
	Při zakázaných přerušeních se zvýší hodnota na semaforu a sníží se
	počet resources, které volající vlákno drží. Pokud je fronta vláken
	zablokovaných na semaforu neprázdná, probudí se následující vlákno.
	Pozn: při definované preprocesorové konstantě DEBUG_MUTEX s
	hodnotou > 0 se u mutexové varianty zkontroluje, zda je mutex
	odemykán týmž vláknem, které jej zamklo.

int sem_try_down(semaphore_t *sem)
	Funkce, která se pokusí snížit hodnotu na semaforu.
	Při zakázaných přerušeních se zjistí hodnota na semaforu. Pokud je
	hodnota nulová, funkce ihned končí. Jinak se hodnota sníží, zároveň
	se zvýší počet resources, které volající vlákno drží.
	Návratová hodnota: 0 (úspěch, hodnotu na semaforu se podařilo
	snížit), -1 (neúspěch).

int sem_down_timeout(semaphore_t *sem, uint msec)
int mutex_lock_timeout(mutex_t *mtx, uint msec)
	Funkce, která se po dobu msec pokouší snížit hodnotu na semaforu.
	Pokud se nepodaří hodnotu na semaforu v jednotlivých iteracích
	snížit a nevypršel ještě timeout, vlákno volající funkci se vzdá
	procesoru.
	Pozn: při definované preprocesorové konstantě DEBUG_MUTEX se u
	mutexové varianty uloží vlákno zamykající mutex.
	Návratová hodnota: 0 (úspěch, hodnotu na semaforu se podařilo
	snížit), -1 (neúspěch, doba msec uplynula, aniž se hodnotu semaforu
	podařilo snížit).

int sem_get_value(semaphore_t *sem)
	Funkce vracející hodnotu na semaforu.
	Návratová hodnota: hodnota na semaforu.



Modul RWLOCK - read/write locky
Modul určený pro práci s r/w locky. Implementace r/w locků je rekurzivní.
Pokud při probouzení vláken zablokovaných na r/w locku je možno vybrat mezi
vlákny čekajícími na čtení a vlákny čekajícími na zápis, dá se vždy
přednost vláknům čekajícím na zápis.

typedef struct rwlock {
        int reading;
        int writing;
        thread_t cur_writer;
        thread_t w_head, w_tail;
        thread_t r_head, r_tail;
} rwlock_t;

int reading	- počet vláken držících v daný okamžik r/w lock pro čtení
int writing	- počet rekurzivních zanoření vlákna držících r/w lock pro
		  zápis (pouze 1 vlákno může držet zámek pro čtení)
thread_t cur_writer	- pointer na vlákno, které zamklo r/w lock pro
			  zápis (nutno držet kvůli rekurzivní implementaci
			  r/w locků)
thread_t w_head	- pointer na první prvek ve frontě vláken zablokovaných na
		  r/w locku čekajících na uvolnění r/w locku pro zápis
thread_t w_tail	- pointer na poslední prvek ve frontě vláken zablokovaných
		  na r/w locku čekajících na uvolnění r/w locku pro zápis
thread_t r_head	- pointer na první prvek ve frontě vláken zablokovaných na
		  r/w locku čekajících na uvolnění r/w locku pro čtení
thread_t r_tail	- pointer na poslední prvek ve frontě vláken zablokovaných
		  na r/w locku čekajících na uvolnění r/w locku pro čtení


Interface

void rwlock_init(rwlock_t *rwl)
	Funkce inicializující r/w lock.
	Všechny proměnné ve struktuře rwlock_t jsou inicializovány na nulu.

void rwlock_destroy(rwlock_t *rwl)
	Funkce používaná pro destrukci r/w locku.
	Protože r/w locky jsou vytvářeny jako statické proměnné a
	nepoužívají žádnou dynamicky alokovanou paměť, funkce
	rwlock_destroy() pouze otestuje, zda je fronta vláken zablokovaných
	na r/w locku při destrukci neprázdná. Pokud tomu tak není, volá se
	(dle zadání) funkce panic().

void rwlock_write_lock(rwlock_t *rwl)
	Funkce zamykající r/w lock pro zápis.
	Při zakázaných přerušeních se porovná, zda vlákno volající funkci
	již daný r/w lock vlastní. Pokud je tomu tak, jedná se o rekurzivní
	volání funkce a zvýší se pouze hodnota rekurzivních přístupů pro
	zápis na daný r/w lock. V opačném případě se zjistí, zda je možné
	získat r/w lock pro zápis (počet čtenářů i zapisovatelů je nulový).
	Pokud ano, zamkne se r/w lock pro zápis a dané vlákno si zvýší
	počet resources, které drží. Jinak se přidá do fronty vláken
	čekajících na daném r/w locku na zápis a zablokuje se.

void rwlock_write_unlock(rwlock_t *rwl)
	Funkce odemykající r/w lock pro zápis.
	Při zakázaných přerušeních se sníží počet rekurzivních přístupů k
	r/w locku pro zápis. Pokud je tento počet snížen na 0, vlákno
	uvolní zámek pro zápis a sníží si počet resources, které drží.
	Dále, pokud je nenulová fronta vláken čekajících na zápis, vzbudí
	1. vlákno z této fronty. Jinak, pokud je nenulová fronta vláken
	čekajících na čtení, vzbudí všechna tato vlákna.

int rwlock_write_try_lock(rwlock_t *rwl)
	Funkce, která zkusí zamknout r/w lock pro zápis.
	Při zakázaných přerušeních se zjistí počet přístupů k r/w locku pro
	zápis i pro čtení. Pokud je alespoň jeden z nich nenulový, funkce
	ihned končí neúspěchem. Jinak se počet přístupů pro zápis zvýší na
	1, volající vlákno si zvýší počet resources, které drží.
	Návratová hodnota: 0 (úspěch, r/w lock se podařilo zamknout),
	-1 (neúspěch).

int rwlock_write_timeout(rwlock_t *rwl, uint msec)
	Funkce, která se po dobu msec pokouší uzamknout r/w lock pro zápis.
	Pokud se jí to v jednotlivých krocích nezdaří a nevypršel ještě
	timeout, vlákno volající funkci se vzdá procesoru.
	Návratová hodnota: 0 (úspěch, r/w lock se podařílo zamknout),
	-1 (neúspěch, doba msec uplynula, r/w lock se nepodařílo zamknout).

void rwlock_read_lock(rwlock_t *rwl)
	Funkce zamykající r/w lock pro čtení.
	Při zakázaných přerušeních se zjistí, zda je možné získat r/w lock
	pro čtení (počet čtenářů je nulový). Pokud ano, zamkne se r/w lock
	pro čtení a dané vlákno si zvýší počet resources, které drží. Jinak
	se přidá do fronty vláken čekajících na daném r/w locku na čtení a
	zablokuje se.

void rwlock_read_unlock(rwlock_t *rwl)
	Funkce odemykající r/w lock pro čtení.
	Při zakázaných přerušeních se sníží počet vláken držících r/w lock
	pro čtení a vlákno si sníží počet resources, které drží. Dále,
	pokud je nenulová fronta vláken čekajících na zápis, vzbudí 1.
	vlákno z této fronty, je-li to možné (počet čtenářů je nulový).
	Jinak, pokud je nenulová fronta vláken čekajících na čtení, vzbudí
	všechna tato vlákna.

int rwlock_read_try_lock(rwlock_t *rwl)
	Funkce, která zkusí zamknout r/w lock pro čtení.
	Při zakázaných přerušeních se zjistí počet přístupů k r/w locku pro
	zápis. Pokud je nenulový, funkce ihned končí neúspěchem. Jinak se
	zvýší počet přístupů k r/w locku pro čtení, volající vlákno si
	zvýší počet resources, které drží.
	Návratová hodnota: 0 (úspěch, r/w lock se podařilo zamknout),
	-1 (neúspěch).

int rwlock_read_timeout(rwlock_t *rwl, uint msec)
	Funkce, která se po dobu msec pokouší uzamknout r/w lock pro čtení.
	Pokud se jí to v jednotlivých krocích nezdaří a nevypršel ještě
	timeout, vlákno volající funkci se vzdá procesoru.
	Návratová hodnota: 0 (úspěch, r/w lock se podařílo zamknout),
	-1 (neúspěch, doba msec uplynula, r/w lock se nepodařílo zamknout).



Modul COND - podmínkové proměnné
Modul je určen pro práci se "standardními" podmínkovými proměnnými.

typedef struct cond {
        thread_t head, tail;
} cond_t;

thread_t head	- pointer na první prvek ve frontě vláken zablokovaných na
		  podmínkové proměnné
thread_t tail	- pointer na poslední prvek ve frontě vláken zablokovaných
		  na podmínkové proměnné


Interface

void cond_init(cond_t *cv)
	Funkce inicializující podmínkovou proměnnou.

void cond_destroy(cond_t *cv)
	Funkce používaná pro destrukci podmínkové proměnné.
	Protože podmínkové proměnné jsou vytvářeny jako statické proměnné a
	nepoužívají žádnou dynamicky alokovanou paměť, funkce
	cond_destroy() pouze otestuje, zda je fronta vláken zablokovaných
	na podmínkové proměnné při destrukci neprázdná. Pokud tomu tak
	není, volá se (dle zadání) funkce panic().

void cond_signal(cond_t *cv)
	Funkce posílající signál na podmínkovou proměnnou.
	Při zakázaných přerušeních se vzbudí 1. prvek z fronty vláken
	zablokovaných na podmínkové proměnné (pokud je tato fronta
	neprázdná).

void cond_broadcast(cond_t *cv)
	Funkce posílající broadcast na podmínkovou proměnnou.
	Při zakázaných přerušeních se vzbudí všechny prvky z fronty vláken
	zablokovaných na podmínkové proměnné (pokud je tato fronta
	neprázdná).

void cond_wait(cond_t *cv, mutex_t *mtx)
	Funkce, která zařídí čekání na podmínkové proměnné.
	Při zakázaných přerušeních funkce atomicky zamkne mutex mtx spojený
	s podmínkovou proměnnou, přidá volající vlákno do fronty vláken
	zablokovaných na podmínkové proměnné a zablokuje se. Až je vlákno
	(někým jiným) probuzeno, odemkne mutex mtx.

int cond_wait_timeout(cond_t *cv, mutex_t *mtx, uint msec)
	Funkce simulující čekání na signál (broadcast) na podmínkové
	proměnné po dobu (maximálně) msec.
	Pokud je hodnota msec rovna 0, funkce ihned skončí (podmínka nemůže
	být změněna). Jinak se při zakázaných přerušeních nejprve atomicky
	zamkne mutex a volající vlákno se přidá do fronty vláken
	zablokovaných na podmínkové proměnné. Zároveň si poznačí čas, kdy k
	tomuto přidání do fronty došlo a uspí se na dobu msec. Až je vlákno
	probuzeno, porovná si dobu, po kterou skutečně spalo, s dobou msec.
	Pokud spalo méně než msec, znamená to, že jej nějaké jiné vlákno
	probudilo voláním buďto cond_signal() nebo cond_broadcast(), tzn.
	čekání proběhlo úspěšně. V opačném případě se vlákno ještě zkusí
	podívat do fronty vláken zablokovaných na podmínkové proměnné.
	Pokud tam sebe samo nenajde, bylo opět probuzeno voláním
	cond_signal() nebo cond_broadcast() a čekání proběhlo úspěšně.
	Pokud se najde, znamená to, že čekání bylo neúspěšné (vypršel
	timeout) a vlákno se z fronty vláken zablokovaných na podmínkové
	proměnné odstraní. Vlákno odemkne mutex.
	Návratová hodnota: 0 (úspěch, vlákno bylo "probuzeno" z fronty
	čekajících před vypršením timeoutu), -1 (neúspěch)