페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법입니다.
페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있습니다.
FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법
단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있음.
LFU : 가장 적은 횟수를 참조하는 페이지를 교체
단점 : 참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생
LRU : 가장 오랫동안 참조되지 않은 페이지를 교체
단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생
◆ 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 알고리즘이다.
◆ 주로 캐시에서 메모리를 다루기 위해 사용된다.
◆ 캐시는 크게 보면 웹 서비스부터, 작게는 CPU가 RAM이나 Disk에 접근할 때.. 등 광범위하게 사용됨.
◆ 이러한 캐시들은 자원이 한정되어있으며, 한정된 자원 내에서 빠르게 데이터 접근이 가능해야 한다.
◆ 따라서 어떤 데이터를 남기고, 어떤 데이터를 지울지에 대한 알고리즘이 필요.
◆ 여기서 오래 참조되지 않은 데이터는 내보내는 '시간(temporal) 지역성'의 성질을 가지는 알고리즘이다.
◆ LRU는 아래와 같은 장/단점을 가진다.
장점
- 빠른 액세스
가장 최근에 사용한 아이템부터 가장 적게 사용한 아이템까지 정렬된다.
따라서 두 아이템에 접근할 경우, O(n)의 시간 복잡도를 가진다.
- 빠른 Update
하나의 아이템에 엑세스 할때마다 업데이트 되며, O(n)의 시간 복잡도를 가진다.
단점
- 많은 공간 차지
n개의 아이템을 저장하는 LRU는 n의 크기를 가지는 1개의 Linked-list와(혹은 Queue) 이를 추적하기 위한 n의 크기를 가지는 1개의 hash-map이 필요하다.
이는 O(n)의 복잡도를 가지지만, 2개의 데이터구조를 사용해야 한다는 단점이 있다.
