---
# System prepended metadata

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

---

# Ć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	
![image](https://hackmd.io/_uploads/rkaxCO3Q0.png)

## 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		![IMG_0475](https://hackmd.io/_uploads/BkcsZ_hQA.jpg)	
:::

## Zadanie 3
:::success
Autor: 	Borys Adamiak	
![image](https://hackmd.io/_uploads/HJAsO13mA.png)
![image](https://hackmd.io/_uploads/r1whuJ2Q0.png)
## 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)
:::



