메모리구조에서의 자료구조

업데이트: April 18, 2020

컴퓨터공학 스터디 W1에서 직접 발표한 내용을 정리한 글입니다.

운영체제에 대한 이해가 부족한 상태에서 작성한 글입니다.

잘못된 해석은 댓글로 지적해주시면 감사하겠습니다.

또한 자료가 부족하여 개인적인 견해가 포함되어있습니다.

들어가기 전에

메모리구조에서 스택과 자료구조에서 스택, 메모리구조에서 힙과 자료구조에서 힙이 어떤 연관성을 가지는지 호기심이 생겨 이러한 주제로 글을 작성하게 되었습니다. 이 글에서 언급하는 모든 메모리 는 실제 존재하는 물리적인 메모리가 아닌 프로그램이 사용하는 가상메모리의 가상주소공간를 의미합니다. 본문의 내용을 이해하기 위해서는 가상메모리와 가상주소공간, 메모리블록의 개념이 필요합니다. 이해를 돕기 위해 자세한 설명이 포함되어있지만 개념만 이해하면 본문의 내용을 이해하는데에는 문제가 없을 것입니다.

가상메모리의 개념

각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 할당해 RAM을 관리하는 방식

사용이유

실제 존재하는 물리적인 메모리의 사용량은 한정되어있습니다. 그래서 개발자들은 물리적인 메모리를 보다 효율적으로 사용할 수 있는 방법을 찾게되었고, 이 방법이 바로 가상메모리입니다. 가상메모리는 하드디스크를 이용하여 어떤 프로세스를 실행할 때 프로세스 전체가 메모리에 적재되지 않고도 실행이 가능하도록 합니다. 또한 어떤 프로세스가 차지하는 메모리가 전체 메모리 용량보다 크더라도 현재 필요한 부분만 메모리에 적재되면 실행이 가능하기 때문에 물리 메모리 용량을 초과하는 프로그램도 동작시킬 수 있습니다.

가상주소공간과 메모리블록

가상메모리는 실제 존재하는 물리적인 메모리의 개념과 사용자의 논리 메모리의 개념을 분리합니다. 따라서 다소 복잡하고, 접근이 어려운 물리 메모리를 가상으로 재구성하여 엄청나게 큰 배열로 추상화시켜줍니다. 그리고 모든 프로그램은 이 배열의 4GB(32비트 시스템기준)에 달하는 가상주소공간을 부여받습니다. 32비트 시스템 기준, 개발자는 운영체제가 사용하는 2GB를 제외한 가상주소공간의 2GB를 실제 메모리인 것 처럼 사용합니다. 하지만 불필요하게 많은 공간을 하드디스크에 할당하는 것은 효율적이지 않기 때문에 메모리를 4KB정도의 메모리블록으로 분할하여 사용합니다. 메모리블록의 크기가 일정한 것은 페이지, 일정하지 않은 것은 세그먼트라고 부릅니다. 그리고 메모리블록을 단위로 여러 전략을 사용하여 메모리를 효율적으로 관리할 수 있습니다.

요약

가상메모리 > 가상주소공간 > 메모리블록

메모리 구조(가상주소공간 구조)

코드 영역

실제 프로그램의 동작을 수행하는 명령어와 전역 상수가 저장됩니다. 이 영역은 읽기 전용으로, 데이터가 변경되지 않습니다.

데이터 영역

위 그림의 bss, data 영역을 묶어서 데이터 영역이라고 합니다. 전역변수와 정적변수가 저장됩니다. 프로그램이 실행될 때 할당되고, 종료될 때 해제됩니다. 이 때, 초기화 된 데이터는 data영역에, 초기화되지 않은 데이터는 bss(block stated symbol)영역에 저장됩니다.

스택 영역

함수 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역입니다. 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다. 일반적으로 컴파일러 기본 설정은 1MB으로 제한됩니다. 즉, 프로그램이 스택 영역에 1MB이상 할당하려 한다면 스택오버플로우 에러가 발생합니다.

정확한 명칭은 콜 스택입니다.

힙 영역

개발자가 자유롭게 할당하고 해제할 수 있는 영역입니다. 개발자에 의해 관리되므로 메모리 누수가 발생할 수 있습니다. 따라서 힙 영역에 데이터를 할당하고 사용한 후에는 반드시 해제해야 합니다.

자료구조

스택

한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO형식의 자료구조입니다.

힙

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다. 종류에는 최대 힙, 최소 힙이 있어 여러 개의 값들 중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어졌습니다. 자세한 설명은 다음 블로그를 참고해주세요.

메모리구조에서 사용하는 자료구조

앞서 설명한 메모리구조에서 코드 영역과 데이터 영역은 데이터를 할당하고 해제하는 과정이 정적이므로 특정한 자료구조를 선택하여 구현할 이유가 없습니다. 따라서 아래의 글은 현재 대부분의 운영체제에서는 데이터를 할당하고 해제하는 과정이 동적인 스택 영역과 힙 영역에 어떤 자료구조를 사용하여 구현되고 있는지 설명합니다.

+ 글 작성의 시발점이 된 스택 영역과 스택 자료구조, 힙 영역과 힙 자료구조의 연관성에 대한 답

모두 동음이의어일뿐, 다른 개념입니다. 하지만 그 개념을 표현하기 위해 사용한 용어의 어원은 같은 것 같습니다.

스택 영역

동작원리

쉬운 이해를 위해 스택 프레임의 개념을 생략하고 정리했습니다.

함수 호출
호출된 함수를 푸시
함수 호출이 완료되면 해당 함수를 팝

사용 자료구조

동작원리에 따르면 함수 호출이 완료되면 이전 함수로 돌아갈 때 완료된 함수의 바로 이전 함수로 돌아가야 합니다. 따라서 LIFO형식의 자료구조인 스택이 가장 적합하고, 대부분의 운영체제와 컴퓨터는 내부적으로 스택 자료구조를 사용해 구현한다고 합니다.

힙 영역

동작원리

런타임 라이브러리가 처리하는 과정을 생략하고 정리했습니다. 실제 malloc이나 new 같은 메모리 요청은 운영체제가 아닌 런타임 라이브러리에서 처리합니다.

사용자의 메모리 요청
운영체제가 프로그램에 메모리 블록 할당
- 이미 존재하는 메모리 블록에 사용가능한 영역이 있다면 그 메모리 블록에 할당
- 이미 존재하는 메모리 블록에 사용가능한 영역이 없다면 메모리 블록을 늘려서 할당
운영체제가 프로그램이 요청한 크기에 맞는 메모리 주소 반환

사용 자료구조

저는 아직 운영체제에 대한 이해가 부족하고, 이 부분에 대해서는 여러 의견이 존재하며, 운영체제에 특성에 따라 사용되는 자료구조가 다르기 때문에 인터넷의 여러 정보를 취합해 작성하였습니다. 댓글로 정확한 사실을 알려주시면 감사하겠습니다.

동작원리에 따라서 메모리를 할당할 때 큰 객체와 작은 객체를 번달아 할당하게 되면, 메모리관리를 효율적으로 할 수 없습니다. 따라서 운영체제는 메모리 블록 내부에 다음번에 할당할 메모리 영역을 계속해서 추적해야 합니다. 대부분의 운영체제는 연결리스트로 이 구조를 유지합니다. 메모리 요청이 들어오면 리스트를 따라가면서 현재 요청된 크기의 메모리가 남아있는 블록까지 가서 그 주소를 반환하고, 남아있지 않다면 새로운 메모리 블록을 할당하는 것입니다.

+ 힙 자료구조는 적합하지 않은가요?

스택오버플로우에도 여러가지 의견이 분분한데, 개인적인 견해로는 연결리스트 기반의 힙 구조를 사용해 구현할 수도 있으나 굳이 구현할 이유가 없다고 생각됩니다. 차라리 연결리스트 기반의 RB트리로 구현하는 것이 더 나을 것 같습니다.