Systemy Operacyjne – semestr drugi

Wyk a

ł d ósmy

r

Ś odki synchronizacji w Linuksie

1.

Operacje niepodzielne na liczbach ca k

ł owitych i na bitach

Operacje niepodzielne (atomowe) na zmiennych prostych typów są zazwyczaj realizowane za pomocą instrukcji maszynowych w a ł

c

ś iwych dla architektury procesora.

Listy rozkazów niektórych procesorów zawierają rozkazy, które pozwalają wprost wykonać niepodzielnie takie instrukcje jak np.: dodawanie, mno en ż

ie, odczyt, zapis,

inne dostarczają rozkazów ułatwiających implementację takich operacji w systemach wieloprocesorowych (np. rozkaz blokowania magistrali), jeszcze inne nie posiadają a

ż dnych rozkazów tego typu (np. SPARC). Jądro systemu Linux udostępnia szereg interfejsów (funkcji) korzystających z tych rozkazów lub pozwalających w inny sposób zrealizować operacje niepodzielne na typach prostych. Twórcy jądra wyró n ż ili specjalny typ atomic_t, który stosowany jest w miejsce zwyk eg ł

o typu „int”.

Pozwala to na zdefiniowanie funkcji, które pracują tylko na takim typie, ukrycie szczegółów implementacji oraz zabezpieczenie przed błędną optymalizacją na poziomie kompilacji. Typ atomic_t, mimo, e

ż zbudowanym jest na typie „int” (32 – bitowym) pozwala na przechowywanie warto c ś i 24-bitowych (3 bajty). Młodsze 8 bitów (1 bajt)

zajmowane jest przez blokadę, co jest konieczno c

ś ią w przypadku takich architektur jak wspomniany wy ej

ż SPARC. Funkcje realizuj c

ą e operacje niepodzielne na

liczbach ca k

ł owitych są implementowane jako makrodefinicje lub funkcje „inline”. Oto te funkcje:

ATOMIC_INIT(int i) – pozwala na inicjalizację zmiennej typu atomic_t w miejscu deklaracji,

int atomic_read(atomic_t *v) – niepodzielny odczyt całkowitej warto c

ś i „v”,

void atomic_set(atomic_t *v, int i) – niepodzielne przypisanie warto c

ś i „i” do „v”,

void atomic_add(int i, atomic_t *v) – niepodzielne dodanie warto c

ś i „i” do „v”,

void atomic_sub(int i, atomic_t *v) – niepodzielne odejmowanie warto c

ś i „i” od „v”,

void atomic_inc(atomic_t *v) – niepodzielna inkrementacja „v”,

void atomic_dec(atomic_t *v) – niepodzielna dekrementacja „v”,

int atomic_sub_and_test(int i, atomic_t *v) – niepodzielne odjęcie „i” od „v” i zwrócenie warto c ś i „true”, je l

ś i ró n

ż ica wynosi „0”,

int atomic_add_negative(int i, atomic_t *v) – niepodzielne dodanie „i” do „v” i zwrócenie warto c ś i „true”, je l

ś i suma jest ujemna,

int atomic_dec_and_test(atomic_t *v) – niepodzielna dekrementacja „v” i zwrócenie warto c ś i „true” je l

ś i po tej operacji „v” będzie miała wartoś

ć „0”,

int atomic_inc_and_test(atomic_t *v) – niepodzielna inkrementacja „v” i zwrócenie warto c ś i „true” je l

ś i po tej operacji „v” b d

ę zie miała wartość „0”.

Oprócz operacji niepodzielnych na liczbach ca k

ł owitych j d

ą ro dostarcza funkcji realizuj c

ą ych niepodzielne operacje na pojedynczych bitach. Nie dzia a

ł ją one na a

ż dnym

konkretnym typie, tylko pobierają przez parametry adres miejsca w pamięci i numer bitu:

void set_bit(int nr, void *addr) – niepodzielne ustawienie bitu okre l

ś onego przez „nr” zmiennej o adresie „addr”,

void clear_bit(int nr, void *addr) – niepodzielne wyzerowanie bitu okre l

ś onego przez „nr” zmiennej o adresie „addr”,

int test_and_set_bit(int nr, void *addr) – niepodzielne ustawienie bitu określonego przez „nr” zmiennej o adresie „addr”, wraz ze zwróceniem jego poprzedniej warto c

ś i,

int test_and_clear_bit(int nr, void *addr) – niepodzielne wyzerowanie bitu określonego przez „nr” zmiennej o adresie „addr”, wraz ze zwróceniem jego poprzedniej warto c

ś i,

int test_and_change_bit(int nr, void *addr) – niepodzielna negacja bitu okre l ś onego przez „nr” zmiennej o adresie „addr”, wraz ze zwróceniem jego poprzedniej warto c

ś i,

int test_bit(int nr, void *addr) – niepodzielne testowanie bitu okre l

ś onego przez „nr” zmiennej o adresie „addr”.

Istnieją oczywi c

ś ie odpowiedniki tych funkcji realizujące takie same operacje, ale nie w sposób niepodzielny. Nazwy tych funkcji są takie same, z tym, e ż rozpoczynają

si

ę znakami „__” (podwójnego podkre l

ś enia). Jądro dostarcza również funkcji pozwalających na znalezienie pierwszego ustawionego bitu w określonym obszarze pami c ę i

i pierwszego bitu o wartości zero w okre l

ś onym obszarze pami c

ę i: find_first_bit() i find_first_zero_bit(). Je l

ś i chcemy przeszukać tylko jedno słowo mo em

ż

y skorzystać

z szybszych wywołań __ffs() i __ffz().

2.

Rygle pętlowe

Najcz

c

ęś iej stosowanym rodzajem blokady są rygle p t

ę lowe (ang. spin lock), które chronią „większe” zasoby (takie jak np. listy zadań) niż zmienne typów całkowitych lub poszczególne bity s ów

ł

w pami c

ę i operacyjnej. Dany rygiel mo e

ż przetrzymywać tylko jeden wątek wykonania (zasada wzajemnego wykluczania), natomiast inne wątki chc c

ą e skorzystać z chronionego zasobu wykonują aktywne oczekiwanie, czyli w pętli oczekują, aż rygiel zostanie zwolniony i jeden z nich będzie mógł uzyskać dostęp do zasobu. Ponieważ aktywne oczekiwanie jest marnotrawieniem czasu procesora rygle pętlowe powinny być stosowane wszędzie tam, gdzie nie mo n ż a zawiesić

wątku i gdzie czas przełączania kontekstu by b

ł y niewspółmiernie dłuższy z czasem aktywnego oczekiwania. Rygle pętlowe mogą być u y ż wane w procedurach obsługi

przerwa ,

ń ale tylko wraz z wyłączeniem lokalnego systemu przerwa ,

ń aby uniknąć zakleszcze .

ń Nale y

ż również pamięta ,

ć e

ż rygle nie są rekurencyjne i nie są

stosowane w systemach jednoprocesorowych (kompilator wstawia w ich miejsce puste instrukcje lub je l ś i podczas kompilacji włączona jest opcja wywłaszczania jądra

zastępuje je funkcjami wł c

ą zającymi i wyłączającymi wywłaszczanie jądra, opisanymi ni ej

ż ). Jądro udostępnia szereg funkcji zwi z

ą anych z obsługą rygli p t

ę lowych:

1

Systemy Operacyjne – semestr drugi

spin_lock() - zak a

ł da zadany rygiel,

spin_lock_irq() - wyłącza lokalne przerwania i zak a

ł da rygiel,

spin_lock_irqsave() - zachowuje stan lokalnych przerwa ,

ń wyłącza je i zakłada rygiel,

spin_lock_bh() - zak a

ł da rygiel i wyłącza dolne połówki,

spin_unlock() - zwalnia rygiel,

spin_unlock_irq() - wł c

ą za przerwania i zwalnia rygiel,

spin_unlock_irqrestore() - przywraca stan przerwań i zwalnia rygiel,

spin_unlock_bh() - zwalnia rygiel i włącza dolne połówki,

spin_trylock() - próbuje zało y

ż ć rygiel, je l

ś i operacja ta si

ę nie powiedzie zwraca zero i nie powoduje wej c

ś ia w pętlę aktywnego oczekiwania,

spin_is_locked() - zwraca wartość różną od zera, je l

ś i rygiel jest już przetrzymywany,

spin_lock_init() - inicjalizuje rygiel (zmienna typu spinlock_t) tworzony w sposób dynamiczny.

Jeśli problem, który chcemy rozwiązać sprowadza si

ę do problemu pisarzy i czytelników, a c

ś i l

ś ej do wersji tego problemu, gdzie faworyzowani są czytelnicy, to mo em

ż

y

zastosować rygle p t

ę lowe R-W. Rygiel dla czytelników mo e

ż być przetrzymywany przez większą liczbę wątków wykonania tego typu (a nawet mo e ż być rekurencyjnie

zakładany przez jeden w t

ą ek wykonania tego typu), rygiel dla pisarzy – tylko przez jeden wątek wykonania tego typu. Ponadto pisarz mo e ż zakładać rygiel tylko wtedy,

gdy z zasobu nie korzysta a

ż den z czytelników. Również w przypadku rygli R-W istnieje w jądrze szereg funkcji pozwalających na manipulację nimi:

read_lock() - zakłada rygiel R (dla czytelnika),

read_lock_irq() - zakłada rygiel R (dla czytelnika) i wyłącza lokalne przerwania,

read_lock_irqsave() - zak a

ł da rygiel R, zapamiętuje stan lokalnych przerwań i wyłącza je,

read_lock_bh() - zakłada rygiel R (dla czytelnika) i wyłącza dolne połówki,

read_ulock() - zdejmuje rygiel R,

read_ulock_irq() - zdejmuje rygiel R i włącza lokalne przerwania,

read_ulock_irqrestore() - zdejmuje rygiel R i przywraca stan lokalnych przerwań,

read_unlock_bh() - zdejmuje rygiel R (dla czytelnika) i włącza dolne połówki,

write_lock() - zakłada rygiel W (dla pisarza),

write_lock_irq() - zakłada rygiel W (dla pisarza) i wyłącza lokalne przerwania,

write_lock_irqsave() - zakłada rygiel W, zapami t

ę uje stan loklanych przerwań i wyłącza je,

write_lock_bh() - zakłada rygiel W (dla pisarza) i wyłącza dolne połówki,

write_ulock() - zdejmuje rygiel W,

write_ulock_irq() - zdejmuje rygiel W i włącza lokalne przerwania,

write_ulock_irqrestore() - zdejmuje rygiel W i przywraca stan lokalnych przerwa , ń

write_ulock_bh() - zdejmuje rygiel W i włącza dolne po ów

ł

ki,

write_trylock() - próbuje zało y

ż ć rygiel W, w przypadku niepowodzenia, zwraca wartość równą zero, ale nie powoduje rozpocz c ę ia p t

ę li aktywnego

oczekiwania,

rw_lock_init() - inicjalizuje strukturę typu rwlock_t,

rw_is_locked() - je l

ś i rygiel jest przetrzymywany, to zwraca wartoś

ć ró n

ż ą od zera.

2

Systemy Operacyjne – semestr drugi

3.

Semafory

Semafory w przeciwieństwie do rygli pętlowych powodują wprowadzenie wątków wykonania oczekuj c ą ych na ich podniesienie w stan zawieszenia. Takie w t

ą ki

wstawiane są do kolejki zadań oczekujących (ang. waitqueue). Semafory nie mogą być przetrzymywane przez wątki, które już przetrzymują rygle pętlowe. Powy s ż ze

cech powodują, że semafory są używane tylko w kontek c

ś ie procesu, kiedy czas oczekiwania na ich podniesienie jest du o

ż dłu s

ż zy niż czas przeł c

ą zania kontekstu.

Semafory nie powodują, tak jak rygle p t

ę lowe wył c

ą zenia wywłaszczania jądra, ponadto umo l

ż iwiają przetrzymywanie blokady przez dowolną, z góry okre l

ś oną przez

licznik semafora liczbę wątków. Semafory binarne, pozwalaj c

ą e na przetrzymywanie blokady tylko przez jeden w t

ą ek nazywane są muteksami. Oto funkcje związane

z obsługą semaforów:

sema_init(sturct semaphore *, int) – inicjalizuje dynamicznie utworzoną struktur ę semafora podaną warto c

ś ią,

init_MUTEX(struct semaphore *) - inicjalizuje dynamicznie utworzoną strukturę muteksa,

init_MUTEX_LOCKED(struct semaphore *) - inicjalizuje dynamicznie utworzoną strukturę muteksa warto c ś ią „0” (zablokowany),

down_interruptible(struct semaphore *) - próbuje opu c

ś i

ć semafor, je l

ś i to się nie udaje to wprowadza wątek wykonania w stan TASK_INTERRUPTIBLE,

down(struct semaphore *) - podobnie jak wy ej

ż , ale wątek roboczy jest wprowadzany w stan TASK_UNINTERRUPTIBLE,

down_trylock(struct semaphore *) - próbuje opu c

ś i

ć semafor, je l

ś i nie jest to mo l

ż iwe zwraca wartoś

ć niezerową i nie zawiesza zadania,

up(struct semaphore *) - podnosi semafor i budzi jeden z wątków roboczych czekających na jego podniesienie.

Semafory reprezentowane są przez strukturę o nazwie „semaphore”. Statycznie semafory mo n ż a inicjalizować za pomocą DECLARE_SEMAPHORE_GENERIC

i DECLARE_MUTEX. Podobnie jak w przypadku rygli istnieją semafory R-W. Inicjalizuje się je statycznie przy pomocy DECLARE_RWSEM, a dynamicznie przy pomocy init_rwsem(). Funkcje obsługi działają podobnie jak w przypadku zwykłych semaforów, ale są podzielone na przeznaczone dla czytelników (nazwy zako c ń zone

słowem read) i pisarzy (write). Nale y

ż pami t

ę ać, e

ż funkcje down_read_trylock() i down_write_trylock() zwracają warto c ś i o znaczeniu odwrotnym niż funkcja

down_trylock(). Ponadto dla tych semaforów istnieje unikatowa funkcja downgrade_writer() pozwalaj c ą a przekształcić producenta do roli konsumenta.

4.

Zmienne sygnałowe (ang. completion)

Zmienne sygnałowe s u

ł żą do synchronizacji pracy zadań i są uproszczoną wersją semaforów. Ich typ jest okre l ś ony strukturą struct completion. Najczęściej tworzone są

jako dynamiczne składowe wi k

ę szych struktur danych. Mogą być definiowane statycznie przy pomocy DECLARE_COMPLETION(mr_comp). Z obsługą tych zmiennych związane są następujące funkcje:

init_completion(struct completion *) - inicjalizuje zmienną sygnałową utworzoną dynamicznie,

wait_for_completion(struct completion *) - oczekuje na sygnał ze zmiennej sygnałowej,

complete(struct completion *) - pobudza zadania oczekujące na sygnał.

5.

Blokada BKL (ang. Big Kernel Lock)

Blokada ta była pomocna w przej c

ś iu z jądra 2.0 do 2.2. W jądrze 2.0 implementacja SMP pozwala a

ł na przebywanie w trybie jądra tylko jednemu procesorowi, w 2.2

mo l

ż iwe by o

ł współbie n

ż e wykonywanie kodu j d

ą ra na wielu procesorach jednocze n

ś ie. BKL miała być rozwiązaniem przej c

ś iowym, które miało być zastąpione

blokadami o mniejszej ziarnistości. Niestety, również obecnie wiele mechanizmów jądra korzysta z tego rozwi z ą ania. Blokada umo l

ż iwia zawieszenie zadania które ją

przetrzymuje. Na czas usuni c

ę ia tego zadania z kolejki zadań gotowych ta blokada jest odblokowywana i przywracana kiedy to zadanie wróci do wspomnianej kolejki.

Ponadto BKL jest rekurencyjna, wyłącza wywłaszczanie jądra i mo n

ż a wykorzystywać ją jedynie w kontek c

ś ie procesu. W chwili obecnej nie zaleca się jej stosowania,

ale w j d

ą rze nadal są obecne funkcje ją obs u

ł gujące:

lock_kernel() - zak a

ł da blokadę BKL,

unlock_kernel() - zdejmuje blokadę BKL,

kernel_locked() - sprawdza, czy blokada BKL jest ju

ż za o

ł

on

ż

a.

6.

Blokady sekwencyjne (ang. seq locks)

Blokady sekwencyjne (zmienne typu seqlock_t) korzystają z licznika sekwencyjnego, który jest inkrementowany kiedy blokada jest zakładana, a dzieje się to wówczas, gdy chroniony zasób jest zapisywany. Blokady sekwencyjne w prosty sposób pozwalają okre l ś ić czy operacja odczytu nie została przepleciona z operacją zapisu. Przed odczytem jest zapamiętywana wartość licznika. Po wykonaniu tej operacji odczytywany jest ponownie licznik i jego wartość porównywana jest z warto c ś ią poprzednią.

Jeśli są takie same to można być pewnym, że nie rozpocz a

ęł się w trakcie odczytu a

ż dna operacja zapisu. Dodatkowo je l

ś i te warto c

ś i są równe i parzyste, to wiadomo,

e

ż odczyt nie został zak óc

ł ony przez zapis. Do zakładania blokady sekwencyjnej s u

ł

y

ż funkcja wirte_seqlock(), a do zdejmowania write_sequnlock(). Do odczytu warto c ś i

pocz t

ą kowej read_seqbegin(), a do odczytu warto c

ś i końcowej read_seqretry(). Obie te funkcje są wywo y

ł wane w pętli „do” ... „while” . Blokady te są używane do rozwiązywania problemów typu pisarze i czytelnicy, gdzie faworyzowani są pisarze.

7.

Blokowanie wyw a

ł szczania

W przypadkach gdy trzeba chronić dane, które są widziane przez jeden procesor przed dostępem współbie n ż ym mo n

ż a zrezygnować z rygli p t

ę lowych i zastosować

zwykłe zablokowanie wywłaszczania. Do tego służą funkcje preempt_disable() i preempt_enable(), które mo n ż a wielokrotnie zagnie d

ż

a

ż ć. Wartość licznika wywłaszcze ,

ń

który jest inkrementowany za ka d

ż ym wywo a

ł niem pierwszej z tych funkcji i dekrementowany z ka d

ż ym wywo a

ł niem drugiej, jest zwracana przez preempt_count().

Licznik ten jest polem o nazwie preempt_count umieszczonym w strukturze thread_info, a więc wła c ś iwym ka d

ż emu z w t

ą ków wykonania z osobna. Funkcja

3

Systemy Operacyjne – semestr drugi

preempt_enable_no_resched() włącza wywłaszczanie j d

ą ra, ale nie powoduje przeszeregowania zada .

ń Zablokowania wywłaszczania jądra w systemach

wieloprocesorwoych mo n

ż a te

ż dokonać przy pomocy get_cpu() i put_cpu(). Pierwsza z tych funkcji zwraca numer procesora, na którym jest wywoływana.

8.

Bariery

Bariery są konstrukcjami, które powstrzymują kompilator i procesor przed zmianą kolejno c ś i operacji odczytu i zapisu. Wykaz barier pamięciowych i kompilatora jest następujący:

rmb() - zapobiega zmianie kolejności odczytów wokół niej,

read_barrier_depends() - zapobiega zmianie kolejności odczytów zale n

ż ych wokół niej,

wmb() - zapobiega zmianie kolejności zapisów wokół niej,

write_barrier_depends() – zapobiega zmianie kolejności zapisów zale n

ż ych wokół niej,

mb() - zapobiega zmianie porządku odczytów i zapisów wokół niej,

smp_rmb() - w systemach SMP dzia a

ł jak rmb(), w jednoprocesorowych jak barrier(),

smp_read_barrier_depends() - w systemach SMP dzia a

ł jak read_barrier_depends(), w jednoprocesorowych działa jak barrier(),

smp_wmb() - w systemach SMP działa jak wmb(), w jednoprocesorowych jak barrier(),

smp_mb() - w systemach SMP działa jak mb(), w jednoprocesorowych jak barrier(),

barrier() - zapobiega optymalizacji kodu wokół niej na etapie kompilacji.

9.

Zmiany od wersji 2.6.16 j d

ą ra

Osoby z grona programistów jądra systemu Linux, które są odpowiedzialne za mechanizmy synchronizacji zauważyły, e ż najczęściej używanym rodzajem semaforów są

semafory binarne, które pełnią rolę muteksów. W wersji j d

ą ra 2.6.16 zosta a

ł wprowadzona poprawka, która definiuje osobny typ danych o nazwie mutex. Jest on okre l

ś ony struktur ,

ą którą mo n

ż a zapisać nast p

ę ująco (bez uwzgl d

ę nienia pól związanych z debugowaniem):

struct mutex {

atomic_t count;

spinlock_t wait_lock;

struct list_head wait_list;

};

W przeciwie s

ń twie do struktury semaphore, zawartość tej struktury jest niezależna od architektury. Tą cechę posiadają również w dużej mierze implementacje operacji wykonywanych na niej – mogą być co najwy ej

ż optymalizowane pod wzgl d

ę em czasu wykonania na poszczególnych platformach. Pole count przechowuje stan muteksu.

Jeśli jego wartość jest równa jeden to jest muteks jest wolny, zero – zajęty, mniejsza od zera – zajęty i na jego podniesienie czekają w t ą ki. Rozró n

ż ienie dwóch stanów

zaj t

ę o c

ś i pozwala okre l

ś i ,

ć czy konieczne jest budzenie w t

ą ków. API muteksów jest dost p

ę ne po włączeniu pliku nag ów

ł

kowego linux/mutex.h i obejmuje nast p

ę ujące

funkcje:

DEFINE_MUTEX(name) – inicjalizacja muteksu na etapie kompilacji,

mutex_init(struct mutex *lock) – inicjalizacja muteksu na etapie wykonania,

mutex_lock_interruptible(struct mutex *lock) – zaj c

ę ie muteksu, je l

ś i operacja się nie powiedzie to zadanie jest ustawiana w stan TASK_INTERRUPTIBLE,

mutex_lock(struct mutex *lock) – jak wy ej

ż , ale zadanie ustawiane jest w stan TASK_UNINTERRUPTIBLE,

mutex_trylock(struct mutex *lock) – zwraca zero je l

ś i nie uda się zająć muteksu, jeden w przeciwnym przypadku,

mutex_unlock(struct mutex *lock) – zwalnia muteks,

mutex_is_locked(struct mutex *lock) – zwraca wartoś

ć wi k

ę szą od zera je l

ś i muteks jest zaj t

ę y, zero je l

ś i jest dostępny.

Muteksy nie są blokadami rekurencyjnymi i nie mogą być u y

ż wane w kontek c

ś ie przerwania. Intencją autorów tego rozwiązania jest całkowite usuni c

ę ie semaforów

z kodu jądra i zastąpienie ich muteksami, jednak e

ż jak do tej pory nie znaleziono innego rozwiązania dla kodu, który u y

ż wa semaforów, które nie są binarne.

10. Zmiany pocz w

ą szy od wersji 2.6.26

W wersji 2.6.26 j d

ą ra wprowadzono poprawk ,

ę która upraszcza implementację semaforów, czyniąc ją niezale n

ż ą od architektury oraz dodano operacje down_timeout()

i down_killable(). Pierwsza oczekuje na podniesienie semafora przez okre l

ś ony czas, a druga pozwala zakończyć zadanie, które oczekuje na podniesienie semafora.

4