[운영체제] 연속 메모리 할당

배경 지식

---

Basic Hardware

• Block: 보조기억장치와 주기억장치 사이의 데이터 전송 단위. 1~4KB
• Word: 주기억장치와 레지스터 사이의 데이터 전송 단위. 16~64bits

레지스터와 캐시는 HW가 관리(CPU)하고, 메인 메모리와 보조기억장치는 SW가 관리한다(OS).

CPU는 레지스터를 참조하며, 레지스터 정보는 PCB에 담겨있다. 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다. 개별적인 메모리 공간을 분리하여 보호하기 위해 레지스터는 base와 limit으로 나뉘진다. base는 프로세스가 메모리에서 사용할 수 있는 가장 작은 physical address를 의미하며,limit은 사용할 수 있는 주소의 크기를 의미한다. 즉, 프로세스가 사용할 수 있는 가장 큰 주소는 base와 limit의 합이다. 따라서 어떤 프로세스의 base가 300040이고, limit이 120900이라면 프로세스가 접근할 수 있는 메모리 주소의 범위는 300040부터, 300040에 120900를 더한 420940까지가 된다.

주소 할당(Address Binding)

명령과 데이터를 메모리 주소로 바인딩하는 시점에 따라 구분이 된다.

• Compile time: 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있다면 컴파일러는 절대코드(absolute code)를 생성할 수 있다. 그러나 위치가 변경된다면 코드를 다시 컴파일해야 한다. 프로그램 전체가 메모리에 올라가야 한다.
• Load time: 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못한다면 컴파일ㅇ러는 이랃ㄴ 이진 코드를 재배치 가능 코드(relocatable code)로 만들어야 한다. 이 경우 최종 바인딩은 로드의 소요 시간만큼 지연 된다. 시작 주소가 변경된다면 이 값을 포함하기 위해 사용자 코드를 다시 적재하기만 하면 된다. 프로그램 전체가 메모리에 올라가야 한다.
• Execution time: 프로세스가 실행 중 메모리의 한 세그먼트에서 다른 세그먼트로 이동할 수 있다면 바인딩은 runtime까지 지연되어야 한다. 하드웨어(MMU)의 도움이 필요하다. 대부분의 OS가 이 방법을 사용한다.

논리 주소 공간 VS 물리 주소 공간

CPU가 생성하는 주소는 논리 주소(logical address)이고,메모리가 취급하는 주소는 물리 주소(physical address)이다. compile-time과 load-time에서 주소를 바인딩할 때는 논리 주소와 물리 주소가 같게 생성되는 반면 execution-time에서는 다르게 생성된다. 이때의 논리 주소를 가상 주소(virtual address)라고 한다.

가상 주소를 물리주소로 run-time에 변환(mapping)하는 작업은 하드웨어 장치인 메모리 관리 장치(MMU, memory management unit)에서 일어난다. 가장 간단한 MMU 변환 기법은 아래 그림과 같다. 이때 base 레지스터는 relocation 레지스터라고 부른다. 따라서 어떤 relocation 레지스터의 값이 14000이라면 프로세스가 346에 접근시 14346으로 맵핑이 된다.

동적 적재(Dynamic Loading)

메모리 공간을 효율적으로 이용하기 위해서는 동적 적재(dynamic loading)을 해야 한다. 동적 적재에서 routine은 호출되기 전까지 적재되지 않는다. 각 routine은 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기한다. 이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 실행할 코드가 많을 경우에 유용하다.

 

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

---

단편화(Fragmentation)

• 내부 단편화(Internal fragmentation): 파티션의 크기>프로세스의 크기. 
• 외부 단편화(External fragmentation): 남은 메모리의 크기>프로세스의 크기. 연속된 공간이 아님. 

1. 고정 분할 할당(FPM)

고정 분할 방법에서는 메모리를 여러 개의 고정된 크기로 분할하고 분할된 각 메모리는 프로세스 하나를 실행하는 방식이다. 고정 분할 방법에서는 논리적 주소가 분할된 메모리보다 크면 오류가 발생하고, 작으면 내부 단편화가 발생한다.

2. 가변 분할 할당(VPM)

가변 분할 방법은 고정된 경계를 없애고 각 프로세스가 필요한 만큼 메모리를 할당하는 방법이다. 프로세스가 할당되고 해제되다보면 사용 가능한 메모리 공간이 흩어져있게 되는데(hole이 생김), 새로 들어갈 작업이 어느 공간에 할당되어야 할 지 결정하는 방법으로는 최초 적합, 최적 적합, 최악 적합 방법이 있다.

• 최초 적합(First fit): 프로세스가 사용 가능한 충분한 크기를 가진 첫번째 파티션을 선택한다. 공간 효용률이 떨어질 수 있다.
• 최적 적합(Best fit): 프로세스가 들어갈 수 있는 파티션 중 가장 작은 곳을 선택한다. 탐색시간이 오래걸린다(모든 파티션을 살펴보아야 하기 때문에). 활용하기에 너무 작은 파티션이 많이 발생한다.
• 최악 적합(Worst fit): 프로세스가 들어갈 수 있는 파티션 중 가장 큰 곳을 선택한다. 탐색 시간이 오래걸린다(모든 파티션을 살펴보아야 하기 때문에). 작은 크기의 파티션 발생을 줄일 수 있으나 큰 크기에 파티션 확보가 어렵다.

가변 분할 할당에서는 내부 단편화는 일어나지 않지만 외부 단편화가 생긴다. 이러한 외부 단편화를 해결할 방안으로 메모리 통합과 메모리 압축 방법이 있다.

• 메모리 통합: 하나의 작업이 끝났을 때 다른 빈 공간과 인접해 있는지 점검하여 하나로 합친다. low overhead.

  

• 메모리 압축: 메모리의 내용을 움직여 빈 공간을 하나로 합친다. 모든 프로세스를 재배치(프로세스 중지)를 해야 함으로 high overhead가 일어난다.