# SO - Lista 13
###### tags: `SO`

## Zadanie 1


1. Odwrócenie priorytetów - Wątek o niskim priorytecie zakłada blokadę na sekcję krytyczną. Następnie zostaje wywłaszczony, przez co żaden inny wątek o wyższym priorytecie nie może kontynuować działania (Wątki o wyższym priorytecie czekają na zakończenie programu o niższym priorytecie)

2. Dziedziczenie priorytetów - Metoda rozwiązywania problemu odwróconych priorytetów, polegająca na tymczasowym zwiększeniu priorytetu wątku będącego w sekcji krytycznej, by ten mógł zdjąć blokadę.


3. Dlaczego mutex pamięta właściciela? - Żeby wiedzieć kto założył blokadę i kogo trzeba wypromować

4. Operacja mutex_lock w przypadku założonej blokady odczytuje właściciela mutexa i zwiększa jego priorytet. Mutex_unlock po ściągnięciu blokady ustawia swój priorytet na domyślną wartość.

5. NIE!

## Zadanie 2


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

## Zadanie 3


## Zadanie 4


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()

1.
1. 3 procesy biorą zasób
2. Kolejne 3 blokują się (linijka 6)
3. Wychodzą procesy trzymajace zasob
4. Ostatni z nich zwalnia blokady zalozone na procesy
5. Po nim przychodzi nowy proces (active=1)
6. Trzy zablokowane wczesniej procesy kolejno korzystaja z zasobu (active=)

2. (W wersji z while)
1. 3 procesy korzystają z zasobu
2. 3 procesy w kolejce są blokowane przez block.wait()
3. Zostaje wykonany release()
4. Must_wait = 0
5. 4 proces z kolejki pierwszy woła mutex.wait()
6. Zabiera zasób
7. 2 kolejne procesy też wchodzą do zasobów
8. 3 proces z kolejki kręci się w pętli
9. KONIEC!

## Zadanie 5


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

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) */
    // N=5
    Sem_wait(&counter);
    Sem_wait(&forks[right]);
    Sem_wait(&forks[left]);
    printf("Eating using %d and %d\n", left, right);
    /* Eat */
    randsleep();
    printf("Finished using %d and %d\n", left, right);
    /* TODO: Put forks (without deadlock & starvation) */
    Sem_post(&forks[left]);
    Sem_post(&forks[right]);
    Sem_post(&counter);
  }

  return NULL;
}

int main(void) {
  /* TODO: If you need extra shared state, initialize it here. */
  Sem_init(&counter, 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


#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 food;
    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->food == 0){
        Sem_post(&shared->empty);
        Sem_wait(&shared->full);
    }
    shared->food--;
    printf("[%d] eating %d left\n", getpid(), shared->food);
    Sem_post(&shared->mutex);
    /* Sleep and digest. */
    usleep(rand() % 1000 + 1000);
  }

  exit(EXIT_SUCCESS);
}

static void cook(void) {
  for (;;) {
    Sem_wait(&shared->empty);
    shared->food = M;
    printf("[%d] cooking\n", getpid());
    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. */
    Sem_init(&shared->mutex, 1, 1);
    Sem_init(&shared->empty, 1, 0);
    Sem_init(&shared->full, 1, 0);
    shared->food = M;
    
    for (int i = 0; i < N; i++)
        if (Fork() == 0)
            savage();

    cook();

    return EXIT_SUCCESS;
}

## Zadanie 7


## Zadanie 8