WIL project 3 Virtual Memory(2)

Demanding Paging

Supplement Page Table

📒 Supplement Page Table 란?

• supplement page table은 각 프로세스마다 보조 데이터를 담고 있는 자료구조
• 각각의 페이지에 대해서 데이터가 존재하는 곳(frame, disk, swap 중에 어디에 존재하는지)에 정보 보유
• 위에 데이터에 상응하는 커널 가상주소를 가리키는 포인터 정보 등을 가지고 있다

📒 Supplement Page Table 사용 목적

• 보조 페이지 테이블은 최소환 두 가지 목적으로 사용
  • 페이지 폴트가 발생 했을 때 그곳에 어떤 데이터가 있었어야 했는지를 알아내기 위해 커널은 보조 페이지 테이블에서 폴트가 발생한 가상 페이지를 탐색
  • 커널이 프로세스가 종료될 때 어떤 자원을 해제(free)할지 고르기 위해서 보조 페이지 테이블을 조사

📒 Supplement Page Table 자료 구조 종류

• Arrays : 가장 간단하게 구현이 가능하지만, 메모리를 낭비하는 밀도가 낮다
• Lists : 꽤나 심플한 편이지만 리스트를 순회하는데 시간을 많이 소모한다
• Bitmaps : true 또는 false가 될 수 있는 비트 배열, 동일한 리소스 집합에서 사용량을 추적할 때 유용
• Hash Tabbles : key-value 1 대 1 매칭 구조이기 때문에 삽입, 삭제, 검색 시간복잡도가 O(1)을 가진다. 하지만 순서를 보장하지 않고, 같은 인덱스에 모든 키값과 데이터가 저장되어(전부 충돌한 경우) O(n)의 시간 복잡도를 가진다.

📌 Supplement Page Table 선언

../thread.h
struct thread {
	/* Owned by thread.c. */
	'
    '
#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
#endif

	'
    '
};

📌 Supplement Page Table 자료 구조 선언 및 초기화

• supplemental_page_table 구조체 안에 spt를 관리할 hash 구초제 선언

../vm.h
/* supplemental_page_table 구조체 안에 hash 구조체 선언 */ 
struct supplemental_page_table {
	struct hash hash;  
};

• page 구조체 안에 쓰기 가능 여부 확인용 writable선언
• hash 자료구조의 elem을 선언

../vm.h
struct page {
	'
    '
    
	/* Your implementation */
	bool writable;						// project 3 Virtual Memory 추가
	struct hash_elem hash_elem;			// project 3 Virtual Memory 추가
	'
    '
	};
};

• supplemental_page_table을 초기화 시킬 때에 hash 자료구조로 init을 해줌

../vm.h
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->hash,page_hash,page_less, NULL);
}