CS 공부 & 면접 맛보기 0x12 [운영체제] : 페이지 교체 알고리즘의 종류 설명

질문
페이지 교체 알고리즘이란 무엇인가요?

면접 답변

페이지 교체 알고리즘(Page Replacement Algorithm)은 메모리 부족 상황에서 페이지를 메모리에 적재할 때, 기존 페이지 중 어떤 것을 제거할지 결정하는 알고리즘입니다.

---

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

1. FIFO (First-In-First-Out)

• 가장 먼저 들어온 페이지를 먼저 제거하는 방식.
• 장점: 구현이 단순하고 직관적.
• 단점: 오래된 페이지가 꼭 불필요한 페이지라는 보장이 없음.

2. OPT (Optimal Page Replacement)

• 앞으로 가장 오래 사용되지 않을 페이지를 제거하는 방식.
• 장점: 페이지 부재(Fault)를 최소화함.
• 단점: 미래의 메모리 접근을 예측할 수 없으므로 이론적 알고리즘에 불과함.

3. LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지를 제거하는 방식.
• 장점: 현실적으로 효율적이고 많이 사용됨.
• 단점: 최근 사용 이력을 유지하는데 추가 메모리가 필요함.

4. LFU (Least Frequently Used)

• 가장 적게 사용된 페이지를 제거하는 방식.
• 장점: 사용 빈도가 적은 페이지를 효과적으로 제거 가능.
• 단점: 최근에 추가된 페이지가 낮은 빈도를 가질 수 있어 비효율적일 수 있음.

5. Clock (Second Chance)

• FIFO 변형 알고리즘으로, 페이지에 참조 비트를 두어 한 번의 기회를 추가로 부여함.
• 장점: FIFO보다 개선된 성능.
• 단점: 참조 비트 관리를 위한 추가 비용 발생.

---

결론

• 페이지 교체 알고리즘은 메모리 관리의 핵심 요소입니다.
• 사용 사례와 메모리 접근 패턴에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.