# Ćwiczenia 14, grupa cz. 10-12, 2 lutego 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 -- 8** z **listy 13** oraz całą **listę 14**.

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

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

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

## Zadanie 1
:::danger
Autor:

**Spójność pamięci podręcznych** (*cache coherence*) polega na zapewnieniu pewnej poprawności (spójności) danych w czasie pomiędzy pamięciami podręcznymi. Np. gdy procesory A i B wczytają do pamięci zmienną x, to gdy procesor A zmieni jej wartość, wtedy procesor B musi umieć to w jakiś sposób stwierdzić.


To, że powyższy program działa szybciej dla pewnych wartości zmiennej `spacing`, wynika z konstrukcji i zasady działania pamięci cache. Procesor wczytując dane do swojej pamięci nie czyta pojedynczej liczby (np. `int`), lecz całą linię (najczęściej 64B), w której może zmieścić się kilka takich zmiennych. Zakładając natomiast tradycyjną reprezentację tablicy w pamięci, tj. komórka po komórce, okazuje się, że chociaż pozornie poszczególne komórki tablicy są "prywatne" dla odpowiadających im wątków, to tak naprawdę każdy z wątków reaguje na zmiany dokonane przez sąsiednie wątki aktualizacją stanu swojej linii.
W sytuacji, gdy `spacing = 8` uzyskujemy faktyczną prywatność tych komórek, ponieważ w linii cache'u wczytanej przez dany wątek znajduje się tylko i wyłącznie jego komórka tablicy, dzięki czemu unikamy zbędnego ruchu na szynie koniecznego do komunikacji między pamięciami podręcznymi różnych procesorów.


W protokole **MSI** każda linia w cache'u jest w jednym z trzech stanów: **M**odified (zmodyfikowana), **S**hared (współdzielona) lub **I**nvalid (nieaktualna).

https://en.wikipedia.org/wiki/MSI_protocol#State_Machine
:::

## Zadanie 2
:::success
Autor: Zuzanna Kania

**Model spójności pamięci** określa w jakiej kolejności procesor może wykonywać otrzymane instrukcje (i tym samym w jakiej kolejności ich efekty zobaczą pozostałe procesory).

**Spójność sekwencyjna** to najbardziej restrykcyjny model spójności, wedle którego instrukcje zawsze są wykonywane w takiej kolejności, w jakiej otrzymał je procesor.


Architektura x86-64 daje programiście praktycznie takie same gwarancje jak spójność sekwencyjna za wyjątkiem tego, że instrukcja zapisu może zostać przesunięta za instrukcje odczytu spod innego adresu.

Architektura ARMv7 natomiast nie daje programiście praktycznie żadnych gwarancji, ponieważ instrukcje odnoszące się do różnych adresów mogą być ze sobą przeplatane w dowolny sposób. Przez to programista chcący wymusić pewien porządek wykonania jest zmuszony użyć do tego celu barier.

Weźmy przykładowy ciąg operacji:

store A
load B
load C
store C
store B
load A

Na architekturze x86-64 jedynie `store A` może zostać przesunięte za `load B` i `load C` oraz `store B` może zostać przesunięte za `load A`.

Natomiast architektura ARMv7 dopuszcza również takie modyfikacje jak np. wykonanie `store C` po `store B` czy wykonanie `load B` po `load C` i `store C`.
:::

## Zadanie 3
:::success
Autor: Zuzanna Kania

### x86-64

Zapis z linii 6 może zostać przesunięty za pętlę z linii 8. Gdy tak się zdarzy w obu wątkach to może się okazać, że oba znalazły się w sekcji krytycznej, co jest sprzeczne z poprawnością rozwiązania problemu wzajemnego wykluczenia.

### ARMv7

Podobnie jak powyżej, ale może się również zdarzyć, że pętla z linii 8 zostanie np. przesunięta za sekcję krytyczną, co tym bardziej psuje poprawne wzajemne wykluczanie.

### Poprawiony kod

shared boolean blocked[2] = {false, false};
shared int turn = 0;

void P (int id) {
    while (true) {
        blocked[id] = true;
        turn = 1 - id;
        fence();
        while (blocked[1 - id] && turn == 1 - id)
            continue;
        fence();
        /* critical section */
        fence();
        blocked[id] = false;
    }
}

:::

## Zadanie 4
:::danger
Autor:
:::

## Zadanie 5
:::success
Autor: Jan Jankowicz
:::

#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. */
  int seats_number;
  int free_seats;
  bool quiting;
  pthread_mutex_t check_state_mutex;
  pthread_cond_t eating_session_end;
} ramen_t;

static void ramen_init(ramen_t *r, unsigned seats) {
  /* TODO: Initialize internal state of ramen restaurant. */
  r->seats_number = seats;
  r->free_seats = seats;
  r->quiting = false;
  Pthread_mutex_init(&r->check_state_mutex, NULL);
  Pthread_cond_init(&r->eating_session_end, NULL);
}

static void ramen_destroy(ramen_t *r) {
  /* TODO: Destroy all synchronization primitives. */
  Pthread_mutex_destroy(&r->check_state_mutex);
  Pthread_cond_destroy(&r->eating_session_end);
}

static void ramen_wait(ramen_t *r) {
  /* TODO: Enter the restaurant unless it's full or people haven't left yet. */
  Pthread_mutex_lock(&r->check_state_mutex);
  rand_yield();
  while (r->free_seats == 0 || r->quiting) {
  	rand_yield();
  	Pthread_cond_wait(&r->eating_session_end, &r->check_state_mutex);
  	rand_yield();
  }
  
  r->free_seats--;
  rand_yield();
  
  Pthread_mutex_unlock(&r->check_state_mutex);
}

static void ramen_finish(ramen_t *r) {
  /* TODO: Finished eating, so wait for all other to finish before leaving. */
  Pthread_mutex_lock(&r->check_state_mutex);
  rand_yield();
  r->free_seats++;
  rand_yield();
  if (r->free_seats == r->seats_number) {
  	rand_yield();
  	r->quiting = false;
  	rand_yield();
  	Pthread_cond_broadcast(&r->eating_session_end);
  } else {
  	r->quiting = true;
  	rand_yield();
  	Pthread_cond_wait(&r->eating_session_end, &r->check_state_mutex);
  	rand_yield();
  }
  rand_yield();
  Pthread_mutex_unlock(&r->check_state_mutex);
}

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. */
    outc('.');
    ramen_wait(r);

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

    /* Time to leave, but don't be rude or else... */
    ramen_finish(r);
    outc('_');
  }
}

#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
:::success
Autor: Zuzanna Kania

#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. */
  pthread_mutex_t door;
  pthread_mutex_t window;
  pthread_cond_t wait_for_customer;
  pthread_cond_t wait_for_clerk;
  pthread_cond_t wait_for_job_done;
  unsigned free_seats;
  unsigned waiting;
  bool busy;
  bool done;
} office_t;

static void office_init(office_t *o, unsigned seats) {
  /* TODO: Initialize internal state of post office. */
  pthread_mutex_init(&o->door, NULL);
  pthread_mutex_init(&o->window, NULL);
  pthread_cond_init(&o->wait_for_customer, NULL);
  pthread_cond_init(&o->wait_for_clerk, NULL);
  pthread_cond_init(&o->wait_for_job_done, NULL);
  o->free_seats = seats;
  o->waiting = 0;
  o->busy = false;
  o->done = false;
}

static void office_destroy(office_t *o) {
  /* TODO: Destroy all synchronization primitives. */
  pthread_mutex_destroy(&o->door);
  pthread_mutex_destroy(&o->window);
  pthread_cond_destroy(&o->wait_for_customer);
  pthread_cond_destroy(&o->wait_for_clerk);
  pthread_cond_destroy(&o->wait_for_job_done);
}

static bool customer_walk_in(office_t *o) {
  /* TODO: No seats then leave, otherwise wait for a clerk call. */
  pthread_mutex_lock(&o->door);
  if (o->free_seats == 0) { // no free seats - release the door lock and go
    printf("No free seats, I'll come back later...\n");
    pthread_mutex_unlock(&o->door);
    return false;
  }
  o->free_seats--; // take a free seat
  o->waiting++;
  printf("Hello, I take one free seat, %d left\n", o->free_seats);
  pthread_mutex_unlock(&o->door);
  pthread_cond_signal(&o->wait_for_customer); // notify the clerk that a customer has arrived
  pthread_mutex_lock(&o->window); // try to come at the window
  while (o->busy) // clerk is busy - wait patiently
    pthread_cond_wait(&o->wait_for_clerk, &o->window);
  o->busy = true; // clerk is now serving me - tell everybody he's busy
  while (!o->done) // wait for clerk to finish his work
    pthread_cond_wait(&o->wait_for_job_done, &o->window);
  o->busy = false; // work done
  o->done = false;
  pthread_mutex_unlock(&o->window); // leave the window
  return true;
}

static void clerk_wait(office_t *o) {
  /* TODO: Wait for a customer or call one from a seat. */
  pthread_mutex_lock(&o->door);
  while (o->waiting == 0) // no customers waiting, wait for one to come
    pthread_cond_wait(&o->wait_for_customer, &o->door);
  o->free_seats++;
  o->waiting--;
  pthread_cond_broadcast(&o->wait_for_clerk); // call waiting customers
  printf("Clerk started serving one customer, %d free seats left\n", o->free_seats);
  pthread_mutex_unlock(&o->door);
}

static void clerk_done(office_t *o) {
  /* TODO: Tell the customer that the job is done. */
  o->done = true;
  pthread_cond_signal(&o->wait_for_job_done); // work done, notify the customer
}

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(1000, 5000);
    /* 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
:::danger
Autor:
:::