스와핑이 일어날 때 페이지교체 알고리즘(PAGE REPLACEMENT ALGORITHM)에 의해 페이지가 교체되게 됩니다.

오프라인알고리즘

오프라인알고리즘은 가장 좋은 알고리즘이라고 일컫는 알고리즘이며 이는 가장 먼 미래에 참조되는 페이지와 현재의 페이지를 바꾸는 알고리즘 (LFD, Longest Forward Distance)입니다.

이게 최고의 알고리즘 근데 사용이 안돼, 미래에 뭐가 사용될지 모른다.

예를 들어 0, 1, 2, 3, 4, 2 이렇게 들어온다하면 가장 먼 미래에 참조되는 2와 스와핑을 한다.

구현 가능한 알고리즘

FIFO

FIFO(FIRST IN FIRST OUT) 첫번째 온 페이지가 첫번 째로 나간다.

LRU

LRU(LEAST RECENTLY USED) 최근에 사용되지 않은 페이지를 바꾸는 방법.
즉, 참조가 오래된 페이지를 바꾼다.
이를 위해서 각 페이지마다 최근 사용한 횟수를 나타내는 자료구조를 따로 만들어야할 수 있다.

예를 들어 7 0 1 2 0 3 0 4로 페이지 요청이 들어온다 가정하면 4개의 페이지만 담는다 가정햇을 때 다음처럼 된다.

7 0 1 2 로 들어온다 그 다음에 0이 들어오면 페이지 히트가 된다, 3이 들어오면 참조가 가장 오래된 페이지는 7이니까 3으로 교체된다, 0이 들어오면 0이 가장 최근에 참조된 것, 3 0 1 2 중에 4가 들어오면 3 0 4 2 가 된다.

NUR

LRU 에서 발전한 알고리즘 NUR(NOT USED RECENTLY) 또는 NUR(Not Recently Used) 라 불리는 알고리즘

0은 참조되지 않음, 1은 참조함

LFU