Systemy operacyjne 2020 - listy zadań 10 - 12

Lista zadań nr 10

Przed rozwiązywaniem zadań należy się zapoznać z podrozdziałami 12.8 - 12.10 Advanced Programming in the UNIX Environment oraz z następującymi rozdziałami Operating Systems: Three Easy Pieces: Concurrency: An Introduction, Interlude: Thread API, Event-based Concurrency. Całość tej książki można znaleźć na jej oficjalnej stronie.

Zadanie 1

Czym różni się przetwarzanie równoległe (ang. parallel) od przetwarzania współbieżnego (ang. concurrent)? Czym charakteryzują się procedury wielobieżne (ang. reentrant)? Podaj przykład procedury w języku C:

1. wielobieżnej, ale nie wątkowo-bezpiecznej (ang. thread-safe)
2. na odwrót (wątkowo-bezpiecznej, ale nie wielobieżnej).

Kiedy w jednowątkowym procesie uniksowym może wystąpić współbieżność?

Definicje wielobieżności są różne w zależności od źródeł, dlatego przykład ze swap może być niepoprawny, w zależności od przyjętej definicji. Ponadto, mówiąc o procedurach bezpiecznych, warto wiedzieć o wątkowej bezpieczności (ang. thread-safe), jak i sygnałowej bezpieczności (ang. signal-safety). Jedną z definicji zależności między funkcjami wielobieżnymi, wątkowo-bezpiecznymi i wątkowo-niebezpiecznymi przedstawia rysunek na samym końcu zadania, którego źródłem jest CS:APP.

Przetwarzanie równoległe (ang. parallel) polega na jednoczesnym przetwarzaniu wielu różnych zadań, czy obliczeń (np. przez 2 lub więcej procesory).

Przetwarzanie współbieżne (ang. concurrent) polega na współistnieniu wielu wątków lub procesów. Uruchomione wątki na tym samym procesorze są wykonywane naprzemiennie, sprawiając wrażenie, że wykonują się równolegle.

Te dwie formy przetwarzania różni sposób, w jaki wykonują zadania/obliczenia. Przy przetwarzaniu współbieżnym w miejscu linii przerywanych należy pamiętać o tym, że zmieniany jest kontekst (przez co zmiana między zadaniami nie jest natychmiastowa).

Procedura wielobieżna (ang. reentrant) to procedura, której wykonywanie może zostać przerwane np. przerwaniem, bądź wywołaniem innej funkcji wewnątrz ciała funkcji, a następnie może ona zostać ponownie wywołana, zanim poprzednie wywołanie zostanie zakończone. Po zakończeniu drugiego wywołania, można wrócić do przerwanego wywołania, a wykonywanie go można bezpiecznie kontynuować. Taką procedurę cechują:

1. Nie powinna operować na niestałych zmiennych globalnych i zmiennych static, jednak może pracować z takimi danymi (nie jest to zalecane!).
2. Nie może modyfikować swojego kodu - techniki takie jak blitting mogłyby sprawić, że kod nie byłby taki sam przy kolejnym wywołaniu.
3. Nie może wywoływać procedur niewielobieżnych.

Procedura wątkowo-bezpieczna (ang. thread-safe) to procedura, która gwarantuje brak sytuacji wyścigu, gdy jest uruchamiana przez kilka wątków jednocześnie.

Procedura wielobieżna, ale nie wątkowo-bezpieczna:

int tmp;

void swap(int* x, int* y)
{
    int s = tmp; // save global variable

    tmp = *x;    // perform normal swap
    *x = *y;
    *y = tmp;     

    // hardware interrupt might invoke isr() here,
    // producing incorrect results in swap

    // restore global variable
    tmp = s;
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}

W powyższym przykładzie może dojść do sytuacji, w której dwa różne wątki wykonują funkcję swap. Jeśli jeden z nich zostanie przerwany po *y = tmp, ale przed tmp = s, a drugi wykonany, potencjalnie może zmienić on wartość zmiennej tmp. W takiej sytuacji powrót do pierwszego wątku mógłby zwracać niepoprawne wyniki.

Procedura wątkowo-bezpieczna, ale nie wielobieżna:

# include <pthread.h>

int increment_counter ()
{
  static int counter = 0;
  static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

  // only allow one thread to increment at a time
  pthread_mutex_lock(&mutex);

  ++counter;

  // store value before any other threads increment it further
  int result = counter;

  pthread_mutex_unlock(&mutex);

  return result;
}

Powyższa procedura może zostać wywołana przez różne wątki, gdyż używa muteksów do zsynchronizowania wszystkich dostępów do współdzielonej zmiennej counter. Jednak gdy taka funkcja zostanie użyta przez wielobieżną obsługę przerwań i zostanie wysłane drugie przerwanie, w trakcie gdy muteks jest zablokowany, drugie wywołanie zawiesi się na zawsze.

Innym przykładem procedury wątkowo-bezpiecznej, ale nie współbieżnej jest printf, jako że POSIX wymaga, aby procedury stdio były wątkowo-bezpieczne. Nie jest ona jednak wielobieżna, gdyż używa synchronizacji za pomocą locków. Z drugiej strony, procedurami współbieżnymi, ale nie wątkowo-bezpiecznymi są takie, które korzystają z globalnego bufora, a następnie go przywraca przy wychodzeniu.

Nieporozumienie wynikające z różnic Wikipedii i StackOverflow i CS:APP: powyżej podane przeze mnie przykłady wywodzą się z Wikipedii i StackOverflow, natomiast w CS:APP funkcje wielobieżne są podzbiorem funkcji wątkowo-bezpiecznych, co przeczy zadaniu (mamy podać przykład funkcji wielobieżnej, ale nie wątkowo-bezpiecznej). W przypadku funkcji wątkowo-bezpiecznej, ale nie wielobieżnej, wszystko jest już w porządku.

Jednowątkowy program może działać współbieżnie, jeśli wykorzysta skoki setjmp(3) i longjmp(3). Taką "współbieżność" nazywamy wielozadaniowością kooperacyjną, a najlepszym przykładem są prawdopodobnie korutyny, czyli kilka współprogramów działających w obrębie jednego procesu.

Zadanie 2

Wybierz odpowiedni scenariusz zachowania wątków, w którym konkurują o dostęp do zasobów, i na tej podstawie precyzyjnie opisz zjawisko zakleszczenia (ang. deadlock), uwięzienia (ang. livelock) oraz głodzenia (ang. starvation). Dalej rozważmy wyłącznie ruch uliczny. Kiedy na jednym lub wielu skrzyżowaniach może powstać każde z tych zjawisk? Zaproponuj metodę:

1. wykrywania i usuwania zakleszczeń,
2. zapobiegania zakleszczeniom.

Wskazówka: Określ zbiór właściwości

$\{p_i\}$, które zachodzą: zawsze, nigdy, od pewnego momentu

$t_k$, nieskończenie wiele razy.

Dla odważnych: Spróbuj użyć logiki LTL, o której więcej będzie na przedmiocie „Automated verification”.

Zakleszczenia (ang. deadlock) to sytuacja, w której wątek A czeka na zakończenie operacji wątka B, a wątek B czeka na zakończenie wątka A. Program nigdy nie zakończy działania, gdyż wątki czekają na siebie nawzajem.

Uwięzienie (ang. livelock) to sytuacja, w której dwa wątki zatrzymują swoje działanie aby uniknąć deadlocka, aby umożliwić innym wątkom wykonanie się, jednak robią to jednocześnie, przez co nie jest możliwe wykonanie się żadnego z nich. W przeciwieństwie do deadlocka, stan wątku może ulec zmianie.

Głodzenie (ang. starvation) to sytuacja, w której wątek nie otrzymuje dostępu do zasobu, na który oczekuje, przez co nie może rozpocząć swojego działania.

Porównanie do ruchu ulicznego:

• Zakleszczenie wystąpi, gdy do skrzyżowania równorzędnego podjadą jednocześnie auta z każdej strony - pierwszeństwo ma pojazd z prawej strony, więc pojazd A musi ustąpić pojazdowi B, pojazd B pojazdowi C, pojazd C pojazdowi D i pojazd D pojazdowi A. Mogą one oczekiwać na ruch pozostałych (każdy jednak ruszyłby w jednym momencie), albo ruszają jednocześnie, powodując zablokowanie całego skrzyżowania.4
  
• Uwięzienie może nastąpić np. na zwężeniu drogi. Samochody z naprzeciwka chcą się wzajemnie przepuścić, jednak żaden nie rozpoczyna manewru pierwszy. Nagle jednocześnie ruszają, powodując uwięzienie - żaden z pojazdów nie może nic zrobić.
  
• Głodzenie nastąpi w sytuacji, gdy na skrzyżowaniu z sygnalizacją świetlną na jednym wyjeździe cały czas będzie palić się czerwone światło, przez co pojazdy nie będą mogły nigdy ruszyć. Może się to również zdarzyć, gdy jest bardzo duży ruch na drodze głównej, przez co pojazdy nie mogą wyjechać z drogi podporządkowanej, jako że muszą ustąpić pierwszeństwa wszystkim poruszającym się pojazdom na głównej.
  

Wykrywanie i usuwanie zakleszczeń polega na tym, że system operacyjny zezwala na wystąpienie zakleszczeń, a następnie je wykrywa i stara się je usunąć. Aby wykryć zakleszczenie dla jednego typu zasobu dla każdego wątku, należy stworzyć graf na podstawie stanu systemu, a następnie sprawdzić, czy zawiera on cykl - jeżeli tak, to wątki są zakleszczone.

W takiej sytuacji istnieje cykl, więc występuje zakleszczenie.

Wykrywanie zakleszczeń w formalny sposób polega na szukaniu cykli (w przypadku pojedynczych dostępów do zasobów) lub na szukaniu cykli i kolorowaniu (ten ogromny algorytm z macierzami, w przypadku dostępów do zasobów wspólnych). Źródłem obu algorytmów jest książka Modern Operating Systems A. Tanenbauma. Algorytmy te można opisać w taki sposób: skonstruuj graf zasobów, a następnie przeprowadź kolejno kroki:

1. Dla każdego węzła
   $N$ w grafie wykonaj poniższe kroki, zaczynając od
   $N$.
2. Stwórz pustą listę 
   $L$, a wszystkie łuki oznacz jako niezaznaczone.
3. Dodaj bieżący węzeł na koniec listy
   $L$ i sprawdź, czy węzeł występuje teraz na liście
   $L$ dwa razy. Jeśli tak, to graf zawiera cykl w postaci listy
   $L$ i algorytm kończy się.
4. Sprawdź, czy z tego węzła wychodzą dowolne niezaznaczone łuki. Jeśli tak, to przejdź do kroku
   $5.$, jeśli nie, to przejdź do kroku
   $6$.
5. Losowo wybierz niezaznaczony wychodzący łuk i go zaznacz. Następnie przejdź wzdłuż niego do następnego węzła i skocz do kroku
   $3$.
6. Jeśli jest to węzeł początkowy, graf nie zawiera żadnych cykli i algorytm kończy działanie. W innym przypadku osiągneliśmy martwy koniec. Usuń węzeł z listy i przejdź do poprzedniego węzła, czyli tego, który był bieżący przed aktualnie analizowanym węzłem. Oznacz go jako bieżący i przejdź do kroku
   $3$.

Algorytm ten polega na analizowaniu kolejnych węzłów w roli korzenia struktruy, która zgodnie z oczekiwaniami jest drzewem, i wykonywaniu na niej wyszukiwania w głąb. Jeśli podczas tego wyszukiwania kiedykolwiek wrócimy do węzła, który już był na liście, mamy do czynienia z cyklem (a więc zakleszczeniem).

Wykrywanie zakleszczeń dla przypadku wielu zasobów każdego typu jest już bardziej złożone i wymaga innego podejścia. Niech

$P_1,\dots ,P_n$ oznaczają procesy, liczba klas zasobów to

$m$, przy czym istnieje

$E_1$ zasobów klasy

$1$,

$E_2$ zasobów klasy

$2$ i ogólnie

$E_i$ zasobów klasy

$i$ (dla

$1\le i\le m$).

$E$ jest wektorem istniejącego zasobu i zwraca on całkowitą liczbę egzemplarzy każdego z istniejących zasobów. Jeśli np. klasa

$1$ to napędy taśm, to

$E_1=2$ oznacza, że są dwa takie napędy. W dowolnym momencie pewne zasoby są przydzielane i nie są dostępne. Niech

$A$ będzie wektorem dostępnych zasobów, a

$A_i$ oznaczać będzie liczbę aktualnie dostępnych egzemplarzy zasobu

$i$. Jeśli oba napędy taśm zostaną przypisane, to

$A_1=0$. Potrzebujemy jeszcze dwóch macierzy:

$C$, czyli macierzy bieżącej alokacji i

$R$, czyli macierzy żądań. Wiersz

$i$ macierzy

$C$ określa, ile egzemplarzy każdego zasobu zawiera w danym momencie klasa

$P_i$. Tak więc

$C_{ij}$ to liczba egzemplarzy zasobu

$j$ będących w posiadaniu procesu

$i$. Na podobnej zasadzie

$R_{ij}$ oznacza liczbę egzemplarzy zasobu

$j$, których żąda proces

$P_i$.

Dla istniejących zasobów

$E_1,\dots ,E_m$, tak wygląda macierz bieżących alokacji i

$i$-ty wiersz oznacza bieżący przydział dla procesu

$i$.

Podobnie wygląda macierz żądań przedstawiona poniżej. Dla dostępnych zasobów

$A_1,\dots ,A_m$, proces

$i$-ty potrzebuje wiersza

$i$-tego.

Mając tak przygotowane dane, możemy przejść do algorytmu, który bazuje na porówynwaniu wektorów. Niech relacja

$A\le B$ dwóch wektorów

$A,B$ oznacza, że każdy element wektora

$A$ jest mniejszy lub równy odpowiadającemu mu wektorowi

$B$. Na samym początku każdy proces jest nieoznaczony, a w miarę postępów zostają one oznaczone, co wskazuje na to, że mogą się wykonać i nie zostaną zakleszczone. Algorytm jest następujący:

1. Poszukaj nieoznaczonego procesu
   $P_i$, dla którego
   $i$-ty wiersz macierzy
   $R$ jest mniejszy lub równy od
   $A$.
2. Jeśli taki proces zostanie znaleziony, to dodaj
   $i$-ty wiersz macierzy
   $C$ do
   $A$, oznacz proces i powróć do kroku
   $1$.
3. Jeśli nie ma takich procesów, to algorytm kończy działanie.

Gdy algorytm się zakończy i pozostaną jakieś procesy nieoznaczone, to będzie to oznaczać, że są one zakleszczone.

Usuwanie zakleszczeń może odbywać się na kilka sposobów:

1. wywłaszczanie - czasowo zabierany jest zasób właścicielowi i przydzielany innemu procesowi,
2. cofnięcie operacji (ang. rollback) - w trakcie działania procesu, są rejestrowane punkty kontrolne (ang. checkpoints) stanu procesów, dzięki czemu można do nich powrócić, w razie wykrycia przez system zakleszczenia,
3. zabijanie procesów.

Zapobieganie zakleszczeniom polega na tym, że system operacyjny tak zarządza zasobami, aby zakleszczenia nie wystąpiły. Zakleszczenia na pewno nie wystąpią, jeżeli zostanie spełniony jeden z poniższych warunków:

1. wzajemne wykluczenie - żaden proces nie może mieć wyłącznego dostępu do zasobu,
2. trzymanie zasobu i oczekiwanie - zadanie może rozpocząć działanie dopiero w momencie dostępności wszystkich zasobów niezbędnych do jego zakończenia lub zadanie zwalnia wszystkie zajmowane zasoby przed żądaniem tych, które potrzebują - metoda ta jest podatna na zagłodzenie, dla procesów które żądają wielu zasobów,
3. cykliczne oczekiwanie - ustalenie określonej kolejności w jakiej muszą wystąpić żądania przydzielania konkretnych zasobów,
4. brak wywłaszczania zasobu - rozwiązaniem najprostszym jest arbitralne zakończenie zadania, przy tym rozwiązaniu system powinien kierować się minimalizowaniem strat np. przez wybieranie takich procesów, które mają bardzo krótki czas uruchomienia.

Zadanie 3

W poniższym programie występuje sytuacja wyścigu (ang. race condition) dotycząca dostępów do współdzielonej zmiennej tally. Wyznacz jej najmniejszą i największą możliwą wartość.

const int n = 50;
shared int tally = 0;

void total() {
  for (int count = 1; count <= n; count++)
    tally = tally + 1;
}

void main() { parbegin (total(), total()); }

Dyrektywa parbegin rozpoczyna współbieżne wykonanie procesów. Maszyna wykonuje instrukcje arytmetyczne wyłącznie na rejestrach – tj. kompilator musi załadować wartość zmiennej tally do rejestru, przed wykonaniem dodawania. Jak zmieni się przedział możliwych wartości zmiennej tally, gdy wystartujemy

$k$ procesów zamiast dwóch? Odpowiedź uzasadnij pokazując przeplot, który prowadzi do określonego wyniku.

Okazuje się, że poniższe rozwiązanie jest błędne, ponieważ założyłem, że wszystkie iteracje pętli są od siebie niezależne, a może wydarzyć się sytuacja, w której przeplot będzie wyglądał w taki sposób: pierwsze wątek pobiera tally = 0, drugi pobiera tally = 0 i wykonuje 49 iteracji pętli, później pierwszy wątek wykonuje dodawanie (na tally = 0) i wpisuje je do pamięci. Następnie wątek drugi wykonuje ostatnią iterację pętli, gdy zapisane jest tally = 1. Teraz pierwszy wątek wraca, wykonuje pozostałe iteracje, czyli tally = 50. Drugi wątek teraz zapisuje wartość tally po wykonaniu dodawania, czyli ostatecznie tally = 2. Oznacza to, że przedział dla

$k$ wątków to

$[2,50k]$.

Zadanie wymaga udowodnienia, że rzeczywiście taki przedział jest poprawny.

Sytuacja wyścigu (ang. race condition) to sytuacja, w której dwa lub więcej procesów jednocześnie czytają lub zapisują współdzielone dane, a rezultat zależy od tego, który proces będzie działał i w jakim momencie.

Aby rozpatrzyć ten przypadek, należy wziąć pod uwagę to, w jaki sposób działa instrukcja w pętli, a więc jakie składowe ma tally = tally + 1. W asemblerze są to trzy następujące instrukcje:

1: załaduj wartość tally do rejestru
2: dodaj 1 do wartości przechowywanej w rejestrze
3: zapisz wartość rejestru do tally

Oczekiwaną wartością wyjściową tally dla 2 procesów jest

$100$, a więc w każdej iteracji wartość zwiększa się o

$+2$, zachodzi to w przypadku poprawnego działania programu. Instrukcje (dla procesów

$A,B$) są wykonywane w kolejności:

$$A1\to A2\to A3\to B1\to B2\to B3$$

Jest to jednocześnie maksymalna wartość, jaką może osiągnąć tally. Możemy łatwo wywnioskować, że dla

$k$ procesów maksymalną wartość tally można osiągnąć poprzez sekwencyjne wykonywanie pełnych instrukcji, tak jakby były otoczone lockami, tzn.:

$$P_1^1\to P_1^2\to P_1^3\to P_2^1\to P_2^2\to P_2^3\to \dots \to P_k^1\to P_k^2\to P_k^3$$

Dokładnym wynikiem dla

$k$ procesów będzie tally = 50 * k.

Rozpatrzmy teraz minimalną wartość, jaką może mieć tally po wykonaniu programu:

$$A1\to A2\to B1\to A3\to B2\to B3$$

Najpierw ładujemy tally do %rax (

$A1$), dodajemy

$1$ (

$A2$), wczytujemy tally ponownie (tutaj bez zmian, bo jeszcze wartość nie została zapisana do tally), mamy więc

$0$ (

$B1$), następnie zapisujemy do tally wartość z rejestru, czyli tally (

$A3$). Teraz dodajemy

$1$ do rejestru

$(B2)$ i zapisujemy wartość w tally

$(B3)$. Taki sam rezultat otrzymamy przy prostym przeplocie:

$$A1\to B1\to A2\to B2\to A3\to B3$$

Tę sytuację przedstawia to poniższy diagram:

Oznacza to, że minimalną wartością, jaką możemy uzyskać po jednej iteracji pętli jest

$+1$. Uogólnienie tej sytuacji dla wielu

$k$ wątków jest następujące:

$$P_1^1\to P_2^1\to \dots \to P_k^1\to P_1^2\to P_2^2\to \dots \to P_k^2\to P_1^{1}3\to P_2^3\to \dots P_k^3$$

Przedziałem wartości, jakie możemy otrzymać po uruchomieniu programu dla 2 procesów jest

$[50,100]$, a dla

$k$ procesów

$[50,50k]$.

Zadanie 4

Podaj odpowiedniki funkcji fork(2), exit(3), waitpid(3), waitpid(2), atexit(3) oraz abort(3) dla wątków i opisz ich semantykę. Niepogrzebane procesy określamy mianem zombie – aby zapobiec ich powstawianiu ustawiamy dyspozycję sygnału «SIGCHLD» na «SIG_IGN». Dla wątków mamy podobną sytuację – porównaj zachowanie wątków przyczepionych (ang. attached) i odczepionych (ang. detached).

Tabelka na podstawie Figure 11.6 - Comparison of process and thread primitives z APUE:

Procesy	Wątki	Działanie
fork(2)	pthread_create(3)	Utworzenie nowego przepływu sterowania
exit(3)	pthread_exit(3)	Wyjście z danego przepływu sterowania
waitpid(2)	pthread_join(3)	Otrzymanie statusu wyjścia przepływu sterowania
atexit(3)	pthread_cleanup_push(3)	Dopisanie funkcji do wywołania przy wyjściu z przepływu sterowania
abort(3)	pthread_cancel(3)	Żądanie zakończenia przepływu sterowania (SIGABRT)
getpid(2)	pthread_self(3)	Uzyskanie ID dla przepływu sterowania

Do tworzenia wątków używana jest poniższa funkcja pthread_create(3) - pierwszy argument thread to wskaźnik na strukturę pthread_t (czyli wątek), attr określa atrybuty wątku, start_routine to wskaźnik na funkcję (rutynę), którą chcemy uruchomić w wątku, a *arg to wskaźnik na argument (strukturę danych) przekazywany do wątku.

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine) (void *), void *arg);

Zakończenie wątku funkcją pthread_exit(3) zwraca wartość przez retval.

void pthread_exit(void *retval);

Oczekiwanie na wątek odbywa się dzięki funkcji pthread_join(3), której argumentami są thread (wątek na który chcemy czekać) oraz retval, czyli wartość, jakiej oczekujemy, że zostanie zwrócona.

int pthread_join(pthread_t thread, void **retval);

Aby zarejestrować funkcję do wywołania na zakończenie wątku, należy dodać funkcję routine z jej argumentami arg na górę stosu, w tym celu używamy funkcji pthread_cleanup_push(3).

void pthread_cleanup_push(void (*routine)(void *), void *arg);

Aby wysłać żądanie zakończenia (anulowania) wątku, korzystamy z funkcji pthread_cancel(3). Jej argumentem jest thread, a więc wątek, który chcemy zatrzymać.

int pthread_cancel(pthread_t thread);

Jeśli chcemy uzyskać ID uruchomionego wątku (w ciele funkcji tego wątku), korzystamy z funkcji pthread_self(3), która zawsze kończy się pomyślnie i zwraca ID.

pthread_t pthread_self(void);

Wątki przyczepione (ang. attached, joinable) są domyślnym rodzajem działania wątków, polegają one na tym, że nie zwalniają zasobów po zakończeniu rutyny. Aby je zwolnić, należy wykorzystać funkcję pthread_join(3) omówioną powyżej.

Wątki odczepione (ang. detached) to wątki, które po zakończeniu rutyny natychmiastowo zwalniają wykorzystywane przez nie zasoby. Aby ustawić takie zachowanie, należy wykorzystać funkcję pthread_detach(3), której argumentem jest ID wybranego wątku.

Te dwa tryby różni więc czas, w którym wątki zwalniają zasoby. Gdybyśmy w wątku przyczepionym nie zwolnili zasobów, to zostaną zwolnione dopiero po zakończeniu programu.

Zadanie 5

Implementacja wątków POSIX skomplikowała semantykę niektórych zachowań procesów, które omawialiśmy do tej pory. Co nieoczekiwanego może się wydarzyć w wielowątkowym procesie uniksowym gdy:

• jeden z wątków zawoła funkcję fork(2) lub execve(2) lub _exit(2)?
• proces zadeklarował procedurę obsługi sygnału SIGINT, sterownik terminala wysyła do procesu SIGINT – który wątek obsłuży sygnał?
• określono domyślną dyspozycję sygnału SIGPIPE, a jeden z wątków spróbuje zapisać do rury pipe(2), której drugi koniec został zamknięty?
• czytamy w wielu wątkach ze pliku zwykłego korzystając z tego samego deskryptora pliku?

Wywołanie fork(2) kopiuje cały proces, a więc strony pamięci, otwarte deskryptory plików i inne. Jedną z różnic procesów dziecka i rodzica jest to, że proces dziecka ma tylko jeden wątek. Klonowanie całego procesu ze wszystkimi wątkami byłoby problematyczne i w większości przypadków nie byłoby to czymś, czego oczekiwałby programista.

Nieoczekiwanym problemem wynikającym z tego podejścia jest to, że w momencie wywołania fork(2), część wątków może być w krytycznych sekcjach kodu i wykonywać nieatomowe operacje otoczone muteksami. W procesie dziecka wątki znikają i pozostałe dane (potencjalnie częściowo zmienione) stają się nienaprawialne. Nie jesteśmy w stanie określić, co robiły inne wątki i co powinno zostać dokończone, aby dane były takie, jak oczekiwaliśmy. Ponadto, stan muteksów jest niezdefiniowany, przez co konieczne będzie wywołanie pthread_mutex_init() w dziecku, aby zresetować je do użytecznego stanu.

Problem z muteksami i sekcjami krytycznymi kodu implikują kolejny problem. Funkcje biblioteczne mog korzystać z danych globalnych i nawet jeśli są wątkowo-bezpieczne, to mogą korzystać z locków. Oznacza to, że nie jest bezpieczne wywoływanie np. fork(2) w programie wielowątkowym, gdy w jakimś wątku używany jest malloc(3) (gdyż używa on system locków).

Użycie execve(2) również powoduje problemy. Po wywołaniu tej funkcji, deskryptory plików zostają otwarte i uruchomiony program może do nich pisać lub z nich czytać. Jeśli deskryptor pliku pozostanie otwarty, w pewnych sytuacjach mogą wystąpić problemy z bezpieczeństwem programu. Aby temu zapobiec, można użyć fcntl(2) z flagą FD_CLOEXEC, jednak w takim przypadku mogą wystąpić sytuacje wyścigu. Załóżmy, że jeden wątek wywołuje fork(2) i execve(2), w trakcie gdy drugi wątek wywołuje open(2). Drugi wątek chce wywołać fcntl(2), jednak pierwszy wątek wykonał już fork(2) i execve(2), co sprawi, że nowo uruchomiony program będzie miał zduplikowany deskryptor pliku. Kolejność wywołań, o jakiej mowa, to:

open -> fork -> execve -> fcntl

Gdy jeden z wątków zawoła _exit(2), to zostanie wyłączony tylko ten wątek, w którym _exit(2) zostało wywołane. Często będzie to nieoczekiwane zachowanie i chcąc zakończyć wszystkie wątki w procesie, powinniśmy użyć exit_group(2).

Zakładając, że w programie został napisany signal handler, zgodnie ze specyfikacją POSIX sytuacja będzie wyglądała następująco:

POSIX.1 distinguishes the notions of signals that are directed to the process as a whole and signals that are directed to individual threads. According to POSIX.1, a process-directed signal (sent using kill(2), for example) should be handled by a single, arbitrarily selected thread within the process.

Oznacza to, że po wysłaniu SIGINT (bądź innego sygnału), zostanie wylosowany dowolny wątek tego procesu, do którego zostanie wysłany sygnał.

Wszystkie wątki w danym procesie dzielą wspólny pipe(2) (info tutaj), a więc zamknięcie jednego końca w którymś wątku sprawi, że pipe zostanie zamknięty we wszystkich wątkach. Wtedy program zakończy się z błędem SIGPIPE, mówiącym o "Broken pipe".

Jeśli wiele wątków chciałoby czytać z jednego pliku (mając ten sam deskryptor), mogłoby dojść do nieoczekiwanej sytuacji, w której oba wątki czytałyby to samo, mimo że nie powinny. Może się coś takiego wydarzyć, gdy wywoływane są takie operacje:

// Thread A
lseek(fd, 300, SEEK_SET);
read(fd, buf1, 100);

// Thread B
lseek(fd, 700, SEEK_SET);
read(fd, buf2, 100);

w kolejności A(lseek) -> B(lseek) -> A(read) -> B(read). Aby tego problemu uniknąć, można skorzystać z funkcji pread, w której dodatkowo przekazujemy offset, a cała operacja odczytu jest wykonywana atomowo:

// Thread A
pread(fd, buf1, 100, 300);

// Thread B
pread(fd, buf2, 100, 700);

Zadanie 6

Program echoclient-thread wczytuje plik tekstowy zadany z wiersza poleceń i dzieli go na linie zakończone znakiem \n. Następnie startuje podaną liczbę wątków, z których każdy wykonuje w pętli: nawiązanie połączenia, wysłanie ITERMAX losowych linii wczytanego pliku, zamknięcie połączenia. Wątki robią to tak długo, aż do programu nie przyjdzie sygnał SIGINT.

Twoim zadaniem jest tak uzupełnić kod, by program uruchamił nthreads wątków i poczekał na ich zakończenie. Czemu nie można go łatwo przerobić w taki sposób, żeby główny wątek czekał na zakończenie pozostałych wątków tak, jak robi się to dla procesów przy pomocy wait(2)?

Jedyna zmiana, jaką należy wykonać jest w main(): chcemy stworzyć nthreads wątków, a na koniec zaczekać, aż wszystkie pozostałe się wykonają. Uruchamiamy serwer (gotowy, z kolejnego zadania) ./echoserver-select <port>, później w osobnym terminalu ./echoclient-thread <plik> <nthreads> localhost <port> i powinniśmy zaobserwować coś takiego:

Server received 48 (48 total) bytes on fd 4
Server received 1 (49 total) bytes on fd 5
Server received 1 (50 total) bytes on fd 6
Server received 37 (87 total) bytes on fd 7
Server received 37 (124 total) bytes on fd 8
Server received 2 (126 total) bytes on fd 9
Server received 48 (174 total) bytes on fd 10
Server received 31 (205 total) bytes on fd 11
Server received 36 (241 total) bytes on fd 12
Server received 1 (242 total) bytes on fd 13
Server received 29 (271 total) bytes on fd 8
Server received 44 (315 total) bytes on fd 5
Server received 48 (363 total) bytes on fd 7
Server received 21 (384 total) bytes on fd 12
*** i tak dalej, do momentu wysłania ^C w kliencie ***

Uzupełniony kod z zadania:

int main(int argc, char **argv) {
  if (argc != 5)
    app_error("usage: %s <textfile> <nthreads> <host> <port>\n", argv[0]);

  size_t nthreads = atol(argv[2]);
  assert(nthreads > 0 && nthreads <= THREADMAX);

  char *text = readtext(argv[1]);

  c_nlines = splitlines(text, &c_lines);
  c_host = argv[3];
  c_port = argv[4];

  Signal(SIGINT, sigint_handler);

  /* TODO: Start threads and wait for them to finish. */
  pthread_t tid[nthreads];
  for (int i = 0; i < nthreads; i++)
    Pthread_create(&tid[i], NULL, thread, NULL);

  for (int i = 0; i < nthreads; i++)
    Pthread_join(tid[i], NULL);

  free(text);
}

Zadanie 7

Program echoserver-poll implementuje serwer usługi echo przy pomocy wywołania poll(2), ale bez użycia wątków i podprocesów. W kodzie wykorzystano wzorzec projektowy pętli zdarzeń (ang. event loop) do współbieżnej obsługi wielu połączeń sieciowych. Program echoserver-select robi to samo, ale przy pomocy wywołania select(2).

Twoim zadaniem jest uzupełnienie pliku źródłowego echoserver-poll.c. W pętli zdarzeń należy obsłużyć połączenia przychodzące, nadejście nowych danych na otwartych połączeniach i zamknięcie połączenia. Do przetestowania serwera użyj programu echoclient-thread z poprzedniego zadania.

  while (!quit)
  {
    int nready = Poll(fds, nfds, 500);
    if (nready == 0)
      continue;

    /* TODO: If listening descriptor ready, add new client to the pool. */
    if (fds[0].revents & POLLIN)
    {
      struct sockaddr_storage addr;
      socklen_t addrlen = sizeof(struct sockaddr_storage);
      int clientfd = Accept(listenfd, (SA *)&addr, &addrlen);

      static char hostname[MAXLINE], port[MAXLINE];
      Getnameinfo((SA *)&addr, addrlen, hostname, MAXLINE, port, MAXLINE, 0);
      addclient(clientfd, hostname, port);

      nready--;
    }

    /* TODO: Echo a text line from each ready connected descriptor.
     * Delete a client when end-of-file condition was detected on socket. */
    for (int i = 1; nready > 0; i++)
    {
      // Co z POLLHUP Hang up (output only)?
      if (fds[i].revents & POLLIN)
      {
        int bytes_read = clientread(i);
        if (bytes_read == 0)
        {
          delclient(i);
          i--; // Zostajemy w miejscu, bo tablica się zmniejszyła.
        }
        nready--;
      }
    }
  }

  printf("Server received %ld total bytes.\n", nbytes);
  return EXIT_SUCCESS;

Zadanie 8

Dla jakich parametrów wiersza poleceń obserwujesz niepoprawne zachowanie programów bug-1 i bug-2? Przeanalizuj kod źródłowy programów i wytypuj przyczyny błędów. Następnie zweryfikuj swoje podejrzenia: skompiluj programy z opcją -fsanitize=thread i uruchom je. Wyjaśnij znaczenie komunikatów diagnostycznych pochodzących z Thread Sanitizer, po czym pokaż jak naprawić błędy.

Zadaniem bug-1 jest zwiększenie wartości cnt w taki sposób, aby otrzymać dwukrotność tego, co przekazaliśmy jako argument na wejściu. Niestety przez to, że zmienna cnt jest volatile, nie zabezpieczamy się w żaden sposób przed sytuacją wyścigu (opisaną dokładniej w zadaniu 3), przez co otrzymujemy dla wielu iteracji wartość niezgodną z tą, której oczekujemy. Aby uzyskać dostęp do Thread Sanitizera, zmieniamy w Makefile flagi (wystarczy odkomentować linijke):

# bug-1: CC += -fsanitize=thread
# bug-2: CC += -fsanitize=thread

Po uruchomieniu bug-1 z "dużą" wartością, np. 500000, otrzymamy błędny wynik, a Thread Sanitizer wyświetli taki komunikat, mówiący o tym, że rzeczywiście w naszym kodzie występuje sytuacja wyścigu pomiędzy oczytami i zapisami wartości cnt przez oba wątki:

==================
WARNING: ThreadSanitizer: data race (pid=13899)
  Read of size 8 at 0x5633fe3a40d0 by thread T2:
    #0 thread /[dir]/lista_10/bug-1.c:13 (bug-1+0x1256)
    #1 <null> <null> (libtsan.so.0+0x29b3d)

  Previous write of size 8 at 0x5633fe3a40d0 by thread T1:
    #0 thread /[dir]/lista_10/bug-1.c:13 (bug-1+0x126d)
    #1 <null> <null> (libtsan.so.0+0x29b3d)

  Location is global 'cnt' of size 8 at 0x5633fe3a40d0 (bug-1+0x0000000040d0)

  Thread T2 (tid=13902, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x2be1b)
    #1 Pthread_create libcsapp/posix_thread.c:9 (bug-1+0x1400)
    #2 __libc_start_main <null> (libc.so.6+0x2409a)

  Thread T1 (tid=13901, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x2be1b)
    #1 Pthread_create libcsapp/posix_thread.c:9 (bug-1+0x1400)
    #2 __libc_start_main <null> (libc.so.6+0x2409a)

SUMMARY: ThreadSanitizer: data race /[dir]/lista_10/bug-1.c:13 in thread
==================

Aby naprawić ten błąd, należy zmienić definicję zmiennej cnt na taką:

static _Atomic long cnt = 0;

W ten sposób sprawimy, że wykonywane zmiany na zmiennej cnt będą atomowe, więc unikniemy sytuacji wyścigu, dzięki czemu program zwróci nam poprawną, oczekiwaną wartość.

Program bug-2 powinien wyświetlić komunikat Hello from thread <tid> dla każdego wątku, a więc powinny to być wartości od

$0$ do

$N$ (gdzie

$N$ to stała zdefiniowana w bug-2.c). Niestety tak się nie dzieje i w zbugowanej wersji programu będziemy otrzymywali mniej więcej coś takiego, jak przedstawiłem poniżej. Problemem jest to, że wartość zmiennej i jest przekazywana przez referencję, co powoduje problemy - w przypadku poniżej, nie otrzymujemy w ogóle informacji o wątku nr 1 oraz dwa razy otrzymujemy informacje o wątku 3.

Hello from thread 3
Hello from thread 2
Hello from thread 3
Hello from thread 0

Thread Sanitizer po uruchomieniu informuje o sytuacji wyścigu, dokładny komunikat jest taki:

==================
WARNING: ThreadSanitizer: data race (pid=17100)
  Write of size 4 at 0x7fff5e9b6c5c by main thread:
    #0 main /[dir]/lista_10/bug-2.c:16 (bug-2+0x12bb)

  Previous read of size 4 at 0x7fff5e9b6c5c by thread T1:
    #0 thread /[dir]/lista_10/bug-2.c:7 (bug-2+0x122a)
    #1 <null> <null> (libtsan.so.0+0x29b3d)

  Location is stack of main thread.

  Location is global '<null>' at 0x000000000000 ([stack]+0x00000001fc5c)

  Thread T1 (tid=17102, finished) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x2be1b)
    #1 Pthread_create libcsapp/posix_thread.c:9 (bug-2+0x134f)
    #2 __libc_start_main <null> (libc.so.6+0x2409a)

SUMMARY: ThreadSanitizer: data race /[dir]/lista_10/bug-2.c:16 in main
==================

Podobnie jak wyżej, wątki otrzymują zmienną i, jednak przed wyświetleniem tej wartości, zostaje ona już zmieniona. Aby to poprawić, każdemu wątkowi alokujemy pamięć na wartość iteratora pętli, dzięki czemu zawsze otrzyma poprawne dane:

  for (i = 0; i < N; i++) {
    int *i_val = malloc(sizeof(int));
    *i_val = i;
    Pthread_create(&tid[i], NULL, thread, i_val);
  }

Lista zadań nr 11

Przed przystąpieniem do rozwiązywania zadań zapoznaj się z dokumentem: The Second Extended File System Internal Layout. W zadaniach 1–5 rozważamy pierwszą korektę ext2 (ang. revision 1).

Zadanie 1

Wyznacz rozmiar bloku, liczbę i-węzłów i bloków przechowywanych w grupie bloków (ang. block group), liczbę wpisów tablicy deskryptorów grup bloków (ang. block group descriptor table) na podstawie pól superbloku (ang. superblock). Wymień składowe należące do grupy bloków oraz podaj ich rozmiar w blokach. Które grupy bloków przechowują kopie zapasową superbloku i tablicy deskryptorów grup bloków?

W ext2 blokiem nazywa się sektory, na które podzielone są partycje, dyski, pliki i urządzenia blokowe.

Większą jednostką od bloku jest grupa bloków, a więc kilka połączonych bloków. Grupy przydają się głównie w dwóch celach: zmniejsza się fragmentacja oraz wyszukiwanie danych jest szybsze.

Superblok to blok przechowujący metadane o systemie plików. Główna kopia superbloku jest przechowywana na offsecie 1024 bajtów od początku urządzenia. Kopie zapasowe można sprawdzić wywołując polecenie sudo dumpe2fs /dev/sdb4 | grep -i superblock:

  Primary superblock at 0, Group descriptors at 1-3
  Backup superblock at 32768, Group descriptors at 32769-32771
  Backup superblock at 98304, Group descriptors at 98305-98307
  Backup superblock at 163840, Group descriptors at 163841-163843
  Backup superblock at 229376, Group descriptors at 229377-229379
  Backup superblock at 294912, Group descriptors at 294913-294915
  Backup superblock at 819200, Group descriptors at 819201-819203
  Backup superblock at 884736, Group descriptors at 884737-884739
  Backup superblock at 1605632, Group descriptors at 1605633-1605635
  Backup superblock at 2654208, Group descriptors at 2654209-2654211
  Backup superblock at 4096000, Group descriptors at 4096001-4096003

Tablica deskryptorów grup bloków to tablica definująca parametry wszystkich grup bloków. Przechowywana jest w pierwszym bloku po superbloku. Ich kopie są przechowywane z każdą kopią superbloku.

Rozmiar bloku: block size = 1024 << s_log_block_size.
Liczba i-węzłów w grupie: s_inodes_per_group.
Liczba bloków w grupie: s_blocks_per_group.
Liczba wpisów tablicy deskryptorów grup bloków: s_blocks_count / s_blocks_per_group.

Każda grupa bloków składa się z kopii superbloku, kopii tablicy deskryptorów grpu bloków, bitmapy bloku, bitmapy i-węzła, tablicy i-węzłów i bloków z danymi. Rozmiar obu bitmap to 1 bajt dla każdej, tablica i-węzłów zajmuje s_inodes_per_group / inodes_per_block, gdzie inodes_per_block = block_size / s_inode_size, a resztę miejsca zajmują bloki z danymi.

Grupy bloków 0, 1 oraz grupy powstałe z potęg liczb 3, 5 i 7 przechowują kopię zapasową superbloku i tablicy deskryptorów grup bloków.

Zadanie 2

Podstawowymi operacjami na systemie plików są: wyzeruj lub zapal bit w bitmapie i-węzłów albo bloków, zmodyfikuj i-węzeł albo blok pośredni (ang. indirect block) albo blok danych. Wymień listę podstawowych operacji niezbędnych do realizacji funkcji: dopisującej

$n$ bloków na koniec pliku; dodającej plik do katalogu, gdy ten ma zbyt mało miejsca na dodanie wpisu. Zakładamy, że poszczególne kroki funkcji są zawsze wdrażane sekwencyjnie zapisami synchronicznymi. Zadbaj o to by funkcje nie naruszyły spójności systemu plików w przypadku awarii zasilania. Dopuszczamy powstawanie wycieków pamięci.

Blok pośredni (ang. indirect block) to blok zawierający wskaźniki na inne bloki pośrednie lub na bloki danych, zwykle jest używany przy pracy z dużymi plikami.

Zapis synchroniczny wykonywany jest za pomocą polecenia fsync(2) lub fdatasync(2). Oznacza to, że dane zapisywane są do deskryptora pliku fd na dysku (lub innym urządzeniu) w taki sposób, że po crashu systemu lub reboocie pliki nadal mogą zostać odzyskane.

Spójność systemu plików polega na zapisie plików o podobnym zastosowaniu w grupach (lub jakiejś przestrzeni nazw, która łączy te pliki).

Dopisanie

$n$ bloków na koniec pliku może odbywaćsię w następujący sposób. Wybieramy wolne bloki i zapalamy ich bity, aby zaznaczyć, że są używane. Następnie zapisujemy zawartość tych bloków i dodajemy bloki do i-węzła: w razie potrzeby tworzymy bloki pośrednie lub modyfikujemy aktualnie istniejące, a później aktualizujemy metadane i-węzła: wskaźniki na bloki, rozmiar i timestamp.

Aby dodać plik do katalogu, w którym nie ma miejsca, wybieramy jakiś wolny blok

$B$ i zapalamy bit użycia (tak jak wyżej). Załóżmy też, że korzystamy z linked list, a nie bardziej skomplikowanej struktury jak drzewo. W wybranym bloku

$B$ dodajemy wpis pliku do linked list, a więc ustawiamy odpowiedni i-węzeł inode, nazwę name, długość nazwy name_len i typ type, a następnie koniec bieżącego katalogu rec_len. Ostatnim zadaniem jest dodanie bloku

$B$ do i-węzła katalogu w taki sposób, jak wyżej.

Zadanie 3

Przy pomocy wywołania systemowego rename(2) można przenieść atomowo plik do katalogu znajdującego się w obrębie tego samego systemu plików. Czemu rename zakończy się błędem EXDEV kiedy próbujemy przenieść plik do innego systemu plików? Powtórz polecenia z zadania 2 dla funkcji przenoszącej plik między dwoma różnymi katalogami. Zakładamy, że w katalogu docelowym jest wystarczająco dużo miejsca na dodanie wpisu.

Atomowość polega na wykonaniu operacji w pełni, albo w ogóle. Oznacza to, że plik zostanie przeniesiony w całości, albo wcale, nie może się wydarzyć nic "pomiędzy". Sprawia to, że wykonywanie różnych akcji jest bezpieczniejsze, jako że mamy pewność, że nie zostanie wykonany jakiś ułamek całości.

rename może zakończyć się błędem EXDEV, gdy oldpath i newpath nie są zamontowane w tym samym systemie plików lub gdy są zamontowane w kilku miejscach - Linux zezwala na takie zachowanie, jednak samo działanie rename jest zdefiniowane w taki sposób, że nie pozwala na przenoszenie plików między różnymi punktami montowania.

Algorytmem wykorzystywanym do przenoszenia pliku między dwoma różnymi katalogami może być następujący ciąg instrukcji: zwiększamy licznik dowiązań i_links_count w i-węźle przenoszonego pliku, a jeśli w katalogu docelowym jest wyzerowany wpis (katalog pusty), to zmieniamy go na wpis pliku, który przenosimy. W przeciwnym wypadku dodajemy do katalogu docelowego wpis przenoszonego pliku i modyfikujemy poprzedni w taki sposób, aby nie wskazywał na koniec bloku. W poprzednim katalogu "usuwamy" wpis zmieniając wartość inode na

$0$ i zmieniamy licznik dowiązań w i-węźle tego pliku (przed przeniesieniem i po powinien być taki sam - jest to pewnego rodzaju niezmiennik, jako że nie wykonujemy kopii, to w systemie powinno być tyle samo dowiązań).

Zadanie 4

Przy pomocy wywołania systemowego unlink(2) można usunąć plik niebędący katalogiem. Powtórz polecenia z zadania 2 dla funkcji usuwającej plik zwykły z katalogu. Kiedy możliwe jest odwrócenie operacji usunięcia pliku tj. odkasowania (ang. undelete)? Zauważ, że usunięcie pliku nie odbiera procesom możliwości czytania jego zawartości, o ile go otworzyły przed wywołaniem unlink(2). Kiedy w takim razie plik zostanie faktycznie usunięty z dysku?

Algorytm na usuwanie pliku niebędącego katalogiem rozpoczyna się usunięciem wpisu z katalogu i zmniejszeniem licznika dowiązań i_links_count. Jeśli licznik ten wynosi

$0$, to zwalniamy i-węzeł oraz bloki, a gdy jest większy od

$0$, to nic nie robimy. Problemem mogą okazać się jednak awarie - jeśli nastąpi bezpośrednio po usunięciu wpisu z katalogu, to będziemy mieli zajęty i-węzeł, który nigdy nie zostanie zwolniony. Jeśli uda nam się zmniejszyć licznik, to wtedy zwolnienie będzie już możliwe (ale nadal niekoniecznie się to uda). Jeśli awaria nastąpi przed zwolnieniem bloków, to zostaniemy z blokami, których nie da się zwolnić.

Aby odkasować plik, musimy mieć pewność, że jego bloki nie zostały nadpisane - w przeciwnym przypadku odkasowanie będzie niemożliwe. Kolejnym warunkiem jest to, że i-węzeł nie mógł zostać nadpisany.

Pliki zostają całkowicie skasowane w momencie, gdy ich dane zostaną nadpisane innymi plikami lub gdy wszystkie deskryptory plików wskazujące na ten plik zostaną usunięte.

Zadanie 5

Wyjaśnij co robi system plików ext2 przy tworzeniu dowiązania twardego (ang. hard link) i symbolicznego (ang. symbolic link). Gdzie jest przechowywana zawartość dowiązania symbolicznego? Jak za pomocą dowiązania symbolicznego stworzyć w systemie plików pętlę? Kiedy jądro systemu operacyjnego ją wykryje i zwróci błąd ELOOP? Czemu pętli nie da się zrobić z użyciem dowiązania twardego?

Dowiązanie twarde (ang. hard link) to wskaźnik na i-węzeł pliku, wlicza się do licznika referencji do pliku. W i-węźle zwiększany jest licznik dowiązań i_links_count, a w katalogu tworzone jest mapowanie name - inode, czyli wiele wpisów pliku z różnych katalogów wskazuje na ten sam i-węzeł.

Dowiązanie symboliczne (ang. symbolic link) to dowiązanie kodujące ścieżkę, do której należy przekierować algorytm rozwiązywania nazw. Dla wszystkich dowiązań symbolicznych krótszych niż 60 bajtów dane są przechowywane w i-węźle.

Różnicę między dowiązaniami można przedstawić w taki sposób:

      +--------- inode     symlink
      |            |          |
 hard link         +-- file --+

Aby stworzyć pętlę, należy w dowolnym katalogu stworzyć dowiązanie symboliczne (flaga -s) do katalogu ., a więc tego, w którym się aktualnie znajdujemy, lub do katalogu ../[katalog]:

~/foo$ ln -s . link
~/foo$ ln -s ../foo/ link2

Z podręcznika path_resolution(7) na temat błędu ELOOP dowiadujemy się tyle, że zostaje on zwracany, gdy zostanie przekroczona maksymalna głębokość rekursji (dla symlinków).

Pętli nie można stworzyć za pomocą dowiązania twardego, gdyż struktura danych systemu plików jest skierowanym grafem acyklicznym, a dowiązanie twarde stworzyłoby cykl, co sobie przeczy.

Zadanie 6

Czemu fragmentacja systemu plików jest szkodliwym zjawiskiem? Zreferuj artykuł The new ext4 filesystem: current status and future plans. Opisz w jaki sposób odroczony przydział bloków (ang. delayed allocation) [§3.2] zapobiega powstawaniu fragmentacji. Wytłumacz jak zakresy (ang. extents) [§2.2] pomagają w ograniczaniu rozmiaru metadanych przechowujących adresy bloków należących do danego pliku. Czy po defragmentacji systemu plików ext4 liczba wolnych bloków może wzrosnąć? Jak mógłby wyglądać najprostszy algorytm defragmentacji [§3.3]?

Fragmentacja systemu plików to sytuacja, gdy dane plików są ułożone na dysku w nieciągły sposób, co spowalnia znacząco dostęp do danych.

Odroczony przydział bloków (ang. delayed allocation) zapisuje wszystkie żądania i wykonuje je dopiero w momencie, gdy wykonywany jest flush strony. W ten sposób zmniejszamy fragmentację i unikamy niepotrzebnej alokacji bloków dla plików tymczasowych.

Zakresy (ang. extents) pomagają w ograniczaniu rozmiaru metadanych przechowujących adresy bloków należących do danego pliku. Wykorzystuje je system plików ext4. Pole zakresu zajmuje 48 bitów i może reprezentować

$2^{15}$ sąsiadujących ze sobą bloków. Każdy węzeł w drzewie zaczyna się nagłówkiem, który zawiera liczbę poprawnych wpisów w węźle. Sposób, w jaki zakresy pomagają w ograniczaniu rozmiaru metadanych jest dość prosty: tworzony jest tymczasowy i-węzeł, a następnie alokowany w nim jest ciągły zakres. Następnie dane są kopiowane z oryginalnego i-węzła do tymczasowego, do czego wykorzystywany jest odroczony przydział bloków. Na samym końcu przepinane są wskaźniki na bloki z tymczasowego i-węzła do oryginalnego. W taki sposób odbywa się defragmentacja, dzięki której możemy uzyskać więcej wolnych bloków - używane będzie mniej zakresów, niż poprzednio. Poniższy schemat przedstawia układ drzewa zakresów:

Zadanie 7 TODO

Przy użyciu programu debugfs(8) dla wybranej instancji systemu plików ext4 (np. partycja przechowująca główny system plików Twojej instalacji systemu Linux) pokaż:

• fragmentację systemu plików (freefrag) i informacje o grupach bloków (stats),
• zakresy bloków z których składa się wybrany duży plik (extents),
• że dowiązanie symboliczne może być przechowywane w i-węźle (idump),
• do jakiego pliku należy wybrany blok (blocks, icheck, ncheck),
• reprezentację liniową małego katalogu (bdump).

Ostrzeżenie! Narzędzie debugfs działa domyślnie w trybie tylko do odczytu, więc możesz go bezpiecznie używać na swoim komputerze. Trybu do odczytu i zapisu używasz na własną odpowiedzialność!

Zadanie 8

Przeczytaj krytykę kluczowej idei systemu Unix, tj. A Unix File Is Just a Big Bag of Bytes. Na podstawie Resource Fork wyjaśnij czym były dodatkowe zasoby pliku w historycznych systemach MacOS.

Jaką postać mają rozszerzone atrybuty pliku xattr(7)? Pobierz z internetu plik przy pomocy przeglądarki Chrome, a następnie wyświetl jego rozszerzone atrybuty przy pomocy polecenia getfattr(1). Następnie policz sumę md5 wybranego pliku i przypisz ją do atrybutu user.md5sum poleceniem setfattr(1), po czym sprawdź czy operacja się powiodła.

Resource fork to zestaw ustrukturyzowanych danych przechowywanych w data forku lub sekcji pliku. Przechowuje on informacje takie jak ikony, kształty okienek, definicje menu i ich zawartość albo kod aplikacji, np. tekst przechowywany jest w data forku, a obrazki w resource forku.

System plików Macintosh (MFS) realizował trzy główne założenia:

• Służył do przechowywania wszystkich danych graficznych na dysku, dopóki nie były potrzebne, a następnie pobrane, rysowane na ekranie i wyrzucane. Ten wariant oprogramowania pamięci wirtualnej pomógł Apple zmniejszyć wymagania dotyczące pamięci z 1 MB w Apple Lisa do 128 KB w Macintoshu.
• Ponieważ wszystkie obrazy i tekst były przechowywane osobno w forku zasobów, można było go użyć, aby umożliwić nieprogramistom na tłumaczenie aplikacji na rynek zagraniczny, proces ten nazywany jest internacjonalizacją i lokalizacją.
• Można było go wykorzystać do dystrybucji prawie wszystkich komponentów aplikacji w jednym pliku, zmniejszając bałagan i upraszczając instalację i usuwanie aplikacji.

Resource fork ułatwiał przechowywanie informacji potrzebnych systemowi np. do wyświetlenia odpowiedniej ikony dla pliku. Dostęp do nich działał podobnie do wydobywania rekordów z bazy danych, czasem służyły one do przechowywania metadanych.

Rozszerzone atrybuty pliku to rozszerzenia zwykłych atrybutów powiązanych ze wszystkimi inode'ami w systemie, często są używane do zapewnienia dodatkowej funkcjonalności systemu plików, na przykład zwiększenia ochrony poprzez listę kontroli dostępu (ang. Access Control List). Atrybuty te mają postać name:value i powiązane są permamentnie z plikami i katalogami, podobnie do environment strings związanych z procesami. Mogą być one zdefiniowane lub nie, a jeżeli atrybut jest zdefiniowany, to jego wartość może być pusta lub niepusta. Ich nazwy są null-terminated, zawsze podawane z uwzględnieniem całej przestrzeni nazw do której należą, tzn. namespace.attribute. Atrybuty te działają atomowo, getxattr(2) odczytuje całą wartość atrybutu, a setxattr(2) zamienia poprzednią wartość na nową.

Aby odczytać wszystkie atrybuty pliku (włącznie z rozszerzonymi) należy użyć pierwszego polecenia, a aby dodać sumę md5 w postaci name:value, należy skorzystać z drugiego. Flaga -d oznacza dump, tzn. wypisanie wszystkich wartości, -n to name, -v to value. Obliczana suma md5 dla danego pliku jest przekazywana jako wartość zmiennej powstałej w subshellu.

$ getfattr -d [plik]
$ setfattr -n user.md5sum -v $(md5sum [plik]) [plik]

Zadanie 9 (bonus) TODO

Na podstawie §3 artykułu A Directory Index for Ext2 opisz strukturę danych HTree i operację wyszukiwania wpisu katalogu o zadanej nazwie. Następnie wyświetl reprezentację HTree dużego katalogu, np. /var/lib/dpkg/info, używając polecenia htree programu debugfs(8).

Lista zadań nr 12

Przed rozwiązywaniem zadań warto zapoznać się z podrozdziałem 2.3 Modern Operating Systems oraz rozdziałami Locks, Semaphores, Common Concurrency Problems Arpaci-Dusseau.

Zadanie 1 TODO

Zmienne współdzielone to zmienne, do których przynajmniej dwa różne wątki robią referencję. Takimi zmiennymi w podanym programie są:

• strtab, która jest dostępna dla wszystkich wątków (zmienna globalna typu static),
• cnt, która jest statyczną zmienną lokalną, dla której istnieje tylko jedna instancja współdzielona przez wątki utworzone przez pthread_create(),
• argv[0], gdyż przekazujemy wartość 0 jako argument *thread przez pthread_create(), ponadto strtab wskazuje na argv, czyli strtab[myid] = argv[0],
• myid, a dokładniej jego adres, jest przekazywany w pthread_create() i we wszystkich wątkach jest wykonywany dostęp do tej wartości. Zmienna ta jest współdzielona pomimo słowa kluczowego __thread, który sprawia, że każdy wątek powinien mieć swoją instancję zmiennej myid.

Wyścig (ang. data race) to sytuacja, w której co najmniej dwa wątki mają dostęp do zmiennej współdzielonej w tym samym czasie i przynajmniej jeden z wątków próbuje modyfikować tę zmienną. Finalny wynik zależy od tego, w jakiej kolejności zostaną wykonane działania na takiej zmiennej. Źródłem wyścigów są dwie zmienne:

• cnt, gdyż wątki mogą się tak przepleść, że więcej niż jeden wątek odczyta i zapisze tę samą wartość. W taki sposób każdy kolejny wątek zwróci nieprawidłowy (nieoczekiwany) wynik.
• myid, gdyż zanim nowy wątek zostanie przypisany, to możliwe jest, że jego rodzic zmieni już swoje myid.

Zadanie 2 TODO

Sekcja krytyczna (ang. critical section) to miejsce w programie współbieżnym, w którym proces wykonuje operacje na współdzielonej pamięci. Sprawia to, że taki kod może być źródłem wyścigów. Aby rozwiązać problem sekcji krytycznej, można założyć, że:

1. żadne dwa procesy nie mogą jednocześnie przebywać wewnątrz swoich sekcji krytycznych (w taki sposób zapobiegamy wyścigom),
2. nie można przyjmować żadnych założeń dotyczących szybkości lub liczby procesorów (program powinien działać niezależnie od sprzętu i zawsze zwracać dobry wynik),
3. proces działający wewnątrz swojego regionu krytycznego nie może blokować innych procesów (procesy blokujemy tylko przy wejściu do swojej sekcji krytycznej),
4. żaden proces nie powinien oczekiwać w nieskończoność na dostęp do swojego regionu krytycznego (nie chcemy głodzić procesów).

Wyłączanie przerwań (ang. interrupt disable) to sposób rozwiązania problemu sekcji krytycznych. Polega ono na wyłączeniu obsługi przerwań w momencie, gdy proces wchodzi do swojej sekcji krytycznej, a następnie po włączeniu obsługi przerwań, gdy proces z niej wyjdzie. Działa to dlatego, że zmiana procesu odbywa się tylko poprzez przerwania, a więc wyłączając przerwania pozbawiamy możliwość zmiany procesu w trakcie wykonywania sekcji krytycznej.

Niestety to podejście jest dość ryzykowne w przypadku, gdyby użytkownik miał do niego dostęp. W sprzęcie jednoprocesorowym mogłoby dojść do sytuacji, w której obsługa przerwań zostałaby wyłączona, po czym nie moglibyśmy jej uruchomić ponownie, co sprawiłoby, że komputer się zawiesi. W przypadku systemu z wieloma procesorami to rozwiązanie nie zadziała, gdyż wyłączanie przerwań odbywa się tylko na jednym procesorze, a więc wątki z pozostałych procesorów nadal będą miały dostęp do współdzielonej pamięci.

Drobnoziarniste blokowanie (ang. fine-grained locking) to sposób pracy przy sekcjach krytycznych. Polega on na wydzielaniu pojedynczych zmiennych i struktur, a następnie utworzeniu dla każdej z nich osobnej blokady. Dzięki temu, przy wielu sekcjach krytycznych wiemy, że w każdej z nich przebywa tylko jeden proces, a więc wiele procesów może wykonywać operacje ze swoich sekcji krytycznych. W ten sposób zwiększamy możliwość zrównoleglenia danych partii programu.

Wykres przedstawiony poniżej (źródło: wikipedia) przedstawia prawo Amdahla. Możemy wywnioskować, że im więcej fragmentów programu można zrównoleglić oraz im więcej procesorów możemy użyć, tym szybciej działać będzie nasz program.

Zadanie 3 TODO

Instrukcja atomowa to instrukcja, której wykonanie nie może zostać przerwane, a więc dopóki się w całości nie wykona, to nic innego nie może się wydarzyć.

int compare_and_swap (int* reg, int oldval, int newval) {
  int old_reg_val = *reg;
  if (old_reg_val == oldval) 
    *reg = newval;
  return old_reg_val;
}

Blokada wirująca (ang. spin lock) to sposób na zatrzymanie wątków czekających na dostanie blokady w pętli while. Stąd bierze się również nazwa tej blokady - pętla wiruje cały czas, dopóki wyznaczony warunek nie zostanie spełniony, co umożliwi dalsze wykonanie programu.

typedef int spin_t;

void lock(spin_t *lock) {
  while (compare_and_swap(lock, 0, 1) == 1); // this semicolon is crucial!
}

void unlock(spin_t *lock) {
  *lock = 0;
}

Blokada sprawiedliwa (ang. fair lock) to blokada, w której każdy wątek próbujący wejść w sekcję krytyczną i założyć blokadę powinien mieć takie same szanse na wykonanie tego. W blokadzie sprawiedliwej nie występuje zjawisko głodzenia. Niestety blokada wirująca nie jest sprawiedliwa, bo można znaleźć taki ciąg instrukcji, dla których pewien wątek zostanie zagłodzony.

Wywłaszczenie wątku będącego w sekcji krytycznej chronioną blokadą w przestrzeni użytkownika może sprawić, że wszystkie wątki zostaną zablokowane, a więc cały program się zawiesi.

Zadanie 4 TODO

Warunki konieczne do powstania zakleszczenia to:

• wzajemne wykluczanie (ang. mutual exclusion) - wątki przejmują wyłączną kontrolę nad zasobami, których potrzebują (np. używając blokady)
• podtrzymanie własności (ang. hold-and-wait) - wątki nie zwalniają zasobów im przyznanym, oczekując na kolejne zasoby
• pierwszeństwo (ang. no preemption) - zasób zostaje przejęty i nie może zostać odebrany
• wzajemne oczekiwanie (ang. circular wait) - istnieje taki cykl: dwa wątki potrzebują jakiegoś zasobu i trzymają inny. Aby jeden wątek otrzymał zasób, musi zwolnić poprzedni, taka sama sytuacja występuje dla drugiego wątku:
  

Zakleszczeniom można oczywiście zapobiegać (ang. deadlock prevention), co przedstawię poniżej.

1. Aby zapobiec wzajemnemu oczekiwaniu można stworzyć taki program, aby zasoby nie były przejmowane w różnej kolejności w zależności od wykonania programu. Polega to na tym, że jeśli są dwie blokady, L1 oraz L2, to aby zapobiec zakleszczeniu, zawsze L1 będzie wykorzystane przed L2. Dzięki temu dwa wątki nie będą na siebie wzajemnie czekać.
2. Innym sposobem jest założenie wszystkich blokad na zasoby jednocześnie, atomowo. W taki sposób albo nie będziemy musieli czekać na inne zasoby, mając wszystkie na własność, albo będziemy musieli poczekać na nie wszystkie. Jest to przeciwdziałanie podtrzymaniu własności.
3. Kolejnym sposobem jest odrzucenie żądania blokady bez wywłaszczenia. Możemy używać instrukcji, które wracają nawet jeśli na zasób jest nałożona blokada. Wtedy, zamiast czekać na zwolnienie tego zasobu, możemy zwolnić zasoby przechowywane przez nas. Następnie spróbujemy uzyskać dostęp do innego zasobu w innym momencie. Niestety nie jest to rozwiązanie optymalne, gdyż może skutkować powstaniem livelocka.
4. Następnym sposobem, niewymagającym zbyt dużego wyjaśnienia jest tworzenie struktur w taki sposób, aby nie wymagały blokad. Jeżeli nie potrzebujemy blokad, to nie powstanie zakleszczenie.
5. Ostatnim sposobem jest podejście od strony schedulera. Jeżeli wiemy, w jakiej kolejności zostaną wykonywane żądania dostępu do zasobów przez wątki, możemy tak ułożyć ich wykonanie, aby uniknąć zakleszczenia.

Niestety nie wszystkie z tych sposobów znajdują zastosowania w praktyce. Są to rozwiązania nr 2., gdyż nie zawsze wiemy o wszystkich blokadach od razu, ponadto blokowanie wszystkich zasobów jest bardzo niewydajne; oraz rozwiązanie nr 5. Nie potrafimy przewidzieć przyszłości, a więc dla skomplikowanych zadań takie podejście jest prawie niemożliwe.

Dobrymi rozwiązaniami są pozostałe. Najprostszą metodą jest sposób pierwszy - wymaga to tylko przemyślenia, lecz po dobrej implementacji unikniemy problemu zakleszczeń. Sposób trzeci może powodować livelock, jednak jest możliwość rozwiązania go. Sposób czwarty jest czasem używany, np. w implementacji linked list. Nie należy on do najłatwiejszych, ale się sprawdza.

Zadanie 5 TODO

shared boolean blocked [2] = { false, false };
shared int turn = 0;

void P (int id) {
  while (true) {
    blocked[id] = true;
    while (turn != id) {
      while (blocked[1 - id])
        continue;
      turn = id;
    }
    /* put code to execute in critical section here */
    blocked[id] = false;
  }
}

void main() { parbegin (P(0), P(1)); }

Zadanie 6 TODO

Zadanie 7 TODO

Zadanie 8 TODO