[자료구조] 메모리 청크

　자료구조를 공부하다 보면 메모리 청크라는 단어를 자주 듣게 된다. 본 카테고리의 두 글을 보더라도, 청크라는 용어가 나온다. 단순히 메모리 덩어리라고 생각하기엔 추상적인 느낌이 강해 본 포스팅을 통해 구체화해 보도록 하자.

 

　먼저 메모리 청크는 동적으로 메모리를 할당할 때 사용되는 일정한 크기의 메모리 블록을 의미한다. 이때 청크는 요소들 간 포인터를 사용하지 않는다. 각 청크는 배열 형태로 데이터를 저장하는 포인터와 청크의 크기, 다음 청크를 가리키는 포인터를 갖고 있다. 여기서 포인터를 사용하지 않는다는 것은 메모리 청크는 일반적인 포인터를 사용하지 않고, 인덱스 또는 오프셋을 사용하여 요소들을 참조한다는 의미다.

　예를 들어, int 형 배열 arr 에서 arr[0] 에 접근하려면, arr의 시작 주소에서 arr[0] 까지의 거리를 계산해서 해당 위치의 값을 찾아야 한다. 이때 arr[0]의 오프셋은 0이며, arr[1]의 오프셋은 int 자료형의 크기만큼인 4다. 따라서 arr[i]의 오프셋은 i * sizeof(int)가 된다.

　청크 안에서 인덱스 0부터 시작하여 4바이트씩 요소를 저장한다고 가정해보자. 그렇다면, 첫 번째 요소의 인덱스는 0이 되고, 두 번째 요소의 인덱스는 4가 된다. 이때 첫 번째 요소의 주소를 찾기 위해서는 청크의 시작 주소와 첫 번째 요소의 오프셋(0)을 더해야 한다. 이렇게 계산된 주소가 첫 번째 요소의 메모리 주소가 되는 것이다. 다음 요소의 주소는 청크 시작 주소와 두 번째 요소의 오프셋(4)을 더해서 구할 수 있다.

 

　반대로 정적으로 메모리를 할당하는 경우에는 이미 메모리 공간이 할당되어 있기 때문에 메모리 청크가 사용되지 않는다. 따라서 동적 할당을 하면 운영체제가 프로그램에 필요한 메모리 공간을 할당하고, 이 공간이 일정한 크기의 메모리 청크로 분할된다. 이를테면, 프로그램이 10 byte의 메모리를 할당하면, OS는 10 byte 크기의 메모리 청크를 할당하는 방식으로.

 

deque의 자료 구조 예시

 

　위 그림은 메모리 청크를 사용하는 deque의 전체 덱 자료구조 예시이다. 여기서 메모리 청크 chunk는 다른 청크들과 연결되어 있으며, Chunk는 이러한 블록들의 덩어리다. deque에서 각각의 청크는 연속된 메모리 블록으로 구성되어 있고, 첫 번째 청크부터 마지막 청크까지 연결되어 이중 연결 리스트를 형성한다. 

 

　만약 이 글을 읽으며 '노드와 비슷한 거 같은데?' 라고 떠올렸다면 자료구조 공부를 열심히 한 것이다(...). 이 둘은 실제로 개념적으로 비슷하다. 하지만 둘의 차이점은 사용되는 목적과 구현의 방법이다. 노드는 연결 리스트에서 요소를 나타내는 데 사용되는 개념이고, 메모리 청크는 메모리 할당과 관련된 개념이다. 쉽게 얘기해서 배열 같은 자료나 동적 메모리 할당하는 자료를 사용할 때는 메모리 청크를 사용하고, 리스트와 같이 연결된 자료를 사용할 때는 노드를 사용하면 된다.