To be done.

To be done.

Zámky alias mutexy jsou jednoduchým prostředkem k synchronizaci na kritické sekci. Zámek má metody lock a unlock se zjevnou funkcí, pouze jeden proces může mít v kterémkoliv okamžiku zamknutý zámek. Implementace jednoduchá, lock otestuje zda je zamčeno, pokud ne tak zamkne, pokud ano tak nechá proces čekat, unlock spustí další čekající proces, pokud nikdo nečeká tak odemkne. Samozřejmě, v implementaci jsou potřeba atomické testy.

Nakreslit implementaci zámku a ukázat, jak je důležitý atomický test, a jak jej lze zajistit buď atomickou instrukcí, nebo zákazem přerušení.

Ukázat příklad, jak lze pomocí mutexu vyřešit nějakou synchronizační úlohu, nejlépe prostě vzájemné vyloučení.

V Linuxu je k dispozici mutex od pthreadů. Je reprezentován datovou strukturou pthread_mutex_t, inicializuje se voláním int pthread_mutex_init (pthread_mutex_t *, pthread_mutexattr_t *), ničí se voláním int pthread_mutex_destroy (pthread_mutex_t *) na odemčeném mutexu, pro práci s ním jsou metody _lock (), _trylock () a _unlock (). Atributy mutexu nastavují co se stane pokud thread zkusí znovu zamknout mutex, který již jednou zamknul, fast mutexy se deadlocknou, error checking mutexy vrátí chybu, recursive mutexy si pamatují kolikrát se zamklo. Podobná situace je při odemykání, fast a recursive mutexy může odemknout každý, u recursive mutexů se testuje vlastník, to je ale na rozdíl od zamykání nepřenositelný detail, zmiňuje se jen aby bylo vidět že existuje také koncept vlastníka zámku.

Když se podíváme na implementaci, pthread_mutex_t je malinká struktura obsahující krom prázdných polí frontu čekajících threadů, stav mutexu, counter rekurzivního zamykání, pointer na vlastníka a typ mutexu. Implementace vlastních operací je pak jednoduchá, sdílení mezi procesy (pokud jej systém umí) se zařizuje pomocí shared memory.

For active waiting, Posix threads library provides spin locks available through the pthread_spinlock_t data structure and pthread_spin_ functions, which are analogical to the mutex functions (except there is no _timedlock variant). Upon initialization, the pshared flag specifies if the spin lock can be used only by threads inside one process, or also by different processes, provided that the spin lock is allocated in a shared memory area.

With mutexes available in user space but threads implemented in kernel space, it is unavoidable that some mutex operations have to call the kernel. It is, however, possible to optimize mutex operations for the case without contention, so that the kernel does not have to be called when no scheduling is needed. Linux makes this optimization possible through its futex interface.

When called with op set to FUTEX_WAIT, the interface suspends the current thread if the value of the futex equals to val. When called with op set to FUTEX_WAKE, the interface wakes at most val threads suspended on the futex.

A simplified example of implementing a mutex using a futex is copied from Drepper.

References. 

Windows NT mají také mutexy, a to hned dvojího druhu. Jedním se říká critical sections, druhým mutexes. Nejprve critical sections:

Critical sections ve Windows NT si pamatují vlastníka, je možné je zamknout jedním threadem několikrát (a tolikrát se musí odemknout). Jsou (víceméně) rychlé, ale nefungují mezi procesy (pochopitelně).

Pro synchronizaci mezi procesy se ve Windows NT používají kernel objekty. Z těch nás momentálně zajímá mutex.

Parametr lpsa určuje security sdělení, nezajímá nás. FInitialOwner říká, zda bude mutex po vytvoření okamžitě zamčený pro volajícího. LpszMutexName umožňuje pojmenovat mutex. Dva procesy mohou sdílet mutex tak, že jej vytvoří pod stejným jménem (případně lze zavolat HANDLE OpenMutex (DWORD fdwAccess, BOOL fInherit, LPTSTR lpszName)). Jinou metodou sdílení (beze jména) je volání BOOL DuplicateHandle (HANDLE hSourceProcess, HANDLE hSource, HANDLE hTargetProcess, LPHANDLE lphTarget, DWORD fdwAccess, BOOL fInherit, DWORD fdwOptions), které umožňuje zduplikovat handle (handle se nedá předat rovnou, je process-specific).

Čeká se pomocí DWORD WaitForSingleObject (object, timeout), vrací OK, TIMEOUT, OWNER_TERMINATED. Také funguje WaitForMultipleObjects, viz výše. Mutexy mají vlastníky a lock count stejně jako critical sections. Odemyká se pomocí BOOL ReleaseMutex (mutex).

Zámků může existovat více verzí, konec konců podobně jako jiných synchronizačních primitiv. Tak se můžete setkat s termíny spin lock pro zámek, který čeká na uvolnění aktivně (termínem spinning se rozumí právě opakované testování přístupu), blocking lock pro zámek, který čeká pasivně, recursive lock pro zámek, který lze zamknout vícekrát stejným threadem, read write lock pro zámek, který má režim zamčení pro čtení a pro zápis, atd. Více zamykání v transakcích.

Implementace odemknutí zámku může být v jednom detailu naprogramovaná dvěma způsoby. Poslední vlastník buď odemkne zámek a rozeběhne některý čekající proces, který zámek znovu zamkne, nebo jej prostě předá zamčený některému čekajícímu procesu. Druhá metoda se sice zdá efektivnější, ale má nepříjemnou vlastnost v situaci, kdy se někdo pokusí zamknout zámek ve chvíli, kdy se jej již vzdal starý vlastník, ale ještě se nerozběhl nový vlastník. V takové situaci skončí pokus o zamčení zablokováním volajícího, což může být pokládáno za špatnou věc (aktivní proces musí čekat na pasivní). Vytváření těchto závislostí mezi procesy se říká convoys.

To implement the Readers And Writers Synchronization Problem, a variant of a lock that distinguishes between readers and writers is typically provided. The lock can be locked by multiple readers, but only by a single writer, and never by both readers and writers.

Read write locks can adopt various strategies to resolve contention between readers and writers. Often, writers take precedence over readers.

Linux provides Read Write Locks as a part of the Posix Threads library.

Windows provide Slim Reader Writer Locks that can be used within a single process.

To be done.

To avoid some of the blocking associated with implementing the Readers And Writers Synchronization Problem using read write locks, the read copy update interface lets readers operate on past copies of data when updates are done. This is achieved by splitting an update into the modification and reclamation phases. In the modification phase, the writer makes the updated copy of data visible to new readers but the past copy of data is retained for existing readers. In between the modification and reclamation phases, the writer waits until all readers of the past copy of data finish. In the reclamation phase, the writer discards the past copy of data. The interface does not deal with writer synchronization.

Linux provides Read Copy Update as a part of the kernel. The rcu_read_lock and rcu_read_unlock functions delimit readers. The synchronize_rcu function synchronizes writers by waiting until there are no active readers. The rcu_assign_pointer and rcu_dereference macros make sure atomicity or ordering does not break synchronization. For simplicity, the interface does not care what data is accessed, all readers are synchronized against all writers.

The interface permits many different implementations. When context switching can be prevented by readers, a straightforward implementation can leave the reader synchronization empty and wait for a context switch on each processor for writer synchronization.

Velmi podobné zámkům jsou semafory, BTW vymyslel je Dijkstra někdy v roce 1965. Semafor má metody signal a wait, často bohužel právě díky Dijkstrovi z holandštiny pojmenované P (passern, projít kolem) a V (vrijgeven, uvolnit), a initial count, který říká, kolik procesů smí současně vlastnit semafor.

Opět stručně nastínit implementaci s atomickou operací a řešení nějakého synchronizačního problému, například producent a konzument.

V Unixech podle System V, a tedy i v Linuxu, jsou semafory poskytovány systémem. Tyto semafory synchronizují procesy s odděleným adresovým prostorem, čemuž odpovídá i jejich interface. Semafor lze vytvořit voláním int semget (key, number, flags), které vrátí sadu semaforů globálně pojmenovanou daným klíčem. Se semafory se pak pracuje voláním int semop (key, ops_data *, ops_number). Každá ze sady operací obsahuje číslo semaforu v sadě, jednu ze tří operací se semaforem, a flagy. Operace je buď přičtení čísla k semaforu, nezajímavé, nebo test semaforu na nulu, čeká se do okamžiku než semafor dosáhne nuly, nebo odečtení čísla od semaforu, čeká se do okamžiku než semafor bude mít dostatečně velkou hodnotu. Z flagů jsou zajímavé IPC_NOWAIT, který říká že se nemá čekat, a SEM_UNDO, který zajišťuje, že operace na semaforu bude vrácena zpět, pokud proces, který jí volal, skončí. Operace se buď udělají všechny nebo žádná. Pak je ještě semctl pro různé dalčí operace.

V Unixu jsou ještě semafory podle POSIX specifikace. Jejich interface je pochopitelně podobný pthread mutexům, inicializují se sem_init, další funkce jsou čekání, pokus o čekání, čtení hodnoty, signalizace, zničení semaforu.

Ve Windows jsou semafory podobně jako mutexy, jen nemají vlastníky a mají reference count.

ReleaseSemaphore se nepovede, pokud by se čítač semaforu zvětšil přes maximum specifikované při jeho vytvoření. Mimochodem není možné zjistit okamžitou hodnotu semaforu bez jeho změny, protože ReleaseSemaphore vyžaduje nenulový cRelease.

Semafory a mutexy vždycky čekají na situace typu uvolnění obsazeného prostředku. Často je potřeba pasivně čekat na složité podmínky, například když nějaký thread zobrazuje stav jiných threadů v GUI a při změně má udělat repaint. Tam se pak hodí například condition variables.

Condition variable má metody wait, signal a broadcast. Pokud proces zavolá wait, začne pasivně čekat. Pokud někdo zavolá signal, vzbudí se jeden z právě čekajících procesů, pokud někdo zavolá broadcast, vzbudí se všechny právě čekající procesy. Využití na pasivní čekání na složité podmínky je pak nasnadě. Proces, který čeká, v cyklu střídá wait s testováním podmínky, kdokoliv pak může ovlivnit vyhodnocení podmínky dělá signal či broadcast. Jen jedno drobné zdokonalení, protože test podmínky musí být atomický, condition variable je svázána s mutexem, který chrání testovanou podmínku.

Implementace condition variable, nastínění použití uvnitř while.

Samozřejmě, operace condition variables je třeba používat s rozmyslem. Jednak je třeba mít na paměti, že u condition variable se signal před broadcast nezapočítá, na rozdíl od zámků a semaforů. Dvak, když se udělá broadcast, může dojít ke spuštění zbytečně velkého počtu procesů naráz.

V pthread library condition variables samozřejmě jsou. Vytvářejí se int pthread_cond_init (pthread_cond_t *, pthread_condattr_t *), další metody jsou _signal (), _broadcast (), _wait (), _timedwait (timeout) a _destroy (). Zřejmě není co dodat.

Úplně stranou, podobný mechanismus je možné najít třeba v Javě, kde thread může zavolat metodu wait na libovolném objektu, jiné thready ho pak pomocí notify nebo notifyAll mohou vzbudit. Podobně jako u klasických condition variables, i tady je možné tyto metody volat pouze pokud je příslušný objekt zamčen.

Mimochodem, condition variables jdou napsat dvěma způsoby, u jednoho po signal běží dál signaller, u druhého běží jeden z čekajících procesů. První způsob se občas také nazývá Mesa Semantics, druhý Hoare Semantics.

Windows provide Condition Variables that can be used within a single process.

Windows events. Parametry jako obvykle, fManualReset říká, zda je event potřeba explicitně shazovat. čeká se také stejně (pomocí WaitForXxx), ale signalizuje se jinak. BOOL SetEvent (HANDLE hEvent) ohlásí event, u non manual reset events se po rozběhnutí jednoho čekajícího threadu event zase shodí. BOOL ResetEvent (HANDLE hEvent) shodí manual reset event. BOOL PulseEvent (HANDLE hEvent) nahodí manual reset event, počká až se rozběhnou všichni kdo na ní čekají a závěrem jí shodí.

PulseEvent údajně občas nemusí fungovat a jeho používání se nedoporučuje.

Monitor dovoluje omezit paralelní přístup k objektu v programovacím jazyce, vymyslel ho pan Hoare v roce 1974 a najdete ho například v Concurrent Pascalu, Module, Javě.

Zřejmě nejjednodušší bude demonstrovat monitory právě na Javě. Ta má klíčové slovo synchronized, které lze uvést u metod objektu. Pokud je nějaká metoda takto označena, před jejím vykonáním se zamkne zámek spojený s jejím objektem, čímž je zajištěna synchronizace. Mimochodem Java nabízí také synchronizaci bloku kódu na explicitně uvedeném objektu, to je původem mírně starší koncept, který v podstatě dovoluje označit v kódu kritické sekce.

Pro případy, kdy je potřeba čekat na něco právě uvnitř monitoru, se k němu doplňují extra funkce. Jedno z možných provedení doplňuje funkce delay (queue) pro umístění procesu do fronty a continue (queue) pro vzbuzení jednoho procesu z fronty.

Note that spurious wake up in monitor wait is typically possible.

Poněkud méně známý synchronizační prostředek dovoluje zapsat před blok kódu podmínku, která musí být splněna, než se daný blok kódu začne vykonávat. Tím je v podstatě dosaženo podobné funkce jako u klasického použití condition variables., až na to, že nikdo nesignalizuje okamžik, kdy se má znovu otestovat podmínka. Což je také důvod, proč obecné guards téméř nikde nejsou k dispozici (okamžik otestování podmínky je těžké určit). Takže se dělají guards, které mají okamžiky otestování podmínky omezené na události jako je volání metody apod.

Příkladem takového guardu může být select a rendez vous v Adě. Ten se zapisuje pomocí příkazů select a accept, které jinak vypadají jako case a deklarace procedury:

Funkce je přímočará, select nejprve vyhodnotí všechny podmínky, pokud je u nějaké splněné podmínky k dispozici rendez vous, provede se, jinak se provede náhodně větev nějaké splněné podmínky nebo větev else, pokud není splněná žádná podmínka tak se hodí výjimka. Accept čeká dokud jej někdo nezavolá.