# 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](http://pages.cs.wisc.edu/~remzi/OSTEP/threads-intro.pdf), [Interlude: Thread API](http://pages.cs.wisc.edu/~remzi/OSTEP/threads-api.pdf), [Event-based Concurrency](http://pages.cs.wisc.edu/~remzi/OSTEP/threads-events.pdf). Całość tej książki można znaleźć na jej [oficjalnej stronie](http://pages.cs.wisc.edu/~remzi/OSTEP/#book-chapters).
### Zadanie 1
:::info
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ść?
:::
:::danger
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*](https://en.wikipedia.org/wiki/Bit_blit) 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:
```c=
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:
```c=
# 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
:::info
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](https://people.eecs.berkeley.edu/~sseshia/fmee/lectures/TemporalLogicIntro.pdf), 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ąć *deadlock*a, 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 *deadlock*a, 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, \ldots, 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 \leq i \leq 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, \ldots, 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, \ldots, 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 \leq 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
:::info
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ść.
```c=
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.
:::
:::danger
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 *lock*ami, 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 \ldots \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 \ldots \to P_k^1 \to P_1^2 \to P_2^2 \to \ldots \to P_k^2 \to P_1^13 \to P_2^3 \to \ldots 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
:::info
Podaj odpowiedniki funkcji [`fork(2)`](https://man7.org/linux/man-pages/man2/fork.2.html), [`exit(3)`](https://man7.org/linux/man-pages/man3/exit.3.html), [`waitpid(3)`](), [`waitpid(2)`](https://man7.org/linux/man-pages/man2/waitpid.2.html), [`atexit(3)`](https://man7.org/linux/man-pages/man3/atexit.3.html) oraz [`abort(3)`](https://man7.org/linux/man-pages/man3/abort.3.html) 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.
```c
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`.
```c
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.
```c
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)`.
```c
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ć.
```c
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.
```c
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
:::info
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)`](https://man7.org/linux/man-pages/man2/fork.2.html) lub [`execve(2)`](https://man7.org/linux/man-pages/man2/execve.2.html) lub [`_exit(2)`](https://man7.org/linux/man-pages/man2/_exit.2.html)?
* 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)`](https://man7.org/linux/man-pages/man2/pipe.2.html), 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](https://stackoverflow.com/questions/976015/why-do-i-need-to-close-fds-when-reading-and-writing-to-the-pipe/976087)), 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:
```c=
// 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:
```c=
// Thread A
pread(fd, buf1, 100, 300);
// Thread B
pread(fd, buf2, 100, 700);
```
### Zadanie 6
:::info
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)`](https://man7.org/linux/man-pages/man2/wait.2.html)?
:::
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:
```c=106
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
:::info
Program `echoserver-poll` implementuje serwer usługi `echo` przy pomocy wywołania [`poll(2)`](https://man7.org/linux/man-pages/man2/poll.2.html), 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)`](https://man7.org/linux/man-pages/man2/select.2.html).
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.
:::
```c=
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
:::info
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](http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/35604.pdf), 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 Sanitizer*a, 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ą:
```c=5
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:
```c=16
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](https://www.nongnu.org/ext2-doc/ext2.html). W zadaniach 1–5 rozważamy pierwszą korektę `ext2` *(ang. revision 1)*.
### Zadanie 1
:::info
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
:::info
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
:::info
Przy pomocy wywołania systemowego [`rename(2)`](https://man7.org/linux/man-pages/man2/rename.2.html) 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
:::info
Przy pomocy wywołania systemowego [`unlink(2)`](https://man7.org/linux/man-pages/man2/unlink.2.html) 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)`](https://man7.org/linux/man-pages/man2/unlink.2.html). 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
:::info
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)`](https://man7.org/linux/man-pages/man7/path_resolution.7.html) 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
:::info
Czemu **fragmentacja systemu plików** jest szkodliwym zjawiskiem? Zreferuj artykuł [The new ext4 filesystem: current status and future plans](https://www.kernel.org/doc/ols/2007/ols2007v2-pages-21-34.pdf). 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
:::info
Przy użyciu programu [`debugfs(8)`](https://man7.org/linux/man-pages/man8/debugfs.8.html) 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
:::info
Przeczytaj krytykę kluczowej idei systemu Unix, tj. [A Unix File Is Just a Big Bag of Bytes](http://www.catb.org/~esr/writings/taoup/html/ch20s03.html#id3015538). Na podstawie [Resource Fork](https://en.wikipedia.org/wiki/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 fork*u 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 fork*u, a obrazki w *resource fork*u.
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)*](https://pl.wikipedia.org/wiki/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 *subshell*u.
```=
$ getfattr -d [plik]
$ setfattr -n user.md5sum -v $(md5sum [plik]) [plik]
```
### Zadanie 9 (bonus) TODO
:::info
Na podstawie §3 artykułu [A Directory Index for Ext2](https://www.kernel.org/doc/ols/2002/ols2002-pages-425-438.pdf) 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)`](https://man7.org/linux/man-pages/man8/debugfs.8.html).
:::
## 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
:::success
:::
**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
:::success
:::
**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](https://en.wikipedia.org/wiki/Amdahl%27s_law))* 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
:::success
:::
**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ć.
```c=
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.
```c=
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
:::success
:::
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 *livelock*a.
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
:::success
```c=
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
:::success
:::
### Zadanie 7 TODO
:::success
:::
### Zadanie 8 TODO
:::success
:::
Sign in with Wallet
Connect another wallet