[운영체제] 가상 메모리 관리 - 3. 페이지 교체 알고리즘

페이지 교체 알고리즘

요구 페이징을 통해 페이지들이 메모리에 점차 적재하다 보면 언젠가는 메모리가 가득 찰 것이다. 메모리에 페이지가 가득 찬 상황에서 추가적으로 페이지를 적재해야 한다면 메모리에 적재된 일부 페이지를 스왑 아웃(페이지 아웃) 해야 한다. 이때 메모리에 적재된 페이지 중 보조기억장치로 내보낼 페이지를 선택하는 방법을 페이지 교체 알고리즘이라고 한다.

 

페이지 교체 알고리즘은 컴퓨터 전체 성능과 직결되며, 좋은 페이지 교체 알고리즘은 페이지 폴트를 적게 일으키는 알고리즘이다.

 

페이지 폴트를 적게 일으킨다는 것은 페이지 참조열을 보면 된다. 페이지 참조열은 CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지열이다.

참조한 페이지 
[ 2, 2, 2, 3, 5, 5, 5, 3, 3, 7 ]

페이지 참조열
[ 2, 3, 5, 3, 7 ]

연속된 페이지는 아무래도 이미 메모리에 적재됨을 나타낸다. 그걸 제외한 페이지의 순차적 리스트가 페이지 참조열이기 때문에 참조열이 많을 수록 페이지 폴트가 일어날 가능성이 크게 된다. (물론 메모리 당 프레임의 개수가 매우 크면 상관없을 수 있다.)

 

FIFO 페이지 교체 알고리즘

이름 그대로 메모리에 가장 먼저 적재된 페이지부터 스왑 아웃하는 페이지 교체 알고리즘이다. 

위 그림의 프레임을보면 참조열에 있는 순서대로 적재가 된다. 적재된 프레임이 있다면 그것을 그래도 사용하므로 폴트가 일어나지 않는다. 페이지 폴트가 일어나는 시점을 보면 프레임이 가득 찬 `5`가 시작된 것을 보면 가장 오래 적재된 페이지 `2`가 페이지 아웃이 되는 것을 알 수 있다.

 

2차 FIFO 교체 알고리즘

일반 FIFO 교체 알고리즘은 가장 오래 적재된 페이지를 아웃시키는 방법인데 이 방법엔 문제가 존재한다. 초기에 적재된 페이지 중 프로그램 실행 내내 유지할 데이터가 있을 경우에도, 오래 적재되었단 이유로 아웃처리 될 수 있다.

 

이러한 문제를 해결하기 위해 FIFO 알고리즘을 변형하게 2차 FIFO 교체 알고리즘이다. 

• 기본적으로 가장 오래 메모리에 머물렀던 페이지부터 페이지-아웃을 시킨다.
• 다만 참조 비트가 1일 경우, 이를 0으로 변경 후 한번 더 기회 부여한다.
• 참조 비트가 0일 경우 페이지-아웃시킨다. 

그림을 통해 자세히 알아보자. 프레임이 페이지로 가득 차있다.

가득한 프레임에 새로운 페이지가 접근한다면, 우선 오래된 페이지를 확인해야 한다. 그럼 페이지 `3`이 가장 오래되었으므로 아웃될 타깃이 된다. 2차 FIFO에 경우 여기서 참조 비트를 확인하게 된다. 참조 비트가 `1`은 참조한 적이 있음을 나타냄으로 해당 페이지는 한번 더 기회를 부여받게 된다. 

 

다음 그림과 같이 페이지 `3`은 최근 적재된 페이지로 이동 후 참조 비트를 `0`으로 변경처리한다. 

 

 

최적 페이지 교체 알고리즘

앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다. 메모리에 적재된 페이지들 중 앞으로 가장 적게 사용할 페이지를 스왑 아웃해 가장 낮은 페이즈 폴트율을 보장한다. 

 

이름 그대로 최적의 알고리즘이지만, 앞으로 가장 적게 사용할 페이지를 미리 예측하기가 어렵기 때문에 실제 구현을 비현실적이다. 그렇기 때문에 실제 사용보단 이론적으로 페이지 교체 알고리즘의 성능을 평가할 때 주로 사용된다.

 

LRU 페이지 교체 알고리즘

가장 적게 사용할 페이지를 스왑 아웃하는 알고리즘은 예측하기 어렵기 때문에 비현실적이라 했다. 하지만 LRU 페이지 교체 알고리즘은 가장 사용한 페이지를 교체하는 알고리즘이다.(최근에 사용되지 않은 페이지를 아웃) 보편적으로 사용되는 교체 알고리즘의 원형이며, 이를 기반으로 만들어진 다양한 파생 알고리즘이 있다.

 

참고

https://fastcampus.co.kr/dev_online_newcomputer

초격차 패키지 : 현실 세상의 컴퓨터공학 지식 with 30가지 실무 시나리오 | 패스트캠퍼스