# SO | Lista 13

# Zadanie 1

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

Sem_t *init(int v){
    Sem_t *semaphore = malloc(sizeof(Sem_t));
    semaphore->value = v;
    pthread_mutex_init(&semaphore->mutex,NULL);    
    pthread_cond_init(&semaphore->wiaters,NULL);
    return semaphore;
}

void 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);
}

void post(){
    pthread_mutex_lock(&s->mutex);
    s->value++;
    pthread_cond_broadcast(&s->waiters);
    pthread_mutex_unlock(&s->mutex);
}

# Zadanie 2

## Opisz semantykę operacji «FUTEX_WAIT» i «FUTEX_WAKE» mechanizmu futex(2) [1, 2.3.6]

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

### «FUTEX_WAIT»


Argumenty
* uaddr <=> Wskaźnik na futex.
* futex_op <=> Operacja: FUTEX_WAIT
* val <=> Oczekiwana wartość.
* timeout <=> Maksymalny czas oczekiwania na zajęcie zamka (modyfikacja z FUTEX_CLOCK_REALTIME w op).
* uaddr2 <=> Ignorowany
* val3 <=> Ignorowany
Zwracana wartość
* EAGAIN <=> Nastąpiło niespodziewana zmiana wartości futexa.
* 0 <=> Wątek został obudzony
### «FUTEX_WAKE»

Argumenty
* uaddr <=> Wskaźnik na futex.
* futex_op <=> Operacja: FUTEX_WAKE
* val <=> Ilość wątków do obudzenia
* timeout <=>Ignorowany
* uaddr2 <=> Ignorowany
* val3 <=> Ignorowany
Zwracana wartość: To ilość obudzonych wątków.
## Czym różnią się blokady adaptacyjne (ang. adaptive lock) od zwykłych blokad usypiających?
Zmniejszają ilość wywołań do jądra.
## Zreferuj implementację prostej blokady z operacjami __lock i __unlock.

void __lock(volatile int *l)
{
	int need_locks = libc.need_locks;
	if (!need_locks) return;
	/* fast path: INT_MIN for the lock, +1 for the congestion */
	int current = a_cas(l, 0, INT_MIN + 1);
	if (need_locks < 0) libc.need_locks = 0;
	if (!current) return;
	/* A first spin loop, for medium congestion. */
	for (unsigned i = 0; i < 10; ++i) {
		if (current < 0) current -= INT_MIN + 1;
		// assertion: current >= 0
		int val = a_cas(l, current, INT_MIN + (current + 1));
		if (val == current) return;
		current = val;
	}
	// Spinning failed, so mark ourselves as being inside the CS.
	current = a_fetch_add(l, 1) + 1;
	/* The main lock acquisition loop for heavy congestion. The only
	 * change to the value performed inside that loop is a successful
	 * lock via the CAS that acquires the lock. */
	for (;;) {
		/* We can only go into wait, if we know that somebody holds the
		 * lock and will eventually wake us up, again. */
		if (current < 0) {
			__futexwait(l, current, 1);
			current -= INT_MIN + 1;
		}
		/* assertion: current > 0, the count includes us already. */
		int val = a_cas(l, current, INT_MIN + current);
		if (val == current) return;
		current = val;
	}
}

void __unlock(volatile int *l)
{
	/* Check l[0] to see if we are multi-threaded. */
	if (l[0] < 0) {
		if (a_fetch_add(l, -(INT_MIN + 1)) != (INT_MIN + 1)) {
			__wake(l, 1, 1);
		}
	}
}

## Co wyraża wartość blokady?
Wartości ujemne oznaczają zajęcie zamka oraz ilość wątków oczekujących na zamek (i go posiadających)(x-INT_MAX).
## Jak zachowuje się blokada w warunkach wysokiego współzawodnictwa?
Uśpione wątki nie mają gwarancji uzyskania dostępu do CS. Nowe szybsze wątki (w sekcji `spin`) mogą im je wykradać.
## W jakich warunkach usypiamy i wybudzamy wątki?
### Usypiamy
Gdy krótki spin nie zapewnił nam dostępu do CS i w momencie zasypiania zamek wciąż jest zajęty.
### Wybudzamy
Gdy liczba śpiących wątków jest większa niż 0.

# Zadanie 3

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.

### 1

1) 3 wątki wykonują `acquire` => do CS uzyskują dostęp 3 wątki
2) 3 kolejne wątki wykonują `acquire`=> blokują się na `block.wait()`
3) 3 wątki (z punktu 1) wykonują `relase` => obudzone zostają wątki z punktu 2
4) 3 wątki z punktu 2 ponownie zasypiają i nie przechodzą do linii 7 (jednak już nie są powstrzymywane przez semafor `block`)
5) Pojawiają się nowe trzy wątki wykonujące `acquire` => uzyskują dostęp do CS (ponieważ must_wait == False)
6) Budzą się wątki z punktu 2 i uzyskują dostęp do CS
Efekt:
W CS znajduje się 6 wątków

### 2

Podobnie jak wcześnej problem występuje przy `block.wait()`.

1) 3 wątki wykonują `acquire` => do CS uzyskują dostęp 3 wątki
2) 1 kolejne wątki wykonują `acquire`=> blokują się na `block.wait()`
3) 3 wątki (z punktu 1) wykonują `relase` => obudzone zostają wątki z punktu 2
4) Pojawiaja się nowy wątek wykonujący `acquire` => uzyskuje dostęp do CS
5) Rozpoczyna pracę wątek z punktu 2 => uzyskuje dostęp do CS póżniej

### 3
Wielokrotne zwiększenie wykonanie `block.post()` dla tego samego wątku (czekającego na `block.wait()`).

Czy przykłady są istotnie różne? Co to oznacza że samafor jest sprawiedliwy?
# Zadanie 4

#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 philosophers[N];

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) */
    if(right % 2 ==0)
      Sem_wait(&philosophers[left]);
    Sem_wait(&philosophers[right]);
    Sem_wait(&forks[right]);
    Sem_wait(&forks[left]);

    /* Eat */
    randsleep();

    /* TODO: Put forks (without deadlock & starvation) */
    Sem_post(&philosophers[right]);
    if(right % 2 ==0)
      Sem_post(&philosophers[left]);
    Sem_post(&forks[left]);
    Sem_post(&forks[right]);
  }

  return NULL;
}

int main(void) {
  /* TODO: If you need extra shared state, initialize it here. */
  for (int i = 0; i < N; i++)
    Sem_init(&philosophers[i], 0, 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 5

#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. */
  sem_t cook;
  sem_t meals_num_s;
  int meals_num;
  sem_t meals;
} *shared = NULL;

static void savage(void)
{
  for (;;)
  {
    /* TODO Take a meal or wait for it to be prepared. */
    while (true)
    {
      Sem_wait(&shared->meals_num_s);
      int id = shared->meals_num--;
      if (id > 0)
      {
        Sem_post(&shared->meals_num_s);
        break;
      }
      if (id == 0)
        Sem_post(&shared->cook);
      Sem_post(&shared->meals_num_s);
      Sem_wait(&shared->meals);
    }
    outc('s');

    /* 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->cook);
    Sem_wait(&shared->meals_num_s);
    outc('\n');

    shared->meals_num = M;
    for (int i = 0; i < M; i++)
      Sem_post(&shared->meals);
    Sem_post(&shared->meals_num_s);
  }
}

/* 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. */
  Sem_init(&shared->cook, 1, 0);
  Sem_init(&shared->meals_num_s, 1, 1);
  Sem_init(&shared->meals, 1, 0);
  shared->meals_num = 0;

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

  cook();

  return EXIT_SUCCESS;
}

# Zadanie 6

#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. */
  sem_t lock;
  sem_t firstBarier;
  int inFirst;
  sem_t secondBarier;
  int inSecond;
  int N;
} 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. */
  b->inFirst = 0;
  b->inSecond = 0;
  Sem_init(&b->lock, 1, 1);
  Sem_init(&b->firstBarier, 1, 50);
  Sem_init(&b->secondBarier, 1, 0);
  b->N = n;
  return b;
}

static void barrier_wait(barrier_t *b)
{
  /* TODO: Provide wait procedure implementation here. */
  Sem_wait(&b->firstBarier);
  Sem_wait(&b->lock);
  if (++b->inFirst == b->N)
  {
    for (int i = 0; i < b->N; i++)
      Sem_post(&b->secondBarier);
    b->inFirst = 0;
  }
  Sem_post(&b->lock);

  Sem_wait(&b->secondBarier);
  Sem_wait(&b->lock);
  if (++b->inSecond == b->N)
  {
    for (int i = 0; i < b->N; i++)
      Sem_post(&b->firstBarier);
    b->inSecond = 0;
  }
  Sem_post(&b->lock);
}

static void barrier_destroy(barrier_t *b)
{
  /* TODO: Provide destroy procedure implementation here. */
  Sem_destroy(&b->firstBarier);
  Sem_destroy(&b->secondBarier);
  Sem_destroy(&b->lock);
  Munmap(b, sizeof(barrier_t));
}

#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 7

#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 smokersLocks[3];
static int smokeCounter[3];
static sem_t smokers_lock;

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 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 */
    int id = 0;
    while (true)
    {
      Sem_wait(&paper);
      Sem_wait(&smokers_lock);
      smokeCounter[id]++;
      Sem_post(&smokers_lock);
      Sem_post(&paper);

      Sem_wait(&tobacco);
      Sem_wait(&smokers_lock);
      smokeCounter[id]++;
      Sem_post(&smokers_lock);
      Sem_post(&tobacco);

      Sem_wait(&smokers_lock);
      if (smokeCounter[id] >= 3)
        break;
      Sem_post(&smokers_lock);
    }
    for (int i = 0; i < 3; i++)
      smokeCounter[i] = 0;
    Sem_post(&smokers_lock);

    Sem_wait(&paper);
    Sem_wait(&tobacco);

    make_and_smoke('M');
  }

  return NULL;
}

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

  while (true)
  {
    /* TODO: wait for paper and matches */
    int id = 1;
    while (true)
    {
      Sem_wait(&paper);
      Sem_wait(&smokers_lock);
      smokeCounter[id]++;
      Sem_post(&smokers_lock);
      Sem_post(&paper);

      Sem_wait(&matches);
      Sem_wait(&smokers_lock);
      smokeCounter[id]++;
      Sem_post(&smokers_lock);
      Sem_post(&matches);

      Sem_wait(&smokers_lock);
      if (smokeCounter[id] >= 3)
        break;
      Sem_post(&smokers_lock);
    }
    for (int i = 0; i < 3; i++)
      smokeCounter[i] = 0;
    Sem_post(&smokers_lock);

    Sem_wait(&paper);
    Sem_wait(&matches);

    make_and_smoke('T');
  }

  return NULL;
}

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

  while (true)
  {
    /* TODO: wait for tobacco and matches */
    int id = 2;
    while (true)
    {

      Sem_wait(&tobacco);
      Sem_wait(&smokers_lock);
      smokeCounter[id]++;
      Sem_post(&smokers_lock);
      Sem_post(&tobacco);

      Sem_wait(&matches);
      Sem_wait(&smokers_lock);
      smokeCounter[id]++;
      Sem_post(&smokers_lock);
      Sem_post(&matches);

      Sem_wait(&smokers_lock);
      if (smokeCounter[id] >= 3)
        break;
      Sem_post(&smokers_lock);
    }
    for (int i = 0; i < 3; i++)
      smokeCounter[i] = 0;
    Sem_post(&smokers_lock);

    Sem_wait(&tobacco);
    Sem_wait(&matches);

    make_and_smoke('P');
  }

  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. */
  for (int i = 0; i < 3; i++)
  {
    Sem_init(&smokersLocks[i], 0, 0);
    smokeCounter[i] = 0;
  }
  Sem_init(&smokers_lock, 0, 1);

  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;
}