# Systemy operacyjne lista 8 Przydział pamięci
## Zadanie 1 kasia

:::info
**sbrk()** changes the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory. sbrk() increments the program's data space by increment bytes. Calling sbrk() with an increment of 0 can be used to find the current location of the program break.

**mmap()** creates a new mapping in the virtual address space of the calling process. The starting address for the new mapping is specified in addr. The length argument specifies the length of the mapping (which must be greater than 0).

The **munmap()** system call deletes the mappings for the specified address range, and causes further references to addresses within the range to generate invalid memory references. The region is also automatically unmapped when the process is terminated. On the other hand, closing the file descriptor does not unmap the region.

:::

brk/sbrk is LIFO (last in first out). Let's say you increase the segment size by X number of bytes to make room for allocation A and X number of bytes to make allocation B, and then free A. You cannot reduce the allocated memory because B is still allocated. And since the segment is shared across the entire program, if multiple parts of the program use it directly, you will have no way of knowing whether particular part is still in use or not. And if one part of the program (let's say malloc) assumes entire control over the use of brk/sbrk, then calling them elsewhere will break the program.

By contrast, mmap can be unmapped in any order and allocation by one part of the program doesn't conflict with other parts of the program.

brk/sbrk are not part of the POSIX standard and thus not portable.

By contrast, mmap is standard and portable.

mmap can also do things like map files into memory which is not possible using brk/sbrk.

## Zadanie 2 Kuba
Wyjaśnij różnicę między fragmentacją wewnętrzną i zewnętrzną.

fragmentacja wewnętrzna – następuje w przypadku, gdy rozmiar alokowanej pamięci jest mniejszy niż rozmiar jednego bloku. Wówczas nadmiarowa pamięć marnuje się.

fragmentacja zewnętrzna – występuje gdy łączna suma wolnej pamięci jest wystarczająco duża do obsłużenia żądania alokacji, ale żaden z wolnych bloków nie jest wystarczająco duży i nie jest możliwa ich konsolidacja.

Czemu nie można zastosować kompaktowania w bibliotecznym algorytmie przydziału pamięci?

kompaktowanie – defragmentacja zaalokowanej pamięci poprzez przeniesienie bloków tak, aby leżały obok siebie, co eliminuje fragmentację zewnętrzną.

Nie można zastosować kompaktowania w bibliotecznym algorytmie przydziału pamieci, gdyż kompaktowanie unieważnia stare wskaźniki (wskaźnik przestaje być poprawny, gdyż odpowiadająca mu pamięć została przeniesiona pod inny adres i nie ma możliwości automatycznego zaktualizowania tych wskaźników).
Na podstawie §2.3 opowiedz o dwóch głównych przyczynach występowania fragmentacji zewnętrznej.

Fragmentation is caused by isolated deaths: krytycznym problemem jest tworzenie wolnych obszarów, których sąsiadujące obszary nie są wolne. Składają się na to dwie rzeczy: które obiekty zostają umieszczone w przyległych obszarach, i kiedy te obiekty umierają. Jeżeli obiekty zostają zwolnione w rożnych momentach, to powstają pomiędzy nimi przerwy.

Fragmentation is caused by time-varying behavior: fragmentacja powstaje przez to, że z upływem czasu może zmieniać się zachowanie programu w sensie tego, jakich alokacji dokonuje – np. zwalnianie małych bloków i alokowanie bardzo dużych, bądź alokowanie wielu obiektów różnych typów. Alokator powinien umieć zauważyć wzorce w alokacji w celu minimalizacji fragmentacji.

## Zadanie 3 Marcin

::: spoiler WYKRES :

:::
**first-fit** -
**next-fit** -
**best-fit** -

## Zadanie 4 Kornelia

**Dwukierunkowa lista wolnych bloków i boundary tag bez optymalizacji :**
**a = 1: Allocated block, a = 0: Free block
Size: Total block size**
Najmniejszy rozmiar wolnego bloku to 4 słowa (nagłówek, wskaźnik na poprzedni, wskaźnik na następny, stopka)

| Header | Next | Prev | Footer |
| ------ | ---- | ---- | ------ |

**Polityka best-fit** - alloc zwraca pierwszy wolny blok o najmniejszym rozmiarze ze wszystkich wolnych nie mniejszych niż rozmiar tego, co chcemy zaalokować

**Gorliwe złączanie bloków** - przy wywołaniu free powstaje nowy blok, jeśli poprzedni lub następny był wolny, to łączymy je w jeden (nigdy nie chcemy, żeby 2 wolne bloki ze sobą sąsiadowały)

*Symulacja*

zielona strzałka -> pierwszy element listy wolnych bloków, czerwona -> ostatni

Przy wywołaniu alloc(18) powstaje nieużytek o rozmiarze 2 słów (nie mogliśmy podzielić wolnego bloku o rozmiarze 22 słów na blok o rozmiarze 20 dla alloca i pusty o rozmiarze 2, bo minimalny rozmiar pustego bloku to 4 słowa).

Gdyby algorytm wykożystywał strategię first-fit, to przedostatnie wywołanie alloca (alloc(6)) podzieliłoby wolny blok o rozmiarze 16 na zajęty o rozmiarze 8 i wolny o rozmiarze 8. Nawet po wywołaniu free(2) nie mielibyśmy tak dużego wolnego bloku, żeby następny alloc(18) się powiódł bez powiększenia tablicy.


## Zadanie 5 Olek

:::info
**Algorytm kubełkowy** (*segregated-fit*) - polega na przechowywaniu list wolnych bloków pamięci, ze względu na rozmiar tych bloków. W momencie wykonywania alokacji wybiera się wolny blok z listy, która przechowuje bloki o najmniejszym wystarczającym rozmiarze.

**Węzeł strażnik** (*sentinel node*) - specjalny wyznaczony węzeł używany z listami połączonymi i drzewami jako terminator ścieżki przejścia.

**Złączanie leniwe** (*deferred coalescing*) polega na łaczeniu bloków dopiero w momencie, gdy kolejny raz chcemy zaalokować pamieć i nie napotkaliśmy bloku o wystarczająco dużym rozmiarze.

:::

> Jak przebiegają operacje `malloc` i `free`?
> Co robi `malloc`, gdy na dane liście nie ma wolnego bloku żądanego rozmiaru?

`malloc` -> wybierany jest odpowiedni najmniejszy kubełek, w przypadku gdy ten kubełek zawiera wolny blok, to blok ten jest usuwany z z listy i oznaczany jako zajęty, zwracany jest wskaźnik na ten blok.
W przypadku gdy kubełek nie zawiera wolnego bloku, należy szukać w kolejnym większym kubełku.
W momencie znalezienia wolnego bloku wykonywany jest podział, alokujemy pamięć a pozostałe miejsce jest umieszczane w kubełku odpowiedniej wielkości. W przypadku gdy wszystkie kubełki są zajęte prosimy jądro o powiększenie sterty przy pomocy `sbrk()`

`free` -> oznacza blok jako wolny, a następnie jeśli sąsiadujący blok jest wolny, są one łączone. Finalny cały wolny blok jest umieszczany w odpowiednim kubełku.

> Gdzie należałoby przechowywać **węzeł strażnik** (*sentinel node*) każdej z list wolnych bloków?

Najpewniej chcemy umieścić naszego wartownika na końcu listy, tak aby zwalnianie ostatniego bloku nie było problematyczne. To znaczy po przejściu całej listy, chcemy zacząć przeglądanie kolejnej.

> Rozważ zastosowanie **leniwego złączania** wolnych bloków w algorytmie kubełkowym przydziału pamięci - jakie probelmy zauważasz?

Gdybyśmy chcieli leniwie złączać bloki, moglibyśmy zmniejszyć czas wyszukiwania bloków przy małych alokacjach. Problemem wynikającym z tego podejścia jest zwiększenie fragmentacji.

---

## Zadanie 6

## Zadanie 7

## Zadanie 8(bonus)