---
# System prepended metadata

title: 'Ćwiczenia 11, grupa śr. 10-12, 17 maja 2023'
tags: [pwit, ćwiczenia, SYK23]

---

# Ćwiczenia 11, grupa śr. 10-12, 17 maja 2023

###### tags: `SYK23` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk            |       |     |     |     |     |     |     |     |     | 
Mikołaj Dworszczak       |       |     |     |     |     |     |     |     |     |
Kacper Jóźwiak           |   X   | X   | X   |  X  | X   | X   |   X |     |     |
Dominik Kiełbowicz       |       |     |     |     |     |     |     |     |     |
Michał Kolasa            |       |     |     |     |     |     |     |     |     |
Konrad Kowalczyk         |   X   |  X  |  X  |  X  |  X  |  X  |  X  |     |     |
Oskar Kropielnicki       |   X   |  X  |  X  |  X  |     |  X  |  X  |     |     |
Anna Krysta              |   X   |  X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  |
Jakub Krzyżowski         |   X   |  X  |  X  |  X  |     |  X  |  X  |     |     |
Oskar Kubkowski          |   X   |  X  | ==X==|  X   |     | X |  X  |     |     |
Mateusz Mazur            |   X   |  X  |  X  |  X  |  X  |  X  |  X  |     |     |
Barbara Moczulska        |   X   |  X  |  X  |  X  |     |  X  |  X  |     |     |
Kacper Sojda             |   X    |  X   |  X   |  X   |  X   |  X   |  X   |     |     |
Marta Strzelec           |    X  | X   |  X  | X   | X   |  X  |  X  |     |     |
Mikołaj Swoboda          |    X  |  X  |  X  |  X  |    | X   | X   |     |     |
Filip Szczepański        |   ==X==    |  X   |  X   |  X   |  X   |  X   |   X  |     |     |
Julian Włodarek          |   X    |  X   |  X   |  X   |  ==X==   |  X   |   X  |     |     |
Beata Łakoma             |   x    |  x   |  x   |  x   |  x   |  x   |   x  |     |     |
Michał Łukasik           |   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:	Filip Szczepański	
:::
![](https://hackmd.io/_uploads/BkYdAZzrn.png)
![](https://hackmd.io/_uploads/SkbRR-MB3.png)

**W planowaniu niewywłaszczającym** proces zmienia stan pomiędzy waiting, running, terminated. Oznacza to, że gdy procesowi zostanie przydzielony procesor, będzie on wykorzystywany przez proces dopuki ten nie zmieni stanu na waiting albo na terminated.

**W planowaniu wywłaszczającym** proces może też zmieniać stan z waiting na ready oraz z running na ready. Podczas tego scheduler podejmuje decyzje.

**proces ograniczony przez dostęp do procesora** - czas wykonania procesu (uzyskania stanu terminated) zależy głownie od czasu procesora, jaki ten proces potrzebuje.

**proces ograniczony przez wejście-wyjście** - czas wykonania procesu zależy głownie od interakcji z urządzeniami I/O.

**proces interaktywny** - proces często wchodzący w interakcję z użytkownikiem. Opóźnienie w działaniu programu powinno być niskie.

**program wsadowy** - mało interakcji z użytkownikiem. Opóźnienie zależy od wykonywanej funckji.

**Po co?**
Planowanie wywłaszczające stosuje się dla stworzenia iluzji działania wielu programów jednocześnie.

## Zadanie 2
:::success
Autor:	Barbara Moczulska	
:::

![](https://hackmd.io/_uploads/SyWyyfMH2.png)
![](https://hackmd.io/_uploads/Bkte1MzBn.png)

- **wykorzystanie CPU** - im dłużej procesor jest wykorzystywany tym lepiej - Chcemy aby procesor był zajęty przez cały czas. Chcemy aby procesor był wykorzystywany również w cyklach IO. Wszystkie przerwy w użyciu trzeba zminimalizować

- **przepustowość systemu** - Chcemy aby jak najwięcej procesów się wykonało w jednostce czasu

- **czas realizacji jednego procesu** - czas od rozpoczęcia pojedyńczego procesu do końca jego wykonania chcemy aby był jak najkrótszy.

- **czas oczekiwania** - zminimalizowanie czasu w którym procesy czekają w kolejce ready. 

- **czas odpowiedzi** - zminimalizowanie czasu odpowiedzi procesu, chcemy mieć wrażenie interaktywności, że proces natychmiast reaguje na polecania.


## Zadanie 3
:::success
Autor:	Oskar Kubkowski	
:::
![](https://hackmd.io/_uploads/BJMhZJ642.png)
![](https://hackmd.io/_uploads/SJF3ZkTN3.png)

### First Come First Served (FCFS)
![](https://hackmd.io/_uploads/B12FVlTVn.png)

Czas cyklu przetworzenia (Turnaround time)
$P_{1} = 2$
$P_{2} = 3$
$P_{3} = 11$
$P_{4} = 15$
$P_{5} = 20$

Czas oczekiwania dla każdego procesu (Waiting time)
$P_{1} = 0$
$P_{2} = 2$
$P_{3} = 3$
$P_{4} = 11$
$P_{5} = 15$

Średni czas oczekiwania
$(0+2+3+11+15) / 5 = 6.2$

### Shortest Job First (SJF)
![](https://hackmd.io/_uploads/SkIMNx6N2.png)

Czas cyklu przetworzenia (Turnaround time)
$P_{1} = 3$
$P_{2} = 1$
$P_{3} = 20$
$P_{4} = 7$
$P_{5} = 12$

Czas oczekiwania dla każdego procesu (Waiting time)
$P_{1} = 1$
$P_{2} = 0$
$P_{3} = 12$
$P_{4} = 3$
$P_{5} = 7$

Średni czas oczekiwania
$(1+0+12+3+7) / 5 = 4.6$

### Priorytetowy bez wywłaszczeń
![](https://hackmd.io/_uploads/Hyh9fxTEh.png)

Czas cyklu przetworzenia (Turnaround time)
$P_{1} = 15$
$P_{2} = 20$
$P_{3} = 8$
$P_{4} = 19$
$P_{5} = 13$

Czas oczekiwania dla każdego procesu (Waiting time)
$P_{1} = 13$
$P_{2} = 19$
$P_{3} = 0$
$P_{4} = 15$
$P_{5} = 8$

Średni czas oczekiwania
$(13+19+0+15+8)/5 = 11$

### Round Robin
![](https://hackmd.io/_uploads/SkmBExT4h.png)

Czas cyklu przetworzenia (Turnaround time):
$P_{1} = 2$
$P_{2} = 3$
$P_{3} = 20$
$P_{4} = 13$
$P_{5} = 18$

Czas oczekiwania dla każdego procesu (Waiting time):
$P_{1} = 0$
$P_{2} = 2$
$P_{3} = 3+4+4+1=12$
$P_{4} = 5+4=9$
$P_{5} = 7+4+2=13$

Średni czas oczekiwania:
$(0+2+12+9+13) / 5 = 7.2$

## Zadanie 4
:::success
Autor:	Michał Łukasik	
:::
![](https://hackmd.io/_uploads/H1R9A-frn.png)

1.
Dla każdego priorytetu możemy stworzyć oddzielną kolejkę round robin. Procesy wykonują się zgodnie z kolejnością priorytetów, natomiast jeśli istnieje kilka procesów o jednakowym priorytecie, to używamy dla nich schematu round robin, każdy maksymalnie przez z góry określony czas (kwant czasu).

2.
a) Q = inf
nie ma żadnych korzyści z Round Robin, jest to FCFS
efektywność około T / (T+S)
słaba interaktywność

b) Q > T
większość procesów wykona się bez przerwań, prawie FCFS
efektywność około T / (T+S)
słaba interaktywność

c) S < Q < T
efektywność to około Q / (Q+S), co jest dobrym wynikiem patrząc na pozostałe opcje

d) Q = S
przez połowę czasu zmieniamy kontekst i przez drugą połowę czasu wykonujemy programy
nie jest to optymalne

e) Q bliskie 0
prawie nic nie zostanie wykonane, większość czasu marnujemy

## Zadanie 5
:::success
Autor:	Julian Włodarek	
:::
![](https://hackmd.io/_uploads/r19g1MfB2.png)

Dane podejście sprawia, że procesy ograniczone przez dostęp do procesora będą miały dłuższy czas działania na procesorze (będą nagradzane / faworyzowane).

Procesy ograniczone przez wejście-wyjście będą działać krócej na procesorze (będą karane).

Zatem taki algorytm może być użyteczny gdy chcemy faworyzować pierwszy rodzaj procesów.

## Zadanie 6

:::success
Autor:	Oskar Kropielnicki	
:::

![](https://hackmd.io/_uploads/BkpEoLTV2.png)

**SJF (Shortest Job First)** - algorytm ten wybiera najpierw procesy, które powinny wykonać się najkrócej, a robi to korzystając z dodatkowych danych od użytkownika lub obliczając czasy wykonania bazując na poprzednich czasach wykonania tych procesów.

$\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n$

gdzie $\tau_n$ oznacza przewidywany czas $n$-tej fazy procesora, a $t_n$ to rzeczywisty czas $n$-tej fazy procesora. $0 \leq \alpha \leq 1$ to dowolna stała.

**SRT (Shortest Remaining Time First)** - algorytm podobny do SJF, ale ten odbiera procesom dostęp do procesora. Gdy pojawia się nowy gotowy proces, obecnie wykonujący się traci prawa do procesora, a algorytm wybiera następny proces bazując na pozostałym czasie każdego procesu.

### a
$\alpha = 0,\;\tau_0 = 100 \text{ms}$

Podstawiając $\alpha = 0$ do równania otrzymujemy $\tau_{n+1} = \tau_n$, czyli nie zwracamy w ogóle uwagi na rzeczywiste czasy wykonania i zakładamy, że każda faza trwa równie długo - 100ms.

### b
$\alpha = 0.99,\;\tau_0 = 10 \text{ms}$

Podstawiając $\alpha = 0.99$ do równania otrzymujemy $\tau_{n+1} = 0.99 t_n + 0.01\tau_n$, czyli rzeczywiste czasy wykonania znacząco będą wpływały na predykcję.


## Zadanie 7
:::success
Autor: Marta Strzelec		
:::
![](https://hackmd.io/_uploads/S1FnCZzSn.png)
Standardowo gdy używamy algorytmu planowania procesów z użyciem kolejek wielopoziomowych, procesy są permanentnie przypisane do danej kolejki i nie wędrują pomiędzy nimi. Taki system jest dość nieelastyczny.

**Wielopoziomowe kolejki ze sprzężeniem zwrotnym** to takie kolejki, w których procesy mogą wędrować między kolejkami.

**W jaki sposób taki algorytm obsługuje różne klasy procesów?**
Algorytm posługuje się prostą zasadą - im wyższy priorytet tym bardziej interaktywne procesy. 

Dodatkowo, żeby system działał poprawnie, kwanty czasu wraz ze zmniejszeniem się priorytetu powinny maleć (chcemy dość szybko przerywać działanie procesu o priorytecie niższym, gdy pojawi się proces o priorytecie wyższym). 

Dodatkowo, jeśli proces czeka zbyt długo w kolejce o niższym priorytecie, może być przeniesiony do kolejki o wyższym priorytecie (zapobieganie zagłodzeniu/starvation -> **reguła promocji**). 

Generalnie, algorytm ten jest zdefiniowany za pomocą następujących parametrów:
* liczby kolejek
* algorytmu planowania procesów dla poszczególnych kolejek
* metody, która determinuje kiedy zupgredować dany proces
* metody, która determinuje kiedy zdegradować dany proces

Algorytm ten jest bardzo elastyczny i może być dostosowany do róznych potrzeb - jednak jednocześnie sprawia to, że staje się złożony - aby zdefiniować najlepsze rozplanowanie procesów musimy wziąć pod uwagę różne parametry.
![](https://hackmd.io/_uploads/Syy8dba4h.png)
## Zadanie 8
:::success
Autor: Anna Krysta		
:::

![](https://hackmd.io/_uploads/ByUHgMzr2.png)

Zasada działania algorytmu
- jest to algorytm round robin with multilevel feedback,
- scheduler wybiera proces z kolejki o najwyższym priorytecie
- jeżeli jest kilka procesów o tym samym najwyższym priorytecie, to scheduler wybiera do wykonania ten, który był „ready” najdłuższy czas
- jeżeli nie ma żadnego procesu do wykonania, scheduler zostaje zamrożony do czasu przerwania, gdy nastąpi przerwanie, scheduler ponownie będzie wybierał jakiś proces do wykonania
- kolejki priorytetów będą podzielona na dwie grupy: kernel grupa oraz użytkownika kolejki
- priorytety użytkownika kolejek to będą funkcje CPU usage, jeżeli jakaś kolejka użyła niedawno CPU, dostaje wtedy mniejszy priorytet
- kernel kolejki są podzielone w sposób następujący: procesy z niskim priorytetem budzą się po otrzymaniu sygnału, a procesy z wysokim priorytetem nadal są zamrożone
- kolejki kernel także będą obliczać dynamicznie swoje priorytety
- kernel przypisuje priorytet procesowi, który ma zostać uśpiony, korelując stałą wartość priorytetu z powodem uśpienia
- zegar może przerywać proces kilka razy podczas jego kwantu czasu. przy każdym przerwaniu zegara, program obsługi zegara inkrementuje pole w tabeli procesów, które rejestruje ostatnie użycie procesora przez proces. Raz na sekundę, program obsługi zegara dostosowuje również ostatnie użycie procesora przez każdy proces zgodnie z funkcją:
decay(CPU) = CPU/2
- podczas ponownego obliczania ostatniego użycia procesora, program obsługi zegara również ponownie oblicza priorytet każdego procesu zgodnie ze wzorem:

priority = ("recent CPU usage"/2) + (base level user priority)

Gdzie "base level user priority" to priorytet progowy między priorytetami kernel a użytkownika
- procesy mogą kontrolować priorytety wywołując systemową funkcję nice(value), wtedy w funkcji zmieniania priorytetów jest jeszcze jedna składowa – nice value:

priority= ("recent CPU usage"/constant) + (base priority) + (nice value)

Wywołanie systemowe nice zwiększa lub zmniejsza pole nice w tabeli procesów o wartość parametru, chociaż tylko superużytkownik może podać wartości nice, które zwiększają priorytet procesu.

![](https://hackmd.io/_uploads/r1iNyGfSn.png)
![](https://hackmd.io/_uploads/rykLyGGS2.png)
![](https://hackmd.io/_uploads/ByCokGzr3.png)


## Zadanie 9
:::success
Autor:	Anna Krysta
:::

![](https://hackmd.io/_uploads/r1nttHjSh.png)


Zasada działania „fair share scheduler” polega na podzieleniu społeczności użytkowników na grupy sprawiedliwego podziału, tak aby członkowie każdej grupy podlegali ograniczeniom regularnego process scheduler w stosunku do innych procesów w grupie. Nowy wzór na aktualizowanie priorytetów jest następujący:

priority = ("recent CPU usage"/constant) + (base priority) + (nice value) + ("fair share group priority"/constant)

System przydziela czas procesora proporcjonalnie do każdej grupy, niezależnie od liczby procesów w grupach.
Czyli dla poniższego przykładu, gdy są dwie grupy 1(A) oraz 2(B, C), to każda tych grup dostaje 50% czasu procesora, zatem A dostaje 50%, B – 25%, C – 25%. Wtedy kolejność wykonywania części jest A, B, A, C, A, B, A, C, A, B, A, C, … , czyli sprawiedliwie.


![](https://hackmd.io/_uploads/rJqVurjSh.png)


