Teorija
Utrka i kritični odsječak
Raspoređivač može prekinuti dretvu između bilo koje dvije atomic instruction (atomarna instrukcija), pa se koraci dretvi isprepleću: interleaving (preplitanje). Ako rezultat ovisi o preplitanju, to je race condition (utrka): x = x + 1 (load, add, store) u dvije dretve daje x = 1 u 18 od 20 preplitanja, a echo ispiše „yy”. Kod koji dira zajedničke podatke je critical section (kritični odsječak). U njemu smije biti najviše jedna dretva, što je mutual exclusion (međusobno isključivanje), a rješenje ne smije uzrokovati deadlock (potpuni zastoj) ni starvation (izgladnjivanje). Vidi i Dretve.
Race condition and critical section
The scheduler can interrupt a thread between any two atomic instructions, so the steps of the threads interleave. If the result depends on the interleaving, that is a race condition: x = x + 1 (load, add, store) in two threads gives x = 1 in 18 of the 20 interleavings, and echo prints “yy”. Code that touches shared data is a critical section. At most one thread may be in it, which is mutual exclusion, and the solution must cause neither deadlock nor starvation. See also Threads.
Programski pristupi: pokušaji 1–4, Dekker i Peterson
Pokušaji 1–4 koriste busy waiting (radno čekanje). Pokušaj 1 (turn) nameće strogu izmjenu: kad jedna dretva završi, druga zauvijek vrti, što provjeravač zove trap (bezizlazno stanje). Pokušaj 2 provjeri tuđu zastavicu prije postavljanja svoje i krši međusobno isključivanje; pokušaj 3 može zaglaviti obje dretve; u pokušaju 4 dretve se u istom ritmu stalno povlače: livelock (živa blokada). Dekker i Peterson dodaju turn, koji odlučuje tko se povlači, i prolaze sve presude. To vrijedi uz sequential consistency (sekvencijalna konzistentnost); stvarni procesori trebaju memory fence (memorijska ograda).
Software approaches: attempts 1–4, Dekker and Peterson
Attempts 1–4 use busy waiting. Attempt 1 (turn) enforces strict alternation: when one thread finishes, the other spins forever, which the checker calls a trap. Attempt 2 checks the other thread's flag before setting its own and violates mutual exclusion; attempt 3 can get both threads stuck; in attempt 4 the threads keep backing off in lockstep: livelock. Dekker and Peterson add turn, which decides who backs off, and pass every verdict. This holds under sequential consistency; real processors need a memory fence.
Hardverska podrška
Na jednom procesoru dretva može onemogućiti prekide oko kritičnog odsječka (vidi Prekidi), ali to ne radi na više procesora. Zato postoje atomarne instrukcije: Stallingsove compare_and_swap i exchange te Tanenbaumova TSL (Test and Set Lock) čitaju i pišu riječ u jednom nedjeljivom koraku. Međusobno isključivanje tada vrijedi, ali dretve čekaju radno, a izbor dretve koja uđe je proizvoljan, pa neka može gladovati. Uz prioritete je moguć i potpuni zastoj (vidi Raspoređivanje).
Hardware support
On a uniprocessor a thread can disable interrupts around its critical section (see Interrupts), but this does not work on a multiprocessor. That is why there are atomic instructions: Stallings's compare_and_swap and exchange and Tanenbaum's TSL (Test and Set Lock) read and write a word in one indivisible step. Mutual exclusion then holds, but the threads busy-wait, and the choice of the thread that enters is arbitrary, so a thread can starve. With priorities, deadlock is possible too (see Scheduling).
Semafori i proizvođač–potrošač
Semaphore (semafor) je brojač s operacijama semWait (umanji; ispod 0 blokiraj) i semSignal (uvećaj; probudi jednu dretvu). Strong semaphore (jaki semafor) budi redom čekanja, weak semaphore (slabi semafor) bilo koju; binary semaphore (binarni semafor) ima vrijednosti 0 i 1, a mutex otključava samo dretva koja ga je zaključala. U problemu producer–consumer (proizvođač–potrošač) sl. 5.12 griješi (tablica 5.4: n padne na −1), a sl. 5.13 to popravlja. Bounded buffer (ograničeni međuspremnik, sl. 5.16) treba tri semafora; zamijeni li potrošač semWait(n) i semWait(s), nastaje potpuni zastoj (vidi Potpuni zastoj).
Semaphores and producer/consumer
A semaphore is a counter with the operations semWait (decrement; below 0, block) and semSignal (increment; wake one thread). A strong semaphore wakes threads in the order they waited, a weak semaphore any of them; a binary semaphore takes only the values 0 and 1, and a mutex can be unlocked only by the thread that locked it. In the producer/consumer problem, Fig. 5.12 is wrong (Table 5.4: n drops to −1), and Fig. 5.13 corrects it. The bounded buffer (Fig. 5.16) needs three semaphores; if the consumer swaps semWait(n) and semWait(s), a deadlock follows (see Deadlock).
Monitori: Hoare i Mesa
Monitor pušta unutra najviše jednu dretvu; uvjet se čeka na condition variable (uvjetna varijabla) operacijom cwait, koja oslobađa monitor. Kod Hoarea csignal odmah predaje monitor probuđenoj dretvi, a signalizator čeka u urgent queue (hitni red), koji ima prednost pred ulaznim; uvjet zato vrijedi i if je dovoljan. Kod Mese cnotify samo premješta čekača u ulazni red, pa ga druga dretva može pretići: s if potrošač uzme iz praznog međuspremnika, s while ponovno provjeri uvjet.
Monitors: Hoare and Mesa
A monitor lets in at most one thread; a thread waits for a condition on a condition variable with cwait, which releases the monitor. With Hoare monitors, csignal hands the monitor at once to the woken thread, and the signaling thread waits in the urgent queue, which has priority over the entry queue; the condition therefore still holds, and if is enough. With Mesa monitors, cnotify only moves the waiter to the entry queue, so another thread can get in first: with if the consumer takes from an empty buffer, with while it checks the condition again.
Čitatelji–pisači i provjeravač
U problemu readers–writers (čitatelji–pisači) čitatelji smiju čitati zajedno, a pisač piše sam. Uz prednost čitatelja pisač može gladovati; uz prednost pisača (sl. 5.26, tablica 5.6) gladovati mogu čitatelji. State-space checker (provjeravač prostora stanja) istražuje svako preplitanje i za prekršenu presudu daje najkraći counterexample (protuprimjer), koji se učitava kao skripta. Živa blokada je ciklus bez napretka (ulaska u kritični odsječak) iz kojeg se napredak još može dosegnuti, a izgladnjivanje ciklus u kojem druge dretve napreduju, a jedna ne. Ciklus se broji samo ako u njemu korak napravi svaka spremna dretva.
Readers/writers and the checker
In the readers/writers problem, readers may read at the same time, but a writer writes alone. When readers have priority, a writer can starve; when writers have priority (Fig. 5.26, Table 5.6), readers can starve. The state-space checker explores every interleaving and, for each verdict that fails, gives the shortest counterexample, which is loaded as a script. A livelock is a cycle without progress (no thread enters a critical section) from which progress can still be reached, and starvation is a cycle in which other threads make progress but one thread does not. A cycle counts only if every ready thread takes a step in it.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 5 (odjeljci 5.1–5.5 i 5.7, dodatak A.1); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 2 (4. izd. odjeljci 2.3.1–2.3.7 i 2.5.2; 5. izd. odjeljci 2.4.1–2.4.7).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 5 (sec. 5.1–5.5 and 5.7, Appendix A.1); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 2 (4th ed. sec. 2.3.1–2.3.7 and 2.5.2; 5th ed. sec. 2.4.1–2.4.7).