[운영체제와 정보기술의 원리] 08장. 가상메모리

운영체제는 보통 모든 모든 프로그램에게 공평하게 같은 크기의 메모리를 할당하기보다는 몇몇 프로그램들에게 집중적으로 메모리를 할당 후 시간이 지나면 메모리를 회수해서 다른 프로그램들에게 다시 집중적으로 할당하는 방식으로 동작한다. 프로세스의 주소 공간 전체가 메모리에 올라와있지 않고, 수행할 부분만 메모리에 올라가고 나머지는 디스크의 스왑영역에 있다가 교체하는 방식이다.

추가적으로 운영체제는 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만의 메모리를 사용하는 것처럼 0번지 부터 시작하는 자신만의 메모리 공간인 가상 메모리를 제공한다. 가상메모리는 방식에 따라 요구 페이징과 요구 세그먼테이션 방식으로 구현된다.

 

요구 페이징

 요구 페이징이란 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는  것이 아니라 당장 사용될 페이지만을 메모리에 올리는 방식이다. 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재하는 방식이다.  당장 필요한 부분만 메모리에 올리기에 메모리 사용량이 감소하고, 입출력 오버헤드도 줄어들게 된다. 또한 물리적 메모리의 용량 제약을 벗어날 수 도 있게된다. 

페이지 테이블에서 유효-무효 비트의 의미

메모리에 올라와있지 않은 페이지들은 디스크의 스왑 영역에 존재한다. 어떤 페이지가 메모리에 존재하는지 구분하기 위해 요구 페이징에서는 유효-무효 비트를 사용하여 표시한다. 이 비트는 각 프로세스를 구성하는 모든 페이지에 대해 존재해야하기 때문에  페이지 테이블의 각 항목별로 저장된다.

 

요구 페이징의 페이지 부재 처리

페이지 부재를 처리하는 과정

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

 

요구 페이징의 성능

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

 

페이지 교체

페이지 교체의 예

디스크에서 메모리로 페이지를 불러올때 빈 프레임이 존재하지 않는 경우 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 페이지 교체가 필요하다. 이때 적절한 교체 알고리즘을 사용하여 페이지 부재율을 최소화하는 것이 중요하다.

 

최적 페이지 교체

최적 페이지 교체 알고리즘을 사용한 페이지 교체

최적 페이지 교체는 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫒아내는 방식이다. 이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제하에 알고리즘을 운영하기에 실제 시스템에서 온라인으로 사용할 수는 없다. 

 

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

FIFO 알고리즘에 의한 페이지 교체

선입선출 알고리즘은 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫒는 방식이다. 향후 참조 가능성을 고려하지 않는다. 다만 무조건 선입선출이기에 일부 페이지에 대해서 비효율적인 상황이 발생할 수 있다. 

 

LRU 알고리즘 (Least Recently Used)

LRU 알고리즘을 적용한 경우의 페이지 교체

LRU 알고리즘은 페이지 교체 시 가장 오래전에 참조가 된 페이지를 내쫒는 방식이다. 시간지역성을 고려한 알고리즘으로써 마지막 참조 시점이 가장 오래된 페이지를 교체하게 된다. 

 

LFU 알고리즘 (Least Frequently Used)

LRU 알고리즘과 LFU 알고리즘의 비교

LFU 알고리즘은 페이지의 참조 횟수로 교체시킬 페이지를 결정하는 방법이다. 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내고 그자리에 새로 참조될 페이지를 적재하게 된다. LFU 알고리즘은 LRU 알고리즘에 비해 오랜 시간 동안의 참조 기록을 반영할 수 있지만, 시간에 따른 페이지 참조의 변화를 반영하지는 못한다.  

 

클럭 알고리즘

클럭 알고리즘

LRU와 LFU 알고리즘은 페이지의 참조를 소프트웨어적으로 유지하고 비교하기 때문에 오버헤드가 발생한다. 클럭 알고리즘은 하드웨어적인 지원을 통해 오버헤드를 줄인 방식이다. 클럭 알고리즘은 NUR(Not Used Recently) 알고리즘이라고도 불린다. 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. LRU와 비슷하지만 가장 오래된 페이지를 교체를 보장하지 않는다는 점에서 다르다. 클럭 알고리즘은 참조비트를 활요한다.

 

페이지 프레임의 할당

프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지 결정해야 한다. 이를 위해 효율적인 메모리할당 알고리즘을 사용한다. 첫번째로 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 균일 할당 방식이 있다. 두번째로는 프로세스의 크기에 비례해 페이지 프레임을 할당하는 비례 할당 방식이 있다. 마지막으로 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 우선순위 할당 방식이 있다. 

 

전역교체와 지역교체

교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위를 어떻게 정하는지에 따라 전역교체와 지역교체로 나눌 수 있다. 전역교체는 모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다. 지역교체는 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법이다. 

 

스레싱

프로세스가 원할하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야 한다. 집중적으로 참조되는 페이지들의 집합을 한번에 메모리에 적재하지 못하면 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어질 수 있는데 이것을 스레싱이라고 한다. 

스레싱이 발생하는 경우

CPU 이용률이 낮으면 메모리에 올라가는 프로세스의 수를 올리게 된다. 즉 CPU 이용률이 낮을 경우 운영체제가 다중프로그래밍의 정도(MPD)를 높인다. 다만 과도하게 MPD가 높아지면 각 프로세스에게 할당되는 메모리양이 지나치게 감소된다. 이렇게 되면 페이지 부재율이 크게 상승하게 되고 스레싱이 발생하게 된다. 따라서 스레싱을 방지하기 위해 MPD를 조절하는 알고리즘인 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있다.

 

워킹셋 알고리즘

집중적으로 참조되는 페이지들의 집합을 지역성 집합이라고 한다. 워킹셋 알고리즘은 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다. 프로세스가 일정 시간 동안 원할히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋이라 하고, 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우만 메모리를 할당하는 방식이다.

 

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

페이지 부재 빈도 알고리즘

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

 

 

출처
운영체제와 정보기술의 원리 - 이화여자대학교출판문화원 출판, 반효경 저

운영체제와 정보기술의 원리 - 교보문고