# Ćwiczenia 12, grupa śr. 14-16, 22 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 |
| ----------------------:| -----| --- | --- | --- |
Krzysztof Chorzempa | X | X | X | |
Maciej Ciepiela | X | X | X| |
Szymon Fica | X | X | X | X |
Agnieszka Grala | X | X | X | |
Karolina Jędraszek | | | | |
Katarzyna Jodłowska | X | X | X | X |
Dominik Kiełbowicz | ==X== | X | X | X |
Michał Kolasa | X | ==X== | X | X |
Rafał Krysa | X | X | X | X |
Miłosz Krzysiek | | | | |
Łukasz Kulczycki | | | | |
Leon Lepkowski | X | X | X | X |
Hanna Makowska | | | | |
Jan Marek | X | X | ==X== | |
Cezary Miłek | X | X | X | X |
Anna Pierzchała | | | | |
Alan Pietrasz | X | X | X | X |
Kacper Ponikowski | X | X | X | X |
Dominik Walecko | X | | X | |
Michał Włodarczak | | | | |
Błażej Molik | X | X | X | X |
:::

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

:::danger
| | 11.6 |11.7 |11.8 |11.9 |
| ----------------------:| -----| --- | --- | --- |
Krzysztof Chorzempa | | | | |
Maciej Ciepiela | | | | |
Szymon Fica | X | | | |
Agnieszka Grala | | | | |
Karolina Jędraszek | | | | |
Katarzyna Jodłowska | X | | | |
Dominik Kiełbowicz | X | X | X | X |
Michał Kolasa | X | X | X | ==X== |
Rafał Krysa | X | | X | |
Miłosz Krzysiek | | | | |
Łukasz Kulczycki | | | | |
Leon Lepkowski | X | | X | |
Hanna Makowska | | | | |
Jan Marek | X | X | X | |
Cezary Miłek | X | | | |
Anna Pierzchała | | | | |
Alan Pietrasz | X | | X | |
Kacper Ponikowski | X | | X | |
Dominik Walecko | X | X | | |
Michał Włodarczak | | | | |
Błażej Molik | X | | | |
:::

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

## Zadanie 0
:::success
Autor: Cezary Miłek
:::

> *Zdefiniuj następujące algorytmy wymiany stron: **optymalny, NRU, FIFO, algorytm drugiej szansy, clock, LRU**. Zastanów się, jakiego **wsparcia ze strony sprzętu** potrzebują te algorytmy.*

### **Optymalny Algorytm Wymiany Stron**:
- **Opis**: Algorytm wybiera do zastąpienia stronę, która nie będzie używana przez najdłuższy czas w przyszłości.
- **Wsparcie sprzętowe**: Algorytm ten jest teoretyczny i nie może być zaimplementowany w praktyce, ponieważ wymaga znajomości przyszłych odniesień do stron. Nie potrzebuje wsparcia sprzętowego, ponieważ jest nierealistyczny.

### **Not Recently Used (NRU)**:
- **Opis**: Strony są klasyfikowane na podstawie dwóch bitów (bitu odniesienia i bitu modyfikacji). Strona do zastąpienia jest wybierana ja podstawie priorytetu, interesuje nas najniższy.
- **Wsparcie sprzętowe**: Wymaga wsparcia do zarządzania bitami odniesienia $(R)$ i modyfikacji $(M)$, które muszą być dostępne i aktualizowane przez sprzęt.

### **First-In, First-Out (FIFO)**:
- **Opis**: Najstarsza strona w pamięci (ta, która była najdłużej bez przerwy w pamięci) jest zastępowana jako pierwsza.
- **Wsparcie sprzętowe**: Nie wymaga specjalnego wsparcia sprzętowego, jedynie kolejkowania stron w pamięci.

### **Algorytm Drugiej Szansy**:
- **Opis**: Jest to modyfikacja algorytmu FIFO. Strona, która ma być zastąpiona, jest sprawdzana; jeśli jej bit odniesienia jest ustawiony, bit jest resetowany i strona jest umieszczana na końcu kolejki.
- **Wsparcie sprzętowe**: Potrzebuje kolejki FIFO i bitu odniesienia $(R)$.

### **Clock Algorithm**:
- **Opis**: Modyfikacja algorytmu drugiej szansy, gdzie strony są organizowane w pierścień. Wskaźnik zegara porusza się w koło i sprawdza bity odniesienia stron, zastępując pierwszą stronę z wyzerowanym bitem.
- **Wsparcie sprzętowe**: Podobnie jak algorytm drugiej szansy, wymaga bitów odniesienia.

### **Least Recently Used (LRU)**:
- **Opis**: Strona, która była najdłużej nieużywana, jest zastępowana.
- **Wsparcie sprzętowe**: Sprzęt pomagający śledzić kolejność odniesień do stron.

## Zadanie 1
:::success
Autor: Katarzyna Jodłowska
:::

Analiza Błędów Stron dla Algorytmów FIFO i LRU
Załóżmy, że mamy pamięć fizyczną z 4 ramkami i pamięć wirtualną z 8 stronami. Procesor generuje odwołania do stron pamięci w kolejności: 0, 1, 7, 2, 3, 2, 7, 1, 0, 3. Zliczymy błędy stron dla dwóch algorytmów: FIFO (First-In First-Out) i LRU (Least Recently Used).

Algorytm FIFO (First-In First-Out)
FIFO wymienia stronę, która była najdłużej w pamięci.
Stan początkowy:
* Pamięć fizyczna: pusta
* Kolejność odwołań: 0, 1, 7, 2, 3, 2, 7, 1, 0, 3
Kroki:
1. 0: [0] - miss
2. 1: [0, 1] - miss
3. 7: [0, 1, 7] - miss
4. 2: [0, 1, 7, 2] - miss
5. 3: [1, 7, 2, 3] - miss (0 usunięte)
6. 2: [1, 7, 2, 3] - hit
7. 7: [1, 7, 2, 3] - hit
8. 1: [1, 7, 2, 3] - hit
9. 0: [7, 2, 3, 0] - miss (1 usunięte)
10. 3: [7, 2, 3, 0] - hit
Liczba błędów stron (misses): 6

Algorytm LRU (Least Recently Used)
LRU wymienia stronę, która była najdawniej używana.
Stan początkowy:
* Pamięć fizyczna: pusta
* Kolejność odwołań: 0, 1, 7, 2, 3, 2, 7, 1, 0, 3
Kroki:
1. 0: [0] - miss
2. 1: [0, 1] - miss
3. 7: [0, 1, 7] - miss
4. 2: [0, 1, 7, 2] - miss
5. 3: [1, 7, 2, 3] - miss (0 usunięte, najdawniej używane)
6. 2: [1, 7, 3, 2] - hit
7. 7: [1, 3, 2, 7] - hit
8. 1: [3, 2, 7, 1] - hit
9. 0: [2, 7, 1, 0] - miss (3 usunięte, najdawniej używane)
10. 3: [7, 1, 0, 3] - hit (2 usunięte, najdawniej używane)
Liczba błędów stron (misses): 7

Podsumowanie
* FIFO: 6 błędów stron
* LRU: 7 błędów stron
Wynika z tego, że dla podanego ciągu odwołań algorytm FIFO jest bardziej efektywny niż LRU, generując mniej błędów stron.

## Zadanie 2
:::success
Autor: Jan Marek
:::


Patrzymy na bit R strony, na którą wskazuje head. Jeśli R=1, to umieszczamy stronę na koniec kolejki (tail) i rozważamy kolejną stronę wskazywaną przez head. Jeśli R=0, to wyrzucamy taką stronę i dodajemy nową na koniec kolejki.

(B, 3, 1) <- head
(C, 7, 1)
(D, 8, 0)
(E, 12, 1)
(F, 14, 1)
(G, 15, 0)
(H, 18, 1)
(A, 20, 1) <- tail

1. Skoro bit R ramki (B, 3, 1) jest ustawiony na 1, to wywalamy ją na koniec kolejki i ustawiamy R=0

(C, 7, 1) <- head
(D, 8, 0)
(E, 12, 1)
(F, 14, 1)
(G, 15, 0)
(H, 18, 1)
(A, 20, 1)
(B, 3, 0) <- tail

2. Tutaj to samo z ramką (C, 7, 1)

(D, 8, 0) <- head
(E, 12, 1)
(F, 14, 1)
(G, 15, 0)
(H, 18, 1)
(A, 20, 1)
(B, 3, 0)
(C, 7, 0) <- tail

3. Teraz bit ramki (D, 8, 0) jest ustawiony na 0, a więc wywalamy taką ramkę z kolejki oraz na koniec kolejki dodajemy wymienioną ramkę

(E, 12, 1) <- head
(F, 14, 1)
(G, 15, 0)
(H, 18, 1)
(A, 20, 1)
(B, 3, 0)
(C, 7, 0)
(NOWA RAMKA) <- tail

A więc zastąpiona ramką będzie (D, 8, 0).

## Zadanie 3
:::success
Autor: Kacper Ponikowski
:::
a) Będzie to mało efektywne ponieważ te algorytmy źle sprawdzają się dla odniesień cyklicznych. I będziemy ciągle nadpisywali te same ramki.

b)

Tutaj przeznaczamy 499 miejsc na pierwsze 499 stron i ich nie ruszmy wiedząc że odniesienia są cykliczne. Pozostałe odniesienia obsługujemy modyfikując pozostałą ramkę.