PageReplacement.md

페이지 교체 알고리즘

• 가상 메모리는 요구 페이징 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.
• 하지만, 필요한 페이지만 올리더라도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다.
• 메모리가 가득차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고 해당 공간에 현재 필요한 페이지를 in 시켜야 한다. 이때, 어떤 페이지를 out 시킬지 정해야 한다.
• 수정이 되지 않는 페이지를 선택해야 좋다. 만약, 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정해야 하므로 시간이 오래걸린다.
• 이러한 상황에서 적절한 페이지 교체를 위해 페이지 교체 알고리즘이 존재한다.

가상 메모리

• 운영체제는 모든 프로그램에게 같은 크기의 메모리를 할당하지 않고 몇몇 프로그램에게 집중적으로 메모리를 할당한 후, 시간이 흐르면 이들에게서 메모리를 회수하여 다른 프로그램들에게 다시 집중적으로 할당하는 방식을 사용한다.
• CPU를 할당받아 당장 수행해야 할 부분만 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지만 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다. 이를 통해 프로그램이 자기 자신만 메모리를 사용하는 것과 같은 효과를 낸다.
• 가상 메모리는 프로세스마다 각각 0번지부터 시작하는 자기 자신만의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 적재된다. -> 요구 페이징 기법

[요구 페이징]

• 가상 메모리는 요구 페이징 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.
• 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재하며, 한번도 접근되지 않은 페이지는 물리적 메모리에 적재되지 않는다.
• 이를 통해 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는데 들었던 입출력 오버헤드가 감소하며 응답시간이 단축된다.
• 유효, 무효 비트를 두어 각 페이지가 메모리에 존재하는지 표시한다.
  • 유효 : 페이지가 메모리에 적재됨.
  • 무효 : 페이지가 현재 메모리에 없는 경우이거나 그 페이지가 속한 주소 영역을 프로세스가 사용하지 않는 경우
• CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 무효로 세팅되어 있는 경우를 '페이지 부재'가 일어났다고 한다.

[페이지 교체]

• 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
• 이 경우, 메모리에 올라와있는 페이지 중 하나를 디스크로 쫓아내고 메모리에 빈 공간을 확보하는 작업이 필요하다. 이를 페이지 교체라고 한다.
• 페이지 교체를 할 때, 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 교체 알고리즘이라 하며, 목표는 페이지 부재율을 최소화하는 것이다.

페이지 부재 발생 -> 새로운 페이지를 할당해야 한다. -> 현재 할당된 페이지(메모리에 올라와있는 페이지) 중 어떤 것을 교체할지 결정하는 방법

페이지 교체 알고리즘

1. FIFO(First in First out) 알고리즘

• 페이지 교체시 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
• 가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법이다.
• 단점
  • 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에 비효율적인 상황이 발생할 수 있다.
  • 빌레이디의 모순 현상이 발생할 수 있다. (페이지 프레임 수가 많으면(메모리 증가) 페이지 부재수가 줄어드는 것이 일반적이지만, 페이지 프레임 수를 증가시켰음에도 페이지 부재가 더 많이 일어나는 현상을 의미한다.)

2. 최적 페이지 교체 알고리즘(Optimal Page Replacement)

• 앞으로 가장 오랫동안 사용하지 않은 페이지를 교체하는 방법
• 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제하에 알고리즘을 운영하므로 현실적으로 구현이 어렵다.
• 페이지 부재율이 가장 낮은 효율적인 알고리즘이다.

3. LRU 알고리즘(Least Recently Used)

• 최근에 사용하지 않은 페이지를 가장 먼저 내보내는 방법
• 최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다.
• OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘 (실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다.)
• OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다.

4. LFU 알고리즘(Least Frequently Used)

• 페이지의 참조 횟수로 교체할 페이지를 결정하는 방법

• 즉, 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 내쫓고 그 자리에 새로 참조될 페이지를 적재한다.

• 단점

  • 시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 구현이 복잡하다.

• LRU, LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야 하므로 알고리즘의 운영에 오버헤드가 발생한다.

5. 클럭 알고리즘(NRU : Not Recently Used, NUR : Not Used Recently)

• 하드웨어적인 지원을 받아 LRU와 LFU 알고리즘에서 발생한 시간적인 오버헤드를 줄인 방식이다.

• LRU를 근사시킨 알고리즘이라고 하며, 오랫동안 사용하지 않은 페이지 중 하나를 교체한다.

• 최근에 참조되지 않은 페이지를 교체 대상으로 선정하는 측면에서 LRU와 비슷하지만 교체되는 페이지의 참조 시점이 가장 오래됐다는 것을 보장하지 못한다.

• 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)를 사용한다.

  • 참조 비트
    • 페이지가 참조될 때, 1로 자동 세팅된다.
    • 페이지가 참조되지 않았을 때는 0이 되며 페이지는 교체한다.
  • 변형 비트
    • 페이지 내용이 변경되었을 때, 1로 지정한다.
    • 페이지 내용이 변경되지 않았을 때는 0으로 지정한다.

• 이 알고리즘은 하드웨어의 자원으로 동작하기 때문에 LRU에 비해 교체 페이지의 선정이 훨씬 빠르게 결정된다.

• 따라서 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.

Reference

• 가상메모리-02-페이지 교체 알고리즘
• 규글님 - 페이지 교체 알고리즘