👀 해당 주제 질문 리스트 미리보기
Q1. 페이지 교체 알고리즘에 대해 설명해주세요.
Q2. 페이지 교체 알고리즘은 어떤 것이 있을까요?
1. 페이지 교체 개념
페이징 시스템에서, 필요한 페이지를 물리 메모리에 적재해야 할 때 물리 메모리가 가득 차 있는 상황이 발생할 수 있습니다. 이 경우, 새로운 페이지를 적재하기 위해 기존에 있던 특정 페이지를 메모리에서 내보내야 하는데, 이를 페이지 교체라고 합니다.
2. 페이지 교체 알고리즘이 필요한 이유
필요한 페이지를 물리 메모리에 적재해야 할 때 물리 메모리가 가득 차 있다면, 특정 페이지를 내보내야 합니다. 이때, 어떤 페이지를 내보낼지 결정하는 과정에서 page fault(페이지 부재)를 최소화하는 것이 중요합니다.
페이지 교체 알고리즘은 이러한 과정을 효율적으로 수행하기 위해 만들어졌습니다.
3. 페이지 교체 알고리즘 종류
1. FIFO (First-In First-Out)
- 작동 방식: 가장 간단하고 직관적인 페이지 교체 방법으로, 먼저 물리 메모리에 들어온 순서대로 페이지를 교체합니다.
-
장점: 이해하기 쉽고 구현이 간단합니다.
-
단점:
단순히 먼저 들어온 페이지가 더 이상 사용되지 않는다는 것을 의미하지 않기 때문에, 활발하게 사용되는 페이지를 교체하여 페이지 폴트(page fault)를 증가시킬 수 있습니다.
FIFO 페이지 교체 알고리즘에서는 Belady의 모순(Belady's anomaly)이 발생할 수 있습니다. 일반적으로 페이지 프레임 수를 늘리면 메모리에 적재할 수 있는 페이지 수가 늘어나 페이지 폴트 발생 확률이 감소해야 합니다. 그러나 FIFO에서는 오래된 페이지를 교체하기 때문에, 프레임 수를 늘려도 오히려 페이지 폴트가 더 많이 발생할 수 있습니다.
2. OPT (Optimal-최적 알고리즘)
- 작동 방식: 가장 이상적인 페이지 교체 알고리즘으로, 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다.
-
장점: 가장 낮은 페이지 폴트 비율을 보일 수 있습니다.
-
단점:
모든 프로세스의 메모리 참조 패턴을 미리 파악해야 하기 때문에, 실제 구현이 매우 어렵고 사실상 불가능합니다.
3. LRU (Least Recently Used)
- 작동 방식: 가장 오랫동안 사용되지 않은 페이지를 교체합니다.
-
장점: 참조 지역성(locality of reference)을 고려하여 페이지 교체를 수행하므로 페이지 폴트 비율이 낮아질 수 있습니다.
-
단점:
페이지 사용 여부를 추적하기 위해 추가적인 데이터 구조와 연산이 필요하여, 알고리즘 구현이 복잡해지고 메모리 사용량이 증가할 수 있습니다.
결론: 가장 많이 사용되는 페이지 교체 알고리즘으로, 간단하면서도 효율적입니다.
4. LFU (Least Frequently Used)
- 작동 방식: 참조 횟수가 가장 적은 페이지를 교체합니다.
-
장점:
적게 사용된 페이지를 우선적으로 제거하므로, 페이지 폴트가 자주 발생하는 페이지를 메모리에 유지할 수 있습니다. -
단점:
어떤 프로세스가 특정 페이지를 집중적으로 사용하다가 다른 기능을 사용하게 되면, 이전에 많이 사용되었지만 현재는 사용되지 않는 페이지가 계속 메모리에 남아 있을 수 있습니다. 이는 '활발하게 사용되는 페이지는 참조 횟수가 많다'는 가정에 어긋나게 되어 의도한 성능 개선이 이루어지지 않을 수 있습니다.
4. 종합
각 페이지 교체 알고리즘은 특정 상황에서 장단점을 가지고 있으며, 사용 환경과 요구사항에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.
FIFO는 단순하지만 비효율적일 수 있고, OPT은 이론적으로 이상적이지만 실제 구현이 불가능합니다. LRU는 효율적이지만 구현이 복잡하고, LFU는 참조 패턴에 따라 예상치 못한 결과를 초래할 수 있습니다.
5. 페이지 교체 알고리즘 관련 기술면접 질문
Q1. 페이지 교체 알고리즘에 대해 설명해주세요.
페이지 교체 알고리즘은 물리 메모리가 가득 찼을 때, 새로운 페이지를 로드하기 위해 어떤 페이지를
내보낼지 결정하는 방법입니다. 이 알고리즘은 페이지 폴트를 최소화하여 시스템 성능을 최적화합니다.
Q2. 페이지 교체 알고리즘은 어떤 것이 있을까요?
FIFO - 가장 먼저 들어온 페이지를 먼저 내보냅니다.
LRU - 가장 오랫동안 사용되지 않은 페이지를 내보냅니다.
Optimal - 앞으로 가장 오랫동안 사용되지 않을 페이지를 내보냅니다.
LFU - 사용 빈도가 가장 낮은 페이지를 내보냅니다.
Clock - FIFO 방식을 사용하되, 한 번의 기회를 더 주어 최근에 사용된 페이지를 내보내지 않도록 합니다.
ref.
[운영체제] 페이지 교체 알고리즘 (Page Replacement Algorithm)
https://github.com/Seongwon97/tech-interview/blob/main/Q&A/OS_Q&A.md
https://rob-coding.tistory.com/37
https://parkground.tistory.com/790
https://code-lab1.tistory.com/60
