# Ćwiczenia 11, grupa śr. 17-19, 25. maja 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | | | |
Kamila Brzozowska | X | X | X | X | X | X | X | X | X |
Adam Ciężkowski | X | X | X | X | X | X | X | X | X |
Natalia Czerep | X | X | X | | | | X | X | |
Jan Dalecki | X | X | X | | | X | X | X | X |
Marko Golovko | X | X | X | X | X | X | X | | |
Adam Górkiewicz | X | X | X | X | X | X | X | | |
Piotr Gunia | X | X |==X==| X | X | X | X | X | |
Krzysztof Jadłowski | | | X | | | X | | | |
Magdalena Jarecka | X | X | X | | | | ==X== | X | X |
Mikołaj Jaszcza | X | X | X | X | | X | X | | |
Monika Jędrzejkowska | | | | | | | | | |
Michał Kierul | X | X | X | ==X== | X | X | X | X | X |
Damian Lukas | | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | | |
Piotr Piesiak | | | | | | | | | |
Damian Ratajski | | | | | | | | | |
Aleksandra Rozkrut | X | X | X | | | X | X | | |
Marcin Sarnecki | X | X | X | X | |==X==| X | | |
Maria Szlasa | X | | X | | | X | X | | |
Mateusz Burdyna | X | X | X | X | | X | X | | |
Magdalena Słonińska | | | | | | | | | |
Nikola Wrona | | | | | | | | | |
Marcin Wróbel | X | X | X | X | X | X | X | X |==X==|
:::

**Tutaj można dodeklarować zad. 7. z listy 10.:**
*
*
*

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

## Zadanie 1
:::success
Autor: Maria Szlasa
:::
:::info
Wyjaśnij różnice pomiędzy **planowaniem wywłaszczającym** (ang. preemptive scheduling) a **planowaniem niewywłaszczającym** (ang. non-preemptive scheduling). Posłuż się diagramem stanów procesu. Zdefiniuj pojęcia: **proces ograniczony przez dostęp do procesora** (ang. CPU-bound process), **proces ograniczony przez wejście-wyjście** (ang. Input-Output bound process), **proces interaktywny**, **proces wsadowy** (ang. batch process). Planowanie wywłaszczające jest trudniejsze w implementacji niż niewywłaszczające, a jednak dominuje we współczesnych systemach operacyjnych. Dlaczego?
:::

Decyzje o porzuceniu / zmienieniu procesu następują w następujących przypadkach:

**planowanie wywłaszczające (ang. preemptive scheduling)** zachodzi w momencie, jeśli planowanie zachodzi we wszystkich momentach.
W schemacie wywłaszczeniowym, w ramach kontrolnego przekazania sterowania do jądra systemu operacyjnego może zostać podjęta decyzja o przełączeniu kontekstu pomimo, że wykonywany proces nie zażądał żadnej usługi, oznaczającej rezygnację z procesora. Przechodzi on wówczas do stanu gotowy, a rozpoczyna się wykonywanie innego procesu.

**planowanie niewywłaszczające (ang. non-preemptive scheduling)** zachodzi w momencie, gdzy planowanie zachodzi tylko w momentach 1 i 4.
W schemacie niewywłaszczeniowym procesor traktowany jest jako zasób niewywłaszczalny. Nie można go odebrać procesowi, ale proces może się go zrzec dobrowolnie (służy do tego np. funkcja yield, dostępna w niektórych systemach) lub się zakończyć. Rezygnacja z procesora jest też uboczną konsekwencją wejścia w stan oczekiwania (np. w wyniku zażądania operacji wejścia-wyjścia).

****
[link](http://jedrzej.ulasiewicz.staff.iiar.pwr.wroc.pl/Programowanie-Syst-i-Wspolbielzne/wyklad/SSOSzeregowanie8.pdf)

**proces ograniczony przez dostęp do procesora (ang. CPU-bound process)** - większość czasu zajmują funkcje wykonywane przez procesor. Przykładem mogą być programy
optymalizacyjne. <ciągle liczy>

**proces ograniczony przez wejście-wyjście (ang. Input-Output bound process)** – większość czasu zajmują funkcje wejścia / wyjścia. Przykładem mogą być bazy danych, aplkacje interaktywne. <ciągle czeka na wejście/wyjście, przeciwieństwo poprzedniego>

**procesy interaktywny** - oddziałują interaktywnie z użytkownikiem. Stąd oczekują zablokowane na nacisnięcie klawisza lub kliknięcie myszki. Gdy to nastąpi reakcja programu powinna być szybka (50-150 mS) gdyż inaczej system uznany zostanie jako wolny. Typowe aplikacje: edytory, aplikacje graficzne, interpretery poleceń.

**proces wsadowy (ang. batch process)** – wykonywanie serii zadań (programów) przez komputer. Zazwyczaj kolejne zadania są ze sobą powiązane: dane wyjściowe jednego programu przekazywane są kolejnemu programowi, któremu służą jako dane wejściowe itd.
Procesy które nie muszą bezpośrednio oddziaływać z użytkownikiem. Mogą to być procesy systemowe np. ~~serwer WWW~~ serwer bazy danych. Ich pilność zależy od funkcji którą wykonują. <przeciwieństwo poprzedniego>

****
**Planowanie wywłaszczające jest trudniejsze w implementacji niż niewywłaszczające, a jednak dominuje we współczesnych systemach operacyjnych. Dlaczego?**
dlatego, że nie chcemy czakać aż w notatniku pojawi się to co wpisaliśmy aż do momentu, kiedy będzie wolny profcfesor, tylko chcemy żeby pojawiał się natychmiast

Np uruchamiając pętlę while (true) {} zawiesilibyśmy komputer

## Zadanie 2
:::success
Autor: Adam Górkiewicz
:::
1. CPU utilization (czas poświęcony na właściwe obliczenia, nie zmianę kontekstu)
* Optymalny algorytm: dowolny taki, który nie wykonuje przerwań/wywłaszczeń, np. FCFS
* Wady: wysoki waiting time / response time
2. Throughput (przepustowość)
* Proporcjonalne do CPU utilization
3. Turnaround time (średni czas od wprowadzenia do zakończenia procesu)
* Zakładając brak przerwań/wywłaszczeń, malejący wraz z waiting timem.
* Optymalny algorytm: shortest job first (SJF) / shortest remaining time (SRT)
* Wady: response time?
4. Waiting time
* Optymalny algorytm: shortest job first (SJF) / shortest remaining time (SRT)
* Jeżeli zakładamy możliwość przerywania: round robin (RR) (z lepszym response timem, gorszym turnaroundem)
5. Response time (dla procesów interaktywnych)
* Optymalny algorytm: priority scheduling z wywłaszczaniem
* Alternatywnie: round robin
* Wady: obniżenie wszystkich pozostałych kryteriów

## Zadanie 3
:::success
Autor: Aleksandra Rozkrut
:::
FCFS:
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:
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$

RR dla Q=2
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: Michał Kierul
:::


1. W pierwszej kolejności są wykonywane procesy o niższym priorytecie. Jeśli procesów o jednakowym priorytecie jest więcej niż 1, to są wykonywane one sekwencyjnie, każdy maksymalnie przez z góry określony czas (kwant czasu).



2.

a) $\frac{T}{T+S}$
b) $\frac{T}{T+S}$

W a) i b) wszystkie lub większość faz wykona się do końca, nie zostanie im odebrany procesor.

c) $\frac{Q}{Q+S}$

Cykl pracy ma postać: Q (działanie procesora), S (zmiana kontekstu), Q, S, Q, S, ...

d) Gdy $Q>T$: $\frac{T}{T+S}$
Gdy $Q<T$: $\frac{Q}{Q+S}=\frac{1}{2}$

Uzasadnienie analogiczne jak we wcześniejszych punktach.

e) Większość czasu będzie zmarnowana na zmienę kontekstu - efektywność bliska $0$.

## Zadanie 5
:::success
Autor: Kamila Brzozowska
:::



|Process|Burst time|I/O burst|
|-------|----------|---------|
| $P_1$ | 4 | 1 |
| $P_2$ | 6 | - |
| $P_3$ | 4 | 2 |

Q=2


|Process|Burst time|I/O burst|
|-------|----------|---------|
| $P_1$ | 12 | 3 |


## Zadanie 6
:::success
Autor: Marcin Sarnecki
:::

**SJF - Shortest Job First**
-> pomysł, tak jak sama nazwa wskazuje, polega na wykonywaniu najpierw procesów najkrótszych
-> algorytm niewywłaszczający
-> optymalny algorytm pod względem średniego czasu oczekiwania procesu na jego wykonanie.

Możemy zmienić w nim sposób wyboru procesów, stosując technikę wykładniczego uśredniania. Pomysł polega na oszacowaniu czasu działania procesu na podstawie jego poprzednich czasów


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

W tym skrajnym przypadku liczyć się będzie jedynie poprzednie oszacowanie
$τ_{n+1} = τ_{n} = τ_{0}$

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

W tym przypadku $(1 - \alpha) \approx 0$ zatem $\tau_{n+1} \approx t_n$

**SRT - SHORTEST REMAINING TIME (FIRST)**
-> wywłaszczająca wersja algorytmu SJF
-> jeśli jakiś proces zakończyłby się szybciej niż proces aktualnie przetwarzany, to przerywamy aktualnie przetwarzany proces, aby wykonać proces, który zakończyłby się szybciej

dobrze widać działanie SRT na przykładzie ze slajdów, proces nr 1 został przerwany, bo pojawił się proces nr 2, który zakończyłby się szybciej

## Zadanie 7
:::success
Autor: Magdalena Jarecka
:::
:::info
Zdefiniuj algorytm planowania procesów z użyciem wielopoziomowych kolejek ze sprzężeniem zwrotnym (ang. multilevel feedback queues). W jaki sposób taki algorytm obsługuje różne klasy procesów (interaktywne, czasu rzeczywistego, wsadowe)? Czemu służą reguły promocji i degradacji procesów pomiędzy kolejkami?
:::

### Zwykłe multilevel queues

- System processes - CPU sam w sobie ma rzeczy do wykonania, które są niezbędne do jego działania
- Interactive processes - procesy mogące wymagać interakcji z użytkownikiem
- Batch processes - procesy które mogą spokojnie działać w tle

Zwyczajny algorytm planowania z użyciem kolejek nadaje tym klasom priorytety. W ten sposób najpierw będziemy brali procesy z kolejki **System processes** a na końcu z kolejki **Batch Processes**.
Każda kolejka ma swój własny system planowania. Przykładowo Kolejki 1 i 2 mogą używać Round-Robin a kolejka 3 FCFS.

Drugim sposobem na używanie multilevel queues jest stworzenie ograniczeń czasowych dla kolejek (w przeciwieństwie do brania najpiperw z pierwszej kolejki potem jak się skończy z drugiej itd). Tutaj np. przypisujemy kolejce nr 50% CPU, kolejce nr 2 30% a kolejce nr 3 20%.

### Multilvl feedback queues
Różni się od poprzednika tym że możemy przerzucać procesy pomiędzy kolejkami. Jest bardziej skomplikowany lecz zapobiega "zaleganiu" procesów. Reguły promocji i degradacji służą właśnie przenoszeniu procesów pomiędzy kolejkami:
- Jeśli proces zużywa zbyt dużo czasu procesora, zostanie przeniesiony do kolejki o niższym priorytecie.
- Jeśli proces jest procesem interaktywnym, zostanie przeniesiony do kolejki o wyższym priorytecie.
- Jeśli proces czeka zbyt długo w kolejce o niskim priorytecie, zostanie przeniesiony do kolejki o wyższym priorytecie.

## Zadanie 8
:::success
Autor: Adam Ciężkowski
:::



Jeśli jest kilka procesów o najwyższym priorytecie, wybierz ten, który jest "ready to run" najdłużej.


* Priorytet jest przypisywany, gdy proces przechodzi w stan "sleep"
* Priorytet procesu jest dostosowany, gdy zmienia się z kernel-mode na user-mode (+ priorytet powinien zostać obniżony, ponieważ właśnie co wrócił z kernel-mode).
* Priorytety są obliczane co ok 1s. (nie zawsze)

Pole CPU usage jest zwiększane podczas obsługi procesu (kilka razy podczas jego wykonywania). Co ok. sekundę jest ono zmieniane wg. funkcji decay:
decay(CPU) = CPU/2;
Wtedy też są obliczane ponownie priorytety procesów będących w stanie "preempted but ready-to-run":
priority = ("recent CPU usage"/2) + (base level user priority)




priority = ("recent CPU usage"/constant) + (base priority) + (nice value)

## Zadanie 9
:::success
Autor: Marcin Wróbel
:::

Chcielibyśmy mieć możliwość przydzielania każdemu użytkownikowi pewnej części czasu działania procesora. Rozwiązaniem jest zmodyfikowanie algorytmu z poprzedniego zadania poprzez przypisanie użytkowników do grup. System będzie przydzielał każdej grupie równą ilość czasu procesora niezależnie od liczby procesów w każdej grupie.

Oznaczenia:
CPU = "recent CPU usage"
Group = "recent Group usage"

Zmodyfikowany wzór na priorytet danego procesu wygląda następująco:
$priority=CPU/constant + \textbf{Group/constant} + \text{(base priority)} + \text{(nice value)}$

$CPU = decay(CPU) = CPU / 2$
$Group = decay(CPU) = Group / 2$

#### Przykład:
Proces `A` należy do grupy 1, procesy `B` i `C` należą do grupy 2
$basepriority = 60$
$constant = 2$
$\text{(nice value)} = 0 \text{ (dla każdego procesu)}$