# Ćwiczenia 12, grupa cz. 14-16, 25 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | |
Wojciech Bogucki | | | X | X | | X | X |
Mateusz Cerulewicz | X | X | X | | X | | |
Mateusz Garncarczyk | ==X== | X | X | X | | | |
Mateusz Golisz | X | X | X | X | X | X | |
Mateusz Kitzol | X | X | X | X | X | | |
Piotr Mańkowski | | | | | | | |
Aleksandra Nicpoń | 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 |
Dominik Szczepaniak | X | X | X | X |==X==| X | X |
Taras Tsehenko | | | | | | | |
Maksymilian Wiśniewski | | | | | | | |
Martyna Wybraniec | X | X | X | X | X | | |
Natalia Zychowicz | X | X | X | X | X | |==X==|
Patryk Maciąg | X | X | X | X | | | |
Michał Mękarski | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Mateusz Garncarczyk
:::


**Okres - periodic {p}**
**Czas obsługi - processsing time {t}**

|$Proces$|$Okres\ (p)$ |$Czas\ obsługi\ (t)$|
|--------|-------------|--------------------|
| P1 |50 ms | 35 ms |
| P2 |100 ms | 20 ms |
| P3 |200 ms | 10 ms |
| P4 |250 ms | $x$ ms |

* Jaka jest maksymalna wartość $x$, dla której będzie to możliwe?
W systemie twardego czasu rzeczywistego (ang. hard real-time system) mamy gwarancję, że każdy proces wykonana się przed deadline'm, czyli muszą wykonać się conajmniej raz w czasie trwania jednego cyklu.
Z tego wynika poniższe równanie:
$\frac{35}{50} + \frac{20}{100} + \frac{10}{200} + \frac{x}{250} = 1$
$x = \frac{25}{2} = 12.5$
* Jak zmieni się ta odpowiedź, gdy będziemy mieli do czynienia z systemem miękkiego czasu rzeczywistego?
W systemie miękkiego czasu rzeczywistego nie ma gwarancji, że każdy proces wykona się w jednym cyklu conajmniej raz np. w czasie oglądania filmu nie zauważymy różnicy, gdy jedna z klatek zostanie wyświetlona z opóźnieniem lub wcale. Zatem wartość $x$ musi być poniżej czasu wykonania, czyli $x\ <\ 250\ ms$, ale trzeba zauważyć, że gdy $x$ $\approx 250\ ms$, to będzie opóźniało to inne procesy, powodując problemy.

## Zadanie 2
:::success
Autor: Ksawery Plis
:::


**a) RMS (rate-monotonic scheduling):**


Nie jest to możliwe, ponieważ w pewnym momencie zostaje dochodzimy do
deadline'u $P2$ a mamy ciągle do wykonania 5 jednostek czasu pracy procesu $P2$.

**b) EDF (earliest deadline first):**


Jest to możliwe
## Zadanie 3
:::success
Autor: Wojciech Bogucki
:::

unsigned int goodness(p) {
 if (p->policy == SCHED_REALTIME)
    return 1000 + p->priority;
 if (p->counter == 0)
    return 0;
 return p->counter + p->priority
}

a) Przejście do kolejnej epoki powinno nastąpić w momencie, gdy zmienna `p->counter` aktualnego procesu osiągnie wartość 0. Oznacza to, że proces wyczerpał swój kwant czasu w bieżącej epoce i powinien zostać przeniesiony na koniec kolejki procesów gotowych.

b) Czas działania tego algorytmu planowania zadań zależy od liczby procesów w systemie. Dla n procesów, algorytm musi przeglądać kolejkę procesów gotowych, aby wybrać następny proces do wykonania. Złożoność czasowa tego przeglądania jest proporcjonalna do liczby procesów, czyli O(n).

c) W tym algorytmie istnieje potencjalne ryzyko głodzenia procesów. Procesy o wyższych priorytetach, zwłaszcza te o priorytetach z przedziału 0-1000 (procesy miękkiego czasu rzeczywistego), są faworyzowane i mają większe szanse na dostęp do zasobów procesora. Procesy o niższych priorytetach mogą być stale pomijane i nie dostawać wystarczającego czasu procesora, co może prowadzić do głodzenia.

d) Ten algorytm faworyzuje procesy miękkiego czasu rzeczywistego (procesy o typie `SHED_REALTIME`), które mają priorytety w zakresie 0-1000. Te procesy mają najwyższe wartości funkcji `goodness()`, co daje im większą szansę na dostęp do procesora. Procesy o typie innym niż `SHED_REALTIME` (np. `SHED_NORMAL`) mają niższe priorytety i są mniej faworyzowane przez ten algorytm.
## Zadanie 4
:::success
Autor: Martyna Wybraniec
:::


* algorytm jest wywłaszczający
* priorytety 0-99 są przeznaczone dla procesów czasu rzeczywistego, a 100-140 dla pozostałych
* te priorytety mapują się na globalny priorytet (im większa wartość numeryczna tym mniejszy priorytet)
* procesy czasu rzeczywistego mają statyczny priorytet
* procesy z większym priorytetem otrzymują większy kwant czasu
* algorytm przechowuje dwie kolejki: dla procesów aktywnych oraz zużytych
* algorytm wybiera proces o najwyższym priorytecie z kolejki procesów aktywnych w czasie O(1)
* proces pozostaje w kolejce aktywnej dopóki nie zużyje całego swojego kwantu czasu, wtedy przenosimy go do kolejki dla procesów zużytych
* w momencie kiedy opróżnimy kolejkę aktywną, zamieniamy ją na kolejkę procesów zużytych a ta druga staje się kolejką aktywną


## Zadanie 5
:::success
Autor: Dominik Szczepaniak
:::

Wszystkie zadania mają przydzielony priorytet statyczny na podstawie wartości nice od -20 do 19, gdzie większa liczba oznacza niższy priorytet.

Scheduler w systemie Linux 2.6.8.1 preferuje zadania związane z operacjami wejścia/wyjścia (I/O) i karze zadania związane z procesorem, poprzez dodawanie lub odejmowanie od priorytetu statycznego zadania. Dostosowany priorytet, zwany priorytetem dynamicznym zadania, jest dostępny poprzez zmienną priorytetu tego zadania.
Jeśli zadanie jest interaktywne, to jego priorytet jest zwiększany. Maksymalny dodatkowy bonus do priorytetu wynosi 5.

Dynamiczne premie i kary za priorytet są obliczane na podstawie heurystyki interaktywności. Heurystyka ta jest zaimplementowana poprzez monitorowanie, ile czasu zadanie spędza w stanie uśpienia (np. zablokowane na operacjach I/O) w porównaniu do aktywności.

Kiedy zadanie zostaje wznowione, jego całkowity czas uśpienia jest dodawany do zmiennej sleep_avg (choć wartość sleep_avg zadania nie może przekroczyć wartości MAX_SLEEP_AVG).

Kiedy zadanie oddaje procesor (dobrowolnie lub przymusowo), czas trwania bieżącego zadania jest odejmowany od wartości sleep_avg. Im wyższa wartość sleep_avg dla zadania, tym wyższy jest jego priorytet dynamiczny. Heurystyka ta jest dość dokładna, ponieważ uwzględnia zarówno czas spędzony na uśpieniu, jak i na wykonywaniu.

Timeslice, czyli kwant czasu przeznaczony dla zadania, jest obliczany poprzez skalowanie priorytetu statycznego zadania w celu uzyskania odpowiedniego zakresu dla kwantu czasu, przy zachowaniu określonego minimalnego i maksymalnego zakresu. Im wyższy priorytet statyczny zadania, tym dłuższy timeslice otrzymuje. Funkcja task_timeslice() po prostu wywołuje makro BASE_TIMESLICE, które jest zdefiniowane jako:


Zasadniczo jest to minimalny przedział czasu plus statyczny priorytet zadania przeskalowany do możliwego zakresu przedziału czasu (MAX_TIMESLICE - MIN_TIMESLICE).

## Zadanie 6
:::success
Autor: Rafał Spyra
:::

## Zadanie 7
:::success
Autor: Natalia Zychowicz
:::
## Wstęp
### Mechanizmy kolejek
### Ocena interaktywności

### Kalkulator priorytetu
* ULE wykorzystuje wynik z oceny interaktywności i wartość nice, aby wyliczyć priorytet.
* Daje szansę na uruchomienie zadań interaktywnych
wcześniej niż zadania nieinteraktywne w momencie ich umieszczania
w tej samej kolejce.

### Nice Impact/ Kalkulator Slice

* ULE śledzi liczbę wątków w kseq
z każdą wartością nice. Zachowuje również bieżącą minimalną wartość nice.
* Wątki znajdujące się w oknie nice otrzymują
wartość wycinka, która jest odwrotnie proporcjonalna do
różnica między ich dobrą a najmniejszą wartością nice czyli
wartością aktualnie zapisana w kseq.
* min wartość slice - 10ms
* max wartość slice - 140 ms
* Zadania interaktywne otrzymują minimalną wartość wycinka.


### Mechanizm balansowania obciążenia procesorów

#### PULL CPU Migration
* ULE implementuje migrację procesora, sprawdzając kolejki innych procesorów pod kątem możliwych do uruchomienia wątków, gdy jeden z procesorów jest bezczynny.
#### PUSH CPU Migration
* dwa razy na sekundę wybiera dwa najbardziej
niezbalansowane kseqs i migruje niektóre wątki do
kseqs z najniższym obciążeniem.
* Jeśli kseqs są niezrównoważone tylko jednym wątkiem jeden wątek jest nadal przenoszony z jednego kseq do następnego. Jest to przydatne, aby zapewnić całkowitą uczciwość
wśród procesów.