# Ćwiczenia 14, grupa śr. 12-14, 1 lutego 2023

###### tags: `PRW22` `ć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!**

:::info
Oprócz zadań z dzisiejszej listy, do zadeklarowania pozostały jeszcze **zadania 5 -- 7** z **listy 13**. Zadania należy zadeklarować w formularzu z poprzedniego tygodnia:
[https://hackmd.io/@iiuwr-kba/rkghoD0jo/edit](https://hackmd.io/@iiuwr-kba/rkghoD0jo/edit)
:::

:::success
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | | | | |
Wiktor Bukowski | | | | | | | | | |
Jan Dalecki | | | | | | | | | |
Mikołaj Depta | X | X | X | X | X | | X | | |
Kamil Galik | | | | | | | | | |
Bartosz Głowacki | | | | | | | | | |
Michał Hetnar | | | | | | | | | |
Adam Jarząbek | | | | | | | | | |
Michał Kierul | | | | | | | | | |
Mateusz Kisiel | | | | | | | | | |
Maksymilian Komarnicki | | | | | | | | | |
Julia Matuszewska | | | | | | | | | |
Andrzej Morawski | | | | | | | | | |
Wojciech Pokój | | | | | | | | | |
Marcin Sarnecki | | | | | | | | | |
Bartosz Szczeciński | | | | | | | | | |
Tomasz Wołczański | | | | | | | | | |
Marcin Wróbel | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Mikołaj Depta
:::


### Wstęp

Licznik współdzielony jest strukturą danych umożliwiającą wielu wątkom wykonanie operacji zwiększenia i/lub zmniejszenia jego aktualnej wartości.
Licznik taki nie musi być wcale linearyzowalny do licznika sekwencyjnego. Chcemy jedynie, żeby zwracane wartości się nie powtarzały oraz, żeby żadna wartość nie została pominięta. Mogą one natomiast być zwracane w dowolnej kolejności.


*Ogólny schemat współdzielonego licznika opartego na sieci zliczającej*

**Własność krokowa** (step property) gwarantuje, że żadne wartości nie zostaną pominięte.

Operacja get and increment realizowana jest poprzez przejście takiej sieci przez wątek, zinkrementowanie licznika (atomowy integer) do którego wątek dotarł a następnie wyliczenie wartości jaka odpowiada temu licznikowi (jak na rysunku powyżej).


*Szczegółowy schemat sieci zliczającej z 4 wejściami/wyjściami*


## Zadanie 2
:::success
Autor: Mikołaj Depta
:::


*Indukcyjna struktura sieci bitonic\[2k\]*

*Indukcyjna struktura sieci merger\[2k\]*

Sieć bitonic\[2k\] to sieć zliczająca dla 2k wejść.
Sieć merger\[2k\] to sieć, która łączy dwa ciągi z własnością kroku w jeden ciąg z własnością kroku.

Fakt 1. Jeśli ciąg wejść o `n` wierszach ma własność kroku to podciagi utworzone z wierszy o parzystych i nieparzystych indeksach też ją mają oraz różnią się łączną liczbą elementów o co najwyżej 1 na korzyść podciągu o parzystych wierszach.

*Podział wierszy wejścia na parzyste i nieparzyste*

Fakt 2. Rozważmy dwa ciągi wejść `a` i `b`, niech oba mają właności kroku. Sekwencje `a'` i `b'` składające się z odpowiednio:
- dla `a'` z parzystych wierszy `a` i nieparzystych wierszy `b`
- dla `b'` z parzystych wierszy `b` i nieparzystych wierszy `a`


Z Faktu 1. wiemy, że podciągi parzystych i nieparzystych wierszy różnią się liczbą elementów o co najwyżej o 1.
Można rozpatrzeć wszystkie 4 wersje różnic rozmiarów podciągów: parzyste `a` i nieparzyste `a`, parzyste `b` i nieparzyste `b` i pokazać, że pociągi `a'` i `b'` również będą różnić się o co najwyżej 1.

### Dowód poprawności sieci zliczającej bitonic\[2k\].

Patrząc na schemat sieci widać, że jeśli sieć merger\[2k\] działa poprawnie to sieć bitonic\[2k\], również działa poprawnie.

Jeśli pokażemy więc, że sieć merger działa poprawnie, to za darmo dostaniemy sieć bitonic.

**Podstawa indukcji**
Dla sieci bitonic podstawą indukcji jest bitonic\[2\] - zwykły balancer - ma własność kroku.
Dla sieci merger podstawą indukcji jest sieć merger\[4\]. Na wykładzie pokazaliśmy, że działa ona poprawnie - znowu wystarczy rozpatrzeć przypadki.

**Krok indukcji**
Załóżmy, że sieć merger\[k\] działa poprawnie. Chcemy pokazać, że wówczas sieć merger\[2k\] również działa poprawnie.

Doprecyzowanie: Sieć merger\[k\] działa poprawnie jeśli otrzyma na swoje wejścia dwa ciągi rozmiaru k/2 o własności kroku i na wyjściu wygeneruje ciąg rozmiaru k o własności kroku.


Lemat 1. Jeśli sieci bitonic\[k\] i merger\[k\] działają poprawnie, to sieć merger\[2k\] również działa poprawnie.

Sieć merger\[2k\] otrzymuje na górną połowę wejść (to co otrzyma górne merger\[k\] z diagramu sieci merger) podciąg parzystych wierszy z górnej sieci bitonic\[k\] i nieparzystych z dolnej sieci bitonic\[k\] analogicznie dolna połowa wejść to nieparzyste wejścia z górnej bitonic\[k\] i parzyste z dolnej sieci bitonic\[k\].

Ponieważ, dolna i górna sieć merger\[k\] działa poprawnie i otrzymała na wejściach dwa podciągi rozmiaru k/2 o właściwości kroku to na wyjściach wygenerują one ciągi o własności kroku rozmiaru k. Dodatkowo z faktu 2. wiemy, że ciągi te różnią się długością o co najwyżej 1.

Teraz ciągi te są przepuszczone przez k balanserów zgodnie ze schematem powyżej dadzą ciąg długości 2k o właności kroku.

Ciągi otrzmane z sieci merger\[k\] różnią się ilością elementów o co najwyżej 1, mają własność kroku i są długości k.

i'ty wiersz podciągu otrzymanego z sieci merger\[k\] zostaje przekazany do i'tego balansera na wyjściu. Ponieważ, ciągi mają własność kroku to wiersze o większej ilości elementów będą ustawiały swoje elementy na przodzie wyjścia z merger\[2k\].

CKD

## Zadanie 3
:::success
Autor: Mikołaj Depta
:::

public class WaitFreeBalancer {
    CombiningTree counter;

    WaitFreeBalancer(int threadCount) {
        this.counter = new CombiningTree(threadCount);
    }
    
    public int traverse() {
        return counter.getAndIncrement() % 2;
    }
}

// lub 

public class WaitFreeBalancer {
    AtomicInteger counter;

    WaitFreeBalancer(int threadCount) {
        this.counter = new AtomicInteger(0);
    }
    
    public int traverse() {
        return counter.getAndIncrement() % 2;
    }
}

## Zadanie 4
:::success
Autor: Mikołaj Depta
:::


## Zadanie 5
:::success
Autor: Mikołaj Depta
:::


### `SimpleReadWriteLock`

public class SimpleReadWriteLock implements ReadWriteLock {
  int readers;
  boolean writer;
  Lock lock;
  Condition condition;
  Lock readLock, writeLock;
  public SimpleReadWriteLock() {
    writer = false;
    readers = 0;
    lock = new ReentrantLock();
    readLock = new ReadLock();
    writeLock = new WriteLock();
    condition = lock.newCondition();
  }
  public Lock readLock() {
    return readLock;
  }
  public Lock writeLock() {
    return writeLock;
  }
  // Definicje zamków wyniesione poniżej
}

*Definicja klasy zamka SimpleReadWriteLock*

class ReadLock implements Lock {
  public void lock() {
    lock.lock();
    try {
      while (writer)
        condition.await();
      readers++;
    } finally {
      lock.unlock();
    }
  }
  
  public void unlock() {
    lock.lock();
    try {
      readers--;
      if (readers == 0)
        condition.signalAll();
    } finally {
      lock.unlock();
    }
  }
}

*ReadLock dla zamka SimpleReadWriteLock*

class WriteLock implements Lock {
  public void lock() {
    lock.lock();
    try {
      while (readers > 0 || writer)
        condition.await();
      writer = true;
    } finally {
      lock.unlock();
    }
  }
  
  public void unlock() {
    lock.lock();
    try {
      writer = false;
      condition.signalAll();
    } finally {
      lock.unlock();
    }
  }
}

*WriteLock dla zamka SimpleReadWriteLock*

### `FifoReadWriteLock`

public class FifoReadWriteLock implements ReadWriteLock {
  int readAcquires, readReleases;
  boolean writer;
  Lock lock;
  Condition condition;
  Lock readLock, writeLock;
  public FifoReadWriteLock() {
    readAcquires = readReleases = 0;
    writer = false;
    lock = new ReentrantLock();
    condition = lock.newCondition();
    readLock = new ReadLock();
    writeLock = new WriteLock();
  }
  public Lock readLock() {
    return readLock;
  }
  public Lock writeLock() {
    return writeLock;
  }
  // Definicje zamków wyniesione poniżej
}

*Definicja klasy zamka FifoReadWriteLock*

private class ReadLock implements Lock {
  public void lock() {
    lock.lock();
    try {
      while (writer)
        condition.await();
      readAcquires++;
    } finally {
      lock.unlock();
    }
  }
  
  public void unlock() {
    lock.lock();
    try {
      readReleases++;
      if (readAcquires == readReleases)
        condition.signalAll();
    } finally {
      lock.unlock();
    }
  }
}

*ReadLock dla zamka FifoReadWriteLock*

private class WriteLock implements Lock {
  public void lock() {
    lock.lock();
    try {
      while (writer)
        condition.await();
      writer = true;
      while (readAcquires != readReleases)
        condition.await();
    } finally {
      lock.unlock();
    }
  }
  public void unlock() {
    lock.lock();
    try {
      writer = false;
      condition.signalAll();
    } finally {
      lock.unlock();
    }
  }
}

*WriteLock dla zamka FifoReadWriteLock*

## Zadanie 6
:::danger
Autor:
:::

## Zadanie 7
:::success
Autor: Mikołaj Depta
:::

class SymmetricReadWriteLock {
    int redAcquires, redReleases;
    int blueAcquires, blueReleases;
    int redWaiting, blueWaiting;
    Lock lock;
    Condition condition;
    Condition wait_finished;
    RedLock redLock;
    BlueLock blueLock;
    public SymmetricReadWriteLock() {
        redAcquires = redReleases = 0;
        blueAcquires = blueReleases = 0;
        redWaiting = blueWaiting = 0;
        lock = new ReentrantLock();
        condition = lock.newCondition();
        wait_finished = lock.newCondition();
        redLock = new RedLock();
        blueLock = new BlueLock();
    }
    public RedLock redLock() {
        return redLock;
    }
    public BlueLock blueLock() {
        return blueLock;
    }
    public class RedLock {
        public void lock() {
            lock.lock();
            try {
                if (blueWaiting > 0) {
                    wait_finished.await(); // await all blue threads finish waiting
                }
                // od teraz nowo przychodzące niebieskie zobaczą,
                // że ktoś czerwony czeka i ustąpią
                redWaiting++;
                // jeśli jakieś niebieskie czekają na wejście - ustąp
                // jeśli jakieś niebieskie mają zamek czekaj
                while (blueAcquires != blueReleases)
                    condition.await();
                redWaiting--;
                if (redWaiting == 0) {
                    wait_finished.signalAll();
                }
                redAcquires++;
                System.out.println("R");
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                lock.unlock();
            }
        }

        public void unlock() {
            lock.lock();
            try {
                System.out.println("r");
                redReleases++;
                // wszystkie czerwone wyszły - daj znać czekającym niebieskim
                if (redAcquires == redReleases)
                    condition.signalAll();
            } finally {
                lock.unlock();
            }
        }
    }
    public class BlueLock {
        public void lock() {
            lock.lock();
            try {
                if (redWaiting > 0) {
                    wait_finished.await(); // await all blue threads finish waiting
                }
                blueWaiting++;
                // jeśli jakieś niebieskie czekają na wejście - ustąp
                while (redAcquires != redReleases)
                    condition.await();
                blueWaiting--;
                if (blueWaiting == 0) {
                    wait_finished.signalAll();
                }
                blueAcquires++;
                System.out.println("B");
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                lock.unlock();
            }
        }
        public void unlock() {
            lock.lock();
            try {
                System.out.println("b");
                blueReleases++;
                if (blueAcquires == blueReleases)
                    condition.signalAll();
            } finally {
                lock.unlock();
            }
        }
    }
}

class RedThread extends Thread {
    SymmetricReadWriteLock.RedLock lock;

    RedThread(SymmetricReadWriteLock symLock) {
        lock = symLock.redLock();
    }

    public void run(){
        while (true) {
            lock.lock();
            try {
                sleep(1000 % ThreadLocalRandom.current().nextInt(0, 500));
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                lock.unlock();
            }
        }
    }
}

class BlueThread extends Thread {
    SymmetricReadWriteLock.BlueLock lock;

    BlueThread(SymmetricReadWriteLock symLock) {
        lock = symLock.blueLock();
    }

    public void run(){
        while (true) {
            lock.lock();
            try {
                sleep(1000 % ThreadLocalRandom.current().nextInt(1, 500));
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                lock.unlock();
            }
        }
    }
}

public class SymmetricReadWriteLock {
    public static void main(String[] args) {
        SymmetricReadWriteLock lock = new SymmetricReadWriteLock();
        ArrayList<RedThread> reds = new ArrayList<RedThread>(10);
        ArrayList<BlueThread> blues = new ArrayList<BlueThread>(10);
        for (int i = 0; i < 10; i++) {
            reds.add(new RedThread(lock));
            blues.add(new BlueThread(lock));
        }
        
        for (int i = 0; i < 10; i++) {
            blues.get(i).start();
            reds.get(i).start();
        }
        while (true) {
            continue;
        }
    }
}

## Zadanie 8
:::danger
Autor:
:::

## Zadanie 9
:::danger
Autor:
:::