[운영체제] 8. Memory Management

메모리의 발전

초기 시스템에서 메모리는 물리 메모리를 직접 사용하는 형태였다. 시스템에는 하나의 프로그램만 동작중이고, overlay를 통해 물리 메모리의 사이즈보다 큰 프로그램은 나누어서 필요할 때 물리 메모리 공간에 올려 수행하게 된다. 이후 컴퓨터 하드웨어의 발전으로 여러 프로세스를 수행할 수 있게 되었고 이때 time sharing이 도입된다. 이후 주소공간을 통해 프로세스는 자신반의 크고 독립적인 가상적인 메모리 공간을 가지게 된다.

 

메모리는 정적으로 변하지 않는 코드, 데이터 영역과 프로그래머의 명시적 할당으로 인해 동적인 힙, 그리고 컴파일러가 암시적으로 할당하는 동적 영역인 스택으로 구별된다.

---

메모리 가상화

위 처럼 프로세스 별로 주소공간(가상 메모리)를 갖게 되었다. 이때 실제 프로그램 수행 시에는 물리 주소를 사용해야 한다. 그렇기에 가상주소는 물리주소로 변환되어야 한다. 가상메모리는 프로세스마다 존재하며 독점적이며 시작주소는 항상 0x0이다. 물리메모리는 가상메모리가 실제 매핑 되는 모든 프로세스가 공유하는 공간이다.

 

가상메모리와 물리메모리의 통합.

• Base register: 물리메모리의 시작 주소를 나타낸다.
• Limit register: 물리 메모리의 끝을 사이즈의 표현으로 나타낸다. → Segmentation fault를 감지함.
• Context switch 시에 base/limit register의 값이 바뀌게 된다.

 

MMU: CPU의 일부분으로 주소 변환을 도와주는 하드웨어이다.

---

Segmentation

위의 base/limit register 방식의 문제점은 내부 단편화가 발생한다는 단점이 있다. 이는 공간의 낭비로 이어진다. 그리고 연속적인 할당을 위해 큰 공간을 찾기 어렵다는 단점이 존재한다. Segmentation은 주소 공간을 독립적으로 관리되는 가변적 크기의 segment로 나누어 불연속적으로 메모리에 배치한다.  Segment는 code/stack/heap segment로 구별된다. 그리고 각 segment 별로 base/limit register를 이용한 관리를 한다. 

 

Segmentation의 주소 변환 방식

가상 주소는 세그먼트 번호와 offset으로 구성된다. 예를 들어 주소공간의 크기는 16KB, 세그먼트의 수는 3개일 경우를 생각해보자.

세그먼트 테이블과 가상 주소의 레이아웃

주소공간의 크기가 16KB라는 것은 총 14개의 비트로 주소를 구별한다는 의미이다. 이 중 세그먼트가 3개일 경우 2개의 비트가 필요하다. 그리고 나머지 하위 비트들은 offset으로 사용된다.

 

이떄, 가상 주소 100, 4200, 7000번을 물리 주소로 변환한다면,

100 = 00 0000 0110 0100 (2). 여기서 00: Code 영역, Offset=100이다. 따라서, 32K+100이 물리주소이다.

비슷한 방식으로,

4200= 01 0000 0110 1000 (2). 01: Heap, Offset=1101000=104. 따라서, 34K+104가 물리주소이다.

7000= 01 1011 0101 1000 (2). 01: Heap, Offset=101101011000=2904. 이때, offset인 2904는 limit register의 크기인 2048을 초과하여 segmentation fault가 발생하는 주소이다.

 

 

Segmentation을 활용하면 얻을 수 있는 장점

• 공간을 활용적으로 사용한다.
• 다중 프로세스 간의 공유가 가능하다. (같은 프로그램 수행 시 코드 세그먼트 영역은 사실상 동일하여 물리메모리에서 공유한다.)
• 세그먼트마다 접근 권한이 있어 보호가 가능하다.

Segment의 크기 지정

• Coarse-grained segment size: 세그먼트가 커져 관리할 세그먼트의 수가 적어진다.
• File-grained segment size: 세그먼트가 많아져 유연하지만 테이블로 관리할 필요가 있다.

Free Space Management

Segmentation과 같은 가변적인 메모리 할당 방식은 외부 단편화를 처리하여야 한다. 물리 메모리의 free한 공간을 적절히 효율적으로 관리하는 기법이 필요하다.

 

외부단편화란, segmenation에서 주소 발생하는 단편화로, 메모리가 할당되고 해제되는 작업이 반복하여 free space가 분리 되는 현상을 의미한다. 그리고 내부단편화는 paging에서 주로 발생하는 단편화로, 고정된 크기 할당에서 발생하는 내부에 발생하는 단편화이다. 실제 사용할 메모리보다 더 큰 공간을 할당해주어 생기는 문제이다.

 

Compaction, Spliting and Coalescing

기본상태: 30B 공간에 20B의 free space가 있으며 중간에 10B 공간을 사용 중이다. Free space를 관리하는 자료구조는 연결리스트이다.

아래와 같은 요청이 올 경우,

1. 10B → 중간의 free entry 한 개를 할당해준다.
2. 10B 이상 → Fail 혹은 Compaction을 통해 할당해준다.
3. 10B 이하 → Spliting을 하여 free entry 하나를 나누어 필요한 공간만큼만 할당해준다.
4. used entry의 반환 → Coalescing으로 이웃한 entry를 합친다.

Free space에서의 할당 정책

• Best-fit: 크기에 가장 알맞은 공간에 할당(남는 공간이 가장 적게 될 곳) → 공간의 효율성
• Worst-fit: 크기에 가장 맞지 않는 공간에 할당(남는 공간이 제일 큰 곳) → 남는 공간을 spliting으로 재활용 가능
• First-fit: 헤드부터 탐색하여 첫 free entry에 할당 → 할당시간이 빠름
• Next-fit: 마지막 할당 공간을 기억하고 그 이후 부터 first fit을 적용 → 공평성

Buddy allocation: 위에서 언급한 할당 정책 이외의 가장 자주 사용되는 할당 정책이다. 2의 거듭제곱 단위로 메모리를 할당해주어 spliting과 coalescing의 간단하다는 장점이 있다.