# Ćwiczenia 12, grupa cz. 12-14, 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 |
| ----------------------| ----- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | x | x | | x | | | |
Adam Ciężkowski | | | | | | | |
Jacek Długopolski | x | x | | x | x | x | |
Jakub Fila | x | x | | | | | |
Krzysztof Grynkiewicz | x | x | | x | | | |
Michał Hetnar | | | | | | | |
Hubert Jabłoński | x | x | x | x | | | |
Antoni Kamiński | | | | | | | |
Paweł Karaś | X | X | X | X | | | |
Emil Kisielewicz | x | x | | x | x | | x |
Kacper Komenda | x | x | | x | x | | |
Filip Komorowski | x | x | x | x | x | x | |
Piotr Piesiak | x | x | x | ==x== | x | x | x |
Artur Krzyżyński | x | x | x | x | x | x | |
Patryk Mazur | X | X | | X | | | |
Szymon Mleczko | X | X | X | X | X | X | |
Michał Mróz | X |==X==| | X | X | X | |
Dominik Olejarz | x | x | ==x== | x | x | x | |
Magdalena Słonińska | X | X | | X | | | |
Oleś Kulczewicz | X | X | X | X | | | |
Adam Szeruda | X | X | X | X | X | X | X |
Kamil Tasarz | X | X | | X | | | |
Michał Zieliński |==X== | X | X | X | X | X | X |
:::

Tu można do-deklarować zadanie 9 z listy 11.:
- Kacper Komenda,
- Adam Szeruda
- Michał Zieliński
- Jacek Długopolski
- Artur Krzyżyński
- Daniel Boguszewski

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

## Zadanie 1
:::success
Autor: Michał Zieliński
:::

### Polecenie
W systemie twardego czasu rzeczywistego (ang. hard real-time system) chcemy wykonać cztery procesy, z okresami 50, 100, 200 i 250 ms. (liczba p) odpowiednio. Czasy obsługi tych procesów (liczba t) to 35, 20, 10 i x odpowiednio. Jaka jest maksymalna wartość x, dla której będzie to możliwe? Jak zmieni się ta odpowiedź, gdy będziemy mieli do czynienia z systemem miękkiego czasu rzeczywistego?

### Rozwiązanie

#### 1) twardy czas rzeczywisty
Mamy gwarancję wykonania zadania przed deadline'm, co najmniej raz w cyklu.
Maksymalna wartość x spełnia równanie:
$\frac{35}{50} + \frac{20}{100} + \frac{10}{200} + \frac{x}{250} = 1$
Czyli $x=\frac{25}{2}$.
#### 2) miękki czas rzeczywisty
Nie musimy zagwarantować conajmniej jednego wykonania w cyklu dla każdego procesu. W zależności od założeń naszego systemu, wartość x może wynieść nawet niewiele mniej niż 250.

## Zadanie 2
:::success
Autor: Michał Mróz

| Proces | Okres | Czas obsługi |
| ------ | ----- | ------------ |
| P1 | 50 ms | 25 ms |
| P2 | 75 ms | 30 ms |

a)

Nie jest to możliwe przy użyciu algorytmu RMS ponieważ w pewnym momęcie zostaje dochodzimy do deadlinu P2 a mamy ciągle do wykonania 5 ms pracy procesu P2

b)

Używając algorytmu EDF jesteśmy w stanie wykonywać te dwa procesy w systemie twardego czasu rzeczywistego

:::

## Zadanie 3
:::success
Autor: Dominik Olejarz

:::

## Zadanie 4
:::success
Autor: Piotr Piesiak
:::
* Algorytm działa w czasie stałym (niezależnie od ilości procesów)
* algorytm jest wywłaszczający
* priorytety 0-99 dla klasy czasu rzeczywistego i 100-140 dla pozostałych (niższa wartość - większy priorytet)
* Gotowe procesy trzymamy w kolejce list, w danej liście trzymamy wszystkie procesy o danym priorytecie
* priorytet tłumaczymy na kwant czasu
* Utrzymujemy kolejkę aktywnych i zużytych procesów
* Uruchamiamy proces pierwszy z kolejki aktywnych i po upływie jego kwantu czasu dokładamy go do kolejki zużytych
* gdy kolejka aktywna zrobi się pusta, zamieniamy rolami kolejkę procesów aktywnych i zużytych

## Zadanie 5
:::success
Autor: Adam Szeruda
:::

> Przeczytaj podrozdziały 5.4.1 — 5.4.5 artykułu [Aas, J. (2005). Understanding the Linux 2.6.8.1 CPU Scheduler](https://web.archive.org/web/20131231085709/http://joshaas.net/linux/linux_cpu_scheduler.pdf) i wyjaśnij, w jaki sposób w algorytmie “O(1)” wyliczany jest dla procesu dynamiczny priorytet i kwant czasu.

Każdy proces ma przypisane następujące wartości:

p->static_prio // Wartość `nice`
p->sleep_avg   // Różnica czasu oczekiwania i czasu działania

Wartość `p->sleep_avg` jest odpowiednio aktualizowana o czas oczekiwania lub o czas działania przy zmianie stanu procesu:

p->sleep_avg = MIN(p->sleep_avg + sleep_time, MAX_SLEEP_AVG);
p->sleep_avg = MAX(p->sleep_avg - running_time, 0);

Do wyliczenia priorytetu procesu używana jest funkcja `effective_prio()`. Do priorytetu wliczana jest wartość `p->static_prio` i (gdy nie jest to proces czasu rzeczywistego) odpowiednio przeskalowany `p->sleep_avg`.

#define MAX_BONUS 10

// Skaluje `p->sleep_avg` z przedziału [0, MAX_SLEEP_AVG] do [0, MAX_BONUS]
#define CURRENT_BONUS(p) ...

int effective_prio(process *p)
{
    if (p->realtime) return p->static_prio;
    
    int bonus = CURRENT_BONUS(p) - MAX_BONUS / 2; // Wartość z przedziału [-5, 5]
    int prio = p->static_prio - bonus;
    
    return MIN(MAX(prio, -20), 19);
}

Czas przydzielony procesowi to wartość `p->static_prio` przeskalowana do odpowiednich wartości. `TIMESLICE_GRANULARITY` to wartość kwantu czasu używana w algorytmie round-robin.

#define MIN_TIMESLICE ...
#define MAX_TIMESLICE ...
#define TIMESLICE_GRANULARITY ...

// Skaluje `p->static_prio` do przedziału [MIN_TIMESLICE, MAX_TIMESLICE],
// gdzie `p->static_prio = -20` odpowiada MAX_TIMESLICE
#define BASE_TIMESLICE(p) ...

int task_timeslice(process *p)
{
    return BASE_TIMESLICE(p);
}

## Zadanie 6
:::success
Autor: Szymon Mleczko
:::
CFS działa na bazie "nice value " z zakresu od -20 do 19.

Algorytm interpretuje wartość mniejszą jako wyższy prorytet.
Procesy są wykonywane w czasie "targeted latency"(tl) - okresie czasu w którym każdy z porocesów powinien się wykonać conajmniej raz. każdy z prtocesów otrzymuje tl/n zmodyfikowane o nice value.
Targeted Latency zależne jest od ilości procesów w romach odpowiednich progów.
Dla każdego procesu utrzymywany jest vruntime - czas którym proces działał równy (real time) x (1 + nice/10) - (dla nice = 0 vrun == relrun ).
Kolejność jest na podstawie najniższego vruntime z tym że niższa wartrość nice może wykonać się przed prosesem z wyższą wartością nice. Można także ustawić grupy priotrity schedule grups które wymuszą wykonanie w całości jednej grupy przed inną.
Jeśli pojawi się zadanie o niższym vruntime nastrępuje wywłaszczenie.

## Zadanie 7
:::success
Autor: Emil Kisielewicz
:::