[OS] Virtual Memory (1/2)

🔍 Backgroud

프로그램을 실행하기 위해서는 프로그램 코드를 디스크에서 메모리로 가져와야 한다. 만약 물리적인 메모리의 크기보다 프로그램의 크기가 더 크다면 이 프로그램은 실행할 수 없을 것이다. 하지만 실제 프로그램을 보면, 많은 경우에 프로그램 전체가 메모리에 올라갈 필요가 없다는 것을 알 수 있다.
이러한 생각으로 메모리에 프로그램의 일부를 로딩해 실행할 수 있는 가상메모리(Virtual Memory) 개념이 등장했다.

Virtual Memory(가상 메모리)란 ?

가상 메모리는 논리적 메모리와 물리적 메모리을 분리해 실제 메모리 크기와 상관 없이 가상의 메모리를 사용하는 방법을 말한다.

가상 메모리를 사용함으로써 다음과 같은 이점들을 제공한다.

• 프로그램은 사용 가능한 물리적 메모리 크기에 제약을 받지 않는다.
  • 프로그램이 물리적 메모리 크기보다 커져도 실행 가능하다.
• 각 프로그램이 물리적 메모리를 최소한으로 사용하기 때문에 CPU 사용률(Utilization)과 처리량(Thoughput)이 증가해 더 많은 프로그램을 동시에 실행할 수 있다.

가상 메모리를 어떻게 사용할까 ?

프로세스가 논리적 주소를 엑세스할 때, 논리적 주소는 물리적 주소로 변환되어야 한다. 이를 Address Binding이라고 한다.
Address Binding: 논리적 주소를 물리적 주소로 변환하는 것

Address binding은 바인딩 시기에 따라 Complie time binding, Load time binding, Run time binding으로 나눌 수 있다.

Compile time binding

• 컴파일 시 물리적 주소로 바인딩
• 컴파일러가 주소를 변경할 수 없는 absolute code를 만든다.
• 주소가 바뀌면 다시 컴파일해야 한다.
• 컴파일러가 메모리 내용을 다 알고 있어야 해서 상당히 비효율적인 방법이다.
• 한 번 주소가 결정되면 다시 컴파일하기 전까지 고정된 주소 공간을 가지기 때문에 멀티프로그래밍이 불가능하다.

Load time binding

• 프로그램 실행 시 물리적 주소로 바인딩
• 컴파일러가 주소를 변경할 수 있는 relocatable code를 만든다.
  • load time에 주소가 변경될 수 있다.
• 주소가 바뀌면 다시 로드해야 한다.
• 로딩될 때마다 코드에 참조된 주소를 다 변경해줘야 하기 때문에 메모리 로딩 시간이 상당히 오래 걸린다.

Run time binding

• 런타임 시 물리적 주소로 바인딩
• 해당 instruction이 실행될 때 MMU(Memory Management Unit)를 통해 바인딩된다.
• MMU는 relocation(base) register와 limit register를 통해 논리적 주소를 물리적 주소로 바인딩한다.
  • logical addr + relocation register = physical addr
• 주소가 바뀌면 relocation register만 변경하면 된다.

메모리 할당하는 방법

위에서 프로그램을 실행하기 위해서는 메인 메모리로 프로그램 코드를 가져와야 한다고 했다. 그렇다면 어떻게 프로그램에게 메모리를 할당할까? 메모리를 할당하는 방법으로는 크게 Contiguous Allocation, Paging이 있다.

Contiguous Allocation

• Contigous allocation은 말 그대로 메모리에 프로세스를 연속적으로 할당하는 방법이다.
• 프로세스가 필요로 하는 메모리의 크기에 따라 가변적인 파티션 크기를 가진다.
• 연속적으로 메모리를 할당하기 때문에 메모리에 구멍(hole)이 생기게 된다.
• 프로세스를 메모리에 로딩할 때, 프로세스가 필요로 하는 메모리 크기에 적합한 구멍을 찾아 메모리를 할당한다.
• OS는 할당된 영역과 남은 영역에 대한 정보를 유지해야 한다.

장점

• 하드웨어(MMU)가 저렴하다.
  • relocation register와 limit register만 사용하면 됨
• 알고리즘이 간단하다.
  • limit보다 작은지 비교하고 base만 더해주면 됨

단점

• 프로세스의 메모리 크기를 키우기 힘들다.
• code나 data 영역을 공유할 수 있는 방법이 없다.
• 외부 단편화(External Fragmentation)이 발생할 수 있다.
  • 외부 단편화를 해결하기 위해서는 Compaction(압축) 또는 Non-contiguous Allocation 방법이 필요하다.

Paging

• Non-contiguous Allocation 방법으로, 논리적 주소 공간과 물리적 주소 공간을 완전히 분리하여 사용자에겐 연속적인 주소 공간으로 인식하게 하지만, 실제로는 물리 메모리에 흩어져 할당하는 방법이다.
• 물리 메모리는 고정 크기의 Frame으로 분리되고 논리 메모리는 고정 크기의 Page로 분리된다.
• 프로세스 당 page table을 가지며, page table을 통해 논리 주소를 물리 주소로 변환한다.
• page table은 main memory에 저장되고, register에 page table의 위치(Page table base register(PTBR))와 크기(Page table length register(PTLR))를 저장한다.
• OS가 free frame list를 관리한다.

장점

1. Transparency(투명성)

논리 메모리와 물리 메모리가 분리되어 사용자는 논리 메모리만 생각하면 되기 때문에 프로그래밍하기 수월하다.

2. No external fragmentation

고정된 frame에 비연속적으로 할당하기 때문에 외부 단편화가 발생하지 않는다.

• 하지만, Internal fragmentation(내부 단편화)가 발생할 수 있다.
• 예를 들어, 페이지 크기가 1,000B 이고 프로세스 A가 3,002B 의 메모리를 요구한다면, 3개의 프레임(3000B)을 할당하고도 2B를 더 할당해야 하기 때문에 총 4개의 프레임이 필요하다. 결론적으로 4번째 프레임에는 998B(1,000-2)의 여유 공간이 남게 되는 내부 단편화 문제가 발생한다.
• 내부 단편화는 페이지 크기가 작을수록 줄어들지만, page table의 크기가 커져 저장 공간을 더 필요로 하고, page table을 탐색하는 시간이 커지고, 디스크 I/O가 자주 일어나게 되는 문제가 발생한다.

3. Shared page

위와 같이 프로세스 간에 코드나 데이터를 공유할 때, 물리 메모리에는 한 번만 저장하고 각 프로세스가 같은 메모리를 참조하는 형태로 코드나 데이터를 공유할 수 있다.

4. Memory protection

프로세스는 할당된 page table 외부의 메모리에 접근할 수 없다.

Paging에서 Address Binding

CPU는 instruction을 수행하면서 MMU를 통해 page table에 접근하여 논리적 주소를 물리적 주소로 변환한다. 이때 page table 액세스와 data/instruction 액세스 총 2번의 메모리 액세스가 요구된다. 매번 메모리를 두번 액세스하는 것은 굉장히 비효율적이고, 속도가 느리기 때문에 translation look aside buffer(TLB)와 Cache를 사용해 메모리 액세스를 최소화한다.

TLB에는 최근에 참조한 page table entry를 저장하고, Cache에는 최근에 참조한 data나 instruction을 저장한다.

• TLB hit & Cache hit → 0번 memory access
• TLB miss & Cache hit → 1번 memory access
• TLB hit & Cache miss → 1번 memory access
• TLB miss & Cache miss → 2번 memory access

---

Reference

10th edition - Operating System Concepts