[PintOS] Victim Policy - 교체 알고리즘

대망의 마지막 핀토스 발표주제는 Swap Out 시 차용할 수 있는 페이지 교체 알고리즘의 정책들을 소개하고 비교해보는 것이었다.

 

우선 Memory의 Frame을 왜 Swap Out하며, 애초에 Swap Out이란 무엇일까?

이 부분부터 짚고 넘어가자

 

Swap Out?

Swap Out은 우리가 실제 물리메모리를 Frame 단위로 관리하고 이를 메인 메모리인 RAM에 적재하는 과정에서 더 이상 RAM에 적재할 수 없을때(용량이 다 차서) Page Fault를 일으키며, 발생하게된다.

 

그래서 페이지 교체가 어떻게 일어난다는건데! 🧐

그걸 위해 희생자 Frame을 만든다. 이때 어떠한 정책을 선택하느냐에 따라 Swap Out의 효율성이 갈리게 된다.

그래서 지금부터 어떠한 정책이 존재하고 각 이점을 설명하도록하겠다.

 

 

Victim Policy (페이지 교체알고리즘 정책)

Swap Out에서는 대중적으로 네 가지 방법이 존재한다

 

1. FIFO

2. LRU

3. Second Chance

4. ESC

 

이중 위의 3개만 다루며, ESC 방법은 Second Chance에 Modified Bit를 추가한 방법이다. 

 

FIFO(First In, First Out)

 

자료구조인 Queue를 사용하는 방법이다.

 

RAM이 꽉차면, 맨앞에 있는 Frame부터 희생 Frame으로 만든다.

 

그렇기에 구현은 간단하나, 자주 사용되는 Frame이 죽을 수 있는등의 단점이 존재하여 효율성이 좋지 못하다.

 

LRU (Least Recently Used)

우선 Pintos에서 LRU를 통해 Swap Out을 구현하는 방법은 두 가지가 있다.

 

첫번째로는 연결리스트를 이용해 구현하는 방법이고, 두번째로는 타임스탬프를 이용하는방법이다.

 

참고로, LRU는 두 방법 모두 시간지역성에 의거한 Swap Out 정책이다.

 

우선 연결리스트 방식부터 살펴보자

 

LRU - Linked List

 

가장 최근에 접근한 Page는 Frame을 관리하는 전역리스트에 맨 뒤로 재배치하는 방법이다.

그렇기에 가장 늦게 참조되는 Frame은 Swap Out시 희생 Frame으로 선택되어 Swap영역으로 방출된다.

 

LRU - TimeStamp

 

 

Time Stamp 방법을 사용하기 위해선 구조체를 수정하여 Frame이 참조되는 시간을 기록할 필드값을 추가한다.

이후 모든 Frame에 접근되는 작업마다 이를 새로운 시간으로 갱신해준다.

 

Second Chance

현재 우리팀에서 구현한 방법이다.

 

Second Chance의 경우 Access Bit가 1(True)인지 확인한다.

Access Bit는 해당 프레임이 최근 작업에 사용되었다면 항상 True로 유지된다.

 

이후 만약 True라면 다시 False로 바꾼후 다음 False인 프레임을 찾는 방법을 반복한다.

 

 

요약