# Ćwiczenia 2, grupa śr. 14-16, 16 października 2024

###### tags: `PRW24` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Michał Chawar | X | X | X | X | X | | X | X | |
Fabian Grodek | | | | | | | | | |
Maria Hreniak | X | X | X | X | X | | X | X | X |
Aleksandra Jędrzejak | | | | | | | | | |
Jan Kamyk | X | X | X | X | X | | | | |
Viktoriia Kashpruk | X | X | ==X== | X |X | |X |X |X |
Miłosz Krzysiek | | | | | | | | | |
Michał Łukasik | X | X | X | | X | | | | |
Kacper Pajor | ==X== | X | X | X | | | X | X | |
Ksawery Plis | X | X | X | X | X | | | | |
Kacper Ponikowski | X | X | X | | | | | | |
Yaryna Rachkevych | X | X | X | ==X== | X | | X | X | X |
Cyprian Skrzypczak | X | X | X | X | X | X | X | X | |
Antoni Strasz | ==X== | X | X | X | | | X | X | |
Marta Strzelec | X | X | X | X | X | | X | ==X== | |
Dominik Szczepaniak | X | X | X | X | X | | X | X | ==X== |
Piotr Thamm | X | ==X== | X | X | X | | | X | |
Michał Włodarczak | X | X | X | X | ==X== | | X | X | X |
:::

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

## Zadanie 1
:::::success
Autor: Kacper Pajor

## Wzajemne wykluczenie
### Założenie
:::: success
:::info
Przez kontrapozycję zakładam że dwa wątki mogą jednocześnie wejść do sekcji krytycznej.
:::

### Z kodu
(K1)A.write(turn = A) -> A.read(busy = false) -> A.write(busy = true) --
-> (K2)A.read(turn = A) -> A.CS

K1 -> K2

(K3)B.write(turn = B) -> B.read(busy = false) -> B.write(busy = true) --
-> (K4)B.read(turn = B) -> B.CS

K3 -> K4

### Z założenia

(Z1) A.read(turn = A) -> B.write(turn = B)

(Z2) B.read(turn = B) -> A.write(turn = A)

### Sprzeczność
:::danger
(K1)A.write(turn = A) -> (K2)A.read(turn = A) (Z1)-> (K3)B.write(turn = B) -> (K4)B.read(turn = B) (Z2)-> (K1)A.write(turn = A)
Pętla, czyli sprzeczność.
:::
::::

## Niezagłodzenie
::::success
### Twierdzenie
:::info
Warunek niezagłodzenia nie jest spełniony.
:::
### Przykład
:::danger
(1)A.write(busy = true) -> (2)B.write(turn = B) -> (3)A.read(turn != A) -> (4)B.read(busy = true)

### Wniosek

Przy takiej kolejności operacji wątek A blokuje wątek B (4) spowoduje że zostanie on w wewnętrznej pętli, A po wykonaniu (2) wątek A zostanie zablokowany z wyjścia z zewnętrznej pętli (3), po czym wróci on do wewnętrznej pętli.

Więc żaden z wątku nie ustawi busy na false. -> Wątek A nigdy nie wejdzie do strefy krytycznej -> zagłodzenie
:::
::::
## Zakleszczenie

### Twierdzenie
::::danger
:::info
Warunek niezakleszczenie nie jest spełniony.
:::
### Przykład

(1)A.write(busy = true) -> (2)B.write(turn = B) -> (3)A.read(turn != A) -> (4)B.read(busy = true)

### Wniosek

Przy takiej kolejności operacji wątek A blokuje wątek B (4) spowoduje że zostanie on w wewnętrznej pętli, A po wykonaniu (2) wątek A zostanie zablokowany z wyjścia z zewnętrznej pętli (3), po czym wróci on do wewnętrznej pętli.

Więc żaden z wątku nie ustawi busy na false. -> Zakleszczenie

Dla ilości wątku większej niż 2 wystarczy że wątki inne niż A będą przed sprawdzeniem warunku wewnętrznej pętli gdy (1).
::::

:::::

## Zadanie 2
:::success
Autor: Piotr Thamm


## Algorytm Petersona ze zmienioną metodą unlock():

public void lock() {
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i){};
}
public void unlock() {
    int i = ThreadID.get(); /*Returns 0 or 1 */
    flag[i] = false;
    int j = 1 - i;
    while(flag[j] == true) {};
}

<div style="display: grid; grid-template-columns: 1fr 1fr; width: 100%; align-items: start; justify-items: center; gap: 3rem" >
<div>
<h3 style="font-size: 2.5rem;">
Niezakleszczenie
</h3>
<h4 style="font-size: 1.75rem;"> 1. Jeden wątek w unlock()</h4>
<p>Załóżmy, że <span style="font-weight: 600; color: #2b60dc">Wątek 0</span> wywołał metodę <span style="font-weight: 600;">unlock()</span>, a <span style="font-weight: 600; color: #ff6048">Wątek 1</span> wywołał metodę <span style="font-weight: 600;">lock()</span>. Wtedy:</p>
<ol>
<li>flag[<span style="font-weight: 600; color: #2b60dc">0</span>] = false</li>
<li>flag[<span style="font-weight: 600; color: #ff6048">1</span>] = true</li>
</ol>
<p>
<span style="font-weight: 600;">Brak zakleszczenia</span>, ponieważ victim = 1 oraz flag[0] = false, zatem <span style="font-weight: 600; color: #ff6048">Wątek 1</span> wejdzie do sekcji krytycznej.
</p>
<h4 style="font-size: 1.75rem;"> Formalnie:</h4>
<p>
Write0(flag[0]=false) => Write1(flag[1]=true) => Write1(victim=1) => read_1(flag[0]==false) => read_1(victim==1) => CS1
</p>
<h4 style="font-size: 1.75rem;">2. Oba wątki w unlock()</h4>
<p>
Jeżeli oba wątki są w unlock() to ich flagi są ustawione na <span style="font-weight:600; color: #ff6048;">false</span>, zatem nie dojdzie do zapętlenia w 10 linijce kodu.
</p>
</div>
<div>
<h3 style="font-size: 2.5rem;">Niezagłodzenie</h3>
<h4 style="font-size: 1.75rem;"> Dojdzie do zagłodzenia:</h4>
<ol>
<li><span style="font-weight: 600; color: #2b60dc">Wątek 0</span> jest w <span style="font-weight: 600;">unlock()</span>, zatem:</br>flag[<span style="font-weight: 600; color: #2b60dc">0</span>] = false </li>
<li><span style="font-weight: 600; color: #ff6048">Wątek 1</span> wchodzi do <span style="font-weight: 600;">lock()</span>, ustawia flag[<span style="font-weight: 600; color: #ff6048">1</span>] = true</li>
<li><span style="font-weight: 600; color: #ff6048">Wątek 1</span> wychodzi z sekcji krytycznej i wchodzi do <span style="font-weight: 600;">unlock()</span>, ustawia flag[<span style="font-weight: 600; color: #ff6048">1</span>] = false, natomiast nie wchodzi do pętli while. Dzieje się tak ponieważ flag[1 - 1] = false, a nie true.</li>
</ol>
<h4 style="font-size: 1.75rem;"> Formalnie:</h4>
<p>
Write0(flag[0] = false) => Write1(flag[1] = true) => Write1(victim = 1) => Read1(flag[0] == false) => Read1(victim == 1) => CS1 => (unlock)=> Write1(flag[1] = false) => Read1(flag[0] == false) => (lock)=> Write1(flag[1] = true) => Write1(victim = 1) => Read1(flag[0] == false) => Read1(victim == 1) => CS1
</p>
<p>Zatem <span style="font-weight: 600; color: #ff6048">Wątek 1</span> może ponownie wejść do <span style="font-weight: 600;">lock()</span>, a potem do sekcji krytycznej. W taki sposób <span style="font-weight: 600; color: #2b60dc">Wątek 0</span> jest głodzony.</p>
</div>
</div>

:::

## Zadanie 3
:::success
Autor: Viktoriia Kashpruk

**Ograniczone czekanie**
Wątek, który oczekuje na wejście do sekcji krytycznej może być wyprzedzony conajwyżej r razy przez jakiś inny wątek. Jeśli to że wątek A wykonał sekcję wejściową wcześniej, niż wątek B oznacza, że wątek A może przepuścić przez sobą conajwyżej r razy wątek B w dostępie do sekcji krytycznej


Pokażemy, że w alg. Petersona r=0
Zał BSO, że $D_A^{k} \rightarrow D_B^{j}$
To znaczy, że $write_A[flag[A]=true] \rightarrow write_B[flag[B]=true]$

1) Z tego wynika, że A wejdzie do sekcji krytycznej od razu, bo B jeszcze nie ma podniesionej flagi.
2) while (flag[B]==true && victim=B) -> A wchodzi

W takim razie r=0

:::

## Zadanie 4
:::success
Autor: Yaryna Rachkevych
Algorytm piekarni:
~~~
class Bakery implements Lock {
…
public void lock() {
flag[i] = true;
label[i] = max(label[0], …,label[n-1])+1;
while (∃k flag[k] && (label[i],i) > (label[k], k));
}
}
~~~

Etykiety label nie są unikatowe, ponieważ funckja max nie jest atomowa. To znaczy, że jednocześnie kilka wątków może wykonywać max na tej samej liście, co spowoduje że znajdą takie same maksimum.

**a) Warunek wzajemnego wykluczania**

Załóżmy, że wątki A i B są jednocześnie w sekcji krytycznej.

Niech $labeling_A$ - nadanie nowej etykiety
Załóżmy, że (label[A], A) << (label[B], B).

***Jak wątek B okazał się w CS?***

Musiało zajść:
{1}flag[A] == false lub {2}(label[B], B) << (label[A], A)

{2} jest sprzeczne z założeniem, więc musiało zajść {1}

***Jak wątek A okazał się w CS?***

Jeśli B zobaczył flag[A] == false, to znaczy, że A ustawił flagę po tym jak B wszedł w CS. To znaczy, że przypisane etykiety dla A też odbyło się nieco później.

W końcu mamy:

$labeling_B → read_B(flag[A]) → write_A(flag[A]) → labeling_A$

$labeling_B → labeling_A$

A ponieważ etykiety są niemalejące, to mamy sprzeczność z założeniem (label[A], A) << (label[B], B).

**c) Warunek niezagłodzenia**

Załóżmy nie wprost, że wątek A czeka na wejście do sekcji krytycznej, ale nie jest w stanie tego zrobić.

Czyli odbyło się: $write_A(flag[A] = true) → labeling_a$

1. Jeśli inne wątki nie mają podniesionych flag, to A po prostu wchodzi do CS.

2. Jeśli inne wątki również mają podniesione flagi, wejdzie ten z najmniejszą etykietą, a po zakończeniu zwolni sekcję. Z tego, że para (label[A], A) jest unikalna wynika, że wątek A wejdzie kiedyś w CS.

**b) Warunek niezakleszczenia**

Z tego że algorytm gwarantuje brak glodzenia, wynika też że warunek niezakleszczenia jest spełniony.

Ew.: Jakiś oczekujący wątek A ma unikalną najmniejszą parę (label[A], A), i ten wątek nigdy nie czeka na inny wątek.
:::

## Zadanie 5
:::success
Autor: Michał Włodarczak
Na start po dwa wątki do każdego liścia. Wątek wchodzi do sekcji krytycznej dopiero z korzenia. Każdy (od korzenia do liścia) zamek zajęty przez dany wątek jest odblokowany przez unlock(). Po zajęciu zamka przez wątek na danym węźle, ten wątek "wygrywa" i idzie poziom wyżej, żeby zająć rodzica itd.
Algorytm Petersona z wykładu

public void lock() {
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i) {};
}

public void unlock() {
    flag[i] = false;
}

### a) Wzajemne wykluczenie

Na pojedynczym węźle działa algorytm Petersona, który spełnia te wszystkie 3 rzeczy (z wykładu). To znaczy, że z każdego węzła na poziom wyżej jest w stanie przejść tylko jeden węzeł, bo na każdym węźle spełnione jest wzajemne wykluczenie.

Zatem do ostatniego węzła (korzenia) wejdą co najwyżej 2 wątki i tylko jeden zostanie wypuszczony do sekcji krytycznej z tego samego powodu co wyżej. Czyli ten algorytm spełnia wzajemne wykluczenie.

### b) Niezagłodzenie

Żaden wątek nie zostanie zagłodzony. Na każdym węźle działa algorytm Petersona, który spełnia warunek niezagłodzenia. Powiedzmy, że wątek, który właśnie skończył sekcję krytyczną wraca z powrotem do liścia, z którego wyszedł poprzednio. Nie ma szansy na zagłodzenie wątku, z którym "wygrał" poprzednio, bo w algorytmie Petersona victim zostanie ustawiony na ten wątek, który właśnie tu wszedł, czyli poprzedni wątek nie utknie w whilu i wyjdzie z tego węzła. To może się stać w dowolnym węźle.

Zatem ten algorytm spełnia warunek niezagłodzenia.

### c) Niezakleszczenie

Podobnie jak wcześnej, przez algorytm Petersona działającym na każdym wierzchołku, na żadnym z nich dwa wątki się nie zakleszczą. Aby się zakleszczyły to victim musi być jednocześnie ustawiony na każdy wątek a to niemożliwe. Zatem algorytm spełnia też warunek niezakleszczenia.

:::

## Zadanie 6
:::success
Autor: Cyprian Skrzypczak
1. Czy istnieje taka liczba r, być może zależna od n, że
algorytm tree-lock spełnia własność r-ograniczonego
czekania (ang. r-Bounded Waiting)? Jako sekcję wejściową
(ang. doorway section) algorytmu przyjmij fragment kodu
przed pętlą while zamka w odpowiednim liściu.

2. Pokaż, być może modyfikując nieco oryginalny algorytm, że założenie o numerach wątków w poprzednim zadaniu może być łatwo usunięte.
---
Fragment z zad 5

   /\
 /\  /\
/\/\/\/\
_____678

Załóżmy że mamy taki stan,
wstamiwamy do kolejki w tym samym czasie wątki 1 i 5

   /\
 /\  /\
/\/\/\/\
1___5678

Korzeń będzie na przemian brał wartości z lewego i prawego poddrzewa

   /\
 /\  /\
/\/\/\/\
1___567_
8 wchodzi do CS
   /\
 /\  /\
/\/\/\/\
____567_
1 wchodzi do CS
1 ustawia się w kolejce
   /\
 /\  /\
/\/\/\/\
1___5_7_
6 wchodzi do CS
   /\
 /\  /\
/\/\/\/\
____5_7_
1 wchodzi do CS drugi raz przed 5 więc nie jest r=0 Bounded

Subtelność:

   /\
 /\  /\
A......D

---
1.
Tak, jest maksymalna liczba r, która powoduje że tree lock spełnia własność r-ograniczonego czekania, i zależy od wysokości drzewa, czyli r=O(logn)
Polega to z faktu że, tak jak pokazane w schemacie z zadania 5, wierzchołek na zmiane bierze wątki z lewego i prawego poddrzewa, nie patrząc na ilość liści w poddrzewach.

Dla h=3 wątek 5 został wyprzedzony przez wątek 1 3 razy, więc zakładam że r=logn.
Indukcyjnie można pokazać że jest to prawda.

---
2.
Jeżeli uda się zmienić, że każdy wierzchołek nie przepuszcza na zmianę lewego i prawego poddrzewa, tylko przepuszcza wątki z jednego poddrzewa kilka razy pod rząd, w zależności od swojej wysokości w drzewie, i dopiero potem zmienia na drugie poddrzewo, to możnaby osiągnąć żądaną własność.

Idea jest taka, że przy liściach wierzchołek przepuści 1 wątek z lewej, potem 1 z prawej, na zmiane
Jeden poziom wyżej przepuści 2 z lewej a dopiero później 2 z prawej.
Jeszcze jeden poziom wyżej przepuści 4 z lewej, potem 4 z prawej

Problem w implementacji polega na tym, że trzeba rozważyć przypadek że po jednej ze stron nie ustawią się w kolejce 2^k wierzchołków i będzie się czekać aż druga strona się wypełni.

Modyfikacja polegałaby na tym, że każdy wierzchołek sumuje, ile jest wątków czekających pod nim w chwili gdy wykonuje `lock` i zmianę `victim`. Gdy wykonuje unlock, przekazuje zarówno wątek jak i informacje o liczbie wątków czekających do drzewa do góry. Gdy wykonywane jest lock, to sprawdzane jest czy wątek jest z lewej lub prawej strony i ma dawany priorytet, tzn przechodzi bez czekania, a drugie poddrzewo czeka dopóki albo nie skończy się liczba wątków w poddrzewie z priorytetem. Po czekaniu zmieniany jest victim na przeciwnego.

---
pseudokod

int i = ThreadID.get(); /*returns 0 or 1*/
int j = 1-i;
shared int subtree[], victim;

public void lock() {
    if (subtree[i] == 0)//rozmiar poddrzewa
    {
        subtree[i] = subtree[0]+subtree[1] of the child node;
        victim = i;
    }
    while (subtree[j] > 0 && victim == i) {};
    //Lemma: two threads dont enter from the same subtree into CS at the same time (recursive property)
}

public void unlock() {
    flag[i] = false;
    subtree[i]--;
    
}

---

:::

## Zadanie 7
:::success
Autor: Michał Chawar
:::


class FastPath implements Lock {
  private Lock lock;
  private int x, y = -1;
  
  public void lock() {
    int i = ThreadID.get();
    
    x = i;
    while (y != -1) {}
    
    y = i;
    if (x != i)
      lock.lock();
  }

  public void unlock() {
    y = -1;
    lock.unlock();
  }
}

#### Wzajemne wykluczanie

Zauważmy, że jeśli zamek jest zajęty ($y \neq -1$) i dwa wątki po kolei wejdą do sekcji wejściowej, to zmienna $x$ przyjmie identyfikator drugiego z nich. W momencie, w którym zamek zostanie zwolniony, oba w jednej chwili spróbują nadać wartość współdzielonej zmiennej $y$, a następnie drugi wątek przejdzie do wykonywania sekcji krytycznej (bo $x$ jest równy jego identyfikatorowi), a pierwszy zablokuje zamek wewnętrzny, który jednak nie będzie wiedział, że inny wątek już wykonuje sekcję krytyczną i pozwoli temu wątkowi też do niej wejść. Stąd zamek nie spełnia warunku wzajemnego wykluczania.

#### Niezagłodzenie
Jeśli kilka wątków oczekuje na zwolnienie zamka w linijce **9**, to po jego zwolnieniu wszystkie przejdą dalej i, skoro jest ich kilka, spełnią warunek w linijce **12**, blokując zamek wewnętrzny. Skoro zamek wewnętrzny spełnia warunek niezagłodzenia, to nie zostaną one zagłodzone. Jeśli tylko jeden wątek oczekuje na wykonanie sekcji krytycznej w zamku wewnętrznym, to również nie zostanie zagłodzony (o ile wątek, który jest w sekcji krytycznej, skończy ją wykonywać). Stąd zamek zewnętrzny spełnia warunek niezagłodzenia.

#### Niezakleszczenie
Widzimy, że zakleszczenie może wystąpić tylko w linijce **9**, gdzie wykonanie sekcji krytycznych jest blokowane. Skoro jednak na początku $y=-1$, $y \neq -1$ tylko, gdy jakiś wątek jest w swojej sekcji krytycznej, oraz gdy wątek wychodzi z sekcji krytycznej następuje odblokowanie $y$ w linijce **17**, to zamek spełnia warunek niezakleszczenia.

## Zadanie 8
:::success
Autor: Marta Strzelec
:::


**A) co najwyzej jeden watek otrzyma jako wartosc zwracana STOP**

Załóżmy niewprost, że istnieją dwa takie wątki, które zwróciły wartość STOP. Oznacza to, że dwa razy (last == i) miało wartość true.

* pierw jeden wątek zwrócił wartość STOP, a następnie drugi

Nie jest to możliwe, ponieważ poprzednik ustawił goRight = true, więc drugi wątek zwróci wartość RIGHT.

Write_1(last = 1) -> read_1(go_right == false) -> **Write_1(goRight = true )** -> Read_1(last == 1)

Write_2(last = 2) -> **read_2(go_right == true)**

* wątki równocześnie przeszły przez if(goRight).

Write_1(last = 1) -> Write_2(last = 2)

Last ma jedną określoną wartość, w takim przypadku tylko jeden z wątków spełni (last == i), a drugi wpadnie w else: return DOWN.

**b) co najwyżej n-1 wątków otrzyma wartość DOWN.**

Załóżmy niewprost, że n wątków otrzymało wartość DOWN.

W takim przypadku dla kazdego wątku porównanie last == i musiało być fałszywe i zaden z wątkow nie zwrocil RIGHT.

Czyli każdy z wątków doszedł tutaj:

każdy z wątków musiał przejść przez instrukcję przypisania last = i. Ostatni z wątków, którego thread id został przypisany do last, przejdzie if (last == i ) z rezultatem True, zwracając return STOP .

**c) co najwyżej n-1 wątków otrzyma wartość RIGHT**

Załóżmy niewprost, że n wątków otrzymało wartość RIGHT.

Nie jest to możliwe, ponieważ początkowo:

private boolean goRight = false;

Aby zmienna goRight była true, należy ominąć if:

if (goRight)
    return RIGHT;
goRight = true;

Read(goRight == false) -> Write(goRight = true)

## Zadanie 9
:::success
Autor: Dominik Szczepaniak
:::

# Założenia podstawowe:

1. **(1)** Na początku w wierzchołku 0 znajduje się $n$ wątków.
2. **(2)** W każdym wierzchołku, w którym znajduje się $k$ wątków, co najwyżej $k - 1$ wątków przejdzie na prawo (do wierzchołka o numerze większym), a co najwyżej $k - 1$ wątków przejdzie w dół (do wierzchołka o numerze większym). Wynika to z właściwości metody `visit()` obiektu `Bouncer`.
3. **(3)** Na każdym poziomie grafu łączna liczba wątków nie przekracza $n$, ponieważ każdy wątek przechodzi tylko do jednego wierzchołka na niższym poziomie.
4. **(4)** Gdy w wierzchołku znajduje się tylko jeden wątek, otrzymuje on wynik `STOP`.

## 1. Dowód, że każdy wątek otrzyma wynik `STOP`

Przeprowadzimy rozumowanie indukcyjne, aby pokazać, że liczba wątków w wierzchołkach maleje z każdym poziomem grafu.

### Podstawa indukcji:

- **Poziom 0:** W wierzchołku 0 znajduje się $n$ wątków.

### Krok indukcyjny:

- **Hipoteza indukcyjna:** Załóżmy, że na poziomie $k$ każdy wierzchołek zawiera maksymalnie $n - k$ wątków.
- **Pokażemy, że na poziomie $k + 1$ każdy wierzchołek zawiera maksymalnie $n - (k + 1)$ wątków.**

### Dowód kroku indukcyjnego:

1. **Rozważmy dowolny wierzchołek $c$ na poziomie $k + 1$.** Wierzchołek ten może być osiągnięty z dwóch wierzchołków na poziomie $k$, nazwijmy je $a$ (lewy) i $b$ (prawy).

2. **Niech $K_a$ i $K_b$ będą liczbami wątków w wierzchołkach $a$ i $b$.** Z hipotezy indukcyjnej mamy:

$$
K_a \leq n - k \quad \text{i} \quad K_b \leq n - k
$$

3. **Liczba wątków przechodzących do wierzchołka $c$:**

- Z każdego wierzchołka $a$ i $b$ może przejść co najwyżej $K_a - 1$ i $K_b - 1$ wątków (zgodnie z założeniem **(2)**).
- Jeśli $K_a$ lub $K_b$ wynosi 0 lub 1, to liczba wątków przechodzących z tego wierzchołka wynosi 0.
- Zatem łączna liczba wątków w wierzchołku $c$ wynosi:

$$
K_c = \max(K_a - 1, 0) + \max(K_b - 1, 0)
$$

4. **Maksymalna wartość $K_c$:**

- Ponieważ $K_a \leq n - k$ i $K_b \leq n - k$, mamy:

$$
K_c \leq (n - k - 1) + (n - k - 1) = 2(n - k - 1)
$$

- Jednakże, z założenia **(3)**, łączna liczba wątków na poziomie $k + 1$ nie może przekroczyć $n$. Dlatego maksymalna liczba wątków w dowolnym wierzchołku na poziomie $k + 1$ to:

$$
K_c \leq n - (k + 1)
$$

5. **Wniosek kroku indukcyjnego:**

- Udowodniliśmy, że na poziomie $k + 1$ każdy wierzchołek zawiera maksymalnie $n - (k + 1)$ wątków.

### Zakończenie dowodu indukcyjnego:

- Na podstawie indukcji mamy, że na każdym poziomie $k$ każdy wierzchołek zawiera maksymalnie $n - k$ wątków.
- **Dla poziomu $k = n - 1$:**

$$
n - k = n - (n - 1) = 1
$$

- Zatem na poziomie $n - 1$ w każdym wierzchołku znajduje się co najwyżej 1 wątek.
- **Zgodnie z założeniem (4),** gdy w wierzchołku jest tylko jeden wątek, otrzymuje on wynik `STOP`.
- **Wniosek:** Każdy wątek musi w końcu otrzymać wynik `STOP`, ponieważ liczba wątków maleje z każdym poziomem, a liczba poziomów jest ograniczona (maksymalnie $n - 1$ poziomów).

## 2. Ograniczenie liczby wierzchołków grafu

Obliczymy łączną liczbę wierzchołków potrzebnych w grafie.

### Liczba wierzchołków na każdym poziomie:

- **Poziom 0:** 1 wierzchołek (wierzchołek 0).
- **Poziom 1:** 2 wierzchołki (wierzchołki 1 i 2).
- **Poziom 2:** 3 wierzchołki.
- ...
- **Poziom $n - 1$:** $n$ wierzchołków.

### Suma wierzchołków:

- Łączna liczba wierzchołków $V$ to suma liczby wierzchołków na każdym poziomie:

$$
V = 1 + 2 + 3 + \dots + n = \sum_{k = 1}^{n} k = \frac{n(n + 1)}{2}
$$

### Wniosek:

- Liczbę wierzchołków grafu można ograniczyć do $\frac{n(n + 1)}{2}$.