victim policy?

물리 메모리에 프레임을 할당하다 메모리 용량이 가득 차서 더 이상 적재할 수 없을 때 어떤 프레임을 스왑공간으로 옮기는 스왑아웃이 발생합니다. 이때 어떤 프레임을 스왑공간으로 쫓아낼지 결정하는 알고리즘이 victim policy입니다.

FIFO

fifo는 first in first out으로 가장 먼저 들어온 프레임부터 희생자로 선정하는 방식입니다. 코드로 보시면, pop_front를 사용하여 리스트의 맨 앞에 있는 프레임을 희생자로 만듭니다. 구현이 매우 간단하다는 장점이 있지만, 자주 사용되는 프레임이 희생될 수 있다는 단점이 있습니다.

LRU

다음으로는 Least Recently Used입니다.
LRU는 최근에 사용되지 않은 페이지를 교체하는 알고리즘입니다.
그림을 보시면, 접근한 프레임은 frame_table의 맨 뒤로 재배치되며, 가장 오래된 프레임을 희생자로 선택합니다.
현재 핀토스에서 제공하는 이중 연결 리스트를 사용해, prev와 next 포인터를 수정하여 구현할 수 있습니다.

코드를 보시면, vm_get_victim 함수에서는 배열이 이미 재배치되어 있기 때문에 FIFO와 마찬가지로 pop을 사용하여 희생자를 선정합니다.
배열을 재배치하는 함수는 lru_update입니다. 이 함수는 접근한 프레임을 프레임 테이블에서 삭제한 후 맨 뒤로 재배치하는 방식으로 동작합니다.

lru_update함수는 프레임에 접근할때마다 작업을 수행해야합니다.
핀토스상에서 swap_in, file read나 write, lazy_load_segment에서 해당 작업을 수행해줘야 한다 생각하고 추가해줬습니다.

clock

Clock 알고리즘은 원형 큐를 사용하며, accessed bit를 통해 페이지를 선택하는 방식입니다.
만약 accessed bit가 1이라면 즉, 최근에 참조된 페이지라면, 해당 비트를 0으로 설정하고, accessed bit가 0인 페이지를 찾을 때까지 계속 검사합니다. accessed bit가 0인 페이지를 발견하면 그 페이지를 희생자로 선정합니다.

코드를 보시면, 원형 큐를 사용하여 리스트의 끝에 도달하면 다시 리스트의 시작으로 돌아가는 방식으로 구현됩니다.
무한 루프에서 pml4_is_accessed를 사용해 페이지가 접근되었는지 확인하고, 접근된 페이지는 pml4_set_accessed로 false 처리합니다. 접근되지 않은 페이지가 발견되면 그 페이지를 희생자로 선정합니다.