Operating System - 페이지 교체 알고리즘

가상 메모리(Virtual Memory)

가상 메모리(Virtual Memory)의 필요성

프로그램이 CPU에서 실행되기 위해서는 실행에 필요한 부분이 메모리에 올라와 있어야 한다. 또한, 여러 프로그램이 동시에 수행되는 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어서 사용해야 하는데, 이를 위해서는 운영 체제가 적절히 프로세스에 메모리를 할당해야 한다.

운영체제는 CPU에서 당장 수행해야 하는 부분만 메모리에 올리고, 나머지는 디스크의 swap 영역에 저장해 두었다가 다시 필요해지면 기존에 메모리에 있었던 부분과 교체하는 방식을 사용한다.

이처럼, 메모리의 연장 공간으로 디스크의 swap 영역을 사용하게 된다면 메모리의 물리적인 크기에 대한 제약을 고려할 필요가 없어진다.

즉, 가상 메모리는 메모리의 물리적인 크기의 한계를 극복하기 위해 나온 기술이며, 프로세스 전체가 메모리 내에 올리오지 않더라도 실행이 가능하도록 하는 기법을 말한다.

---

요구 페이징(Demand Paging)

요구 페이징(Demand Paging)이란?

프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라, 당장 사용될 페이지만 올리는 방식이다. 특정 페이지에 대해 CPU의 요청이 들어온 후에 해당 페이지를 메모리에 적재하는 것이다.

특정 프로세스를 구성하는 페이지 중 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않는 지를 구별해야 한다. 요구 페이징에서는 valid-invalid bit(유효-무효 비트)를 사용하여 각 페이지가 메모리에 존재하는지 표시한다.

 

 

프로세스가 실행되기 전에는 모든 페이지의 valid-invalid bit가 무효 값으로 초기화되어 있지만, 특정 페이지가 참조되어 메모리에 적재되는 경우 해당 페이지의 valid-invalid bit는 유효 값으로 바뀌게 된다. 그리고 해당 페이지가 디스크의 swap 영역으로 쫓겨날 경우 무효 값으로 다시 바뀌게 된다.

CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아서 valid-invalid bit가 무효 값으로 설정되어 있는 경우를 페이지 부재라고 한다.

---

페이지 부재(Page Fault)

페이지 부재(Page Fault)란?

페이지 부재란 CPU가 접근하려는 페이지가 메모리에 없는 상황이다. 즉, 페이지 테이블의 valid-invalid bit가 0인 상태를 말한다.

페이지 부재 발생 시 페이지를 디스크에서 읽어와야 하는데, 이 과정에서 막대한 오버헤드가 발생한다. 따라서, 요구 페이징 기법에서 페이지 부재 발생률은 성능에 큰 영향을 끼치게 된다.

 

페이지 부재 시 동작 과정

1. 특정 페이지를 실행하기 위해 페이지 테이블을 참조하여 메모리에 올라와있는지 여부를 확인한다.

2. 페이지가 메모리에 올라와있지 않을 경우 MMU(Memory Management Unit)가 인터럽트를 발생시킨다.

3 & 4. 운영체제는 해당 프로세스를 wait 상태로 만들고 요구된 페이지를 하드 디스크에서 찾아 메모리에 적재시킨다.

5. 페이지 테이블에서 해당 페이지의 valid-invalid bit를 유효 값으로 설정한다.

6. 해당 프로세스를 다시 ready → running 하여 작업을 진행한다.

---

페이지 교체(Page Replacement)

페이지 교체(Page Replacement)란?

페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 하는데, 물리적 메모리에 빈 프레임이 존재하지 않을 수도 있다. 이러한 경우, 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하여 새로운 페이지를 메모리에 올려야 한다. 이러한 과정을 페이지 교체라고 하며, page-out 된 페이지를 희생양 페이지(victim page)라고 한다.

 

희생양 페이지(Victim Page)

희생양 페이지는 보통 메모리에 올라가 있는 페이지 중 CPU에 의해 수정되지 않은 페이지를 고르는 것이 효율적이다. 수정되지 않은 페이즈는 page-out이 될 때 backing store에 쓰기 연산을 할 필요가 없기 때문이다.

해당 페이지가 수정되었는지 판단하기 위해, 페이지 테이블에 modified bit(dirty bit)를 추가하여 수정 여부를 검사한다. 해당 페이지가 수정되었다면 이 비트를 1로 설정하고, 수정되지 않았으면 0으로 설정한다. 이를 이용해서 최대한 수정되지 않은 페이지를 희생양 페이지로 선택한다.

 

위 그림에서 수정되지 않은 페이지는 0, 2, 3번으로 총 3개의 페이지가 존재하는데 이 중에서 하나의 페이지를 선택해서 교체해야 한다.

페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 교체 알고리즘이라고 하며, 페이지 부재율을 최소화하는 것이 페이지 교체 알고리즘의 최종 목표이다.

---

페이지 교체 알고리즘(Page Replacement Algorithm)

페이지 교체 알고리즘 (Page Replacement Algorithm)의 종류

1. Optimal

 

ㆍ 빌레디의 최적 알고리즘으로 MIN, OPT 등으로 불린다.

ㆍ 가장 이상적인 페이지 교체 알고리즘이다.

ㆍ 프로세스가 앞으로 사용할 페이지를 미리 알아야 하므로 현실 세계에서는 사용이 어려운 알고리즘이다.

ㆍ 어떠한 알고리즘 보다도 가장 적은 페이지 부재율을 보장하기 때문에 다른 알고리즘에 성능에 대한 상한성을 제공한다.

 

2. FIFO(First in First out)

 

ㆍ 메모리에 가장 먼저 올라온 페이지를 교체하는 방식의 알고리즘이다.

ㆍ 들어온 시간을 저장하거나 올라온 순서를 큐에 저장하고, 페이지 부재 시 메모리에 가장 먼저 올라온 페이지를 먼저 교체하는 방식이다.

 

 

ㆍ 보통 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소할 것이라 생각할 수 있지만, 물리적인 공간이 늘어났음에도 불구하고 성능이 더 나빠지는 경우가 발생할 수 있다. 이러한 상황을 FIFO의 이상 현상, Belady's Anomaly (FIFO anomaly)라고 한다.

 

3. LRU(Least Recently Used)

 

ㆍ FIFO의 이상 현상이 발생하지 않는다.

ㆍ 메모리 페이지의 참조 성향 중 시간 지역성을 고려한 알고리즘이다. (시간 지역성 : 최근에 참조된 페이지가 가장 가까운 미래에 다시 참조될 가능성이 높음)

ㆍ 사용된 시간을 알 수 있는 부분을 저장하여 가장 오랫동안 참조되지 않은 페이지를 제거하는 방식이다.

ㆍ 프로세스가 주기억장치에 접근할 때마다 참조된 페이지의 시간을 기록해야 하기 때문에 막대한 오버헤드가 발생할 수 있다.

 

4. LFU(Least Frequently Used)

 

ㆍ 물리적 메모리 내에 존재하는 페이지 중 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재하는 방식이다.

ㆍ 만약 최저 참조 횟수를 가진 페이지가 여러 개라면 그들 중 상대적으로 더 오래전에 참조된 페이지를 쫓아내도록 구현하는 것이 효율적이다.

ㆍ 직접 참조된 시점만을 반영한 LRU와는 다르게 LFU는 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다.

ㆍ 가장 최근에 불러온 페이지가 교체될 수 있으며, 이에 따른 오버헤드가 발생할 수 있다.

 

5. MFU(Most Frequently Used)

 

ㆍ LFU 알고리즘과는 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.

ㆍ 가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라는 가정에 의한 방식이다.

---

출처

ㆍ https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

ㆍ https://steady-coding.tistory.com/526