08:45 입실
해시 테이블 보충 학습하고,
pintos project2 재통과 목표로 구현!
해시 테이블
해시 충돌 해결
체이닝
버킷에 헤드 노드
충돌이 발생하면 링크드 리스트 맨 앞에 값을 추가하는 방식
왜 앞 쪽에 추가하나?
뒤 쪽에 추가하면 링크드 리스트를 순회하면서 맨 마지막 노드를 찾아야 됨.
앞 쪽에 추가하면 O(1)으로 바로 추가 가능.
정렬된 체이닝의 장점
삽입 시 비용이 들어가나, 검색이 빨라짐(이진 탐색도 가능)
개방 주소법
개방 주소법 구현 방법
1. 선형 조사 (Linear Probing) : 클러스터링 발생으로 성능 저하
2. 이차 조사 (Quadratic Probing)
3. 이중 해싱 (Double Hashing) : 다른 해시 함수로 2차 해싱
해시 함수 아이디어
- Mod
- Midsquare: 제곱한 다음, 중간에 위치한 숫자들을 해시 값으로 사용
- Folding: 입력 값을 여러 부분으로 나누고, 이 부분들을 서로 더하거나 다른 방식으로 조합하여 해시 값을 생성
해시 함수는 정해진 게 아니라 작성자가 디자인할 수 있음.
Pintos
가상 메모리는 진짜 어렵다.
테이블 초기화 후 일부 코드 구현했지만 문제 발생해서 롤백
매크로 미인식 오류 해결
/* Returns a hash value for page p. */
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);
}
/* Returns true if page a precedes page b. */
bool
page_less (const struct hash_elem *a_,
const struct hash_elem *b_, void *aux UNUSED) {
const struct page *a = hash_entry (a_, struct page, hash_elem);
const struct page *b = hash_entry (b_, struct page, hash_elem);
return a->va < b->va;
}hash_entry가 계속 인식되지 않는 문제 발생
page 구조체에 hash_elem 멤버 넣어서 해결
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;
/* 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
};
};init 구현
/* Returns a hash value for page p. */
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);
}
/* Returns true if page a precedes page b. */
bool
page_less (const struct hash_elem *a_,
const struct hash_elem *b_, void *aux UNUSED) {
const struct page *a = hash_entry (a_, struct page, hash_elem);
const struct page *b = hash_entry (b_, struct page, hash_elem);
return a->va < b->va;
}
/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
hash_init(&spt->pages, page_hash, page_less, NULL);
}find & insert 구현
/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
struct page *page = NULL;
/* TODO: Fill this function. */
struct page temp_page;
temp_page.va = va;
struct hash_elem *e = hash_find(&spt->pages, &temp_page.hash_elem);
if (e != NULL) {
page = hash_entry(e, struct page, hash_elem);
}
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. */
struct hash_elem *prev_elem = hash_insert(&spt->pages, &page->hash_elem);
if (prev_elem == NULL) {
succ = true;
}
return succ;
}페이지 구조체 vs 프레임 구조체
페이지 구조체
- 연산
- 가상 주소
- 프레임
- 해시 원소
프레임 구조체
- kva
- 페이지
vm_claim과 vm_do_claim 차이
vm_claim으로 페이지를 가상 메모리에 연결
vm_do_claim으로 실제 물리 메모리를 할당
메모리 관리 이해하려고 노력 중
먼저, 크게 두 부분으로 구현한다.
1. 보조 페이지 테이블
2. 프레임 관리
보조 페이지 테이블은 기존 pml4가 물리 메모리에만 매핑되어 있는 한계를 보충하기 위해 필요한 테이블임.
구현해야 하는 함수는 두 가지이다.
- spt_find_page: 보조 페이지 테이블에서 va에 해당하는 페이지를 찾는다.
- spt_insert_page:주어진 보조 페이지 테이블에 page 구조체를 삽입한다.
위의 두 함수를 통해 보조 페이지 테이블의 읽기와 추가가 가능하다.
다음은 프레임 관리이다.
프레임은 총 3단계로 이루어진다.
1. 유저 풀에 메모리를 할당 후 해당 주소를 초기화된 frame의 kva에 연결하여 frame을 반환
즉, 이 kva를 통해 나중에 연결된 page에 접근할 수 있음.
2. 특정 va에 page 할당
3. 페이지가 할당된 va에 frame을 할당
이건가?
kernel pool은 물리 메모리의 커널 영역
kva는 가상 메모리의 커널 영역
가상 메모리의 커널 영역은 물리 메모리의 커널 영역과 일치
user pool은 물리 메모리의 유저 영역
va는 가상 메모리의 유저 영역
용어 정리
물리 메모리 (Physical Memory): 실제 하드웨어 메모리입니다. RAM을 나타냅니다.
가상 메모리 (Virtual Memory): 각 프로세스에게 할당되는 가상 주소 공간입니다. 각 프로세스는 독립된 가상 메모리를 가집니다.
프레임 (Frame): 물리 메모리를 작은 블록으로 분할한 것입니다. 각 프레임은 페이지와 매핑됩니다.
페이지 (Page): 가상 메모리의 작은 블록으로, 각 프로세스의 주소 공간을 나타냅니다. 페이지는 프레임에 매핑되어 실제 메모리에 저장됩니다.
KVA (Kernel Virtual Address): 커널 영역에 대응하는 가상 주소 공간입니다. 커널 코드와 데이터에 접근하는 데 사용됩니다. 커널 풀과 커널 데이터는 여기에 저장됩니다.
VA (Virtual Address): 유저 영역에 대응하는 가상 주소 공간입니다. 유저 프로세스의 데이터와 스택에 접근하는 데 사용됩니다. 유저 풀과 유저 데이터는 여기에 저장됩니다.
커널 풀 (Kernel Pool): KVA 내의 커널 영역에 대응하는 물리 메모리 공간입니다. 커널 코드 및 데이터가 저장됩니다.
유저 풀 (User Pool): VA 내의 유저 영역에 대응하는 물리 메모리 공간입니다. 각 유저 프로세스의 데이터와 스택이 저장됩니다.
user pool이 왜 kva?
할당된 메모리는 user pool에 할당되지만,
이 메모리에 접근하는 코드는 커널 모드에서 실행되어야 하므로,
frame의 kva에 저장한다.
나만 이해하는 후다닥 그림
뭔가 이거 같다
익명 페이지 구조체
뭘 넣어야 되는거야.. 막막..
struct anon_page {
};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
};
};지연 로딩
vm_alloc_page_with_initializer() : 페이지 구조체 초기화 후 페이지 유형에 따라 적절하게 이니셜라이저 설정
폴트가 발생하면 uninit_initialize가 호출됨
-> 익명 페이지: anon_initializer 호출
-> 파일 백킹 페이지: file_backed_initializer
모든 페이지는 VM_UNINIT 페이지로 생성됨
페이지의 수명 주기
초기화 -> 페이지 폴트 -> 지연 로드 -> 스왑 인 -> 스왑 아웃 -> (반복) -> 삭제
정글 입소 후 최대 위기
핀토스 가상 메모리 😱😱😱😱😱😱😱😱😱😱
