[OS] 가상메모리

<운영체제와 정보기술의 원리> 반효경 저

 

운영체제는 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다. 이렇게 되면 프로그램은 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이를 가상메모리(virtual memory)라고 부른다.

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

프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상메모리 기법은 요구 페이징(demand paging) 방식과 요구 세그먼테이션(demand segmentation) 방식으로 구현된다.

 

 

1. 요구 페이징

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

당장 실행에 필요한 페이지만을 메모리에 적재하므로 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다. 또 프로그램을 구성하는 페이지 중 일부만 메모리에 적재하므로 물리적 메모리의 용량보다 큰 프로그램도 실행 가능하다.

이 기법에서는 프로세스가 실행되는 동안 일부 페이지만 메모리에 올라와 있고 나머지는 디스크의 스왑 영역에 존재하므로 특정 프로세스를 구성하는 페이지 중에서 어떤 페이지가 메모리에 존재하고 메모리에 존재하지 않는지 구별하기 위한 방안이 필요하다.

• 유효-무효 비트(valid-invalid bit): 이를 이용하여 각 페이지가 메모리에 존재하는지 표시
• 페이지 부재(page fault): CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우

CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩을 발생시킨다. 그러면 CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴이 호출된다.

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다. 페이지 부재가 일어나면 요청된 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문이다. 즉 페이지 부재가 적게 발생할수록 요구 페이징의 성능은 향상될 수 있다.

 

 

2. 페이지 교체

페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때 물리적 메모리에 빈 프레임이 존재하지 않으면 메모리에 빈 공간을 확보하는 작업이 필요하다.

• 페이지 교체: 메모리에 올라와 있는 페이지 중 하나를 디스크로 스왑 아웃 시키는 것
• 교체 알고리즘: 페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘

페이지 교체 알고리즘의 성능은 주어진 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가 가능하다.

• 페이지 참조열: 참조되는 페이지들의 번호를 시간 순서에 따라 나열한 것
• 적중(hit): 해당 번호의 페이지가 메모리에 이미 올라와 있는 경우
• 페이지 부재: 해당 번호의 페이지가 메모리에 없는 경우

 

최적 페이지 알고리즘

• 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 알고리즘

미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하므로 실제 시스템에서 온라인으로 사용할 수 있는 알고리즘은 아니지만, 어떠한 알고리즘을 사용하는 경우보다도 가장 적은 페이지 부재율을 보장한다.

 

선입선출(First In First Out: FIFO) 알고리즘

• 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 알고리즘

페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓기 때문에 비효율적인 상황이 발생할 수 있다.

• FIFO의 이상 현상(FIFO anomaly): FIFO 알고리즘에서 메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황

 

LRU(Least Recently Used) 알고리즘

• 가장 오래 전에 참조된 페이지를 내쫓는 알고리즘

• 시간지역성(temporal locality): 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질

 

LFU(Least Frequently Used) 알고리즘

• 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내는 알고리즘

페이지의 참조 횟수를 계산하는 방식에 따라 Incache-LFU와 Perfect-LFU로 나뉜다.

• Incache-LFU: 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식
• Perfect-LFU: 메모리에 올라와있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트하는 방식

LRU 알고리즘보다 오랜 시간 동안의 참조 기록을 반영할 수 있다는 장점이 있으나 시간에 따른 페이지 참조의 변화를 반영하지 못하고 구현이 복잡하다는 단점이 있다.

LRU와 LFU 알고리즘은 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 하므로 알고리즘의 운영에 시간적인 오버헤드가 발생한다.

 

클럭 알고리즘

• 하드웨어적인 지원을 통해 알고리즘의 운영 오버헤드를 줄인 방식으로, LRU를 근사시킨 알고리즘

오랫동안 참조되지 않은 페이지 중 하나를 교체한다는 면에서 LRU와 유사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다는 점에서 다르다. 이 알고리즘은 하드웨어적인 지원으로 동작하기 때문에 LRU에 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이루어지므로 대부분의 시스템에서 이 알고리즘을 채택한다.

클럭 알고리즘은 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트(reference bit)를 순차적으로 조사한다. 참조비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다. 알고리즘은 시곗바늘이 한 바퀴 도는 동안 참조비트가 1인 페이지는 0으로 바꾼 후 그냥 지나가고 0인 페이지는 교체한다.

적어도 시곗바늘이 한 바퀴를 도는 데 소요되는 시간만큼 페이지를 메모리에 유지시켜둠으로써 페이지 부재율을 줄이도록 설계되었기 때문에 2차기회 알고리즘이라고도 불린다.

 

 

3. 페이지 프레임의 할당

프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지 결정해야 한다.

• 균등할당: 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 방식
• 비례할당: 프로세스의 크기에 비례해 페이지 프레임을 할당하는 방식
• 우선순위 할당: 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 방식

그러나 이와 같은 할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 우려가 있으니 종합적인 상황을 고려하여 각 프로세스에 할당되는 페이지 프레임의 수를 결정해야 한다.

 

 

4. 전역교체와 지역교체

교체할 페이지를 선정할 때 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분한다.

• 전역교체(global replacement): 모든 페이지 프레임이 교체 대상이 될 수 있는 방법
• 지역교체(local replacement): 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법

지역교체는 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제하는 반면 전역교체는 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변한다.

 

 

5. 스레싱

프로세스가 원활하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야 한다. 최소한의 페이지 프레임을 할당받지 못할 경우 성능상의 심각한 문제가 발생할 수 있다.

• 스레싱(thrashing): 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못해 페이지 부재율(page fault rate)이 크게 상승하고 CPU 이용률이 급격히 떨어지는 현상

CPU 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스의 수, 즉 MPD를 늘리게 된다.

• 다중 프로그래밍의 정도(Multi-Programming Degree: MPD): 메모리에 동시에 올라가 있는 프로세스의 수

MPD가 과도하게 높아지면 각 프로세스에 할당되는 메모리가 감소하여, 프로세스가 필요한 최소 페이지 프레임을 받지 못해 페이지 부재가 빈번히 발생한다. 페이지 부재는 디스크 I/O를 수반하며, 이로 인해 다른 프로세스에게 CPU가 할당된다. 그러나 다른 프로세스도 메모리가 부족해 페이지 부재를 일으켜 또 다른 프로세스에게 CPU가 할당된다. 이러한 현상이 반복되면 시스템은 페이지 부재 처리로 바빠지고 CPU 이용률은 급격히 감소한다. 운영체제는 이를 MPD가 낮아서 발생한 문제로 오인해 또 다른 프로세스를 메모리에 추가하여 상황을 악화시킨다. 이로 인해 스왑 인과 스왑 아웃이 지속적으로 발생하고 CPU는 일을 하지 못하는 상황이 되는데, 이를 스레싱이라고 한다. 따라서, 스레싱을 방지하면서 CPU 이용률을 최대화하도록 MPD를 조절하는 것이 중요하다.

 

워킹셋 알고리즘

• 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘
• 지역성 집합(locality set): 집중적으로 참조되는 페이지들의 집합
• 워킹셋(working-set): 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합

워킹셋 알고리즘에서는 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에 메모리를 할당하고, 않을 경우엔 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃시킨다.

 

페이지 부재 빈도 알고리즘(Page Fault Frequency: PFF)

• 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절하는 알고리즘

어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 프레임을 추가로 더 할당한다. 반면 프로세스의 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄인다.