Memory Allocation
컴퓨터 부팅 직후에 메인 메모리는 OS를 제외하고 큰 구멍이 생긴 것처럼 보인다. 다중 프로그래밍에서는 다수의 프로그램들이 메모리에 적재되어 프로세스의 생성과 종료를 반복한다. 그렇기 때문에 한정된 메모리 공간을 여러 프로세스에게 효율적으로 나누고 메모리 사용률을 높이는 것이 중요하다고 할 수 있다. OS는 이 역할을 담당할 뿐만 아니라 사용 중인 메모리와 비어 있는 메모리에 대한 정보를 관리한다.
| 방법 | 종류 (다중 프로그래밍 기준) |
|---|---|
| Contiguous Allocation | fixed partition, variable partition |
| Discontiguous Allocation | fixed partition(Paging), variable partition(Segmentation) |
Contiguous Allocation
하나의 프로세스를 메모리 공간에서 하나의 연속적인 주소 공간에 할당하는 방법이다. 재배치 레지스터를 사용함으로써 논리적 주소를 물리적 주소로 동적으로 바꿀 수 있다. 또한 이 레지스터로 인해 사용자 프로세스들을 서로로부터, 그리고 운영체제를 사용자 프로세스로부터 보호할 수 있다. 다중 프로세스를 메모리에 적재하는 방법은 fixed partition과 variable paritition이 있다.
메인 메모리에 비어있는 공간을 hole이라고 하자. OS는 적재하려는 프로세스의 크기보다 큰 hole을 할당한다. 어떤 기준으로 비어있는 hole에 프로세스를 넣을 것인지에 따라 first-fit, best-fit, worst-fit으로 나뉜다.
Dynamic allocation
1. First-Fit: 메모리를 위에서부터 아래로 순서대로 훑고, 프로세스를 적재할 수 있는 hole 중 가장 첫번째로 만난 곳에 할당한다. search 시간이 적게 소요되지만 공간 활용률이 떨어질 수 있다.
2. Best-Fit: 메모리를 위에서부터 아래로 순서대로 훑고, 프로세스를 적재할 수 있는 hole 중 가장 작은 곳에 할당한다. 이로써 공간 활용률은 상승하지만 hole이 크기에 따라 정렬되어 있지 않으면 메모리 전체를 search 해야 한다.
3. Worst-Fit: 메모리를 위에서부터 아래로 순서대로 훑고, 프로세스를 적재할 수 있는 hole 중 가장 큰 곳에 할당한다.
메모리 보호
메모리를 할당한 공간마다 기준 레지스터와 경계 레지스터를 두고 이를 통해 프로세스의 메모리 접근을 제어한다. 예를 들어 partition 1에 해당하는 기준 레지스터와 경계 레지스터의 값이 1000, 500이고, 프로세스가 접근하려는 주소가 400이라고 하자. (참고로 이 partition의 물리적 주소 공간은 1000부터 1500이다.) 먼저 경계 레지스터와 논리적 주소를 비교한다. 논리적 주소 > 경계 레지스터라면 잘못된 메모리 접근으로 처리하고, 그렇지 않다면 논리적 주소에 기준 레지스터를 더하여 메모리에 접근한다.
Fixed Partition
메모리를 여러 개의 고정된 크기의 partition으로 분할하여 비어 있는 곳에 프로세스를 할당하는 방법이다. partition의 크기와 프로세스의 크기가 같지 않다면 내부에 메모리가 반드시 남게 된다. 그리고 프로세스가 적재되어 있는 동안 어떤 프로세스들에게도 할당되지 못하는데 이를 internal fragmentation이라고 한다. 이외에도 partition의 개수가 정해져 있어 다중 프로그래밍의 정도가 제한되어 성능이 떨어질 수 있다.
Variable Partition
고정된 크기의 공간이 아닌 프로세스가 필요한 만큼 메모리를 할당하는 방법이다. 다중 프로그래밍의 경우 크기가 다른 프로세스들이 생성과 종료를 반복한다면 군데군데 비어있는 공간이 생기게 될 것이고, 그 크기보다 큰 프로세스를 메모리에 적재할 수 없을 것이다. 메모리의 공간이 남아있음에도 프로세스를 적재하기에 충분히 큰 공간은 없는 것을 external fragmentation이라고 한다.
Discontiguous Allocation
하나의 프로세스를 잘라 메모리 공간에서 여러 개의 불연속적인 주소 공간에 할당하는 방법이다. 즉, contiguous allocation과 달리 같은 프로세스에 속하더라도 메모리 상에서는 불연속적인 공간에 할당될 수 있음을 주의하자.
Paging
프로세스를 일정한 크기로 잘라 고정된 크기의 partition에 할당한다. 잘린 프로세스의 조각을 page, 잘린 메모리의 공간을 frame이라고 부른다. internal fragmentation 문제가 있다.
Address Translation
논리적 주소는 페이지 테이블 상의 인덱스를 나타내는 페이지 번호와 페이지 내 오프셋으로 구성된다. 페이지 테이블의 엔트리는 프레임 번호로 구성되며 이를 참고하여 물리적 주소를 계산한다.
| 인덱스(페이지 번호) | 프레임 번호 |
|---|---|
| 0 | 4 |
| 1 | 0 |
| 2 | 1 |
| 3 | 5 |
| 4 | 2 |
| 5 | 3 |
예를 들어 페이지 테이블이 위와 같고 페이지 크기는 4 byte이며 논리적 주소가 20(=10100)에 해당하는 물리적 주소를 구해보자. 페이지 크기가 2^2이므로 하위 2비트는 오프셋으로 사용되고 남은 상위 비트들은 페이지 번호가 된다. 따라서 페이지 번호는 5, 오프셋은 0이다. 페이지 테이블에 따르면, 인덱스가 5인 엔트리는 3이다. 물리적 주소를 구하면 3 * 4(페이지 크기) + 0(오프셋) = 20이 된다.
위에서 이미 눈치를 챘을 수도 있겠지만 페이지 번호는 페이지 테이블의 크기, 오프셋은 한 페이지의 크기와 관련이 있다. 16비트 주소에서 상위 6비트가 페이지 번호로, 하위 10비트가 오프셋을 나타낸다고 하자. 그러면 2^10 byte 크기의 페이지가 64개 존재한다는 뜻이다.
❗️경계 레지스트가 없는 이유❗️
고정된 크기로 메모리가 분할되어 있고(=페이지) 페이지의 크기에 해당하는 비트 수를 오프셋으로 활용하기 때문에 경계 레지스터가 필요 없다.
Segmentation
Variable partition를 사용해 메모리를 할당한다. 하나의 프로그램은 main program, procedure, function, local variable, global variable, symbol table 등의 논리적 단위로 구성되어 있다. 각 논리적 조각을 세그먼트(segment)라고 하며, 각 세그먼트의 크기 만큼만 메모리를 할당한다. external fragmentation 문제가 있다.
Address Translation
논리적 주소는 세그먼트 테이블 상의 인덱스를 나타내는 세그먼트 번호와 세그먼트 내 오프셋으로 구성된다. 접근하고자 하는 메모리 주소는 세그먼트 테이블에 있는 해당 세그먼트의 기준 레지스터와 경계 레지스터를 참고하여 계산한다.
| 인덱스(세그먼트 번호) | 경계 레지스터 | 기준 레지스터 |
|---|---|---|
| 0 | 100 | 0 |
| 1 | 300 | 200 |
| 2 | 100 | 1000 |
| 3 | 500 | 1500 |
예를 들어 세그먼트 테이블이 위와 같고 32비트 주소 공간에서 세그먼트 번호가 3, 오프셋이 200라고 하자. 인덱스 3에 해당하는 경계 레지스터와 기준 레지스터를 보면 된다. 오프셋 < 경계 레지스터이므로 물리적 주소는 기준 레지스터를 더해 1500 + 200 = 1700이 된다.
❗️경계 레지스트가 있는 이유❗️
위와 반대로 가변적인 크기로 메모리가 분할되어 있고(=세그먼트) 오프셋으로 사용하는 비트 수는 고정되어 있다. 따라서 임의의 오프셋이 세그먼트 주소 범위를 벗어날 수 있다.
