Belady's Anomaly(벨라디의 모순)

'Belady's Anomaly(벨라디의 모순)'는 컴퓨터 과학에서 발생하는 현상 중 하나로, 페이지 교체 알고리즘을 평가하는 데 사용됩니다. 페이지 교체 알고리즘은 가상 메모리 관리 시스템에서 사용되며, 메모리에 로드된 페이지 중 어느 것을 제거하고 디스크로 스왑아웃해야 할지 결정하는 데 사용됩니다.

Belady's Anomaly는 페이지 교체 알고리즘이 FIFO(First-In-First-Out) 방식을 따를 때 발생할 수 있습니다. FIFO 알고리즘은 가장 오래된 페이지를 제거하는 방식으로 동작합니다. 이 현상은 페이지 프레임의 수를 늘리더라도 페이지 부재(페이지 폴트)의 발생 횟수가 감소하지 않는다는 것을 의미합니다. 즉, 페이지 프레임의 증가가 페이지 부재를 더 자주 발생시키는 결과를 가져옵니다.

이 현상의 발생 원인은 다음과 같습니다. 페이지 프레임의 수가 증가하면 FIFO 알고리즘은 더 이전에 로드된 페이지를 제거하지 않고 유지합니다. 그러나 예기치 않게 더 이전에 로드된 페이지가 나중에 다시 참조될 수 있습니다. 따라서 페이지 프레임의 증가는 이러한 예기치 않은 페이지 참조에 대한 대비책으로는 작용하지 못하며, 결과적으로 페이지 부재의 빈도가 증가합니다.

Belady's Anomaly는 FIFO 알고리즘 외에도 다른 페이지 교체 알고리즘에도 영향을 줄 수 있지만, FIFO 알고리즘에서 가장 두드러지게 나타납니다. 이러한 이유로 FIFO 알고리즘은 메모리 관리에 사용되는 데에는 적합하지 않습니다. 이러한 문제를 해결하기 위해 최적 페이지 교체(Optimal Page Replacement) 알고리즘이나 LRU(Least Recently Used) 알고리즘 등 더 효율적인 알고리즘이 개발되었습니다.