# SO lista 9+4

## Zadanie 1
<!-- treść -->

### Odwrócenie priorytetów
zdobycie zasobów związanych z synchronizacją przez wątek o niskim priorytecie np. mutexów, kiedy wątek o wysokim priorytecie chce z tego zasobu skorzytsać. W efekcie, wątek o wysokim priorytecie nie będzie się wykonywać, bo czeka na locka, ale jakiś inny random go wziął (w skrócie spowalnia system)

### Dziedziczenie priorytetów
Wątek o wysokim priorytecie, któremu ktoś zakosił blokadę, promotuje ten wątek z blokadą do swojego prio na czas trwania jego sekcji krytycznej, a potem go demotuje i bierze blokadę

### 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ął.

### W jakim celu mutex pamięta właściciela?
Bo w razie potrzeby można go wypromować i dać mu się wykonać, żeby nie było odwrócenia priorytetów. Potem znów demot :( (wtedy trzeba wiedzieć kogo)

### W jaki sposób należy rozszerzyć implementację operacji «mutex_lock» i «mutex_unlock», żeby nie dopuścić do odwrócenia priorytetów?
Trzeba zrobić tak, że mutex_lock() zawiera kod, który sprawdza, czy przypadkiem wątek o niższym priorytecie nie wziął tego locka i w razie potrzeby ustwaił mu prio (chyba) równe wątkowi który sprowadził
### 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ć.
<!-- zdjęcia -->

## Zadanie 2
<!-- treść -->

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;
    s->mutex = pthread_mutex_init(NULL);  //&s->mutex
    s->waiters = pthread_cond_init(NULL); //&s->waiters
}

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.
<!-- zdjęcia -->

## Zadanie 3
<!-- treść -->

### futex
int 32-bit. Ma jakąś wartość, ale zajmuje się tym kernel

#### FUTEX_WAIT
sprawia, że wątek który wywołał futex(), zostanie zsuspendowany w kernelu i będzie czekał, aż ktoś go obudzi (FUTEX_WAKE) albo jakiś określony czas

#### FUTEX_WAKE
żeby obudzić 1 lub więcej wątków trzeba użyć tej flagi w syscallu i futex (pointer na miejsce do niego)

### Czym się różni od blokady adaptacyjnej?
#### Blokada adaptacyjna
::: success
Nie wiem kurwa ~PK 2023
:::
Może jakiś mix spin-lock dla małej ilości threadów (bo krótko trzeba czekać) i oddawanie czasu procesorowi dla większego contestu o blokadę (jak jest dużo wątków).
#### Blokada usypiająca
to te co zawsze robią yield() do CPU

### Co wyraża wartość blokady
w syscallu 4 argument powinien być równy wartości blokady przy WAIT num...

wartość blokady to `congesion count`, czyli jakbyś przeczytał source code kernela to byś wiedział
::: info
nie wiem co palił jak pisał
:::

### Jak zachowuje się blokada w warunkach wysokiego współzawodnictwa?
Usypia wątek który chce zablokować i (?) do kolejki w kerenlu

### W jakich warunkach usypiamy i wybudzamy wątki?
usypiamy gdy wiemy(?), że jest ktoś kto nas może wybudzić, a wybuzdamy, gdy jest ktoś do wybudzenia

<!-- zdjęcia -->

## Zadanie 4
<!-- treść -->

### Kontrprzykład 1
1. 3 wątki wchodzą do SK
2. 3 wątki robią acquire() i wchodzą do ifa. Wszystkie siedzą miedzy 5-6
3. 3 wątki w SK wychodzą. Ostatni wrzuca 3 metody na block i ustawia must_wait na false
4. Kolejny wątek przychodzi znikąd. Przechodzi ifa w acquire() i spierdala do SK
5. 3 zablokowane wątki biorą po żetonie z block i też spierdalają do SK
6. Są 4 wątki w SK

### Kontrprzykład 2
Można popsuć FIFO dając n wątków między 5-6. Gdy 3 są w SK, jak (?) (?) to scheduler może je inaczej wybudzić i później mogą być prędzej (nwm co robię)

::: success
#### To jest pożyczone
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
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
:::

<!-- zdjęcia -->

## Uwaga przed 5-7

## Zadanie 5
<!-- treść -->

/* TODO: If you need extra shared state, define it here. */
static sem_t seat;
static sem_t guard;

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

  for (;;) {

    /* Think */
    printf("[%d]thinking\n",right);
    randsleep();

    /* Przed pokojem ze stołem stoi ochroniarz, wpusza tylko wtedy gdy filozof zajmie miejsce */
    Sem_wait(&guard);

    /* Tylko N-1 filozofów może siedzieć przy stole */
    Sem_wait(&seat);
    Sem_post(&guard);

    /* TODO: Take forks (without deadlock & starvation) */
    Sem_wait(&forks[right]);
    Sem_wait(&forks[left]);

    /* Eat */
    printf("[%d]eating\n",right);
    randsleep();

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

  /* TODO: If you need extra shared state, initialize it here. */
  Sem_init(&seat,0,N-1);
  Sem_init(&guard,0,1);

## Zadanie 6
<!-- treść -->

static struct {
   /* TODO: Put semaphores and shared variables here. */
  sem_t take;
  sem_t empty;
  sem_t full;
  size_t meals; 
} *shared = NULL;

static void savage(void) {
  for (;;) {
    /* TODO Take a meal or wait for it to be prepared. */

    /* Tylko jeden dzikus przy kociołku na raz */
    Sem_wait(&shared->take);

    /* Jeśli kociołek pusty to obudź kucharza */
    if(!shared->meals){
      printf("%d wake cook, ",getpid());
      Sem_post(&shared->empty);
      printf("wait for gulash\n");
      Sem_wait(&shared->full);
    }

    /* weź porcję */
    shared->meals--;
    printf("%d eating, left: %ld\n",getpid(),shared->meals);
    Sem_post(&shared->take);

    /* 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);
    /* zrób M porcji gulaszu */
    printf("[cook] *skinning misjonarz alive for gulash*\n");
    shared->meals = M;
    printf("[cook] oogaboga gulash ready\n");
    Sem_post(&shared->full);
  }
}

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

## Zadanie 7
<!-- treść -->

No tak śrenio bym powiedział

## Zadanie 8
<!-- treść -->

/* TODO: If you need any extra global variables, then define them here. */
static sem_t tobacco_guy,paper_guy,matches_guy,next_round,mutex;
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 *notifier(void* arg){
  int t=0,m=0,p=0,notified=0;
  for(;;){
    Sem_getvalue(&tobacco,&t);
    Sem_getvalue(&matches,&m);
    Sem_getvalue(&paper  ,&p);
    if(t && m){
      Sem_post(&paper_guy);
      notified = 1;
    }
    else if(t && p){
      Sem_post(&matches_guy);
      notified = 1;
    }
    else if(m && p){
      Sem_post(&tobacco_guy);
      notified = 1;
    }
    if(notified){
      t=0;m=0,p=0,notified=0;
      Sem_wait(&next_round);
    }
  }
  return NULL;
}

static void *smokerWithMatches(void *arg) {
  seed = pthread_self();
  while (true) {
    /* TODO: wait for paper and tobacco */
    Sem_wait(&matches_guy);
    Sem_wait(&tobacco);
    Sem_wait(&paper);
    make_and_smoke('M');
    Sem_post(&next_round);
  }
  return NULL;
}

static void *smokerWithTobacco(void *arg) {
  seed = pthread_self();
  while (true) {
    /* TODO: wait for paper and matches */
    Sem_wait(&tobacco_guy);
    Sem_wait(&paper);
    Sem_wait(&matches);
    make_and_smoke('T');
    Sem_post(&next_round);
  }
  return NULL;
}

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

/* TODO: Initialize your global variables here. */
  Sem_init(&paper_guy, 0, 0);
  Sem_init(&tobacco_guy, 0, 0);
  Sem_init(&matches_guy, 0, 0);
  Sem_init(&next_round, 0, 0);
  Sem_init(&mutex, 0, 1);
  pthread_t notifierThread;
  Pthread_create(&notifierThread, NULL, notifier, NULL);