# 질의 응답 상황
[면접관]
지원자님 자료구조에서 페이지교체 알고리즘에 대해서 간략하게 설명해주세요. |
[막개발자]
페이지 부재가 발생하였을 때 OS는 해당 페이지를 디스크에서 메모리로 올리려고 합니다. 그런데 메모리에 공간이 없을 경우, 메모리의 페이지 일부를 내보내야 되는데 이때 사용하는 알고리즘을 페이지 교체 알고리즘이라고 합니다. 가장 대표적인 알고리즘 3가지를 설명드리겠습니다.
|
# 상세 설명
페이지 교체 알고리즘 (Page Replacement Algorithm)
페이지 교체 알고리즘은 운영 체제에서 가상 메모리를 사용할 때, 물리적인 메모리에 있는 페이지들이 부족해졌을 때 어떤 페이지를 교체할지 결정하는 방법입니다. 물리 메모리가 한정되어 있기 때문에, 프로세스가 참조하는 페이지들이 메모리 공간을 초과하면 운영 체제는 **페이지 폴트(Page Fault)**가 발생할 때마다 교체할 페이지를 선택해야 합니다. 이때 선택하는 알고리즘을 페이지 교체 알고리즘이라고 합니다.
가상 메모리 시스템에서는 프로그램이 물리 메모리보다 더 많은 메모리를 사용하는 것처럼 보이도록 합니다. 운영 체제는 디스크와 물리 메모리 간에 데이터를 교환하여 이를 처리합니다. 페이지 교체 알고리즘은 페이지 폴트를 처리하는 중요한 역할을 하며, 페이지를 디스크와 메모리 간에 교환할 때 시스템의 성능에 큰 영향을 미칩니다.
페이지 교체 알고리즘의 목적
- 효율성: 페이지 교체가 자주 발생하면 성능이 저하됩니다. 따라서 교체할 페이지를 선택할 때, 최소한의 교체가 발생하도록 하는 것이 중요합니다.
- 최소화: 가능한 한 적은 페이지 폴트를 발생시키도록 교체할 페이지를 선택합니다.
주요 페이지 교체 알고리즘
1. 최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm)
- 작동 원리: 현재 메모리에 있는 페이지들 중에서 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다.
- 단점: 미래를 예측할 수 없기 때문에 실제로 구현할 수 없습니다.
최적 알고리즘은 페이지가 앞으로 가장 오래 사용되지 않을 페이지를 교체하는 알고리즘입니다. 이 알고리즘은 이론적으로 가장 효율적이며 페이지 폴트를 최소화할 수 있지만, 실제로는 미래의 참조를 예측할 수 없기 때문에 실제 시스템에서는 사용되지 않습니다. 다만 이 알고리즘은 다른 알고리즘들의 성능을 비교할 때 기준으로 사용됩니다.
2. 가장 오래된 페이지 교체 (Least Recently Used, LRU)
- 작동 원리: 각 페이지의 참조 시간을 기록하고, 가장 오래 전에 참조된 페이지를 교체합니다.
- 단점: 각 페이지의 참조 시간을 계속 추적해야 하므로 오버헤드가 발생할 수 있습니다.
LRU (Least Recently Used) 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식입니다. 이 알고리즘은 페이지가 참조된 시간을 추적하고, 가장 오래전에 사용된 페이지를 교체합니다.
3. 첫 번째로 들어온 페이지 교체 (First-In-First-Out, FIFO)
- 작동 원리: 페이지가 메모리에 들어온 순서대로, 가장 먼저 들어온 페이지부터 교체합니다.
- 단점: 최신 참조에 대한 정보를 무시하고, 처음에 들어온 페이지를 교체하기 때문에 비효율적일 수 있습니다.
FIFO (First-In-First-Out) 알고리즘은 가장 먼저 들어온 페이지를 가장 먼저 교체하는 방식입니다. 이 알고리즘은 구현이 간단하지만, 최적화된 알고리즘은 아닙니다.
4. 리페이스 카운트 페이지 교체 (Least Frequently Used, LFU)
- 작동 원리: 각 페이지가 참조된 횟수를 추적하고, 참조 횟수가 가장 적은 페이지를 교체합니다.
- 단점: 참조 횟수를 추적하는 데 오버헤드가 발생하고, 주기적으로 참조 패턴이 변화하는 경우 비효율적일 수 있습니다.
LFU (Least Frequently Used) 알고리즘은 사용 빈도가 가장 적은 페이지를 교체하는 방식입니다. 즉, 가장 적게 참조된 페이지를 교체합니다.
5. 나쁜 페이지 교체 (Clock Algorithm)
- 작동 원리: 원형 큐를 사용하여 각 페이지의 참조 비트를 관리하며, 교체할 때 비트가 0인 페이지를 선택합니다.
**시계 알고리즘(Clock Algorithm)**은 LRU 알고리즘의 변형으로, 원형 큐를 사용하여 페이지 교체를 효율적으로 수행하는 방식입니다. 각 페이지에 대해 참조 비트를 두고, 페이지가 참조되면 비트가 설정됩니다. 페이지를 교체할 때 참조 비트가 0인 페이지를 교체합니다.
결론
페이지 교체 알고리즘은 가상 메모리를 효율적으로 관리하고, 페이지 폴트를 최소화하는 중요한 역할을 합니다. 각 알고리즘은 장단점이 있으며, 시스템의 요구 사항과 페이지 참조 패턴에 따라 적합한 알고리즘을 선택하는 것이 중요합니다. 이 중 LRU, FIFO, LFU는 실제 운영 체제에서 많이 사용되는 알고리즘이며, Optimal은 이론적인 최적 알고리즘으로 주로 비교 대상이 됩니다.
'[이직 면접] 질의 응답' 카테고리의 다른 글
[Web 개발 기본] Proxy Pattern에 대해서 설명 하세요. (0) | 2020.12.06 |
---|---|
[Java] 객체와 class에 대해서 설명하세요. (0) | 2020.12.06 |
[Java] 탐색 알고리즘에 대해서 설명하세요. (0) | 2020.12.06 |
[Java] primitive type, reference type에 대해서 설명하세요 (0) | 2020.12.04 |
[Java] String / Stringbuffer / StringBuilder에 대해서 설명하세요. (0) | 2020.12.04 |