[운영체제] 페이지 교체 알고리즘이란?

• 운영체제에서 프로세스가 사용하는 **가상 메모리(Virtual Memory)**는 실제 물리 메모리보다 큰 주소 공간을 가짐.
• 하지만 실제 물리 메모리는 한정되어 있기 때문에, 페이지 부재(Page Fault)가 발생할 때마다 메모리에서 어떤 페이지를 교체할지 결정하는 페이지 교체 알고리즘이 필요함.
• 페이지 교체 알고리즘은 **페이지 부재율(Page Fault Rate)**을 최소화하는 것이 핵심 목표!!
• 메모리 참조열(reference string)을 사용하여 페이지 부재 횟수를 측정하는 방법으로 알고리즘들을 평가

---

1. FIFO (First-In First-Out)

1) 개념

• 가장 먼저 메모리에 들어온 페이지를 가장 먼저 내보내는 방식
• 큐(Queue) 형태로 페이지를 관리

2) 작동 방식

1. 메모리에 공간이 있을 때는 그대로 페이지를 적재
2. 공간이 없을 경우 가장 오래전에 들어온 페이지를 제거

3) 예시

• 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 프레임 수: 3
• 결과: 9번의 페이지 부재

4) 특징

• Belady의 모순(Belady's Anomaly): 프레임 수가 늘어나도 페이지 부재가 더 많아질 수 있음

---

2. OPT (Optimal Algorithm)

1) 개념

• 미래에 가장 오랫동안 사용되지 않을 페이지를 제거
• 가장 이상적인 알고리즘이지만 미래 참조 정보를 알아야 하므로 구현은 불가능

2) 작동 방식

1. 페이지 부재 발생 시, 앞으로 가장 오랫동안 참조되지 않을 페이지를 교체

3) 예시

• 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 프레임 수: 4
• 결과: 6번의 페이지 부재

4) 특징

• 실제로는 구현되지 않지만 다른 알고리즘의 성능 비교 기준으로 사용됨

---

3. LRU (Least Recently Used)

 

 

1) 개념

• 가장 오랫동안 사용되지 않은 페이지를 교체
• 실제 사용 빈도를 고려하는 방식

2) 구현 방법

1. 카운터 방식: 각 페이지에 시간값 저장
2. 스택 방식: 페이지를 스택으로 관리하여 최근 참조된 순서 유지

3) 예시

• 참조열: 1, 2, 1, 0, 4, 1, 3
• 프레임 수: 3
• 최종 메모리 상태: 1, 4, 3
• 결과: 8번의 페이지 부재

4) 특징

• 실제 시스템에서 널리 사용됨
• 최근 사용된 페이지는 앞으로도 사용할 가능성이 높다는 가정

---

4. Second Chance (2차 기회)

1) 개념

• FIFO에 **참조 비트(reference bit)**를 추가한 LRU 근사 알고리즘
• 참조 비트가 1이면 2차 기회를 주고, 0이면 바로 교체

2) 작동 방식

1. 순환 큐 형태로 페이지를 관리
2. 포인터가 교체 대상 페이지를 가리킴
3. 참조 비트가 1이면 0으로 초기화하고 다음으로 이동
4. 0인 페이지를 만나면 교체

3) 특징

• 구현이 단순하면서도 성능은 LRU에 근접
• 하드웨어 지원 없이도 운영체제 수준에서 구현 가능

---

5. LFU (Least Frequently Used)

1) 개념

• 가장 적게 참조된 페이지를 교체
• 참조 횟수가 적은 페이지는 앞으로도 사용할 확률이 낮다고 가정

2) 작동 방식

• 각 페이지마다 참조 횟수를 기록
• 페이지 부재 시, 카운터 값이 가장 작은 페이지 제거

3) 문제점

• 오래전에 잠깐 자주 참조되고 이후 사용되지 않는 페이지가 계속 남아 있을 수 있음

---

6. MFU (Most Frequently Used)

1) 개념

• 가장 많이 참조된 페이지를 제거
• 자주 참조된 페이지는 이미 역할을 다했을 가능성이 크다고 가정

2) 작동 방식

• LFU와 반대로, 카운터 값이 가장 큰 페이지를 교체

3) 문제점

• 기본 가정이 항상 성립하지 않으며, 대부분의 경우 LFU보다 효율이 낮음

---

7. 전역 vs 지역 페이지 교체

1) 전역 교체 (Global Replacement)

• 모든 프레임을 대상으로 교체
• 시스템 전체에서 가장 적절한 페이지를 제거할 수 있음
• 하지만 한 프로세스가 다른 프로세스의 프레임을 침범할 수 있어 예측 어려움

2) 지역 교체 (Local Replacement)

• 자신에게 할당된 프레임 내에서만 페이지를 교체
• 각 프로세스의 메모리 안정성을 보장
• 하지만 전체적인 효율성은 낮아질 수 있음

---

8. 마무리

 

알고리즘	핵심 전략	장점	단점
FIFO	가장 먼저 들어온 페이지 제거	구현 간단	Belady’s anomaly 가능
OPT	미래에 가장 늦게 사용될 페이지 제거	이론적으로 최적	실제 구현 불가능
LRU	가장 오래 사용되지 않은 페이지 제거	성능 우수	구현 비용 큼
Second Chance	LRU 근사, 참조 비트 활용	효율적, 구현 쉬움	약간의 부정확성
LFU	참조 횟수가 적은 페이지 제거	사용 빈도 반영	과거 사용 잔재 가능
MFU	참조 횟수가 많은 페이지 제거	빠른 교체 가능	잘못된 가정일 수 있음