---
# System prepended metadata

title: 'Ćwiczenia 12, grupa śr. 14-16, 22 maja 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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	
:::

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

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	
:::
![image](https://hackmd.io/_uploads/BJ-0hocmR.png)
![image](https://hackmd.io/_uploads/HyDR3j9mR.png)
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)
![image](https://hackmd.io/_uploads/Sy_eQvjQR.png)

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ę.
