---
# System prepended metadata

title: 'Konsultacje, śr. 14, 29 grudnia 2022, Lista 7'
tags: [PRW22, pwit, ćwiczenia]

---

# Konsultacje, śr. 14, 29 grudnia 2022, Lista 7

###### 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!**


:::success
|                        | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |  
Patryk Mazur             |     |  X  |     |  X  | X   |     |     |  X  |     |
:::




## Zadanie 2
:::danger
Autor:
:::
![](https://i.imgur.com/QVrCqzL.png)

Załóżmy nie wprost, że taka implementacja istnieje

Załóżmy, że dwa wyróżnione wątki zakończyły działanie, a pozostałe wątki wykonają się później.
Sprowadziliśmy właśnie ten problem do problemu implementacji protokołu binarnego konsensusu dla 2 wątków (używającego jedynie rejestrów atomowych). Wiemy natomiast, że taka implementacja nie istnieje.
Sprzeczność

## Zadanie 5
:::danger
Autor:
:::
![](https://i.imgur.com/BR6IfeO.png)
![](https://i.imgur.com/8Dw1EJd.png)

* Wartość zwracana przez **decide()** jest jedną z wartości zaproponowanych przez wątki

Obiekt zwraca wartość z tablicy proposed[], która jest zapełniana wartościami zaproponowanymi przez wątki

* Metoda ta zwraca tę samą wartość obydwu wątkom

Aby tak się nie stało, oba wątki musiałyby wejść do tej samej gałęzi ifa

1. if

Wątek $i$ pierwszy wchodzi do ifa, zatem 
(1) $position[i] > position[j] + speed[j]$
$\rightarrow$
$position[j] = position[j] + speed[j]$

Aby wątek $j$ wszedł teraz do ifa, musiałoby zajść
$position[j] > position[i] + speed[i]$

Ale z (1)
$position[j] < position[i] + speed[i]$
Sprzeczność

2. else if

Wątek $i$ pierwszy wchodzi do else ifa, zatem 
$position[i] < position[j]$

$i$ zwraca wartość i przestaje już zwiększać swoją pozycję, natomiast $j$ będzie cały czas zwiększało swoją pozycję, przez co nigdy nie nastąpi $position[i] >= position[j]$

* Dlaczego ten wynik nie jest sprzeczny z faktem, że poziom konsensusu dla rejestrów atomowych wynosi 1?

Podana implementacja nie jest *wait-free*