2022-06-13 (Mon)
오늘은 저번 주에 시도했다가 실패했던 부분에 대한 구현을 다시 시도해보았다.
supplemental_page_table
PintOS에서는 Supplemental Page Table이라는 개념이 등장한다. 설계 과정에서 발생하는 한계로 인해, 모든 정보를 기존의 Page Table이 갖고 있지는 못하기 때문이라고 한다. 따라서 Supplemental Page Table이 필요하고, page fault나 resource management를 처리하는데 이 Supplemental Page Table이 쓰이게 된다.
그렇다면 Supplemental Page Table을 어떻게 설계해주면 될까? 깃북에서는, 원하는 자료구조를 하나 선택해서 자유롭게 디자인해주면 된다고 하였다. 하지만 리스트나 배열의 경우 퍼포먼스적인 측면에서 아쉽다는 내용이 있었어서, 사실상 좋은 선택지는 비트맵과 해시테이블 2가지였다. 그 중, 우리 조는 해시 테이블을 사용하기로 하였다.
해시테이블은 위와 같이 쉬운코드 영상을 보며 이해해보았다.
PintOS에서는 Open addressing 대신 Separate Chaining 방식을 택하고 있는데, 간단히 설명하자면 key는 다른데 hash가 같은 'hash collision'이 발생하는 경우를 대비해, bucket을 linked list로 구현해서 동일한 해쉬 값을 가지는 여러 자료들을 이어주는 방식 이라고 생각하면 된다.
따라서, 위와 같이 hash table을 활용해 Supplemental Page Table을 간단히 설계해주었다. 그리고, 이에 맞추어 해시테이블에 page가 들어갈 수 있도록 page 구조체에는 hash_elem 필드를 추가해주었다.
Supplemental Page Table을 해쉬테이블 자료구조를 활용해 디자인 해준 후, 깃북의 안내에 따라 Supplemental Page Table을 활용하기 위해 다음의 3가지 함수를 구현해주었다.
supplemental_page_table_init()
spt_find_page()
spt_insert_page()
Frame Management
또한, physical memory 를 관리하기 위해 page frame (physical frame) 이 필요하며, 그에 대한 구조체로 struct frame이 PintOS 소스코드에 주어져있는 상태였다. 
깃북에서는 frame management 인터페이스를 구현하는 과정에서 추가적으로 필드를 자유롭게 설정해준다고 하였다. 따라서 우리는 frame table을 doubly-linked-list 로 구현하기로 하고, 각 frame 이 해당 리스트에 들어갈 수 있도록 f_elem을 새로운 필드로 추가해주었다. (kva와 page는 기존에 주어져있던 필드)
frame 구조체에 필드를 추가해준 후, frame을 활용하기 위해 이번에도 3가지 함수를 구현해주었다. 
일단 각 함수에 대해 공부하고 일단 페어프로그래밍 방식으로 구현해보았는데, 이에 대해서는 다음 글에서 다뤄보도록 하겠다:)
정신없는 시간을 보내며 TIL 작성이 자꾸 밀리는데, 그래도 바쁜 와중에 하나씩이라도 쓰려고 노력하는 것에 의의를 두고 싶다. 열심히 쓰자 ! 🥲
