포도가게의 개발일지
동적 메모리 할당 본문
dynamic memory allocation
- 동적 메모리 할당기는 heap이라고 하는 프로세스의 가상메모리 영역을 관리한다.
- 힙이 미초기화된 데이터 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 메모리 영역으로 가정
- 커널은 힙의 꼭대기를 가리키는 변수 brk(break)를 사용한다.
할당기는 힙을 다양한 크기의 블록들의 집합으로 관리하며, 각 블록은 할당되었거나 가용한 가상메모리의 연속적인 묶음이다.
할당기 기본 유형
- 명시적 할당기 : C표준 라이브러리는 malloc 패키지라고 하는 명시적 할당기를 제공한다. c는 malloc 함수를 호출해서 블록을 할당하며, free 함수를 이용하여 블록을 반환한다.
- 묵시적 할당기 : 묵시적 할당기는 가비지 컬렉터라고 알려져 있으며, 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 부른다.
* 인텔이 4바이트 객체를 더블 워드라고 말한다, 하지만 이번 내용에서는 워드는 4바이트 객체이고, 더블 워드는 8바이트 객체라고 가정하여 이것은 일반적인 용어와 일관성을 가진다.
32bit 컴퓨터는 malloc 주소가 항상 8의 배수인 블록을 리턴하며 index: address -> 0 : 0 , 1 : 8, 2 : 16, 3 : 24 워드의 길이가 8
64bit 컴퓨터는 항상 16배수이다. index: address -> 0 : 0 , 1 : 16, 2 : 32, 3 : 48 워드의 길이가 16바이트 이다.
malloc vs calloc
- malloc 함수는 할당된 메모리를 리턴할때 초기화하지 않으며
- calloc 함수는 할당된 메모리를 리턴하기전에 0으로 초기화 한 후에 리턴해준다.
- 이전에 할단된 블록의 크기를 변경하려는 응용은 realloc이라는 함수를 통해 할 수 있다.
- malloc 같은 동적 메모리 할당기는 mmap과 munmap함수를 사용하여 명시적으로 메모리를 할당하거나 반환하며, 또는 sbrk 함수를 사용할 수 있다.
동적 메모리 할당을 쓰는 이유?
- 가장 중요한 이유는 종종 프로그램을 실제 실행하기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.
- 또한 간단한 프로그램에서 고정된 배열의 크기가 있는것은 문제가 되지 않지만, 수백만 라인의 코드와 수 많은 사용자가 있는
대규모 프로젝트에서는 관리하는데 어려움이 생길 수 있다.
할당기의 요구사항과 목표
- 임의의 요청 순서 처리하기 : 할당과 free가 어떤 순서로 명령이 들어올지 모르기 때문에 -> fragmentation이 생기는 이유 같음
- 요청에 즉시 응답하기 : 할당기는 요청을 즉시 응답해야한다.! 할당기는 성능 향상을 위해 재배치하지말고 들어온 순차적으로 요청을 처리해야한다.
- 힙만사용하기 : 확장성을 갖기 위해 할당기가 사용하는 비확장성 자료 구조들은 힙자체에 저장되어야한다.
- 블록 정렬하기 : 할당기는 블록들을 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬 해야한다.
- 블록 수정하지 않기 : 할당기는 가용 블록을 조작하거나 변경할 수 만있다. 특히 일단 블록이 할당되면 이들을 수정하거나 이동하지않는다. 그래서 할당된 블록들을 압축하는 것 같은 기법들은 허용되지 않는다.
목표
- 처리량 극대화 하기 최소시간동안 최대한의 요청을 처리
- 메모리 이용도를 최대화하기 -> 가상메모리를 효율적으로 사용해야한다. 소스는 무한대가 아니다.
묵시적 가용 리스트(implict free list)
*block size : 현재 블럭의 크기
*0~31 bit는 32Bit고 8byte이다 헤더에서 31~3까지는 block의 크기를 의미하며 2~0까지는 allocated되었는지를 의미한다. 따라서
header 값을 통해 block의 크기와 블럭이 할당되었는지를 알 수 있다. 32bit 기준으로 블럭의 사이즈는 8의 배수이며 16진수로 표현했을때 마지막 자리 수는 8의 배수이다 숫자 8 은 이진수로 표현이 1000이며 16진수 1은 이진수로 표현이 001이다 이렇게 두 숫자를 or 비트연산을 하면 1001이 되면 이것은 숫자 9를 의미한다. 고로 8의 배수가 아닌 값은 할당된 블럭을 의미한다.
free된 블럭 연결하기
- footer(경계 태그)에 header와 같이 blocksize와 할당정보를 저장함으로써 next block header가 curr_footer를 봄으로써 한쪽으로 탐색을 통해 연결을 하는게 아니라 이전 블럭과 다음 블럭이 할당이 끝났다면 인접 블럭들을 하나로 합쳐줄수 있다.
- footer의 잠재적인 단점은 4byte data를 저장하고싶은데 header footer가 붙게되면 3word가 생성된다. 이렇게 되버리면
아주 많은 소형의 블럭들이 생성하게되면 실제 사용되는 데이터들의 수보다 header와 footer가 더 많아지게 된다.이렇게 되면 상당한 오버헤드가 발생하게 될 것 이다.
간단한 할당기 구현
