# Ćwiczenia 12, grupa śr. 17-19, 1. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | |
Kamila Brzozowska | ==X== | X | X | X | X | | |
Adam Ciężkowski | X | X | | X | X | X | |
Natalia Czerep | X | X | | ==X== | X | X | |
Jan Dalecki | X | X | X | X | X | X | |
Marko Golovko | X | X | X | X | X | | |
Adam Górkiewicz | | | | | | | |
Piotr Gunia | X | X | | X | X | | |
Krzysztof Jadłowski | | | | | | | |
Magdalena Jarecka | X | X | | X | ==X== | | X | |
Mikołaj Jaszcza | X | X | | X | | | |
Monika Jędrzejkowska | | | | | | | |
Michał Kierul | X | X | X | | | X | |
Damian Lukas | | | | | | | |
Karol Ochman-Milarski | | | | | | | |
Piotr Piesiak | | | | | | | |
Damian Ratajski | | | | | | | |
Aleksandra Rozkrut | X | X | | X | X | | |
Marcin Sarnecki | X | X | | X | | | |
Maria Szlasa | X | X | | X | X | | |
Mateusz Burdyna | X | X |==X==| | | X | |
Magdalena Słonińska | | | | | | | |
Nikola Wrona | X | X | X | X | X | | |
Marcin Wróbel | X |==X==| X | X | X | X | |
:::

**Tutaj można dodeklarować zad. 9. z listy 11.:**
*
*
*

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

## Zadanie 1
:::success
Autor: Kamila Brzozowska
:::



|Proces|Okres|Czas obsługi|
|------|-----|------------|
| P1 |50ms | 35ms |
| P2 |100ms| 20ms |
| P3 |200ms| 10ms |
| P4 |250ms| x ms |

### System twardego czasu rzeczywistego
35/50 + 20/100 + 10/200 + x/250 = 1
x = 12.5


### System miękkiego czasu rzeczywistego
Procesy nie muszą się wykonywać dokładnie w swoim okresie. Przykładowo w czasie oglądania filmu nie jest problemem wyświetlenie jednej klatki z opóźnieniem lub nie wyświetlenie jej wcale. Wtedy np. gdyby proces P1 na przedziale 250 ms raz się nie wykonywał to proces P4 mógłby być obsługiwany przez 60ms.

## Zadanie 2
:::success
Autor: Marcin Wróbel
:::

### RMS (rate-monotonic scheduling)
W **RMS** im krótszy okres tym większy priorytet

| | P1 | P2 |
| ---------------------- | --- | --- |
| czas obsługi \(**t**\) | 25 | 30 |
| okres \(**p**\) | 50 | 75 |


Na początku wykonuje się proces **P1**, po 25 jednostkach czasu przestanie się wykonywać. Następnie wykonuje się proces **P2** i w 50 jednostce czasu proces zostaje wywłaszczony, ponieważ proces **P1** ma krótszy okres i może rozpocząć się wykonywać. Podczas wywłaszczenia procesowi **P2** zostało 5 jednostek czasu. W 75 jednostce czasu proces **P1** przestanie się wykonywać, jest to deadline procesu **P2** i zostało mu 5 jednostek czasu pracy. Stąd niemożliwe jest zaplanowanie pracy procesora z wykorzystaniem **rate-monotonic scheduling** dla powyższego planu.

### EDF (earliest deadline first)
W **EDF** im wcześniejszy deadline tym większy priorytet
Udało się zaplanować pracę procesora z wykorzystaniem **earliest deadline first**. Najmniejsza wspólna wielokrotność 50 i 75 to 150, w kolejnych okresach o długości 150 układ pracy procesów będzie taki sam.

## Zadanie 3
:::success
Autor: Mateusz Burdyna
:::



### a)

Przejście do następnej epoki powinno się odbywać gdy każdy proces w bieżącej epoce został obsłużony wyliczonym czasem procesora.

### b)

Funkcja goodness jest $O(1)$, w każdej epoce system musi wyliczyć dla każdego z $n$ procesów wartość funkcji goodness, a następnie w malejącej kolejności dawać im wyliczony czas procesora. W każdej epoce dany proces otrzymuje przynajmniej połowe pozostałego potrzebnego mu czasu:
`p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice)`

Niech $t$ będzie ilością 'ticków' procesora potrzebnego dla procesu potrzebującego najwięcej procesora.

Wtedy liczba epok w których wykonają się wszystkie zlecone procesy jest $O(log(t))$.

W każdej z tych epok wywołujemy dla każdego procesu funkcje goodness, a następnie sortujemy liczbe procesów.
Dlatego w każdej epoce potrzebujemy $O(n)$ czasu (zakładam że wyniki funkcji goodness są z ograniczonego uniwersum, więc da się je posortować w czasie $O(n)$, np bucket sortem)

Więc aby zakończyć obsługe wszystkich zleconych procesów potrzebujemy $O(nlog(t))$ czasu.

### c)

Głodzenie wystąpi wtedy gdy wyliczony kwant czasu w epoce wyniesie $0$.

Taka możliwość może zajść gdy
`NICE_TO_TICKS(p->nice) + p->counter` $\leq 0$ i `p->counter` $> 0$, wtedy $q \leq 0$

### d)

Faworyzowane procesy to:
- Real time
- Procesy wymagające dużo czasu procesora
- Procesy z wysokim priorytetem

## Zadanie 4
:::success
Autor: Natalia Czerep
:::


- wywłaszczający
- ustawia procesy bazując na priorytetach
- 2 rodzaje priorytetu: real-time (0-99) i nice value (100-140), one mapują się na globalny priorytet
- mniejsza wartośc priorytetu (numerycznie) -> wyższy priorytet
- są czasy dla tasków (time slice),
- task może byc wykonywany jeśli został mu czas (time slice)
- jeśli skończył się czas to task jest wygasły, idzie do expired dostaje nowy priorytet
- kernel ma runqueue gdzie ma listę tasków runnable
- każda runqueue jest podzielona na active i expired
- active ma taski które mają jeszcze czas
- expired ma tylko wygasłe
- oba są indeksowane priorytetami
- scheduler wybiera task z active z max prority
- jak wszystkie są już wygasłe to expired zamieniamy z active

Kolejki active i expired są wielopoziomowe, są one indeksowane priorytetami.
Przedstawia to obrazek:


## Zadanie 5
:::success
Autor: Magdalena Jarecka
:::

Wszystkie taki mają priorytet statyczny nice od -20 do 19. Im większa liczba tym niższy priorytet.

Scheduler Linux 2.6.8.1 faworyzuje zadania związane z I/O i karze zadania związane z procesorem, dodając lub odejmując od statycznego priorytetu zadania. Dostosowany priorytet nazywany jest priorytetem dynamicznym zadania i jest dostępny poprzez zmienną priorytetu zadania.
Jeśli zadanie jest interaktywne, jego priorytet jest zwiększany. Maksymalny bonus do priorytetu wynosi 5.

Dynamiczne premie i kary za priorytet są oparte na heurystyce interaktywności. Ta heurystyka jest implementowana przez monitorowanie, ile czasu zadania spędzają na uśpieniu (przypuszczalnie zablokowane na I/O), w przeciwieństwie do działania.

Kiedy zadanie zostaje wznowione, jego całkowity czas snu jest dodawany do jego zmiennej sleep_avg (chociaż sleep_avg zadania nie może przekroczyć MAX_SLEEP_AVG)

Kiedy zadanie zwalnia procesor (z własnej woli lub nie) czas trwania bieżącego zadania jest odejmowany od jego sleep_avg. Im wyższa wartość sleep_avg zadania, tym wyższy będzie jego priorytet dynamiczny. Ta heurystyka jest dość dokładna, ponieważ śledzi zarówno ilość czasu spędzonego na spaniu, jak i wykonywaniu.

Timeslice jest obliczany przez proste przeskalowanie statycznego priorytetu zadania do możliwego zakresu przedziału czasu i upewnienie się, że określony minimalny i maksymalny przedział czasu jest wymuszony. Im wyższy priorytet statyczny zadania tym większy timeslice otrzymuje. Funkcja task_timeslice() jest po prostu wywołaniem makra BASE_TIMESLICE, które jest zdefiniowane jako:

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

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: Michał Kierul
:::

Algorytm CFS (Completely Fair Sheduler):

Kwant czasu jest obliczany dla każdego procesu na podstawie "nice value" (od -20 do 19). Algorytm oblicza tzw. "target latency" - czas, w którym każdy aktywny proces powinien wykonać jedną fazę co najmniej jeden raz (epoka). Wartość ta jest uaktualniana gdy liczba aktywnych procesów się zmienia (uaktywnienie zadania może spowodać wydłużenie tego czasu).
Algorytm przydziela procesor zadaniu o najniższym czasie wirtualnym, który jest równy długości czasowi wykonania zmodyfikowanym przez czynnik zależny od wartości "nice" (priorytetu). Algorytm jest wywłaszczeniowy - jeżeli w międzyczasie do kolejki dojdzie proces o niższym czasie wirtualnym, procesor zostanie przekazany temu zadaniu.

## Zadanie 7
::: success
Autor: Magdalena Jarecka
:::
ULE ma stały czas wykonania niezależnie od liczby wątków
Oprócz tych podstawowych celów związanych z wydajnością, starannie identyfikuje również zadania interaktywne i zapewnia im możliwie najmniejsze opóźnienia.
Podstawowe składniki planowania obejmują kilka kolejek, dwa algorytmy równoważenia obciążenia procesora, wskaźnik interaktywności, estymator wykorzystania procesora, kalkulator wycinka i kalkulator priorytetów.

Kolejki nazywane są kseq.
Każdy kseq zawiera trzy tablice kolejek uruchamiania, które są indeksowane według priorytetów segmentowych. Do implementacji klas planowania przerwań, czasu rzeczywistego i współdzielenia czasu używane są dwie kolejki uruchomieniowe. Ostatni jest dla klasy bezczynności. Oprócz tych kolejek kseq śledzi również statystyki obciążenia i bieżący przedział “nice”.

Ponieważ ULE jest shedulerem sterowanym zdarzeniami, nie ma okresowego timera, który dostosowuje priorytet wątków, aby zapobiec głodzeniu.

Wątki są wybierane z bieżącej kolejki w kolejności priorytetu, dopóki bieżąca kolejka nie będzie pusta. W tym czasie kolejna kolejka i bieżąca są przełączane. Gwarantuje to, że każdy wątek będzie korzystał ze swojego wycinka raz na dwa przełączniki kolejki, niezależnie od priorytetu.

Wątek jest przypisywany do kolejki do czasu uśpienia lub na czas trwania wycinka. Priorytet podstawowy, rozmiar wycinka i wynik interaktywności są obliczane ponownie za każdym razem, gdy czas wycinka się skończy. Wątek jest przypisywany do bieżącej kolejki, jeśli jest interaktywny, lub do następnej kolejki w przeciwnym razie.

Mechanizm punktacji interaktywności
|
v

Scheduler używa wyniku interaktywności do określenia, czy wątek powinien zostać przypisany do bieżącej kolejki, gdy stanie się on możliwy do uruchomienia. Próg wyniku interaktywności został ustawiony, a wątki, które uzyskały wynik poniżej tego progu, są oznaczane jako interaktywne.

Priorytet jest używany w ULE do wskazania kolejności, w jakiej powinny być wybierane wątki w kolejce uruchamiania. Tylko wątki współdzielenia czasu mają obliczone priorytety; reszta jest przypisywana statycznie.

ULE wykorzystuje wynik interaktywności do określenia priorytetu. Następnie wartość nice jest dodawana do priorytetu, co może faktycznie obniżyć priorytet w przypadku ujemnych wartości nice.

ULE śledzi liczbę wątków w kseq z każdą wartością nice. Zachowuje również obecną minimalną wartość nice. Aby być kompatybilnym z harmonogramem 4BSD, ULE pozwala tylko wątkom, które mają nice w zakresie od 20 do wątku z najmniejszym nice, na uzyskanie wycinków. Pozostałe wątki otrzymują wycinek zerowy i nadal są wstawiane do kolejki uruchamiania. Po wybraniu ich do uruchomienia, ich kawałek jest ponownie oceniany, a następnie umieszczany bezpośrednio w następnej kolejce.
Wątki, które znajdują się w oknie nice, otrzymują wartość wycinka, która jest odwrotnie proporcjonalna do różnicy między ich wartością nice a najmniejszą wartością aktualnie zarejestrowaną w kseq.