---
# System prepended metadata

title: 'Ćwiczenia 12, grupa cz. 16-18, 23 maja 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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	
![Zrzut ekranu 2024-05-23 o 16.21.50](https://hackmd.io/_uploads/r12-b027C.png)

### 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.**

![Zrzut ekranu 2024-05-23 o 16.24.32](https://hackmd.io/_uploads/ryCjWA27A.png)


*Wymaga bitów odniesienia.*

### **6. LRU (Least Recently Used)**:
  **Zastępowana jest strona, która była najdłużej nieużywana**
  ![Zrzut ekranu 2024-05-23 o 16.30.14](https://hackmd.io/_uploads/ByEb7ChXC.png)

*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	
:::

![image](https://hackmd.io/_uploads/rkTd-G1rC.png)
![image](https://hackmd.io/_uploads/r1tFZG1S0.png)

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)



