페이지 교체 알고리즘 계산기 (FIFO·LRU·LFU·OPT)

프레임을 늘렸는데 페이지 부재가 오히려 늘어나는 현상입니다. 메모리를 더 줬는데 성능이 나빠지는 것이라 직관에 반해서 발견자 이름을 붙여 부릅니다. 참조열 1 2 3 4 1 2 5 1 2 3 4 5를 FIFO로 돌리면 프레임 3개일 때 9회, 4개일 때 10회로 늘어납니다. 이 계산기의 «벨레이디 이상 현상» 예제를 FIFO로 돌리시면 직접 보실 수 있습니다.

LRU가 스택 알고리즘이기 때문입니다. 프레임이 n개일 때 메모리에 들어 있는 페이지 집합이 언제나 n+1개일 때의 부분집합이 된다는 성질인데, 부분집합이면 프레임을 늘렸을 때 적중하던 것은 계속 적중하므로 부재가 늘어날 수 없습니다. LFU와 OPT도 스택 알고리즘이고, FIFO와 2차 기회는 아닙니다. 「LRU에서는 안 일어난다」가 아니라 「스택 알고리즘이라 일어날 수 없다」가 정확한 설명입니다.

쓸 수 없습니다. 앞으로 어떤 페이지를 언제 참조할지 미리 알아야 하기 때문입니다. 그럼에도 계산하는 이유는 하한선이기 때문입니다 — 어떤 알고리즘도 OPT보다 페이지 부재를 줄일 수 없으므로, 지금 쓰는 알고리즘이 OPT에 얼마나 가까운지가 개선 여지를 말해 줍니다. 교재의 표준 참조열에서 OPT는 9회, LRU는 12회, FIFO는 15회입니다.

구현 비용 때문입니다. 참조할 때마다 시각을 기록하거나 페이지 목록의 순서를 바꿔야 하는데, 이것을 메모리 참조마다 하는 것은 하드웨어 도움 없이는 너무 비쌉니다. 그래서 실제로는 참조비트 하나만 두고 근사하는 2차 기회(Clock) 계열을 씁니다. 성능은 LRU에 조금 못 미치지만 비용이 훨씬 쌉니다.

FIFO인데 참조비트가 1이면 한 번 봐줍니다. 시곗바늘을 돌리며 후보를 보고, 참조비트가 0이면 그것을 내보내고 1이면 0으로 내린 뒤 지나갑니다. 모두 1이어도 한 바퀴를 돌면 전부 0이 되므로 두 바퀴 안에 반드시 하나가 잡힙니다. 새로 올린 페이지의 참조비트를 1로 둘지 0으로 둘지에 따라 답이 달라지므로 이 계산기는 그것을 고를 수 있게 해 두었습니다.

동점 처리 규약이 다르기 때문일 가능성이 큽니다. 이 계산기는 LFU에서 참조 횟수가 같으면 먼저 들어온 것을 내보내는데, 가장 오래 안 쓴 것을 내보내는 규약을 쓰는 자료도 있어 값이 갈립니다. OPT에서 앞으로 다시 안 쓰는 페이지가 여럿일 때도 먼저 들어온 것을 내보냅니다. 이 경우 부재 횟수는 어느 것을 골라도 같지만 표에 남는 모양이 달라집니다. 2차 기회라면 새 페이지의 참조비트 설정을 먼저 확인해 보세요.

피할 수 없는 부재입니다. 프레임이 비어 있을 때는 어떤 알고리즘을 써도 그 페이지를 처음 올려야 하므로, 서로 다른 페이지가 k종류라면 최소 k번의 부재는 반드시 생깁니다. 그래서 알고리즘을 견줄 때는 전체 부재보다 «교체로 생긴 부재»를 보는 편이 뜻이 있습니다. 이 계산기는 둘을 나눠 보여 줍니다.

다루지 않습니다. 이 계산기는 참조열 하나와 프레임 수가 정해진 상태에서 교체 알고리즘만 비교합니다. 스레싱은 여러 프로세스가 프레임을 나눠 쓰면서 서로의 페이지를 밀어내는 상황이라 프로세스별 프레임 할당 정책이 함께 필요하고, 워킹셋과 프리페이징도 별도 모형이 있어야 합니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.