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

Tu można do-deklarować zadanie 9 z listy 11.:
- Anna Karykowska
- Dawid Dudek

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

## Zadanie 1
:::success
Autor: Krzysztof Piekarczyk
:::


a) hard-real time systems

Każdy proces musi zostać wykonany przynajmniej raz w cyklu.

$\frac{35}{50} + \frac{20}{100} + \frac{10}{200} + \frac{x}{250} = 1$

$x = 12.5$

b) soft-real time systems

Nie musimy gwarantować wykonania się każdego procesu w cyklu. W konsekwencji wartość x może być bliska 250 (w zależności od założeń). Może być to jednak niepraktyczne.

## Zadanie 2
:::success
Autor Mateusz Suszek
:::


P1 - t (czas wykonania) = 25, p (okres) = 50
P2 - t (czas wykonania) = 30, p (okres) = 75

a) RMS (rate-monotonic scheduling) - im krótszy okres, tym większy priorytet

b) EDF (earliest deadline first) - im wcześniejszy deadline, tym większy priorytet

## Zadanie 3
:::success
Autor: Dawid Dudek
:::


### Kiedy przejść do kolejnej epoki?

Gdy w kolejce procesów aktywnych nie ma już procesów mających p->counter > 0

### W jakim czasie działa algorytm?

Działa on w O(n) -> Dla każdego procesu policzenie funkcji goodness jest w czasie trwałym. Musimy policzyć to dla każdego procesu i wybrać max.

### Czy algorytm głodzi procesy?

Głodzenie nie może wystąpić ponieważ epoka trwa aż wszystkie aktywne procesy mają p->counter > 0. W nowej epoce natomiast każdy proces dostanie niezerową liczbę ticków (zakładmay, że NICE_TO_TICKS > 0)

### Wszystkie typy faworyzowanych procesów

- procesy miękkiego czasu rzeczywistego
- procesy które mają wysoki priorytet
- procesy interaktywne (bo one często mogą nie wykorzystać całego swojego countera za jednym razem - proces będzie skakał z aktywnych do nieaktywnych)

## Zadanie 4
:::success
Autor: Paweł Richert
:::
Algorytm O(1):
-Zapewnie wsparcie dla wieloprocesorowych systemów

-Jest to algorytm wywłaszczający.

-Ma dwa rodzaje priorytetu real time (0-99) i nice value (100-140).
mniejsza wartosc priorytetu -> wyższy priorytet.

-Linux przyznaje taskom z wyższym priorytetem większą ilość czasu.


-Jeżeli task przekroczy swój time slice to uznajemy go za przedawniony.

-Procesy są trzymane w kolejce.

-Każdy procesor ma swoja własną kolejke.

-Każda kolejka zawiera dwie priorytetowe tablice aktywnych i przedawnionych procesów. Gdy skonczy się kolejka aktywnych procesów to procesor zamienia aktywną kolejkę na expired a expired na aktywną. Czym dłużej proces "śpi" tym większy będzie jego nice-value.

## Zadanie 5
:::success
Autor: Dawid Strojek
:::


**Static priority (nice value)**
- im mniejsza liczba, tym większy priorytet
- na linuksie wartości (-20, 19)
- początkowo wartość 0
- może zostać zmieniony za pomocą wywołania systemowego nice()
- scheduler nie zmienia tej wartości

**Dynamic priority**
- bonusy dla "I/O hog" (max 5) odejmowane od static priority (większy priorytet)
- kary dla "CPU hog" (max 5) dodawane do static priority (mniejszy priorytet)
- heurystka interaktywności
- sleep_avg - im wyższe, tym wyższy priorytet
- proces się budzi - czas snu jest dodawany do sleep_avg
- proces wchodzi w stan uśpienia - czas działania jest odjęty od sleep_avg

**Kwant czasu**
Skalowanie "static priority" na przedział od minimalnej do maksymalnej długości kwantu czasu (im większy priorytet tym większy kwant jest otrzymany).

#define BASE_TIMESLICE(p) 
(MIN_TIMESLICE + ((MAX_TIMESLICE - MIN_TIMESLICE) * 
(MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1)))

## Zadanie 6
:::success
Autor: Przemysław Grochal
:::

CFS rezygnuje z przydziału kwantów czasu na podstawie priorytetu. Zamiast tego definiuje `target latency`, czyli okres, w trakcie którego każdy proces chcący się wykonać zostanie uruchomiony przynajmniej raz. Następnie, w oparciu o `nice value`, scheduler przydziela procesom pewną porcję tego `target latency`.
`Nice value` może wahać się od -20 do 19, gdzie niższa liczba oznaczy wyższy priorytet.

Dla każdego procesu pamiętamy jego wirtualny czas wykonania procesu (`vruntime`). Domyślnie, jest to faktyczny czas wykonanania procesu, skalowany przez `nice value`. Planowanie odbywa się poprzez wybór procesu z najmniejszym `vruntime`. Dodatkowo, procesy z wyższym priorytetem mogą wywłaszczać procesy z priorytetem niższym.

Aby sprawnie wybierać kolejne zadania do wykonania, informacje o procesach przetrzymujemy w drzewie czerwono-czarnym. Węzeł umieszczony najbardziej na lewo jest następnym zadaniem do wykonania. Umieszczenie go w pamięci podręcznej umożliwia szybkie uzyskanie tej wartości. Proces, który nie może zostać uruchomiony, na przykład z powodu oczekiwania na I/O, jest wyrzucany z drzewa.

CFS umożliwia balansowanie pomiędzy wieloma rdzeniami procesora. Jest również NUMA-aware i stara się minimalizować migrację wątków. Dla każdego wątku, definiujemy jego obciążenie jako połączenie jego priorytetu ze średnim wykorzystaniem CPU. Obciążenie kolejki zadań to po prostu suma obciążeń wewnątrz kolejki i balansowanie odbywa się przez wyrównywanie "rozmiaru" kolejek.

Aby uniknąć kar związanych z dostępami pamięci, wyznaczamy domeny planowania(? — scheduling domains), czyli zbiory rdzeni, które mają dostęp do tych samych zasobów systemowych i mogą balansować się między sobą. Domeny można hierarchizować. Wtedy migracja wątku nastąpi do domeny o najniższym możliwym stopniu.

Perfekcyjną wielozadaniowość przybliżamy za pomocą `target latency`. Im mniejsza ona jest, tym mniejsze będą kwanty czasu przydzielone procesom, a tym samym będą w danej jednosce czasu wykonywać się częściej. Ze względu na priorytety procesów, nie uzyskamy najpewniej równego podziału, lecz możemy się do niego zbliżyć.

## Zadanie 7
:::danger
Autor: do-deklarować
:::