---
# System prepended metadata

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

---

# Ć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
:::

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



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
:::

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

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


b) EDF (earliest deadline first) - im wcześniejszy deadline, tym większy priorytet
![](https://i.imgur.com/mFEjfdE.png)




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

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


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

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

-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
:::

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

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

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

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ć
:::

