메모리 구조
프로그램 실행 시 운영체제에 의해 마련되는 메모리의 구조는 다음과 같다.
-
코드 영역(code Area)
실행할 프로그램의 코드가 저장되는 메모리 공간. CPU는 코드 영역에 저장된 명령문들을 하나씩 가져가서 실행한다.
-
데이터 영역(Data Area)
전역 변수와 static 변수가 할당된다. 프로그램의 시작과 동시에 메모리에 할당되어 프로그램 종료 시까지 남아있다. main 함수가 호출되기 이전에 데이터 영역이 먼저 초기화되고, (return문이 실행되어) 프로그램이 종료된 이후에 운영체제에 의해 할당된 메모리 공간 전체를 반환하는데, 이때가 전역 변수가 소멸하는 시점이다.
-
스택 영역(Stack Area)
지역변수와 매개변수가 할당된다. 함수를 빠져나가면 소멸한다.
-
힙 영역(Heap Area)
malloc, calloc, realloc함수를 통해 동적 할당되는 메모리들이 있는 공간 => 여기가 동적 할당 메모리되는 Heap
파이썬에서 배운 자료구조 Heap이랑 똑같은가? : NO
힙 메모리는 프로그래머의 명령을 실행하는 동안 할당됩니다. 이름 힙은 힙 데이터 구조와 관련이 없음을 강조하는 것이 중요합니다. 프로그래머가 할당 및 할당 해제할 수 있는 메모리 공간의 모음이기 때문에 힙이라고 합니다.
Heaps memory is allocated during the execution of programmers’ instructions. It is crucial to highlight that the name heap has nothing to do with the heap data structure. It is termed a heap because it is a collection of memory space that programmers can allocate and deallocate.
동적 메모리 할당(Dynamic Memory Allocation)
할당기(allocator)는 힙을 블록의 집합으로 유지한다. 블록은 할당(allocheap area is same heap with data structureated)되거나 가용(free) 상태이다. 힙의 가장 위(Top)이 brk ptr(break pointer)이다.
할당기의 종류
- 명시적(explicit) 할당기 : malloc과 free
- 묵시적(implicit) 할당기 : garbage collection(Java)
애초에 C는 수동 메모리 관리를 가정하고 설계되어서 implicit dynamic memory allocator는 없는듯
garbage collection
동적 할당된 메모리 영역 가운데 더 이상 사용할 수 없게 된 영역을 탐지하여 자동으로 해제
장점
Garbage collection 이 방지할 수 있는 bug
- 유효하지 않은 포인터 접근 : 이미 해제된 메모리에 접근하는 것
- 이중 해제: 이미 해제된 메모리를 또 다시 해제하는 것
- 메모리 누수
단점
- 타겟으로할 메모리를 결정하는데 필요한 비용
- garbage collection의 타이밍이나 점유 시간 예측 힘듬. 실시간 시스템에는 부적합
- 메모리 해제 시점 알수 없음
malloc package
#include <stdlib.h>
void *malloc(size_t size)
- 성공 : 8바이트나 16바이트 boundary로 나열된 ‘size’ bytes크기의 메모리블록의 포인터 반환, size = 0 이면 NULL 반환
- 실패 : Null(0) , sets errno 반환
void free(void *p)
- p가 가리키는 블록을 가용 메모리로 반환
- p는 이전의 malloc 이나 realloc 호출 이후 와야 한다.
other function
- calloc : malloc + 값을 0으로 초기화
- realloc : 이전에 할당된 블록의 크기 변화
- sbrk : program break의 위치를 변경. program break는 프로세스의 데이터 세그먼트의 끝을 규정한다. 즉, program break는 초기화되지 않은 데이터 세그먼트 영역 후의 첫부분의 위치이다. 따라서 program break를 증가시키면 프로세스에 메모리를 할당하는 효과가 나타난다. (brk는 break point “설정”, sbrk는 “이동”)
malloc lab
throughput(처리율) : 초당 처리하는 작업의 갯수
fragmentation
internal Fragmentation
payload가 block size보다 작을 때 발생
- heap data structure 유지의 overhead(간접비)로 인해 발생하는데 다음 2가지가 그것이다.
- double word 맞추느라
- payload보다 훨씬 큰 block을 쓰느라
external Fragmentation
전체 가용은 충분하나, 단일 블록들이 너무 작을때 ( internal 이 쌓여서 )
고민해봐야할 문제
- 받은 포인터 만으로 얼마나 많은 메모리를 free할지 우리는 어떻게 알 수 있을까?
- 어떻게 가용 블록 트랙(track)을 유지할까?
- 존재하는 가용 블록보다 작은 구조를 할당할 때, 여분의 공간은 어떻게 할까?
- 어떻게 할당할때 쓸 블록을 고를까?
- free된 블록에 어떻게 다시 할당할까?
1. Free할 양 파악하는 법
일반적인 방법 : ‘header field’ 나 ‘header’라고 불리는 word의 선행블록 안에 써있는 블록의 길이 유지.
모든 할당된 블록을 위한 여분의 word 요청
2. 가용 블록 트랙 유지
- “모든” 블록을 잇는 길이를 사용한 묵시적 리스트 방법(implicit)
- 포인터를 활용하는 “가용” 블록들 간의 명시적 리스트 방법(explicit)
-
분리 가용 리스트 방법(segregated free list)
- 블록을 크기로 정렬 방법 : 각 가용 블록에서 RB tree 같은 균형 트리를 포인터와 활용하고 key로 사용되는 길이를 이용한다.
방법 1 : Implicit List
- 각 블록마다 크기와 할당 상황을 알아야 한다. (2개의 word에 저장해야하는데, 낭비임)
- 블록이 나열되어 있으면, 일부 낮은 순서의 주소값은 비트는 항상 0이다.
- 항상 0 비트를 저장하는 대신, 할당/가용 표시를 위해 사용한다.
- 크기 word를 읽을때, 이 bit도 같이 본다.
implicit list 에서 가용 블록 찾기
-
First fit : 시작부터 찾아서 알맞은 첫번째 블록을 고른다.
블록 총 갯수와 비슷한 시간 소요된다.
splinter 발생 가능 이 splinter가 쌓이면서 fragmentation 현상이 나타난다.
-
Next fit : first fit처럼 하되, 직전에 탐색이 끝난 곳부터 시작한다.
한번 본 곳은 다시 보지 않으니 first fit보단 빠르다.
단편화 가능성이 더 높다.
-
Best fit : list를 탐색해 가장 잘맞고 남는 부분이 남지 않는 최고의 가용블록을 찾는다.
단편화가 덜 발생하여 메모리 활용이 높다.
first fit 보다 느리다.
가용 블록에 할당하기 : splitting(분할)
- 내가 할당할 양보다 가용 공간이 크면? : split으로 나누어서 필요한만큼만 쓴다.
할당된 블록 Free하게 하기
가장 쉬운 방법 : 그냥 대상 header에 있는 할당/비할당 숫자(위에서 선행블록에 넣는다고 말했던 것)만 바꿔준다.
=> false fragmentation : 단편화 발생
ex) free 됐지만 여전히 4+2 는 4+2로 남겨져있음 => 5 or 6 못넣음
Coalescing(합체)
위 단편화 방지를 위해 앞뒤 가용 블록과 합쳐준다.
할당이나 크기 정보는 Top 쪽 head에 있는데 이전 블록(앞 블록)은 가용 블록인지 어떻게 알까?
‘Boundary tags’ 를 이용
-
가용 블록의 bottom(end)에도 크기(size)와 할당여부(allocated/free)를 복제해 둔다.
-
그래서 뒤에서부터 읽어도 해당 블록의 정보를 파악할 수 있다.
-
하지만 이 저장을 위해 추가 공간이 필요하다.
단점
- 내부 단편화
- 최적화 문제(footer tag 필요한 block은 누굴까? 그게 필요하다는게 무슨 의미일까?)
주요 할당 논점 정리
-
위치(placement) 관련
- first fit, next-fit, best-fit, etc
- 낮은 처리속도와 낮은 단편화율의 균형
- 새로운 관점 : 분리 가용 리스트는 전체 free list를 탐색할 필요 없이 best fit을 수행하는것과 근사한 결과를 나타내나?
-
분할(splitting) 관련
- 언제 우리는 앞으로 전진하고 가용 블록을 나누나?
- 어느정도의 내부 단편화는 감수할만할까?
-
Coalescing(합체) 관련
- immediate coalescing(즉각적인 합체) : free 가 호출될 때마다 매번 합체.
- Deffered coalescing(연기된 합체) : 필요한 경우 전까지 free의 성능을 향상시키기 위해 합체를 미뤄둔다.
예시 : malloc을 위해 free list를 만들때까지 미루거나, 외부 단편화의 양이 역치를 넘기기 전까
Implicit list 요약
- 실행 : 매우 간단함
- 할당 비용 : 최악의 경우 선형
- Free 비용 : 최악의 경우 상수, coalescing 하더라도.
- 메모리 사용 : first-fit, next-fit, best-fit에 따라 다르다.
- 실제로는 malloc/free는 선형으로 걸리는 시간으로 인해 사용되지 않음 : 실제로는 특수한 목적의 application이 많다.
- 분할(splitting)과 boundary tag coalescing의 개념은 모든 할당기에서 일반적이다.
Explicit free list
모든 블록이 아닌 가용(free) 블록의 리스트를 만든다.
가용블록은 이전,다음 블록 포인터를 저장.
논리적 순서에 따르기 때문에 실제 물리적 배치 순서와 다를 수 있음.
새롭게 free된 블록은 free list 어디에 넣어야 할까?
- LIFO(last-in-first-out) : 간단하고 적은 시간(상수). 그러나 단편화가 더 심함
- Address-orders(순서대로 넣기) : LIFO보다 덜한 단편화, 하지만 탐색이 필요함
요약
- memory가 차 있을수록 implicit list보다 빠른 속도를 보여준다.
- list 안팎으로 넣고 빼는 과정으로 인해 할당과 비할당(free)가 조금 더 복잡하다.
- 연결을 위한 여분의 공간이 필요하다(각 블록당 2 words) => 이로 인한 내부단편화 증가가 있을까?
segregated List(Seglist) Allocators
free list의 배열이 있고, 각 list는 크기가 다르다.
n 크기의 블록을 할당
-
사이즈가 n보다 큰 블록에 적절한 free list 탐색
- 찾았다면 블록을 쪼개고(split) 알맞은 리스트에 파편을 넣는다?
- 못찾았다면 더 큰 free list에 해본다.
- 블록을 찾을 때 까지 반복.
블록이 없다면 :
- sbrk를 통해 OS에 추가 힙 메모리를 요구
- 이 새로운 메모리에서 n 바이트의 블록을 할당??
- 가장 큰 사이즈의 free list에 있는 단일 가용 블록에 remainder 두기??
블록을 비할당화(free)하기 : Coalesce 하고 적절한 list에 두기
seglist의 이점
- 높은 작업속도 : 2의 제곱 크기의 seglist가 log만큼 시간 소요
- 메모리 효율 높음
- 전체 힙중에서 seglist의 First-fit 방식이 전체 heap의 best-fit 과 비슷할 정도.
- 각블록이 본인 seglist와 같은 크기더라도 bes-fit과 비슷함.
Explicit free list
모든 블록이 아닌 가용(free) 블록의 리스트를 만든다.
가용블록은 이전,다음 블록 포인터를 저장.
논리적 순서에 따르기 때문에 실제 물리적 배치 순서와 다를 수 있음.
새롭게 free된 블록은 free list 어디에 넣어야 할까?
- LIFO(last-in-first-out) : 간단하고 적은 시간(상수). 그러나 단편화가 더 심함
- Address-orders(순서대로 넣기) : LIFO보다 덜한 단편화, 하지만 탐색이 필요함
요약
- memory가 차 있을수록 implicit list보다 빠른 속도를 보여준다.
- list 안팎으로 넣고 빼는 과정으로 인해 할당과 비할당(free)가 조금 더 복잡하다.
- 연결을 위한 여분의 공간이 필요하다(각 블록당 2 words) => 이로 인한 내부단편화 증가가 있을까?
segregated List(Seglist) Allocators
free list의 배열이 있고, 각 list는 크기가 다르다.
n 크기의 블록을 할당
-
사이즈가 n보다 큰 블록에 적절한 free list 탐색
- 찾았다면 블록을 쪼개고(split) 알맞은 리스트에 파편을 넣는다?
- 못찾았다면 더 큰 free list에 해본다.
- 블록을 찾을 때 까지 반복.
블록이 없다면 :
- sbrk를 통해 OS에 추가 힙 메모리를 요구
- 이 새로운 메모리에서 n 바이트의 블록을 할당??
- 가장 큰 사이즈의 free list에 있는 단일 가용 블록에 remainder 두기??
블록을 비할당화(free)하기 : Coalesce 하고 적절한 list에 두기
seglist의 이점
- 높은 작업속도 : 2의 제곱 크기의 seglist가 log만큼 시간 소요
- 메모리 효율 높음
- 전체 힙중에서 seglist의 First-fit 방식이 전체 heap의 best-fit 과 비슷할 정도.
- 각블록이 본인 seglist와 같은 크기더라도 bes-fit과 비슷함.
