[CS : OS] 페이지 교체 알고리즘

1. 가상 메모리

물리 메모리가 가지는 크기의 한계를 극복하기 위해 나온 기술이 가상 메모리이다. 각 프로세스에서 현재 실행에 필요한 부분만 메모리에 적재하여 효율을 극대화하는데 이때 현재 필요한 부분(보통은 페이지)만 올리는 것을 Demading Paging(요구 페이징)이라고 함.

 

 

두 프로세스 P1, P2는 현재 필요한 페이지만 메모리에 할당한 상태인데, 지금은 P1이 수행 중이다. 기존의 페이지 테이블과 다른 점은 Valid bit를 두어서 현재 메모리에 적재된 부분은 1 , 아닌 부분은 0으로 표시한다.
그러나 CPU가 지금 P1의 3번째 페이지에 접근하려고 하는데 Valid bit 가 0이면 인터럽트가 발생하는데 이런 현상을 ‘페이지 부재’ Page Fault 라고 부른다.

 

다음과 같은 방식으로 페이지 부재를 처리한다. 즉 페이지 부재가 발생하면 프로세스로 가서 할당되어야 할 페이지를 찾아서 할당해줘야 한다는 의미이다.
이때 페이지 부재 상황에서 페이지 할당하는 방식이 2가지 있다.

 

1) Pure Demading Paging

프로세스가 맨 처음 실행될 때 어떤 페이지가 필요한지 모르므로 아무 페이지도 할당 안한다. 그러면 시작하자마자 페이지 부재가 발생하고 그때부터 필요한 페이지를 뽑아가는 형식. 메모리를 쓸데없는 건 아예 안 올리므로 최대한의 효율로 쓰지만 속도는 당연히 느리다.

2) Preparing
위의 방식과 반대되는 개념으로 미리 필요할 것 같은 페이지를 미리 올려두는 것이다. 페이지 부재가 발생할 확률을 줄이므로 속도는 빠르지만, 이미 올라간 페이지가 쓰이지 않는다면 메모리가 낭비되는 단점이 있다.

현실적으로 페이지 부재는 얼마나 발생하는가? 지역성의 원리에 의해 페이지 부재 확률은 실제로 굉장히 낮다. 메모리 접근은 시간적, 공간적 지역성을 가진다.

그럼에도 페이지 부재를 더욱 효율적으로 관리하기 위해 페이지 교체 (Page Replacement) 기법을 사용한다.

---

2. 페이지 교체 (Page Replacement)

위에서 말한 요구 페이징은 그때 그떄 필요한 페이지를 가져온다. 그러나 프로그램들이 계속 실행되면 제아무리 가상 메모리를 쓴다 하더라도 메모리가 페이지들로 가득 차게 된다.
이런 상황에서 메모리에 올라가 있는 페이지를 다시 내리고 새로운 패이지를 올리는 과정을 페이지 교체라고 한다.

• Victim Page(희생양 페이지)
  그럼 어떤 페이지를 내릴 것인가? 기본적으로 CPU에 수정되지 않은 페이지를 고르는 것이 좋다. 수정된 페이지는 다시 내려갈 때 수정된 부분을 Write 연산을 해야 하기 때문이다. 이를 위해서 페이지가 수정되었는지 안되었는지를 판단할 수 있는 Modified bit(=dirty bit)를 추가하여 수정된 페이지는 1 , 안된 페이지는 0으로 한다. 이를 이용해서 희생 페이지는 최대한 수정 안된 페이지를 우선적으로 한다.
  하지만 이러한 방식 말고도 여러가지 방식들이 존재한다.

---

3. 페이지 교체 알고리즘

1) FIFO(First In First Out)

간단하게 먼저 메모리에 적재된 페이지가 먼저 나가는 알고리즘. 보통 처음에 초기화하는 코드는 프로세스 실행 때만 초기화하고 안 쓰이므로 이런 경우에 적절한 방법이다. FIFO는 프레임의 수가 적다면 금방 프레임이 꽉 차서 계속 가장 오래된 놈을 내려야 되므로 페이지 부재가 일어난다. 그러나 프레임의 수가 많을수록 페이지 부재가 적어지며 이를 Belady’s Anomaly라고 부른다.

2) OPT(Optimal)

최적화 알고리즘이란 의미로 가장 사용 안 할 것 같은 페이지를 가장 우선적으로 내려보내는 알고리즘이다. FIFO에 비해 페이지 부재가 감소하긴 하지만 앞으로도 사용 안될 것인지에 대한 예측이 보장되지 않으므로 실제로 많이 쓰이지 않는다.

3) LRU(Least Recently Used)

최근에 사용하지 않은 페이지를 가장 먼저 내리는 알고리즘이다. 과거에 많이 안 쓰였다면 미래에도 많이 안 쓰일 것이라는 전제로 쓰인다. 실제로 그런 경우가 많아서 실 사용되는 알고리즘이다.

4) LFU(Least Frequently Used)

사용 빈도가 가장 적은 페이지를 교체해준다. LRU와 비슷한 것 같지만 전혀 다른 방식이다. LRU는 시간적으로 가장 오래된 페이지를 교체한다면 LFU는 사용 횟수 자체가 가장 적은 페이지를 교체해준다.

1) Global 교체 방식

메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

2) Local 교체 방식

메모리 상의 자기 프로세스 페이지에서만 교체하는 방식