벌써 어느덧 4개의 pintos 프로젝트 중 3번째인 Virtual Memory에 도착했다. Project 3. Virtual Memory는 말 그대로 가상 메모리를 구현하는 것이다.
이전에는 가상 메모리가 없었나요..?
이전에 Project 2에서도 pml4 라는 multi level page table을 사용하였고, page table은 가상 메모리를 일정 크기로 나눈 페이지들을 관리하는 자료구조이므로 가상 메모리가 구현되어있는 상태이지 않나? 라는 생각을 했다.
project 3를 구현하기 전까지의 pintos의 가상 메모리는 가상 메모리 시스템에서 필요로 하는 기능들을 정상적으로 갖추고 있지 않기 때문에, pml4라는 페이지 테이블을 관리하는 자료구조만 가지고 있다고 해서 가상 메모리를 사용하고 있다고 말하기는 어렵다.
여기서 말하는 가상 메모리에서 필요로하는 기능에는 어떤 것들이 있을까?
가상 메모리의 필수 기능
- 메모리 보호
한 프로세스가 다른 프로세스의 메모리를 방해하거나 액세스 할 수 없어야 한다. - Demand Paging
모든 page를 메모리에 한번에 적재하는 것이 아니라, 필요할 때 page를 그때 그때 메모리에 적재할 수 있어야 한다. - 메모리 공유
프로세스가 메모리 리소스를 효율적으로 공유할 수 있어야 한다.
여기에 더해서, 가상 메모리는 페이지 스와핑 같은 기능을 구현해서 프로세스가 물리 메모리 크기 만큼의 메모리를 사용하고 있다고 느낄 수 있도록 해야 한다.
project 3이전의 pintos에서는 page fault가 발생하면 exit(-1)로 page fault를 핸들링하지 않고, 프로세스를 종료시켰다. 이로 인해 당연히 demand paging 같은 메커니즘이 적용될 수 없었고, 메모리 자원을 효율적으로 사용할 수 없는 상태였으므로 가상 메모리를 사용하고 있다고 말하기 어려운 것이다.
Supplemental Page Table(SPT)
처음 Project 3를 구현하기 시작하면, SPT라는 자료구조를 먼저 만들어야한다. 그런데 이것을 이해하는게 도통 쉬운일이 아니었다. SPT는 계속해서 사용되지만, 사용되는 예시를 하나만 들어서 이해해보자.
앞서 우리는 virtual memory를 구현하기 위해서는 demand paging을 만족해야 한다고 했었다. demand paging을 구현하기 위해서는 그때 그때 필요한 page를 요청받게 되고, 이는 page fault가 발생함을 의미한다.
page fault는 해당 page에 대응되는 frame이 물리 메모리에 없기 때문에 발생하고, 그렇다면 page fault를 핸들링 하기 위해서는 해당 page에 대응되는 데이터를 담고 있는 자료구조가 필요하다는 것을 의미한다. 이 외에도 spt는 다양한 보조 데이터들을 담게 된다.
SPT를 구현하는데 권장 되는 자료구조는 크게 array, hash table, bitmap 으로 3가지 정도가 있었다. 이 중에서 우리 조는 hash table을 채택하였다.
Hash Table 채택 이유?
3가지 자료 구조 중 hash table을 선택한 이유는 Demand Paging의 단점과도 연결된다. 이전에는 파일 전체를 실행하지 않더라도 메모리에 적재 시켜두고 사용하였다.
그러나 Demand Paging의 경우에는 해당 page가 필요할때마다 page fault를 발생시키고, 이를 핸들링해서 메모리에 적재 시켜주는 과정이 추가된다.
그렇기 때문에, 가능한 빠르게 page에 대응되는 데이터를 찾아서 메모리에 적재시켜주는것이 중요하다고 생각했고 검색 시간 복잡도가 가장 뛰어난 Hash Table을 채택하게 되었다.
Hash Table의 단점은 해시 충돌과 구현 복잡성이 있지만, 우리에게 주어진 pintos 코드에서는 bucket 이라는 list로 체이닝 방식을 사용해서 해시 충돌을 해결하고 있었고, 구현 복잡성은 이미 구현되어 있는 hash 함수들이 어느정도 해결해주었기 때문에 크게 문제가 되지 않는다고 생각했다.
