# Ćwiczenia 11, grupa cz. 14-16, 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | | |
Mateusz Burdyna | | | | | | | | | |
Dariusz Ciesielski | | | | | | | | | |
Dawid Dudek | X | X | X | X | X | X | X | X | |
Mikołaj Dworszczak | | | | | | | | | |
Przemysław Grochal | X | X | X | | | X | | | |
Adam Jarząbek | X | X | X | X | | X |==X== | X | |
Anna Karykowska | X | ==X== | X | X | | X | X | X | |
Oleś Kulczewicz | | | | | | | | | |
Pola Marciniak | X | X | X | X | | X | X | | |
Mikołaj Mroziuk | X | X | X | X | | x | X | | |
Marcelina Oset | x | x | x | | | | | | |
Natalia Piasta | X | X | X | X | xx | X | X | X | X |
Krzysztof Piekarczyk | X | X | ==X== | X | X | X | X | X | |
Marcin Płaza | X | X | ==X== | X | | X | X | | |
Paweł Richert | X | X | X | | | | | | |
Rafał Starypan | X | X | X | X | | X | X | | |
Dawid Strojek | X | X | X | X | | X | X | | |
Mateusz Suszek | X | X | X | X | | ==X== | X | | |
Wojciech Śniady | X | X | X | X | | X | X | | |
Volha Tsekalo | X | X | X | X | | X | X | | |
Yana Vashkevich | X | X | X | X | | X | X | | |
Konrad Woźniak | X | X | X | X | | X | X | | |
Natalia Czerep | | | | | | | | | |
Joanna Stachowicz |==X== | X | X | X | | X | X | | |
:::

**Tu można dodeklarować zad. 6. z listy 8.:**
* Krzysztof Piekarczyk
*
*

**Tu można dodeklarować zad. 9. z listy 9.:**
* Krzysztof Piekarczyk
*
*

**Tu można dodeklarować zad. 9. z listy 10.:**
* Przemysław Grochal
*
*

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

## Zadanie 1
:::success
Autor: Joanna Stachowicz




:::

## Zadanie 2
:::success
Autor: Anna Karykowska
:::

Miary efektywności algorytmów planowania procesów:

▪ **CPU utilization** – keep the CPU as busy as possible
Tutaj sprawne będą algorytmy bez wywłaszczania, czyli np. FCFS. Jeżeli skupimy się na tym aspekcie, to zaniedbamy response time.

▪ **Throughput** – # of processes that complete their execution per time unit
Podobnie do CPU utilization.

▪ **Turnaround time** – amount of time to execute a particular process
Dobre będą np. SJF i SRT. Zaniedbujemy response i waiting time.

▪ **Waiting time** – amount of time a process has been waiting in the ready queue
Tutaj możemy mieć np. algorytm RR. Zaniedbujemy wtedy turnaround time.

▪ **Response time** – amount of time it takes from when a request was submitted until the first response is produced.
Możemy mieć np. algorytmy RR lub priorytetowy z wywłaszczaniem. Zaniedbujemy wtedy pozostałe kryteria.

## Zadanie 3
:::success
Autor: Marcin Płaza
:::


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

avg wait: 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

avg wait: 4.6
Priorytet

turnaround time
P1: 15, P2: 20, P3: 8, P4: 19, P5: 13
waiting time
P1: 13, P2: 19, P3: 0, P4: 15, P5: 8

avg wait: 11
RR 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

avg wait: 7.2
## Zadanie 4
:::success
Autor: Wojciech Śniady
:::
1. Dla każdego priorytetu tworzymy osobną kolejkę Round Robin.
Problem: Starvation - procesy posiadające niski priorytet mogą nigdy nie dojść do momentu wykonywania
Rozwiązanie: Aging - procesom o niskim priorytecie zwiększany jest ich priorytet po długim czasie oczekiwania na wykonianie
2.
a) Q = inf => nie ma w ogóle korzyści z Round Robin, jest to de facto FCFS
b) Q > T => lepszy niż a, bo te to średni czas, np. dla trzech procesów o niskim T i jednym o dużym zyskamy odrobinę, ale nadal nie jest to optymalne
c) S < Q < T => najbardziej optymalny wariant
d) Q = S => czas wykonywania procesu jest równy czasowi na zmianę kontekstu, więc nie jest to optymalne (jeśli zależy nam na wysokiej interaktywności), ponieważ jedynie przez połowę czasu wykonujemy procesy, a drugą połowę czasu tracimy
e) Q bliskie 0 => jeśli S nie jest bliskie 0, to program będzie się liczył bardzo długo

## Zadanie 5
:::success
Autor: Dawid Dudek
:::


Rozważmy dwa rodzaje procesów:

- Te które są ograniczone przez procesor
- Te które mają krótki czas procesora (np mają jakieś i/o burst)

Widzimy, że ta modyfikacja nie jest sprawiedliwa:

- procesy, które są ograniczone przez procesor są nagradzane
- procesy, które czekają na jakiś sygnał są karane -> dostają mniejszy kwant czasu i pomimo, że mógłby się jeszcze wykonywać to proces trafi na koniec kolejki bo dostał mniejszy kwant

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

## Zadanie 6
:::success
Autor: Mateusz Suszek
:::


## Zadanie 7
:::success
Autor: Adam Jarząbek
:::



## Zadanie 8
:::danger
Autor: Natalia Piasta
:::
Uniksowy algorytm planowania procesów to algorytm karuzelowy, tylko z użyciem wielopoziomowych kolejek ze sprzężeniem zwrotnym (ang. *round robin with multilevel feedback*).

Jednak co to tak naprawdę oznacza? Oznacza to, że procesy są przydzielane procesom na określony fragment czasu. Gdy proces wykorzysta swój czas, to zostaje on z powrotem umieszczony w kolejce.

Algorytm Planowania:

Dopóki nie ma procesu do wykonania:
    Dla każdego procesu z kolejki uruchomień:
        Wybierz do wykonania procesu ten o najwyższym priorytecie, który jest załadowany do pamieci
    Jeżeli nie ma procesu kwalifikującego się do wykonania:
        Bezczynność maszyny
        // Przerwanie wyprowadzi maszynę ze stanu bezczynności
Usuń wybrany proces z kolejki uruchomień
Przełącz kontekst na wybrany proces i wznów jego wykonanie

Wybieramy proces o najwyższym priorytecie z tych gotowych uruchomienia. Jeśli jest parę procesów o najwyższym prorytecie to wybieramy ten gotowy do uruchomienia przez najdłuższy czas.

Są dwie klasy priorytetów:
* priorytety użytkownika (ang. *user priority*)
* priorytety jądrowe (ang. *kernel priority*)


Jądro oblicza priorytet procesu w określonych stanach procesu:
* Przypisuje priorytet procesowi, który ma zostać uśpiony na podstawie powodu uśpienia.
* Priorytet procesu zostaje przeliczony podczas zmiany.
* Obsługa zegara co jakiś czas oblicza priorytety wszystkich procesów.

Za każdym razem obliczmy rozpad procesora (ang. *decay of the CPU*) wzorem:
$CPU = decay(CPU) = \frac{CPU}{2}$

Oraz priorytet procesu:
$priority = (nowe\ \frac{CPU}{2}) + (podstawowy\ priorytet\ użytkownika)$

## Zadanie 9
:::success
Autor: Anna Karykowska
:::

Większość założeń zostaje taka, jak w zadaniu 8, ale dodajemy podział na grupy.

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

$priority = (\frac{CPU}{constant}) + (\frac{Group}{constant}) + (podstawowy\ priorytet\ użytkownika) + (nice)$

Przykład dla:
1. grupa - A
2. grupa - B, C