# Ćwiczenia 13, grupa cz. 10-12, 26 stycznia 2023

###### tags: `SO22` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::warning
**Uwaga**: Dzisiaj deklarujemy zadania **5 -- 9** z **listy 12** oraz **1 -- 4** z **listy 13**.

Formularz deklaracji **listy 12**:
[https://hackmd.io/@iiuwr-kba/r1T8KdIio/edit](https://hackmd.io/@iiuwr-kba/r1T8KdIio/edit)
:::

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Miriam Bouhajeb | X | | | | | | | |
Kacper Chmielewski | X | X | | X | | | | |
Jan Jankowicz | X | X | | | X | X | X | X |
Jakub Kaczmarek | | | | | | | | |
Jarosław Kadecki | | | | | X | | | |
Zuzanna Kania | X | | | | X | X | | X |
Julia Konefał | | | | | | | | |
Daniel Sarniak | X | X | | | X | X | | X |
Paweł Tkocz | | | | | X | X | X | X |
Miłosz Urbanik | X | X | X | | X | X | | X |
Tomasz Wołczański | X | X | | | | X | | |
Radosław Śliwiński | | | | | | | | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Zuzanna Kania

**Mutex** to specjalna struktura służąca do synchronizacji wątków. Działaniem przypomina semafor binarny, jednak oprócz tego pamięta jeszcze wątek, który go zajął, dzięki czemu możliwe jest działanie dziedziczenia priorytetów oraz możliwe jest kontrolowanie tego, czy wątkiem zwalniającym blokadę jest ten, który ją zajął.

**Odwrócenie priorytetów** polega na tym, że wątek o wysokim priorytecie zostaje zmuszony do uśpienia pomimo swojego pierwszeństwa tylko dlatego, że wątek o niższym priorytecie zajął mutex i został wywłaszczony zanim zdążył go zwolnić.

**Dziedziczenie priorytetów** to metoda rozwiązywania powyższego problemu. Polega na tym, że wątek o wysokim priorytecie udziela swojego priorytetu wątkowi o priorytecie niższym (korzystając z tego, że mutex przechowuje informację o tym, który wątek go zajmuje). Taki pożyczony priorytet jest "oddawany" po zwolnieniu mutexa, co umożliwia wątkowi o wysokim priorytecie kontynuowanie wykonywania własnego kodu.


Jednym z rozwiązań zapobiegających wystąpieniu zjawiska odwrócenia priorytetów jest ustawienie możliwie najwyższego priorytetu wątkowi, który zajął zamek, i przywrócenie ich, gdy ten odda zamek. Tak więc implementacja `mutex_lock` powinna zawierać wywołanie funkcji `pthread_setschedprio` z parametrem zawierającym maksymalny priorytet dla danej polityki planisty, a `mutex_unlock` powinno zawierać wywołanie tej samej funkcji z poprzednią wartością priorytetu.

**Czy semafory są odporne na problem odwrócenia priorytetów?**
Nie, ponieważ semafor nie wie, które wątki go zajmują i tym samym czekający wątek o wysokim priorytecie nie jest w stanie wpłynąć na blokujące go wątki o niższym priorytecie - jest zmuszony czekać.
:::

## Zadanie 2
:::success
Autor: Daniel Sarniak

~~Założenie, że `pthread_cond_signal` budzi tylko jeden wątek (błędne założenie)~~

> [name=Piotr Witkowski] Wbrew temu, co stwierdziłem na ćwiczeniach, powyższe założenie nie jest wymagane. Zmienna warunkowa `waiters` jest przecież związana z muteksem `mutex`. Każdy, z być może wielu procesów wybudzonych przez `pthread_cond_signal`, zanim powróci z wywołania `pthread_cond_wait`, musi odzyskać `mutex`. Zatem test warunku w wierszu 23 będzie odbywać się w sposób uszeregowany, a nie współbieżny.
> Rozważmy przykład z trzema wątkami A, B, C i początkową wartością `value` równą 1:

> 1. wątek A wykonuje `sem_wait(s)` i zajmuje semafor, `value == 0`
> 2. wątek B wykonuje `sem_wait(s)` i usypia się w wierszu 24
> 3. wątek C wykonuje `sem_wait(s)` i usypia się w wierszu 24
> 4. wątek A wykonuje `sem_post(s)`, czyli ustawia value na 1, oraz budzi wątki B i C funkcją `pthread_cond_signal`
> 5. wątki B i C rozpoczynają rywalizację o `mutex`, załóżmy, że wygrywa ją B
> 6. wątek B powraca z wywołania `pthread_cond_wait` i kontynuuje wykonanie `sem_wait(s)`, ustawia value na 0 i zajmuje semafor
> 7. wątek C zajmuje `mutex` zwolniony w poprzednim punkcie przez B i powraca z wywołania `pthread_cond_wait`. W wierszu 23 okazuje się, że `value == 0`, więc C ponownie wywołuje `pthread_cond_wait` i usypia się w wierszu 24.
> 8. wątek C będzie miał szansę na kontynuację dopiero po wywołaniu `sem_post(s)` przez wątek B.

> Współbieżne wykonanie wierszy 23-24 przez B i C nie jest możliwe, gdyż tylko jeden z nich (w naszym przykładzie B) może w danym momencie zajmować `mutex`.
> Rozwiązanie jest zatem poprawne.

typedef struct Sem {
    pthread_mutex_t mutex;
    pthread_cond_t waiters;
    int value;
} Sem_t;

typedef struct Sem {
    pthread_mutex_t mutex;
    pthread_cond_t waiters;
    int value;
} Sem_t;

void sem_init(Sem_t* s, int value) {
    assert(value >= 0);
    s->value = value;
    pthread_mutex_init(&s->mutex, NULL);
    pthread_cond_init(&s->waiters, NULL);
}

void sem_post(Sem_t* s) {
    pthread_mutex_lock(&s->mutex);
    s->value++;
    pthread_cond_signal(*s->waiters); 
    pthread_mutex_unlock(&s->mutex);
}

void sem_wait(Sem_t* s) {
    pthread_mutex_lock(&s->mutex);
    while (s->value == 0) {
        pthread_cond_wait(&s->waiters, &s->mutex);
    }
    s->value--;
    pthread_mutex_unlock(&s->mutex);
}

`int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)`
used to block on a condition variable. They are called with mutex locked by the calling thread or undefined behaviour will result.
These functions atomically release mutex and cause the calling thread to block on the condition variable cond; atomically here means "atomically with respect to access by another thread to the mutex and then the condition variable"

`int pthread_cond_signal(pthread_cond_t *cond)`
The pthread_cond_signal() call unblocks at least one of the threads that are blocked on the specified condition variable cond (if any threads are blocked on cond).

`int pthread_cond_init(pthread_cond_t *cond,
const pthread_condt_t *attr);`
The function pthread_cond_init() initialises the condition variable referenced by cond with attributes referenced by attr. If attr is NULL, the default condition variable attributes are used; the effect is the same as passing the address of a default condition variable attributes object

`int pthread_mutex_init(pthread_mutex_t *mutex,
const pthread_mutex_t *attr);`
The pthread_mutex_init() function initialises the mutex referenced by mutex with attributes specified by attr. If attr is NULL, the default mutex attributes are used; the effect is the same as passing the address of a default mutex attributes object. Upon successful initialisation, the state of the mutex becomes initialised and unlocked.

`pthread_mutex_lock / pthread_mutex_unlock`
Releases a mutex object. If one or more threads are waiting to lock the mutex, pthread_mutex_unlock() causes one of those threads to return from pthread_mutex_lock() with the mutex object acquired. If no threads are waiting for the mutex, the mutex unlocks with no current owner.
:::

## Zadanie 3
:::success
Autor: Miłosz Urbanik

:::

Syscall `futex` (fast user-space locking/mutex) służy implementacji niskopoziomowych blokad, które działają w przestrzeni użytkownika.

`FUTEX_WAIT` - sprawia, że wątek/proces jest dodawany do kolejki w przestrzeni jądra
`FUTEX_WAKE` - budzi n wątków z kolejki
Jądro identyfikuje kolejki na podstawie adresu zmiennej, które przechowuje wartość blokady

* **blokada adaptacyjna** - blokada, która w swojej implementacji zawiera różne strategie blokowania/odblokowania w zależności od stopnia współzawodnictwa, wykorzystania procesora, aktualnie wykonywanego wątku.

* **współzawodnictwo** - określenie na liczbę procesów/wątków chcących otrzymać dostęp do zasobu

Wartość blokady futex określa (niewprost) liczbę wątków, które oczekują na blokadę.

W warunkach wysokiego współzawodnictwa blokada wykonuje syscall `FUTEX_WAIT`

> [name=Piotr Witkowski] Alternatywna, bardziej czytelna implementacja zamka opartego na futeksie
> [https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf](https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf), str. 19, rysunek 28.10

## Zadanie 4
:::success
Autor: Kacper Chmielewski
1. Między liniami 5, a 6 jest szansa na to, że niektóre wątki zakończą się przed obudzeniem innego wątka, co doprowadzi do uśpienia tego jednego na zawsze
2. Proces, który będzie w miejscu wywołania block.wait(), może wykonywać się dlużej niz inny proces, kolejny proces, co może doprowadzić do zaprzeczenia porządku fifo

:::

:::info
Deklarowanie i prezentacja poniższych zadań przeniesione na następne ćwiczenia.
:::

## Zadanie 5
:::success
Autor: Daniel Sarniak


#include "csapp.h"

static __unused void outc(char c) {
  Write(STDOUT_FILENO, &c, 1);
}

static void randsleep(void) {
  usleep(rand() % 5000 + 5000);
}

#define N 50

static pthread_t td[N];
static sem_t forks[N];
/* TODO: If you need extra shared state, define it here. */
static sem_t mutex;
/*  ======================================================   */

void *philosopher(void *id) {
  int right = (intptr_t)id;
  int left = right == 0 ? N - 1 : right - 1;

  for (;;) {
    /* Think */
    randsleep();

    /* TODO: Take forks (without deadlock & starvation) */
    Sem_wait(&mutex);
    Sem_wait(&forks[right]);
    Sem_wait(&forks[left]);
    printf("[%02d] Eating using chopsticks   [%02d] and [%02d]\n", right, left, right);

    /* Eat */
    randsleep();
    printf("[%02d] Finished using chopsticks [%02d] and [%02d]\n", right, left, right);

    /* TODO: Put forks (without deadlock & starvation) */
    Sem_post(&forks[left]);
    Sem_post(&forks[right]);
    Sem_post(&mutex);
  }

  return NULL;
}

int main(void) {
  /* TODO: If you need extra shared state, initialize it here. */
  Sem_init(&mutex, 0, N - 1);
  /*  ======================================================   */
  for (int i = 0; i < N; i++)
    Sem_init(&forks[i], 0, 1);

  for (int i = 0; i < N; i++)
    Pthread_create(&td[i], NULL, philosopher, (void *)(intptr_t)i);

  for (int i = 0; i < N; i++)
    Pthread_join(td[i], NULL);
  
  return EXIT_SUCCESS;
}

:::

## Zadanie 6
:::success
Autor: Tomasz Wołczański
:::

#include "csapp.h"

static __unused void outc(char c) {
  Write(STDOUT_FILENO, &c, 1);
}

#define N 100
#define M 100

static struct {
  /* TODO: Put semaphores and shared variables here. */
  int portions;
  sem_t empty;
  sem_t full;
  sem_t mutex;
} *shared = NULL;


static void savage(void) {
  for (;;) {
    /* TODO Take a meal or wait for it to be prepared. */
    Sem_wait(&shared->mutex);
    if (shared->portions == 0) {
      Sem_post(&shared->empty);
      Sem_wait(&shared->full);
    }
    shared->portions--;
    Sem_post(&shared->mutex);

    /* Sleep and digest. */
    usleep(rand() % 1000 + 1000);
  }

  exit(EXIT_SUCCESS);
}

static void cook(void) {
  for (;;) {
    /* TODO Cook is asleep as long as there are meals.
     * If woken up they cook exactly M meals. */
    Sem_wait(&shared->empty);
    shared->portions = M;
    Sem_post(&shared->full);
  }
}

/* Do not bother cleaning up after this process. Let's assume that controlling
 * terminal sends SIGINT to the process group on CTRL+C. */
int main(void) {
  shared = Mmap(NULL, getpagesize(), PROT_READ|PROT_WRITE, MAP_ANON|MAP_SHARED,
                -1, 0);

  /* TODO: Initialize semaphores and other shared state. */
  shared->portions = M;
  Sem_init(&shared->empty, 1, 0);
  Sem_init(&shared->full, 1, 0);
  Sem_init(&shared->mutex, 1, 1);

  for (int i = 0; i < N; i++)
    if (Fork() == 0)
      savage();

  cook();

  return EXIT_SUCCESS;
}

## Zadanie 7
:::success
Autor: Paweł Tkocz
:::

#include "csapp.h"

static __unused void outc(char c) {
  Write(STDOUT_FILENO, &c, 1);
}

typedef struct {
  /* TODO: Use this structure to store barrier internal state. */
  int waiting;
  int max_count;
  int started;
  int finished;
  sem_t mutex;
  sem_t barrier;
  sem_t barrier2;
} barrier_t;

static barrier_t *barrier_init(int n) {
  if (n < 1)
    app_error("barrier_init requires n > 0");

  barrier_t *b = Mmap(NULL, sizeof(barrier_t), PROT_READ|PROT_WRITE,
                      MAP_ANON|MAP_SHARED, -1, 0);

  /* TODO: Initialize barrier internal state. */
  Sem_init(&b->barrier, 1, 0);
  Sem_init(&b->barrier2, 1, 0);
  Sem_init(&b->mutex, 1, 1);
  b->waiting = 0;
  b->finished = 0;
  b->max_count = n;
  b->started = 0;
  return b;
}

static void barrier_wait(barrier_t *b) {
  /* TODO: Provide wait procedure implementation here. */
  
  Sem_wait(&b->mutex);
  b->waiting += 1;
  if(b->waiting==b->max_count){
    Sem_post(&b->barrier);
    b->waiting = 0;
  }
  Sem_post(&b->mutex);
  Sem_wait(&b->barrier);


  Sem_wait(&b->mutex);
  b->started += 1;
  if(b->started == b->max_count){
    b->started = 0;
    Sem_post(&b->barrier2);
  }
  else
    Sem_post(&b->barrier);
  Sem_post(&b->mutex);
  Sem_wait(&b->barrier2);

  Sem_wait(&b->mutex);
  b->finished += 1;
  outc('*');
  if(b->finished != b->max_count)
    Sem_post(&b->barrier2);
  else{
    b->finished = 0;
    outc(10);
  }
  Sem_post(&b->mutex);
}

static void barrier_destroy(barrier_t *b) {
  /* TODO: Provide destroy procedure implementation here. */
  sem_destroy(&b->barrier2);
  sem_destroy(&b->barrier);
  sem_destroy(&b->mutex);
}

#define K 100
#define N 50
#define P 100

static noreturn void horse(barrier_t *b) {
  int n = rand() % K + K;

  outc('+');

  for (int i = 0; i < n; i++) {
    barrier_wait(b);
    usleep(rand() % 2000 + 1000);
  }

  outc('-');

  exit(EXIT_SUCCESS);
}

/* Do not bother cleaning up after this process. Let's assume that controlling
 * terminal sends SIGINT to the process group on CTRL+C. */
int main(void) {
  barrier_t *b = barrier_init(N);

  int horses = 0;

  for (;;) {
    do {
      if (Fork() == 0) {
        srand(getpid());
        horse(b);
      }
      horses++;
    } while (horses < P);

    Wait(NULL);
    horses--;
  }

  barrier_destroy(b);

  return EXIT_SUCCESS;
}

## Zadanie 8
:::success
Autor: Jan Jankowicz
:::

#include "csapp.h"

static __unused void outc(char c) {
  Write(STDOUT_FILENO, &c, 1);
}

static __thread unsigned seed;

static sem_t tobacco;
static sem_t matches;
static sem_t paper;
static sem_t doneSmoking;

/* TODO: If you need any extra global variables, then define them here. */
static sem_t smokerWithMatches_sem;
static sem_t smokerWithTobacco_sem;
static sem_t smokerWithPaper_sem;

static sem_t checker_sem;

static bool matchesPresent;
static bool tobaccoPresent;
static bool paperPresent;

static void *agent(void *arg) {
  seed = pthread_self();

  while (true) {
    Sem_wait(&doneSmoking);

    int choice = rand_r(&seed) % 3;
    if (choice == 0) {
      Sem_post(&tobacco);
      Sem_post(&paper);
    } else if (choice == 1) {
      Sem_post(&tobacco);
      Sem_post(&matches);
    } else {
      Sem_post(&paper);
      Sem_post(&matches);
    }
  }

  return NULL;
}

/* TODO: If you need extra threads, then define their main procedures here. */
static void *matchesChecker(void *arg) {
  seed = pthread_self();
 
  while (true) {
    /* wait for matches */
    Sem_wait(&matches);
    Sem_wait(&checker_sem);
    matchesPresent = true;
    
	if (tobaccoPresent) {
		Sem_post(&smokerWithPaper_sem);
		tobaccoPresent = false;
		matchesPresent = false;
	}
	
	if (paperPresent) {
		Sem_post(&smokerWithTobacco_sem);
		paperPresent = false;
		matchesPresent = false;
	}
	
	Sem_post(&checker_sem);
  }

  return NULL;
}

static void *tobaccoChecker(void *arg) {
  seed = pthread_self();
 
  while (true) {
    /* wait for tobacco */
    Sem_wait(&tobacco);
    Sem_wait(&checker_sem);
    tobaccoPresent = true;
    
	if (matchesPresent) {
		Sem_post(&smokerWithPaper_sem);
		matchesPresent = false;
		tobaccoPresent = false;
	}
	
	if (paperPresent) {
		Sem_post(&smokerWithMatches_sem);
		paperPresent = false;
		tobaccoPresent = false;
	}
	
	Sem_post(&checker_sem);
  }

  return NULL;
}

static void *paperChecker(void *arg) {
  seed = pthread_self();
 
  while (true) {
    /* wait for paper */
    Sem_wait(&paper);
    Sem_wait(&checker_sem);
    paperPresent = true;
    
	if (tobaccoPresent) {
		Sem_post(&smokerWithMatches_sem);
		tobaccoPresent = false;
		paperPresent = false;
	}
	
	if (matchesPresent) {
		Sem_post(&smokerWithTobacco_sem);
		matchesPresent = false;
		paperPresent = false;
	}
	
	Sem_post(&checker_sem);
  }

  return NULL;
}


static void randsleep(void) {
  usleep(rand_r(&seed) % 1000 + 1000);
}

static void make_and_smoke(char smoker) {
  randsleep();
  Sem_post(&doneSmoking);
  outc(smoker);
  randsleep();
}

static void *smokerWithMatches(void *arg) {
  seed = pthread_self();

  while (true) {
    /* TODO: wait for paper and tobacco */
    Sem_wait(&smokerWithMatches_sem);
    make_and_smoke('M');
    Sem_post(&smokerWithMatches_sem);
  }

  return NULL;
}

static void *smokerWithTobacco(void *arg) {
  seed = pthread_self();

  while (true) {
    /* TODO: wait for paper and matches */
    Sem_wait(&smokerWithTobacco_sem);
    make_and_smoke('T');
    Sem_post(&smokerWithTobacco_sem);
  }

  return NULL;
}

static void *smokerWithPaper(void *arg) {
  seed = pthread_self();
 
  while (true) {
    /* TODO: wait for tobacco and matches */
    Sem_wait(&smokerWithPaper_sem);
    make_and_smoke('P');
    Sem_post(&smokerWithPaper_sem);
  }

  return NULL;
}

int main(void) {
  Sem_init(&tobacco, 0, 0);
  Sem_init(&matches, 0, 0);
  Sem_init(&paper, 0, 0);
  Sem_init(&doneSmoking, 0, 1);

  /* TODO: Initialize your global variables here. */
  matchesPresent = false;
  tobaccoPresent = false;
  paperPresent = false;
  
  Sem_init(&checker_sem, 0, 1);
  
  Sem_init(&smokerWithMatches_sem, 0, 0);
  Sem_init(&smokerWithTobacco_sem, 0, 0);
  Sem_init(&smokerWithPaper_sem, 0, 0);
  
  pthread_t paperCheckerThread, matchesCheckerThread, tobaccoCheckerThread;
  Pthread_create(&paperCheckerThread, NULL, paperChecker, NULL);
  Pthread_create(&matchesCheckerThread, NULL, matchesChecker, NULL);
  Pthread_create(&tobaccoCheckerThread, NULL, tobaccoChecker, NULL);

  pthread_t agentThread;
  Pthread_create(&agentThread, NULL, agent, NULL);

  pthread_t smokerPaperThread, smokerMatchesThread, smokerTobaccoThread;
  Pthread_create(&smokerPaperThread, NULL, smokerWithPaper, NULL);
  Pthread_create(&smokerMatchesThread, NULL, smokerWithMatches, NULL);
  Pthread_create(&smokerTobaccoThread, NULL, smokerWithTobacco, NULL);

  Pthread_join(agentThread, NULL);
  Pthread_join(smokerPaperThread, NULL);
  Pthread_join(smokerMatchesThread, NULL);
  Pthread_join(smokerTobaccoThread, NULL);

  return 0;
}