# Ćwiczenia 12, grupa cz. 16-18, 23 maja 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
| | 0 | 1 | 2 | 3 |
| ----------------------:| -----| --- | --- | --- |
Marcin Banak | X | X | X | X |
Bartosz Borecki | X | X | X | X |
Karol Burczyk | X | X | X | X |
Yelyzaveta Ilman | X | X |X | X |
Antoni Kamiński | X | X | X | X |
Jan Kamyk | | | | |
Bartosz Kruszewski | X | X | X | X |
Hanna Laszkiewicz | X | X | X | X |
Kaja Matuszewska | | | | |
Dominik Muc | | | | |
Krzysztof Ostrowski | | | | |
Franciszek Przeliorz | X | X | ==X== | X |
Yaryna Rachkevych | X |==X==| X | X |
Mikołaj Kalitka | X | X | X | X |
Piotr Thamm | ==X== | X | X | |
Taras Tsehenko | | | | |
Wiktor Małek | | | | |
Piotr Salamon | X | X |X | ==X== |
:::

**UWAGA: Poniżej można zadeklarować zadania 4 -- 9 z listy 11**

:::danger
| | 11.4 |11.5 |11.6 |11.7 |11.8 |11.9 |
| ----------------------:| -----| --- | --- | --- | --- | --- |
Marcin Banak | X | | | | X | |
Bartosz Borecki | X | | | | | |
Karol Burczyk | X | | | | | |
Yelyzaveta Ilman | X | X | X | |==X== | |
Antoni Kamiński | X | X | X | ==X== | X | X |
Jan Kamyk | X | X | X | | X | |
Bartosz Kruszewski | X | X | X | X | X | X |
Hanna Laszkiewicz | ==X== | X | X | | X | X |
Kaja Matuszewska | | | | | | |
Dominik Muc | | | | | | |
Krzysztof Ostrowski | | | | | | |
Franciszek Przeliorz | X | X | X | | X | |
Yaryna Rachkevych | X | | | | X | |
Mikołaj Kalitka | X | X | | | X | |
Piotr Thamm | X | | | | | |
Taras Tsehenko | | | | | | |
Wiktor Małek | | | | | | |
Piotr Salamon | X | X | X | | X | |
Michał Włodarczak | X | | X | | X | |
:::

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

## Zadanie 0
:::success
Autor: Piotr Thamm

### 1. Optymalny

**Wymienia stronę, która nie zostanie wykorzystana przez najdłuższy czas w przyszłości:**

"Odwołanie do innych stron może nastąpić za 10, 100 lub nawet 1000 instrukcji później. Każdą stronę można oznaczyć etykietą w postaci liczby instrukcji, które będą wykonane, zanim nastąpi pierwsze odwołanie do tej strony.
Zgodnie z zasadami optymalnego algorytmu zastępowania stron, z pamięci powinna być usunięta strona o najwyższej wartości etykiety."

**Wymaga wiedzy o tym, kiedy nastąpią kolejne odwołania do każdej ze strony, co jest niewykonalne.**

**Algorytmu używa się jako punkt odniesienia do oceny innych algorytmów.**

### 2. NRU (Not Recently Used)

**Strony są klasyfikowane na podstawie dwóch bitów (bitu odniesienia i bitu modyfikacji). Istnieją cztery klasy:**
* Klasa 0: strony, do których nie było odwołań, niemodyfikowane.
* Klasa 1: strony, do których nie było odwołań, zmodyfikowane.
* Klasa 2: strony, do których były odwołania, niemodyfikowane.
* Klasa 3: strony, do których były odwołania, zmodyfikowane.

**Algorytm usuwa losowo stroną z niepustej klasy o najniższym numerze.**

*Wymaga wsparcia do zarządzania bitami odniesienia $(R)$ i modyfikacji $(M)$, które muszą być dostępne aktualizowane przez sprzęt.*

### **3. FIFO (First-In, First-Out )**:
**Najstarsza strona w pamięci (ta, która była najdłużej bez przerwy w pamięci, czyli jest na początku kolejki) jest zastępowana jako pierwsza. Nowa strona jest umieszczana na końcu listy**

*Wymaga kolejkowania stron w pamięci.*

### **4. Algorytm Drugiej Szansy**:
**Modyfikacja algorytmu FIFO. Sprawdzamy czy strona, która ma być zastąpiona, ma bit odniesienia ustawiony na 1. Jeżeli tak, to bit jest resetowany(ustawiany na 0) i strona jest umieszczana na końcu listy stron(kolejki). Zapewnia to uniknięcie problemu wyrzucenia często używanej strony**

*Wymaga kolejki FIFO i bitu odniesienia $(R)$ dla każdej strony.*

### **5. Clock**:

**Modyfikacja algorytmu drugiej szansy, gdzie strony są utrzymywane wszystkich na liście cyklicznej w formie zegara,. Wskaźnik zegara porusza się w koło i sprawdza bity odniesienia stron, zastępując pierwszą stronę z wyzerowanym bitem.**


*Wymaga bitów odniesienia.*

### **6. LRU (Least Recently Used)**:
**Zastępowana jest strona, która była najdłużej nieużywana**

*Wymaga wsparcia do śledzenia kolejności użycia stron.*

:::

## Zadanie 1
:::success
Autor: Marcin Banak
#### Potencjalne błędy stron

Zauważmy, że w zapytaniach 0 1 7 2 1 7 2 3 0 3 mamy 5 różnych stron i 4 ramki, więc pamięć wirtualna, która ma pojemność 8 stron nigdy nie zostanie przepełniona, więc wystarczy analizować pamięć fizyczną.

#### Algorytm FIFO

System operacyjny
utrzymuje listę wszystkich stron, które aktualnie znajdują się w pamięci, przy czym strony dodane
jako ostatnie znajdują się na końcu, natomiast te dodane najwcześniej — na początku.

0 -> 0       miss
1 -> 0 1     miss
7 -> 0 1 7   miss
2 -> 0 1 7 2 miss
3 -> 1 7 2 3 swap
2 -> 1 7 2 3
7 -> 1 7 2 3
1 -> 1 7 2 3
0 -> 7 2 3 0 swap
3 -> 7 2 3 0

Liczba błędów: $6$

#### Algorytm LRU

Strony, które były często
używane w ostatnich kilku instrukcjach, prawdopodobnie będą również często używane w następnych kilku. Z kolei strony, których nie używano od dłuższego czasu, prawdopodobnie pozostaną
nieużywane przez długi czas.

0 -> 0       miss
1 -> 0 1     miss
7 -> 0 1 7   miss
2 -> 0 1 7 2 miss
3 -> 1 7 2 3 swap
2 -> 1 7 3 2
7 -> 1 3 2 7
1 -> 3 2 7 1
0 -> 2 7 1 0 swap
3 -> 7 1 0 3 swap

Liczba błędów: $7$

:::

## Zadanie 2
:::success
Autor: Bartosz Borecki
(B, 3, 1)
(C, 7, 1)
(D, 8, 0)
(E, 12, 1)
(F, 14, 1)
(G, 15, 0)
(H, 18, 1)
(A, 20, 1)
:::

## Zadanie 3
:::success
Autor: Karol Burczyk
:::


A) będzie to mało efektywne, ponieważ cykl wynosi 512, więc elementy, które będziemy mieli w kolejnym cyklu na początku są usuwane jako pierwsze
![IMG_0344[3132]](https://hackmd.io/_uploads/rJCQWfkBA.jpg)

B) 499 ramek rezerwujemy na np. strony 0-498, a 1 ramkę przeznaczamy jako bufor dla reszty stron z algorytmem np. FIFO/LRU, cykl będzie 13, więc powinno to być optymalne
![IMG_0345[3134]](https://hackmd.io/_uploads/rJ28bzkB0.jpg)