---
# System prepended metadata

title: 'Ćwiczenia 11, grupa cz. 14-16, 26. maja 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ćwiczenia 11, grupa cz. 14-16, 26. maja 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   | 8   | 9   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś              |       |     |     |     |     |     |     |     |     | 
Mateusz Burdyna          |       |     |     |     |     |     |     |     |     |
Dariusz Ciesielski       |       |     |     |     |     |     |     |     |     |
Dawid Dudek              |   X   |  X  | X   |  X  |  X  | X   |  X  |  X  |     |
Mikołaj Dworszczak       |       |     |     |     |     |     |     |     |     |
Przemysław Grochal       |   X   |  X  |  X  |     |     |  X  |     |     |     |
Adam Jarząbek            |   X    |  X   | X    | X    |     |  X   |==X==     | X    |     |
Anna Karykowska          |   X   |  ==X==  |  X  |  X  |     | X    |  X  |  X  |     |
Oleś Kulczewicz          |       |     |     |     |     |     |     |     |     |
Pola Marciniak           |   X   |  X  |  X  |  X  |     |  X  |  X  |     |     |
Mikołaj Mroziuk          |  X    |  X  |  X  |    X |     |   x |  X  |     |     |
Marcelina Oset           |   x   |  x  |  x  |     |     |     |     |     |     |
Natalia Piasta           |    X   |   X  |   X  |  X  |  xx   |  X   |   X  |   X  |   X  |
Krzysztof Piekarczyk     |   X    |  X   |  ==X==   |   X  |  X   |  X   |  X   |  X   |     |
Marcin Płaza             |   X    |   X  |   ==X==  |  X   |     |  X   |   X  |     |     |
Paweł Richert            |   X   |  X  |  X  |     |     |     |     |     |     |
Rafał Starypan           |   X    |  X   |   X  |  X   |     |  X   |  X   |     |     |
Dawid Strojek            |   X   |  X  |  X  |  X  |     |  X  |  X  |     |     |
Mateusz Suszek           |   X    |  X   |  X   |  X   |     |  ==X==   |  X   |     |     |
Wojciech Śniady          |    X   |  X   |  X   |  X   |     |  X   |  X   |     |     |
Volha Tsekalo            |    X |    X | X    | X    |     |  X   |   X  |     |     |
Yana Vashkevich          |   X    |  X   |  X   |  X   |     |  X   |  X   |     |     |
Konrad Woźniak           |   X    |  X   |  X   |  X   |     |  X   |  X   |     |     |
Natalia Czerep           |       |     |     |     |     |     |     |     |     |
Joanna Stachowicz        |==X==  |  X  |  X  |  X  |     |  X   |  X   |     |     |
:::


**Tu można dodeklarować zad. 6. z listy 8.:**
* Krzysztof Piekarczyk
* 
* 

**Tu można dodeklarować zad. 9. z listy 9.:**
* Krzysztof Piekarczyk
* 
* 



**Tu można dodeklarować zad. 9. z listy 10.:**
* Przemysław Grochal
* 
* 


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


## Zadanie 1
:::success
Autor: Joanna Stachowicz

![](https://i.imgur.com/3Q5sTQT.jpg)

![](https://i.imgur.com/MO5tO1G.jpg)

![](https://i.imgur.com/97SQPzm.jpg)




:::

## Zadanie 2
:::success
Autor: Anna Karykowska
:::
![](https://i.imgur.com/9Ej2aW2.png)

Miary efektywności algorytmów planowania procesów:

▪ **CPU utilization** – keep the CPU as busy as possible
Tutaj sprawne będą algorytmy bez wywłaszczania, czyli np. FCFS. Jeżeli skupimy się na tym aspekcie, to zaniedbamy response time.

▪ **Throughput** – # of processes that complete their execution per time unit
Podobnie do CPU utilization.

▪ **Turnaround time** – amount of time to execute a particular process
Dobre będą np. SJF i SRT. Zaniedbujemy response i waiting time.

▪ **Waiting time** – amount of time a process has been waiting in the ready queue
Tutaj możemy mieć np. algorytm RR. Zaniedbujemy wtedy turnaround time.

▪ **Response time** – amount of time it takes from when a request was submitted until the first response is produced.
Możemy mieć np. algorytmy RR lub priorytetowy z wywłaszczaniem. Zaniedbujemy wtedy pozostałe kryteria.

## Zadanie 3
:::success
Autor: Marcin Płaza
:::

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

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

turnaround time
P1: 2, P2: 3, P3: 11, P4: 15, P5: 20
waiting time
P1: 0, P2: 2 , P3: 3, P4: 11, P5: 15

avg wait: 6.2
SJF 
![](https://i.imgur.com/v6nJcam.png)

turnaround time
P1: 3, P2: 1, P3: 20, P4: 7, P5: 12
waiting time
P1: 1, P2: 0, P3: 12, P4: 3, P5: 7

avg wait: 4.6
Priorytet
![](https://i.imgur.com/YYbsQ7N.png)

turnaround time
P1: 15, P2: 20, P3: 8, P4: 19, P5: 13
waiting time
P1: 13, P2: 19, P3: 0, P4: 15, P5: 8

avg wait: 11
RR Q=2
![](https://i.imgur.com/rvVPA0s.png)

turnaround time
P1: 2, P2: 3, P3: 20, P4: 13, P5: 18
waiting time
P1: 0, P2: 2, P3: 12, P4: 9, P5: 13

avg wait: 7.2
## Zadanie 4
:::success
Autor: Wojciech Śniady
:::
![](https://i.imgur.com/7X4XX8H.png)
1. Dla każdego priorytetu tworzymy osobną kolejkę Round Robin.
![](https://i.imgur.com/J63VxWj.png)
Problem: Starvation - procesy posiadające niski priorytet mogą nigdy nie dojść do momentu wykonywania
Rozwiązanie: Aging - procesom o niskim priorytecie zwiększany jest ich priorytet po długim czasie oczekiwania na wykonianie
2.
a) Q = inf => nie ma w ogóle korzyści z Round Robin, jest to de facto FCFS
b) Q > T => lepszy niż a, bo te to średni czas, np. dla trzech procesów o niskim T i jednym o dużym zyskamy odrobinę, ale nadal nie jest to optymalne
c) S < Q < T => najbardziej optymalny wariant
d) Q = S => czas wykonywania procesu jest równy czasowi na zmianę kontekstu, więc nie jest to optymalne (jeśli zależy nam na wysokiej interaktywności), ponieważ jedynie przez połowę czasu wykonujemy procesy, a drugą połowę czasu tracimy
e) Q bliskie 0 => jeśli S nie jest bliskie 0, to program będzie się liczył bardzo długo

## Zadanie 5
:::success
Autor: Dawid Dudek
:::

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


Rozważmy dwa rodzaje procesów:

- Te które są ograniczone przez procesor
- Te które mają krótki czas procesora (np mają jakieś i/o burst)


Widzimy, że ta modyfikacja nie jest sprawiedliwa:

- procesy, które są ograniczone przez procesor są nagradzane 
- procesy, które czekają na jakiś sygnał są karane -> dostają mniejszy kwant czasu i pomimo, że mógłby się jeszcze wykonywać to proces trafi na koniec kolejki bo dostał mniejszy kwant


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

## Zadanie 6
:::success
Autor: Mateusz Suszek
:::
![](https://i.imgur.com/dh27UNm.png)

![](https://i.imgur.com/1IZwocL.png)
![](https://i.imgur.com/pkmwjvp.png)
![](https://i.imgur.com/yvxHG1o.png)
![](https://i.imgur.com/QF3egd1.png)


## Zadanie 7
:::success
Autor: Adam Jarząbek
:::

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

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

## Zadanie 8
:::danger
Autor: Natalia Piasta
:::
Uniksowy algorytm planowania procesów to algorytm karuzelowy, tylko z użyciem wielopoziomowych kolejek ze sprzężeniem zwrotnym (ang. *round robin with multilevel feedback*).

Jednak co to tak naprawdę oznacza? Oznacza to, że procesy są przydzielane procesom na określony fragment czasu. Gdy proces wykorzysta swój czas, to zostaje on z powrotem umieszczony w kolejce.

Algorytm Planowania:
```
Dopóki nie ma procesu do wykonania:
    Dla każdego procesu z kolejki uruchomień:
        Wybierz do wykonania procesu ten o najwyższym priorytecie, który jest załadowany do pamieci
    Jeżeli nie ma procesu kwalifikującego się do wykonania:
        Bezczynność maszyny
        // Przerwanie wyprowadzi maszynę ze stanu bezczynności
Usuń wybrany proces z kolejki uruchomień
Przełącz kontekst na wybrany proces i wznów jego wykonanie
```
Wybieramy proces o najwyższym priorytecie z tych gotowych uruchomienia. Jeśli jest parę procesów o najwyższym prorytecie to wybieramy ten gotowy do uruchomienia przez najdłuższy czas.

Są dwie klasy priorytetów:
* priorytety użytkownika (ang. *user priority*)
* priorytety jądrowe (ang. *kernel priority*)

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

Jądro oblicza priorytet procesu w określonych stanach procesu:
* Przypisuje priorytet procesowi, który ma zostać uśpiony na podstawie powodu uśpienia.
* Priorytet procesu zostaje przeliczony podczas zmiany. 
* Obsługa zegara co jakiś czas oblicza priorytety wszystkich procesów.


Za każdym razem obliczmy rozpad procesora (ang. *decay of the CPU*) wzorem:
$CPU = decay(CPU) = \frac{CPU}{2}$

Oraz priorytet procesu:
$priority = (nowe\ \frac{CPU}{2}) + (podstawowy\ priorytet\ użytkownika)$


## Zadanie 9
:::success
Autor: Anna Karykowska
:::

Większość założeń zostaje taka, jak w zadaniu 8, ale dodajemy podział na grupy.

$CPU = decay(CPU) = CPU/2$
$Group = decay(Group) = Group/2$

$priority = (\frac{CPU}{constant}) + (\frac{Group}{constant}) + (podstawowy\ priorytet\ użytkownika) + (nice)$

Przykład dla:
1. grupa - A
2. grupa - B, C

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

