FIFO(First-In, First-Out) 알고리즘
설명 : 가장 먼저 메모리에 들어온 페이지를 가장 먼저 교체
장점 : 구현이 간단하고 직관적
단점 : 오래된 페이지가 자주 사용될 수 있는데도 불구하고 교체될 수 있음(이는 성능 저하를 초래할 수 있음)
예시 : 페이지가 A, B, C 순서로 들어왔고 새 페이지 D가 들어와야 한다면, 가장 먼저 들어온 A 페이지를 교체
LRU(Least Recently Used) 알고리즘
설명 : 가장 오랫동안 사용되지 않은 페이지를 교체
장점 : 자주 사용되는 페이지는 메모리에 남아 있도록 하여 성능을 최적화할 수 있음
단점 : 구현이 복잡하고 페이지의 최근 사용 기간을 추적하는 데 오버헤드가 발생할 수 있음
예시 : 페이지 A, B, C가 메모리에 있고 최근 사용 순서가 C, B, A라면 새 페이지 D가 들어올 때 가장 오래 사용되지 않은 A가 교체됨
LFU(Least Frequently Used) 알고리즘
설명 : 사용 빈도가 가장 적은 페이지를 교체
장점 : 자주 사용되는 페이지는 메모리에 남아 있도록 함
단점 : 페이지의 사용 빈도를 추적해야 하므로 오버헤드가 발생할 수 있음, 최근에 많이 사용되었지만 현재는 사용되지 않는 페이지가 남아 있을 수 있음
예시 : 페이지 A(3번), B(2번), C(1번) 사용되었다면 새 페이지 D가 들어올 때 가장 적게 사용된 C가 교체됨
Optimal(OPT) 알고리즘(LFD, Longest Forword Distance)
설명 : 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체함, 이론적으로 최적의 알고리즘으로 페이지 포트율을 최소화할 수 있음
장점 : 이론적으로 가장 낮은 페이지 폴트율을 보장함
단점 : 미래의 메모리 참조를 예측해야 하므로 현실적으로 구현이 불가능함
예시 : 페이지 A, B, C가 있고 미래 참조 순서가 B, C, A라면 새 페이지 D가 들어올 때 앞으로 가장 오랫동안 사용되지 않을 A가 교체
Clock 알고리즘(Second-Chance 알고리즘)
설명 : 각 페이지에 접근 여부를 기록하는 비트를 사용하여 FIFO 알고리즘을 수정한 것, 페이지가 교체될 때 해당 페이지의 비트를 확인하고 비트가 설정되어 있으며 한 번의 기회를 더 주고 비트를 초기화함
장점 : FIFO의 단점을 보완하며 최근 사용된 페이지를 좀 더 오래 유지할 수 있음
단점 : 비트 확인 및 설정 작업이 필요하므로 오버헤드가 있을 수 있음
예시 : 페이지가 A, B, C가 있고 A와 C가 최근에 사용되었지만 B는 사용되지 않았다면, B를 교체함(만약 모두 사용되었다면 한 번의 기회를 더 주고 다음 페이지를 검토)
NRU(Not Recently Used) 알고리즘
설명 : 페이지에 두 개의 비트(참조 비트와 수정 비트)를 사용하여 특정 시간 간격마다 이 비트를 초기화함, 교체 시 참조 되지 않고 수정되지 않은 페이지를 우선적으로 교체
장점 : 자주 사용되지 않은 페이지를 우선적으로 교체
단점 : 참조 및 수정 비트를 자주 초기화하고 검사해야 하므로 오버헤드가 발생할 수 있음
예시 : 참조 비트와 수정 비트가 모두 0인 페이지 중에서 선택하여 교체
