[CS] 페이지 교체 알고리즘

giggle·2023년 8월 1일

📌 페이지 교체 알고리즘이란?

페이지란?

논리적 주소 공간은 동일한 크기로 나눈 것을 페이지(Page)라 하고, 물리적 주소 공간을 동일한 크기로 나눈 것을 프레임(Frame)이라 합니다.

페이지는 논리 메모리와 물리 메모리간의 매핑 단위로 사용되는 고정 크기의 블록입니다. 논리 메모리는 프로세스가 사용하는 주소 공간이며, 물리 메모리는 실제 램에 해당하는 주소 공간입니다.

페이지는 페이지 테이블을 통해 가상 주소에서 물리 주소로 변환되어 실제 메모리에 적재됩니다.

페이지 교체 알고리즘이란?

프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재(page fault)가 발생합니다. 페이지 부재가 발생하면 스왑 영역에서 페이지를 메모리로 가져오는데, 만약 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑영역으로 보내야 합니다.

페이지 교체 알고리즘은 이러한 상황에서 스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 앞으로 사용할 가능성이 적은 페이지를 대상 페이지(victim page)로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상합니다.

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

무작위 페이지 교체 알고리즘(random page replacement algorithm)

페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방식입니다. 말 그대로 스왑 영역으로 보낼 대상 페이지를 특별한 로직없이 무작위로 선정합니다.

대부분 프로세스의 메모리 접근 패턴을 보면 메모리의 인접한 영역에 저장되는 지역성을 가지는데, 해당 알고리즘은 지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 합니다.

따라서, 알고리즘의 성능이 좋지 않아 거의 사용되지 않습니다.

FIFO 페이지 교체 알고리즘(First In First Out page replacement algorithm)

선입선출 페이지 교체알고리즘인 FIFO 페이지 교체 알고리즘은 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지(victim page)로 선정하여 스왑 영역으로 보냅니다.

FIFO 페이지 교체 알고리즘은 큐로 구현하여 페이지 부재(page fault)가 일어난 경우(원하는 페이지가 메모리에 없는 경우)는 실패로, 그렇지 않은 경우(원하는 페이지가 메모리에 있는 경우)는 성공이라고 표시했습니다.

무조건 오래된 페이지를 대상 페이지(victim page)로 선정하기 때문에 자주 사용하는 페이지를 고려하지 못해 성능이 떨어지는데 이러한 문제점을 개선한 것이 2차 기회 페이지 교체 알고리즘(second chance replacement algorithm)입니다.

최적 페이지 교체 알고리즘(Optimal page replacement algorithm)

최적 페이지 교체 알고리즘은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옯깁니다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정합니다. 즉, 프레임에 있는 페이지가 가장 나중에 불리는 것을 대상 페이지로 선정하는 것입니다.

최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋습니다. 하지만 미래의 접근 패턴을 확인하는 것이 불가능하기 때문에 실제 구현은 불가능합니다.

최적 페이지 교체 알고리즘에 근접하는 방법을 연구한 결과 최근 최소 사용 알고리즘인 LRU(Latest Recently Used)와 최소 빈도 사용 알고리즘인 LFU(Latest Frequently Used), 최근 미사용 알고리즘인 NUR(Not Used Recently) 등이 개발되었습니다. 이러한 알고리즘은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(Optimal approximation algorithm)이라고 부릅니다.

LRU 페이지 교체 알고리즘(Latest Recently Used page replacement algorithm)

LRU 페이지 교체 알고리즘은 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮기게 됩니다. 오래전에 사용된 페이지를 대상 페이지로 선정된다는 것입니다. LRU 페이지 교체 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있습니다.

LRU 페이지 교체 알고리즘은 페이지에 접근한 지 가장 오래된 페이지를 교체합니다. 즉 페이지에 읽기, 쓰기, 실행과 같은 연산이 이루어진 시간을 기준으로 선정합니다. 해당 알고리즘은 카운터를 활용해서 구현할 수도 있으나, 접근 시간을 기록하든 카운트를 기록하든 두 방법은 모두 추가적인 메모리 공간을 필요로 하는 것이 단점입니다.

LFU 페이지 교체 알고리즘(Latest Frequently Used page replacement algorithm)

LFU 페이지 교체 알고리즘(Latest Frequently Used page replacement algorithm)은 '최소 빈도 사용 알고리즘' 이라고도 합니다. 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정합니다. 즉, 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 이동시킵니다.

위에서 괄호의 숫자는 사용빈도를 나타냅니다. 이 사용빈도에 따라 대상 페이지를 결정하는데, 만약 사용 빈도가 동일하다면 맨 위의 페이지를 선택하도록 가정했습니다.

LFU 페이지 교체 알고리즘의 단점은 LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많다는 것입니다. 페이지 접근 횟수(빈도)를 표시하는 데 추가 공간이 필요하므로 그만큼 메모리가 낭비됩니다.

NUR 페이지 교체 알고리즘(Not Recently page replacement algorithm)

NUR 페이지 교체 알고리즘(Not Recentlu replacement algorithm)은 LRU, LFU 페이지 교체 알고리즘 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘입니다. NUR 페이지 교체 알고리즘은 '최근 미사용 페이지 교체 알고리즘'이라고도 불립니다.

NUR 페이지 교체 알고리즘에서 우선 고려 대상은 참조 비트이다. 참조 비트가 0인 페이지를 먼저 찾고, 변경 비트가 0인 페이지를 찾는다. 만약 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정한다. 흔한 경우는 아니지만 모든 페이지의 비트가 (1,1)일 때는 어떤 페이지가 더 자주 사용되는 지를 알 수 없어 NUR 페이지 교체 알고리즘을 정상적으로 적용할 수 없다. 그러므로 NUR 페이지 교체 알고리즘에서 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (0,0)으로 초기화한다.(reset)