---
# System prepended metadata

title: 'Ćwiczenia 14, grupa cz. 16-18, 25 stycznia 2024'
tags: [pwit, ćwiczenia, PRW23]

---

# Ć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	
:::
![obraz](https://hackmd.io/_uploads/SkzJ5DJ5a.png)

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.

![obraz](https://hackmd.io/_uploads/r1HbqTkcT.png)
![obraz](https://hackmd.io/_uploads/SyEX9pkcp.png)
![obraz](https://hackmd.io/_uploads/S1_ic6k9a.png)



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

## Zadanie 3
:::success
Autor: 	Mateusz Reis	
:::
![image](https://hackmd.io/_uploads/rJ_83ll9p.png)

```java=
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.
 

```java=
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	
:::
``` java=
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: 	
:::


