[OS] 7. 가상 메모리 (Virtual Memory)

7. 가상 메모리 (Virtual Memory)

1. 가상 메모리
2. 요구 페이징
3. 페이지 교체 알고리즘

 

1. 가상 메모리 (Virtual Memory)

1.1. 배경

운영체제는 CPU에서 당장 수행해야 할 부분만 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역(Swap Area) 에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다. 이와 같이 메모리의 연장 공간으로 스왑 영역이 사용될 수 있기 때문에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없다.

1.2. 개념

가상 메모리는 프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다.

 

 

2. 요구 페이징

2.1. 요구 페이징 (Demand Paging)

프로그램 실행 시, 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 메모리에 올리는 방식이다.

당장 실행에 필요한 페이지만을 메모리에 적재하기 때문에, 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는 데 들었던 입출력 오버헤드도 줄어든다.

요구 페이징에서는 유효-무효비트 를 두어 각 페이지가 메모리에 존재하는지를 구별한다.

유효비트

• 현재 페이지가 메모리에 있는 경우

무효비트

• 현재 페이지가 스왑 영역에 있는 경우

2.2. 페이지 부재 (Page Fault)

CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효비트가 무효로 세팅되어 있는 경우를 말한다.

페이지 부재 처리

CPU가 무효 페이지에 접근하면, 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩(page fault trap) 을 발생시킨다. 그러면 CPU 제어권이 커널 모드로 전환되고, 운영체제의 페이지 부재 처리 루틴(page fault handler) 이 호출되어 아래와 같이 처리를 진행한다.

1. 해당 페이지에 대한 접근이 적법한지를 체크

2. 물리적 메모리에서 비어 있는 프레임(free frame) 을 할당받아 그 공간에 해당 페이지를 읽어옴

   • 만약 비어 있는 프레임이 없다면 페이지 중 하나를 스왑 영역으로 쫓아냄 swap out

이 과정은 오랜 시간이 소요되므로, 페이지 부재를 발생시킨 프로세스는 CPU 제어권을 빼앗기고 blocked 상태가 된다. 작업이 모두 완료되면 해당 페이지를 다시 유효비트로 설정하고, blocked 상태의 프로세스를 ready queue 로 이동시킨다.

 

 

3. 페이지 교체 알고리즘

페이지 부재가 발생했을 때, 페이지 부재율을 최소화하여 swap out 시킬 페이지를 선택하는 알고리즘

 

3.1. 최적 페이지 교체 (Optimal Page Replacement)

페이지 교체시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 방법이다. 이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전재 하에 운영하므로 실제로 사용할 수 있는 알고리즘은 아니다.

3.2. FIFO 알고리즘

페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다. 페이지의 향후 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에 비효율적인 상황이 발생할 수 있다.

FIFO 이상 현상

메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황

3.3. LRU 알고리즘

최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높다는 시간 지역성(Temporal Locality) 을 활용해서 페이지 교체시 가장 오래 전에 참조가 이루어진 페이지를 교체하는 방법이다.

3.4. LFU 알고리즘

페이지 부재시 과거에 참조 횟수가 가장 적었던 페이지를 교체하는 방법이다. 최저 참조 횟수를 가진 페이지가 여러 개 존재한다면 임의로 하나를 선정하여 쫓아낸다. LRU 는 직접 참조된 시점만을 반영하지만, LFU 는 참조 횟수를 통해 장기적인 시간 규모에서의 참조 성향을 고려한다는 장점을 가지고 있다.

3.5. Clock 알고리즘

LRU 와 LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 유지해야 하므로 시간적인 오버헤드가 발생한다. 클럭 알고리즘은 하드웨어적인 지원을 통해 운영 오버헤드를 감소시킨 방법이다.

LRU 를 근사(approximation)시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 라고 불린다. LRU 이 가장 오래 전에 참조된 페이지를 교체하는 것에 비해, 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있다.

• 하드웨어에 의해 조작되며 운영체제는 참조 비트(Reference bit) 를 참고하여 Victim 결정
• Reference bit = 1 (최근사용) , Reference bit = 0 (최근사용 X)
• 시계방향으로 움직이며 참조 비트가 1이면 0으로 바꾸고, 한바퀴 돌고와서도 0인 것을 교체