Memory Management

프로세스는 CPU에 의해 위와 같은 가상 메모리 영역을 할당받게 되고,

이 가상 메모리는 MMU(Memory Management Unit)에 의해 실제 DRAM의 메모리 영역에 매핑된다.

malloc으로 메모리를 할당받을 수 있고, realloc으로 메모리 영역을 확장할 수 있다.

 

하지만 경우에 따라 realloc시 메모리 영역을 통째로 복사해야 하는 경우가 생긴다.

이런 경우 성능저하 이슈가 생길 수 있는데, 이런 경우를 줄이기 위해 메모리 공간을 할당부터 관리까지

세심한 노력이 필요하다.

지금부터 그 노력의 흔적을 살펴보자.

 

메모리를 위와 같이 words 단위로 관리한다고 가정하자. (실제로 1word = 32B or 64B 이렇게 하고있긴 함)

만약 p = malloc으로 메모리 공간을 할당 받았는데, free(p)를 할 때, 얼마만큼의 메모리 공간을 지워야 할까?

할당 받은 메모리 공간 뒤로 연속적으로 다른 곳에서 할당 받은 메모리 공간이 존재할 경우

운영체제는 얼마만큼의 메모리 공간을 해제해야 하는 지 알지 못한다.

 

따라서 malloc은 메모리를 할당할 때 1word 더 큰 블럭을 할당받아 포인터로 가리키는 바로 앞 위치에

할당받은 메모리 공간의 크기를 저장한다.

따라서 free(p) 할 때는 p[-1]위치에 저장된 block size만큼만 메모리 공간을 해제하면 된다.

 

메모리를 할당하기 이전에 비어있는 메모리 공간을 어떻게 찾고 적절한 빈공간에 할당하는걸까?

이론적인 세 가지 방법이 존재하는데 하나씩 살펴보자.

 

1. Implicit list

위에서는 할당된 메모리 영역에만 block size를 표기했는데, lmplicit list 방법은

할당되지 않은 메모리 영역에서 block size를 표기한다.

할당된 것과 그렇지 않은 것을 구분하는 방법은 block size를 저장하는 word에서 1bit을 할당하여

0이면 free block, 1이면 allocated block으로 구분한다.

 

이렇게 하면 비어있는 메모리 공간을 block size만큼 이동하며 찾을 수 있는데, 총 세 가지 방법이 존재한다.

붉은색이 first fit 방식으로 처음부터 탐색하며 들어갈 수 있는 free blocks가 존재하면 할당한다.

주황색은 next fit 방식으로 탐색이 종료된 곳 부터 이어서 탐색하며 들어갈 수 있는 free blocks가 존재하면 할당한다.

초록색은 best fit 방식으로 처음부터 탐색하며 최적의 위치를 찾아 할당한다.

 

할당 시간 측면에선 주황색이 가장 빠르나, 조각화가 가장 심하게 발생한다.

조각화가 적게 일어나는 측면에선 녹색이 가장 좋다. 하지만 할당 속도가 느리다.

 

메모리 공간을 할당했으면 해제도 해야한다.

위에서 설명했던 방법대로라면 block size를 저장한 word에 1bit를 0으로 바꾸면 간단하게 해결된다고 생각할 것이다.

하지만, 문제가 있다.

4words 공간을 해제한 후 6words 짜리 공간이 4/2words 공간으로 분리되는 문제가 발생한다.

위의 예시로는 다음 블럭의 시작 주소를 계산할 수 있기에 크게 문제가 되지 않고 해결할 수 있다.

하지만, 이전 블럭도 비어있는 블럭이라면?

위와 같이 단방향으로 검색할 수 있게 구현된 특성때문에 이전 블럭의 크기를 알 방법이 없다.

따라서 사실 아래와 같이 Implicit list를 구현해야 한다.

 

이렇에 양 끝에 블럭 사이즈를 저장한다면, 순방향, 역방향 탐색이 가능하기 때문에

block coalescing 문제를 해결할 수 있다.

 

 

2. Explicit list

이 방법은 비어있는 메모리 공간끼리 forward link, backward link를 걸어 관리하는 방법이다.

링크의 연결 순서는 사용할수록 뒤죽박죽으로 꼬이게 되는데 별 상관 없다.

비어있는 메모리 공간 사이를 이동하며 데이터를 넣을 때 두 가지 정책(방법)이 존재한다.

a. LIFO policy (stack)

    가장 늦게 free된 블럭부터 찾아 넣는다. 이러면 탐색 시간은 줄어들지만, 조각화 이슈가 크다.

b. Address-ordered policy

    적절한 크기의 빈 공간을 찾아 넣는다. 이러면 조각화 이슈는 적지만, 탐색 시간이 늘어난다.

 

 

3. Segregated free list

실제로 malloc이 구현된 방법이다.

비어있는 공간의 크기를 분류하여 연결 리스트로 관리한다.

따라서 필요한 만큼의 공간만 할당해줄 수 있기 때문에 best fit을 흉내 내면서도 속도를 챙길 수 있다.

 

예로 들어 7만큼의 공간을 할당한다고 치자. 그러면 자동으로 8짜리 collection에 할당된다.

그럼 1의 잉여 공간이 생기게 되는데, 이 때문인지 a[7]같이 잘못된 인덱스에 접근해도

프로그램이 죽지 않는 일이 생기는 것이다.