malloc 7

[WEEK07] Trace 데이터 분석 기반 Segregated-fit Size Class 최적화

😨 문제 발생명시적 가용 리스트에서 분리 가용 리스트 방식으로 전환해서 프로그램을 실행했더니 다음과 같은 결과가 나왔다.Explicit free listSegregated free list9, 10번 trace는 realloc 성능을 평가하는 것이라서 제외했다.분리 맞춤을 사용하면 할당 시간을 줄이고 메모리 이용도를 개선할 수 있다고 알고 있었는데, 분리 맞춤으로 전환했음에도 불구하고 성능 점수는 명시적 가용 리스트를 사용한 점수에서 변하지 않았다. util과 secs 및 Kops를 비교해 보면, 오히려 분리 맞춤을 사용한 이후의 성능이 소폭 감소했다는 것을 확인할 수 있다.🤔 원인 찾기static int get_index(size_t size) { size_t a = 1; size_t b..

[WEEK07] 가비지 컬렉션과 메모리 관련 오류들

Garbage CollectionGarbage Collection(이하 GC)는 heap에서 할당된 저장공간의 자동화된 회수이다: 응용프로그램은 free를 해 줄 필요가 없다파이썬, 루비, 자바 등 많은 동적 언어에서 사용한다.C나 C++에도 보수적인Conservative GC 비슷한 무언가가 있지만 모든 garbage를 collect하지는 못한다.묵시적 메모리 관리자는 어떻게 메모리가 free될 수 있는지 알 수 있을까?일반적으로 우리는 미래에 어떻게 될지 알지 못한다.하지만 우리는 특정한 블록이 연결된 포인터가 없다면 사용되지 않을 것이라는 것을 알 수 있다.포인터에 대해 특정한 추측을 해야 한다.메모리 관리자는 포인터와 non-pointer를 구분할 수 있다.모든 포인터들은 블록의 시작을 가리킨다...

[WEEK07] 명시적 가용 리스트와 분리 가용 리스트

Explicit Free Lists모든 block이 아닌, free block의 리스트만 유지한다.next free block은 어느곳이나 가능하다.그래서 우리는 size 뿐만 아니라 이전/다음 포인터도 저장해야 한다.여전히 coalescing에는 boundary tag가 필요하다.다행히도 우리는 free block만 추적할 것이기 때문에, payload area를 사용할 수 있다.논리적으로는물리적으로는 : block들이 아무 순서로도 가능하다 😵Explicit Free Lists에서 Allocating하기Explicit Free Lists로 Freeing하기Insertion 정책 : free list의 어디에 새롭게 free된 block을 넣을 것인가?LIFO 정책free list의 시작 부분에 fr..

[WEEK07] 묵시적 가용 리스트

Implicit List우리가 size와 allocation 상태를 알아야 하는 각각의 block에 대해서 2워드 안에 이 정보들을 저장할 수는 있지만 wasteful하다.block들이 정렬되어 있으면, 어떤 low-order address bits는 항상 0이다.항상 0인 비트를 저장하는 대신에 allocated/free flag로서 사용한다.size word를 읽을 때 이 비트를 mask out해야 한다.자세한 Implicit Free List 예시Free Block을 찾기First-fitlist의 처음부터 탐색을 시작해서, fit한 최초의 free block을 선택한다.allocate & free된 총 block 개수만큼의 선형적인 시간이 걸린다.실제로는 리스트의 시작 부분에 splinter를 발생..

[WEEK07] 동적 메모리 할당

Dynamic Memory Allocation개발자들은 런타임에서 VM을 취극하기 위해 (런타임에서만 그 크기를 알 수 있는 자료구조들을 위해) malloc과 같은 동적 메모리 할당기dynamic memory allocator (이하 DMA)를 사용한다.DMA는 heap이라고 알려진 프로세스 VM의 한 영역을 관리한다.Heap은 아래에서 위로 성장하는 모습이며, heap의 top은 brk 포인터로 가리킨다.할당기는 힙을 allocated 상태이거나 free 상태인 다양한 크기의 block들로 유지한다.할당기의 종류Explicit allocator (명시적 할당기) : 응용프로그램이 공간을 allocate하거나 free한다.(예: C의 malloc/free)Implicit allocator (묵시적 할당기..

[Computer System] ⑨ 가상메모리 (2)

9.9 동적 메모리 할당동적 메모리 할당기Dynamic memory allocator는 힙heap이라고 하는 프로세스의 가상메모리 영역을 관리한다. 여기서 힙은 미초기화된 데이터 영역 직후에서 시작해 위쪽(높은 주소 방향)으로 커지는 무요구 메모리demand-zero memory 영역이라고 가정한다. 각각의 프로세스에 대해서 커널은 힙의 Top을 가리키는 변수 brk(break)를 사용한다. 할당기는 힙을 다양한 크기의 블록block들의 집합으로 관리한다. 각 블록은 할당allocated되었거나 가용free 상태인 가상메모리의 연속적인 묶음(contiguous chunk)이다. 할당기의 두 가지 기본 유형은 다음과 같다:명시적 할당기Explicit allocator : 응용 프로그램이 명시적으로 할당된 ..