페이지 교체 알고리즘

페이지 교체 알고리즘

●페이지 교체 알고리즘

• 가상 메모리 관리 기법(Virtual Memory Management) 은 프로그램의 일부만을 메모리에 적재하여 실제 사용 가능한 물리 메모리 양보다 큰 프로세스를 실행할 수 있도록 하는 기법이며, 가상 메모리 관리 기법 중 하나인 페이징은 메모리의 물리 주소 공간을 프레임 단위로 나눈 이후, 프로세스의 논리 주소 공간을 페이지로 나누어 프레임에 할당하는 방식

• 프로세스를 메모리에 적재할 때, 실제로 필요할 때만 페이지를 메모리에 적재하는 것을 요구 페이징(Demand Paging) 이라 하며, 요구 페이징을 사용하는 운영체제에서 새로운 페이지를 할당하려고 하는데, 공간이 부족한 경우 메모리에 존재하는 다른 페이지와 신규 페이지를 교체해야하며 이때, 교체 대상을 결정하는 방법을 페이지 교체 알고리즘(Page Replacement Algorithm) 라고 함

●페이지 교체 알고리즘 종류

• FIFO 페이지 교체 알고리즘(First In First Out Page Replacement Algorithm) : 적재된 페이지의 순서대로 교체하는 알고리즘입니다. 단순히 먼저 적재되었다는 이유로 교체된다는 비효율을 개선하기 위해 2차 기회 페이지 교체 알고리즘과 같은 변형 알고리즘이 존재

• OPT 페이지 교체 알고리즘(Optimal Page Replacement Algorithm) : 앞으로 가장 나중에 사용될 페이지를 교체하지만, 페이지의 미래 사용 빈도와 접근 패턴을 알기 어렵기 때문에 이론적 알고리즘으로 분류

• LRU 페이지 교체 알고리즘(Least Recently Used Page Replacement Algorithm) : 가장 오래 사용되지 않은 페이지를 교체

• LFU 페이지 교체 알고리즘(Least Frequently Used Page Replacement Algorithm) : 가장 적게 사용된 페이지를 교체하며, 사용 빈도가 같은 경우에는 다른 페이지 교체 알고리즘을 사용

• NUR 페이지 교체 알고리즘(Not Used Recently Page Replacement Algorithm) : 최근에 사용된 적이 없는 페이지를 교체하며 LRU, LFU 알고리즘과 유사한 성능이 보이면서, LRU, LFU의 메모리 오버헤드를 줄일 수 있으며 LRU와 LFU는 페이지에 대한 추가적인 정보(사용 횟수, 마지막 접근 시간)를 관리해야 하며, NUR은 페이지 테이블 엔트리의 참조 비트와 수정 비트를 활용하여 교체 대상을 결정