---
# System prepended metadata

title: Lista 8
tags: [SO2022]

---

# Lista 8
###### tags: `SO2022`
![](https://i.imgur.com/Njwkyor.png)
![](https://i.imgur.com/HyzTSkd.png)

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

## Deklaracja
:::spoiler

| Zadanie   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|-----------|---|---|---|---|---|---|---|---|
|Deklaracja |:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:white_check_mark:||||

:heavy_check_mark:
:::

## Zadanie 1
![](https://i.imgur.com/81baMvx.png)

* ### Jakie są wady stosowania `sbrk` do zarządzania rozmiarem sterty przez biblioteczny algorytm zarządzania pamięcią `malloc(3)`?
    ![](https://i.imgur.com/fDCcoc9.png)
    `sbrk` może przesuwać `program break` tylko w górę i w dół, więc jeżeli przesuniemy `program break` w górę żeby zaalokować zmienną x, a później jeszcze raz przesuniemy w górę by zaalokować zmienną y i zmienna x przestanie być potrzebna to nie możemy przesunąć program break w dół bo stracilibyśmy zmienną y.

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

* ### Jak można to poprawić przy pomocy `mmap` i `munmap`? 
    Używanie `mmap` i `munmap` daje nam możliwość na dostęp (usuwanie itp) "starych" bloków, więc większe struktury danych możemy zaallokować w innym miejscu niż tym dostępnym przez `sbrk`

* ### Kiedy procedura `free` może zwrócić pamięć do jądra?
    `free` można używać na pamięci z `malloca`

    ```
    free()
           The  free() function frees the memory space pointed to by ptr, which must have been returned by
           a previous call to malloc() or related functions.  Otherwise, or if ptr has already been freed,
           undefined behavior occurs.  If ptr is NULL, no operation is performed.
    ```    
    [FreeBSD MAN](https://www.freebsd.org/cgi/man.cgi?query=sbrk&sektion=2)

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


## Zadanie 2
![](https://i.imgur.com/MgoFhYn.png)

* ### Wyjaśnij różnicę między `fragmentacją wewnętrzną` i `zewnętrzną`. 
    * fragmentacja wewnętrzna
        polega na podziale wewnetrznym jedego bloku np. jeden blok na rozmiar
        ![](https://i.imgur.com/TAISOU3.png)
        
    * fragmentacja zewnętrzna
        znawisko to zachodzi gdy mamy odpowiednią ilość wolnej pamięci ale nie możemy jej użyć ze względu na jej rozrzucenie po całej pamięci(wiele małych bloków)
        ![](https://i.imgur.com/vG3bhYM.png)


* ### Czemu algorytm malloc nie można stosować `kompaktowania`? 
    * W przypadku przeprowadzeina kompaktowania przesuwalibyśmy miejsca w pamięci, a w wielu miejscach programu możemy mieć w tym czasie wskaźniki na to miejsce, więc musilibyśy wszystkie te wskaźniki podmienić
    * malloc musbu być cały czas dostępny i odrazu odpowiadać na żądania bez kolejkowania

* ### Opowiedz o dwóch głównych przyczynach występowania `fragmentacji zewnętrznej`.
    ![](https://i.imgur.com/QkLGAn4.png)

    * czas życia zamiennych
    * program zmienia zachowanie najpierw małe zmienne potem duże



## Zadanie 3
![](https://i.imgur.com/TtJzveI.png)

* ### Opowiedz o trzech wzorcach przydziału pamięci występujących w programach.
    ![](https://i.imgur.com/cPi4iJq.png)
    ![](https://i.imgur.com/rR23He8.png)
    ![](https://i.imgur.com/C3oPaPH.png)


* ### Wyjaśnij jaki jest związek między czasem życia bloku, a jego rozmiarem?
    * Obiekty zaalokowane w tym samym czasie z dużym prawdopodobieństwem umrą w tym samym czasie
    * Obiekty o róznych typach służą do innych zastosowań, zatem prawdopodobnie umrą w innym czasie
    :::spoiler
    ![](https://i.imgur.com/l12GDVd.png)
    ![](https://i.imgur.com/IKRrFix.png)

    ---
    ![](https://i.imgur.com/wsOhKC6.png)
    ![](https://i.imgur.com/wJDH32b.png)
    :::


* ### Wyjaśnij różnice między politykami znajdowania wolnych bloków i wymień ich mocne i słabe strony:
    * `first-fit`
    * `next-fit`
    * `best-fit `
![](https://i.imgur.com/H7ge6aF.png)



## Zadanie 4
![](https://i.imgur.com/Fb7zrc5.png)

* ### Wykonaj krokową symulację algorytmu przydziału pamięci dla poniższego ciągu żądań.
![](https://i.imgur.com/UIWaC5z.png)

* Start
    ![](https://i.imgur.com/K0VNl5n.png)
* `alloc(4)`
    ![](https://i.imgur.com/uGuUfa2.png)
* `alloc(8)`
    ![](https://i.imgur.com/sj4WL4m.png)
* `alloc(4)`
    ![](https://i.imgur.com/kHYlE5Q.png)
* `alloc(4)`
    ![](https://i.imgur.com/1id1Fth.png)
* `alloc(10)`
    ![](https://i.imgur.com/OHOl0WW.png)
* `alloc(6)`
    ![](https://i.imgur.com/7yGkOBs.png)
* `free(C)`
    ![](https://i.imgur.com/45PgwKv.png)
* `free(B)`
    ![](https://i.imgur.com/XnLMUHB.png)
* `free(F)`
    ![](https://i.imgur.com/5L3cuen.png)

* `alloc(6)`
    * best-fit
        ![](https://i.imgur.com/nBoa7h2.png)
    * first-fit
        ![](https://i.imgur.com/OTiJR7S.png)
* `free(D)`
    * best-fit
        ![](https://i.imgur.com/DnGL9Wy.png)
    * first-fit
        ![](https://i.imgur.com/fgHuti9.png)

* `alloc(18)`
    * best-fit
        ![](https://i.imgur.com/NfolzI5.png)
    * first-fit
        Nie udało się :(
        ![](https://i.imgur.com/gbpVoBD.png)

## Zadanie 5
![](https://i.imgur.com/H3cNaNB.png)

* ### Porównaj go z algorytmem, który zarządza jedną listą wolnych bloków zgodnie ze strategią `best-fit`. 
    ![](https://i.imgur.com/wg1jcdm.png)

* ### Jak przebiegają operacje `malloc` i `free`?

* ### Co robi `malloc`, gdy na danej liście nie ma wolnego bloku żądanego rozmiaru?
    Przechodzi do listy o większym rozmiarze znajduje miejsce i odpowiednio ją dzieli.

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

* ### Rozważ zastosowanie `leniwego złączania` wolnych bloków w algorytmie kubełkowym przydziału pamięci – jakie problemy zauważasz?

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

    Problem rozwiazywany przez leniwe zlaczania: musielibysmy czesciej szukac duzych blokow i je rozbijac na mniejsze, zamiast uzywac blokow odpowiednich rozmiarow jesli bysmy uzywali czesto podobnych rozmiarow obiektow
    Problem spowodowany przez leniwe zlaczania: nadmierna fragmentacja
    :::spoiler
    ![](https://i.imgur.com/qu1BUu9.png)
    ![](https://i.imgur.com/2kw4AiY.png)
    ![](https://i.imgur.com/uVWzgu8.png)
    ![](https://i.imgur.com/d3AIXpb.png)
    ![](https://i.imgur.com/GoLT5JK.png)

    Deferred Coalescing
    ![](https://i.imgur.com/NkRY71T.png)
    ![](https://i.imgur.com/sxud2f5.png)
    ![](https://i.imgur.com/fA5Ljp6.png)
    ![](https://i.imgur.com/VMHyaN7.png)
    :::





## Zadanie 6
![](https://i.imgur.com/AXXZ8es.png)
![](https://i.imgur.com/dVXrkib.png)
```c
#include "csapp.h"
#include "arena.h"

#define MAX_LENGTH 126
#define MAX_BLKSZ (MAX_LENGTH + 1)

#define DEBUG_LEVEL 2

static arenalist_t arenas = STAILQ_HEAD_INITIALIZER(arenas);
static arena_t *cur_arena = NULL;
static unsigned cur_offset;

static void init_chunk(void *ar) {
  uint8_t *data = ar;
  unsigned offset = sizeof(arena_t);

  while (offset + MAX_BLKSZ < ARENA_SIZE) {
    data[offset] = -MAX_BLKSZ;
    offset += MAX_BLKSZ;
  }

  data[offset] = -(ARENA_SIZE - 1 - offset);
  data[ARENA_SIZE - 1] = 0;
}

#define BLOCK_HEADER(data) (data[cur_offset])
#define END_OF_CHUNK(data) (BLOCK_HEADER(data) == 0)
#define BLOCK_USED(data) (BLOCK_HEADER(data) > 0)
#define BLOCK_SIZE(data) (abs(BLOCK_HEADER(data)))

#define NEXT_BLOCK_HEADER(data) (data[cur_offset + BLOCK_SIZE(data)])
#define NEXT_BLOCK_FREE(data) (NEXT_BLOCK_HEADER(data) < 0)
#define NEXT_BLOCK_SIZE(data) (abs(NEXT_BLOCK_HEADER(data)))

#define MOVE_NEXT(data) cur_offset += BLOCK_SIZE(data)
#define CURRENT_PTR(data) (data + cur_offset + 1)

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

  while (!END_OF_CHUNK(data)) {
    if (BLOCK_USED(data)) {
      /* TODO: occupied block */
      MOVE_NEXT(data);
    } else if (BLOCK_SIZE(data) == len) {
      /* TODO: free block of exact size */
      BLOCK_HEADER(data)=BLOCK_SIZE(data);
      result=CURRENT_PTR(data);
      break;
    } else if (BLOCK_SIZE(data) > len) {
      /* TODO: free block is too large */
      int8_t split = BLOCK_SIZE(data)-len;
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data)=-split;
      result = CURRENT_PTR(data);
      break;
    } else if (!NEXT_BLOCK_FREE(data)) {
      /* TODO: next block is occupied or does not exists */
      MOVE_NEXT(data);

    } else if (NEXT_BLOCK_SIZE(data) <= len - BLOCK_SIZE(data)) {
      /* TODO: merge two free blocks, but do not allocate */
      int8_t merge=BLOCK_SIZE(data)+NEXT_BLOCK_SIZE(data);
      BLOCK_HEADER(data)=-merge;
    } else {
      /* TODO: merge two free blocks and allocate with split */
      int8_t merge=BLOCK_SIZE(data)+NEXT_BLOCK_SIZE(data);
      int8_t second_block_size=merge-len;
      BLOCK_HEADER(data)=len;
      if(second_block_size!=0){
        NEXT_BLOCK_HEADER(data)=-second_block_size;
      }
      result=CURRENT_PTR(data);
      break;
    }
  }
  return result;
}

static char *stralloc(size_t len) {
  assert(len <= MAX_LENGTH);

  if (len == 0)
    return NULL;

  if (cur_arena == NULL) {
    /* there are no arenas yet */
    init_chunk(alloc_first_arena(&arenas));
    cur_arena = STAILQ_FIRST(&arenas);
    cur_offset = sizeof(arena_t);
  }

  arena_t *ar = cur_arena;
  char *ptr;

  while (!(ptr = alloc_block((int8_t *)ar, len + 1))) {
    /* no space left on the current arena, move to the next one */
    ar = STAILQ_NEXT(ar, arenalink);
    cur_offset = sizeof(arena_t);

    /* that was the last arena, move to the first one */
    if (ar == NULL)
      ar = STAILQ_FIRST(&arenas);

    if (ar == cur_arena) { /* we've checked all arenas on the list. */
      init_chunk(alloc_after_arena(&arenas, ar));
      ar = STAILQ_NEXT(ar, arenalink);
    }
  }

  cur_arena = ar;
  return ptr;
}

static void strfree(char *str) {
  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 */
  assert(*ptr>0);
  *ptr *=-1;
}

static void strmemcheck(void) {
  arena_t *ar;
  STAILQ_FOREACH(ar, &arenas, arenalink) {
    const int8_t *data = (const int8_t *)ar;
    unsigned offset = sizeof(arena_t);
    while (offset != ARENA_SIZE - 1) {
      assert(offset < ARENA_SIZE);
      assert(data[offset] != 0);
      offset += abs(data[offset]);
    }
    assert(data[offset] == 0);
  }
}

/* The test */

#define MAX_PTRS 10000
#define MAX_LEN 100
#define CYCLES 100

static void *alloc_fn(int *lenp) {
  *lenp = rand() % (MAX_LEN + 1);
  return stralloc(*lenp);
}

#define free_fn(ptr) strfree(ptr)
#define memchk_fn() strmemcheck()

#include "test.h"

```

## Zadanie 7
![](https://i.imgur.com/zy98buh.png)

## Zadanie 8
![](https://i.imgur.com/cOclf3T.png)
