Ćwiczenia 8: Procesy i synchronizacja na poziomie jądra

Definicje

Na potrzeby kilku następnych ćwiczeń zakładamy dostępność następujących typów danych oraz operacji na nich:

typ reprezentujący kolejki procesów zawieszonych: wait_queue
operacja sleep(q) wstawiająca wykonujący ją proces do kolejki qprocesów zawieszonych, zmieniająca jego stan na wstrzymany oraz inicjująca przełączenie kontekstu
operacja wakeup(q) zmieniająca stan wszystkich procesów zawieszonych w kolejce q na gotowy i przenosząca je do kolejki procesów gotowych
operacja disable_interrupts wyłącza przerwania
operacja enable_interrupts włącza przerwania

Ćwiczenie

Czy synchronizacja globalnych struktur danych w jednoprocesorowym systemie operacyjnym z jądrem niewywłaszczalnym (takim jak tradycyjne jądro Uniksa) jest w ogóle potrzebna?

Odpowiedź

Nawet w niewywłaszczalnym jądrze działającym na komputerze jednoprocesorowym może być w danej chwili aktywnych wiele procesów. Oczywiście wykonuje się jeden z nich, a pozostałe oczekują na procesor lub jakiś zasób. Dzieje się tak, gdyż proces mógł rozpocząć wykonanie funkcji systemowej, po czym zrzec się dobrowolnie procesora (bo na przykład musi poczekać na zajście jakiegoś zdarzenia na przykład zainicjowanej operacji wejścia-wyjścia).
Takie jądro nazywamy wielowejściowym.

Wszystkie te procesy współdzielą tę samą kopię struktur danych jądra, więc jądro musi dbać o zachowanie ich spójności. Szczęśliwie niewywłaszczalność bardzo mu w tym pomaga. Przypomnijmy niewywłaszczalność jądra oznacza, że proces wykonujący się w trybie jądra nie może zostać wywłaszczony przez inny proces, nawet jeśli upłynie przeznaczony dla niego kwant czasu. Proces może jednak dobrowolnie oddać procesor. Ponieważ dzieje się to w konkretnym punkcie programu wykonywanego przez proces, więc proces może zadbać o pozostawienie jądra w stanie spójnym. Dzięki temu jądro może na przykład swobodnie manipulować wskaźnikami listy dwukierunkowej bez blokowania dostępu do niej, gdyż nie grozi wywłaszczenie po modyfikacji wskaźnika w przód, a przed modyfikacją wskaźnika w tył.

Są jednak dwa powody, w których synchronizacja w jednoprocesorowym systemie z niewywłaszczalnym jądrem jest jednak niezbędna:

przerwania
konieczność zachowania spójności danych w czasie trwania operacji blokującej

Ćwiczenie

Jak zapewnić spójność struktur danych, z których korzystają podprogramy obsługi przerwań?

Odpowiedź

Wyłączając przerwania na czas modyfikacji tych struktur danych, z których może również korzystać podprogram obsługi przerwania. W ten sposób kod modyfikujący kluczowe struktury danych jest w istocie sekcją krytyczną.
Należy jednak przy tym pamiętać, że:

Przerwania wymagają zazwyczaj szybkiej obsługi i nie powinny czekać za długo na obsługę. Sekcje krytyczne powinny być zatem krótkie.
Zazwyczaj dysponujemy możliwością selektywnego wyłączania konkretnych przerwań lub grup przerwań. Należy z tego korzystać - na przykład modyfikując pule buforów dyskowych wystarczy wyłączyć przerwania dyskowe pozostawiając włączone przerwania od urządzeń sieciowych.

Rozważmy następujący przykład. W pewnym systemie operacyjnym pula wolnych buforów wejścia-wyjścia jest przechowywana w jednokierunkowej liście bufcache. Rozpoczynając operację wejścia-wyjścia jądro wywołuje funkcję GetBuffer, która znajduje pierwszy wolny bufor i usuwa go z listy wolnych buforów. Jeśli w puli nie ma wolnych buforów, to proces jest wstrzymywany w kolejce procesów zawieszonych nobuffers. Po zakończeniu operacji wejścia-wyjścia podprogram obsługi przerwania wywołuje procedure ReleaseBuffer (b). Dane są następujące deklaracje:

   type
      Buffer = ^ record 
                          next: Buffer;
                          data: array[0..BUFFERSIZE] of byte;
                          ...
                        end;
   var
      bufcache: Buffer;  {pierwszy bufor w puli buforów}

Zaimplementuj funkcję GetBuffer oraz ReleaseBuffer.

function GetBuffer: Buffer;
begin
   while bufcache = nil do 
     sleep (nobuffers);
   disable_interrupts; 
   GetBuffer := bufcache;
   bufcache := bufcache^.next;
   enable_interrupts; 
end;
 
procedure ReleaseBuffer (b: Buffer);
begin
   b^.next := bufcache;
   bufcache := b;
   wakeup (nobuffers)
end;

Wyłączenie przerwań w GetBuffer jest tu kluczowe! Niestety, nie daje ono jeszcze poprawności rozwiązania, pojawia się bowiem tzw. problem zagubionej pobudki. Zaobserwuj, co się stanie, jeśli przerwanie pojawi się po sprawdzeniu warunku pętli, a przed uśpieniem. Proces zostanie wówczas uśpiony, choć tak naprawdę jest dla niego bufor. Co więcej, pobudka dla niego (w postaci wakeup z ReleaseBuffer została wygenerowana ... zanim został on uśpiony!

Odłóżmy na razie rozwiązanie tego problemu i nie przejmując się nim przyjrzyjmy się drugiej sytuacji wymagającej synchronizacji w jądrze niewywłaszczalnym na jednoprocesorze. Zauważmy jeszcze tylko, że o ile disable_interrupt blokuje także przerwania zegarowe nie dopuszczając tym samym do wywłaszczenia procesu z powodu upływu kwantu czasu oraz o ile w trakcie obsługi przerwań blokowane są przerwania, to rozwiązania to zadziała poprawnie (z dokładnością do zagubionej pobudki) także w systemie z jądrem wywłaszczalnym (ale nie na wieloprocesorze).

Ćwiczenie

Jak zapewnić spójność struktur danych w czasie wykonywania operacji blokującej?
Przypuśćmy, że w poprzednim zadaniu bufory znalezione przez GetBuffer są jedynie blokowane i nie usuwa się ich z puli wolnych buforów. Zmodyfikuj treść funkcji GetBuffer i procedury ReleaseBuffer. Nie przejmuj się problemem zagubionej pobudki.

Tym razem w ogóle nie musimy blokować przerwań, a właściwą synchronizację zapewni dodatkowe pole blocked związane z każdym buforem oraz niewywłaszczalność jądra.

function GetBuffer: Buffer;
var
   found: boolean;
   p: Buffer;
begin
   found := false; 
   while not found do 
   begin  
       p := bufcache;
       while (p <> nil) and not found do
       if p^.blocked then 
         p := p^.next 
      else begin  
        found := true;
        GetBuffer := p;
        p^.blocked := true  
      end;
      if not found then 
        sleep (nobuffers)
   end;
end;
 
procedure ReleaseBuffer (p: Buffer);
begin
   p^.blocked := false;
  wakeup (nobuffers)
end;

Choć struktura danych nie straci spójności, to jednak jeszcze dobitniej widać tu problem zagubionej pobudki, który drastycznie ujawni się, gdy podczas poszukiwania wolnego bufora zostanie zwolniony bufor, który już sprawdzaliśmy.
Zauważmy przy okazji, że w jądrze wywłaszczalnym oraz na wieloprocesorze powyższe rozwiązanie nie zapewni spójności danych.

W praktyce powyższe rozwiązanie zapisalibyśmy unikając przeszukiwania, gdy wiadomo, że buforów brakuje. Wystarczy, aby jądro utrzymywało globalną zmienną freebuffers zliczającą wolne bufory. Dla uproszczenia załóżmy, że operacje zwiększania i zmniejszanie tej zmiennej są atomowe:

function GetBuffer: Buffer;
   p: Buffer;
begin
   while freebuffers = 0 do 
     sleep (nobuffers);
    freebuffers--;
    p := bufcache;
    while p^.blocked do
         p := p^.next; 
    GetBuffer := p;
    p^.blocked := true  
end;
 
procedure ReleaseBuffer (p: Buffer);
begin
   p^.blocked := false;
   freebuffers++;
   wakeup (nobuffers)
end;

W dalszym ciągu jest to rozwiązanie, które nie zadziała ani z jądrem wywłaszczalnym ani z wieloprocesorem, a w przypadku jądra wywłaszczalnego mamy problem z zagubioną pobudką.

Ćwiczenie

Czy można poradzić sobie jakoś z problemem zagubionej pobudki?

Odpowiedź

Nie. Proces musi odblokować przerwania zanim zostanie uśpiony, ale odblokowanie przerwań przed uśpieniem może spowodować, że przerwanie pojawi się zanim proces zostanie uśpiony. Chyba, że zmienimy semantykę operacji sleep. Niech teraz sleep atomowo zmienia stan procesu, przenosi go do kolejki procesów zatrzymanych i odblokowuje przerwania. Dzięki temu można go wywołać przy wyłączonych przerwaniach, a nasz ostatni program wyglądałby tak:

function GetBuffer: Buffer;
   p: Buffer;
begin
   disable_interrupts;
   while freebuffers = 0 do
   begin 
     sleep (nobuffers);
     disable_interrupts;
    end;
    freebuffers--;
    enable_interrupts;
    p := bufcache;
    while p^.blocked do
         p := p^.next; 
    GetBuffer := p;
    p^.blocked := true  
end;
 
procedure ReleaseBuffer (p: Buffer);
begin
   p^.blocked := false;
   freebuffers++;
   wakeup (nobuffers)
end;

Teraz już nie trzeba zakładać niepodzielności operacji zwiększania i zmniejszania zmiennej freebuffers.

Ćwiczenie

Zaimplementuj operacje P i V na semaforze ogólnym w systemie jednoprocesorowym bez wywłaszczania. Załóż, że żadna procedura obsługi przerwania nigdy nie manipuluje semaforem.

type
   semaphore = record
      count: integer;
      wait: wait_queue;
   end;
 
procedure P (var s: semaphore); { tryb jądra}
begin
  while (s.count <= 0) do sleep (s.wait);
  s.count--;
end;
 
procedure V (var s: semaphore); { tryb jądra }
begin
   inc (s.count);
   wakeup (s.wait);
end;

Oczywiście w systemie z jądrem wywłaszczalnym i na wieloprocesorze rozwiązanie jest niepoprawne - brakuje nawet bezpieczeństwa, bo wiele procesów może wykonywać jednocześnie procedurę P.

Ćwiczenie

Niektóre procesory (na przykład MIPS R4000, Alpha AXP firmy Digital oraz mikrokontrolery rodziny ARM) oferują parę specjalnych rozkazów:

load-locked (adres) przekazuje w wyniku wartość z komórki pamięci o podanym adresie i ustawia znacznik sprzętowy związany z konkretnym procesorem. Ten znacznik sprzętowy oznacza, że jedynie procesor wykonujący load-locked(adres) ma prawo wykonać na tym adresie operację store-cond
store-cond (adres, wartość)wpisuje wartość do pamięci, o ile jest ustawiony znacznik wykonującego procesora. Jeśli zapis się udał, to przekazuje w wyniku true, w przeciwnym razie wynikiem jest false. Znacznik jest zerowany.

Zaimplementuj blokadę wirującą dla wieloprocesora za pomocą pary rozkazów load-locked i store-cond. (Implementacja za pomocą xchng oraz test-and-set była na wykładzie). Załóż, że spin_lock jest niewywłaszczalny.

Rozwiązanie

var
  lock: boolean := false;
 
procedure spin_lock (var lock: boolean);
begin
   repeat
      while load-locked (lock) do {nic};
   until store-cond (lock, true)  
end;   
 
procedure spin_unlock (var lock: boolean);
begin
     lock := false;   
end;

Ćwiczenie

Czy blokady wirujące w kodzie jądra mają sens:

w jądrze niewywłaszczalnym na jednoprocesorze?
w jądrze wywłaszczalnym na jednoprocesorze?
na wieloprocesorze?

Odpowiedź

Blokady wirujące mają sens na wieloprocesorze, gdzie oczekiwanie w sposób aktywny na zasób zablokowany przez aktualnie wykonujący się (na innym procesorze) proces, może okazać się efektywniejsze niż wstrzymywanie procesu.
W systemach jednoprocesorowych z jądrem wywłaszczalnym blokady wirujące są nieefektywne, choć jeszcze niczego nie psują. Natomiast w jądrze niewywłaszczalnym "zawieszenie" się na blokadzie wirującej oznacza zakleszczenie.
Z tego powodu operacje spin_lock oraz spin_unlock są w takich systemach implementowane jako operacje puste.

Ćwiczenie

Spróbujmy teraz uzupełnić poprzednią implementację semafora o wzajemne wykluczanie realizowane za pomocą blokad wirujących. Czy otrzymamy w ten sposób poprawną implementację semafora?

 
type
   semaphore = record
      count: integer;
      wait: wait_queue;
      lock: boolean;
   end;
 
procedure P (var s: semaphore); { tryb jądra}
begin
  spin_lock(s.lock);
  while (s.count <= 0) do begin
     spin_unlock(s.lock); 
     sleep (s.wait);
     spin_lock(s.lock);
  end; 
  s.count--;
  spin_unlock(s.lock);
end;
 
procedure V (var s: semaphore); { tryb jądra }
begin
   spin_lock (s.lock);
   s.count++;
   wakeup (s.wait);
   spin_unlock (s.lock)
end;

W systemie jednoprocesorowym jest OK (o ile operacje na blokadach wirujących są implementowane jako puste w przypadku jądra niewywłaszczalnego). Natomiast w systemie wieloprocesorowym mamy znów problem z zagubioną pobudką - tym razem jednak na nieco innym poziomie niż poprzednio.

Żeby sobie z tym problemem poradzić potrzebujemy niepodzielną operacje spin_unlock i sleep. Implementacja semafora w wieloprocesorowym jądrze Linuksa korzysta na przykład z wariantu funkcji sleep, której jednym z parametrów jest semafor s. Operacja sleep jest wywoływana bez zwalniania blokady wirującej i dopiero po faktycznym umieszczeniu procesu w odpowiedniej kolejce tuż przed przełączeniem kontekstu, wywołuje ona spin_unlock (s.lock).

Informatyka MIMUW