---
# System prepended metadata

title: Lista 13 (10 czerwca 2021)
tags: [kba, ask21, ćwiczenia]

---

# Lista 13 (10 czerwca 2021)

###### tags: `ask21` `ćwiczenia` `kba`

## 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
|                       |  1  | 2(2) |  3  |  4  |  5  |  6  |
| ---------------------:| --- |:----:| --- | --- | --- | --- |
|         Andriy Bernad |  X  |      |     |     |     |     | 1
|      Wojciech	Bogucki |  X  |  X   |     |     |     |     | 3
|          Michał Doros |  X  |  X   | X   |  X  |   X | X   | 7
|         Marko Golovko |     |      |     |     |     |     | 0
|     Magdalena Jarecka |     |      |     |     |     |     | 0
|         Szymon Jędras |  X  |  X   |     |     |     |     | 3
|      Heorhii Karpenko |  X  |      |     |     |  X  |     | 2
|     Szymon Kosakowski |     |      |     |     |     |     | 0
|       Izabella Kozioł |     |      |     |     |     |     | 0
|    Franciszek Malinka |  X  |  X   | X   |  X  |   X | X   | 7
|          Filip Pazera |     |      |     |     |     |     | 0
|     Franciszek Pindel |  X  |  X   |     |     |     |     | 3
|      Kacper Puchalski |  X  |  X   | X   |     |     |     | 4
|        Kacper Solecki |  X  |  X   |  X  |  X  |  X  |  X  | 7
|       Andrzej Tkaczyk |  X  |      |     |     |     |     | 1
|     Łukasz Wasilewski |     |      |     |     |     |     | 0
|  Vladyslav Yablonskyi |     |      |     |     |  X  |     | 1
|            Adam Zyzik |  X  |  X   |     |     |     |     | 2
:::

## Zadanie 1

:::info
Autor: Andrzej Tkaczyk
:::
W czasie wykonywania programu procesor układa kolejne instrukcje na kolejce do wykonania. Gdy napotka skok warunkowy mamy rozgałęzienie i są dwie możliwości na ułożenie instrukcji w kolejce. Wtedy często nie wiadomo jeszcze jaka jest wartość warunku i który wariant do ułożenia kolejki wybrać. Procesor, żeby nie marnować czasu na bezczynne czekanie aż policzy wartość warunku, próbuje przewidzieć jego wartość i ułożyć na kolejce odpowiednie instrukcje.

**Predyktor skoków** - algorytm używany do przewidywania którą gałęzią pójdzie program.

W momencie w którym okaże się, że procesor się pomylił i wybrał złą gałąź, wszystkie obliczone wartości związane z tą gałęzią muszą zostać wyrzucone do śmieci, a na kolejkę muszą zostać wrzucone instrukcje z dobrej gałęzi.

Do instrukcji cmov warto optymalizować skoki które nie są łatwo przewidywalne, bo jeśli skoki są przewidywalne, to procesor nie płaci kar za złe przewidywania, bo ich nie robi.

#### oryginalna wersja:
```c=
void merge1(long src1[], long src2[], long dest[], long n) {
    long i1 = 0, i2 = 0;
    while (i1 < n && i2 < n)
        *dest++ = src1[i1] < src2[i2] ? src1[i1++] : src2[i2++];
}
```
```asm=
merge1:
        testq   %rcx, %rcx
        jle     .L1
        movl    $0, %r8d
        movl    $0, %eax
        jmp     .L5
.L3:
        addq    $1, %r8
        movq    %r10, %r9
.L4:
        addq    $8, %rdx
        movq    %r9, -8(%rdx)
        cmpq    %r8, %rax
        movq    %r8, %r9
        cmovge  %rax, %r9
        cmpq    %rcx, %r9
        jge     .L1
.L5:
        movq    (%rdi,%rax,8), %r9
        movq    (%rsi,%r8,8), %r10
        cmpq    %r10, %r9
        jge     .L3
        addq    $1, %rax
        jmp     .L4
.L1:
        ret
```
#### wersja z cmov:
```c=
void merge1a(long src1[], long src2[], long dest[], long n) {
    long i1 = 0, i2 = 0;
    while (i1 < n && i2 < n) {
        long a = src1[i1];
        long b = src2[i2];
        long c = a < b;
        *dest++ = a < b ? a : b;
        i1 += c;
        i2 += c^1;
    }
}
```
```asm=
merge1a:
        movq    %rdi, %r10
        movq    %rsi, %r11
        testq   %rcx, %rcx
        jle     .L7
        movl    $0, %esi
        movl    $0, %eax
.L9:
        movq    (%r10,%rax,8), %r8
        movq    (%r11,%rsi,8), %rdi
        addq    $8, %rdx
        cmpq    %rdi, %r8
        movq    %rdi, %r9
        cmovle  %r8, %r9
        movq    %r9, -8(%rdx)
        setl    %r9b
        movzbl  %r9b, %r9d
        addq    %r9, %rax
        cmpq    %rdi, %r8
        setge   %dil
        movzbl  %dil, %edi
        addq    %rdi, %rsi
        cmpq    %rsi, %rax
        movq    %rsi, %rdi
        cmovge  %rax, %rdi
        cmpq    %rcx, %rdi
        jl      .L9
.L7:
        ret
```


## Zadanie 2

:::success
Autor: Franciszek Pindel
:::

> Pobierz ze strony przedmiotu archiwum «ask21_lista_13.tgz», rozpakuj je i zapoznaj się z kodem źródłowym w pliku «dictionary.c». Powtórz eksperyment z [1, §5.14], tj.: uruchom program, poczekaj na wyniki profilowania, a następnie na podstawie wydruku wskaż kandydata do optymalizacji. Zmień dokładnie jedenz argumentów przekazywanych do polecenia «make gprof»: SIZE=N, HASH=0/1/2, FIND=0/1/2, LOWER=0/1, QUICK=0/1. Odpowiednia opcja zmieni rozmiar tablicy mieszającej N lub ustali wersję implementacji jednej z kluczowych funkcji w programie. Wyjaśnij co zmieniło przekazanie danej opcji. Powtarzaj powyższe kroki tak długo, aż uzyskasz najkrótszy czas wykonania programu.

* **profilowanie** - analiza zachowania programu w trakcie uruczomienia - polega na mierzeniu np. używanej pamięci albo liczby wywołań poszczególnych funkcji

Z profilu płaskiego wynika że większość czasu zajmuje posortowanie elementów (`sort wrods`), co nie dziwi, bo to jest zaimplementowane jako insertion sort

```
size	1021
hash	1
lower	0
find	0
ngram	2
quicksort	0

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 98.00    298.75   298.75        1   298.75   298.75  sort_words
  1.88    304.47     5.72   965027     0.00     0.00  find_ele_rec
  0.21    305.11     0.64   965027     0.00     0.00  lower1
  0.05    305.26     0.15   965027     0.00     0.00  h_mod
  0.03    305.36     0.10   965028     0.00     0.00  get_token
  0.01    305.40     0.05   363039     0.00     0.00  save_string
  0.01    305.42     0.02   965027     0.00     0.00  
```

Po zmianie algorytmu na quicksort widać znaczącą poprawę, oraz widać że najwięcej czasu zabiera znajdywanie elementów (`find-ele_rec`)

```
size	1021
hash	1
lower	0
find	0
ngram	2
quicksort	1

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 93.17     11.42    11.42   965027     0.00     0.00  find_ele_rec
  2.66     11.75     0.33   965027     0.00     0.00  lower1
  1.47     11.93     0.18                             compare_ele
  0.98     12.05     0.12   965028     0.00     0.00  get_token
  0.57     12.12     0.07        1     0.07     0.07  sort_words
  0.41     12.17     0.05   965027     0.00     0.00  insert_string
```

Próba zmiany z wersji rekurencyjnej na iteracyjną nie przynosi poprawy, a nawet psuje (powodem jest umieszczanie elementów na początku listy zamiast na końcu, co powoduje że częściej pojawiające się elementy znajdą się na końcu listy, co wydłuża czas ich wyszukiwania - szczegóły polecam sobie doczytać, tutaj są mało istotne)

```
size	1021
hash	1
lower	0
find	1
ngram	2
quicksort	1


Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 95.00     22.15    22.15   965027     0.00     0.00  find_ele_iter_f
  2.71     22.79     0.63   965027     0.00     0.00  lower1
  0.52     22.91     0.12   965027     0.00     0.00  insert_string
  0.47     23.02     0.11   965028     0.00     0.00  get_token
  0.47     23.13     0.11                             compare_ele
  0.39     23.22     0.09   965027     0.00     0.00  h_add
  0.30     23.29     0.07        1     0.07     0.07  sort_words
  0.26     23.35     0.06   363039     0.00     0.00  new_ele
  0.04     23.36     0.01   965029     0.00     0.00  get_word
  0.04     23.37     0.01                             find_ele_rec
  0.00     23.37     0.00   363039     0.00     0.00  save_string
```

Zmiana na wersję iteracyjną z umieszczaniem elementów na końcu daje nieznaczne przyspieszenie (albo i nie):

```
size	1021
hash	1
lower	0
find	2
ngram	2
quicksort	1


Flat profile:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 92.74     14.83    14.83   965027     0.00     0.00  find_ele_iter_r
  4.04     15.48     0.65   965027     0.00     0.00  lower1
  1.00     15.64     0.16   965028     0.00     0.00  get_token
  0.75     15.76     0.12   965027     0.00     0.00  insert_string
  0.56     15.85     0.09                             compare_ele
  0.50     15.93     0.08        1     0.08     0.08  sort_words
  0.22     15.96     0.04   965027     0.00     0.00  h_add
  0.13     15.98     0.02   363039     0.00     0.00  new_ele
  0.06     15.99     0.01                             Strlen             
```

Zwiększenie rozmiaru tablicy mieszającej nie daje poprawy, bo algorytm haszujący daje wyniki z małego przedziału

```
size	199999
hash	1
lower	0
find	2
ngram	2
quicksort	1

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 93.42     13.66    13.66   965027     0.00     0.00  find_ele_iter_r
  4.18     14.27     0.61   965027     0.00     0.00  lower1
  0.82     14.39     0.12   965028     0.00     0.00  get_token
  0.48     14.46     0.07   965027     0.00     0.00  insert_string
  0.41     14.52     0.06        1     0.06     0.06  sort_words
  0.34     14.57     0.05                             compare_ele
```

Dopiero zmiana algorytmu hashującego pozwala zredukować czas wykonania:

```
size	199999
hash	2
lower	0
find	2
ngram	2
quicksort	1


Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 50.78      0.38     0.38   965027     0.00     0.00  lower1
 12.19      0.47     0.09                             compare_ele
 12.19      0.56     0.09   965027     0.00     0.00  find_ele_iter_r
  6.77      0.61     0.05   965027     0.00     0.00  insert_string
  5.42      0.65     0.04   965028     0.00     0.00  get_token
  4.06      0.68     0.03   965027     0.00     0.00  h_xor
  2.71      0.70     0.02   965029     0.00     0.00  get_word
  2.71      0.72     0.02        1    20.04    20.04  sort_words
  1.35      0.73     0.01   363039     0.00     0.00  save_string
  1.35      0.74     0.01                             find_ele_iter_f
```

Pozostaje polepszyć strlen która w tym kodzie ma złożoność kwadratową, ulepszona wersja nieznacznie przyspiesza program:

```
size	199999
hash	2
lower	1
find	2
ngram	2
quicksort	1


Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 34.03      0.18     0.18   965027     0.00     0.00  find_ele_iter_r
 20.80      0.29     0.11   965027     0.00     0.00  insert_string
 11.34      0.35     0.06                             compare_ele
  9.45      0.40     0.05   965028     0.00     0.00  get_token
  7.56      0.44     0.04        1    40.08    40.08  sort_words
  3.78      0.46     0.02   965027     0.00     0.00  h_xor
  3.78      0.48     0.02   965027     0.00     0.00  lower2
  3.78      0.50     0.02   363039     0.00     0.00  save_string
```

## Zadanie 3

:::danger
Autor: Franciszek Malinka
:::

**Graf wywołań funkcji** - skierowany graf ilustrujący kolejność wywoływanych funkcji i relację między funkcjami wyłowującymi, a wywołanymi.

![](https://i.imgur.com/pOt0lLa.png)

Graf został wygenerowany przy pomocy narzędzia *kcachegrind*. Każdy bloczek przedstawia jedną funkcję, krawędzie są skierowane z funkcji wołających do funkcji wołanych. Przy każdym bloczku napisany jest procentowy czas działania programu, który został spędzony w danej funkcji (sumarycznie we wszystkich jej wywołaniach).

Wywołania funkcji biblioteki standardowej C to te, których nazwy bloczków są liczbami (prawdopodobnie są to adresy wirtualne z poziomy procesu, do których odwoływał się wywołując funkcje z bibliotek współdzielonych).

Funkcje biblioteczne, w których program spędził najwięcej czasu:
- strtok (30.67%)
- malloc (10.59%)
- qsort (9.51%)

Nie mamy możliwości optymalizacji samych funkcji bibliotecznych, ale mamy możliwość np. ograniczenia liczby wywołań tych funkcji, np. zamiast alokować pamięc dopiero wtedy, kiedy chcemy dodać nowy element do hashmapy, możemy alokować za każdym razem trochę więcej pamięci (np. za każdym razem 1.5 razy więcej pamięci), żeby robić mało "dużych" malloców, zamiast dużo "małych". To zapobiega fragmentacji pamięci i zmniejsza liczbę wywołań systemowych, co wpływa na performance naszego progrmau.


## Zadanie 4

:::success
Autor: Michał Doros
:::

**fizyczna przestrzen adresowa**
zakres adresow ktore reprezentuja komorki pamieci glownej, a takze urzadzenia I/O 

**translacja adresow**
Wykonywana przez MMU - memory management unit
Tlumaczenie adresu wirtualnego na fizyczny przy pomocy ponizszego wzoru
PFN odczytywane z tabeli stron (page table)
![](https://i.imgur.com/wFz7lU2.png)

Strona ma 4096 bajtow = 2^12 B, zatem offset to ostatnie 3 cyfry 16-kowe

address = PFN * page_size + offset
Dla adresu:
0x55e7926f3000     : pfn 249dac
address = 0x249dac * 0x1000 + 0x000 = 0x249dac000
w System RAM



**numer ramki**
adres fizyczny podzielony przez rozmiar strony


mapa pamici fizycznej
![](https://i.imgur.com/E4ViOq0.png)

mapa pamieci wirtualnej procesu 2566
![](https://i.imgur.com/qUdfRDN.png)


## Zadanie 5

:::success
Autor: Grzegorz Karpenko
:::

**Pamięć wirtualna** – mechanizm zarządzania pamięcią komputera zapewniający procesowi wrażenie pracy w jednym, dużym, ciągłym obszarze pamięci operacyjnej, podczas gdy fizycznie może być ona pofragmentowana, nieciągła i częściowo przechowywana na urządzeniach pamięci masowej.

**RSS** to Resident Set Size i służy do  pokazywania rozmiaru stron pamięci przydzielonych przez system operacyjny i aktualnie znajdujących się w pamięci RAM (RAM). Ale w rzeczywistości nie jest to dokładny pomiar wykorzystania pamięci RAM dla procesu, ponieważ nie uwzględnia bibliotek już załadowanych do pamięci. 
Jeśli dwa procesy używają jednej lub więcej bibliotek, wtedy RSS doda rozmiary bibliotek dla każdego procesu, nawet jeśli biblioteki byłyby już wcześniej załadowane w przypadku jednego procesu rozpoczynającego się po drugim. Więc czasami jeśli dodamy wszystko na liście procesów, otrzymamy więcej pamięci niż całkowita przydzielona pamięć.

**VSZ** to skrót od Virtual Memory Size. Jest to całkowita ilość pamięci, do której hipotetycznie może uzyskać dostęp proces. Uwzględnia rozmiar pliku binarnego, wszelkich połączonych bibliotek i wszelkich alokacji stosu lub sterty. 

**Stronicowanie na żądanie** jest metodą zarządzania pamięcią wirtualną. W systemie korzystającym ze stronicowania na żądanie system operacyjny kopiuje stronę dysku do pamięci fizycznej tylko wtedy, gdy podjęto próbę uzyskania dostępu do niej, a strona nie znajduje się już w pamięci.

**Pamięć współdzielona** jest specjalnie utworzonym segmentem wirtualnej przestrzeni adresowej, do którego dostęp może mieć wiele procesów. Jest to najszybszy sposób komunikacji pomiędzy procesami.

:::spoiler
![](https://i.imgur.com/jxihIwC.png)
![](https://i.imgur.com/VLJYXpj.png)
Napewno nie mam 32Gb RAM !
:::
:::spoiler
![](https://i.imgur.com/SLljzie.png)

:::

## Zadanie 6

:::success
Autor: Kacper Solecki
:::

**pamięć wymiany (swap)** - pamięć procesów trzymana na dysku twardym, gdy RAM jest przepełniony

![](https://i.imgur.com/KrL7Rib.png)

Karty na chrome wyświetlające miliony particli:
![](https://i.imgur.com/r5HpznW.png)



**zbiór roboczy** - pamięć, której proces używa w danym przedziale czasowym (lub ostatnie $k$ stron do których były odwołania)

Aproksymacja zbioru roboczego:
System kiedy zdarzy się page fault skanuje strony pamięci - sprawdza, do których stron pamięci odwoływały się procesy od czasu ostatniego czyszczenia bitu Referenced. 
(strony pamięci mają bit 'Referenced' ustawiany w stałych odstępach czasu na 0). 
Strony, ze zgaszonym bitem Referenced, których jednocześnie ostatnie odwołanie było dawniej niż pewne ustalone $t$ uznawane są za nie będące w zbiorze roboczym - a więc są potencjalnymi ofiarami do przeniesienia na dysk (swap).
Jeżeli wszystkie strony mają zapalony bit Referenced ofiarą jest najdawniej używana strona.
Strony, które były używane mają aktualizowany czas ostatniego użycia na czas obecnego skanu.

![](https://i.imgur.com/9VTbSuX.gif)


**zbiór rezydentny** - część pamięci procesu, która obecnie znajduje się w RAMie.

**pamięć drugorzędna** - Pamięć, do której dostęp jest wolny, ale jest trwała (w znaczeniu - nie potrzebuje zasilania, aby trzymać dane), zwykle ma dużą pojemność, np. dyski twarde, pamięć urządzeń przenośnych

System używa pamięci drugorzędnej, gdy zabraknie miejsca w pamięci operacyjnej, przy wymianie danych z urządzeniami I/O, zapisuje tam dane, by nie zniknęły przy odłączeniu od prądu.  

> Co dzieje się z systemem, jeśli łączny rozmiar zbiorów
roboczych wszystkich procesów jest większy niż rozmiar pamięci fizycznej?

**trashing** - System drastycznie spowalnia, odwołania do pamięci na dysku są bardzo wolne, a brakuje nam miejsca by trzymać całą aktualnie używaną pamięć w RAMie.