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

Tu można zadeklarować zad 9 z listy 11:
-Anna Krysta
-
-

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

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

W systemie twardego czasu rzeczywistego mamy gwarancję, że każdy proces wykona się przed deadline'm, czyli musi wykonać się przynajmniej raz w cyklu. Z tego wynika, że x musi spełniać poniższe równanie:

35/50 + 20/100 + 10/200 + x/250 = 1
x = 25/2

Jeśli rozważymy system miękkiego czasu dostępu to maksymalna wartość x będzie bliska 250 (w zależności od założeń). Warto jednak zauważyć, że taki czas obsługi procesu będzie skrajnie nie praktyczny, bo procesy nie będą wykonywane tak często jak powinny być.

## Zadanie 2
:::success
Autor: Kacper Sojda
:::

a)


Nie da się

b)


Da się

## Zadanie 3
:::success
Autor: Kacper Jóźwiak
:::

* Przejście do następnej epoki występuje, gdy w kolejce aktywnych procesów nie
ma już procesów o wartości counter większej od 0.
* Algorytm działa w czasie $O(n)$, gdzie $n$ to liczba procesów, bo funkcja
*goodness* wykonuje się w czasie stałym, a musimy wywołać ją dla każdego
procesu, by znaleźć maksimum.
* Głodzenie procesów nie może wystąpić, ponieważ epoka trwa dopóty, dopóki
wszystkie aktywne procesy mają counter > 0. Po przejściu do kolejnej epoki
każdy proces dostaje niezerową liczbę *ticków*.
* Typy procesów, które są faworyzowane to:
* procesy czasu rzeczywistego,
* procesy, które mają wysoki priorytet,
* procesy nieinteraktywne, bo wykorzystują cały counter za jednym razem

## Zadanie 4
:::success
Autor: Marta Strzelec
:::


**Algorytm "O(1)" jest wywłaszczający (preemptive)**.

**Procesy dzielimy na dwie kategorie: real-time tasks i other tasks.**
* Nadejemy im kolejno priorytety od 0-99 i 100-140.
* Im mniejszy numer priorytetu, tym większy priorytet oraz zadany mu kwant czasu.
* Procesy real-time mają priorytet statyczny
* Other-tasks mają priorytety statyczne i priorytety dynamiczne. Te ostatnie mogą być modyfikowane za pomocą *nice* .

**Algorytm posiada dwie kolejki: active array i expired array**.
* Na początku wszystkie procesy znajdują się w active array i są wyciągane zgodnie z priorytetem (w czasie O(1)).
* Jeżeli jakiś proces nie zdąży wykonać się w swoim kwancie czasu przenoszony jest do tablicy expired array.
* W momencie, gdy active array staje się pusta, expired array traktujemy jako active array, a active array jako expired array.

## Zadanie 5
:::success
Autor: Jakub Krzyżowski
:::
Wszystkie zadania mają pola `static_prio` (wartości od -20 do 19 - im niższa liczba tym wyższy priorytet) i `sleep_avg`.
Priorytet statyczny zadania może być zmieniany przez użytkownika na wywołaniu `nice()`, poza tym nie jest zmieniany przez schedulera.
`sleep_avg` za to jest aktualizowane przy zmianie stanu procesu: przy wybudzeniu procesu czas jego 'snu' jest dodawany do `sleep_avg` (maksymalnie `MAX_SLEEP_AVG`), a przy zwolnienu CPU przez proces czas jego działania jest odejmowany od `sleep_avg`

**Dynamiczny priorytet procesu** jest obliczany przez funkcję `effective_prio()`
Funkcja działa w następujący sposób:

jeśli zadanie jest typu Real Time to zwróć priorytet statyczny zadania.
bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
prio = p->static_prio - bonus;

gdzie `p` to proces, a `CURRENT_BONUS(p)` to makro mapujące `p->sleep_avg` na zakres 0 - MAX_BONUS

następnie sprawdza, czy nadanie bonusu nie spowoduje przekroczenia limitu priorytetu dla zadania non-RT (-19 - 20)

**Kwant czasu procesu** wyliczany jest przez funkcję `task_timeslice()`, która do `MIN_TIMESLICE` dodaje `p->static_prio` przeskalowane do odpowiednich wartości z zakresu (MIN_TIMESLICE, MAX_TIMESLICE).

## Zadanie 6
:::success
Autor: Mikołaj Swoboda
:::

Istnieją klasy, w wariancie podstawowym dwie: *default* oraz *real-time*. Każda ma własny priorytet. Poza tym procesy mają wartości *vruntime* „wirtualny czas działania” oraz *nice*.

Za pomocą tych pierwszych algorytm liczy, jak długo dany proces działał, stosując dodatkowo stopniowe zwiększanie dla zadań o niskim priorytecie i zmniejszanie dla zadań o wysokim priorytecie. Na podstawie *vruntime* planista decyduje, któremu procesowi dać dostęp do procesora (wybierana jest najmniejsza).

Wartości *nice*, z przedziału [-20, 19], służą do wyznaczania, ile czasu pracy procesora przydzielić danemu procesowi. Im większa, tym proces „uprzejmiejszy” -- wówczas ustępuje on innym. Domyślnie wszystkie są równe 0.

Planista CFS nie używa dyskretnych wartości kwantów czasu, ale zamiast tego wyznacza docelowy przedział czasu (*targeted latency*), w którym każdy proces powinien wykonać się co najmniej raz. Ten właśnie przedział jest dzielony między zadania na podstawie wartości *nice*.

Ta cecha pozwala przybliżać perfekcyjną wielozadaniowość. Załóżmy, że wartości *nice* wszystkich *n* procesów są takie same. Ponieważ kwanty czasu mogą być dowolnie małe, docelowy przedział czasowy może być bardzo mały, przybliżając żądane $\varepsilon$. Skoro czas przełączania kontekstu wynosi 0, każdy proces dostanie $n/\varepsilon$ czasu na pracę.

## Zadanie 7
:::success
Autor: Oskar Kropielnicki
:::


Czas działania planisty ULE jest stały, niezależny od ilości procesów.
Identyfikuje procesy interaktywne i daje im tak niski czas odpowiedzi jak to możliwe.
W skład jego kluczowych komponentów wchodzi kilka kolejek, 2 algorytmy wyrównujące zużycie procesora, przydzielanie wyniku procesom na podstawie interaktywności, szacowanie użycia procesora, kalkulator długości przydziału do procesora, oraz kalkulator priorytetów.

### Kolejki

Każdy procesor ma własną kolejkę "kse" (kseq), która zawiera 3 tablice kolejek uruchamiania indeksowanych kubełkowanymi priorytetami. Dwie z tych wewnętrznych kolejek używane są do implementacji klas planowania przerwań, czasu rzeczywistego i współdzielenia czasu. Ostatnia, trzecia z nich jest dla klasy bezczynnej. Do tego, kseq również pamięta statystyki obciążenia i obecny przedział `nice`.

ULE jest sterowany zdarzeniami, nie ma żadnego mechanizmu odmierzania czasu, który dostosowuje priorytet wątków by zapobiec ich głodzeniu. Sprawiedliwość zaimplementowana jest przez dwie kolejki: obecną i następną. Każdy wątek, który dostaje kwant, jest przydzielony do jednej z tych kolejek. Wątki brane są z kolejki obecnej w kolejności priorytetów, dopóki nie zostanie opróżniona. Wtedy, kolejki są zamieniane. To gwarantuje, że każdy proces wykorzysta swój kwant co dwie takie zmiany, bez względu na priorytet.

Wątek jest przydzielony do kolejki dopóki nie zaśnie, lub na czas swojego kwantu. Podstawowy priorytet, wielkość kwantu i wynik interaktywności są ponownie przeliczane za każdym razem, gdy kwant zostanie wyczerpany. Wątek przydzielany jest do kolejki obecnej, jeśli jest interaktywny. To sprawia, że otrzymują niski czas odpowiedzi.

Wątki przerwaniowe i czasu rzeczywistego również dodawane sa do tej kolejki, tak jak te, których priorytet został odpowiednio zwiększony przez propagację priorytetu. Bez tego, nieinteraktywny wątek w kolejce następnej, mógłby powstrzymywać jakiś bardzo ważny wątek przed działaniem, jeśli ten pierwszy trzyma jakąś wielką blokadę.

Klasa bezczynna ma oddzielną kolejkę. Sprawdzana jest tylko wtedy, gdy nie ma niczego innego do zrobienia. Procesy bezczynne zawsze są tu dodawane, chyba że ich priorytet został zwiększony przez propagację.

### Wynik interaktywności

W ULE interaktywność wątku zależy od czasu trwania jego dobrowolnego snu i czasu działania. Interaktywne procesy zazwyczaj dłużej śpią czekając na dane od użytkownika. Ten czas jest wykorzystywany przez planistę, żeby lepiej oszacować planowane zachowanie aplikacji. Jeśli niedobrowolny sen byłby brany pod uwagę, nieinteraktywne procesy mogłyby być wysoko oceniane tylko dlatego, że nie było im dane dłużej działać przez obciążenie systemu.

Czas dobrowolnego snu liczony jest przez ilość tyknięć między zaśnięciem a obudzeniem lub podczas snu warunkowego.

Wynik interaktywności liczony jest na podstawie związku między czasem snu, a czasem działania.
Jeśli czas snu przekracza czas działania, wynik to stosunek czasu snu do czasu działania, przeskalowany przez połowę zakresu wyniku ($m$).
Jeśli jednak to czas działania przekracza czas snu, to odwrotny stosunek jest skalowany, a następnie ten skalar jest jeszcze dodawany.


W ten sposób procesy, które dłużej śpią niż pracują, są wyraźnie oddzielone od tych pozostałych. Gdy suma tych dwóch liczb osiągnie pewien konfigurowalny limit, obie są odpowiednio przeskalowywane. Zachowuje to ich względne wielkości, a także sprawia, że szybciej jest wykryć proces, który przestaje nagle być interaktywny.

Ten wynik używany jest do określenia czy dany proces powinien trafić do kolejki obecnej. Jeśli ten wynik jest niższy niż pewna ustalona wartość, proces oznaczany jest jako interaktywny.

### Kalkulator priorytetu

Priorytet używany w ULE określa kolejność, w jakiej wątki w kolejce uruchomieniowej powinny być wybierane. W przeciwieństwie do niektórych innych planistów, nie jest on tutaj wykorzystywany to określania sprawiedliwości.
Tylko wątki czasu współdzielonego mają obliczany priorytet; reszta ma statycznie ustawiany.
Do ustalenia priorytetu przydaje się wynik interaktywności. Potem, do priorytetu dodawana jest wartość `nice`, która może nawet zmniejszyć priorytet, jeśli jest ujemna.
W ogólności sprawia to, że procesy interaktywne uruchamiane są wcześniej niż pozostałe, jeśli są w tej samej kolejce. Jednak może się też zdarzyć, że nieinteraktywne procesy o ujemnej `nice` otrzymają wyższy priorytet niż jakiś interaktywny, lecz drogi. Jest to akurat pożądane z uwagi na czas odpowiedzi i dystrybucję dostępu do procesora.

### Kalkulator kwantu / wpływ `nice`

Ostateczna implementacja `nice` wykorzystuje ruchomy przedział wartości `nice`, którym należą się kwanty. ULE pamięta ilość wątków w kseq z każdą wartością `nice`. Pamięta również najmniejszą wartość `nice`, czyli najmniej uprzejmy proces. Ze względu na kompatybilność dopuszcza tylko wątki, których `nice` odbiega nie dalej niż 20 od tego minimum. Pozostałe procesy nie dostają kwantu, ale są wciąż dodawane do kolejki uruchomieniowej. Gdy są one wybrane, ich kwant jest ponownie obliczany i dodawane są bezpośrednio do następnej kolejki.

Procesy, których `nice` mieści się w tym przedziale, dostają kwant odwrotnie proporcjonalny do różnicy między ich `nice` a minimalnym `nice`. Dzięki temu, bardziej uprzejme procesy dostają mniejszy kwant.

Największym kwantem w ULE jest 140ms. Większe wartości są niepraktyczne. Najmniej uprzejme procesy otrzymają 14 razy większy kwant od najbardziej uprzejmych procesów, które dostały jakikolwiek kwant.

Procesy interaktywne otrzymują najmniejszy kwant. To umożliwia szybsze odkrycie procesu, który stał się nieinteraktywny.

### Szacowanie użycia procesora

Mechanizm szacowania użycia używany jest tylko w `ps`, `top` i podobnych narzędziach.

ULE pamięta ilość tyknięć w pewnym zmiennym przedziale. Zwiększa się on do 1s ponad pewien limit, a następnie przeskalowywany jest w dół. Stosunek czasu działania do czasu snu jest zachowany, a dodatkowo nowe odczyty bardziej na niego wpłyną.