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

foresec·2023년 7월 27일

Computer Science

목록 보기

26/28

페이지 교체 알고리즘

페이지 부재(프로세스가 요구한 페이지가 현재메모리에 없음)가 발생할 시, 새로운 페이지를 할당해야하는데 현재 할당된 페이지 중 어떤것을 교체할지 결정하는 방법

메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 재배치 정책

Page Reference String

CPU는 논리 주소를 통해 특정 주소를 요구함

메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함 발생 X

따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로 Page Reference String

종류

성능 평가 기준

페이지 부재 횟수, 페이지 성공 횟수 기준으로 비교
유지비용도 고려해야함

무작위 페이지 교체 알고리즘

스왑 영역으로 쫒아낼 대상 페이지(victim page)를 특별한 로직 없이 무작위로 선정
알고리즘의 성능이 좋지 않아 거의 사용되지 않음

FIFO 알고리즘

시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지(victim page)로 선정하여 스왑 영역으로 쫒아냄

이지 부재(page fault)가 일어난 경우(원하는 페이지가 메모리에 없는 경우)는 실패로, 그렇지 않은 경우(원하는 페이지가 메모리에 있는 경우)는 성공

큐로 구현됨

초기화 코드에 적절함
(초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음)

메모리에 먼저 올라왔어도 자수 사용되는 페이지가 있기도 하고, 나중에 올라왔어도 한 번만 사용되는 페이지가 있기도 함. FIFO 페이지 교체 알고리즘은 무조건 오래된 페이지를 대상 페이지(victim page)로 선정하기 때문에 성능이 떨어지는데 이러한 문제점을 개선한 것이 2차 기회 페이지 교체 알고리즘

OPT 알고리즘

최적 페이지 교체 알고리즘(Optimal page replacement algorithm)은 앞으로 가장 사용하지 않을 페이지를 스왑 영역으로 옮김. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정

최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋음. 하지만 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없음

위와 같은 방식에 근접한 방식이 대표적인 최적 근접 알고리즘들인 LRU(Latest Recently Used)와 LFU(Latest Frequently Used).
최적 페이지 교체 알고리즘은 미래의 데이터를 참고로 하기 때문에 구현이 불가능한 반면에, 최적 근접 알고리즘은 과거의 데이터로부터 미래를 예측하기 때문에 최적 페이지 교체 알고리즘과 유사한 성능을 가짐

LRU 알고리즘

(접근 시간 기준)
Latest Recently Used page replacement algorithm
메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮기는 방식

시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있음

반적으로 LRU 페이지 교체 알고리즘의 선능은 FIFO 페이지 교체 알고리즘보다 우수하고 최적 페이지 교체 알고리즘보다는 조금 떨어진 것

LFU 알고리즘

현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김

처음 메모리에 올라온 페이지의 사용 빈도가 1이고, 페이지가 사용될 때마다 하나씩 증가함

RU, LFU 페이지 교체 알고리즘은 둘 다 FIFO 페이지 교체 알고리즘보다 성능이 우수

LFU 페이지 교체 알고리즘의 단점은 LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많아 메모리가 낭비됨

NUR 알고리즘

최근 미사용 페이지 교체 알고리즘

LRU, LFU 페이지 교체 알고리즘 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘

참조비트와 변경비트 2개만 사용하여 미래를 추정함
참조비트를 우선적으로 고려하며 그다음으로 변경비트

최적 근접 알고리즘인 LRU, LFU, NUR 페이지 교체 알고리즘의 성능은 거의 비슷하며 FIFO 페이지 교체 알고리즘보다 우수하다. 이 중에서 NUR 페이지 교체 알고리즘은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 뿐만 아니라 쉽게 구현할 수 있다는 장점 덕분에 가장 많이 사용

FIFO 변형 알고리즘

2차 기회 페이지 교체 알고리즘과 시계 알고리즘 2가지

2차 기회 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용하지만, 차이점은 특정 페이지에 접근하여 페이지 부재(page fault)없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지(page fault)에서 제외하는 방식
즉, 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줌

성능은 LRU, LFU, NUR 페이지 교체 알고리즘보다 약간 낮고, FIFO 페이지 교체 알고리즘보다 약간 높음

단점은 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가되는 것

시계 알고리즘

시계 알고리즘은 원형 큐를 사용함
스왑 영역으로 옮길 대상 페이지(victim page)를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 바닥으로 내려가면 다음에는 다시 큐의 처음을 가리키게 된다. 위 그림에서 보듯이 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부름