[ Pobierz całość w formacie PDF ]

Synchronizacja na wieloprocesorze
" Problem zagubionej pobudki (lost wakeup problem)
" Problem wygłodniałego stada (thundering herd problem)
" Zakleszczenia
We wczesnych implementacjach UNIX-a synchronizacja na wieloproceso-
rach była oparta prawie wyłącznie na semaforach Dijkstry (semaforach
zliczających). Mogą one być wykorzystywane do realizacji wzajemnego wy-
kluczania i do oczekiwania na zdarzenie.
Dostępne mechanizmy synchronizacji:
" blokady wirujące
" zmienne warunkowe
" blokady typu czytelnicy-pisarze
" liczniki odwołań
Zakleszczenia 159
Zakleszczenia (deadlocks, deadly embraces)
Zbiór procesów jest w stanie zakleszczenia, kiedy każdy z procesów ze
zbioru czeka na zdarzenie, które może spowodować inny z procesów.
Zakleszczenie zdarza się, gdy każdy z procesów otrzymał wyłączne prawo
do używania jakiegoś zasobu i dodatkowo żąda dostępu do zasobu już
zajętego.
Przykłady:
" Proces A otrzymuje dostęp do drukarki, a proces B do dysku, a na-
stępnie proces A żąda dostępu do dysku, a proces B do drukarki.
" Proces A otrzymał prawo dostępu do dwóch (lub więcej) rekordów bazy
danych, na których operacje mają być przeprowadzane w tym samym
czasie przez proces B.
Zakleszczenia 160
Zakleszczenia (cd)
Jak unikać zakleszczeń?
1. Jeśli to tylko możliwe, to należy unikać stosowania blokad (zamiast
blokad można stosować operacje atomowe lub używać struktur danych
nie wymagających zakładania blokad).
2. Jeśli blokada jest niezbędna, to należy stosować blokadę pojedynczą.
3. Jeśli potrzebnych jest kilka blokad, to należy zdefiniować (małą) lokalną
hierarchię blokad lub zastosować blokowanie stochastyczne.
Zakleszczenia 161
Synchronizacja wątków wg Linuksa
pojęcie proste ochrona ograniczenia
maskowanie przerwań współbieżność przerwań
blokady pętlowe współbieżność CPU tylko dla maszyn SMP
semafory współbieżność CPU nie dla obsługi przerwań
operacje atomowe współbieżność CPU i przerwań tylko proste operacje
Zakleszczenia 162
Synchronizacja wątków wg Linuksa (cd)
Operacje atomowe i przerwania:
xchg(ptr,new); /* exchange value */
cmpxchg(ptr,old,new); /* compare & exchange value */
atomic set(c,i); /* set counter to i */
atomic dec(c); /* substract i from the counter */
atomic add(i,c); /* add i to the counter */
set bit(nr,set); /* set bit nr in set */
change bit(nr,set); /* toggle bit nr in set */
local irq disable(); /* disable interrupts */
local irq enable(); /* enable interrupts */
local bh disable(); /* disable software interrupts */
local bh enable(); /* enable software interrupts */
Zakleszczenia 163
Synchronizacja wątków wg Linuksa (cd)
Semafory:
struct semaphore;
down(sem); /* aquire semaphore */
up(sem); /* release semaphore */
down trylock(sem); /* aquire semaphore, if possible */
struct rw semaphore;
down read(sem); /* aquire read semaphore */
up read(sem); /* release read semaphore */
down write(sem); /* aquire write semaphore */
up write(sem); /* release write semaphore */
Zakleszczenia 164
Synchronizacja wątków wg Linuksa (cd)
Blokady wirujące:
struct spinlock t; /* platform-specific spinlock type */
spin lock(l); /* aquire spinlock l */
spin unlock(l); /* release spinlock l */
spin is locked(l) /* return true if l is locked */
spin trylock(l); /* aquire lock if uncontended, true if successful */
struct rw lock t; /* platform-specific read/write lock type */
read lock(rw); /* aquire read lock on rw */
read unlock(rw); /* release read lock on rw */
write lock(rw); /* aquire write lock on rw */
write unlock(rw); /* release write lock on rw */
Klasyczne problemy IPC 165
Klasyczne problemy komunikacji międzyprocesowej:
" problem ucztujących filozofów  modelowania procesów, które współza-
wodniczą w dostępie do ograniczonych zasobów, np. urządzeń wej-wyj
" problem pisarzy i czytelników  zagadnienie zapewnienia prawidłowego
dostępu do bazy danych (w trybie odczytu i zapisu)
" problem śpiącego fryzjera
komunikacja międzyprocesowa  IPC, InterProcess Communication
Klasyczne problemy IPC 166
Problem śpiącego fryzjera (rozwiązanie z trzema semaforami)
# include   prototypes.h 
#define CHAIRS 5 /* # of chairs for waiting customers */
typdef int semaphore; /* semaphores are a special kind of int */
semaphore customers = 0; /* # of customers waiting for service */
semaphore barbers = 0; /* # of barbers waiting for customers */
semaphore mutex = 1; /* controles access to critical section */
int waiting = 0; /* # of customers waiting */
void Barber(void)
{
while (TRUE) {
down (customers); /* go to sleep if # of customers is 0 */
down(&mutex); /* aquire to waiting */
waiting = waiting - 1; /* decrement count of waiting customers */
up(barbers); /* one barber is ready to cut hair */
up(&mutex); /* release  waiting */
cut_hair(); /* cut hair (outside critical region) */
}
}
Klasyczne problemy IPC 167
Problem śpiącego fryzjera (cd)
void Customer(void)
{
down(&mutex); /* enter critical region */
if (waiting
waiting = waiting +1; /* increment count of waiting customers */
up(customers); /* wake up barber if necessary */
up(&mutex); /* release access to  waiting */ [ Pobierz całość w formacie PDF ]