페이지 교체 알고리즘 공부

개념

페이지 교체 알고리즘(page replacement algorithm)은 가상 메모리 시스템에서 사용되는 핵심 기술로, 메모리에 올라와 있는 페이지 중 어떤 것을 제거하고 새로운 페이지를 불러올지 결정하는 방법.

운영체제가 사용하는 메모리 관리 방식에서 물리 메모리는 한정적이기 때문에, 필요한 페이지가 없을 경우 디스크에서 가져와야 하고, 이때 기존 페이지 중 하나를 제거해야 한다. 이때 어떤 페이지를 제거할지를 정하는 기준이 바로 페이지 교체 알고리즘이다.

 

 

 

728x90

 

 

페이지 교체가 필요한 상황: 페이지 부재(Page Fault)

1. 프로세스가 어떤 페이지에 접근하려고 한다.
2. 그 페이지가 현재 물리 메모리에 없으면 페이지 폴트(page fault) 발생.
3. 새 페이지를 디스크에서 불러와야 함.
4. 물리 메모리가 꽉 찼다면, 기존 페이지 중 하나를 제거해야 함.
5. 이때 어떤 페이지를 제거할지 결정하는 게 페이지 교체 알고리즘.

 

 

 

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

대표적인 페이지 교체 알고리즘은 FIFO, OPT, LRU, LFU, NUR이 존재한다.

FIFO 페이지 교체 알고리즘(First In First Out Page Replacement Algorithm)은 메모리에 적재된 순서대로 페이지를 교체하는 방식이다. 먼저 들어왔다는 이유만으로 교체되기 때문에 비효율적인 경우가 많다. 이런 단점을 보완하기 위해 2차 기회 페이지 교체 알고리즘 같은 변형 알고리즘도 존재한다.

- 요약

• 가장 먼저 들어온 페이지를 가장 먼저 제거
• 구현이 간단하지만, 성능이 안 좋을 수 있음
• Belady’s anomaly 발생 가능 (프레임 수 늘어나도 페이지 폴트 증가 가능)

Page stream: 7 0 1 2 0 3 0 4
Frames: 3
교체 순서: [7,0,1] → 2 replaces 7, 3 replaces 0, ...

 

 

 

OPT 페이지 교체 알고리즘(Optimal Page Replacement Algorithm)은 앞으로 가장 나중에 사용될 페이지를 교체하는 방식이다. 이론적으로는 가장 효율적인 알고리즘이지만, 실제로는 페이지의 미래 사용 여부를 알 수 없기 때문에 실제 운영체제에서는 사용되지 않는다. 대신 다른 알고리즘의 성능을 비교할 때 기준점으로 사용된다.

- 요약

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 제거
• 이론적으로 가장 좋은 성능
• 하지만 미래를 알아야 하므로 실제 시스템에는 사용 불가
• 성능 비교의 기준으로 사용됨 (benchmark)

 

LRU 페이지 교체 알고리즘(Least Recently Used Page Replacement Algorithm)은 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식이다. 최근에 사용된 페이지는 다시 사용할 가능성이 높다는 가정을 기반으로 한다.

- 요약

• 가장 오랫동안 사용되지 않은 페이지를 제거
• 시간 지역성(locality of reference)에 기반
• 구현은 복잡하지만 실제 시스템에서는 가장 널리 사용됨

 

- 구현 방법
접근 시간을 기록하거나
최근 사용 순서를 스택이나 큐로 관리하거나

 

 

 

LFU 페이지 교체 알고리즘(Least Frequently Used Page Replacement Algorithm)은 가장 적게 사용된 페이지를 교체한다. 사용 횟수가 같을 경우에는 다른 기준을 함께 사용하기도 한다.

- 요약

• 사용 빈도가 가장 낮은 페이지를 제거
• 자주 사용되는 페이지는 오래 유지됨
• 단점: 최근엔 안 쓰여도 과거에 많이 쓰인 페이지는 계속 유지됨

 

 

NUR 페이지 교체 알고리즘(Not Used Recently Page Replacement Algorithm)은 최근에 사용된 적이 없는 페이지를 교체하는 알고리즘이다. LRU나 LFU처럼 과거의 사용 정보를 기반으로 하지만, 참조 비트와 수정 비트만을 이용해서 메모리 오버헤드를 줄일 수 있다는 장점이 있다. 페이지에 대한 접근 시간이나 사용 횟수를 별도로 저장하지 않아도 되기 때문에 LRU, LFU보다 구현이 간단하다.

LRU, LFU, NUR, FIFO의 변형 알고리즘은 모두 OPT 알고리즘처럼 미래를 예측할 수는 없지만, 과거의 접근 패턴을 기반으로 어느 정도 예측을 하려는 방식이라서 최적 근접 알고리즘으로 분류된다.

 

 

알고리즘 장점/단점

FIFO	구현 간단	Belady's anomaly, locality 고려 안 됨
LRU	locality 잘 반영	구현 복잡 (타임스탬프/스택 필요)
OPT	최적 성능	실제 구현 불가 (미래 예측 불가)
LFU	사용량 기준	오래된 사용 기록이 유지됨
Clock	성능-구현 절충	정확한 LRU 아님