[Virtual Memory] Page replacement

이전에 가상 메모리 시스템에서 프레임 할당을 관리하는데 단일 연결 리스트를 사용하는 방법을 살펴보았다.

당시 논점 중 하나인 사용 가능한 프레임의 리스트가 비어 있을 때 어떻게 새로운 프레임을 할당하는가에 대한 얘기를 해보자.

이 상황을 처리하기 위해 실제 메모리의 페이지를 스왑 디스크라고 불리는 영역으로 옮겨서 한 프레임을 해제한다.

어떤 순간에 어느 프레임을 해제할 것인지를 결정하는 데 페이지 교체(page-replacement) 알고리즘이 사용된다. 페이지 교체 알고리즘의 한 예가 재시도 알고리즘(second-change) 또는 클릭(click) 알고리즘이다.

이상적으로는 프로세스들의 모든 페이지가 실제 메모리에 존재하면 좋겠짐나 일반적으로 불가능하다.

전형저으로 한 시스템의 많은 프로세스들이 실제 메모리를 서로 차지하려고 다투면서 동시에 실행된다. 때로는 심지어 한 프로세스가 실제 메모리보다 큰 주소 공간을 사용할 수 도 있다.

페이지를 교체해야 하는 상황에서 앞으로 가장 오랫동안 접근되지 않을 페이지를 교체하는 것이 합리적으로 보인다.

하지만 미래를 예측할 수 없으므로 과거가 미래에 대한 암시라는 가정 하에 가장 오랫동안 접근하지 않은 페이지를 교체한다.

이 방법을 LRU(Least Recently Used) 페이지 교체라고 한다.

재시도 알고리즘은 LRU 페이지 교체 방법을 구현하는 하나의 방법이다. 이 방법은 실제 메모리에 존재하는 페이지들을 원형 리스트로 관리한다.

단순히 리스트의 각 항목이 페이지에 존재하는 페이지들을 원형리스트로 관리한다.

단순히 리스트의 각 항목이 페이지 번호와 reference 값( 0또는 1)만 갖는다고 생각하자. 실세로 각 항목은 다른 정보도 함께 가질 수 있다. 모든 페이지의 초기 reference 값은 0이다. 시스템이 페이지에 접근할 때마다(페이지를 읽거나 쓰는 과정에서) 그 페이지의 값은 1이 된다.

새로운 프레임이 필요하게 될 때 교체할 페이지를 결정하기 위해 원형 리스트와 reference 값들을 사용한다. 

이를 결정하기 위해 리스트의 항목 중 reference 값이 0인 항목을 찾는다. 리스트의 각 항목을 순회할 때 페이지의 reference 값이 1이면 0으로 바꾼다.

reference 값이 0인 항목을 만나면 리스트의 마지막 쉰회 이우에 접근되지 않은 페이지 즉, LRU 페이지를 찾은 것이다. 이 페잊의 실제 메모리가 새로운 페이지로 교체되고 리스트의 항목도 새 페이지로 바뀐다.

이전 리스트 순회 과정 이후에 모든 페이지에 접근되었다면 순회 과정은 전체 리스트를 한바퀴 돌게 되고 이 때는 순회를 시작했던 위치의 페이지를 교체한다.

replace_page 함수는이러한 페이지 교체 방법을 구현한 것이다.

순회를 시작할 페이지 항목을 가리키는 매개변수 current를 전달받는다. 리스트를 순회할 때 각 항목에 저장된 구조체 Page의 reference 멤버가 1이지 0인지를 조사한다.

1이면 0으로 바꾼 후 다음 페이지로 이동하고, 0이면 교체할 페이지를 찾은 것이다.

모든 페이지가 순회된다면 리스트의 원형적 특성으로 순회를 시작한 페이지로 돌아온다. 이 떄에는 이 페이지의 reference 값이 0이므로 교체할 페이지로 리턴된다. 리턴할 때 current는 순회가 끝난 시점의 페이지를 가리키고 다음에 새로운 프레임이 필요할 때 순회의 시작 위치가 된다.

실행 시간 복잡도는 원형 리스트의 페이지 개수가 n일 때 O(n)이다. 최악의 경우에는 교체할 페이지를 찾기 위해 리스트를 한바퀴 돌아야 하기 때문이다.

int replace_page(CListElmt ** current){

 // 교체할 페이지를 찾을 떄 까지 리스트 순회

while (((Page*)(*current)->data)->reference !=0) {

((Page*)(*current->data)->reference = 0;

*current = clist_next(*current);

}

return ((Page *)(*current)->data)->number;

}

[참조] Algorithms with C