[자료구조] 페이지교체 알고리즘에 대해서 설명하세요.

# 질의 응답 상황

[면접관]

지원자님 자료구조에서 페이지교체 알고리즘에 대해서 간략하게 설명해주세요.

 

[막개발자] 

페이지 부재가 발생하였을 때 OS는 해당 페이지를 디스크에서 메모리로 올리려고 합니다. 그런데 메모리에 공간이 없을 경우, 메모리의 페이지 일부를 내보내야 되는데 이때 사용하는 알고리즘을 페이지 교체 알고리즘이라고 합니다. 가장 대표적인 알고리즘 3가지를 설명드리겠습니다. FIFO 가장 먼저 메모리에 적재된 페이지를 먼저 내보냅니다. LRU 가장 오랫동안 사용되지 않은 페이지를 내보냅니다. LFU 사용 빈도가 가장 적은 페이지를 내보냅니다.

 

 

# 상세 설명

 

페이지 교체 알고리즘 (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은 이론적인 최적 알고리즘으로 주로 비교 대상이 됩니다.