# Systemy operacyjne 14

Dygresja zaczela sie na zadaniu 2 i do konca...

## Zadanie 1 być może kuba

**Definicja cache coherence**
cache coherence - lokalna spójność pamieci podręcznej; polega na tym aby różne jednostki (wątki, procesy, być może maszyny) miały jednakowy stan wspódzielonej zmiennej lub wiedziały że mają nieaktualny stan zmiennej. Można również to zdefiniowac w następujący sposób: "system ze spójnością lokalną pamięci musi wykonywać wszystkie zapisy i wczytania wątków do ***jednego*** segmentu pamięci w określonym porządku zachowującym porządek programu każdego wątku"
Cahir - mechamizm uspokajania cache: jezeli procesor1 zapisze do a 20 to musi to rozglosic do innych procesorow 'hej procesorze jesli masz a to juz masz nieaktualna'. musimy miec jedno zrodlo prawdy w tym systemie
Odsyłam do: https://en.wikipedia.org/wiki/Cache_coherence#Definition oraz do https://www.youtube.com/watch?v=N0glmhANHfU&ab_channel=MargoSeltzer

**Dlaczego program działa szybciej gdy zmienimy spacing z 1 na 8?**
Działa szybciej bo mamy "mniej" zapytań do pamięci z powodu page faultów, mamy większy przedział pamięci w cache-u.

**Opis przejścia stanu dla MSI**

:::spoiler
TODO: Opisać graf na górze i rozwiązać ten syf...
:::
Na razie ogólnie jak działa ten graf:
Załóżmy, że jesteśmy na początku w I (Cache line invalid - może być to spowodowane że jej nie ma w cach-u albo z powodu protokołu) i chcemy lokalnie wczytać dane. Wtedy na magistrale leci fetch shared i zmieniamy stan cache-u na S (Cache line is shared). Będąc w shared dowolny read cache-u nie będzie zmieniać stanu ani nie będzie robić request-u. Jeśli chce zmodyfikować linie cache to wysyłam sygnał invalid do reszty procesów i zmieniam swój status z S na M (Cache line modified). Będąc w modified dowolny read-y oraz write przez nas nie zmieniają naszego stanu. Załóżmy teraz że jesteśmy w I i chcemy zrobić zapis do wspólnej linii cache-u. Ogłaszamy więc nasz zamiar robiąc fetch modified, w którym pobieramy najaktualniejszą wersję, a potem modyfikujemy ją. Reszta procesów po tym musi zmienić stan na I. Załóżmy teraz, że jesteśmy w stanie M i chcemy pozbyć się danej linii cache-u, zatem zapisuj w pamięci zmienną (nie lokalnie w cache-u) i zmieniam stan na I. Natomiast jeśli jesteśmy w S to zrobienie eviction nie wysyła żadnego sygnału. Co jeśli jestem w M i ktoś wyśle mi sygnał że chce pisać bądź czytać? Muszę wtedy zrobić eviction. Jeśli natomaist jeste w S to jeśli ktoś chce odczytać dane to nie zmieniam stanu natomiast jeśli ktoś chce zmodyfikować dane to muszę zmienić stan na I.

## Zadanie 2 poddaje sie

_Zdefiniuj pojęcie modelu spójności pamięci (ang. memory consistency model)._

**model spójności pamięci** - Model spójności jest zasadniczo kontraktem między procesami a pamięcią. Zgodnie z tym kontraktem jeśli procesy zgodzą się podporządkować pewnym zasadom, to pamięć obiecuje zachowywać się poprawnie.

_Następnie opowiedz jakie gwarancje daje programiście spójność sekwencyjna._

- operacje dotyczące pamięci i należące do różnych procesów są wykonywane w pewnej określonej kolejności;

- operacje każdego pojedycznego procesu są wykonywane w porządku określonym przez jego program.

::: spoiler
Pierwszy warunek mówi o tym, że lokalne uporządkowanie operacji powinno być zachowane w obrazie przetwarzania w każdym procesie.
Dotyczy to oczywiście operacji wykonywanych w danym węźle oraz
wszystkich zapisów, które zostały zgłoszone. Odczyty wykonywane na innych węzłach nie są brane pod uwagę, ponieważ są one realizowane jedynie lokalnie. Zapisy natomiast muszą być propagowane do wszystkich węzłów.
Drugi warunek mówi o tym, że wszystkie zapisy w systemie muszą być globalnie uszeregowane. Innymi słowy: istnieje jedna, globalnie ustalona kolejność wykonywania wszystkich zapisów, które zostały zlecone w systemie. Zostało to zdefiniowane w ten sposób, że dla każdej pary operacji zapisu w1 i w2 wszystkie węzły albo realizują najpierw w1 a później w2, albo najpierw w2 a później w1. W skrócie można więc powiedzieć, że spójność sekwencyjna wymusza globalne uporządkowanie zapisów.
:::
cahir cos takiego gadal jeszcze:

poprzez wprowadzenie fence'ów zapewniamy sobie, że instrukcje przed płotkiem rozpoczynającym nie wykonają się za nim, instrukcje między płotkami nie mogą się wykonać poza nimi, a instrukcje za płotkami nie wskoczą do środka.

_Niestety procesory wykonujące instrukcje poza porządkiem programu potrafią zmienić kolejność żądań odczytu i zapisu pamięci, co może zostać zaobserwowane przez inne procesory.
Artykuł „Memory ordering” opisuje model pamięci implementowany przez architekturę x86-64 i ARMv7. Wyjaśnij gwarancje, które daje programiście każdy z tych modeli. Wybierz ciąg instrukcji load i store, a następnie powiedz, które z nich procesor może zmieniać kolejnością wysyłając
do magistrali pamięci._

## Zadanie 3

Na ARMie możliwe jest, by jeden z wątków (T0) wczytał wielkość blocked[1] na samym początku. T1 wczytuje blocked[0]=false. Potem oba wątki wykonują resztę instrukcji sekwencyjnie, a T0 ustawia turn=1, jako drugi.
Oba wchodzą do sekcji krytycznej.

## Zadanie 4 Marcin
**blokada współdzielona** - Blokada współdzielona wprowadza nowy rodzaj sekcji krytycznej: w jej środku może znajdować się albo jeden wątek piszący, albo wiele wątków czytających. Wątek chcący czytać, wywołując pthread `rwlock_rdlock`, wejdzie do sekcji krytycznej lub zostanie zablokowany do czasu aż w sekcji nie będzie wątku piszącego. Wątki chcące pisać wywołują pthread `rwlock wrlock`. Wyjście z sekcji krytycznej realizowane jest przez pthread `rwlock_unlock`. Faworyzowanie wątków piszących lub czytających w dostępie do blokady jest zależne od aktualnej polityki systemowej albo od implementacji, w przypadku braku takiej polityki.
::: spoiler Wątpliwe rozwiązanie

class SharedLock {
  private:
    int read_count;
    bool write_flag;
    std::mutex lock;
    std::condition_variable cv_read, cv_write;
  
  public:
    SharedLock() : read_count(0), write_flag(false) {}
  
    void init() {} // optional, not necessary for implementation

    void rdlock() {
      std::unique_lock<std::mutex> ul(lock);
      cv_read.wait(ul, [this](){return !write_flag;});
      ++read_count;
    }

    void wrlock() {
      std::unique_lock<std::mutex> ul(lock);
      cv_write.wait(ul, [this](){return !write_flag && read_count == 0;});
      write_flag = true;
    }

    void unlock() {
      std::unique_lock<std::mutex> ul(lock);
      if (write_flag) {
        write_flag = false;
        cv_write.notify_one();
      } else {
        --read_count;
        if (read_count == 0) {
          cv_write.notify_one();
        }
      }
    }
};

:::
## Zadanie 5

#include "csapp.h"

static __thread unsigned seed;

static void rand_usleep(int min, int max) {
  usleep(rand_r(&seed) % (max - min + 1) + min);
}

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

/* XXX Please use following function to simulate malicious scheduler.
 * Just insert a call to rand_yield between instructions in your solution. */
static __unused void rand_yield(void) {
  /* Once every 100 calls to this function (on average)
   * it yields and lets kernel choose another thread. */
  if (rand_r(&seed) % 100 == 42)
    sched_yield();
}
#else
#define outc(c)
#define rand_yield()
#endif

typedef struct ramen {
  /* TODO: Put internal state & mutexes & condvars here. */
  sem_t waiter;
  pthread_cond_t is_full;
  pthread_cond_t wait_for_others;
  pthread_mutex_t mutex;
  unsigned int leaving;
  unsigned int waiting;
  unsigned int seats;
  unsigned int at_the_table;
} ramen_t;

static void ramen_init(ramen_t *r, unsigned seats) {
  /* TODO: Initialize internal state of ramen restaurant. */
  r->leaving = 0;
  r->at_the_table = 0;
  r->seats = seats;
  r->waiting = 0;
  Sem_init(&r->waiter, 0, seats);
  pthread_cond_init(&r->is_full, NULL);
  pthread_cond_init(&r->wait_for_others, NULL);
  pthread_mutex_init(&r->mutex, NULL);

}

static void ramen_destroy(ramen_t *r) {
  /* TODO: Destroy all synchronization primitives. */
  Sem_destroy(&r->waiter);
  pthread_cond_destroy(&r->is_full);
  pthread_cond_destroy(&r->wait_for_others);
  pthread_mutex_destroy(&r->mutex);
}

static void ramen_wait(ramen_t *r) {
  /* TODO: Enter the restaurant unless it's full or people haven't left yet. */
  if (r->at_the_table == r->seats || r->waiting > 0){
    r->waiting++;
    pthread_cond_wait(&r->is_full, &r->mutex);
    r->waiting--;
  }
  r->at_the_table++;
}

static void ramen_finish(ramen_t *r) {
  /* TODO: Finished eating, so wait for all other to finish before leaving. */
  r->leaving++;
  while (r->leaving != r->at_the_table){
    pthread_cond_wait(&r->wait_for_others, &r->mutex);
  }
  pthread_cond_broadcast(&r->wait_for_others);
  r->leaving--;
  r->at_the_table--;
  assert(r->leaving == r->at_the_table);

  if (r->leaving == 0){
    pthread_cond_broadcast(&r->is_full);
  }
}

void *customer(void *data) {
  ramen_t *r = data;

  seed = (unsigned)pthread_self();

  while (true) {
    /* Wait till you get hungry. */
    rand_usleep(5000, 10000);

    /* Queue for delicious ramen. */
    pthread_mutex_lock(&r->mutex);
    outc('.');
    ramen_wait(r);
    pthread_mutex_unlock(&r->mutex);

    /* It's so yummy! */
    outc('@');
    rand_usleep(1000, 2000);

    /* Time to leave, but don't be rude or else... */
    pthread_mutex_lock(&r->mutex);
    ramen_finish(r);
    outc('/');
    pthread_mutex_unlock(&r->mutex);
  }
}

#define THREADS 10
#define SEATS 5

int main(void) {
  ramen_t r;
  ramen_init(&r, SEATS);

  pthread_t tid[THREADS];

  for (int i = 0; i < THREADS; i++)
    Pthread_create(&tid[i], NULL, customer, &r);

  for (int i = 0; i < THREADS; i++)
    Pthread_join(tid[i], NULL);

  ramen_destroy(&r);
  return 0;
}

## Zadanie 6

#include "csapp.h"

static __thread unsigned seed;

static void rand_usleep(int min, int max) {
  usleep(rand_r(&seed) % (max - min + 1) + min);
}

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

/* XXX Please use following function to simulate malicious scheduler.
 * Just insert a call to rand_yield between instructions in your solution. */
static __unused void rand_yield(void) {
  /* Once every 100 calls to this function (on average)
   * it yields and lets kernel choose another thread. */
  if (rand_r(&seed) % 100 == 42)
    sched_yield();
}
#else
#define outc(c)
#define rand_yield()
#endif

typedef struct office {
  /* TODO: Put internal state & mutexes & condvars here. */
  sem_t chairs;
  sem_t new_client;
  sem_t is_done;
  unsigned taken;
  unsigned seats;
  int serving;
  pthread_mutex_t mutex;
} office_t;

static void office_init(office_t *o, unsigned seats) {
  /* TODO: Initialize internal state of post office. */
  o->taken = 0;
  o->seats = seats;
  o->serving = false;
  Sem_init(&o->chairs, 0, 0);
  Sem_init(&o->new_client, 0, 0);
  Sem_init(&o->is_done, 0, 0);
  pthread_mutex_init(&o->mutex, NULL);
}

static void office_destroy(office_t *o) {
  /* TODO: Destroy all synchronization primitives. */
  Sem_destroy(&o->chairs);
  Sem_destroy(&o->new_client);
  Sem_destroy(&o->is_done);
  pthread_mutex_destroy(&o->mutex);
}

static bool customer_walk_in(office_t *o) {
  /* TODO: No seats then leave, otherwise wait for a clerk call. */
  pthread_mutex_lock(&o->mutex);

  if (o->taken == o->seats){
    pthread_mutex_unlock(&o->mutex);
    return false;
  }

  if(o->taken == 0 && !o->serving){
    o->serving = true;
    Sem_post(&o->new_client);
  }
  else{
    o->taken++;
    // outc('?');
    pthread_mutex_unlock(&o->mutex);  
    Sem_wait(&o->chairs);
    pthread_mutex_lock(&o->mutex);
    o->serving = true;
    o->taken--;
  }
  pthread_mutex_unlock(&o->mutex);
  Sem_wait(&o->is_done);
  return true;
}

static void clerk_wait(office_t *o) {
  /* TODO: Wait for a customer or call one from a seat. */
  pthread_mutex_lock(&o->mutex);
  if(o->taken > 0){
    Sem_post(&o->chairs);
    pthread_mutex_unlock(&o->mutex);
  }
  else {
    o->serving = false;
    pthread_mutex_unlock(&o->mutex);
    Sem_wait(&o->new_client); 
  }
}

static void clerk_done(office_t *o) {
  /* TODO: Tell the customer that the job is done. */
  pthread_mutex_lock(&o->mutex);
  Sem_post(&o->is_done);
  pthread_mutex_unlock(&o->mutex);
}

static void *customer(void *data) {
  office_t *b = data;

  seed = (unsigned)pthread_self();

  while (true) {
    if (customer_walk_in(b)) {
      /* Yay! I sent my registered mail :) */
      outc('+');
      /* I guess they'll force me to go there again... */
      rand_usleep(5000, 10000);
    } else {
      /* Heck! No empty seats :( */
      outc('-');
      /* Try again in a while... */
      rand_usleep(500, 1000);
    }
  }

  return NULL;
}

static void *clerk(void *data) {
  office_t *b = data;

  seed = (unsigned)pthread_self();

  while (true) {
    /* Wait for customer to walk in or grab one that is seated. */
    clerk_wait(b);
    /* Do the paperwork! */
    rand_usleep(500, 1000);
    /* Another customer leaving happy? */
    clerk_done(b);
  }

  return NULL;
}

#define SEATS 4
#define CUSTOMERS 12

int main(void) {
  office_t o;
  office_init(&o, SEATS);

  pthread_t clerkThread;
  pthread_t customerThread[CUSTOMERS];

  Pthread_create(&clerkThread, NULL, clerk, &o);
  for (int i = 0; i < CUSTOMERS; i++)
    Pthread_create(&customerThread[i], NULL, customer, &o);

  pthread_join(clerkThread, NULL);
  for (int i = 0; i < CUSTOMERS; i++)
    Pthread_join(customerThread[i], NULL);

  office_destroy(&o);
  return 0;
}

## Zadanie 7