# Lista 8
###### tags: `SO`

## Zadanie 1

## Zadanie 2

Fragmentacja wewnętrzna:
- skutek trzymania struktur danych
- wyrównania
- konsekwencja konkretnych polityk

Fragmentacja zewnętrzna:
- występuje, gdy mamy wystarczająco pamięci, ale nie w postaci spójnego bloku

**Czemu algorytm malloc nie może stosować kompaktowania?**

Nie możemy przesuwać pamięci nadanej użytkownikowi.

Dwie główne przyczyny fragmentacji:
- isolated deaths

Najbardziej opłaca się umieszczać obok siebie w pamięci fragmenty, które zostaną zwolnione w podobnym czasie.
Gdy fragment pamięci zostanie zwolniony "w odosobnieniu", stworzy dziurę w pamięci, będącą potencjalnym źródłem fragmentacji.

- zmiana zachowania w czasie

Zachowanie programu jest nieprzewidywalne. Alokator może próbować przewidzieć przyszłość. (np. zwalnianie wielu małych przydziałów i alokacja dużych)

## Zadanie 3

Alokacja, gdy potrzebujemy i zwolnienie, gdy już nie potrzebujemy:


Alokacja, gdy potrzebujemy i zwolnienie na końcu działania programu:



Alokacja od razu całej potrzebnej pamięci:



Związek między czasem życia a rozmiarem bloku:
Rozmiar bloku może sugerować typ, a różne typy mogą sugerować inne przeznaczenie - a zatem inny czas zwolnienia.

* first-fit
Szukamy pierwszego wolnego bloku, który jest w stanie pomieścić nasz blok. Jeśli wolny > nasz to robimy splita i pozostałą cześć zostawiamy jako wolnom
* Zalety
Jest szybki i prosty
* Wady
Tworzy wiele splitów na początku listy co powoduje, że musimy przejść przez wiele małych bloków jeśli chcemy zaalokować duży blok

* next-fit
Szukanie wolnego bloku zaczynamy tam gdzie skończyliśmy poprzednie szukanie i to samo co w first-fit
* Zalety
Jest szybszy
* Wady
Bardzo duża fragmentacja

* best-fit
Szuka najmniejszego wolnego bloku, który pomieści to co chcemy zaalokować
* Zalety
Niska fragmentacja
* Wady
Czas działania
Źle skaluje się przy wielu alokacjach małych bloków

## Zadanie 4

alloc(4) A
alloc(8) B
alloc(4) C
alloc(4) D
alloc(10) E
alloc(6) F
free(C) 
free(B) 
free(F) 
alloc(6) G
free(D) 
alloc(18) H

best-fit

+AAAA++__________________________________________+
+AAAA++BBBBBBBB++________________________________+
+AAAA++BBBBBBBB++CCCC++__________________________+
+AAAA++BBBBBBBB++CCCC++DDDD++____________________+
+AAAA++BBBBBBBB++CCCC++DDDD++EEEEEEEEEE++________+
+AAAA++BBBBBBBB++CCCC++DDDD++EEEEEEEEEE++FFFFFF+++
+AAAA++BBBBBBBB++____++DDDD++EEEEEEEEEE++FFFFFF+++
+AAAA++______________++DDDD++EEEEEEEEEE++FFFFFF+++
+AAAA++______________++DDDD++EEEEEEEEEE++________+
+AAAA++______________++DDDD++EEEEEEEEEE++GGGGGG+++
+AAAA++____________________++EEEEEEEEEE++GGGGGG+++
+AAAA++HHHHHHHHHHHHHHHHHH++++EEEEEEEEEE++GGGGGG+++

first-fit

+AAAA++__________________________________________+
+AAAA++BBBBBBBB++________________________________+
+AAAA++BBBBBBBB++CCCC++__________________________+
+AAAA++BBBBBBBB++CCCC++DDDD++____________________+
+AAAA++BBBBBBBB++CCCC++DDDD++EEEEEEEEEE++________+
+AAAA++BBBBBBBB++CCCC++DDDD++EEEEEEEEEE++FFFFFF+++
+AAAA++BBBBBBBB++_1__++DDDD++EEEEEEEEEE++FFFFFF+++
+AAAA++______________++DDDD++EEEEEEEEEE++FFFFFF+++
+AAAA++______________++DDDD++EEEEEEEEEE++___2____+
+AAAA++GGGGGG++__2___++DDDD++EEEEEEEEEE++___1____+
+AAAA++GGGGGG++____________++EEEEEEEEEE++___1____+
+AAAA++GGGGGG++____________++EEEEEEEEEE++___1____+ <- H się nie zmieści

## Zadanie 5

`malloc`:
1. Szuka kubełka o odpowiadającym rozmiarze
2. Szuka bloku o najmniejszym rozmiarze >= rozmiarowi żądanemu

`free`:
1. Gorliwie łączy zwolniony blok i wrzuca do odpowiedniego kubełka
2. Gorliwie łączy i dodaje na koniec kolejki

`malloc`, gdy nie ma miejsca:
1. Prosi o dodatkową pamięć, allokuje odpowiedni blok, resztę wrzuca do odpowiedniego kubełka
2. Prosi o dodatkową pamięć, allokuje odpowiedni blok, z reszty tworzy blok i wrzuca do kolejki

Gdzie przechowywać strażnika?
Na końcu każdej z list.

Jaki problem powoduje leniwe złączanie bloków w algorytmie kubełkowym?
4 - 3 - 4

## Zadanie 6

static void *alloc_block(int8_t *data, uint8_t len) {
    void *result = NULL;

    while (!END_OF_CHUNK(data)) {
//        printf("LOOP\n");
        if (BLOCK_USED(data)) {
            /* TODO: occupied block */
//            printf("B\n");
            MOVE_NEXT(data);
//            data = data + data[0];
        } else if (BLOCK_SIZE(data) == len) {
            /* TODO: free block of exact size */
//            printf("C\n");
            BLOCK_HEADER(data) = len;

            result = CURRENT_PTR(data);

            assert(BLOCK_HEADER(data) > 0);
            break;
        } else if (BLOCK_SIZE(data) > len) {
            /* TODO: free block is too large */
//            printf("D\n");

            int8_t prev = BLOCK_SIZE(data);
            BLOCK_HEADER(data) = len;
            NEXT_BLOCK_HEADER(data) = - (prev - len);


            result = CURRENT_PTR(data);

            assert(NEXT_BLOCK_HEADER(data) < 0);
            assert(BLOCK_HEADER(data) > 0);
            break;
        } else if (!NEXT_BLOCK_FREE(data)) {
            /* TODO: next block is occupied or does not exists */
//            printf("E\n");
            MOVE_NEXT(data);
            if (END_OF_CHUNK(data))
                break;
        } else if (NEXT_BLOCK_SIZE(data) <= len - BLOCK_SIZE(data)) {
            /* TODO: merge two free blocks, but do not allocate */
//            printf("F\n");
            BLOCK_HEADER(data) = -(BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data));

            assert(BLOCK_HEADER(data) < 0);
        } else {
            /* TODO: merge two free blocks and allocate with split */
            //Len 70
            //ACT: 34 NEXT: 127

//            printf("G\n");
//            printf("Len %d\n", len);

            int8_t next = NEXT_BLOCK_SIZE(data);
            int8_t act = BLOCK_SIZE(data);
            BLOCK_HEADER(data) = len;
            NEXT_BLOCK_HEADER(data) = -(next - len + act);


            result = CURRENT_PTR(data);

            assert(BLOCK_HEADER(data) > 0);
            assert(NEXT_BLOCK_HEADER(data) < 0);
            break;
        }
    }
    
    return result;
}


static void strfree(char *str) {
//    printf("FREE\n");
    if (str == NULL)
        return;
    int8_t *sstr = (int8_t *) str;
#if DEBUG_LEVEL > 0
    assert(sstr[-1] > 0);
    arena_t *ar = find_ptr_arena(&arenas, str);
    assert(ar != NULL);
#if DEBUG_LEVEL > 1
    int8_t *ptr = (int8_t *) ar + sizeof(arena_t);
    while (ptr < sstr - 1) {
        assert(*ptr != 0);
        ptr += (*ptr > 0 ? *ptr : -*ptr);
    }
    assert(ptr == sstr - 1);
#endif
#endif
    /* TODO: mark block as free */
    str[-1] *= -1;
    assert(str[-1] < 0);
}

## Zadanie 7

https://prod.liveshare.vsengsaas.visualstudio.com/join?E183DB0C991F450120F2B5C0BB19E0C72895

## Zadanie 8