# Ćwiczenia 13, grupa śr. 14-16, 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 |
| ----------------------:| ----| ---| --- | ---| ---|--- |--- |--- |--- |
Krzysztof Chorzempa | X | X | X | X | X | X | X | X | X |
Maciej Ciepiela | X | X | X | | | | | | |
Szymon Fica | X | | | | | | | | |
Agnieszka Grala | X | X | ==X== | X | | X | | | |
Karolina Jędraszek | X | | | | | | | | |
Katarzyna Jodłowska | | | | | | | | | |
Dominik Kiełbowicz | X | X | X | X | X | X | ==X== | X | X |
Michał Kolasa | X | X | X | X | ==X== | X | X | X | X |
Rafał Krysa | X | X | X | X | | X | | | |
Miłosz Krzysiek | | | | | | | | | |
Łukasz Kulczycki | | | | | | | | | |
Leon Lepkowski | X | X | X | | | | | | |
Hanna Makowska | X | X | X | | | X | | | |
Jan Marek | X | X | X | X | | X | X | | |
Cezary Miłek | X | X | X | X | | | | | |
Anna Pierzchała | | | | | | | | | |
Alan Pietrasz | ==X== | X | X | X | X | X | X | | |
Kacper Ponikowski | X | X | X | X | | X | | | |
Dominik Walecko | | | | | | X | | | |
Michał Włodarczak | | | | | | | | | |
Błażej Molik | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Alan Pietrasz
:::

- planowanie wywłaszczające
występuje w 1, 2, 3, 4
- planowanie niewywłaszczające
występuje w 1, 4

- proces ograniczony przez dostęp do procesora
czas jego wykonania zależy w największym stopniu od szybkości procesora
- proces ograniczony przez wejście-wyjście
czas jego wykonania zależy w największym stopniu od czasu oczekiwania na wejście-wyjście
- proces interaktywny
proces w dużym stopniu zależny od interakcji z użytkownikiem
- proces wsadowy
użytkownik tylko na początku zapewnia ewentualne dane, a potem proces nie wymaga już żadnych interakcji z użytkownikiem

- Planowanie wywłaszczające jest trudniejsze w implementacji niż niewywłaszczające, a jednak dominuje we współczesnych systemach operacyjnych. Dlaczego?
Przykład z wykładu: program, w którym występuje nieskończona pętla przy planowaniu niewywłaszczającym może sprawić, że inne procesy nie będą w ogóle mogły się wykonywać. Natomiast jeśli planowanie jest wywłaszczające, to program ten będzie po pewnym czasie wywłaszczony i procesor będzie mógł działać produktywniej.

## Zadanie 2
:::success
Autor: Leon Lepkowski
:::

| Optymalizacja | Algorytm | Wada |
| --------------- | ----------- | ---------------------------------------------- |
| CPU utilization | FCFS | Waiting time, Response time |
| Throughput | SRT | Response time |
| Turnaround time | SRT | Response time |
| Waiting time | SJF | Response time |
| Response time | Round robin | Waiting time, Turnaround time, CPU unilization |

## Zadanie 3
:::success
Autor: Agnieszka Grala
:::

**First- Come, First-Served (FCFS)**

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

Średni czas oczekiwania = (0+2+3+11+15)/5 = 6,2

**Shortest-Job-First (SJF)**

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

Średni czas oczekiwania = (1+0+12+3+7)/5 = 4,6

**Priorytetowy bez wywłaszczeń**

| Proces | Czas oczekiwania | Czas cyklu przetwarzania |
| ------ | ---------------- | ------------------------ |
| P1 | 13 | 15 |
| P2 | 19 | 20 |
| P3 | 0 | 8 |
| P4 | 15 | 19 |
| P5 | 8 | 13 |

Średni czas oczekiwania = (13+19+0+15+8)/5 = 11

**Karuzelowy (Round-Robin) dla Q=2**

| Proces | Czas oczekiwania | Czas cyklu przetwarzania |
| ------ | ---------------- | ------------------------ |
| P1 | 0 | 2 |
| P2 | 2 | 3 |
| P3 | 3+4+4+1=12 | 20 |
| P4 | 5+4=9 | 13 |
| P5 | 7+4+2=13 | 18 |

Średni czas oczekiwania = (0+2+12+9+13)/5 = 7,2

## Zadanie 4
:::success
Autor: Kacper Ponikowski
:::

1. Idziemy zgodnie z priorytetem procesów. Na procesach o tym samym priorytecie używamy round robin.

2.
a) $Q = \infty$
$\frac{T}{T + S}$
b) $Q > T$
$\frac{T}{T + S}$
c) $S < Q < T$
$\frac{Q}{Q + S}$
d) $Q = S$
1. $Q > T$
$\frac{T}{T + S}$
2. $Q < T$
$\frac{Q}{Q + S} = \frac{1}{2}$
e) Q bliskie 0
0 ,bo cały czas będziemy tylko zmieniać procesy
## Zadanie 5
:::success
Autor: Michał Kolasa
:::
Dla uproszcznia załóżmy, że każda faza procesu bedzie trwała tylo co poprzednia.

1) Dla $P >= Q_{0}$ algorytm działa jak zwykłe Round Robin.
2) Dla $P = Q_{0}/2$ czas wykonakona procesu też się nie zmieni.
3) Dla $P < Q_{0}/2$, $Q_{1} = Q_{0} - P$ czyli $P < Q_{1}$ zatem algorytm będzie się wykonywał
jak zwykłe Round Robin
4) Dla $Q_{0} > P > Q_{0}/2$, $Q_{1} = Q_{0} - P$ czyli $P > Q_{1}$ będziemy zatem do czasu wykonania procesu dodawać czas zmiany/zmian kontekstu, przy czym im P będzie bliżej do $Q_{0}$ tym $Q_{1}$ będzie mniejsze, a zatem ilość zmian kontekstu też będzie większa (dla $P = 0.99Q_{0}$ będzie 100 zmian, dla $P = 0.999Q_{0}$ 1000).
Dodatkowo przy każdej zmianie kontekstu, żeby proces wrócił do procesora Robin Robin musi przejść przez pozostałe procesy, zatem faktyczny czas wykonia procesy może wzrosnąć wielokrotnie.

Podsumowują nowy algorytm ma wady, które mogą zwiększać czas wykonia procesu, przy czym nie widać jak miałby poprawić jakieś miary efektywności (może responsywność ale nieznacznie)

## Zadanie 6
:::success
Autor: Hanna Makowska
:::

## Zadanie 7
:::success
Autor: Dominik Kiełbowicz
:::

**Multilevel feedback queues**

Użycie zwyczajnych wielopoziomowych kolejek zakłada, że zamiast pojedynczej kolejki `ready` mamy ich wiele. Każda z nich może mieć inny algorytm planowania procesów, potrzebujemy metody determinacji do której z kolejek powinien zostać dodany proces.

Używając kolejek wielopoziomowych ze sprzężeniem zwrotnym, główna różnica polega na tym, że proces może być przemieszczany pomiędzy różnymi poziomami. Aby zdefiniować MLFQ (multilevel feedback queue) potrzebujemy:

- liczby kolejek
- algorytmu planowania dla każdej z kolejek
- metody determinacji kiedy proces powinien zostać przemieszczony do wyższego/niższego poziomu
- metody determinacji do której kolejki powinien zostać dodany nowy proces.

Obsługa różnych klas procesów odbywa się poprzez nadanie poszczególnym klasom priorytetów.


Reguły promocji i degradacji to nic innego jak metoda determinacji kiedy proces powinien zostać przemieszczony do innej kolejki. Zapobiega to sytuacjom, że bardzo długi proces może blokować kolejkę o wysokim priorytecie i sytuacjom, kiedy proces bardzo długo nie jest obsługiwany przez to, że znajduje się w kolejce o niskim priorytecie.


Przykład z wykładu:
Mamy MLFQ o 3 poziomach, opisane jak na slajdzie. Kiedy nowy proces jest dodawany do kolejki $Q_0$, czeka na swoją kolej do użycia procesora. Kiedy uzyskuje dostęp, wykonuje swoje należne 8ms obliczeń. Jeśli w tym czasie proces zostanie ukończony to super, przechodzimy do kolejnego procesu z kolejki. W przeciwnym wypadku, proces jest przeniesiony na koniec kolejki $Q_1$ i kontynuujemy wykonywanie procesów z $Q_0$ aż będzie ona pusta. Wtedy przechodzimy do $Q_1$ i dzieje się to samo - proces jest wykonywany, jeśli nie zostaje ukończony to przerzucamy do niższej kolejki. Po przerobieniu procesów z $Q_1$ przechodzimy do ostatniej kolejki, w której już wszystkie procesy są wykonywane po kolei.

## Zadanie 8
:::success
Autor: Krzysztof Chorzempa
:::
Mamy dwa tryby: *kernel mode* i *user mode*.
W *kernel mode* mamy priorytety zależące od powodu *spania*, czyli np. proces, który śpi z powodu odczytu dysku (*disk I/O*) po powrocie ze snu będzie miał większy priorytet niż proces, który spał z powodu czekania na wejście od użytkownika.
| *kernel mode* | *user mode* |
| -------------------------------------------- | ----------------------------------------------------------------- |
| priorytet zależy od powodu spania | priorytet zależy od *nice value*, wcześniejszego użycia procesora |
| niewywłaszczające | wywłaszczające |
| nie dzieli czasu (bo jest niewywłaszczające) | stosuje RR dla procesów o takim samym priorytecie |
| priorytet jest stały | priorytet się zmienia |

Każdy proces ma priorytet od 0 do 127.
Priorytety 0-49 to procesy w *kernel mode*, reszta to *user mode* (**najwyższy priorytet to najmniejsza wartość [0]**).
Każdy proces ma następujące pola:
- p_pri - priorytet procesu (od 0 do 127)
- p_usrpri - priorytet procesu w *user mode*
- p_cpu - użycie procesora w przeszłości
- p_nice - "modyfikator" podany przez użytkownika.

Decyzje są podejmowane patrząc na *p_pri*.
Proces wchodzi w *kernel mode* -> *p_pri* jest zapisywane do *p_usrpri*.
Proces wychodzi z *kernel mode* -> *p_pri* przyjmuje wartość z *p_usrpri*.
*p_cpu* jest inkrementowane przy każdej jednostce czasu, którą procesor poświęca na wykonywanie danego procesu (przy każdym cyklu).
Co 100 cykli (~raz na sekundę) *p_cpu* jest przemnażane przez *correction factor* (*CF*) (maleje, aby uniknąć *głodzenia* - *aging*).
W System V Release 3: $CF = \frac{1}{2}$.
Alternatywne podejście: *CF* zależy od średniej liczby procesów w stanie *ready*.

$P\_USER = 50$
$p\_pri = P\_USER + p\_cpu/4 + 2*p\_nice$

W każdym cyklu jeżeli "pojawia" się jakiś proces z większym priorytetem to przełączamy się na niego.
Co 10 cykli działamy na zasadzie Round-Robin, czyli przełączamy się na następny proces o tym samym priorytecie.
Co 100 cykli przeliczamy priorytety na nowo, bierzemy proces z najwyższym priorytetem.

Proces przechodzi do *kernel mode* bezpośrednio przed wykonaniem operacji zarezerwowanej dla tego trybu, wraca do *user mode* kiedy ją wykonał.
[Slajdy z Budapesztu](https://www.mit.bme.hu/eng/system/files/oktatas/targyak/8776/unix_3_process_scheduling.pdf)

## Zadanie 9
:::success
Autor: Michał Kolasa
:::


Zasada działania Fair Share Scheduler:
"User community" jest podzieleny na grupy, z których każda ma przydzielony określony udział czasu procesora.
System przydziela czas procesora proporcjonalnie do każdej grupy, niezależnie od liczby procesów w grupach.
Przykład:
Jeśli mamy cztery grupy, każda z przydziałem 25% czasu procesora i grupy zawierają odpowiednio 1, 2, 3 i 4 procesy intensywnie korzystające z CPU, to bez Fair Share Scheduler każdy proces otrzymałby 10% czasu CPU (bo jest ich 10). Jednak z Fair Share Scheduler proces w grupie 1 otrzyma dwa razy więcej czasu CPU niż każdy proces w grupie 2, trzy razy więcej niż każdy proces w grupie 3, i cztery razy więcej niż każdy proces w grupie 4.

Implementacja:
Do wzoru obliczania priorytetu procesu dodaje się nowy składnik - "priorytet grupy fair share". Każdy proces ma nowe pole wskazujące na pole użycia CPU przez grupę fair share, wspólne dla wszystkich procesów w grupie. Obsługa przerwań zegara zwiększa pole użycia CPU grupy dla aktualnie działającego procesu, podobnie jak pole użycia CPU samego procesu, a wartości te są co sekundę redukowane.

Przykład działania:
Załóżmy, że mamy trzy procesy: A, B i C. Proces A należy do jednej grupy, a procesy B i C do innej. Jeśli najpierw uruchomiony zostanie proces A, jego pole użycia CPU i pole użycia grupy będą zwiększane przez następne sekundy. Po przeliczeniu priorytetów procesów po 1 sekundzie, procesy B i C będą miały najwyższy priorytet i załóżmy, że jądro uruchomi proces B. W następnej sekundzie pole użycia CPU procesu B oraz pole użycia grupy dla procesów B i C wzrośnie. W ten sposób, po przeliczeniu priorytetów po 2 sekundach, proces C będzie miał priorytet 75, a jądro uruchomi proces A z priorytetem 74. Wzorzec będzie się powtarzał: procesy będą uruchamiane w kolejności A, B, A, C, A, B itd.