SECTION 136 페이지 교체 알고리즘

페이지 교체 알고리즘

1. 페이지 교체 알고리즘
   1. 의미: 페이지 교체 알고리즘은 운영체제에서 메모리가 부족할 때, 현재 사용되지 않는 페이지를 교체하여 새로운 페이지를 메모리에 올리는 방법을 결정하는 알고리즘입니다.
   2. 종류: OPT, FIFO, LRU, LFU, NUR, SCR 등
   3. 전체적인 특징: 페이지 교체 알고리즘은 시스템 성능에 큰 영향을 미치며, 페이지 부재를 줄이기 위해 다양한 방식으로 페이지 교체 대상을 선정합니다. 각 알고리즘은 장단점이 있으며, 특정 상황에 따라 성능이 다르게 나타날 수 있습니다.
2. OPT (Optimal Replacement)
   1. 의미: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘입니다.
   2. 특징: 미래의 페이지 참조를 예측할 수 있다면 페이지 부재를 최소화할 수 있는 최적의 알고리즘입니다. 그러나 실제 시스템에서는 미래의 참조를 알 수 없으므로 구현이 어렵습니다.
      • 장점: 이론적으로 가장 적은 페이지 부재를 보장합니다. 최소한의 페이지 교체 횟수를 달성하여 성능이 가장 뛰어납니다.
      • 단점: 미래의 메모리 참조를 예측해야 하므로 실제 시스템에서는 구현이 어렵습니다. 구현이 불가능한 경우가 많아 주로 이론적인 최적화 기준으로 사용됩니다.
   3. 예시: 페이지 프레임이 3개이고 페이지 참조가 1, 2, 3, 4, 1, 2, 5일 때, 4가 들어올 때 앞으로 가장 늦게 사용될 3이 교체됩니다.
3. FIFO (First In First Out)
   1. 의미: 가장 먼저 들어온 페이지를 가장 먼저 교체하는 알고리즘입니다.
   2. 특징: 페이지가 메모리에 들어온 순서대로 교체됩니다. 오래된 페이지가 반드시 필요하지 않다는 가정에서 동작하지만, 페이지의 유용성을 고려하지 않는다는 단점이 있습니다.
      • 장점: 구현이 간단하고 직관적입니다. 순서대로 처리하기 때문에 데이터 구조의 관리가 용이합니다.
      • 단점: 오래된 페이지가 꼭 쓸모없는 것은 아니기 때문에 비효율적일 수 있습니다. 특히 Belady의 모순이 발생하여 페이지 부재가 증가하는 현상이 나타날 수 있습니다.
   3. 예시: 페이지 프레임이 3개이고 페이지 참조가 1, 2, 3, 4일 때, 1이 가장 먼저 들어왔기 때문에 4가 들어올 때 1이 교체됩니다.
4. LRU (Least Recently Used)
   1. 의미: 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.
   2. 특징: 최근에 사용된 페이지는 앞으로도 사용될 가능성이 높다는 가정을 기반으로 하며, 페이지 참조 시간을 기록하여 가장 오래 사용되지 않은 페이지를 선택합니다.
      • 장점: 최근에 사용된 페이지는 앞으로도 사용될 가능성이 높다는 가정을 사용합니다. 현실적인 메모리 접근 패턴을 반영하여 효율적인 성능을 보일 수 있습니다.
      • 단점: 구현이 복잡하며, 참조 시간을 기록해야 하므로 오버헤드가 발생할 수 있습니다. 모든 페이지의 사용 시간을 기록하거나 스택을 사용해야 하므로 비용이 높습니다.
   3. 예시: 페이지 프레임이 3개이고 페이지 참조가 1, 2, 3, 4일 때, 4가 들어올 때 가장 오랫동안 사용되지 않은 1이 교체됩니다.
5. LFU (Least Frequently Used)
   1. 의미: 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘입니다.
   2. 특징: 페이지 참조 횟수를 기반으로 하여 가장 적게 참조된 페이지를 교체하며, 최근에 많이 사용되지 않은 페이지를 선택하는 경향이 있습니다.
      • 장점: 사용 빈도가 낮은 페이지를 제거하여 자주 사용되는 페이지의 유지에 집중합니다. 데이터 접근 패턴이 비교적 일정한 경우 효율적입니다.
      • 단점: 최근에 빈번하게 사용되었지만 갑자기 사용 빈도가 줄어든 페이지를 교체할 수 있습니다. 오래된 참조 횟수가 계속 누적되기 때문에 최근에 자주 사용된 페이지가 교체될 수 있습니다.
   3. 예시: 페이지 프레임이 3개이고 페이지 참조가 1, 2, 1, 3, 4일 때, 4가 들어올 때 사용 빈도가 가장 낮은 2가 교체됩니다.
6. NUR (Not Used Recently)
   1. 의미: 최근에 사용되지 않은 페이지를 교체하는 알고리즘입니다.
   2. 특징: 참조 비트와 변경 비트를 사용하여 페이지가 최근에 사용되었는지를 판단하며, 이를 통해 교체 대상을 선정합니다.
      • 장점: LRU와 유사하지만 구현이 더 간단합니다. 참조 비트를 사용하여 최근의 사용 여부를 판단하기 때문에 LRU보다 효율적으로 구현할 수 있습니다.
      • 단점: 참조 비트만을 기준으로 하기 때문에 정확도가 떨어질 수 있습니다. 단순히 참조 여부만 체크하므로 세밀한 관리가 어렵습니다.
   3. 예시: 페이지 프레임이 3개이고 참조 비트가 설정된 페이지가 1, 2, 3일 때, 4가 들어올 경우 최근 참조되지 않은 페이지를 교체합니다.
7. SCR (Second Chance Replacement)
   1. 의미: FIFO 알고리즘에 페이지에 대해 두 번째 기회를 주는 방식입니다.
   2. 특징: 페이지가 교체될 때 참조 비트를 확인하여 교체 여부를 결정하며, 참조 비트가 설정되어 있으면 페이지는 교체되지 않고 참조 비트를 초기화한 후 다음 페이지로 넘어갑니다.
      • 장점: 페이지가 교체되기 전에 참조 비트를 검사하여 다시 사용할 수 있는 기회를 줍니다. FIFO의 단점을 일부 보완하여 쓸모 있는 페이지를 즉시 교체하지 않도록 합니다.
      • 단점: 구현이 복잡하며, 페이지 회전으로 인한 오버헤드가 발생할 수 있습니다. 페이지를 순환하며 교체 대상을 찾는 과정에서 시간이 소모될 수 있습니다.
   3. 예시: 페이지 프레임이 3개이고 페이지 참조가 1, 2, 3, 4일 때, 1의 참조 비트가 설정되어 있으면 초기화하고 2로 넘어가며, 참조 비트가 없는 페이지는 교체됩니다.

기출 따라잡기

문제 1

4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때, FIFO 페이지 교체 알고리즘을 사용할 경우 페이지 결함의 발생 횟수를 구하시오.

페이지 참조 순서: 1, 2, 3, 1, 2, 4, 5, 1

• 답: 6회
• 해설: FIFO 알고리즘은 가장 먼저 들어온 페이지를 가장 먼저 교체하는 방식입니다. 초기에는 모든 페이지가 비어 있으므로 처음 4개의 페이지는 모두 적재되고 이후 페이지 4와 5가 참조되면서 페이지 결함이 발생하게 됩니다.

문제 2

4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때, LRU 페이지 교체 알고리즘을 사용할 경우 페이지 결함의 발생 횟수를 구하시오.

페이지 참조 순서: 1, 2, 3, 1, 2, 4, 5, 1

• 답: 5회
• 해설: LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식입니다. 처음 4개의 페이지가 모두 적재된 이후, 가장 오랫동안 참조되지 않은 페이지가 교체됩니다. 이 과정에서 페이지 결함이 총 5회 발생합니다.

문제 3

페이지 교체 기법 중 매 페이지마다 두 개의 하드웨어 비트, 즉 참조 비트와 변경 비트가 필요한 기법을 쓰시오.

• 답: NUR (Not Used Recently)
• 해설: NUR 알고리즘은 참조 비트와 변경 비트를 사용하여 페이지가 최근에 사용되었는지를 판단합니다. 이를 통해 페이지 교체 대상을 선정하는 방식입니다.

문제 4

요구 페이지 기법 중 가장 오랫동안 사용되지 않았던 페이지를 먼저 교체하는 기법을 쓰시오.

• 답: LRU (Least Recently Used)
• 해설: LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식으로, 페이지 참조 시간을 기록하여 사용하지 않은 페이지를 선택합니다.