# SyK 11

## Zadanie 1
**Planowanie wywłaszczające pozwala na odebranie procesowi dostępu do procesora i przekazaniu tych zasobów innemu procesowi.**




**Proces ograniczony przez dostęp do procesora (ang. CPU-bound
process)** to proces wymagający długiego dostępu do procesora. Dostęp do procesora to najważniejszy zasób wymagany do ukończenia procesu.

**Proces ograniczony przez wejście-wyjście (ang.
Input-Output bound process)** to proces, którego wykonanie najmocniej obciąża układ wejścia/wyjścia, np. odczyt dużej ilości danych z dysku

**Proces interaktywny** to proces powiązany z programem, który podejmuje interakcję z użytkownikiem, np. przeglądarka internetowa. Takie procesy muszą być obsługiwane bardzo szybko, aby zapewnić użytkownikowi komfort z korzystania z programu.

**Proces wsadowy** to proces wykonujący się w tle, na który użytkownik nie ma żadnego wpływu

**Planowanie wywłaszczające pozwala** na obsługę procesów interaktywnych, co jest niezbędne, by zapewnić płynne korzystanie z programów. Daje również większą kontrolę nad kolejnością wykonania procesów, co optymalizuje wykorzystanie CPU i działanie systemu operacyjnego.

## Zadanie 2

Zdefiniuj miary efektywności algorytmów planowania procesów i uzasadnij ich sensowność. Dla każdej z nich zastanów się, czy każdy algorytm optymalizujący tą miarę optymalizuje również pozostałe.


Miary efektywności algorytmów planowania procesów to wyznaczniki skuteczności danej polityki przydziału procesora dla procesów operujące w wybranym przez siebie spektrum oceny. Różne miary efektywności oceniają wydajność algorytmu przydziału według wybranych metryk, kolejno są to:
-> ( A ) użycie (np. procentowe) procesora w wybranej ramie czasowej
-> ( B ) liczba procesów które zakończyły swoje wykonanie w wybranej ramie czasowej
-> ( C ) (średni) czas pomiędzy rozpoczęciem a zakończeniem procesu
-> ( D ) czas oczekiwania procesu w kolejce (do czasu rozpoczęcia wykonywania i potencjalnie czas przerw w dostępie do procesora)
-> ( E ) czas pomiędzy dodaniem procesu na kolejkę a jego zakończeniem

Każda z tych miar rozpatruje inny aspekt optymalności algorytmu. Wyjaśnienie sensowności wymienionych powyżej miar:

( A ) maksymalizacja czasu realnej pracy procesora (pomijając czas potrzebny schedulerowi procesów) oznacza efektywne wykorzystanie dostępnych zasobów hardware'owych. Potencjalne przerwy w pracy procesora należy minimalizować (oprócz przypadków gdy procesor nie ma dostępnych żadnych zadań i jest skazany na tymczasową bezczynność)

( B ) zwrócenie odpowiedzi dla jak największej liczby procesów jest pomocne dla zachowania np. płynności działania procesów interaktywnych

( C ) rozpoczęcie procesu tylko po to aby potem go przerywać (potencjalnie wielokrotnie) nie jest idealnym podejściem. Takie działanie potencjalnie spowodowałoby, że procesor mógłby wykonywać większość obliczeń dla wielu procesów, a jednocześnie żaden z nich nie dostałby żadnej odpowiedzi w rozsądnym czasie od rozpoczęcia. W tym czasie proces ten mógłby już np. zlecić operacje I/O i przyspieszyć tym samym całościowe wykonanie programu

( D ) trzymanie wielu procesów w kolejce nie jest optymalne z powodów jak opisałem wyżej

( E ) kluczowa metryka dla procesów interaktywnych. Ponadto nawet dla procesów wsadowych oczekujemy jak najszybszych odpowiedzi, nie chcemy bowiem by procesy wykonały się w 90% a następnie zostały odłożone na kolejkę na długi czas

Jak widać każda z powyższych miar ma swoje zalety. Między wieloma parami metryk występuje korelacja dla przypadku średniego. Każda potencjalna korelacja jest jednak mocno powiązana z otrzymanymi procesami (i ich własnościami), możemy więc analizować jedynie tendencje do korelacji między parami metryk. Mamy więc np. korelację dla pary (4, 5). Jasnym jest, że w ogólności im krótszy czas oczekiwania w kolejce - tym szybciej wynik zostanie zwrócony.

Jednakże maksymalizacja (1) wcale nie musi oznaczać że zminimalizowany zostanie (5). Algorytm mógłby bowiem rozpoczynać każdy proces, wykonywać go częściowo a następnie odkładać na kolejkę na długi czas. Tym samym procesor mógłby być wykorzystywany w 100% a jednak metryka (5) osiągałaby bardzo słabe wyniki.

## Zadanie 6

**SJF - Shortest Job First**
-> pomysł, tak jak sama nazwa wskazuje, polega na wykonywaniu najpierw procesów najkrótszych
-> algorytm niewywłaszczający
-> optymalny algorytm pod względem średniego czasu oczekiwania procesu na jego wykonanie.

Możemy zmienić w nim sposób wyboru procesów, stosując technikę wykładniczego uśredniania. Pomysł polega na oszacowaniu czasu działania procesu na podstawie jego poprzednich czasów


**a)** $\alpha = 0 \space i \space \tau_{0} = 100$ milisekund

W tym skrajnym przypadku liczyć się będzie jedynie poprzednie oszacowanie
$τ_{n+1} = τ_{n} = τ_{0}$

**b)** $\alpha = 0.99 \space i \space \tau_{0} = 10$ milisekund

W tym przypadku $(1 - \alpha) \approx 0$ zatem $\tau_{n+1} \approx t_n$

**SRT - SHORTEST REMAINING TIME (FIRST)**
-> wywłaszczająca wersja algorytmu SJF
-> jeśli jakiś proces zakończyłby się szybciej niż proces aktualnie przetwarzany, to przerywamy aktualnie przetwarzany proces, aby wykonać proces, który zakończyłby się szybciej

dobrze widać działanie SRT na przykładzie ze slajdów, proces nr 1 został przerwany, bo pojawił się proces nr 2, który zakończyłby się szybciej

## Zadanie 7
Wielopoziomowa kolejka składa się z wielu kolejek gotowych procesów, każda z nich o innym priorytecie. Najpierw zostają wykonane procesy w kolejce o najwyższym priorytecie, potem te w kolejkach o niższym priorytecie.
Procesy mogą zostać **promowane** do kolejki o wyższym priorytecie, albo **zdegradowane** do kolejki o niższym. Po fazie procesora danego procesu możemy użyć informacji o czasie trwania tej fazy, aby zmienić przydzielić proces do innej kolejki. Gdy dany proces ma dłuższe fazy procesora niż dana kolejka oczekuje, możemy go zdegradować do kolejki o niższym priorytecie. Natomiast, gdy ma krótsze możemy go promować do kolejki o wyższym priorytecie.

Promowanie procesu do kolejki o wyższym priorytecie jest przydatne także, gdy dany proces czeka bardzo długo w kolejce o niższym priorytecie i ciągle wykonywane są procesy z kolejek o wyższym priorytecie. Taka metoda nazywa się metodą postarzania (ang. aging).

Procesy **czasu rzeczywistego** algorytm powinien dodać do kolejki o bardzo wysokim priorytecie, procesy **interaktywne** do kolejki o niższym, a procesy **wsadowe** do kolejki o bardzo niskim priorytecie.


## Zadanie 8
Klasyczny Uniksowy algorytm planowania procesów opiera się na wielopoziomowej kolejce.
Każdy proces dostaje pewien stały kwant czasu, jeżeli nie wykona się w tym czasie zostaje zwrócony do kolejki.

Zegar wielokrotnie w trakcie kwantu czasu zwiększa wartość "recent CPU usage" działającego procesu o 1.
Raz na sekundę wszystkie procesy mają aktualizowane "recent CPU usage" za pomocą funkcji degradacji (decay)
#### Wzory
(mniejsza liczba ocznacza większy priorytet)
$priority=CPU/constant + \text{(base priority)} + \text{(nice value)}$
$CPU = decay(CPU) = CPU / 2$

Procesy użytkownika mają priorytety większe, lub równe (base priority)

#### Przykład:
Proces `A` należy do grupy 1, procesy `B` i `C` należą do grupy 2
$basepriority = 60$
$constant = 2$
$\text{(nice value)} = 0 \text{ (dla każdego procesu)}$


## Zadanie 9
Chcielibyśmy mieć możliwość przydzielania każdemu użytkownikowi pewnej części czasu działania procesora. Rozwiązaniem jest zmodyfikowanie algorytmu z poprzedniego zadania poprzez przypisanie użytkowników do grup. System będzie przydzielał każdej grupie równą ilość czasu procesora niezależnie od liczby procesów w każdej grupie.

Oznaczenia:
CPU = "recent CPU usage"
Group = "recent Group usage"

Zmodyfikowany wzór na priorytet danego procesu wygląda następująco:
$priority=CPU/constant + \textbf{Group/constant} + \text{(base priority)} + \text{(nice value)}$

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

#### Przykład:
Proces `A` należy do grupy 1, procesy `B` i `C` należą do grupy 2
$basepriority = 60$
$constant = 2$
$\text{(nice value)} = 0 \text{ (dla każdego procesu)}$