Zadania

  1. average_rating.c: dla pliku title.ratings.tsv.gz (dostępny tutaj), wylicz średnią ocenę w serwisie IMDb. Wczytaj plik w programie (a nie np. przekaż na standardowe wejście), stosując funkcje fopen. Parsowanie pól wykonaj z wykorzystaniem funkcji scanf (lub innych funkcji biblioteki języka C). Nie dodawaj plików title.ratings.tsv.gz i title.ratings.tsv do repozytorium.

  2. stack_freelist.c: Usprawnij listową implementację stack.c przez wykorzystanie techniki free list

  3. bst_bump_alloc.c: Zmień implementację bst.c z poprzednich zajęć tak by wykorzystywała bump allocator do alokacji i dealokacji węzłów drzewa. Porównaj wydajność i zużycie pamięci obu technik alokacji.

Wywołania systemowe

Wywołania systemowe są uniwersalnym (używanym przez każdą platformę) sposobem na komunikację aplikacji użytkownika z systemem operacyjnym. Implementowane są przez wywoływanie specjalnej instrukcji procesora syscall, która inicjuje tzw. przerwanie (ang. interrupt) - zatrzymanie wykonywania aktualnego programu i przeniesienie kontekstu do systememu operacyjnego. Działanie obsługi przerwania zależne jest od wybranego numeru wywołania systemowego. Lista numerów jest różna w zależności od systemu operacyjnego:

strace

Program strace pozwala na śledzenie wywołań systemowych wykorzystywanych przez program:

$ cat test.c
#include <stdio.h>

int main()
{
        printf("hello, world\n");
        return 0;
}
$ gcc -static -o test test.c
$ strace ./test
execve("./test", ["./test"], 0x7fff1c1dd1a0 /* 92 vars */) = 0
brk(NULL)                               = 0x189f8000
brk(0x189f8d40)                         = 0x189f8d40
arch_prctl(ARCH_SET_FS, 0x189f83c0)     = 0
set_tid_address(0x189f8690)             = 68150
set_robust_list(0x189f86a0, 24)         = 0
rseq(0x189f8340, 0x20, 0, 0x53053053)   = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
readlinkat(AT_FDCWD, "/proc/self/exe", "/tmp/test", 4096) = 45
getrandom("\x9f\x76\xab\xaa\x01\x77\x20\x50", 8, GRND_NONBLOCK) = 8
brk(NULL)                               = 0x189f8d40
brk(0x18a19d40)                         = 0x18a19d40
brk(0x18a1a000)                         = 0x18a1a000
mprotect(0x4a2000, 20480, PROT_READ)    = 0
fstat(1, {st_mode=S_IFCHR|0600, st_rdev=makedev(0x88, 0x3), ...}) = 0
write(1, "hello, world\n", 13hello, world
)          = 13
exit_group(0)                           = ?
+++ exited with 0 +++

Alokacja pamięci

Rekomendowany talk: CppCon 2015: Andrei Alexandrescu “std::allocator…​”.

Alokacja pamięci: system operacyjny

Alokacja pamięci: biblioteka języka C

Alokacji pamięci: perspektywa algorytmiczna

Free list

Niezaalokowane regiony pamięci łączone są w listę jednokierunkową. Aby zaalokować nowy region, należy znaleźć w liście region, który spełnia wymagania dot. rozmiaru. Algorytm zakłada, że regiony pamięci mają co najmniej rozmiar wskaźnika.

Algorytm alokacji void* free_list_alloc(size_t size):

  1. Znajdź region, którego wielkość jest co najmniej size. Jeśli nie ma takiego regionu zwróć NULL.

  2. Ustaw wskaźnik kolejnego regionu w poprzednim regionie na region następny do znalezionego.

  3. Zwróć znaleziony region.

Algorytm dealokacji void free_list_dealloc(void *region):

  1. Dodaj region na początek listy, zapisując wskaźnik do początku listy na początku regionu oraz zapisując wskaźnik regionu jako początek listy.

Bump allocator

Tablica bajtów, z wskaźnikiem na koniec poprzedniej alokacji. Użyteczna w zastosowaniach sieciowych czy gamedevie - wtedy kiedy program potrzebuje dużą ilość małych alokacji z znaną górną granicą (i możliwością regularnego czyszczenia).

Algorytm alokacji: void* bump_alloc(size_t size):

  1. Niech p będzie wskaźnikiem na pierwszy bajt za ostatnią alokacją (lub na początek tablicy jeśli to jest pierwsza alokacja). Jeśli p+size wykracza poza rozmiar tablicy zwróć NULL. W innym przypadku zwróć p i zwiększ p o size.

Algorytm dealokacji: brak