[PINTOS] victim frame

메모리의 공간이 거의 없다면 운영체제는 메모리 압박을 해소하기 위해 다른 페이지들을 강제적으로 paing out 해여 활발히 사용 중인 페이지들을 위한 공간을 확보해야한다.. 내보낼(evit) 페이지 선택은 운영체제의 교체 정책에 따라서 달라진다. 
핀토스에서 우리팀이 구현한 내보낼 페이지의 선택을 어떻게 하는지 알아보자

 

 

Memory pressure

 

 

먼저 물리 메모리가 가득 찬 상황을 알아보자

우리팀이 구현한 가상메모리 페이지를 물리메모리 프레임과 맵핑을 시키는 함수이다.

해당함수에서 frame을 얻어오는 함수인 vm_get_frame()이 있는데 해당 함수를 살펴보면..

 

먼저 frame을 calloc을 통해서 커널풀에서 할당받고 난뒤에 frame 내부에 존재하는 kva를 초기화 시켜주는데

 

이때 palloc_get_page(PAL_USER) 를 이용해 커널풀이 아닌 유저풀에서 1페이지의 크기(4KiB)로 할당받아서 kva를 초기화 시켜준다

 

palloc_get_page 함수의 설명을 읽어보면

 

더이상 할당할 페이지가 없을때 null 포인터를 반환한다 , 즉 메모리 압박을 느끼는 상황이다

 

해당 상황일때 희생할 프레임을 선정해서 페이지와 맵핑을 해제하고 맵핑이 해제된 프레임을 다시 반환시켜서 정상적으로 새로운 페이지와 맵핑시켜주면된다.

 

---

 

vm_evict_frame() -FIFO

그렇다면 과연 어떤 프레임을 희생자프레임으로 선정해야할까

 

가장 단순한 방법으로는 FIFO를 생각 해볼 수 있다.

 

프레임을 새롭게 할당받으면 프레임을 관리하는 리스트에 push_back으로 넣어주고 메모리 압박을 받을 때마다 리스트의 맨 앞에서 꺼내서 프레임을 희생프레임으로 만들어버리고 새로 맵핑을 한뒤 다시 뒤로 넣어주면된다.

 

하지만 단순한 만큼 손해를 볼 것인데 여기서 캐쉬와 유사한 개념을 생각해야한다

FIFO의 구조라면 희생자로 선정된 프레임에 할당된 페이지가  자주접근하고 중요도가 높은 페이지일지라도 단지 먼저 들어왔다는 이유만으로 swap_out이 되어야한다 .

 

또한 FIFO는  Belady's anomaly가 나타 나는 알고리즘이다.       

3->4 구간을 보면 프레임수를 증가시켰는데도 오히려 page fault가 증가했다.

 

따라서 FIFO의 대안이 되는 다양한 희생프레임을 선정하는 알고리즘이 많은데 .. 그중에서 우리팀이 선택한 알고리즘은

 

Second-Chance Algorithm이다 

 

 

---

Second-Chance Algorithm

Second-Chance Algorithm은 Clock algorithm이라고도 하는데,  기본적으로 FIFO 구조이지만 참조 비트를 사용해서 참조(접근)이 된 프레임이라면 한번의 살려줄 기회를 부여하는 알고리즘이다.

검색하다가 참조비트가 꺼진 비트를 확인했다면 해당 프레임을 희생자 프레임으로 선정하면 된다.

보통은 원형큐를 이용해서 구현하지만 우리팀은 list를 두번 순회하는 방식으로 구현했다.

Second-Chance Algorithm

 

 

 

 

감사하게도 핀토스에서는 pml4_is_accessed()라는 함수를 제공해준다, 즉 프레임 리스트를 순회하면서 

pml4_is_accessed()를 체크하고 만약에 접근이 되어있다면 해당 접근 비트를 꺼주고 pml4_is_accessed()의 결과가 false 라면

해당하는 프레임을 희생프레임으로 선택해주면된다. 그렇게해서 리스트의 끝까지 희생자를 못 찾았다면 다시한 바뀌 순회서해 접근 비트가 꺼진 프레임을 희생자 프레임으로 선택해주면된다.

 

희생할 프레임을 선정했다면, 해당하는 프레임에 맵핑된 page의 swap_out 함수를 호출해줘서 새로운 page 맵핑을 위해 기존page와 프레임의 맵핑을 해제시켜준다 정상적으로 swap_out 이 되었다면 이제 frame의 정보도 탈탈탈 초기화 시켜준뒤 새로운 프레임인 척 반환해서 do_claim 시켜주면 된다..

---

 

Dirty Page

여기서 약간의 개선을 조금.. 조금더 하자면

만약 어떤 페이지가 읽기만한게 아니라  쓰기까지 되어서 Dirty bit가 on이라면 , 그 페이지를 swap_out 할때는 디스크에 변경 된 내용을 기록 해야하기 때문에 비싼 비용을 지불 해야한다 ..즉. 변경되지 않은 페이지라면 추가적인 I/O 없이 재사용 될 수있지만 Dirty인 경우 추가 작업을 해줘야하기 때문에 VM 시스템들은 더티 페이지 대신 깨끗한 페이지를 내보내는 것이 효율 면에서 좋다. 

해당 내용을 까지 고려를 해서 좀 더 효율을 높혀 볼 수있다, 왜냐면 Pintos가 dirty 비트가 on인지 아닌지 확인하는 함수까지 제공하고 있기 때문 .. ! 좀 더 고쳐보자 ..! 

 

 

 

일단 for 순회를  정직하게 두번 순회하도록 분리했고 첫번째 순회에서는 희생자 페이지 선정에 두가지를 확인한다 먼저 접근 비트가 꺼져있는지 확인하고, 접근 비트가 꺼져있다면 추가로 해당 페이지가 수정되었는지 여부를 확인해서 수정이 안된페이지라면 희생자 페이지로 반환한다

 

만약 첫번째 for 순회에서 희생자 페이지를 못찼았다면 조건을 완화해서 접근 비트가 꺼져있는 페이지를 찾아서 반환하도록 만들어줬다

 

이렇게 한다면 최대한 디스크에 접근을 덜하면서 희생자 프레임을 선정 할 수가 있을 것..?!이다.

 

 

 

그럼  2000