# Ćwiczenia 14, grupa cz. 16-18, 25 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 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | | | | | | | | | |
Paweł Borek | | | | | | | | | |
Arti Brzozowski | | | | | | | | | |
Mateusz Golisz | X | | X | X | X | x? | | | |
Kacper Jóźwiak | | | | | | | | | |
Julia Konefał | | | | | | | | | |
Adam Korta | | | | | | | | | |
Jakub Mikołajczyk | | | | | X | | | | |
Bartosz Morasz | | | | | | | | | |
Andrzej Morawski | | | | | | | | | |
Aleksandra Nicpoń | | | | | | | | | |
Mateusz Reis | | | x | | | | | | |
Tomasz Stachurski | | | | | | | | | |
Marcel Szelwiga | X | | X | X | X | | | | |
Volha Tsekalo | | | | | | | | | |
Martyna Wybraniec | | | | | | | | | |
Denys Zinoviev | | | | | | | | | |
Dominik Olejarz | | | | | | | | | |
:::

Tutaj można zadeklarować zaległe zadania 5, 6 i 7 z listy 13:

:::danger
| | 13.5 | 13.6 | 13.7 |
| ----------------------:| ----- | ----- | ----- |
| Jakub Mikołajczyk | X | X | X |
| | | | |
| | | | |
| | | | |
:::

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

## Zadanie 1
:::success
Autor: Mateusz Golisz
:::

Sieci zliczające składają się z balancerów - obiektów, które odpowiednio rozkładają niekoniecznie zbalansowane wejścia na zbalansowane wyjścia, tj. takie, gdzie każde z nich otrzyma tyle samo (+-1) rzeczy z wejść. Działają tak, że co drugie wejście jest wysyłane na wyjście pierwsze, a reszta na wyście drugie.

Balancery są połączone tak, że wyjście jednego wchodzi do wejścia drugiego w odpowiedni sposób.

Własność kroku (step property) - liczba elementów na wyjściach różni się maksymalnie o 1, a nadmiarowe elementy trafiają na wyścia o mniejszych indeksach - dzięki temu można w łatwy sposób przerobić ten schemat na licznik dodając liczniki na każdym wyjściu.


## Zadanie 2
:::danger
Autor:
:::

## Zadanie 3
:::success
Autor: Mateusz Reis
:::

public class Balancer {
    private final AtomicInteger counter = new AtomicInteger(0);

    public int traverse() {
        return counter.getAndIncrement() % 2;
    }
}

## Zadanie 4
:::success
Autor: Marcel Szelwiga
:::

Drzewa równoważników

Balancer:

         0, 2, 4
      /
 - [B]
      \  1, 3, 5
 

Pomysł na licznik z użyciem drzewa równoważników:

           [CNT]
          /
       [B]
      /   \[CNT]
 - [B]     [CNT]
      \   / 
       [B]
          \[CNT]
 

           0, 4, 8 ...
          /
       [B]
      /   \2, 6, 10 ...
 - [B]     1, 5, 9 ...
      \   / 
       [B]
          \3, 7, 11 ...
 

Pytanie: w jaki sposób uzyskać permutację wyjściową?

Który licznik będzie zwracał wartości dla danej ikrementacji?

Dwa podejścia do rozwiązania:

* Możemy brutalnie wykonać symulację bez wątków, która pokaże nam gdzie trafi dana wartość modulo liczba liści. [Zdecydowanie nie chemy tego rozwiązania]

* Rozwiązanie szybsze:
zauważmy, że na górną połowę trafią liście parzyste, a na dolną połowę trafią liście nie parzyste.
Zatem przejście krawędzią w górę dopisuje 0 na początek zapisu binarnego, a przejście w dół zapisuje 1 na początek zapisu binarnego.

           0 = 00b
          /
       [B]
      /   \2 = 10b
 - [B]     1 = 01b
      \   / 
       [B]
          \3 = 11b
 

## Zadanie 5
:::success
Autor: Marcel Szelwiga
:::
Problem czytelników i pisarzy.
Wiele wątków może wejść do blokady podczas czytania, ponieważ nie modyfikują struktury, tylko jeden pisarz może na raz pisać, ponieważ mogłyby nastąpić konflikty.

public interface ReadWriteLock {
	Lock readLock();
	Lock writeLock();
}

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;
	}
	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();
			}
		}
	}
	protected 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();
			}
		}
	}
}


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

## Zadanie 6
:::success
Autor: Mateusz Golisz
:::

public class FifoReadWriteLock implements ReadWriteLock {
    //...
    
    private class WriteLock implements Lock {
        public void lock() {

            if(!hasReadLock){
                getReadLock();
                bool exit_later = true; //na wyjsciu uwolni tez zamek read
            }

            lock.lock();
            try {
                readReleases++; //virtual release, not actual one
                if (readAcquires == readReleases)
                    condition.signalAll();
                while (writer)
                    condition.await();
                writer = true;
                while (readAcquires != readReleases) 
                    condition.await();
            } finally {
                lock.unlock();
            }
        }

        public void unlock() {
            lock.lock();
            try {
                writer = false;
                readAcquires++; //virtual reacquire
                condition.signalAll();
            } finally {
                if(exit_later) // 
                    read_lock.unlock();
                lock.unlock();
            }
        }
    }
}

## Zadanie 7
:::danger
Autor:
:::

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

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