벨라디의 역설

벨라디의 역설(Belady's anomaly)은 페이지 교체 알고리즘에서 프레임 수를 늘렸는데도 오히려 페이지 폴트가 증가하는 비정상적인 현상을 말한다. 이는 직관에 어긋나는 결과로, 모든 페이지 교체 알고리즘에서 발생하지는 않으며, 특정 알고리즘(FIFO 등)에서만 나타난다.

1 개념

• 일반적으로는 페이지 프레임 수를 늘리면 페이지 폴트 수가 줄어들거나 유지된다고 기대된다.
• 그러나 벨라디의 역설이 발생하는 알고리즘에서는 프레임 수가 증가했을 때 오히려 더 많은 페이지 폴트가 발생할 수 있다.
• 이는 해당 알고리즘이 사용 빈도나 시간 정보 없이 단순한 기준만으로 페이지를 교체하기 때문에 발생한다.

2 발생 조건

• FIFO(First-In, First-Out) 알고리즘에서 대표적으로 발생
• LRU(Least Recently Used), OPT(Optimal)와 같은 알고리즘에서는 발생하지 않음
• 특정 입력 시퀀스에 따라 발생 여부가 달라짐

3 예시

요청 페이지 순서: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• 프레임 수 3일 때:
  • 페이지 폴트: 9회

• 프레임 수 4일 때:
  • 페이지 폴트: 10회 (오히려 증가)

→ FIFO 알고리즘에서 이와 같은 현상이 발생함

4 영향

• 페이지 교체 알고리즘이 "프레임 수 증가 → 성능 향상"이라는 일반 원칙을 항상 만족하지 않음을 보여줌
• 실제 운영체제에서는 벨라디의 역설이 발생하지 않는 알고리즘(LRU, LFU 등)을 사용하는 것이 일반적

5 이름 유래

• 이 현상은 1969년, Laszlo Belady가 IBM 연구소에서 최초로 제시
• 실험을 통해 FIFO 방식에서 페이지 수 증가에 따른 역효과를 확인함

6 같이 보기

• 페이지 교체 알고리즘
• FIFO (페이지 교체 알고리즘)
• LRU (페이지 교체 알고리즘)
• OPT (최적 페이지 교체)
• 페이지 폴트

7 참고 문헌

• Belady, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 78–101
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson