운영체제를 공부하다보면 물리적 주소가 아닌 가상의 주소를 사용하는 가상메모리와 가상 메모리 기법 중에 큰 프로그램을 여러 개의 page 단위로 쪼개서 사용하는 paging 기법에 대하여 공부하게 됩니다. 하나의 프로그램이 수행될 때, 한 번에 메모리에 올리지 않고 page 단위로 쪼개서 사용하게 되면서, HDD나 SSD와 같은 저장장치에서 일부만 불러와서 사용할 수 있습니다. 이렇게 되면서 여러개의 프로그램을 메모리에 올릴 수 있고, 메모리 용량보다 프로그램의 크기가 큰 경우에도 수행할 수 있으며, CPU의 가용률이 더 높아지게 됩니다. 또, 부족한 메모리를 효율적으로 사용할 수 있습니다.
이후, 프로그램 전체를 디스크에서 물리 메모리에 적재하지 않고, 초기에 필요한 것들만 적재하는 전략 Demand Paging(요구 페이징)에 대하여 공부하게 됩니다. 이 때, 여러 요구 페이징 알고리즘이 있는데 FIFO 에 대하여 먼저 배우게 됩니다. 먼저 들어온 페이지를 먼저 삭제하는 방법입니다.
요구 페이징의 FIFO를 배우면 바로 이 포스팅의 주제인 Belady의 역설(Bélády's anomaly)이라는 단어가 등장합니다. Belady의 역설은 일반적인 통념과 매우 다릅니다. 흔히 생각했을 때에는, 사용하는 page frame이 많아질수록 가지고 있는 page의 개수가 많기 때문에 사용하려는 페이지가 없는 page fault 문제가 덜 발생할 것이라고 예측합니다. 하지만 아래의 사례는 이 통념을 깨줍니다.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 3개의 page frames을 사용하면 9개의 page faults가 발생합니다. 4개의 page frames 으로 증가시키는 경우에는 10개의 page faults가 발생합니다. 빨간색으로 표기된 곳에서 Page faults가 발생합니다. |
위의 표는 위키피디아에서 참조한 것으로, 실제 예시를 통하여 확인할 수 있습니다. 직관적으로 말이 전혀 되지 않아보이지만, 아래의 사례를 통하여 이런 사례가 존재한다는 것을 알 수 있습니다. 3개의 page frames을 사용하는 경우에 4개의 page frames 을 사용하는 것보다 더 적은 page fault가 발생합니다.
Belady의 역설은 일반적으로 FIFO (선입 선출) 페이지 교체 알고리즘을 사용할 때 발생하고, LRU (Least Recently Used) 와 같은 알고리즘에서는 페이지 프레임이 증가함에 따라 페이지 폴트가 감소한다고 합니다.
Reference