# Ćwiczenia 13, grupa cz. 10-12, 6 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 |
| ----------------------:| ---| ---| ---| ---| ---| ---| ---| ---| ---|
Borys Adamiak | X | X | X | X | | ==X== | | | X |
Michał Chawar | X | X | X | X | | X | | | |
Julia Cygan | X | X | X | X | | X | | | |
Maciej Dengusiak | | | | | | | | | |
Patryk Flama | X | X | X | X | | X | | | |
Szymon Fluder | ==X== | X | X | X | X | X | X | X | X |
Aleksandra Jędrzejak | X | X | X | X | | X | | | |
Mikołaj Karapka | | | | | | | | | |
Viktoriia Kashpruk | X |X | X | ==X== | X | X | X |X |X |
Wiktor Małek | X | X | X | X | X | X | X | X | ==X== |
Błażej Molik | X | X | ==X== | X | X | X | X | | |
Andrzej Morawski | | | | | | | | | |
Konrad Oleksy | | | | | | | | | |
Lucjan Pucelak | X | X | X | X | | X | | | |
Aleksandra Sęk | | | | | | | | | |
Radosław Śliwiński | | | | | | | | | |
Piotr Traczyński | X | X | X | X | X | X | X | | |
Katarzyna Trzos | X | ==X== | X |X | | X | | | |
Piotr Warząchowski | | | | | | | | | |
Olga Zaborska | X | X | X | | | X | | | |
:::

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

## Zadanie 1
:::success
Autor: Olga Zaborska
:::



## Zadanie 2
:::success
Autor: Katarzyna Trzos
:::

## MIARY EFEKTYWNOSNI ALGORYTMOW PLANOWANIA PROCESOW

### CPU Utilization (*Wykorzystanie procesora*)
Procent czasu, w którym procesor jest zajęty przetwarzaniem zadań.
Wysokie wykorzystanie procesora oznacza efektywne wykorzystanie zasobów systemowych.
Chcemy, żeby wykorzystanie procesora bylo maksymalne.

### Throughput (*Przepustowość*)
Liczba prosesów, które kończą swoje wykonywanie w jednostce czasu.
Wysoka przepustowość oznacza, że system jest w stanie przetworzyć dużą liczbę zadań w krótkim czasie.
Chcemy, żeby przepustowość byla maksymalna.

### Turnaround time (*Czas cyklu przetwarzania*)
Czas od momentu zgłoszenia procesu do momentu jego zakończenia.
Dla zadań wymagających dużo czasu przetwarzania. Krótszy czas zakończenia zadań zwiększa wydajność systemu.
Chcemy, żeby ten czas był minimalny.

### Waiting time (*Czas oczekiwania*)
Czas, jaki proces spędza w kolejce procesów gotowych oczekując na przydzielenie procesora.
Krótki czas oczekiwania oznacza, że procesy są szybko obsługiwane, co przekłada się na lepszą responsywność systemu.
Chcemy, żeby ten czas był minimalny.

### Response time (*Czas odpowiedzi*)
Czas od momentu przekazania inputu do momentu gdy proces zacznie na niego reagować.
Dla systemów gdzie użytkownicy mają otrzymać szybką odpowiedź.
Chcemy, żeby ten czas był minimalny.

## Algorytmy optymalizujące:

| miara | Algorytm| Wada |
| -------- | -------- | -------- |
| CPU Utilization|Priority Scheduling | Algorytm może prowadzić do przeciążenia systemu i zwiększenia czasu oczekiwania na inne zadania.|
| Throughput | Shortest Remaining Time First (SRTF) | Optymalizacja przepustowości może prowadzić do dłuższego czasu oczekiwania dla indywidualnych zadań. |
| Turnaround time | First-Come, First-Served (FCFS) | Algorytm może nie optymalizować innych miar, np. czasu oczekiwania dla krótkich procesów |
|Waiting time | Shortest Job Next (SJN)| Optymalizacja tej miary nie zawsze optymalizuje inne miary, takie jak czas odpowiedzi czy wykorzystanie procesora.|
|Response time|Round Robin (RR)|Optymalizacja czasu odpowiedzi może prowadzić do zwiększenia całkowitego czasu zakończenia zadań (turnaround time).|

## Zadanie 3
:::success
Autor: Błażej Molik
:::


**a) FCFS - First come, first served**
Procesy są realizowane w kolejności ich przyjścia. Pierwszy proces, który przychodzi, jest realizowany jako pierwszy.


| Proces | Czas oczekiwania | Czas cyklu przetwarzania |
| ------ | ---------------- | ------------------------ |
| P1 | 0 | 2 |
| P2 | 2 | 3 |
| P3 | 3 | 11 |
| P4 | 11 | 15 |
| P5 | 15 | 20 |

* Średni czas oczekiwania: $\frac{0+2+3+11+15}{5} = 6,2$

**b) SJF - Shortest job first**
Proces o najkrótszym czasie wykonania (burst time) jest realizowany jako pierwszy.


| Proces | Czas oczekiwania | Czas cyklu przetwarzania |
| ------ | ---------------- | ------------------------ |
| P1 | 1 | 3 |
| P2 | 0 | 1 |
| P3 | 12 | 20 |
| P4 | 3 | 7 |
| P5 | 7 | 12

* Średni czas oczekiwania: $\frac{1+0+12+3+7}{3} = 4,6$

**c) Priorytetowe bez wywłaszczeń** (mniejsza liczba oznacza większy priorytet)
Procesy są realizowane zgodnie z ich priorytetami. Jeśli dwa procesy mają ten sam priorytet, możemy skorzystać z Round-Robin.


| Proces | Czas oczekiwania | Czas cyklu przetwarzania |
| ------ | ---------------- | ------------------------ |
| P1 | 1 | 3 |
| P2 | 0 | 1 |
| P3 | 12 | 20 |
| P4 | 3 | 7 |
| P5 | 7 | 12

* Średni czas oczekiwania: $\frac{1+0+12+3+7}{5} = 4,6$

**d) Karuzelowe - Round-Robin, dla Q=2**
Każdy proces jest realizowany przez określony kwant czasu Q, po czym przechodzi do końca kolejki, jeśli nie został zakończony.


| Proces | Czas oczekiwania | Czas cyklu przetwarzania |
| ------ | ---------------- | ------------------------ |
| P1 | 0 | 2 |
| P2 | 2 | 3 |
| P3 | 12 | 20 |
| P4 | 9 | 13 |
| P5 | 13 | 18

* Średni czas oczekiwania: $\frac{0+2+12+9+13}{5} = 7,2$

## Zadanie 4
:::success
Autor: Patryk Flama
:::

1. Zakładam, że czym wyższy jest priorytet procesu, tym dłużej będzie wykonywanł.
Mamy kolejkę, w ktorej mamy ustawione bloki kontrolny procesów.
W jaki sposób sprawic, że proces, się wykonywał nie przez kwant czasu, a przez n kwantów czasu?
Wystarczy w kolejkę cykliczną dodać ten sam blok kontrolny n razy.
2.
a) $Q = \infty$ = > $\frac{T}{T + S}$
Efektywność wysoka, bo każdy proces się wykona do końca, i będzie minimalnie zmian kontekstu.
b) $Q > T$
Analogicznie do a)
c) $S < Q < T$ - będzie dużo przełączeń kontekstu $\frac{Q}{Q + S}$
d) $Q = S$
1. $Q > T$ - analogicznie jak w b)
2. $Q < T$ - $\frac{Q}{Q + S}$

e) Q = 0, efektywność 0

## Zadanie 5
:::success
Autor: Piotr Traczyński
:::


Możemy zauważyć, że taka zmiana nie powinnna pozytywnie wpłynąć na efektywność wykorzystania procesora, bo jeśli proces nie korzysta z procesora w swoim kwancie to i tak jest zmieniany kontekst.

Ponadto łatwo zauważyć, że w wielu przypadkach spowoduje zwiększenie liczby zmiany kontekstów, co negatywnie wpłynie na efektywność wykorzystania procesora.

Przykład:
Niech $P1$, $P2$ oznaczają kolejne fazy procesora tego samego procesu.
Jeśli $P1 < Q_0$ i $P2 = Q_0$, to proces, który potrzebowałby tylko jednej zmiany kontekstu teraz będzie potrzebował przynajmniej trzech.

Co prawda może to zwiększyć responsywność systemu, ale wydaje się być to absolutnie losowym narzędziem do tego celu.

## Zadanie 6
:::success
Autor: Borys Adamiak
:::
W algorytmie SJF priorytet maja procesy z najmniejszym czasem wykonania. Nie znamy jednak tych czasow wiec stosujemy przyblizenie.
$t_n = n_th\;$ CPU burst
$\tau_{n+1}$ - predicted value of the next CPU burst
$0 \leq \alpha \leq 1$
$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

Wariant wywłaszczający SRT w momencie przybycia nowego procesu przerywa pracę nad obecnym i ustala nową kolejność.

a) $\alpha = 0, \tau_0 = 100ms$
$\tau_{n+1} = \tau_n$
każda faza trwa 100ms z przyblizenia
b) $\alpha = 0.99 \tau_0 = 10ms$
$\tau_{n+1} = 0.99t_n + 0.01\tau_n$
poprzednie predykcje maja małe znaczenie dla aktualnej ale za to bliskie poprzedniemu czasowi wykonania

## Zadanie 7
:::success
Autor: Viktoriia Kashpruk

Zwykła wielopoziomowa kolejka:

**Wielopoziomowe kolejki ze sprzężeniem zwrotnym** to takie kolejki, w których procesy mogą wędrować między kolejkami.
Algortym zależy od:
* liczby kolejek
* algorytmu planowania procesów dla poszczególnych kolejek
* Metoda używana do określenia, do której kolejki proces wejdzie, gdy będzie potrzebował obsługi
* metody, która determinuje kiedy zdegradować dany proces

Aby zapobiec starvation, to korzystamy z promocji procesów:
-jeśli proces czeka zbyt długo w kolejce o niższym priorytecie, może być przeniesiony do kolejki o wyższym priorytecie
Degradację procesu, czyli przesuwanie do niższej kolejki używamy, wtedy kiedy ten proces zbyt dlugo się wykonuje, naprzykład przekracza przydzielony mu kwant czasu
Przykład:

:::

## Zadanie 8
:::success
Autor: Szymon Fluder


### Wybieranie procesu

*idle state* - kiedy coś jest uruchomione,ale nie przetwarza aktywnie żadnych zadań/danych.

Jesli jest kilka procesów o najwyższym priorytecie kernel wybiera ten proces, który najdłużej był "ready".

### Hierarchia procesów

Priorytety dzielą się na priorytety jądra systemu oraz użytkownika, te należące do jądra dzielą się dalej na przerywalne i nieprzerywalne. Każdy priorytet może mieć wiele procesów(gdy mają one te same priorytety).


Procesy z trybu użytkownika mogą mieć nadany priorytet z grupy jądra poprzez system call/interrupt, procesy z trybu jądra mogą zostać "zwrócone" w tryb użytkownika.

### Uruchamianie procesów

#### zmiana z trybu kernel na user


Proces wracający do trybu użytkownika z trybu jądra dostaje adekwatną karę, ponieważ właśnie korzystał z cennych zasobów.


#### aktualizacja priorytetów w trybie użytkownika

Każdy proces ma swój licznik, który na pączątku ma bazowy priorytet, który zapewnia, że proces nie przejdzie w tryb jądra "sam z siebie". Licznik jest zwiększany co pewien moment odmierzany przez zegar. Priorytety są co pewien ustalony czas akutalizowane(w tym przypadku co sekunde), aby zapobiec monopolizacji wykorzystania CPU przez pojedyncze procesy(Proces zmienia swoje położenie jak chodzi o priorytet - może zostać przeniesiony do innej kolejki); Zgodnie z poniższymi wzorami:



#### Przykład wykonywania 3 procesów ze zmianą priorytetu

wartość bazowa procesu = 60
Zegar 60 razy na sekundę zwiększa CPU count.


### Nice value


Wartość *nice* jest przechowywana w tabeli procesu

Można wywołać funkcje *nice(value)*, która zmieni wartość nice danego procesu. Tylko superuser może zwiększać w ten sposób priorytet procesu.

:::

## Zadanie 9
:::success
Autor: Wiktor Małek
Idea:
Chcemy podzielić procesy usera na grupy, oraz tak przydzielać czas procesora, aby czas na każdą grupę był równy(nie na każdy proces), czyli jeśli jedna grupa jest bardziej liczna od drugiej (ma więcej procesów), to mimo tego dostanie ona tyle samo czasu procesora.

Algorytm:
Implementacja tej idei odbywa się w ten sposób, że wyznaczając priorytet danego procesu w sumie mamy jeden dodatkowy składnik, który jest współdzielony przez wszystkie procesy w grupie.

W momencie kiedy wykonujemy jakiś proces, zwiększamy licznik tego procesu oraz całej grupy, do której należy.

Przez to w momencie, gdy chcemy wybrać proces do wykonania wybierzemy proces z grupy, która nie była ostatnio użyta(ma wysoki priorytet, przez to że już jakiś czas temu jej licznik został zwiększany przy wykonywaniu), oraz proces o wysokim priorytecie w tej grupie(ponieważ licznik tego procesu, był zwiększany stosunkowo dawno).
:::