가상 메모리, Heap, 동적 할당기, Malloc Lab 과제에 대한 글입니다.
1. Virtual Memory
메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리라고 알려진 메인 메모리의 추상화를 제공한다. 가상 메모리는 각 프로세스에 하나의 크고 통합된, 사적 주소공간을 제공하며, 기능을 크게 세 가지로 요약할 수 있다.
1) 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급한다.
2) 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
3) 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.
2. Heap
프로세스는 Stack, Heap, bss, data, text로 메모리 공간을 나눠놓고 사용하는데, Heap이라는 영역은 사용자가 필요에 따라 원하는 메모리 Block을 요청하고, 반환할 수 있다. Heap 영역은 일반적으로 낮은 주소에서 높은 주소로 자란다.
3. 동적 할당기 (Memory Allocator)
: 프로그램을 실행시키기 전에 자료구조의 크기를 알 수 없는 경우가 있기 때문에 동적 할당을 사용하는데, Heap 영역을 관리하는 도구를 동적 메모리 할당기라고 부른다. 할당기에는 두 가지 종류가 있다.
1) 명시적 할당기 : 명시적으로 malloc을 통해 공간을 할당하고, free를 통해 공간을 반환해야 하는 방식의 할당기. 즉, 사용자가 직접 공간을 할당하고 반환하는 작업을 명시적으로 해줘야 한다.
2) 묵시적 할당기 : 사용자가 할당한 메모리 Blcok들에 대하여, 더 이상 프로그램에 의해 사용되지 않는 Block을 검출하여 반환시켜주는 작업을 수행하는 할당기. 가비지 컬렉터라고 부르며, Block을 반환하는 작업을 가비지 컬렉션이라고 부른다.
* 명시적 할당기 예시 - C의 표준 라이브러리 : Malloc
사용자가 요청한 크기의 빈 Block을 찾고, 포인터를 return한다. 32bit 시스템은 8의 배수, 64비트 시스템은 16의 배수로 align된 주소값을 return한다. 사용 가능한 메모리보다 큰 Block을 요청하는 경우 null을 return하고, 성공적으로 메모리 Block을 return하는 경우에도 메모리 블럭의 내용을 초기화하지는 않는다. 이를 원한다면 할당된 메모리를 0으로 초기화하는 calloc을 사용할 수 있다. 이미 할당된 메모리 Block의 크기를 변경하고자 한다면 realloc을 사용한다.
명시적 할당기의 구현
명시적 할당기를 구현하는 과정이 Malloc Lab의 과제였다. 메모리 할당 과정은 아래와 같은 함수들로 구성된다. (Block에 관한 자세한 설명은 맨 아래 참조)
mem_sbrk() : Heap 전체 사이즈를 늘린다. 요청된 메모리 Block을 만족하는 빈 공간이 없을 때 호출된다.
find_fit() : 허용된 Heap 영역 내에서, 요청된 메모리 Block Size를 만족하는 빈 공간이 있는지 찾는다.
coalesce() : 빈 공간이 연속적으로 있다면, 합친다.
malloc() : 메모리 공간을 할당하기 위해 호출된다.
free() : 메모리 공간을 반환한다.
동적 할당은 아래와 같은 과정으로 이루어진다.
1) Heap을 초기 사이즈인 CHUNK_SIZE(ex : 4KB)로 생성한다.
2) 사용자의 요청에 따라 Heap 내에 공간을 할당한다.
3) 할당된 Heap 내에 더이상 할당할 공간이 없다면, CHUNK_SIZE 단위로 Heap을 증가시킨다.
실제로 구현하는 방법은 아래와 같이 구조/기능에 따라 다양하다.
[ 구조 ]
1) 묵시적 가용 리스트(Implicit Free List) : Allocated Block, Free Block이 할당된 채로 아무것도 하지 않은 구조. Header/Footer를 확인하며 순차적으로 검색한다.
2) 명시적 가용 리스트(Explicit Free List) : Free Block들만 연결 List로 연결한 뒤, Free List에서 요청한 크기를 만족하는 Free Block을 찾는다. 이 때 Free Block에 연결 List를 구성하기 위한 추가 데이터를 넣는다. 어짜피 비어있는 공간이라 메모리 낭비는 발생하지 않는다.
3) 분리 가용 리스트(Segregated Free List) : Free List를 크기 별로 관리한다. 크기를 관리하는 방법은 다양하다. 특정 크기가 들어왔을 때 해당 크기가 포함된 범위의 Free List만 살펴보면 되므로 검색 시간이 단축될 수 있다.
[ 기능 ]
1) First Fit : 처음부터 끝까지 순차적으로 검색하며 조건을 만족하는 Block을 바로 return한다.
2) Next Fit : 가장 최근에 할당된 Block을 기록해놓은 뒤, 그 다음 것 부터 찾는다.
3) Best Fit : 모든 공간을 검색해본 뒤, 가장 가까운 크기를 갖는 Block을 return한다.
할당기의 성능
할당기의 성능은 아래와 같이 측정할 수 있다.
할당된 공간 / 전체 Heap Size
위의 값이 클수록, 단편화(Fragmentation)가 적게 일어나서 메모리가 효율적으로 사용된 것이다.
(단편화에 관한 자세한 설명은 맨 아래 참조)
* 묵시적 할당기 예시 : 가비지 컬렉터
아래와 같은 경우 가비지(사용자가 메모리 Block을 동적 할당해놓고 반환하지 않는 경우)가 발생한다.
이런 가비지들을 Free하기 위해서, 다양한 방법들이 있지만 가장 기초적인 Mark & Sweep 방법을 소개한다. 아래 그림과 같이 루트 노드들과 힙 노드들로 이루어진 방향성 도달 그래프로 메모리 참조 관계를 나타낸다. 각 힙 노드는 하나의 할당된 Block을 나타내며, 어떤 루트 노드에서도 특정 힙 노드 p로 향하는 경로가 없다면, p는 가비지로 인식된다.
Mark : 루트 노드들의 도달 가능하며 할당된 하위노드들을 표시하는 행위
Sweep : 표시되지 않은 블록을 반환하는 행위
어떤 가비지 컬렉터는 별도의 쓰레드로서 실행되어 그래프를 관리하며 가비지를 회수하기도 하고, 어떤 가비지 컬렉터는 가용 블럭이 더이상 없을 때 호출되어 찾기도 한다. 후자를 보수적인 가비지 컬렉터라고 한다.
* Segmentation Fault : 페이지 테이블에는 허가 비트라는 것이 있어서 가상 페이지 내용으로의 접근을 제어하는데, 어떤 인스트럭션이 이 허가사항을 위반할 경우 Fault를 발생시키며, 이것이 Segmentation Fault이다.
* Stack Buffer Overflow : 버퍼의 사이즈를 할당해놓고 입력을 받을 때, 입력의 사이즈가 버퍼의 크기를 넘어가는 경우 발생한다. fgets를 사용하여 입력 사이즈를 제한하여 해결한다.
* Block과 Free Block, Allocated Block
이 글에서 명시하는 Block은 Heap 영역 내에 쪼개진 하나의 저장 공간을 의미한다. Allocated Block은 사용자가 명시적으로 할당을 요청한 Block이고, Free Block은 Allocated되지 않은 Block이다. 우선 하나의 Block은 어떤 구조를 갖는지 살펴보자.
Block은 아래와 같은 구조를 갖는다. 맨 앞, 맨 뒤에 있는 식별자인 Header, Footer는 Free 시에 활용된다. 예를 들어 Allocated Block을 Free시킨다고 하자. 해당 Block을 Free시키는 것은 문제가 없지만, 외부 단편화와 내부 단편화를 막기 위해 앞뒤로 Free Block이 있는 경우 합치는 작업(Coalesce)을 진행해야 한다. 이 때 앞뒤에 있는 Block의 할당 여부, 크기를 알기 위해서 사용되는 것이 Header와 Footer이다.
* Header : 크기와 할당 여부를 나타내는 1Word 크기의 식별자
* Payload : 사용자가 할당을 요청한 데이터 영역. Malloc의 경우 해당 영역을 초기화하지 않는다.
* Footer : 크기와 할당 여부를 나타내는 1Word 크기의 식별자
* 외부 단편화(External Fragmentation) : 사용자가 요청한 메모리 할당을 위한 Free Space는 충분하지만, 연속적이지 않아 메모리 할당이 불가능한 경우. 아래와 같이 Free Space(흰색)와 Allocated Space(회색)가 있고, 사용자가 50KB의 메모리 공간 할당을 요청했다고 하자. 전체 Free Space의 합은 55KB로 요청한 메모리 할당을 위한 공간이 충분하지만, 연속적이지 않아 할당이 불가능하여 Heap 영역을 늘려야 한다. (이 때, 임의로 Assigned Block을 이동시켜 Free Block들을 합치는건 불가능하다.)
* 내부 단편화(Internal Fragmentation) : 할당기의 규칙에 의해 할당한 메모리 공간에서 실제로 사용되는 공간이 작은 경우 발생한다. 아래와 같이 Assigned Space보다 Used Space가 작을 때 발생한다. Padding이나 메모리 할당 방식의 차이에 따라 발생한다.
'SW사관학교 정글 > 프로젝트' 카테고리의 다른 글
| B-Tree 삭제 (0) | 2021.02.15 |
|---|---|
| B-Tree 생성, 삽입 (0) | 2021.02.15 |
| Pintos Project2 - User Programming (0) | 2021.02.15 |
| PINTOS Project1 - Threads (0) | 2021.01.28 |
| B-Tree란? (0) | 2021.01.21 |