# Ćwiczenia 11, grupa cz. 12-14, 26. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | x | x | x | x | x | x | x | x | |
Adam Ciężkowski | | | | | | | | | |
Jacek Długopolski | x | x | x | x | | | x | x | x |
Jakub Fila | x | x | x | | | x | x | x | x |
Krzysztof Grynkiewicz | | | | | | | | | |
Michał Hetnar | x | x | | | | | | | |
Hubert Jabłoński | x | x | x | x |==x==| x | x | x | x |
Antoni Kamiński | | | | | | | | | |
Paweł Karaś | X | ==X== | X | X | X | X | X | X | X |
Emil Kisielewicz | x | x | x | x | x | | x | | |
Kacper Komenda | x | x | x | x | x | x | x |==x==| x |
Filip Komorowski | x | x | x | x | x | x | x | x | |
Piotr Piesiak | x | x | x | x | x | x | x | x | x |
Artur Krzyżyński | x | x | x | x | x | x | x | x | ==x== |
Patryk Mazur | X | X | ==X== | X | | X | X | | |
Szymon Mleczko | x | x | x | x | x | x | x | x | |
Michał Mróz | X | X | X | | | | | | |
Dominik Olejarz | ==x== | x | x | x | x | x | x | x | x |
Magdalena Słonińska | X | X |==X==| X | | X | X | | |
Oleś Kulczewicz | X | X | X | X | | | | | |
Adam Szeruda | X | X | X | X | X | X | X | X | X |
Kamil Tasarz | X | X | X | X | | | X | | |
Michał Zieliński | ==X== | X | X | X | X | X | X | X | X |
:::

Lista 10, zadanie 9:
- Adam Szeruda
- Piotr Piesiak
- Jacek Długopolski
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Dominik Olejarz
:::
*proces ograniczony przez dostęp do procesora-proces który potrzebuje byc przez dlugi czas wykonywany

*proces ograniczony przez wejście-wyjście - proces który potrzebuje interakcji z urządzeniami zewnetrznymi

*proces interaktywny - proces który potrzebuje interakcji z użytkownikiem (np klikniecie przycisku)

*program wsadowy - wykonywany w trybie wsadowym, bez wpływu użytkownika na przebieg programu

## Zadanie 2
:::success
Autor: Paweł Karaś
:::


### Miary efektywności algorytmów
- **CPU Utilization**
Utrzymywanie procesora zajętego
- **Throughput**
Liczba procesów które się zakończą na daną jednostkę czasu
- **Turnaround time**
Średni czas na wykonanie danego procesu
- **Waiting time**
Średni czas jaki proces musiał czekać w ready queue
- **Response Time**
Czas jaki zajął systemowi od czasu rządania procesu do czasu pierwszej odpowiedzi

| Algorytm | Optymalizuje |
| --------------------------- | -------------------------------------------- |
| FCFS | CPU Utilization |
| SJF | CPU Utilization, Throughput, Turnaround time |
| SRT | Throughput, Turnaround time |
| Round Robin | Response Time |
| Priority Queue (preemptive) | Response Time |

## Zadanie 3
:::success
Autor: Patryk Mazur
:::

:::spoiler First-Come, First-Served FCFS

### Czas cyklu przetworzenia (Turnaround time)
$P1 = 2$
$P2 = 3$
$P3 = 11$
$P4 = 15$
$P5 = 20$

### Czas oczekiwania dla każdego procesu (Waiting time)
$P1 = 0$
$P2 = 2$
$P3 = 3$
$P4 = 11$
$P5 = 15$

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

:::spoiler Shortest-Job-First SJF

### Czas cyklu przetworzenia (Turnaround time)
$P1 = 3$
$P2 = 1$
$P3 = 20$
$P4 = 7$
$P5 = 12$

### Czas oczekiwania dla każdego procesu (Waiting time)
$P1 = 1$
$P2 = 0$
$P3 = 12$
$P4 = 3$
$P5 = 7$

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

:::spoiler Priorytetowy bez wywłaszczeń

### Czas cyklu przetworzenia (Turnaround time)
$P1 = 15$
$P2 = 20$
$P3 = 8$
$P4 = 19$
$P5 = 13$

### Czas oczekiwania dla każdego procesu (Waiting time)
$P1 = 13$
$P2 = 19$
$P3 = 0$
$P4 = 15$
$P5 = 8$

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

:::spoiler Round-Robin

### Czas cyklu przetworzenia (Turnaround time)
$P1 = 2$
$P2 = 3$
$P3 = 20$
$P4 = 13$
$P5 = 18$

### Czas oczekiwania dla każdego procesu (Waiting time)
$P1 = 0$
$P2 = 2$
$P3 = 3+4+4+1=12$
$P4 = 5+4=9$
$P5 = 7+4+2=13$

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

## Zadanie 4
:::success
Autor: Jacek Długopolski
:::

## Zadanie 5
:::success
Autor: Hubert Jabłoński
:::

| P | Burst time | I/O burst |
|-----|------------|-----------|
|$P_1$| 10 | 3 |
|$P_2$| 8 | - |

$Q = 4$

$|P_1 P_1 P_1|P_2 P_2 P_2 P_2|P_1|P_2 P_2 P_2 P_2|P_1 P_1 P_1|P_1|P_1 P_1 P_1|P_1|P_1|$

Karanie procesów czekające na sygnały wejścia/wyjścia

Faworyzowanie wszystkich innych procesów
## Zadanie 6
:::success
Autor: Filip Komorowski
:::

* SJF

* Wykładnicze uśrednianie

* SRT

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

W tym przypadku widzimy, że poprzednie czasy rzeczywiste nie są w żaden sposób uwzględniane i bierzemy cały czas początkową predykcję.

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

W tym przypadku z kolei poprzednie predykcje mają marginalne znaczenie i predykcja następnego czasu będzie równa mniej więcej poprzedniemu czasowi wykonania.

## Zadanie 7
:::success
Autor: Adam Szeruda
:::

> 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?

Wilopoziomowa kolejka ze sprzężeniem zwrotnym:
- składa się z $n$ składowych kolejek, każda ma swój algorytm planowania
- ustalona metoda degradacji i promocji procesu na późniejszą/wcześniejszą kolejkę
- ustalona metoda wyboru kolejki dla procesu

Obsługa procesów interaktywnych, czasu rzeczywistego, wsadowych - każdemu procesowi przydzielana jest początkowa kolejka - procesom czasu rzeczywistego jedna z początkowych kolejek, procesow wsadowym jedna z końcowych.

Reguła promocji - metoda zapobiegania starzeniu się procesów - proces o długim czasie oczekiwania zostaje promowany do wcześniejszej kolejki.

## Zadanie 8
:::success
Autor: Kacper Komenda
:::
Klasyczny algorytm UNIX wykorzystuje wiele karuzel RR dla różnych poziomów priorytetów.
Kolejki podzielone są na kolejki jądra i kolejki użytkownika, nie mogą przeskakiwać między sobą.
Priorytety kernela są zakodowane, by np. czekanie na dysk było wyżej niż czekanie na bufor.
Procesy nie mogą przeskoczyć ze strefy użytkownika na tę kernelu. Przy powrocie z kernelu system oblicza priorytety powracających procesów.
W trakcie działania priorytety użytkownika mogą przeskakiwać pomiędzy poszczególnymi levelami. Kernel dynamicznie oblicza priorytet stosując do tego priorytet zadany przez użytkownika i czas dostępu do procesora. Co jakiś czas dodawany jest czas procesora. Rekalkulowane jest to co mniej więcej sekundę, wtedy zgromadzony czas procesora dzielony jest na 2. Aby obliczyć aktualny priorytet dzieli się obecnie zgromadzony czas procesora na 2 i do tego dodaje się priorytet zlecony przez użytkownika.
Dodatkowo istnieje jeszcze zmienna "nice", która jest dodawana do obliczanego priorytetu. Jednak tylko superużytkownik może dodać do tego obliczonego priorytetu wartość, która zwiększy priorytet.

## Zadanie 9
:::success
Autor: Artur Krzyżyński
:::

:::info
Zadanie 9. Zaprezentuj algorytm planowania ze sprawiedliwym
podziałem (ang. fair share scheduler), będący wariantem
algorytmu z poprzedniego zadania.

Wskazówka: Przeczytaj podrozdział 8.1.5 książki wymienionej we wskazówce do
zadania 8.
:::

Tak jak w zadaniu 8 tylko dodajemy GROUP/const
priority = 'base priority' + CPU/const + 'nice value' + GROUP/const

decay(GROUP) = GROUP/2

Przykład:
A - grupa 1
B, C - grupa 2
ABACABAC..
grupa 1 - 50%
grupa 2 - 50% (po 25% na B, C)