page를 디스크로 스왑시키기 위해 필요한 것
1. present bit
하드웨어가 PTE에서 해당 page가 물리 메모리에 존재하지 않음을 표현해야 한다. 하드웨어는 present bit를 사용해 각 PTE에 어떤 페이지가 존재하는지를 표현한다. present bit가 1이라면 물리 메모리에 해당 page가 존재한다는 것이고 0은 물리 메모리에 존재하지 않고 디스크 어딘가 존재한다는 것이다.
만약 물리 메모리에 존재하지 않는 페이지에 접근하려고 한다면 페이지 폴트(page fault)를 만나게 될 것이다.
페이지 폴트 발생시, 페이지 폴트를 처리하기 위해 OS로 제어권이 넘어가, 페이지 폴트 핸들러(page fault handler)가 실행된다.
tip💡 여기서의 오류는 페이지가 존재하지 않음의 오류로 합법적인 접근을 오류라고 부른다. 그 이유는 프로세스가 불법적인 일을 할 때 처리하는 방법과 동일하기에, 이 동작을 "오류"라 해도 이상하지 않은 것이다. 일반적이지 않은 일 즉, 하드웨어가 어떻게 다뤄야 할지 모르는 어떤 일이 발생한다면, 상황 개선을 기대하며 하드웨어는 제어권을 운영체제에게 넘긴다. 프로세스가 원하는 페이지가 메모리에 없다고 하드웨어는 "예외"를 발생시키며, 그 이후는 OS가 처리를 담당하는 것이다.
2. page table
많은 시스템들에서 해당 페이지의 swap 공간에서의 위치를 페이지 테이블에 저장한다. 운영체제는 PFN과 PTE 비트들을 페이지의 디스크 주소를 나타내는데 사용할 수 있다.
페이지 폴트 발생시, 운영체제는 페이지 테이블 항목에서 해당 페이지의 디스크 상 위치를 파악하여, 메모리로 올린다. 디스크 I/O가 완료되면 운영체제는 해당 페이지 테이블 항목(PTE)의 PFN값을 올린 페이지의 메모리 위치로 변경한다. 이 작업이 완료되면 페이지 폴트를 발생시켰던 명령어가 재실행된다.
재실행할 때 변경된 주소를 참조해, 물리 주소에서 원하는 데이터를 가져온다.
tip💡 I/O 전송 중에는 해당 프로세스가 차단된(blocked) 상태가 된다. 페이지 폴트 처리시 매우 많은 시간이 걸리기 때문에 효율을 위해 다른 프로세스의 실행을 중첩시킴으로 운영체제는 다른 프로세스를 실행할 수 있다.
3. 페이지 교체 정책
Q swap-in을 하려 하는데 물리 메모리에 빈공간이 없다면?
공간 확보를 위해 이전에 물리 메모리에 있던 페이지들을 먼저 swap-out해야한다. 이렇게 교체할 페이지를 선택하기 위한 페이지 교체 정책이 필요하다.
Q 교체는 실제 언제 일어나는가?
우리의 작고 예민한 핀토스는 메모리에 여유 공간이 고갈된 후에 교체 알고리즘이 작동하지만 대부분의 운영체제들은 여유 공간 관련 최댓값과 최솟값을 설정하여 교체 알고리즘이 작동하게 된다.
물리 메모리의 여유 공간 크기가 최솟값보다 작아진다면 운영체제가 여유 공간 확보를 담당하는 백그라운드 쓰레드를 실행시킨다. 해당 쓰레드는 여유 공간의 크기가 최댓값에 이를 때까지 페이지를 제거 후 슬립 모드로 들어간다. 이 쓰레드가 스왑 데몬 혹은 페이지 데몬이라 불리는 놈이다.
우리 조는 시계 페이지 교체 알고리즘으로 교체정책을 정하여 진행하였다.
clock(시계의 시침)이 가리키는 페이지부터 시작하여 제거할 페이지를 찾을 때까지 while문을 도는 것이다. 최근 사용함을 표현한 accessed bit(used bit)가 0이면 최근 참조가 안됬다는 것으로 해당 페이지를 교체할 페이지로 선정하고, 1이면 최근 참조가 되었음으로 accessed bit(used bit)를 0으로 바꿔주고 다음 page로 clock(시계의 시침)을 이동시킨다. 0으로 바꿔주는 이유는 모두가 최근 참조되었다면 한바퀴를 다 돌았을 때 교체할 수 있을만한 페이지를 만들어주기 위해서이다.
시계 알고리즘으로 교체할 페이지를 골랐다면 해당 페이지의 dirty bit(수정되었는지 여부를 나타내는 bit)를 참조하여 1이면 file에 적어주고 dirty bit를 다시 0으로 설정한다. dirty bit는 수정시 hw에서 1로 세팅해준다.
추가적으로 우리조는 구현하지 않았지만 dirty bit가 1이라면 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야하기에 비싼 비용을 지불해야함으로 이를 고려하여 dirty하지 않은 페이를 내보내는 방법으로 시계 알고리즘을 업그레이드 할 수도 있다.
vm_get_victim
제거될 struct frame을 가져오는 함수를 구현하기 위해 필요한 리스트 및 lock을 vm.h에 선언해주고, vm_init()에서 초기화 해주었다.
struct list lru_list; // 할당된 물리 프레임들을 관리하는 리스트
struct lock lru_list_lock;
struct list_elem *lru_clock;lru_list가 할당된 물리 프레임들을 관리하는 리스트이기에 들어갈 lru_list에 들어갈 elem은 frame 구조체에 선언해주었다.
struct frame{
...
struct list_elem lru;
}
이 함수는 사용 가능한 메모리 공간을 얻기 위해 실제로 프레임을 제거한다.
static struct frame *
vm_get_victim(void){
struct frame *victim = NULL;
struct list_elem *fe;
struct frame *f;
/* TODO: The policy for eviction is up to you. - Clock Algorithm*/
/* while (제거할 페이지를 못찾을때까지 = 리스트 끝까지) {
if (현재 페이지의 accessed bit == 0)
너가 나가
else
accessed bit 0으로 세팅
clock pointer 옮기기
}*/
lock_acquire(&lru_list_lock);
if (lru_clock == NULL){
lru_clock = list_begin(&lru_list);
}
/* 첫번째 for문 : lru clock부터 리스트 끝까지 돌기*/
for (fe = lru_clock; fe != list_tail(&lru_list); fe = list_next(fe)){
f = list_entry(fe, struct frame, lru);
if (!pml4_is_accessed(f->thread->pml4, f->page->va)){
victim = f;
lru_clock = list_remove(fe);
if (lru_clock == list_tail(&lru_list)){
lru_clock = list_begin(&lru_clock);
}
goto done;
}
else {
pml4_set_accessed(f->thread->pml4, f->page->va, 0);
}
}
/* 두번째 for 문 : 처음부터 lru clock까지 돌기 */
for (fe = list_begin(&lru_list); fe != list_next(lru_clock); fe = list_next(fe)){
f = list_entry(fe, struct frame, lru);
if (!pml4_is_accessed(f->thread->pml4, f->page->va)){
victim = f;
lru_clock = list_remove(fe);
if (lru_clock == list_tail(&lru_list)){
lru_clock = list_begin(&lru_clock);
}
goto done;
}
else{
pml4_set_accessed(f->thread->pml4, f->page->va, 0);
}
}
goto done;
done:
lock_release(&lru_list_lock);
return victim;
}vm_evict_frame
초기화를 위해 페이지를 지우고 해당 프레임을 반환해주는 함수다.
static struct frame *
vm_evict_frame(void)
{
struct frame *victim UNUSED = vm_get_victim();
if (victim == NULL){
return victim;
}
/* virtual page swap out */
swap_out(victim->page);
/* frame 구조체 초기화 */
victim->page = NULL;
victim->thread = NULL;
/* frame 메모리 영역 안에 기록된 내용 0으로 초기화해주기 */
memset(victim->kva, 0, PGSIZE);
return victim;
}참고. OSTEP 물리 메모리 크기의 극복 : 메커니즘
