#19. 연속 메모리 할당(Contiguous Memory Allocation)

연속 메모리 할당

- 다중 프로그래밍 환경

  * 부팅 직후 메모리 상태: O/S + big single hole

  * 프로세스 생성 & 종료 반복 -> scattered holes

(비어있는 메모리 영역을 hole이라고 표현한다. 초기 booting 시에는 OS를 제외한 큰 하나의 hole만 존재한다. 그러나 여러 프로세스가 올라가면서 작은 hole들이 여러개 생기게 되는데 이 흩어져있는 작은 hole들이 여러개 생기는 현상을 메모리 단편화(memory fragmentation)라고 한다.)

- 메모리 단편화 (Memory fragmentation)

  * Hole 들이 불연속하게 흩어져 있기 때문에 프로세스 적재 불가

  * 외부 단편화 (external fragmentation) 발생

  * 외부 단편화를 최소화 하려면?

 

 

- 연속 메모리 할당 방식

  * First-fit (최초 적합) - 순차적으로 가장 먼저 발견된 hole부터 들어갈 수 있으면 할당

  * Best-fit (최적 적합) - 가장 크기가 비슷한 hole부터 할당

  * Worst-fit (최악 적합) - 가장 크기가 맞지 않는 hole부터 할당 (당연히 hole에 들어갈 수 있어야 함)

- 예제

  * Hole: 100 / 500 / 600 / 300 / 200 KB

  * 프로세스 : 212 417 112 426 KB

 

First-fit : {212 : 500}, {417 : 600}, {112 : 228}

Best-fit : {212 : 300}, {417 : 500}, {112 : 200}, {426 : 600}

Worst-fit : {212 : 600}, {417 : 500}, {112 : 388}

 

일반적으로는 어떨까?

- 할당 방식 성능 비교 : 속도 및 메모리 이용률

  * 속도: first-fit

  * 이용률: first-fit, best-fit

- 외부 단편화로 인한 메모리 낭비: 1/3 수준 (사용 불가)

  * Compaction: 최적 알고리즘 없음, 고부담 (hole을 줄이기 위해 최대한 모은다.)

  * 다른 방법은? 바로 페이징!!

 (발상의 전환, 항상 프로세스는 연속적이어야한다는 관점을 바꾸는 기법, 연속적이기에 메모리 단편화 문제가 생김)

 

페이징 (Paging)

(메모리를 일정한 간격으로 자른다.)

과연 프로세스를 일부 간격으로 자르면 과연 실행 될까?

잘라서 실행되도록 하려면 어떻게 해야 할까?

바로 CPU를 속이자. 즉, 주소를 조작해서 CPU가 프로세스를 잘 실행될 수 있도록 하자.

(이전에 MMU의 relocation register를 이용해 access 조작을 했던 것처럼...)

페이지(Page) : 페이징(Paging)을 위한 일정 간격으로 프로세스를 자른 영역

프레임(Frame) : 페이징(Paging)을 위한 일정 간격으로 메모리를 자른 영역

 

그래서 Booting이후 big single hole을 프레임 단위로 메모리를 자른다.

그리고 하드디스크에 있는 프로그램을 Load할 때 프레임 크기에 맞게 프로세스를 자른다.(페이지)

그리고 각 프레임에 해당 페이지를 로드한다.

 

CPU가 메모리 접근 시 relocation register를 이용해 접근 영역을 적절히 조작해서 마치 연속적인 프로세스를 읽는 것처럼 CPU를 속인다.

 

- 프로세스를 일정 크기(=페이지)로 잘라서 메모리에!

  * 프로세스는 페이지(Page)의 집합

  * 메모리는 프레임(Frame)의 집합

- 페이지를 프레임에 할당

  * MMU 내의 재배치 레지스터 값을 바뀜으로서

  * CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각

  * MMU는 페이지 테이블 (page table)이 된다.

(MMU가 relocation register가 여러개 테이블 형식으로 들어있어서 테이블이라 부르고, 페이지 목적으로 된 테이블이므로 페이지 테이블이라고 함. 이를 통해 외부단편화 문제를 완전히 해소한다.)

 

주소 변환 (Address Translation)

- 논리주소 (Logical address)

  * CPU가 내는 주소는 2진수로 표현(전체 m비트)

  * 하위 n비트는 오프셋(offset) 또는 변위(displacement)

  * 상위 m-n 비트는 페이지 번호

- 주소변환: 논리주소 -> 물리주소 (Physical address)

  * 페이지 번호(p)는 페이지 테이블 인덱스 값

  * p에 해당되는 테이블 내용이 프레임 번호(f)

  * 변위(d)는 변하지 않음

 

전체길이 : mbit

n

n

n

n으로 되어있는 일부 메모리 영역을 n이라 할때

m - n을 p (page number)

n을 d (displacement)

 

예를 들어 16byte를 페이지 단위라고 생각해보자. = 2^4

하위 n비트는 4비트가 된다.

만약 1KB가 페이지 단위라면 하위 n 비트는 10비트이다. (1kb = 1024 byte = 2^10)

 

 

주소변환은 어떻게 될까?

MMU를 페이징 시 페이지 테이블 용도로 쓰는데, 

페이지 테이블의 페이지 갯수는 얼마나 될까?

만약 페이지 단위가 1KB이고, 프로세스 크기가 8KB라면 8개의 relocation register가 있는 

페이지 테이블이 될것이다. 

 

이걸 예로 들어보자

Page table	Page Number
0	5
1	4
2	9
3	8
....	...

CPU가 50번지를 읽으려고 한다. 페이지 크기 단위는 16byte이다.

50 -> 11_0010(2)

displacement = 4byte

p(page number) = 11(2) = 3

d(displacement) = 0010(2) = 2

page table의 3번째 페이지에 있는 번호로 주소변환 3 -> 8

displacement는 안바뀜. 따라서 주소의 내용은 이렇게 바뀐다.

p = 8, d = 2 => 1000_0010 = 130

결론 : CPU가 접근할 메모리의 논리 주소는 50번지.

Page Table을 통해 주소 변환된 메모리의 물리 주소는 128번지에서 d(2)만큼 떨어져있는 130번지