# Ćwiczenia 13, grupa cz. 16-18, 18 stycznia 2024

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

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | | | | | | | |
Paweł Borek | | | | | | | |
Arti Brzozowski | | | | | | | |
Mateusz Golisz | | | | | | | |
Kacper Jóźwiak | | | | | | | |
Julia Konefał | | | | | | | |
Adam Korta | x | | | | | | |
Jakub Mikołajczyk | X | | X | X | | | |
Bartosz Morasz | x | | x | | | | |
Andrzej Morawski | x | x | x | | | | |
Aleksandra Nicpoń | x | x | x | | | | |
Mateusz Reis | x | | x | | | | |
Tomasz Stachurski | X | | X | | | | |
Marcel Szelwiga | X | X | X | | | | |
Volha Tsekalo | x | x | | | | | |
Martyna Wybraniec | x | x | x | | | | |
Denys Zinoviev | | | | | | | |
Dominik Olejarz | x | | x | | | | |
:::

Tutaj można zadeklarować zaległe zadania 1 i 4 z listy 12:

:::danger
| | 12.1 | 12.4 |
| ----------------------:| ----- | ----- |
| Tomasz Stachurski | | X |
| Marcel Szelwiga | X | X |
| Andrzej Morawski | X | |
| | | |
:::

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

## Zadanie 1
:::success
Autor: Bartosz Morasz
:::


## Zadanie 2
:::success
Autor: Martyna Wybraniec
:::


Klasa `RangePolicy` odpowiada za dynamiczne ustawianie przedziału, z którego wątek losuje komórkę EliminationArray. Jeśli zauważa dużo timeoutów, zmniejsza zakres i odwrotnie.

Punkty linearyzacji:
- jeśli metoda `push()` lub `pop()` zmodyfikowała `LockFreeStack` punktem linearyzacji będzie miejsce uzyskania dostępu do stosu
- jeśli doszło do eliminacji punkt linearyzacji to moment wymiany

## Zadanie 3
:::success
Autor: Marcel Szelwiga
:::

    ----[ ]----
   |           |
  [ ]         [ ]
 /   \       /   \
()   ()     ()   ()

public int getAndIncrement() {
	Stack<Node> stack = new Stack<Node>();
	Node myLeaf = leaf[ThreadID.get()/2];
	Node node = myLeaf;
	// precombining phase
	while (node.precombine()) {
		node = node.parent;
	}
	Node stop = node;
	// combining phase
	int combined = 1;
	for (node = myLeaf; node != stop; node = node.parent) {
		combined = node.combine(combined);
		stack.push(node);
	}
	// operation phase
	int prior = stop.op(combined);
	// distribution phase
	while (!stack.empty()) {
		node = stack.pop();
		node.distribute(prior);
	}
	return prior;
}

Faza `precombination` -- każdy wątek zaczyna od swojego liścia i idzie do korzenia, kończy swoją drogę jeśli trafi do jakiegoś wierzchołka jako drugi. Jeśli dojdzie do korzenia, to znaczy, że to on będzie inkrementował globalny licznik. Natomiast jeśli dotrze jako drugi to w późniejszych etapach dostanie on od innego wierzchołka policzoną już dla niego wartość. Jeśli wątek był pierwszy to będzie musiał zebrać wartości od wątków drugich i przekazać je odpowiednio wyżej, do wierzchołka, w którym on był drugi lub korzenia.

Faza `combination` -- w tej fazie wąkti idą do góry od liścia do korzenia i jeśli był pierwszy to zbiera wartość od swojego sąsiada i propaguje ją do góry. Wątek musi czekać na ten drugi. Tak całe drzewo, a w zasadzie cała używana część drzewa zostanie obsłużona przez jakiś wątek.

Faza `operation` -- w tej fazie wątki, które czekały na poinformowanie o stanie licznika są budzone oraz dowiadują się jaka jest ich wartość, muszą wtedy tą wartość rozpropagować w swoim poddrzewie.

Faza `distribution` -- w tej fazie wątek propaguje wartość na swoje poddrzewo.

## Zadanie 4
:::success
Autor: Jakub Mikołajczyk
:::






1.

2.
Ponieważ wywołanie ```op()``` i ```distibute()``` następuje po fazie ```combine```, zatem działają już na zablokowanych drzewach

3.

Szybszy wątek w fazie ```distribute``` policzył rezultat i zrzucił na nas odpowiedzialność za wyzerowanie ustawień wierzchołka

## Zadanie 5
:::success
Autor: Jakub Mikołajczyk
:::

package z5;

import java.util.Stack;

public class TriCombiningTree {

    TriNode[] leaf;

    public TriCombiningTree(int width) {
        TriNode[] nodes = new TriNode[width + width / 2];
        nodes[0] = new TriNode();
        for (int i = 1; i < nodes.length; i++) {
            nodes[i] = new TriNode(nodes[(i - 1) / 3]);
        }
        leaf = new TriNode[width];
        for (int i = 0; i < leaf.length; i++) {
            leaf[i] = nodes[nodes.length - i - 1];
        }
    }

    public int getAndIncrement(int ThreadID) throws Exception {
        Stack<TriNode> stack = new Stack<>();
        TriNode myLeaf = leaf[ThreadID/3];
        TriNode node = myLeaf;
        // precombining phase
        while (node.precombine()) {
            node = node.parent;
        }
        TriNode stop = node;
        // combining phase
        int combined = 1;
        for (node = myLeaf; node != stop; node = node.parent) {
            combined = node.combine(combined);
            stack.push(node);
        }
        // operation phase
        int prior = stop.op(combined);
        // distribution phase
        while (!stack.empty()) {
            node = stack.pop();
            node.distribute(prior);
        }
        return prior;
    }
}

package z5;
public class TriNode {


    enum CStatus {IDLE, FIRST, SECOND, THIRD, RESULT, ROOT;}

    CStatus cStatus;
    boolean lateLock;
    boolean waitLock;
    int waitingNodes, readyNodes;
    int firstValue;
    int[] secondVal = new int[2];
    int[] result = new int[2];
    TriNode parent;

    TriNode() {
        cStatus = CStatus.ROOT;
        lateLock = false;
        waitLock = false;
        waitingNodes = 0;
        readyNodes = 0;
    }

    TriNode(TriNode myParent) {
        parent = myParent;
        cStatus = CStatus.IDLE;
        lateLock = false;
        waitLock = false;
        waitingNodes = 0;
        readyNodes = 0;
    }

    synchronized boolean precombine() throws Exception {
        while (lateLock || waitingNodes >= 2) wait();

        switch (cStatus) {
            case IDLE:
                cStatus = CStatus.FIRST;
                return true;
            case FIRST:
                waitLock = true;
                waitingNodes = 1;
                cStatus = CStatus.SECOND;
                return false;
            case SECOND:
                waitingNodes = 2;
                cStatus = CStatus.THIRD;
                return false;
            case ROOT:
                return false;
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
    }

    synchronized int combine(int combined) throws InterruptedException {
        while (waitLock || readyNodes < waitingNodes) wait();

        firstValue = combined;
        lateLock = true;
        switch (cStatus) {
            case FIRST:
                return firstValue;
            case SECOND:
                return firstValue + secondVal[0];
            case THIRD:
                return firstValue + secondVal[0] + secondVal[1];
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
    }

    synchronized int op(int combined) throws InterruptedException, IllegalStateException {
        switch (cStatus) {
            case ROOT:
                int prior = result[0];
                result[0] += combined;
                return prior;
            case SECOND:
            case THIRD:
                secondVal[readyNodes] = combined;
                readyNodes++;
                if (readyNodes == waitingNodes) {
                    waitLock = false;
                    notifyAll();
                }
                while (cStatus != CStatus.RESULT) wait();
                readyNodes--;
                prior = result[readyNodes];
                if (readyNodes == 0) {
                    lateLock = false;
                    waitingNodes = 0;
                    notifyAll();
                    cStatus = CStatus.IDLE;
                }
                return prior;
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
    }

    synchronized void distribute(int prior) {
        switch (cStatus) {
            case FIRST:
                cStatus = CStatus.IDLE;
                lateLock = false;
                break;
            case SECOND:
                result[0] = prior + firstValue;
                cStatus = CStatus.RESULT;
                break;
            case THIRD:
                result[1] = prior + firstValue;
                result[0] = result[1] + secondVal[0];
                cStatus = CStatus.RESULT;
                break;
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
        notifyAll();
    }
}

## Zadanie 6
:::success
Autor: Jakub Mikołajczyk
:::

package z6;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;

public class ExchangeNode {

    enum CStatus {IDLE, FIRST, SECOND, ROOT;}

    CStatus cStatus;
    boolean lock;
    int firstValue;
    LockFreeExchanger<Integer> exchanger;
    ExchangeNode parent;

    ExchangeNode() {
        cStatus = CStatus.ROOT;
        lock = false;
    }

    ExchangeNode(ExchangeNode myParent) {
        parent = myParent;
        cStatus = CStatus.IDLE;
        lock = false;
        exchanger = new LockFreeExchanger<Integer>();
    }

    synchronized boolean precombine() throws Exception {
        while (lock) wait();

        switch (cStatus) {
            case IDLE:
                cStatus = CStatus.FIRST;
                return true;
            case FIRST:
                lock = true;
                cStatus = CStatus.SECOND;
                return false;
            case ROOT:
                return false;
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
    }

    synchronized int combine(int combined) throws InterruptedException, TimeoutException {
        lock = true;
        firstValue = combined;
        switch (cStatus) {
            case FIRST:
                return firstValue;
            case SECOND:
                return firstValue + exchanger.exchange(0, 10, TimeUnit.SECONDS);
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
    }

    synchronized int op(int combined) throws InterruptedException, IllegalStateException, TimeoutException {
        switch (cStatus) {
            case ROOT:
                int prior = firstValue;
                firstValue += combined;
                return prior;
            case SECOND:
                exchanger.exchange(combined, 10, TimeUnit.SECONDS);

                int result = exchanger.exchange(0, 10, TimeUnit.SECONDS);
                cStatus = CStatus.IDLE;
                lock = false;
                return result;
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
    }

    synchronized void distribute(int prior) throws InterruptedException, TimeoutException {
        switch (cStatus) {
            case FIRST:
                cStatus = CStatus.IDLE;
                lock = false;
                break;
            case SECOND:
                exchanger.exchange(firstValue + prior, 10, TimeUnit.SECONDS);
                break;
            default:
                throw new IllegalStateException("unexpected Node state " + cStatus);
        }
        notifyAll();
    }
}

## Zadanie 7
:::success
Autor: Jakub Mikołajczyk
:::

package z7;

import z5.TriCombiningTree;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.ReentrantLock;

public class Pool<T> {
    TriCombiningTree in, out;
    List<T> pool;
    ReentrantLock[] locks;

    Pool(int poolSize, int threadsNum){
        in = new TriCombiningTree(Math.ceilDiv(threadsNum, 3));
        out = new TriCombiningTree(Math.ceilDiv(threadsNum, 3));

        locks = new ReentrantLock[poolSize];
        pool = new ArrayList<>(poolSize);
        for (int i = 0; i < poolSize; i++) {
            pool.add(null);
            locks[i] = new ReentrantLock();
        }
    }

    void put(T item, int threadId) throws Exception {
        int i = in.getAndIncrement(threadId) % pool.size();
        while (true) {
            while (!locks[i].tryLock())
                ;
            try {
                if (pool.get(i) == null) {
                    pool.set(i, item);
                    System.out.println("THREAT ID: " + threadId + " PUT: " + item);
                    return;
                }
            } finally {
                locks[i].unlock();
            }
        }
    }

    T get (int threadId) throws Exception {
        int i = out.getAndIncrement(threadId) % pool.size();
        while (true) {
            while (!locks[i].tryLock())
                ;
            try {
                if (pool.get(i) != null) {
                    System.out.println("THREAT ID: " + threadId + " GET: " + pool.get(i));
                    return pool.set(i, null);
                }
            } finally {
                locks[i].unlock();
            }
        }
    }
}