Pintos project 3 간단하게 구조체 정리
pages
: virtual page -> 연속된 영역의 virtual memory, 4KB.
page aligned 되어야 함
64bit page table -> pml4
12 bit는 Offset, 나머지 52 bit는 페이지 테이블의 인덱스
struct page {
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
/* Your implementation */
/* Per-type data are binded into the union.
* Each function automatically detects the current union */
union {
struct uninit_page uninit;
struct anon_page anon;
struct file_page file;
#ifdef EFILESYS
struct page_cache page_cache;
#endif
};
};63 48 47 39 38 30 29 21 20 12 11 0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend | Page-Map | Page-Directory | Page-directory | Page-Table | Page |
| | Level-4 Offset | Pointer | Offset | Offset | Offset |
+-------------+----------------+----------------+----------------+-------------+------------+
| | | | | |
+------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
Virtual Address해당 구조체가 union 멤버를 포함하니 3가지 유형의 페이지 표현이 가능하다.
union⇒ 여러 멤버를 가질 수 있지만 한 시점에 하나의 멤버만 값을 가질 수 있는 특별한 자료형 - 여러 멤버가 동일한 메모리 영역을 공유한다는 의미
uninit_page: 초기화되지 않은 페이지를 위한 정보를 담고 있음annon_page: 익명 페이지는 파일 시스템에 저장되지 않고 메모리에만 존재하는 페이지
→ 익명 페이지의 관리에 필요한 정보를 담고 있을 것 - swap_out될 때 디스크의 어느 위치에 저장될지에 대한 정보file_page: 파일 시스템에 저장된 페이지에 관한 정보 - 특정 파일의 일부를 메모리에 매핑한 페이지page_cache: 파일 시스템의 데이터를 캐싱하기 위한 메모리 영역 → 캐싱된 데이터를 관리하는 데 필요한 정보
- user page set:
KERN_BASE로 정의된 주소보다 낮은 주소 공간에 존재하는 사용자 페이지들 - 각 프로세스는 자신만의 독립된 user page set을 가짐. 이를 통해 자신의 코드, 데이터, 힙, 스택 등을 관리- kernel page set:
전역적으로 관리되는 커널 페이지들의 집합 → 어떤 쓰레드나 프로세스가 실행 중이든 상관없이 동일한 위치를 유지 → 커널 주소 공간은 모든 프로세스에 공통적으로 매핑되어 있음 - 시스템 콜이나 인터럽트 처리 등의 커널 작업을 위해 사용됨
사용자 프로세스는 오직 자신의 사용자 프로세스 페이지에만 접근 가능 -> 직접적으로 커널 페이지에 접근하는 것은 허용되지 않음
Frames
: 물리 프레임, 페이지 프레임 -> 물리 메모리 상의 연속적인 영역
프레임도 동일하게 페이즈 사이즈여야 하고, 페이지 크기에 정렬되어 있어야 함
12 11 0
+-----------------------+-----------+
| Frame Number | Offset |
+-----------------------+-----------+
Physical Address
- pintos에서는) kernel virtual memory를 physical memory에 직접적으로 매핑시키는 방법을 제공한다.
KERN_BASE: 커널 가상 메모리의 시작 주소KERN_BASE에 위치한 가상 주소는 물리 주소 0에 매핑KERN_BASE+0x1234에 위치한 가상 주소는 물리 주소 0x1234에 매핑된다.- 커널 가상 메모리의 첫 번째 페이지가 물리 메모리의 첫 번째 프레임에 매핑
- 두 번째 페이지는 두 번째 프레임에 매핑되는 방식
page tables
: cpu가 가상 주소를 물리 주소로, 즉 페이지를 프레임으로 변환하기 위해 사용하는 자료 구조
⇒ page table은 Page number를 frame number로 바꿔줌
⇒ frame number + offset을 합치면 우측의 physical address가 된다
+----------+
.--------------->|Page Table|-----------.
/ +----------+ |
| 12 11 0 V 12 11 0
+---------+----+ +---------+----+
| Page Nr | Ofs| |Frame Nr | Ofs|
+---------+----+ +---------+----+
Virt Addr | Phys Addr ^
\_______________________________________/
swap slots
스왑 파티션 내의 디스크 공간에 있는 페이지 크기의 영역
- 운영체제가 메모리 관리를 위해 사용하는 하드 디스크의 특정 영역
- 운영체제는 메모리가 부족할 때 일부 데이터를 임시로 하드 디스크의 swap 영역으로 옮겨 놓음. 데이터는 Swap slot이라 불리는 단위로 관리된다.
- swap slot의 크기는 페이지 사이즈와 동일 → 4KB = 운영체제가 메모리를 페이지 단위로 관리하기 때문
핀토스 프로젝트 3에서 구현해야 할 3가지의 자료 구조
supplemental page table
: Page fault 발생 시 page fault에 대응할 수 있도록 필요한 정보 제공
1. page fault handler
2. process termination handler
-> 각각의 페이지에 대해서 데이터가 존재하는 곳 (frame, disk, swap 중에 어디에 존재하는지) 확인할 수 있게
frame table
: 물리 메모리 공간이 부족할 경우 디스크로 쫓아낼 (eviction) frame을 효율적으로 결정
eviction 과정
- evict할 프레임 선택
- 페이지 테이블 참조 제거
- 필요한 경우 파일 시스템이나 스왑 영역에 페이지 쓰기
swap table
: 디스크에 임시 저장된 frame들의 공간인 swap slot의 사용 현황을 추적할 수 있게
Memory Management 구현하기
supplemental page table 구현
pintos에서는 pml4 page table로 가상 메모리와 물리적 메모리를 매핑하지만, page fault와 lazy-loading 등 page에 대한 추가 정보를 저장할 수 있는 spt가 필요하다.
struct supplemental_page_table {
struct hash spt_hash;
};struct page {
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
/* Your implementation */
struct hash_elem hash_elem;
bool writable;
/* Per-type data are binded into the union.
* Each function automatically detects the current union */
union {
struct uninit_page uninit;
struct anon_page anon;
struct file_page file;
#ifdef EFILESYS
struct page_cache page_cache;
#endif
};
};해쉬 테이블을 사용해서 page fault와 lazy loading에 필요한 정보를 효율적으로 빠르게 접근할 수 있도록 ->
hash table
평균적으로 O(1)의 시간 복잡도로 데이터 검색
해시 함수가 각 키에 대한 고유한 index 생성
- index: 배열의 특정 위치
- bucket: 실제 값이 저장되는 장소
/* Hash table. */
struct hash {
size_t elem_cnt; /* Number of elements in table. */
size_t bucket_cnt; /* Number of buckets, a power of 2. */
struct list *buckets; /* Array of `bucket_cnt' lists. */
hash_hash_func *hash; /* Hash function. */
hash_less_func *less; /* Comparison function. */
void *aux; /* Auxiliary data for `hash' and `less'. */
};-
hash_hash_func: 주어진 (hash_elem *e)에 대해 해시 값 계산하고 return
→ 해쉬 버킷을 결정하는데 사용 -
hash_less_func: 두 해쉬 요소 a, b를 비교해서 a < b이면 return true, 그렇지 않으면 return false→ 해쉬 테이블 요소 정렬, 검색하는데 사용됨
unsigned page_hash (const struct hash_elem *p_, void *aux UNUSED){ const struct page *p = hash_entry(p_, struct page, hash_elem); return hash_bytes(&p->va, sizeof(p->va)); //p->va의 해시값 계산. } bool page_less (const struct hash_elem *p_, void *aux UNUSED){ const struct page *a = hash_entry(p_, struct page, hash_elem); const struct page *b = hash_entry(p_, struct page, hash_elem); return a->va < b->va; }
hash_bytes(): 해쉬 테이블에서 사용되는 해쉬 함수의 역할 → 주어진 데이터 (va)를 받아 고정된 크기의 해쉬 값을 return → 해쉬 값은 데이터를 해쉬 테이블의 버켓 중 하나에 매핑하는데 사용
→ 각 데이터는 해쉬 값에 따라 특정 버켓에 할당
supplemental_page_table_init
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
hash_init(&spt->spt_hash, page_hash, page_less, NULL);
}
spt 초기화하는 함수 -> __do_fork, process_create_initd 함수에서 호출된다.
spt_find_page
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
// struct page *page = NULL;
/* TODO: Fill this function. */
//page의 VA와 spt의 VA가 일치하는 경우
struct page *temp_page = (struct page *)malloc(sizeof(struct page));
struct hash_elem *e;
temp_page->va = pg_round_down(va); //주어진 가상 주소 va를 포함하는 페이지의 시작 주소 return
//주어진 주소를 페이지 크기 단위로 내림하여 해당 페이지의 시작 주소 구함
e = hash_find(&spt->spt_hash, &temp_page->hash_elem); //spt에서 hash값을 활용하여 페이지를 찾음
free(temp_page);
//일치하는 페이지를 찾았으면 해당 페이지 return
if (e != NULL) {
return hash_entry(e, struct page, hash_elem);
}
else {
return NULL; //해당 페이지를 찾지 못하는 경우
}
}spt에서 가상 주소 va와 일치하는 페이지를 찾아서 반환한다.
더미 페이지, 임시 페이지 temp_page를 만들고
va를 pg_round_down()을 이용해서 페이지 경계로 정렬된 시작 주소로 설정한다. - 정확한 페이지의 시작 주소
궁금증 - pg_round_down
pg_round_down(): 주어진 가상 주소를 해당 페이지의 시작 주소로 내림 처리
→ 페이지는 보통 4KB (0x1000 byte)
⇒ 예를 들어서 가상 주소가 0x1234인 경우 이 주소가 포함된 페이지의 시작 주소는 0x1000이다.
페이지 테이블은 가상 주소를 물리 주소로 변환되는데 사용된다.
→ 가상 주소는 페이지 단위로 관리
→ 각 페이지는 페이지 테이블 엔트리로 매핑된다.만약
temp_page->va = va로 설정하면, 주어진 가상 주소va가 페이지의 시작 주소가 아닐 때 정확한 페이지를 찾지 못할 수 있다. 예를 들어, 페이지 크기가 4KB일 때, 가상 주소0x1234와0x1000은 같은 페이지에 속하지만, 서로 다른 주소다.
그리고 hash_find 함수 를 이용해서 spt_hash 해시 테이블에서 해당 가상 주소를 가진 hash_elem을 찾고 이를 hash_entry를 이용해서 page를 return한다.
va를 통해서page를 얻어내기 위해서
dummy page를 생성.
->hash_find함수를 통해 실제 페이지를 찾기 위한 일종의 검색 키로 활용하기 위해서
- 먼저
temp_page->hash_elem에 대응하는 해쉬 버킷을 찾고
- 받은 버킷 내에서 주어진
temp_page->hash_elem와 일치하는 실제hash_elem요소를 찾는다.
- 이를
hash_entry를 이용해서page로 return 한다.
hash_find
struct hash_elem *
hash_find (struct hash *h, struct hash_elem *e) {
return find_elem (h, find_bucket (h, e), e);
}find_bucket 함수를 활용하여 주어진 해시 요소e에 대응하는 해시 버킷을 찾음.
그 후 find_elem 함수를 호출해서 버킷 내에서 주어진 hash_elem e와 일치하는 실제 요소를 찾는다.
spt_insert_page
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
struct page *page UNUSED) {
return insert_page(&spt->spt_hash, page);
}
static bool insert_page(struct hash *hash, struct page *page){
if (!hash_insert(hash, &page->hash_elem)) {
return true;
}
else {
return false;
}
}spt에 page를 insert하는 함수.
해당 페이지가 이미 존재하지 않으면 삽입하고 존재한다면 삽입하지 않는다.
frame management
struct frame {
void *kva; /*커널 virtual address*/
struct page *page; /*페이지 구조*/
/*---------added for Project 3-------*/
struct list_elem frame_elem;
};
frame 도 list로 관리해주기 위해서 frame_elem 필드를 만들어서 frame 구조체에 추가해주었다.
vm.h에 frame_elem관리를 위한 frame_table list를 선언해준다.
static struct list frame_table;
static struct list_elem *ft_start;ft_start는 그냥 frame_table 리스트의 순회 시작점을 가리키는 포인터이다.
vm_get_frame
static struct frame *
vm_get_frame (void) {
/* TODO: Fill this function. */
struct frame *frame = (struct frame *)malloc(sizeof(struct frame));
frame->kva = palloc_get_page(PAL_USER); //사용자 풀에서 메모리 할당을 위해 PAL_USER
if (frame == NULL || frame->kva == NULL) {
PANIC("TODO");
return NULL;
// frame = vm_evict_frame();
// frame->page = NULL;
// return frame;
}
list_push_back(&frame_table, &frame->frame_elem);
frame->page = NULL; //물리 프레임을 할당받고 아직 매핑된 가상 페이지는 없으니까 NULL로 초기 설정을 해준다.
ASSERT(frame != NULL);
ASSERT(frame->page == NULL);
return frame;
}
새로운 물리 프레임을 할당받고 초기화하는 함수
그리고 frame_table리스트에 추가해준다.
물리 프레임을 palloc_get_page(PAL_USER)로 할당받는다.
그리고 frame->page = NULL
물리 프레임을 할당받고 아직 매핑된 가상 페이지는 없으니까 NULL로 초기화해준다.
아마도 swap 과제할 때 따로 페이지 할당에 실패한 경우
vm_evict_frame()함수를 사용해서 수정할 예정
vm_evict_frame (void) {
struct frame *victim UNUSED = vm_get_victim ();
swap_out(victim->page);
return victim;
}victim 페이지 프레임을 선택하고, swap_out 함수를 통해서 해당 프레임을 디스크로 이동시킨다.
vm_get_victim(): swap out할 victim frame을 선택하는 함수
static struct frame *
vm_get_victim (void) {
struct frame *victim = NULL;
/* TODO: The policy for eviction is up to you. */
struct thread *cur = thread_current();
struct list_elem *frame_e;
struct list_elem *e = ft_start;
for (frame_e = list_begin(&frame_table); frame_e != list_end(&frame_table); frame_e = list_next(frame_e)){
victim = list_entry(frame_e, struct frame, frame_elem);
//현재 쓰레드의 페이지 테이블에서 victim 페이지가 접근된 페이지인지 확인
if (pml4_is_accessed(cur->pml4, victim->page->va))
//만약 접근된 페이지라면 접근 플래그를 0으로 설정.
//다음번 탐색에서 victim으로 선택될 수 있도록 한다.
pml4_set_accessed(cur->pml4, victim->page->va, 0);
else
return victim;
}
return victim;
}
- 반복문을 통해서
frame_table순회하면서 각 frame을 검사한다.pml4_is_accessed를 통해 해당 페이지가 접근되었는지 확인 - accessed 비트를 확인해서 해당 페이지가 최근에 접근되었는지 확인pml4_set_accessed: 해당 페이지의 accessed bit를 설정 -> 0으로 설정하여 해당 페이지가 다음 순회 때는 victim으로 설정될 수 있도록 함
vm_do_claim_page
static bool
vm_do_claim_page (struct page *page) {
if (!page || page->frame) {
return false;
}
struct frame *frame = vm_get_frame ();
/* Set links */
frame->page = page;
page->frame = frame;
/* TODO: Insert page table entry to map page's VA to frame's PA. */
struct thread *cur = thread_current();
pml4_set_page(cur->pml4, page->va, frame->kva, page->writable);
//swap-in을 통해서 디스크의 스왑 영역에서 물리 메모리 프레임으로 load -> 스왑 작업 성공 여부 boolean 리턴
return swap_in(page, frame->kva);
}사용 가능한 물리 frame을 vm_get_frame()을 통해서 할당 받는다.
그리고 pml4_set_page를 이용해서 pml4 페이지 테이블에 새로운 PTE를 삽입한다.
-> page의 va, frame의 kva 가상 주소와 물리 주소를 매핑한다.
그리고 swap_in을 통해서 디스크의 swap 영역에서 물리 메모리로 load한다. => swap 작업의 성공 여부를 boolean으로 return하게 된다.
vm_claim_page
bool
vm_claim_page (void *va UNUSED) {
struct page *page = NULL;
struct thread *cur = thread_current();
//va에 해당하는 페이지를 현재 쓰레드의 spt에서 찾음
page = spt_find_page(&cur->spt, va);
if (page == NULL) {
return false;
}
return vm_do_claim_page (page);
}
spt에서 va에 해당하는 페이지를 찾아서 가져온 다음, vm_do_claim_page(page) 를 리턴한다.
=> 물리 프레임과 매핑을 claim하는 것이다.
