---
# System prepended metadata

title: 'Ćwiczenia 12, grupa cz. 12-14, 2. czerwca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ć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) 
![](https://i.imgur.com/bJIiBF6.png)

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) 
![](https://i.imgur.com/dYFwa7g.png)

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


:::

## Zadanie 3
:::success
Autor: Dominik Olejarz
![](https://i.imgur.com/CaEDVpe.png)
![](https://i.imgur.com/EmJ60Js.png)



:::

## Zadanie 4
:::success
Autor: Piotr Piesiak
:::
![](https://i.imgur.com/cjbdrBN.png)
* 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:

```c
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:
```c
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`.

```c
#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.

```c
#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
:::
![](https://i.imgur.com/5LNR51g.jpg)
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	
:::

![](https://i.imgur.com/O3AGGFo.png)

![](https://i.imgur.com/eshZCxt.png)

![](https://i.imgur.com/vuDyh0e.png)

![](https://i.imgur.com/WmwOJTI.png)

![](https://i.imgur.com/0HjQMLk.png)

![](https://i.imgur.com/LTKRFQh.png)





