project 3-1. Memory Management
효율적으로 페이지와 프레임을 관리하는 것에 대해 구현할 것이다. 이 말인 즉슨 사용되고 있는 가상/물리 메모리 영역에 대해 추적해야 한다는 것!
먼저 supplemental page table(spt; 보조 페이지 테이블->우리가 구조체 생성해야 함), 그리고 physical frame을 다룰 것이다.
들어가기 앞서 개념 정리를 하고 넘어가겠수다
Pages
VM은 운영체제의 핵심 design인 protection, isolation, sharing을 위해 필수적으로 사용되는 추상화
모든 유저 프로세서는(커널 코드 자체도) 이 가상메모리 환경의 가상주소 상에서 동작하며, 이에 대한 실제 물리주소로의 번역은 MMU 라는 하드웨어가 지원해준다.
커널은 자신의 주소공간에 프로세스별 페이지 테이블을 구성해 놓고, 각 프로세스가 실행될 때마다 CR3 레지스터에 해당 페이지 테이블 주소를 적어줌으로써 MMU가 그 페이지 테이블을 walking할 수 있도록 해준다.
*walking?
페이지 테이블의 엔트리들을 타고타고 들어가서 최하단 페이지 테이블의 PTE(Page table Entry)를 찾아 물리 주소를 알아낸다는 것
페이지 테이블 엔트리에는 '물리 주소'가 적혀야 한다. 하드웨어인 MMU는 가상주소라는 개념을 이해하지 못한다. 단지 그 PTE에 적힌 어떤 값(물리 주소)을 참고해서 자신의 임무를 수행할 뿐이다.
페이지 테이블은 가상 주소 지원을 위한 것!!
페이징 기법
페이징은 주소 공간을 동일 크기의 조각으로 분할하는 것을 말하는데 프로세스의 주소 공간을 가변 크기를 가지는 세그먼트로 나누는 것이 아니라 고정 크기를 가진 페이지로 나누는 것을 의미한다.
가상 메모리에서 이렇게 고정 크기로 나눈 단위를 페이지라고 부르고, 물리 메모리에서도 같은 고정 크기로 나누는데 물리 메모리에서 부르는 단위는 프레임이라고 한다.
이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있는 것이다.
기본적인 원리는 가상 메모리를 고정된 크기로 나누어 페이지를 만들고 해당 페이지를 물리 메모리의 프레임에 매핑시켜주는 것이다.
여기서 해결해야할 것은 공간과 시간 오버헤드를 최소로 하면서 페이징 기법을 완성하는 것이다.
가상 메모리의 페이지를 어떻게 물리 메모리에 올리고 이것들을 어떻게 관리할까?
1. 페이지가 물리 메모리에 올라가야하는 상황이 됐다면 운영체제는 빈 공간 즉, frame 리스트를 유지하고 있어야 하고 이 리스트에서 하나를 선택하여 그 프레임에 페이지를 올리면 된다.
2. 가상 메모리의 각 페이지에 대한 물리 메모리 상의 위치를 기록해둬야하므로 운영체제는 프로세스마다 페이지 테이블이라는 자료구조를 유지한다.
페이지 테이블의 주요 역할은 가상 메모리의 페이지 주소 변환 정보를 저장하는 것이다!
여기서 알아두어야 할 중요한 점은 각 프로세스마다 페이지 테이블이 존재하는 것이고, 페이지 테이블을 통해 각 페이지가 저장된 물리 메모리의 위치가 어디인지 알려준다는 것이다.
Frames
물리 메모리 상의 연속적인 영역으로, 물리 프레임 또는 페이지 프레임이라고도 불린다.
페이지와 동일하게 프레임은 페이지 사이즈여야하고 페이지 크기에 정렬되어 있어야 한다. 그러므로 64비트 물리주소는 아래 그림처럼 프레임 넘버와 프레임 오프셋(offset)으로 나누어질 수 있다.
*offset?
우리가 페이지 내에서 원하는 바이트의 위치
12 11 0
+-----------------------+-----------+
| Frame Number | Offset |
+-----------------------+-----------+
Physical Address보조 페이지 테이블
보조 페이지 테이블에서 폴트가 발생한 페이지를 찾는다.
만일 메모리 참조가 유효하다면, 보조 페이지 엔트리를 사용해서 데이터가 들어갈 페이지를 찾아야 한다. 페이지는 파일 시스템에 있거나, 스왑 슬롯에 있거나, 또는 단순히 0으로만 이루어져야 할 수도 있다.
Code
struct page {
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
union {
struct uninit_page uninit;
struct anon_page anon;
struct file_page file;
#ifdef EFILESYS
struct page_cache page_cache;
#endif
};
};anonymous page -> 따라 들어가보니 비어있음ㅋ .. MM 다음 파트가 Anonymous Page라 그 때 알아야 할 개념인가
struct anon_page {
};페이지는 uninit page나 anon page, file page가 될 수 있다는 것을 의미하나보다.
페이지는 swaping in, swaping out이나 destroy와 같은 액션들을 취할 수 있고 각각 타입의 페이지들은 어떤 것들을 요구 받는지에 따라 다른 작업을 수행한다.
하나의 방법으로 각 함수의 switch-case문을 사용하여 각각의 케이스들을 처리하는 것.
# 페이지들이 작업하는 것과 관련된 구조체
struct page_operations {
bool (*swap_in) (struct page *, void *);
bool (*swap_out) (struct page *);
void (*destroy) (struct page *);
enum vm_type type;
};각각의 구조체들은 함수 포인터를 담고 있는 함수 테이블이다.
pintos는 가상 주소와 물리 주소의 매핑을 관리하는 페이지 테이블인 pml4가 있다. 하지만 이것으로는 page fault와 resource management를 처리하는데 충분하지 않다. 그래서! 우리는 프로젝트 3의 첫 번째 과제로 supplemental page table(보조 페이지 테이블)을 구현하는 것이 목표다.
spt 어딨는지 찾아보자.
/* Representation of current process's memory space.
* We don't want to force you to obey any specific design for this struct.
* All designs up to you for this. */
struct supplemental_page_table {
};
# 보조 페이지 테이블 초기화
/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
}강요는 안하지만 모든 결정이 우리들한테 달려있다는 저 어마무시한 주석.. ;_;
결론은 우리가 다 채워야한다..~
정확히 spt가 뭘까?
페이지들에 대해 추가적인 데이터로 페이지 테이블을 보완하는 것이다. 사용 용도는 *page fault 상황에서 커널은 spt에 fault된 virtual page를 찾는다. 또한, 페이지를 다 사용한 후 종료될 때 메모리 할당을 해제하기 위해 필요하다.
*page fault?
cpu에서 요청한 정보가 메인 메모리 내에 캐시되어 있지 않을 때를 말한다.
cpu의 cr3 레지스터에 저장되며 mmu에 의해 traverse(순회)되는 pml4 table은 supplemental page table과는 무관하게 virtual address에서 physical address mapping을 지원한다.
supplemental page table은 process별로 생성되는 별도의 구조체로써, 동일하게 virtual address와 physical address간 mapping을 지원하지만 struct page와 struct frame 구조체들을 이용하여 기존 page table(pml4t)이 담지 못하는 정보들을 추가적으로 저장하기 위해 사용된다.
(ex. evicted page. mmaped page, etc...)
= 이름 그대로 보조 테이블 그 잡채
- 구현 전 pintos memory layout
기존 pintos의 가상 주소 공간 초기화 과정은 디스크로부터 ELF이미지의 세그먼트를 물리메로리로 읽어들인다. (load_segment()로 data, code 세그먼트를 읽고, setup_stack()로 스택에 물리페이지를 할당)
이는 물리 메모리의 낭비를 초래하기 때문에 물리 메모리 할당 대신 가상 페이지마다 spt를 통해 적재할 정보들만 관리하도록 구현해야 한다.
- 구현 후 pintos virtual memory
hash의 등장....
그게 뭔데...............? -> 프로세스가 요청한 페이지들에 대해서만!!! physical frame을 할당하기 위해서 해시 테이블 자료구조 사용
# hash 구조체
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 table은 (key, value)로 데이터를 저장하는 자료구조이다. 고로 빠르게 데이터를 검색할 수 있음
이유는.. 내부적으로 배열(bucket or slot)을 사용하여 데이터를 저장하기 때문이다.
해시 테이블은 각각의 key값에 해시 함수를 적용해 배열의 고유한 인덱스를 생성하고, 이 인덱스를 활용하여 value를 저장하거나 검색한다. 여기서 실제 값이 저장되는 장소를 bucket or slot이라고 한다.
핀토스 가상 메모리 그림처럼 해시 테이블의 인덱스 값들이 실제 주소를 가지고 있는 버킷을 찾는다.
이런 hash table이 어디서 사용될까?
위에서 설명했던 보조 페이지 테이블 spt에서 사용한다. spt 내 해시 테이블을 통해 요청되는 주소들을 넣어야 한다는 것이고, spt를 init하는 함수에서 해시 테이블도 init을 해야한다.
hash_init()을 찾아보자
/* Initializes hash table H to compute hash values using HASH and
compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init (struct hash *h,
hash_hash_func *hash, hash_less_func *less, void *aux) {
h->elem_cnt = 0;
h->bucket_cnt = 4;
h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
h->hash = hash;
h->less = less;
h->aux = aux;
if (h->buckets != NULL) {
hash_clear (h, NULL);
return true;
} else
return false;
}hash_init()은 파라미터로 받는 함수들로 해시 테이블의 해시들을 초기화한다. 실제 값이 저장되는 장소를 나타낸 buckets을 보면 malloc()을 호출해서 메모리를 할당받고, 만약 실패했다면 메모리에 할당되지 않는다.(if문)
여기서 또 구현해야되는거 등장~
hash_hash_func *hash - 주어진 aux 데이터에서 해시 요소에 대한 해시 값을 계산하여 반환
hash_less_func \*less - 해시 요소들 비교
추가로 깃북에서는
/* Find VA from spt and return page. On error, return NULL. */
# 인자로 받은 va에 해당하는 page num을 검색하여 page num을 추출하는 함수
struct page *spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
struct page *page = NULL;
/* TODO: Fill this function. */
return page;
}&
/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
struct page *page UNUSED) {
int succ = false;
/* TODO: Fill this function. */
return succ;
}도 구현하라고 써있다...
지금까지 page table과 관련된 코드들을 살펴봤다면.. 이제는 물리 주소와 매핑할 때 필요한 frame을 수정해야 한다. 커널의 가상 주소를 나타내는 kva와 매핑될 page 구조체. 이렇게 두 개만 필드로 있지만 뭔가를 더 추가해야 할지도..ㅜ
/* The representation of "frame" */
struct frame {
void *kva; // 커널의 가상 주소
struct page *page; // page 구조체
};frame과 관련된 숨어있는 TODO를 찾아보자
/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
struct page *page = NULL;
/* TODO: Fill this function */
return vm_do_claim_page (page);
}
/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page (struct page *page) {
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. */
return swap_in (page, frame->kva);
}
/* palloc() and get frame. If there is no available page, evict the page
* and return it. This always return valid address. That is, if the user pool
* memory is full, this function evicts the frame to get the available memory
* space.*/
static struct frame *vm_get_frame (void) {
struct frame *frame = NULL;
/* TODO: Fill this function. */
ASSERT (frame != NULL);
ASSERT (frame->page == NULL);
return frame;
}-
vm_get_frame (void)
palloc_get_page() 함수 호출을 통해 유저풀로부터 새로운 물리 프레임을 할당 받는 함수. 유저풀로부터 페이지를 받고 프레임을 할당 받았을 때, 멤버들을 초기화하고 유효한 주소를 리턴한다. 즉 이 함수를 통해 모든 유저 공간 페이지들을 할당 받게 된다. 만약 유저풀 메모리가 가득 차서 가용한 페이지가 없다면, 이 함수는 가용한 메모리 공간을 얻기 위해 할당되어 있는 프레임을 제거한다. -
vm_do_claim_page(void)
*claim: 물리적인 프레임 또는 페이지를 할당하는 것
먼저, vm_get_frame() 함수를 호출하여 프레임을 얻는다.(이미 템플릿에서 수행) 그런 다음 MMU(Memory Management Unit)를 설정해야 한다. 다시 말해, 가상 주소에서 물리 주소로의 매핑을 페이지 테이블에 추가해야 한다. return값은 작업이 성공했는지 여부를 나타내어야 한다. -
vm_claim_page(void)
페이지를 할당하려면 va(가상 주소)를 클레임한다. 먼저 페이지를 얻어야하며, 그런 다음 해당 페이지를 사용하여 vm_do_claim_page() 함수를 호출해야 한다.
또 추가로 나올수도 있겠지만 일단은 여기까지 우리가 메모리 매니지먼트에서 구현해야하는 부분인 것 같다.
화이팅
