Ćwiczenia 13, grupa cz. 16-18, 6 czerwca 2024

###### tags: `SYK24` `ć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 | 8 | 9 |
| ----------------------:| ----| ---| ---| ---| ---| ---| ---| ---| ---|
Marcin Banak | X | X | X | X | X | X | X | X | ==X== |
Bartosz Borecki | X | X | X | | X | | | | |
Karol Burczyk | X | X | X | X | X | X | X | | |
Yelyzaveta Ilman | X | X | X | X | X | ==X== | X | X | X |
Antoni Kamiński | X | X | X | | X | X | X | | X |
Jan Kamyk | | | | | | | | | |
Bartosz Kruszewski | X | X | X | X | X | X | ==X== | X | X |
Hanna Laszkiewicz | ==X== | X | X | X | X | X | X | X | X|
Kaja Matuszewska | | | | | | | | | |
Dominik Muc | | | | | | | | | |
Krzysztof Ostrowski | X | X |==X==| X | X | X | | X | X |
Franciszek Przeliorz | X | X | X | X | ==X== | X | | X | X |
Yaryna Rachkevych | X | X | X | | | X | | | |
Mikołaj Kalitka | X | X | X | X | X | X | X | ==X== | X |
Piotr Thamm | X | ==X== | X | X | | | | | |
Taras Tsehenko | X | X | X | | X | X | X | | |
Wiktor Małek | | | | | | | | | |
Piotr Warząchowski | X | X | X | | X | X | X | | |
Piotr Salamon | X | X | X | X | X | X | X | | |
:::

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

## Zadanie 1
:::success
Autor: Hanna Laszkiewicz




:::

## Zadanie 2
:::success
Autor: Piotr Thamm


### Wykorzystanie procesora (**ang. CPU utilization**)
**Czas, w którym procesor jest zajęty przetwarzaniem zadań.**
Chcemy, żeby wykorzystanie procesora było jak największe.

***Optymalizacja innych miar:*** *Optymalizacja wykorzystania CPU może nie poprawić innych miar. Prxzykładowo, wysokie wykorzystanie CPU może prowadzić do zwiększenia czasu oczekiwania procesów w kolejce, co źle wpływa na czas oczekiwania i czas odpowiedzi.*

### Przepustowość (**ang. Throughput**)
**Liczba prosesów, które kończą swoje wykonywanie w jednostce czasu.**
Chcemy, żeby przepustowość byla jak największa.

***Optymalizacja innych miar:*** *Optymalizacja przepustowości może nie poprawić innych miar. Przykładowo, skupienie się wyłącznie na zwiększeniu liczby ukończonych procesów może prowadzić do wzrostu czasu oczekiwania dla poszczególnych procesów. Dzieje się tak, ponieważ algorytmu optymalizujące przepustowość priorytetyzują krótkie procesy, ponieważ mogą one szybko zakończyć się, zwiększając liczbę zakończonych procesów w krótkim czasie.*

### Czas cyklu przetwarzania (**ang. Turnaround time**)
**Czas od momentu zgłoszenia procesu do momentu jego zakończenia.**
Inaczej jest to czas wykonania jakiegoś określonego procesu
Chcemy, ten czas zminimalizować.

***Optymalizacja innych miar:*** *Optymalizacja czasu realizacji może wpływać źle na czasy odpowiedzi i oczekiwania oraz na przepustowość*

**Przykład**
Algorytm First-Come, First-Served (FCFS) - kolejka:

Procesy są wykonywane w kolejności przybycia, co może minimalizować czas realizacji długich procesów.
Nie jest to korzystne dla czasu odpowiedzi, czasu oczekiwania i przepustowości. Krótsze procesy mogą czekać bardzo długo, a ogólna liczba zakończonych procesów może być niska.

### Czas oczekiwania (**ang. Waiting time**)
**Czas, jaki proces spędza w kolejce procesów gotowych oczekując na przydzielenie procesora.**
Chcemy, żeby ten czas był jak najkrótszy.

***Optymalizacja innych miar:*** *Optymalizacja czasu oczekiwania polega na minimalizacji okresu, w którym procesy spędzają czas w kolejce oczekując na przydzielenie procesora, może to źle wpłwać na czas odpowiedzi.*

**Przykład:**
Algorytm Shortest Job First (SJF):
Krótsze procesy są priorytetyzowane, co może zmniejszać średni czas oczekiwania, ponieważ krótkie procesy szybko kończą swoje wykonywanie.
Procesy o dłuższym czasie trwania mogą być stale odkładane, co oznacza, że mogą mieć wydłużony czas oczekiwania na rozpoczęcie, co w efekcie zwiększa czas odpowiedzi.

### Czas odpowiedzi (**ang. Response Time**)
**Czas od momentu przekazania inputu do momentu gdy proces zacznie na niego reagować.**
Przykładowo, czas w jakim na ekranie wypisze nam się litera po naciśnięciu klawisza.
Chcemy ten czas zminimalizować.

:::

## Zadanie 3
:::success
Autor: Krzysztof Ostrowski
:::


| Proces | $P_1$ | $P_2$ | $P_3$ | $P_4$ | $P_5$ |
| -------- | ----- | ----- | ----- | ----- | ----- |
| Czas | 2 | 1 | 8 | 4 | 5 |
| Piorytet | 2 | 1 | 4 | 2 | 3 |

**FCFS (First Come First Served)**
> Diagram Gantta
> 
> Czasy przetworzenia:
>
> - P1: $2$
> - P2: $3$
> - P3: $11$
> - P4: $15$
> - P5: $20$
>
> Czasy oczekiwania:
>
> - P1: $0$
> - P2: $2$
> - P3: $3$
> - P4: $11$
> - P5: $15$
> - Średni: $\frac{0 + 2 + 3 + 11 + 15}{5} = 6.2$

**SJF (Shortest Job First)**
> Diagram Gantta
> 
> Czasy przetworzenia:
>
> - P1: $3$
> - P2: $1$
> - P3: $20$
> - P4: $7$
> - P5: $12$
>
> Czasy oczekiwania:
>
> - P1: $1$
> - P2: $0$
> - P3: $12$
> - P4: $3$
> - P5: $7$
> - Średni: $\frac{1 + 0 + 12 + 3 + 7}{5} = 4.6$

**Priorytetowy bez wywłaszczeń**
> Diagram Gantta
> 
> Czasy przetworzenia:
>
> - P1: $15$
> - P2: $20$
> - P3: $8$
> - P4: $19$
> - P5: $13$
>
> Czasy oczekiwania:
>
> - P1: $13$
> - P2: $19$
> - P3: $0$
> - P4: $15$
> - P5: $8$
> - Średni: $\frac{13 + 19 + 0 + 15 + 8}{5} = 11$

**Karuzelowy Q=2**
> Diagram Gantta
> 
> Czasy przetworzenia:
>
> - P1: $2$
> - P2: $3$
> - P3: $20$
> - P4: $13$
> - P5: $18$
>
> Czasy oczekiwania:
>
> - P1: $0$
> - P2: $2$
> - P3: $3 + 4 + 4 + 1 = 12$
> - P4: $5 + 4 = 9$
> - P5: $7 + 4 + 2 = 13$
> - Średni: $\frac{0 + 2 + 12 + 9 + 13}{5} = 7.2$

## Zadanie 4
:::success
Autor: Piotr Salamon




:::

## Zadanie 5
:::success
Autor: Franciszek Przeliorz
#### Algorytm

1. Przydzielenie $Q_0$ czasu
2. Jeżeli proces przerwał działanie szybciej: $P < Q_0$ to następnym razem przydzielone mu zostanie $Q_0 - P$ czasu.
4. Jeżeli $P = Q_0$ to dalej dostanie $Q_0$ czasu

#### Przykład

$Q_0 = 3$

P1:

- całkowity czas: $6$
- oczekiwanie: $2$

P2:

- całkowity czas: $9$
- bez oczekiwania


#### Podsumowanie

Jak widać na przykładzie, mocno faworyzowane są procesy bez oczekiwania (np. oczekiwanie na operacje wejścia/wyjścia).
:::

## Zadanie 6
:::success
Autor: Yelyzaveta Ilman

:::
## Zadanie 7
:::success
Autor: Bartosz Kruszewski
:::

#### Podział procesów

Procesy mają różną "ważność" dla działania komputera. Możemy je podzielić na grupy z wagą malejąco:

1. Real-time: wymagające ciągłej synchronizacji
2. System: - niezbędne do działania systemu
3. Interactive: - interakcje z użytkownikiem
4. Batch: - mogące działać w tle

#### Algorytm Multilevel feedback queues

Procesów przypisywane są do odpowiedniej kolejki w zależności od tego do jakiej należą grupy. Zauważmy, że im jest większy priorytet grupy tym procesy wymagają większej interaktywności. Algorytm promuje procesy bardziej interaktywne.

#### Reguła promocji i degradacji

- Jeśli proces zużywa zbyt dużo czasu procesora, zostanie przeniesiony do kolejki o niższym priorytecie.
- Jeśli proces jest interaktywny, zostanie przeniesiony do kolejki o wyższym priorytecie.
- Jeśli proces czeka zbyt długo, zostanie przeniesiony do kolejki o wyższym priorytecie.

## Zadanie 8
:::success
Autor: Mikołaj Kalitka
:::
#### Algorytm

while (nie ma procesu do wykonania):
    for proces in queue:
        Wybierz proces o najwyższym priorytecie, który jest załadowany do pamieci
    if (nie ma takiego procesu):
        Bezczynność maszyny
Usuń wybrany proces z kolejki uruchomień
Przełącz kontekst na wybrany proces i wznów jego wykonanie

Jest to algorytm Karuzelowy z wielopoziomowymi kolejkami, oraz priorytetami.

#### Własności

- Każdy proces w systemie Unix ma przypisany priorytet, który może się zmieniać w trakcie działania procesu.
- Procesy mają priorytety w zakresie od 0 do 127.
- Wybierany jest proces z kolejki o najwyszym priorytecie (najniszej liczbie)
- Jeżeli priorytety są równe, to wybierany jest ten, który dłużej był "ready"
- Kolejki jądra systemu są podzielone w zależności od ważności dla działania komputera
- Są dwie grupy kolejek: kolejki jądra systemu, oraz kolejki użytkownika. Priorytety systemowe mieszczą się w zakresie od 0 do 39. Priorytety użytkownika są w zakresie od 40 do 127.
- Priorytety w kolejkach użytkownika są ustalane na podstawie przypisania przez użytkownika, oraz poprzez sprawdzanie czasu dostępu do procesora
- Superuser może dodatkowo zapalić wartość nice (od -20 do 19), która jest dodawana do bazowego priorytetu procesu. Niższe wartości nice oznaczają wyższy priorytet, a wyższe wartości nice oznaczają niższy priorytet.

## Zadanie 9
:::success
Autor: Marcin Banak
:::

Fair Share Scheduler to algorytm, który stara się zapewnić, aby zasoby systemowe były podzielone sprawiedliwie między użytkowników lub grupy użytkowników, zgodnie z ich udziałem w systemie. Algorytm ten bierze pod uwagę nie tylko indywidualne zadania, ale także całkowity przydział zasobów dla każdego użytkownika lub grupy.

### Podstawowe założenia
- Udział użytkowników/grup: Każdemu użytkownikowi lub grupie przypisywany jest udział w systemie. $(Koszt)$
- Historyczne wykorzystanie zasobów: Algorytm monitoruje, ile zasobów każdy użytkownik lub grupa zużyła w przeszłości. $(Ile już zapłaciliśmy)$
- Priorytetyzacja na podstawie udziału i historii: Zadania użytkowników/grup, które dotychczas zużywały mniej zasobów niż im przysługuje, są priorytetyzowane.

### Kroki algorytmu
1. Inicjalizacja: Na początku każdemu użytkownikowi lub grupie przypisany jest jego udział w systemie. Początkowa wartość zużycia zasobów dla każdego użytkownika lub grupy jest ustawiona na zero.

2. Kolejka zadań: Zadania są dodawane do kolejki zgodnie z normalnymi zasadami systemu operacyjnego (np. FIFO, priorytetowa).

3. Monitorowanie zasobów: Algorytm monitoruje, ile zasobów (np. czasu procesora) każdy użytkownik lub grupa zużywa w czasie.

4. Obliczanie priorytetów:

- Dla każdego użytkownika lub grupy obliczana jest wartość "fair share", która jest różnicą między przypisanym udziałem a rzeczywistym zużyciem zasobów.
- Zadania użytkowników/grup z większym niedoborem zasobów (większą wartością "fair share") otrzymują wyższy priorytet.

5. Wybór zadania: Zadanie z najwyższym priorytetem (czyli największą wartością "fair share") jest wybierane do wykonania.

6. Wykonywanie zadania: Zadanie jest wykonywane przez ustalony czas kwantu. Po zakończeniu kwantu, algorytm aktualizuje zużycie zasobów przez odpowiedniego użytkownika lub grupę.

7. Aktualizacja: Po każdym cyklu algorytm aktualizuje dane dotyczące zużycia zasobów przez użytkowników/grupy oraz odpowiednio modyfikuje wartości "fair share".

8. Powrót do kroku 4: Algorytm powtarza kroki od 4 do 7, aż do zakończenia wszystkich zadań w systemie.

### Przykład działania algorytmu Fair Share Scheduler

Załóżmy, że kwant zajmuje $10$ jednostek czasu.
Załóżmy, że mamy trzech użytkowników $U1$, $U2$ i $U3$ z następującymi udziałami w systemie:
- U1: 50% zasobów
- U2: 30% zasobów
- U3: 20% zasobów

Początkowo wszyscy użytkownicy mają zero zużycia zasobów.

U1: 50%, U2: 30%, U3: 20%

Zużycie początkowe:
U1: 0%, U2: 0%, U3: 0%

Fair Share:
U1: 50% - 0% = 50%
U2: 30% - 0% = 30%
U3: 20% - 0% = 20%

Zadanie użytkownika $U1$ ma najwyższy Fair Share (50%), więc jest wybierane jako pierwsze.

U1: 10%, U2: 0%, U3: 0%

Nowe wartości Fair Share:
U1: 50% - 10% = 40%
U2: 30% - 0% = 30%
U3: 20% - 0% = 20%

Zadanie użytkownika $U1$ nadal ma najwyższy Fair Share (40%), więc jest ponownie wybierane.

U1: 20%, U2: 0%, U3: 0%

Nowe wartości Fair Share:
U1: 50% - 20% = 30%
U2: 30% - 0% = 30%
U3: 20% - 0% = 20%

Zadania $U1$ i $U2$ mają teraz równą wartość Fair Share (30%). Przyjmujemy, że system wybiera w takiej sytuacji użytkownika z najmniejszym zużyciem zasobów, więc zadanie użytkownika $U2$ jest teraz wybierane.

U1: 20%, U2: 10%, U3: 0%

Nowe wartości Fair Share:
U1: 50% - 20% = 30%
U2: 30% - 10% = 20%
U3: 20% - 0% = 20%

Zadanie użytkownika $U1$ ma teraz najwyższą wartość Fair Share (30%), więc jest ponownie wybierane.

U1: 30%, U2: 10%, U3: 0%

Nowe wartości Fair Share:
U1: 50% - 30% = 20%
U2: 30% - 10% = 20%
U3: 20% - 0% = 20%

Wszyscy użytkownicy mają teraz równą wartość Fair Share (20%). Przyjmujemy, że system wybiera użytkownika z najmniejszym zużyciem zasobów, więc teraz wybierane jest zadanie użytkownika $U3$.

U1: 30%, U2: 10%, U3: 10%

Nowe wartości Fair Share:
U1: 50% - 30% = 20%
U2: 30% - 10% = 20%
U3: 20% - 10% = 10%

#### Kontynuacja
Algorytm będzie kontynuował wybór i wykonywanie zadań w ten sposób, priorytetyzując użytkowników z największym niedoborem zasobów zgodnie z ich przydziałem.

### Podsumowanie
Fair Share Scheduler zapewnia, że zasoby są dzielone sprawiedliwie między użytkowników lub grupy użytkowników na podstawie ich przydziału i historycznego zużycia zasobów. W naszym przykładzie, mimo że $U1$ miał początkowo największy udział, algorytm sprawiedliwie rozdzielił czas procesora, gdy inni użytkownicy zaczęli zużywać swoje przydziały.