# Ćwiczenia 12, grupa cz. 10-12, 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 |
| ---:| ---| --- | --- | --- |
Borys Adamiak | X | X | X | ==X== |
Michał Chawar | | | | |
Julia Cygan | X | X | X | X |
Maciej Dengusiak | | | | |
Patryk Flama | X | X | X|X |
Szymon Fluder | X | X | X | X |
Aleksandra Jędrzejak | X | X | X | X |
Mikołaj Karapka | ==X== | X | X | X |
Viktoriia Kashpruk | X |==X== | X | X |
Wiktor Małek | X | X | X | X |
Błażej Molik | | | | |
Andrzej Morawski | | | | |
Konrad Oleksy | | | | |
Lucjan Pucelak | X | X | X | X |
Aleksandra Sęk | | | | |
Radosław Śliwiński | | | | |
Piotr Traczyński | | | | |
Katarzyna Trzos | X | X | ==X== | X |
Piotr Warząchowski | X | X | X | X |
Olga Zaborska | X | X | X | X |
:::

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

:::danger
| | 11.6 |11.7 |11.8 |11.9 |10.9 |
| ----------------------:| -----| --- | --- | --- | --- |
Borys Adamiak | X | | | X | |
Michał Chawar | | | | | |
Julia Cygan | X | | | | |
Maciej Dengusiak | | | | | |
Patryk Flama | X | | | | |
Szymon Fluder | X | X | X | X | X |
Aleksandra Jędrzejak | X | | X | | |
Mikołaj Karapka | X | | | ||
Viktoriia Kashpruk | X | X | X | | |
Wiktor Małek | X | X | X | X | X |
Błażej Molik | | | | | |
Andrzej Morawski | | | | | |
Konrad Oleksy | | | | | |
Lucjan Pucelak | X | | X | | |
Aleksandra Sęk | | | | | |
Radosław Śliwiński | | | | | |
Piotr Traczyński | | | | | |
Katarzyna Trzos | ==X== | | | X | |
Piotr Warząchowski | | | | | | |
Olga Zaborska | X | | X | | |
:::

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

## Zadanie 0
:::success
Autor: Mikołaj Karapka
:::
### Co to jest wymiana stron?
Kiedy program wykryje, że **brakuje wolnej pamięci** RAM na załadowanie nowej strony, musi **zwolnić miejsce**. Wymaga to przeniesienia jednej lub wielu stron z pamięci RAM **do pamięci masowej** (dysku) i załadowania odpowiednich stron z pamięci masowej do RAM.

### Algorytmy wymiany stron:
#### Optymalny
- Wymienia stronę, która nie będzie używana przez dłuższy czas w przyszłości
- Wymaga wiedzy o przyszłych odwołaniach do pamięci. Jednak w praktyce jest to niemal niemożliwe. Używa się go bardziej jako punkt odniesienia do innych algorytmów

#### NRU (Not Recently Used)
- Klasyfikacja stron opiera się na użyciu dwóch bitów
- odniesienia (referenced)
- bit modyfikacji (dirty)
Wybieramy stronę o **najniższym priorytecie**
- Wymaga wparcia do zarządzania tymi bitami oraz żeby były na każdej ze stron

#### FIFO (First-in First-out)
- Wymiana strony, która jest **najstarsza** w pamięci (kolejność FIFO)
- Wymaga kolejności śledzenia stron za pomocą kolejki

#### Drugiej szansy (Last Recently Used)
- Jest to zmodyfikowany **alogrytm FIFO**. Sprawdza się bit odniesienia (referenced). Nie usuwamy teraz od razu, zamiast tego **resetujemy bit** odniesienia, a stronę przenosimy na **koniec kolejki**
- kolejka FIFO i bit odniesienia

#### Clock
- Jest to wariant **algorytmu drugiej szansy**, w którym strony są zorganizowane w "okrągłą listę". Wskaźnik zegara przesuwa się po "kole", dając każdej stronie "drugą szansę", następnie zatępujemy pierwszą stronę z wyzerowanym bitem.
- Podobnie jak algorytm drugiej szansy, wymaga bitów odniesienia.

#### LRU (Last Recently Used)
- Wymienia ostatnio używaną stronę
- Wymaga wsparcia do śledzenia kolejności użycia stron

## Zadanie 1
:::success
Autor: Viktoriia Kashpruk

## Parametry
- **Pamięć fizyczna**: 4 ramki
- **Pamięć wirtualna**: 8 stron
- **Ciąg dostępów**: 0, 1, 7, 2, 3, 2, 7, 1, 0, 3

## a) FIFO (First In, First Out)
1. **Odwołanie do 0**
- Stan ramek: `0` - page fault
2. **Odwołanie do 1**
- Stan ramek: `1 0` - page fault
3. **Odwołanie do 7**
- Stan ramek: `7 1 0` - page fault
4. **Odwołanie do 2**
- Stan ramek: `2 7 1 0` - page fault
5. **Odwołanie do 3**
- Stan ramek: `3 2 7 1` - page fault
6. **Odwołanie do 2**
- Stan ramek: `3 2 7 1`
7. **Odwołanie do 7**
- Stan ramek: `3 2 7 1`
8. **Odwołanie do 1**
- Stan ramek: `3 2 7 1`
9. **Odwołanie do 0**
- Stan ramek: `0 3 2 7` - page fault
10. **Odwołanie do 3**
- Stan ramek: `0 3 2 7`

**Liczba page faultów**: 6

## b) LRU (Least Recently Used)
1. **Odwołanie do 0**
- Stan ramek: `0: 1` - page fault
2. **Odwołanie do 1**
- Stan ramek: `0: 1, 1: 2` - page fault
3. **Odwołanie do 7**
- Stan ramek: `0: 1, 1: 2, 7: 3` - page fault
4. **Odwołanie do 2**
- Stan ramek: `0: 1, 1: 2, 7: 3, 2: 4` - page fault
5. **Odwołanie do 3**
- Stan ramek: `3: 5, 1: 2, 7: 3, 2: 4` - page fault
6. **Odwołanie do 2**
- Stan ramek: `3: 5, 1: 2, 7: 3, 2: 6`
7. **Odwołanie do 7**
- Stan ramek: `3: 5, 1: 2, 7: 7, 2: 6`
8. **Odwołanie do 1**
- Stan ramek: `3: 5, 1: 8, 7: 7, 2: 6`
9. **Odwołanie do 0**
- Stan ramek: `0: 9, 1: 8, 7: 7, 2: 6` - page fault
10. **Odwołanie do 3**
- Stan ramek: `0: 9, 1: 8, 7: 7, 3: 10` - page fault

**Liczba page faultów**: 7

:::

## Zadanie 2
:::success
Autor: Katarzyna Trzos 
:::

## Zadanie 3
:::success
Autor: Borys Adamiak
## a)
Dla odniesień cyklicznych wymienione algorytmy bedą nadpisywać ciągle te same ramki
## b)
Rezerwujemy 499 ramek na strony 0-498
Dla reszty odniesien podmieniamy tylko jedna ramke
(Podmianki beda wykonane tylko cyklicznie 13 razy)
:::