# Ćwiczenia 13, grupa śr. 12-14, 5 czerwca 2024

###### tags: `SYK24` `ć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 | X | X | X | X | X | | | |
Małgorzata Galińska | X | X | | | | | | | |
Maria Hreniak | | | | | | | | | |
Jakub Jankowski | X | X | X | | | | | | |
Mikołaj Kalitka | | | | | | | | | |
Julia Konefał | X | X | | X | | X | | | |
Julia Kulczycka | | | | | | | | | |
Cecylia Łyjak | | | | | | | | | |
Adam Majchrowski | | | | | | | | | |
Piotr Mańkowski | | | | | | | | | |
Piotr Salamon | | | | | | | | | |
Maciej Szałasz | | | | | | | | | |
:::

**UWAGA: Poniżej można zadeklarować zadania 9 z listy 11 oraz 0 -- 3 z listy 12**

:::danger
| | 11.9 | 12.0| 12.1| 12.2| 12.3|
| ----------------------:| -----| --- | --- | --- | --- |
Mikołaj Balwicki | | X | X | X | |
Małgorzata Galińska | | X | X | X | X |
Maria Hreniak | |==X==| X | X | X |
Jakub Jankowski | | X | X | X | X |
Mikołaj Kalitka | | | | | |
Julia Konefał | | X | ==X== | X | X |
Julia Kulczycka | | | | | |
Cecylia Łyjak | | | | | |
Adam Majchrowski | | X | X | ==X== | X |
Piotr Mańkowski | | | | | |
Piotr Salamon | | | | | |
Maciej Szałasz | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Jakub Jankowski

:::

## Zadanie 2
:::success
Autor: Małgorzata Galińska
:::

## Zadanie 3
:::success
Autor: Mikołaj Balwicki
:::
FCFS
Turnaround: (2+3+11+15+20)/5 = 10.2

SJF
Turnaround: (1+3+7+12+20)/5 = 8.6

Priorytetytowe bez wywłaszczeń
Turnaround: (2+3+7+12+20)/5 = 8.8

Karuzelowe, Q = 2
Turnaround: (2+3+20+13+18)/5 = 11.2

## Zadanie 4
:::success
Autor: Julia Konefał
# Zadanie 4
## 1)
1. Wysoki priorytet na początku: nowo przychodzące procesy są umieszczane w kolejce o najwyższym priorytecie.
2. Obniżanie priorytetu: jeśli proces nie zakończy się w swoim kwancie czasu, jest przenoszony do kolejki o niższym priorytecie.
3. Promowanie procesów: procesy, które czekają zbyt długo, mogą być promowane do kolejki o wyższym priorytecie, aby zapobiec głodzeniu.
Kolejność w jednym priorytecie ustala round robin.

## 2)
$\eta$ - efektywność wykorzystania proceseora

**a)** $Q = \infty$
proces jest wykonywany aż do zakończenia, bez przełączania kontekstu.
$\eta = \frac{T}{T+S}$
Ponieważ nie ma przełączeń kontekstu, efektywność wynosi 100%. Każdy proces jest wykonywany w całości, a przełączania kontekstu nie występują

**b)** $Q > T$
proces zakończy się przed upływem kwantu czasu. W tym przypadku każde przełączenie kontekstu następuje po zakończeniu procesu.
$\eta = \frac{T}{T+S}$
Efekywność wyniesie blisko 100%.

**c)** $S < Q < T$
kwant czasu jest mniejszy niż średnia długość fazy procesora, ale większy niż czas przełączania kontekstu. Proces będzie przełączany w trakcie swojej pracy.
$\eta = \frac{Q}{Q+S}$
Efektywność zależy od relacji Q do S. Jeśli Q jest znacznie większy niż S, efektywność będzie wysoka, ale nigdy nie osiągnie 100%.

**d)** $Q = S$
w każdej jednostce czasu pracy procesora występuje przełączanie kontekstu.
$\eta = \frac{Q}{Q+S} = \frac{Q}{Q+Q} = \frac{1}{2}$

**e)** $Q \approx 0$
przełączania kontekstu występują bardzo często, co znacząco obniża efektywność wykorzystania procesora
$\eta \approx 0$, ponieważ większość czasu zajmuje S
:::

## Zadanie 5
:::success
Autor: Mikołaj Balwicki
:::
Obserwacje:
Algorytm priorytetyzuje procesy, które wykorzystują swoje kwanty czasu w pełni.
Jeśli algorytm zrzeknie się części swojego czasu, jego następna faza będzie krótsza. Jego dwie następne fazy będą łącznej długości Q, zakładając, że nie dojdzie do kolejnego zrzeknięcia.
Przykład
Q0 = 4
P1 – proces o burst time 15, bez wstrzymań
P2 – proces który będzie się wykonywał przez czas 3, potem będzie czekać do t = 10 i wykonywać przez czas 5

Ze stałym kwantem czasu:
Turnaround time: 24
Waiting time (avg): 11

Ze zmiennym kwantem czasu:
Turnaround time: 22.5
Waiting time (avg): 9.5

## Zadanie 6
:::success
Autor: Julia Konefał

Wzór na wykładnicze uśrednianie:
$\tau_{n+1}=\alpha⋅t_{n}+(1−\alpha)⋅\tau_{n}$

gdzie:

$\tau_{n+1}$ to przewidywana długość następnej fazy procesora,
$t_{n}$ to rzeczywista długość ostatniej fazy procesora,
$\tau_{n}$ to poprzednia przewidywana długość fazy procesora,
$\alpha$ to waga wykładnicza (0 ≤ $\alpha$ ≤ 1), która kontroluje wpływ ostatniego pomiaru na przewidywaną wartość.

Algorytm SJF z wykładniczym uśrednianiem

Inicjalizacja:
1. Na początku dla każdego procesu ustalamy przewidywaną długość fazy procesora $\tau_{n}$ (np. jako stałą wartość lub pierwszą zaobserwowaną długość fazy).
2. Wartość $\alpha$ jest stałą wybraną na podstawie specyfiki systemu.

Działanie:
1. Po zakończeniu każdego fazy procesora dla procesu $i$, rzeczywista długość fazy $\tau_{i}$ jest używana do aktualizacji przewidywania $\tau_{i+1}$ za pomocą wzoru wykładniczego uśredniania.
2. Kolejny proces do wykonania wybierany jest na podstawie najkrótszego przewidywanego czasu fazy $\tau$

Implementacja SRT z wykładniczym uśrednianiem

Inicjalizacja:
Podobnie jak w SJF, dla każdego procesu ustalamy początkową przewidywaną długość fazy procesora $\tau_{0}$ i wartość $\alpha$.

Działanie:
1. Po zakończeniu każdego fazy procesora aktualizujemy przewidywaną długość fazy $\tau_{i+1}$ dla danego procesu.
2. Procesor wykonuje proces z najkrótszym przewidywanym czasem pozostałym do końca. Jeśli nowy proces o krótszym przewidywanym czasie zostanie wprowadzony, procesor może wywłaszczyć bieżący proces.
3. W każdej chwili przewidywana długość pozostałego czasu fazy procesora jest aktualizowana dla bieżącego procesu.

#### a) $\alpha = 0 \space i \space \tau_{0} = 100$ milisekund

Nie uwzględniamy poprzednich czasów rzeczywistych - bierzemy za każdym razem początkową predykcję

#### b) $\alpha = 0.99 \space i \space \tau_{0} = 10$ milisekund

W tym przypadku poprzednie predykcje nie mają praktycznie znaczenia i predykcja następnego czasu będzie podobna do poprzedniego czasu wykonania.
:::

## Zadanie 7
:::success
Autor: Mikołaj Balwicki
:::

## Zadanie 8
:::success
Autor: Mikołaj Balwicki
:::

## Zadanie 9
:::success
Autor: Mikołaj Balwicki
:::
W powyższym algorytmie wszystkie procesy traktowane są tak samo, ale możemy chcieć je grupować. Wówczas staramy się dzielić użycie procesora uczciwie pomiędzy grupy, a nie pomiędzy poszczególne procesy.