---
# System prepended metadata

title: 'Ćwiczenia 14, grupa śr. 10-12, 26 stycznia 2024'
tags: [pwit, ćwiczenia, PRW23]

---

# Ćwiczenia 14, grupa śr. 10-12, 26 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  | 
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki         |  X  |     |     |     |     |     |     |     |     |  
Konrad Kowalczyk         |     |     |     |     |     |     |     |     |     |
Jakub Krzyżowski         |  X  |     |  X  |     |  X  |     |     |     |     |
Łukasz Magnuszewski      |     |     |     |     |     |     |     |     |     |
Marcin Majchrzyk         |     |     |     |     |     |     |     |     |     |  
Jan Marek                |     |     |     |     |     |     |     |     |     |  
Marcin Mierzejewski      |     |     |     |     |     |     |     |     |     |  
Juan Jose Nieto Ruiz     |     |     |     |     |     |     |     |     |     | 
Konrad Oleksy            |     |     |     |     |     |     |     |     |     |  
Javier Rábago Montero    |     |     |     |     |     |     |     |     |     |  
Michał Mękarski          |     |     |     |     |     |     |     |     |     |  
:::



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

:::danger
|                        | 13.5    | 13.6    | 13.7    |
| ----------------------:| -----   | -----   | -----   |
|                        |         |         |         |
|                        |         |         |         |
|                        |         |         |         |
|                        |         |         |         |
:::


    


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



## Zadanie 1
:::success
Autor: 	Mikołaj Balwicki
:::
Ogólny diagram:
![image](https://hackmd.io/_uploads/rJAZYgW5T.png)
Step Property:
![image](https://hackmd.io/_uploads/rJrrtx-ca.png)
Sieć szerokości 4:
![image](https://hackmd.io/_uploads/Sk56Fgbqp.png)




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

## Zadanie 3
:::success
Autor: 	Jakub Krzyżowski
:::
**Zadanie 3.** Podaj wydajną, nieczekającą (ang. wait-free) implementację klasy Balancer.

```java=
public class Balancer {
    AtomicInteger value = new AtomicInteger(0);
    public int traverse() {
        int myValue = value.getAndIncrement();
        return myValue % 2;
    }
}
```

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


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


## Zadanie 5
:::success
Autor: 	Jakub Krzyżowski
:::

**Zadanie 5 (bonus).** Do czego służy blokada
odczytujący–zapisujący (ang. readers–writers lock). Porównaj
klasę SimpleReadWriteLock z FifoReadWriteLock i wskaż, jaką
pożądaną cechę ma ta druga.

Blokada odczytujący-zapisujący służy do synchronizacji pomiędzy wątkami odczytającymi i wątkami piszącymi. Idea jest taka, że wątki odczytujące, niezmieniające stanu nie muszą blokować sobie nawzajem dostępu, dopiero wątki które chcą zmodyfikować dane muszą je zablokować innym wątkom. 

```java=
public class SimpleReadWriteLock implements ReadWriteLock {
    int readers = 0;
    boolean writer = false;
    Lock lock = new ReentrantLock();
    Condition condition = lock.newCondition();
    Lock readLock = new ReadLock(), writeLock = new WriteLock();
    
    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();
            }
        }
    }
    
    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();
            }
        }
    }
}
```
Gdy wątek piszący próbuje zająć write lock najpierw zajmuje wewnętrzny zamek i jeśli jacyś czytający, lub drugi piszący zajmują obecnie zamek to czeka na condition. Czytający zwalniający read lock zajmuje zamek wewnętrzny i jeśli wszyscy czytający zwolnili zamek, to powiadamia wątki czekające na condition.
Podobnie gdy wątek czytający próbuje zająć zamek, to jeśli zajmuje go obecnie jakiś piszący czeka na condition i zwalniający zamek piszący go powiadomi.
Problemem jest tu możliwość zagłodzenia piszących - jeśli czytających napływa ciągły potok, to mogą przez długi czas nie zwolnić read locka, który musi zająć piszący.

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

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

Tutaj nie występuje zagłodzenie piszących, ponieważ jak piszący wywoła lock, to więcej czytających już nie zajmie zamka, więc jest pewność, że po pewnym czasie zamek nie będzie już zajmowany przez czytających i będzie można bezpiecznie pisać.

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

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

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

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

