페이지 교체 방법

💻 먼저 운영체제는 주기억장치보다 더 큰 용량을 담기위해서 프로그램의 일부만 주기억장치에 적재해서 사용하는데 이를 가상메모리 기법이라한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어떤 것으로 교체할지 정하는 방법이다. 페이지의 부재가 발생했을시 시행하는데 쉽게 말하면 페이지를 적재할만한 빈 페이지가 없을 때를 말한다.

📃 페이지란?

페이징 기법에서 일정한 크기를 가진 블록을 페이지(page)라고 한다.
페이징 기법은 컴퓨터가 RAM에서 사용하기 위해 2차 기억 장치로부터 데이터를 저장하고 검색하는 메모리 관리 기법이다. 이때 가상기억장치를 모두 같은 크기의 블록으로 만들어 운영한다고 생각하면 된다. 이때 비교되는 것이 프레임이라는 용어인데 간단하게 정리해보자.

• 프레임(Frame): 물리 메모리를 일정한 크기로 나눈 블록
• 페이지(page): 가상 메모리를 일정한 크기로 나눈 블록

페이지 교체 알고리즘의 종류 👾

• FIFO(First In First Out)

• OPT (다른말로 Belady의 최적 알고리즘이라 함)

• LRU (Least Recently Used) 최근에 사용되지 않은 페이지 교체

• LFU (Least Frequently Used) 참조 횟수가 가장 자주일어난 것 교체

• MFU (Most Frequently used) 참조 횟수가 가장 많은 페이지 교체

• NUR (Not Used Recently) 최근에 사용하지 않은 페이지 교체

FIFO(First In First Out)

가장 간단한 알고리즘이다.
메모리에 올라온지 가장 오래된 페이지를 교체한다. 이것을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록 OR 페이지가 올라온 순서를 큐(Queue)에 저장하는 방식 등을 사용할 수 있다.

이미지 출처

장점은 이해가 쉽고 간편하다는 것. 하지만 성능은 항상 좋다고 할 수는 없다.

이 부분의 페이지 7을 봐보자. 한동안 쓰이지 않았기 때문에 FIFO방식이 문제를 일으키지 않았지만.

페이지 2의 경우를 보면 전체 표를 봤을때 직전 페이지 부재(페이지 4번)로 인해서 페이지 4와 2가 교체되고 난후 또 페이지 2를 사용하기 위해 교체했던 것을 다시 불러왔다. 이렇게 활발하게 사용중인 페이지를 계속해서 교체하게 된다면 페이지 부재율이 높아지고 속도도 떨어진다. 하지만 올바르게 동작은 한다. 즉, 효율이 좋지 않다는 것이지 잘못된 실행을 야기하지는 않는다는 것이다.

그럼 FIFO으로 인한 심각한 문제는 뭐가 있을까? 결과부터 말하면 이를 Belady의 모순이라고 한다. 이 개념은 프로세스에게 프레일을 더 주었는데 오히려 페이지 부재율은 더 증가하는 현상을 말한다. 우리가 보통은 프로세스에게 더 많은 프레임을 할당하면 성능이 좋아질 것으로 생각하는데 이것이 항상 옳은 방법은 아닌 것이 밝혀졌다.

위에 그래프는 페이지 부재율 대 할당된 프레임 수간의 그래프다. 해석해보면 4개의 프레임을 할당했을때 페이지 부재율이 10번으로 일어났지만 프레임을 3개로 할당하면 부재율이 9번 일어나는 것으로 보인다. -> 말이 안된다. 이것이 모순이다.

이 모순이 가져온 결과가 아래에 설명할 OPT 다.

OPT(최적 페이지 교체)

이것은 모든 알고리즘보다 낮은 페이지 부재율을 보여주고 위에서 말한 Belady의 모순을 보여주지 않는다. 이 알고리즘을 요약하면 다음과 같다.

앞으로 가장 오랫 동안 사용되지 않을 페이지를 찾아 교체해라.

이 알고리즘은 할당된 프레임 수가 고정된 경우 가장 낮은 페이지 부재율을 보장한다.
이론 적으로는 완벽하지만 아쉽게도 구현할 수는 없다.

왜???

이 방식은 프로세스가 앞으로 메모리를 어떻게 참조할 것인지를 미리 알아야 하기 때문. 보통은 그래서 연구 목적으로 사용한다. 그럼에도 불구하도 작동 방법을 소개하자면 다음과 같다.

그림을 보면 페이지 7의 경우 18번째에 다시 쓰이는 것을 미리 알고 있기 때문에 페이지 2와 7을 교체한다. (이게 말이 안된다)

페이지 1에 경우 3이랑 바꿨는데 14번째 참조로 가장 뒤에 쓰일 것을 미리 알고 있기 때문에 바꿨다.

이것이 불가능 하므로 우리는 LRU 페이지 교체를 이용한다.

LRU 페이지 교체

최적(OPT)알고리즘이 불가능하다면, 최적 알고리즘의 근사 알고리즘은 가능할 것이다. 먼저 FIFO와 OPT 알고리즘의 결정적인 차이점은 FIFO 알고리즘이 페이지가 메모리로 들어온 시간을 이용하지만 OPT는 페이지가 사용될 시간을 이용한다.

LRU 기법은 최근의 과거를 가까운 미래의 근사치로 본다면 가장 오랜기간동안 사용되지 않은 페이를 교체하는 방법이다. 쉽게 풀어쓰자면. 가장 오래 사용되지 않은 페이지를 교체하는데 그 방법은 OPT처럼 미리 아는 것이 불가능하니까 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측해서 교체하는 것이다.

LRU 알고리즘은 각 페이지 마다 마지막 사용 시간을 유지한다. 그리고 페이지 교체시에 LRU는 가장 오랫동안 사용되지 않은 페이지를 선택한다.

9번째에 있는 페이지 2를 봤을때, 직전의 페이지 부재에서(페이지 4) 2,0,3중 가장 오랫동안 사용 안한 것을 교체함.
11번째에 있는 페이지 0은 가장 오랫동안 사용 안한 페이지 4를 0과 교체함

지금까지 효율성으로만 봤을때
OPT (구현 불가능) > LRU > FIFO 이다.

이 알고리즘은 페이지 교체를 할때 자주 사용되면서 좋은 알고리즘으로 인정받고 있다. 문제는 어떻게 구현할 것인가인데 이 알고리즘은 하드웨어의 지원이 필요하다. 무슨 말이냐면 프레임들을 최근 사용된 시간 순서대로 파악할 수 있어야 하는데 이때 두 가지 방법으로 가능하다.

• 계수기
  가장 간단한 방법이며, 각 페이지 항목마다 사용 시간을 넣고 CPU에 논리적인 시계나 계수기를 달아놓는다. 그러면 메모리에 접근시마다 시간이 증가한다. 이 기록된 시간은 페이지의 사용 시간 필드에 레지스터 내용이 복사가 되어 마지막 참조 시간을 유지할 수 있다. 이때 시간 값이 가장 작은 것이 교체된다.

• 스택
  또 다른 방법은 스택인데 페이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되서 스택 꼭대기에 놓인다. 이런 방식으로 반복하면 스택의 Top 부분은 항상 가장 최근에 사용된 페이지고 바닥 부분은 가장 오랫동안 사용 하지 않은 페이지일 것이다.

이 LRU 알고리즘은 위에서 말한 Belady의 모순을 야기하지 않는다. 페이지 교체 알고리즘들 중에는 이 모순 현상을 나타내지 않는 것들이 있는데 이런 알고리즘 들을 스택 알고리즘이라고 한다.

LFU 알고리즘 그리고 MFU 알고리즘.

이 둘은 크게 보면 계수-기반 페이지 교체 알고리즘의 범주에 들어간다. 페이지 교체를 하기 위해 사용되는 알고리즘들이 존재하는데 이 둘은 페이지를 참조할 때마다 계수를 하는 기법이다.

• LFU :
  이것은 참조횟수가 가장 작은 페이지를 교체하는것이다. 이런 이유는 활발하게 사용하는 페이지는 큰 참조 횟수 값을 갖게 될 것이라는 점! 어찌보면 당연한 것 같다.

• MFU :
  이것은 가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고 앞으로 사용될 것이라는 판단에 근거한 것. 쉽게 말해 LFU와는 반대로 참조 횟수가 가장 많은 페이지를 교체한다는 뜻이다.

  이 두 알고리즘은 실제 사용에 잘 쓰이진 않는다. 그 이유는

• 구현에 상당한 비용

• LRU만큼 제대로 유사하게 구현도 못함.

---

참고 문헌.

Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 공저 / 조유근, 박민규, 고건 공역 | 홍릉과학출판사 | 2019년 01월 03일

이책이다.