# Ćwiczenia 11, grupa śr. 10-12, 17 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk | | | | | | | | | |
Mikołaj Dworszczak | | | | | | | | | |
Kacper Jóźwiak | X | X | X | X | X | X | X | | |
Dominik Kiełbowicz | | | | | | | | | |
Michał Kolasa | | | | | | | | | |
Konrad Kowalczyk | X | X | X | X | X | X | X | | |
Oskar Kropielnicki | X | X | X | X | | X | X | | |
Anna Krysta | X | X | X | X | X | X | X | X | X |
Jakub Krzyżowski | X | X | X | X | | X | X | | |
Oskar Kubkowski | X | X | ==X==| X | | X | X | | |
Mateusz Mazur | X | X | X | X | X | X | X | | |
Barbara Moczulska | X | X | X | X | | X | X | | |
Kacper Sojda | X | X | X | X | X | X | X | | |
Marta Strzelec | X | X | X | X | X | X | X | | |
Mikołaj Swoboda | X | X | X | X | | X | X | | |
Filip Szczepański | ==X== | X | X | X | X | X | X | | |
Julian Włodarek | X | X | X | X | ==X== | X | X | | |
Beata Łakoma | x | x | x | x | x | x | x | | |
Michał Łukasik | 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: Filip Szczepański
:::

**W planowaniu niewywłaszczającym** proces zmienia stan pomiędzy waiting, running, terminated. Oznacza to, że gdy procesowi zostanie przydzielony procesor, będzie on wykorzystywany przez proces dopuki ten nie zmieni stanu na waiting albo na terminated.

**W planowaniu wywłaszczającym** proces może też zmieniać stan z waiting na ready oraz z running na ready. Podczas tego scheduler podejmuje decyzje.

**proces ograniczony przez dostęp do procesora** - czas wykonania procesu (uzyskania stanu terminated) zależy głownie od czasu procesora, jaki ten proces potrzebuje.

**proces ograniczony przez wejście-wyjście** - czas wykonania procesu zależy głownie od interakcji z urządzeniami I/O.

**proces interaktywny** - proces często wchodzący w interakcję z użytkownikiem. Opóźnienie w działaniu programu powinno być niskie.

**program wsadowy** - mało interakcji z użytkownikiem. Opóźnienie zależy od wykonywanej funckji.

**Po co?**
Planowanie wywłaszczające stosuje się dla stworzenia iluzji działania wielu programów jednocześnie.

## Zadanie 2
:::success
Autor: Barbara Moczulska
:::


- **wykorzystanie CPU** - im dłużej procesor jest wykorzystywany tym lepiej - Chcemy aby procesor był zajęty przez cały czas. Chcemy aby procesor był wykorzystywany również w cyklach IO. Wszystkie przerwy w użyciu trzeba zminimalizować

- **przepustowość systemu** - Chcemy aby jak najwięcej procesów się wykonało w jednostce czasu

- **czas realizacji jednego procesu** - czas od rozpoczęcia pojedyńczego procesu do końca jego wykonania chcemy aby był jak najkrótszy.

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

- **czas odpowiedzi** - zminimalizowanie czasu odpowiedzi procesu, chcemy mieć wrażenie interaktywności, że proces natychmiast reaguje na polecania.

## Zadanie 3
:::success
Autor: Oskar Kubkowski
:::

### First Come First Served (FCFS)

Czas cyklu przetworzenia (Turnaround time)
$P_{1} = 2$
$P_{2} = 3$
$P_{3} = 11$
$P_{4} = 15$
$P_{5} = 20$

Czas oczekiwania dla każdego procesu (Waiting time)
$P_{1} = 0$
$P_{2} = 2$
$P_{3} = 3$
$P_{4} = 11$
$P_{5} = 15$

Średni czas oczekiwania
$(0+2+3+11+15) / 5 = 6.2$

### Shortest Job First (SJF)

Czas cyklu przetworzenia (Turnaround time)
$P_{1} = 3$
$P_{2} = 1$
$P_{3} = 20$
$P_{4} = 7$
$P_{5} = 12$

Czas oczekiwania dla każdego procesu (Waiting time)
$P_{1} = 1$
$P_{2} = 0$
$P_{3} = 12$
$P_{4} = 3$
$P_{5} = 7$

Średni czas oczekiwania
$(1+0+12+3+7) / 5 = 4.6$

### Priorytetowy bez wywłaszczeń

Czas cyklu przetworzenia (Turnaround time)
$P_{1} = 15$
$P_{2} = 20$
$P_{3} = 8$
$P_{4} = 19$
$P_{5} = 13$

Czas oczekiwania dla każdego procesu (Waiting time)
$P_{1} = 13$
$P_{2} = 19$
$P_{3} = 0$
$P_{4} = 15$
$P_{5} = 8$

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

### Round Robin

Czas cyklu przetworzenia (Turnaround time):
$P_{1} = 2$
$P_{2} = 3$
$P_{3} = 20$
$P_{4} = 13$
$P_{5} = 18$

Czas oczekiwania dla każdego procesu (Waiting time):
$P_{1} = 0$
$P_{2} = 2$
$P_{3} = 3+4+4+1=12$
$P_{4} = 5+4=9$
$P_{5} = 7+4+2=13$

Średni czas oczekiwania:
$(0+2+12+9+13) / 5 = 7.2$

## Zadanie 4
:::success
Autor: Michał Łukasik
:::

1.
Dla każdego priorytetu możemy stworzyć oddzielną kolejkę round robin. Procesy wykonują się zgodnie z kolejnością priorytetów, natomiast jeśli istnieje kilka procesów o jednakowym priorytecie, to używamy dla nich schematu round robin, każdy maksymalnie przez z góry określony czas (kwant czasu).

2.
a) Q = inf
nie ma żadnych korzyści z Round Robin, jest to FCFS
efektywność około T / (T+S)
słaba interaktywność

b) Q > T
większość procesów wykona się bez przerwań, prawie FCFS
efektywność około T / (T+S)
słaba interaktywność

c) S < Q < T
efektywność to około Q / (Q+S), co jest dobrym wynikiem patrząc na pozostałe opcje

d) Q = S
przez połowę czasu zmieniamy kontekst i przez drugą połowę czasu wykonujemy programy
nie jest to optymalne

e) Q bliskie 0
prawie nic nie zostanie wykonane, większość czasu marnujemy

## Zadanie 5
:::success
Autor: Julian Włodarek
:::

Dane podejście sprawia, że procesy ograniczone przez dostęp do procesora będą miały dłuższy czas działania na procesorze (będą nagradzane / faworyzowane).

Procesy ograniczone przez wejście-wyjście będą działać krócej na procesorze (będą karane).

Zatem taki algorytm może być użyteczny gdy chcemy faworyzować pierwszy rodzaj procesów.

## Zadanie 6

:::success
Autor: Oskar Kropielnicki
:::


**SJF (Shortest Job First)** - algorytm ten wybiera najpierw procesy, które powinny wykonać się najkrócej, a robi to korzystając z dodatkowych danych od użytkownika lub obliczając czasy wykonania bazując na poprzednich czasach wykonania tych procesów.

$\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n$

gdzie $\tau_n$ oznacza przewidywany czas $n$-tej fazy procesora, a $t_n$ to rzeczywisty czas $n$-tej fazy procesora. $0 \leq \alpha \leq 1$ to dowolna stała.

**SRT (Shortest Remaining Time First)** - algorytm podobny do SJF, ale ten odbiera procesom dostęp do procesora. Gdy pojawia się nowy gotowy proces, obecnie wykonujący się traci prawa do procesora, a algorytm wybiera następny proces bazując na pozostałym czasie każdego procesu.

### a
$\alpha = 0,\;\tau_0 = 100 \text{ms}$

Podstawiając $\alpha = 0$ do równania otrzymujemy $\tau_{n+1} = \tau_n$, czyli nie zwracamy w ogóle uwagi na rzeczywiste czasy wykonania i zakładamy, że każda faza trwa równie długo - 100ms.

### b
$\alpha = 0.99,\;\tau_0 = 10 \text{ms}$

Podstawiając $\alpha = 0.99$ do równania otrzymujemy $\tau_{n+1} = 0.99 t_n + 0.01\tau_n$, czyli rzeczywiste czasy wykonania znacząco będą wpływały na predykcję.

## Zadanie 7
:::success
Autor: Marta Strzelec
:::
Standardowo gdy używamy algorytmu planowania procesów z użyciem kolejek wielopoziomowych, procesy są permanentnie przypisane do danej kolejki i nie wędrują pomiędzy nimi. Taki system jest dość nieelastyczny.

**Wielopoziomowe kolejki ze sprzężeniem zwrotnym** to takie kolejki, w których procesy mogą wędrować między kolejkami.

**W jaki sposób taki algorytm obsługuje różne klasy procesów?**
Algorytm posługuje się prostą zasadą - im wyższy priorytet tym bardziej interaktywne procesy.

Dodatkowo, żeby system działał poprawnie, kwanty czasu wraz ze zmniejszeniem się priorytetu powinny maleć (chcemy dość szybko przerywać działanie procesu o priorytecie niższym, gdy pojawi się proces o priorytecie wyższym).

Dodatkowo, jeśli proces czeka zbyt długo w kolejce o niższym priorytecie, może być przeniesiony do kolejki o wyższym priorytecie (zapobieganie zagłodzeniu/starvation -> **reguła promocji**).

Generalnie, algorytm ten jest zdefiniowany za pomocą następujących parametrów:
* liczby kolejek
* algorytmu planowania procesów dla poszczególnych kolejek
* metody, która determinuje kiedy zupgredować dany proces
* metody, która determinuje kiedy zdegradować dany proces

Algorytm ten jest bardzo elastyczny i może być dostosowany do róznych potrzeb - jednak jednocześnie sprawia to, że staje się złożony - aby zdefiniować najlepsze rozplanowanie procesów musimy wziąć pod uwagę różne parametry.
## Zadanie 8
:::success
Autor: Anna Krysta
:::


Zasada działania algorytmu
- jest to algorytm round robin with multilevel feedback,
- scheduler wybiera proces z kolejki o najwyższym priorytecie
- jeżeli jest kilka procesów o tym samym najwyższym priorytecie, to scheduler wybiera do wykonania ten, który był „ready” najdłuższy czas
- jeżeli nie ma żadnego procesu do wykonania, scheduler zostaje zamrożony do czasu przerwania, gdy nastąpi przerwanie, scheduler ponownie będzie wybierał jakiś proces do wykonania
- kolejki priorytetów będą podzielona na dwie grupy: kernel grupa oraz użytkownika kolejki
- priorytety użytkownika kolejek to będą funkcje CPU usage, jeżeli jakaś kolejka użyła niedawno CPU, dostaje wtedy mniejszy priorytet
- kernel kolejki są podzielone w sposób następujący: procesy z niskim priorytetem budzą się po otrzymaniu sygnału, a procesy z wysokim priorytetem nadal są zamrożone
- kolejki kernel także będą obliczać dynamicznie swoje priorytety
- kernel przypisuje priorytet procesowi, który ma zostać uśpiony, korelując stałą wartość priorytetu z powodem uśpienia
- zegar może przerywać proces kilka razy podczas jego kwantu czasu. przy każdym przerwaniu zegara, program obsługi zegara inkrementuje pole w tabeli procesów, które rejestruje ostatnie użycie procesora przez proces. Raz na sekundę, program obsługi zegara dostosowuje również ostatnie użycie procesora przez każdy proces zgodnie z funkcją:
decay(CPU) = CPU/2
- podczas ponownego obliczania ostatniego użycia procesora, program obsługi zegara również ponownie oblicza priorytet każdego procesu zgodnie ze wzorem:

priority = ("recent CPU usage"/2) + (base level user priority)

Gdzie "base level user priority" to priorytet progowy między priorytetami kernel a użytkownika
- procesy mogą kontrolować priorytety wywołując systemową funkcję nice(value), wtedy w funkcji zmieniania priorytetów jest jeszcze jedna składowa – nice value:

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

Wywołanie systemowe nice zwiększa lub zmniejsza pole nice w tabeli procesów o wartość parametru, chociaż tylko superużytkownik może podać wartości nice, które zwiększają priorytet procesu.


## Zadanie 9
:::success
Autor: Anna Krysta
:::


Zasada działania „fair share scheduler” polega na podzieleniu społeczności użytkowników na grupy sprawiedliwego podziału, tak aby członkowie każdej grupy podlegali ograniczeniom regularnego process scheduler w stosunku do innych procesów w grupie. Nowy wzór na aktualizowanie priorytetów jest następujący:

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

System przydziela czas procesora proporcjonalnie do każdej grupy, niezależnie od liczby procesów w grupach.
Czyli dla poniższego przykładu, gdy są dwie grupy 1(A) oraz 2(B, C), to każda tych grup dostaje 50% czasu procesora, zatem A dostaje 50%, B – 25%, C – 25%. Wtedy kolejność wykonywania części jest A, B, A, C, A, B, A, C, A, B, A, C, … , czyli sprawiedliwie.