운영체제 시리즈 12. Virtual memory

운영체제가 프로세스에게 어떤 식으로 메모리를 할당하는지 알아본다. CPU가 바라보는 메모리 영역을 가상 메모리 영역이라고 한다. 각 프로세스마다 독자적인 0번지부터 시작하는 가상 메모리 공간을 가지게 된다. (메모리 공간이 4기가라면 모든 프로세스는 본인이 4기가를 모두 사용하고 있다고 생각한다.)

 

메모리를 적재하는 단위에 따라 요구 페이징(demand paging) 방식과 요구 세그먼테이션(demand segmentation)방식으로 나뉘지만 세부적 구현에서는 요구 페이징 기법만이 사용된다.

요구 페이징(Demand paging)

실제로 필요할 때 페이지를 물리적 메모리에 올리는 기법이다. 메모리 사용량이 감소하고, 입출력 오버헤드도 줄어든다. 따라서 빠른 응답시간을 기대할 수 있으며 더 많은 프로세스를 수용할 수 있게 해준다. 어떤 메모리가 메모리에 존재하고 존재하지 않는지 구별하기 위해 유효-무효비트(valid-invalid bit)를 사용한다. 페이지 테이블에 프레임 번호와 더불어 무효-유효 비트를 표기한다. 무효로 셋팅되어 있는 경우를 페이지 부재(page fault)가 일어났다고 한다.

Page fault

CPU가 무효 페이지에 접근하면 MMU가 페이지 부재 트랩(page fault trap)을 발생시킨다. 사용자모드에서 커널모드로 전환되고 OS의 page fault handler가 호출된다.

 

page fault

 

페이지 부재루틴(page fault handler)의 처리방법은 다음과 같다. 참조하는 페이지 테이블에서 무효비트로 선언되어 있으면 트랩이 발생된다. 트랩이 발생하면 OS는 해당 페이지의 접근 권한이 있는지 확인한다. bad address나 protection violation의 경우에는 해당 프로세스를 종료(abort) 시킨다. 그렇지 않고 접근권한이 유효한 경우 디스크에서 해당 페이지에 접근하고 물리 메모리에서 빈 페이지를 할당받아 해당 페이지를 올린다. 디스크 입출력이 완료되면 페이지 테이블에서 무효비트를 유효비트로 재설정한다. 봉쇄되었던 프로세스를 준비큐로 이동시키고 다시 CPU를 할당받으면 중돤되었던 명령(instruction)부터 재시작 한다.

요구 페이징의 성능

요구 페이징의 성능을 크게 좌지우지 하는 것은 page fault의 빈도이다. page fault가 일어나면 디스크 입출력, 문맥교환 등의 오버헤드가 발생하기 때문이다.

 

 

페이지 교체

페이지 부재가 발생해서 페이지를 읽어왔는데 물리적 메모리에 빈 프레임이 존재하지 않을 수도 있다. 이 경우 물리적 메모리에 올라와 있는 페이지 중 하나를 쫓아내고 빈 공간을 확보해야 한다. 이것을 페이지 교체(page replacement)라고 한다. 이것을 결정하는 알고리즘을 교체 알고리즘(replacement algorithm)이라고 하는데, 알고리즘의 목표는 페이지 부재율(page-fault rate)를 최소화하는 것이다. 해당 페이지가 메모리에 올라와 있다면 메모리에서 적중(hit)되었다고 하고, 아닌 경우 페이지 부재가 발생했다고 한다. 아래에서 페이지교체 알고리즘에 대해 정리해보도록 하겠다.

최적 페이지 교체(Optimal algorithm)

가장 먼 미래에 참조될 페이지를 쫓아내면 된다. 이 알고리즘은 미래에 페이지가 어떤 순서로 참조될 지 알고 있다는 가정하에 진행된다. 실제 온라인에서 사용할 수 없어 오프라인 알고리즘이라고 하지만, 알고리즘 성능에 대한 상한선을 제공한다. 따라서 어떤 알고리즘이 optimal algorithm과 가깝다면 최적화된 알고리즘이라고 판단한다.

선입선출 알고리즘(FIFO)

물리적 메모리에 먼저 올라온 페이지를 우선적으로 내쫓는 알고리즘이다. 상황을 고려하지 않기 때문에 비효율적인 경우가 발생할 수 있다. 프래임을 증가 시켰는데도 page fault가 증가하는 현상이 발생될 수도 있는데 이것을 FIFO의 이상현상(FIFO anomaly)라고 한다. 

LRU 알고리즘

가장 오래전에 참조된 페이지를 쫓아내는 방식이다. LRU 알고리즘에서는 FIFO 이상현상이 발생하지 않는다. 링크드리스트와 비슷하게 시간 순서대로 줄세우기를 하며 시간 복잡도는 O(1)이다.

LFU 알고리즘

참조횟수가 가장 적은 페이지를 쫓아내는 방식이다. 최저 참조 횟수가 같은 페이지가 여러개라면 그 중 임의로 선정한다. 페이지 참조횟수를 계산하는 방식에 따라 Incache-LFU와 Perfect-LFU로 나뉜다. Incache-LFU는 메모리에 올라온 후부터 참조횟수를 계산하는 경우라 쫓겨났다 온 경우 다시 1부터 시작한다. Perfect-LFU는 과거 참조횟수까지 포함하여 계산하는 것으로 Incache-LFU보다 오버헤드가 크다. 

줄세우기를 하는데 참조횟수를 비교해서 몇번째인지 확인해야함으로 시간 복잡도는 O(n)이다. 따라서 이진트리로 구현하여 O(log n)으로 계산한다. 

LFU를 사용할 경우 이제부터 참조가 많아지는 페이지를 알아낼 수 없다. 과거에 자주 참조되던 페이지보다 이제 많이 참조되는 페이지가 있을 수 있는데, 이 경우에도 계속 참조가 일어나는 페이지를 쫓아내게 되는 경우가 발생할 수 있다.

클럭 알고리즘

LRU, LFU는 소프트웨어적으로 유지 비교하므로 오버헤드가 크다. 클럭 알고리즘은 하드웨어적 지원을 통해 알고리즘의 오버헤드를 줄인다. LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently), NRU(Not Recently Used)라고 불린다. 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 내쫓는다. 페이지 참조 시점이 가장 오래되었음을 의미하지는 않는다.

참조되는 페이지를 1로 비트를 바꾼다. 한바퀴를 돌 동안 참조되지 않는 페이지(0 비트)를 쫒아내는 알고리즘이다. LRU와 일치하지 않지만 적어도 1바퀴 도는 동안 참조가 안 된 페이지를 쫓아낸다.

 

reference bit과 더불어 modified bit(dirty bit)도 함께 사용한다. modified bit이 1이라면 최근에 write가 발생한 페이지를 의미한다. 따라서 쫓아낼 땐 backing store에 변경 내용을 반영하여 쫓아낸다. 가능하면 reference bit이 0인 것 중에서 modified bit이 0인 것을 쫓아낸다. 

페이지 프레임의 할당

각 프로세스에게 얼마만큼의 메모리 공간을 할당할 것인지 결정해야 한다. 할당 알고리즘은 3가지로 나누어 볼 수 있다.

 

1. 균등할당(equal allocation) : 모든 프로세스에게 페이지 프레임을 균등하게 할당

2. 비례할당(proportional allocation) : 프로세스 크기에 비례하여 프레임을 비례 할당

3. 우선순위할당(priority allocation) : 당장 CPU에게 실행될 프로세스에게 더 많은 페이지 프레임을 할당

 

명령어 수행을 위해서 최소한 할당되어야 하는 페이지 프레임은 충족시켜야 하며, loop를 구성하는 페이지들은 한 번에 할당되는 것이 유리하다.

전역교체와 지역교체

전역교체에서는 다른 프로그램도 쫓아낼 수 있다. 그때마다 경쟁하면서 메모리 공간을 차지한다. 지역교체는 자신에게 할당된 페이지 프레임 내에서만 교체가 일어난다. 자신의 몫 중에서 메모리 공간을 활용한다.

스레싱(thrashing)

프로세스의 원활한 수행을 위해 최소한의 페이지 프레임 수를 할당받지 못 한 경우 발생한다. 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어지는 현상을 스레싱(thrashing)이라고 한다. 메모리에 올라온 프로세스가 너무 많으면 각 프로세스가 가진 메모리 공간의 크기가 매우 작아진다. 이 경우 page fault가 많이 발생되어 IO 작업이 많아지고 CPU 이용률이 급격하게 떨어지는 것이다. 동시에 메모리에 올라간 프로세스의 수(MPD : Multi-Programming Degree)를 조절해주어야 한다.

워킹셋 알고리즘

프로세스는 일정 시간 동안 집중적으로 참조하는 페이지가 있는데 이 페이지의 집합을 지역성 집합(locality set)이라고 한다. 지역성에 기반하여 프로세스가 일정 시간동안 원활히 수행되기 위해 한 번에 메모리에 올라와 있어야 하는 페이지들의 집합을 working set 이라고 한다. 워킹셋 모델에서는 프로세스의 워킹셋 전체가 메모리에 올라와 있어야 하고, 그렇지 않으면 모든 프레임을 반납 후 스왑아웃시킨다. 과거시간을 통해 델타시간(window size)을 정해 현재~델타시간까지참조되는 페이지들을 워킹셋으로 판단한다. 워킹셋의 크기는 가변적이다. 

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

페이지 부재율(page-fault rate)을 주기적으로 조사하고 이 값에 근거하여 각 프로세스에 할당할 메모리 양을 동적으로 조정한다. page-fault rate의 상한값과 하한값을 둔다. page-fault rate가 상한값을 넘으면 프레임을 더 할당하고, 하한값 이하이면 할당하는 프레임의 수를 줄인다. 

정리

page-fault가 일어나면 IO작업이 많아지기 때문에 성능이 저하된다. 메모리 공간이 부족할 때, 어떤 페이지를 쫓아내고 필요한 페이지를 받아올 것인지(replacement), 프로세스에게 얼마만큼의 메모리를 할당할 것인지(allocation) 등을 결정해야 한다. 이 모든 알고리즘은 결국 page-fault rate를 줄여서 빠른 일처리를 가능하게 하려는 목적이 있다.

 

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.