# Ćwiczenia 11, grupa cz. 14-16, 18 maja 2023

###### tags: `SYK23` `ć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 | | | | | | | | | |
Wojciech Bogucki | X | X | X | X | | X | X | X | X |
Mateusz Cerulewicz | X | X | X | X | | X | X | | |
Mateusz Garncarczyk | X | X |==X==| X | | X | X | | |
Mateusz Golisz | X | ==X== | X | X | X | X | X | | |
Mateusz Kitzol | X | X | X | X | | X | X | | |
Piotr Mańkowski | | | | | | | | | |
Aleksandra Nicpoń | X | X | X | X | | X | X | | |
Ksawery Plis | X | X | X | X | | ==X== | X | | |
Patryk Rybak | X | X | X | X | | | | | |
Rafał Spyra | X | X | X | X | X | X | X | X | ==X== |
Dominik Szczepaniak | ==X== | X | X | X | X | X | X | X | X |
Taras Tsehenko | | | | | | | | | |
Maksymilian Wiśniewski | X | X | X | X | | X | X | ==X== | X |
Martyna Wybraniec | X | X | X | X | | X | X | | |
Natalia Zychowicz | X | X | X | | | X | ==X== | X | X |
Patryk Maciąg | X | X | X | | | X | X | X | X |
Michał Mękarski | 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: Dominik Szczepaniak
:::



**Planowanie wywłaszczające (ang. preemptive scheduling)** zachodzi wtedy, gdy planowanie występuje w każdym momencie.

**Planowanie niewywłaszczające (ang. non-preemptive scheduling)** zachodzi wtedy, gdy planowanie występuje tylko w momentach 1 i 4.

**Proces ograniczony przez dostęp do procesora (ang. CPU-bound process)** - większość czasu zajmują funkcje wykonywane przez procesor.

**Proces ograniczony przez wejście-wyjście (ang. Input-Output bound process)** – większość czasu zajmują funkcje wejścia/wyjścia.

**Procesy interaktywn**e - oddziałują interaktywnie z użytkownikiem. Z tego powodu mogą być zablokowane, oczekując na naciśnięcie klawisza lub kliknięcie myszki.

**Proces wsadowy (ang. batch process)** – polega na wykonywaniu serii zadań (programów) przez komputer. Zazwyczaj kolejne zadania są ze sobą powiązane: dane wyjściowe jednego programu są przekazywane jako dane wejściowe kolejnemu programowi itd.

**Planowanie wywłaszczające jest trudniejsze w implementacji niż planowanie niewywłaszczające, ale dominuje we współczesnych systemach operacyjnych. Dlaczego?**

Ponieważ użytkownicy oczekują szybkiej reakcji systemu na ich interakcje.

## Zadanie 2
:::success
Autor: Mateusz Golisz
:::

**wykorzystanie CPU** - im dłużej procesor jest wykorzystywany na użyteczne obliczenia tym lepiej.

**przepustowość** - ilość wykonanych procesów w jednostce czasu; im więcej tym lepiej

**czas realizacji jednego procesu** - czas od rozpoczęcia pojedynczego procesu do końca jego wykonania; im krótszy tym lepiej.

**czas oczekiwania** - zminimalizowanie czasu w którym procesy czekają w kolejce ready.

**czas odpowiedzi** - zminimalizowanie czasu odpowiedzi procesu na instrukcje z wejścia w celu utworzenia wrażenia interaktywności.

optymalizowanie czasu odpowiedzi danego procesu jest sprzeczne przykładowo z wykorzystaniem CPU

|Optymalizowane|przykład|problem|
| ------ | --- |---|
| Wykorzystanie CPU | działany bez wywłaszczeń, nie marnujemy czasu na przełączanie między procesami | cierpi np. czas odpowiedzi |
| Przepustowość | mamy jeden bardzo długi proces i bardzo dużo małych, najpierw wykonujemy te krótkie, a długi zostawiamy na koniec | cierpi czas oczekiwania (dla długiego procesu) |
| czas realizacji jednego procesu | | |
| czas oczekiwania | | |
| czas odpowiedzi | proces interaktywny zajmuje procesor cały czas, dzięki czemu jest w stanie zminimalizować czas reakcji na dane z wejścia | żaden inny proces się nie wykonuje, cierpi np. przepustowość |

## Zadanie 3
:::success
Autor: Mateusz Garncarczyk
:::



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

$Turnaround\ time:$
* P1: 2
* P2: 3
* P3: 11
* P4: 15
* P5: 20

$Waiting\ time:$
* P1: 0
* P2: 2
* P3: 3
* P4: 11
* P5: 15

Średni czas oczekiwania: $\frac{31}{5}=6.2$

### SJF (Shortest-Job-First)

$Turnaround\ time:$
* P1: 3
* P2: 1
* P3: 20
* P4: 7
* P5: 12

$Waiting\ time:$
* P1: 1
* P2: 0
* P3: 12
* P4: 3
* P5: 7

Średni czas oczekiwania: $\frac{23}{5}=4.6$

### Priorytetowy bez wywłaszczeń

$Turnaround\ time:$
* P1: 15
* P2: 20
* P3: 8
* P4: 19
* P5: 13

$Waiting\ time:$
* P1: 13
* P2: 19
* P3: 0
* P4: 15
* P5: 8

Średni czas oczekiwania: $\frac{55}{5}=11$

### Karuzelowy (RR - Round Robin) dla Q = 2
$Q - kwantyl\ czasu$

$Turnaround\ time:$
* P1: 2
* P2: 3
* P3: 20
* P4: 13
* P5: 18

$Waiting\ time:$
* P1: 0
* P2: 2
* P3: 12
* P4: 9
* P5: 13

Średni czas oczekiwania: $\frac{36}{5}=7.2$

## Zadanie 4
:::success
Autor: Patryk Rybak
:::


1.
Można zminić sposób w jaki procesy przykazjują sobie żeton na taki, żeby na początku planista wybrał proces o najwyższym priorytecie i po upływie kwantu czasu, żeton przekazywany był do procesu o najwyższym priorytecie. Jeżeli dojdzie do sytuacji, że ten sam priorytet ma więcej niż jeden proces, powinny one wymieniać się żetonem tak jak w algorytmie round-robin do czasu, gdy nie pojawi się proces o większym priorytecie.

2.
CPU burst time to czas, jaki potrzebuje procesor do wykonania określonej porcji pracy dla danego procesu.
a) Q = inf - kazdy proces wykonuje sie od razu do konca
T / (T + S)
b) Q > T - kwant czasu jest dluzszy od sredniego czasu potrzebnego do wykonania procesu
T / (T + S)
c) S < Q < T
Q / (Q + S)
d) Q = S
Q / (Q + S) = Q / 2Q = 0.5
e) Q bliskie 0
Q / (Q + S) -> 0 / S = 0
praktycznie cały czas procesora zostaje poświęcona zmianie kontekstu

## Zadanie 5
:::success
Autor: Rafał Spyra
:::
O takim wariancie algorytmu round-robin możemy powiedzieć, że będzie nieoptymalny dla procesów, które będą stale wymagały kwantu czasu Q takiego, że Q0 > Q > Q/2 i optymalny dla Q=0.5 lub Q=1.

## Zadanie 6
:::success
Autor: Ksawery Plis
:::

Algorytm **SJF (Shortest Job First)** wybiera jako pierwsze procesy z najniższym czasem wykonania. W czasie działania systemu czas wykonania nie jest znany przed jego wykonaniem. Stosuje się więc technikę wykładniczego przybliżania za pomocą wzoru:
$\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha)\tau_n$

gdzie:
$\tau_{n+1}$ - przewidywana wartość czasu wykonywania obecnego procesu
$\tau_{n}$ - przewidywana wartość czasu wykonywania poprzedniego procesu
$t_n$ - faktyczna wartość czasu wykonywania poprzedniego procesu
$\alpha$ - stała, taka że $0 \leq \alpha \leq 1$, najczęściej ustawiana na $\frac{1}{2}$

W wariancie wywłaszczającym **(SRT - Shortest Remaining Time)** w momencie przybycia nowego procesu przerywana jest praca nad obecnym procesem i ustalana jest nowa kolejność. W wariancie bez wywłaszczania nowa kolejność ustalana jest dopiero po zakończeniu wykonywania obecnego procesu.

a) $\alpha = 0$ i $\tau_0 = 100 ms$
$\tau_{n+1} = 0 \cdot t_n + (1 - 0)\tau_n = \tau_n$
Nie zwracamy uwagi na rzeczywiste czasy wykonania i zakładamy, że każda faza trwa $100ms$.

b) $\alpha = 0.99$ i $\tau_0 = 10 ms$
$\tau_{n+1} = 0.99 \cdot t_n + (1 - 0.99)\tau_n = 0.99 \cdot t_n + 0.01 \cdot \tau_n$
Poprzednie predykcje mają pomijalne znaczenie dla obecnej predykcji, która byłaby równa mniej więcej czasowi wykonania poprzedniego procesu
## Zadanie 7
:::success
Autor: Natalia Zychowicz
:::

## Zadanie 8
:::success
Autor: Maksymilian Wiśniewski
:::

### Classical unix scheduling algorithm

https://en.wikipedia.org/wiki/Round-robin_scheduling

- Część kernela.

- Płynnność w działaniu procesów

- Virtual runitime (priorytet)

### Round-robin scheduling

- Najprosttszy algorytm szeregowania procesów w systemie operacyjnym

- każdy proces ma ten sam priorytet

- time-sharing techinque

- Każdy proces otrzymuje kwant czasu

- po uþływie czasu przerywa zadanie jeśli nie zostało one ukończone

- Zadanie jest wznawiane przy kolejnym przydziale czasu procesora dla danego procesu.

- Jeśli proces zakończy się lub zmieni swój stan na oczekujący w trakcie swojego przydzielonego kwantu czasu, planista wybiera pierwszy proces w kolejce gotowych do wykonania

- Na przykład, jeśli przedział czasowy wynosi 100 milisekund, a zadanie 1 trwa łącznie 250 ms, round-robin zawiesi zadanie po 100 ms i da innym zadaniom ich czas na procesorze. Gdy inne zadania otrzymają swój równy udział (100 ms każde), zadanie1 otrzyma kolejną alokację czasu procesora i cykl się powtórzy. Proces ten trwa do momentu, gdy zadanie zakończy pracę i nie będzie potrzebować więcej czasu na CPU.

### CFS - completely fair scheduler

- priority queue

- cirtual runtime( priorytert )

- klasy problemów:
- other
- batch(do not interrupt)
- idle

- rankingi (0-100)

https://en.wikipedia.org/wiki/Completely_Fair_Scheduler

https://man.archlinux.org/man/sched.7.en

## Zadanie 9
:::success
Autor: Wojciech Bogucki
:::

Algorytm:

1. Podziel społeczność użytkowników na zestaw sprawiedliwych grup (fair share groups), gdzie członkowie każdej grupy są poddani ograniczeniom standardowego algorytmu planowania procesów w stosunku do innych procesów w grupie.

2. Przydzielaj czas procesora proporcjonalnie dla każdej grupy niezależnie od liczby procesów w grupach. Na przykład, jeśli na systemie są cztery grupy, z których każda ma przydzieloną 25% czasu CPU, a grupy zawierają odpowiednio 1, 2, 3 i 4 procesy, które nie rezygnują z procesora (np. wykonują nieskończoną pętlę), to każdy proces w czterech grupach otrzyma 10% czasu CPU.

3. Wprowadź dodatkowe pole "fair share group priority" (priorytet grupy ze sprawiedliwym podziałem) w obszarze danych (u area) każdego procesu, wskazujące na współdzielone pole "fair share CPU usage" (użycie CPU przez grupę ze sprawiedliwym podziałem) dla wszystkich procesów w grupie.

4. W obsłudze przerwania zegara zwiększaj pole "fair share group CPU usage" dla działającego procesu tak samo, jak pole "CPU usage" dla działającego procesu, a raz na sekundę zmniejszaj wartości wszystkich pól "fair share group CPU usage".

5. Podczas obliczania priorytetów procesów, uwzględnij wartość "group CPU usage" znormalizowaną według ilości przydzielonego czasu CPU dla danej grupy ze sprawiedliwym podziałem. Im więcej czasu CPU otrzymali procesy w grupie niedawno, tym wyższa wartość numeryczna pola "group CPU usage" i tym niższy priorytet dla wszystkich procesów w grupie ze sprawiedliwym podziałem.

Algorytm ten umożliwia sprawiedliwy podział czasu CPU między grupy użytkowników i przydzielanie im określonych udziałów w procesie planowania.