## Systemy Operacyjne - Lista 13

### Zadanie 1

**Odwrócenie priorytetów** - to sytuacja w której zadanie o wysokim priorytecie jest zastępowane przez zadanie o niższym priorytecie, co odwraca przypisane priorytety zadań i narusza model priorytetów. Dobrze ilustruje to obrazek z wykładu:
Dochodzi tutaj do sytuacji w której swoje zadanie wykonuje task o niższym priorytecie, nakładając jednocześnie blokadę na jakiś zasób, który dzieli z zadaniem o wysokim priorytecie. W momencie pojawienia się zadania o wyższym priorytecie, TH1 oddaje czas procesora zadaniu o wyższym priorytecie, następnie wchodzi zadanie TH3 o najwyższym priorytecie, które potrzebuje dostępu do zasoby, który został zablokowany przez TH1, w związku z czym TH3 idzie spać, teraz następuje ODWRÓCENIE PRIORYTETÓW, ponieważ czas procesora zostaje oddany do zadania o priorytecie TH2, ponieważ jest on obecnie najwyższym "aktywnym" priorytetem, który może się wykonać. Przy okazji może tutaj dojść do sytuacji w której TH1 nigdy (lub za bardzo długo) dopiero się wykona, bo jeśli nastąpi seria zadań TH2, to TH1 się nie wykona więc nie będzie mógł zwolnić zasobu.

**Dziedziczenie priorytetów** to metoda, która rozwiązuje powyższy problem, mianowicie - gdy dochodzimy do wykonania TH3 i nie ma on dostępu do zasobu, "pożycza" swój priorytet zadaniu TH1, tak aby mogło się wykonać (i zwolnić potrzebny zasób), a po wykonaniu zadania TH1 wraca do swojego starego priorytetu i wszystko jest z powrotem w pyte.

**Mutex** - Wolne tłumaczenie Pana ze stack'a:
Kiedy mamy w pracy gorącą dyskusję, używam gumowego kurczaka, którego trzymam w biurku na specjalne okazje takie jak ta. Sytuacja jest dosyć prosta, w momencie w którym trzymam kurczaka tylko ja mogę mówić. Jako osoba bez kurczaka możesz tylko podnieść rękę i zasygnalizować, że chcesz kurczaka otrzymać. W momencie w którym kończysz mówić, oddajesz kurczaka do moderatora rozmowy, a on przekazuje go następnej osobie, która chciała mówić. Dzięki temu osoby się wzajemnie nie przekrzykują i każda ma możliwosć wypowiedzenia swojego zdania.

*W jakim celu mutex pamięta właściciela?*
Mutex pamięta swojego właściciela (czyli wątek który trzyma blokadę) aby uniknąć sytuacji w której kilka wątek próbuje zwolnić blokadę, której już nie posiada. Dzięki temu można uniknąć błędów spowodowanych przez nieprawidłowe zwolnienie zamka, co mogłoby prowadzić do nieoczekiwanych błędów. Gdy blokadę próbuje zwolnić wątek, który jej nie posiada program wywala się na głupi ryj.

*W jaki sposób należy rozszerzyć implementację operacji `mutex_lock` i `mutex unlock` żeby nie dopuścić do odwrócenia priorytetów?*

A) Idead implementacji polega na tym, aby pamiętać priorytet każdego wątku, który trzyma blokadę, i ustawić go na poziom wyższy niż priorytet wątku, który próbuje uzyskać blokadę. Następnie, po zwolnieniu blokady, należy przywrócić pierwotny priorytet wątku, który trzymał blokadę.

Implementuje się to w następujący sposób, korzystamy z dodatkowych procedur:

`pthread_mutexattr semaphore->value = value;_getprotocol()`
`pthread_mutexattr_setprotocol()`
`pthread_mutexattr_init()`

Funkcje pthread_mutexattr_getprotocol() i pthread_mutexattr_setprotocol() odpowiednio pobierają i ustawiają atrybut protokołu obiektu atrybutów muteksu wskazywanego przez attr, który został wcześniej utworzony przez funkcję pthread_mutexattr_init().

atrtybut 'protocol' określa protokół, który ma być wykorzystywany:

PTHREAD_PRIO_NONE - nie ma wpływu
PTHREAD_PRIO_INHERIT - gdy ma te protokuł i blokuje mutexa dla wątku o wyższym priorytecie, powinien mu się zmienić priorytet na adekwatny

PTHREAD_PRIO_PROTECT - nie wiem czy rozumiem ale chyba wykonuje się na najwyższym priorytecie i

*Czy semafory są odporne na problem odwrócenia priorytetów?* - Nie, semafory nie zawierają wbudowanego mechanizmu dziedziczenia priorytetów.

### Zadanie 2

#include <pthread.h>

// Zakładamy chyba wersję z counting semaphore, więc działa to tak,
// że value oznacza ilość dostępnych instancji zasobu:

// wait dekrementuje value semafora i oddelegowuje zasób do procesu,
// gdy wartość semafora spada do 0, znaczy to, że żaden zasób nie
// jest dostępny a proces zostanie zablokowany

typedef struct Sem {
  pthread_mutex_t mutex;   // mutex (taka dosyć skomplikowana strukturka)
  pthread_cond_t  waiters; // kolejka wątków oczekująca na jakiś warunek
  int value;                   
} Sem_t;



int sem_init(Sem_t *sem, unsigned int value) {

  if (sem == NULL) {
    errno = EINVAL;
    return -1;
  }

  if (value > SEM_MAX_VALUE || value < 0) {
    errno = EINVAL;
    return -1;
  }

  sem->value = value;
  
  //Inicjujemy mutexa z defaultowymi wartościami
  pthread_mutex_init(&semaphore->mutex, NULL);
  //Inicjujemy zmienną warunkową (kolejkę wątków ...)
  pthread_cond_init(&semaphore->waiters, NULL);

}

/* zablokuj semafor */
void sem_wait(Sem_t * sem) {
  pthread_mutex_trylock(&semaphore->mutex);
  
  do {
      if (semaphore->value > 0) {
          break;
      }
      pthread_cond_wait(&semaphore->waiters, &semaphore->mutex)
      //blokuje wątek do chwili, kiedy jakiś inny wątek wyśle do niego sygnał.
      yield() ??
  }

  semaphore->value--;
  pthread_mutex_unlock(&semaphore->mutex);

}

/* odblokuj semafor */
void sem_post(Sem_t * sem) {

  pthread_mutex_trylock(&semaphore->mutex);    // blokujemy mutexa
  semaphore->value++;                       // zwracamy zasób  
  pthread_cond_signal(&semaphore->waiters); // odblokowanie zmiennej
  // warunkowej (afaik przywracamy po prostu do życia któregoś oczekującego)
  // żeby wziął sobie zameczek
  pthread_mutex_unlock(&semaphore->mutex);  // odblokowujemy mutexa

}

### Zadanie 3

**Futex (fast user space mutex)** - linuxowy mechanizm sinchronizacji działający w przestrzeni użytkownika. Zaletą tego mechanizmy jest unikanie używania wywołań systemowych (które są bardzo kosztowne) w momencie w którym istnieje mała rywalizacja.

int futex(int *uaddr, int futex_op, int val, 
          const struct timespec *timeout, /* or: uint32_t val2 */
          int *uaddr2, int val3);

- *uaddr - wskaźnik na futex word
- futex_op - operacja jaka ma zostać wykonana na futexie
- val - wartość, której znaczenie i przeznaczenie zależy od operacji
- timeout, uaddr2, val3 - opcjonalne argumenty, wymagane przez niektóre operacje

w zbiór futex_op wchodzą operacje FUTEX_WAIT oraz FUTEX_WAKE

- **FUTEX_WAIT** - ta operacja sprawdza czy wartość futex word'a pod wskaźnikiem `uadrr` nadal zawiera oczekiwaną wartość `val` i jeśli tak, to usypia wątek na futexie w oczekiwaniu na `FUTEX_WAKE`. Jeśli wartość jest różna (uadrr =/= val), to natychmiastowo zwraca błąd EAGAIN.

- **FUTEX_WAKE** - Budzi co najmniej `val` wątków oczekujących na futexie wskazanych przez `uaddr`. Zazwyczaj będzie to 1 (obudź jednego oczekującego) lub INT_MAX (obudź wszystkich oczekujących). Nie ma żadnej gwarancji co do tego, którzy oczekujący zostaną obudzeni (np. nie ma gwarancji tego, że najpierw budzą się te z większym priorytetem).

**Blokady adaptacyjne (ang. adaptive locks)** - to taka blokada, która nie posiada konkretnej stategii oczekiwania na zwolnienie zasobu, w zależności od obciążenia komputera, tego ile wątków rywalizuje o zasób itd. Czyli np. wybiera spin lock'a, gdy niewiele zasobów walczy o dostęp, kiedy może być problem z kolejnością dostępów to strzeli sobie jakąś blokadę sprawiedliwą i gra gitara, ładnie to brzmi, nie wiem jak jest zaimplementowane i nie zamierzam szukać bo 5:58 na sikorze, 5 zadań przede mną, a psycha to już siedzi od 2:30.

*Czym róźni się od sleep locka?*
No to jak wyżej, sleep lock gdy nie może uzyskać dostępu do zasobu to idzie w spanko a adaptive lock być może w tym momencie jest spin lockiem i się kręci

Dobra nie mówiłem nic wcześniej, jednak ogarniamy implementację ...

#include "pthread_impl.h"

/* This lock primitive combines a flag (in the sign bit) and a
 * congestion count (= threads inside the critical section, CS) in a
 * single int that is accessed through atomic operations. The states
 * of the int for value x are:
 *
 * x == 0: unlocked and no thread inside the critical section
 *
 * x < 0: locked with a congestion of x-INT_MIN, including the thread
 * that holds the lock
 *
 * x > 0: unlocked with a congestion of x
 *
 * or in an equivalent formulation x is the congestion count or'ed
 * with INT_MIN as a lock flag.
 */
    
// Czyli łączymy flagę na ostatnim bicie i &&'ujemy ją z "liczbą zatłoczeń".
// Jeśli x == 0 to flaga odblokowana i 0 wątków w sekcji krytycznej
// Jeśli x < 0 to zablokowany z zatłoczeniem na poziomie x-INT_MIN
// Jeśli x > 0 Odblokowany z zatłoczeniem na poziomie x
    
//czyli chyba te 32 bity są zrobione tak, że pierwszy to flaga, a pozostałę to "liczba zatłoczenia", czyli liczba bitów uśpionych na tym futexie

void __lock(volatile int *l)
{
    // need_lock = 1 (tak przyjmujemy, wywalam części odnoszące się do tego bo przy tym założeniu są useless)
	int current = a_cas(l, 0, INT_MIN + 1);
    // a_cas to COMPARE AND SWAP, ciekawe jak       // się można było tego domyślić ...
	if (!current) return;
    // jeśli blokada była wolna to oznaczamy ją 
    // jako zajętą i ustawiamy licznik zatłoczenia na 1 (INT_MIN + 1 bo liczymy sobie w taki sposób)

//zwracamy old_reg_val, czyli zawsze zwracamy l,
//jeśli l = 0 (czyli blokada była zajęta, to się //wywalamy), wpp. idziemy dalej, current = l, a //jeśli l (old_reg_val) == 0 (oldval) to l //dostaje INT_MIN + 1
    
	for (unsigned i = 0; i < 10; ++i) {
		if (current < 0) current -= INT_MIN + 1;
// tutaj jeśli current < 0 (czyli nasze zadane l), to current = l - INT_MIN + 1 (wartość l na wejściu)
		int val = a_cas(l, current, INT_MIN + (current + 1));
        
		if (val == current) return;
		current = val;
// Sprawdzamy czy blokada była zajęta, jeśli nie, to zwiększamy licznik zatłoczenia i zwracamy, a jeśli nie to pętla leci sobie dalej z nową wartością
	}
    
    // jeśli nie udało się spin lockiem, to trafiamy do kolejki wątków oczekujących w kolejce po blokadę
	current = a_fetch_add(l, 1) + 1;

    
	for (;;) {
    // Skoro wiemy, że ktoś trzyma blokadę, to jedyną sensowną rzeczą jest pójście w spanko
		if (current < 0) {
    // sprawdzamy jeszcze raz czy blokada się nie zwolniła i jeśli nie to iddziemy spać
			__futexwait(l, current, 1);
			current -= INT_MIN + 1;
		}
    //compare and swap'em sprawdzamy czy blokada jest już wolna, jeśli tak to fajnie i się stad zawijamy a jeśli nie to pętlimy się dalej
		int val = a_cas(l, current, INT_MIN + current);
		if (val == current) return;
		current = val;
	}
}

void __unlock(volatile int *l)
{
    // jeśli nie jesteśmy jedynym czekającym wątkiem, to budzimy resztę chłopaków
	if (l[0] < 0) {
		if (a_fetch_add(l, -(INT_MIN + 1)) != (INT_MIN + 1)) {
			__wake(l, 1, 1);
		}
	}
}

*Wartość blokady wyraża stan blokady oraz poziom zatłoczenia, czyli to ile wątków czeka*

*Gdy występuje wysokie współzawodnictwo, to istnieje mała szansa, że podczas spinlocka uda nam się zakosić blokadę dla siebie, więc częściej wątki będą usypiane*

*Wątki są usypiane tylko jeśli jest taka konieczność, tzn blokada jest zajęta, gdyby się zwolniła, to mimo, że jakieś wątki czekają, to my i tak ją bierzemy*

### Zadanie 4

- mogą być co najwyżej trzy procesy współbieżne korzystające z zasobu
- jeśli w danej chwili zasób ma mniej niż trzech użytkowników, to możemy bez opóźnień przydzielić zasób kolejnemu procesowi
- jednakże, gdy zasób ma już trzech użytkowników, to muszą oni wszyscy zwolnić zasób, zanim zaczniemy dopuszczać do niego kolejne procesy
- operacja `acquire` wymusza porządek FIFO

mutex = semaphore(1) # implementuje sekcję krytyczną
block = semaphore(0) # oczekiwanie na opuszczenie zasobu
active = 0 # liczba użytkowników zasobu
waiting = 0 # liczba użytkowników oczekujących na zasób
must_wait = False # czy kolejni użytkownicy muszą czekać?

    def acquire():
  mutex.wait()
  if must_wait: # czy while coś zmieni?
    waiting += 1
    mutex.post()
    block.wait()
    mutex.wait()
    waiting -= 1
  active += 1
  must_wait = (active == 3)
  mutex.post()
  
def release():
  mutex.wait()
  active -= 1
  if active == 0:
    n = min(waiting, 3);
    while n > 0:
      block.post()
      n -= 1
    must_wait = False
  mutex.post()

Podaj dwa istotnie różne kontrprzykłady wskazujące na to, że powyższe rozwiązanie jest niepoprawne.

|Wątek|Co robi|Active|Waiting|Must_wait|
|-----|-------|------|-------|---------|
| 1 |acquire|1 |0 | False |
| 2 |acquire|2 |0 | False |
| 3 |acquire|3 |0 | True |
| 4 |acquire|3 |1 | True |
| 1 |release|2 |1 | True |
| 2 |release|1 |1 | True |
| 3 |release|0 |1 | False |
| 5 |acquire|1 |1 | False |

Wątek 4 zatrzymuje się na block.wait() i oczekuje na zwolnienie zasobu.

W tym momencie łamiemy czwartą zasadę zaburzając porządek FIFO

Nie wiem na ile jest to "istotnie różny kontrprzykład", bo jest kinda kontynuację, ALE złamiemy tym razem dodatkowo (przede wszystkim) inną zasadę

|Wątek|Co robi|Active|Waiting|Must_wait|
|-----|-------|------|-------|---------|
| 1 |acquire|1 |0 | False |
| 2 |acquire|2 |0 | False |
| 3 |acquire|3 |0 | True |
| 4 |acquire|3 |1 | True |
| 1 |release|2 |1 | True |
| 2 |release|1 |1 | True |
| 3 |release|0 |1 | False |
| 5 |acquire|1 |1 | False |
| 6 |acquire|2 |1 | False |
| 7 |acquire|3 |1 | TRUE |
| 4 |acquire|4 |0 | TRUE |

W tym momencie łamiemy FIFO, ale co ważniejsze łamiemy także pierwszą zasadę, ponieważ aktywne są 4 wątki na raz

### Zadanie 5

**PROBLEM UCZTUJĄCYCH FILOZOFÓW**

Rozwiązanie tego problemu jest następujące: Musimy kontrolować liczbę jednocześnie siedzących filozofów, a dokładniej zapewnić, że co najmniej jedno miejsce jest puste, dzięki temu w najgorszym przypadku, gdy mamy N filozofów -> mamy N pałeczek, przy stole posadzimy N-1 filozofów i każdy weźmie sobie pałeczkę, to nadal pozostanie jedna wolna, dzięki czemu któryś filozof będzie mógł zacząć jeść (wpp. mogłoby dojśc do sytuacji, w której każdy filozof wziął po jednej pałeczce, a więc mamy zero wolnych pałeczek oraz 0 filozofów, którzy mogą jeść, żaden z nich nie zwolni swojej pałeczki, bo czeka na otrzymanie drugiej i mamy deadlock'a).
Powyższe rozwiązanie jest dobre, ponieważ
a) Pałeczka może być trzymana tylko przez jedną osobę (to akurat baza kodu rozwiązuje)
b) Nie dojdzie do deadlock'a
c) Nie możemy głodzić filozofa - nie możemy, bo, powiedzmy, że mamy filozofów A B C, A jak i C obecnie jedzą, więc B musi czekać na lewą i prawą pałeczkę, wiadomym jest, że czas jedzenia jest skończony, więc prędzej czy później skończą, a tylko filozof B będzie w kolejce po jedną i drugą pałeczkę, więc prędzej czy później je dostanie.
d) jest możliwe aby kilku filozofów (min 2) jadło w tym samym czasie, wystarczy aby przy stole mogło siedzieć w jakimś momencie nie więcej niż N-2 filozofów, co jest możliwe, nigdzie tego nie ogranicziliśmy

### Zadanie 6

**PROBLEM OBIADUJĄCYCH DZIKUSÓW**