Task listing

Memory Management

• 목표: 물리 메모리 로드 대신, supplement page table으로 메모리를 관리한다
• 구현
  • Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가
  • struct thread, page, supplement_page_table, frame에 필요한 멤버 추가 가능
  • spt 관련 기본 함수 구현 (init, copy, kill 3가지)
  • 종료 시 SPT를 참조하여 어떤 리소스를 해제할 지 결정
  • spt 관련 page 연산 함수 구현 (find, insert, remove)
  • frame 관련 함수 구현 (get, claim, do_claim)
  • Free Frame이 없으면(swap slot이 가득차면), victim page 선택(eviction policy 구현)

Anonymous Page

• 목표: Page Type에 따라 알맞게 처리하고, lazy loading을 구현한다.
• 구현
  • page type에 따른 initializer 호출
  • struct anon_page에 필요한 멤버 추가 가능
  • 처음은 무조건 uninit 페이지로 생성, 페이지 구조만 할당
  • lazy loading을 위해 load_segment while문 로직, setup_stack 로직 수정
  • Page Fault Handler에서 Valid한 Fault인지 체크
    [여기까지 하면 fork 제외 Project2 테케 모두 통과]
  • fork를 고려한 SPT copy, kill 함수 구현
  • uninit_destroy, anon_destroy 구현
    [ 여기까지 하면 Project2 테케 모두 통과 ]

Stack Growth

• 목표: 스택이 현재 크기보다 커지면(Stack Access) 추가 페이지를 할당한다.
• 구현
  • 스택 포인터의 잘못된 access를 어디에서 체크할건지 고민
  • page fault handler에서 vm_stack_groth 호출, 구현 (최대 1MB 제한)

Memory Mapped Files

• 목표: File-backed Page를 구현한다.
• 구현
  • lazy하게 do_mmap, do_munmap 구현
  • exit될 때 매핑 해제
  • file_init, initializer, destroy 구현

Swap In/Out

• 목표: 메모리 할당량이 가득 차면, 프레임을 디스크로 교체한다.
• 구현
  • Anon일 경우 anon_init, initializer 수정
    swap_in, swap_out 구현(out을 먼저)
  • file-backed인 경우, 매핑된 파일에 다시 기록됨 init, initializer 수정
    backed_swap_in, backed_swap_out 구현

---

kaist list

https://www.youtube.com/watch?v=8twIUEo1mIs

• Enable Demand paging/swapping
• Enable Strck Growth
  • Dynamic page allocation for page fault on stack
• Implement Memory mapped file
  • Implement mmap() and munmap()
  • differentiate file backed page and anonymous page
• Enable Accewnssign user memory

---

page_fault()

Userprog/exception.c
page_fault()
{

}

• Check if the memory ref is valid

  • valid
    • vm page에 들어가야하는 내용 locate하기
      (공유페이지가 구현되어있다면, 페이지가 페이지 테이블에는 없는데 이미 페이지 프레임에 있을 수도 있다)
  • invalid
    • could be the invalid user address or Kernel address or permission error

• Allocate page frame

  • 페이지 폴트가 나면 os는 모든 페이지 프레임을 스캔하고 하나의 페이지 프레임을 선택해서 디스크에서부터 완벽한 페이지를 load? allocate 해야한다

• Fetch the data form the disk to the page frame

• Update page table

additional info for the individual virtual pages

• Virtual page num
• Read/Write permission
• Type of virtual page
  • (unwritable&unmodifiable) a page of EyLF executable file
  • a page of general file
  • (anonymous) a page of swap area
• (memory mapped file) Reference to the file object(info about which file it is from?) and offset
• amount of date in the page : the content size out of 4KB
• location the swap area
• In-momory flag: is it in memeory?

vm_entry(data structure: set of attribute each page)

what I have done

Memory Management

• 목표: 물리 메모리 로드 대신, supplemental page table으로 메모리를 관리한다
• 구현 list
  • 1. Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가
  • 2. struct thread, page, supplement_page_table, frame에 필요한 멤버 추가 가능
  • 3. spt 관련 기본 함수 구현 (init, copy, kill 3가지)
  • 4. 종료 시 SPT를 참조하여 어떤 리소스를 해제할 지 결정
  • 5. spt 관련 page 연산 함수 구현 (find, insert, remove)
  • 6. frame 관련 함수 구현 (get, claim, do_claim)
  • 7. Free Frame이 없으면(swap slot이 가득차면), victim page 선택(eviction policy 구현)

현재 상태는 페이지 테이블만 있음(pml4).

1번 Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가

1.1 Implementing Supplemental Page Table

supplemental page table 구조체가 비어있다. 어떠한 정보가 필요한가?

페이지 폴트와 자원 관리를 처리해야함. 그럼 hash table이 일단 필요하겠다. hash 구조체 구경하기

• Hash 구조체를 supplemental_page_table 구조체 안에 추가

<vm.h>
struct supplemental_page_table { 
	struct hash spt_hash;
};

• hash.h 에 주석을 보면 Instead, each structure that can potentially be in a hash must embed a struct hash_elem member. 이라고 되어있어서 page에 hash_elem 구조체 추가함

<vm.h>
struct page { 
    '''
    struct hash_elem hash_elem;
    '''
};

그리고 세가지 function을 손봐야한다.

• void supplemental_page_table_init (struct supplemental_page_table *spt);

  • spt를 initialize 하기 위해 hash_init이라는 함수를 사용하고 싶은데 인자로 hash_hash_func?라는 것과 hash_less_func라는 function pointer들을 넘겨야한다.
    bool hash_init (struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux)
    그렇다면 hash_hash_func와 hash_less_func를 참고해서 page_hash, page_less함수를 만들자.
    만들었으니 hash_init함수를 사용해서 한줄로 초기화를 해버리자.

  •   <vm.c>
    /* Computes and returns the hash value for hash element E, */
    unsigned
    page_hash (const struct hash_elem *he, void *aux UNUSED) {
    	const struct page *p = hash_entry(he, struct page, hash_elem);
    	// hash_bytes: returns a hash of the size(sec arg) bytes in BUF(first arg) 
    	return hash_bytes (&p->va, sizeof(p->va));
    }
    /* Returns true if A is less than B, or false if A is greater than or equal to B */
    bool
    page_less (const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED) {
    	const struct page *pa = hash_entry(a, struct page, hash_elem);
    	const struct page *pb = hash_entry(b, struct page, hash_elem);
    	return pa->va < pb->va;
    }
    /* Initialize new supplemental page table */
    void
    supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
    	hash_init(spt, page_hash, page_less, NULL);
    }

• struct page spt_find_page (struct supplemental_page_table spt, void *va);

  • hash_find() 함수 사용하자. 주석 설명
    Finds and returns an element equal to E in hash table H, or a
    null pointer if no equal element exists in the table.
    그렇다면 spt_find_page에서 인자로 받아오는 spt가 hash이니까 첫번째 매개변수로 넘기고, va를 아니까 page 할당받아서 va넣고 그 페이지의 hash_elem 을 넘기자.

    /* 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;
    	
    	page = malloc(size_of(struct page)); // 얘는 왜이래
    	page->va = va;
    	
    	struct hash_elem *e;
    	e = hash_find(&spt, &page->hash_elem);
    
    	return e!=NULL ? hash_entry(e, struct page, hash_elem):NULL;
    }

• bool spt_insert_page (struct supplemental_page_table spt, struct page page);

  • hash_insert(&spt, &page->hash_elem) 이렇게 쓰면 될것같은데 존재하지 않을 경우에만이라는 조건을 어떻게 넣을 수 있을까.
    hash_insert 함수의 주석을 보고 아이디어를 얻었다.
    Inserts NEW into hash table H and returns a null pointer, if no equal element is already in the table. If an equal element is already in the table, returns it without inserting NEW.
    그럼 없던 데이터를 넣을 땐 null pointer를 반환하니까 함수 값이 널일 때만 실행 되게 하면 되겠다.

    /* Insert PAGE into spt with validation. */
    bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
                       struct page *page UNUSED) {
      int succ = false;
    
      return hash_insert(&spt, &page->hash_elem) == NULL ? true : false;
    }

quiz

1번 문제: TLB

1.1 TLB 가 어떻게 페이지 테이블의 성능을 향상시키는지?

1.1 TLB는 Table Load Buffer 의 약자로 가상주소를 물리주소로 변환하는 것을 위한 페이지 테이블의 성능을 향상시키기 위해 있는 것으로, cache 기능과 비슷하게 시간지역성을 활용해서 한번 페이지 테이블을 통해 가져온 데이터를 TLB에 업데이트하여 다음에 같은 페이지를 참조하게 되면 TLB를 먼저 확인해서 페이지 테이블을 통해 변환하는 작업을 하지 않아도 되게 하는 것이다.

1.2 TLB miss 가 발생하면 시스템이 어떤 과정을 거쳐 메모리에 접근하는지?

1.2 TLB miss가 나면 크게 하드웨어가 처리하느냐, 소프트웨어가 처리하느냐에 따라 처리 방식이 다르다.
전통적으로는 하드웨어가 처리하는 방식인데 이는,

1. 페이지 참조가 유효한지 확인하고
2. 페이지 테이블에서 사용가능한 page를 확인하고 (사용 가능한 free page가 없다면 eviction policy에 따라 victim 을 선정하고 swap disk 에 swap 한다)
3. backup disk 에서 완벽한 free frame을 load하고
4. 페이지 테이블과 TLB를 업데이트한다.

소프트웨어가 처리하는 방식은 페이지 테이블을 거치지 않고 바로 가져와서 업데이트하는데 정확히는 기억이 나질 않는다. -> 이부분 찾아보기

내가 잘못 생각했던거 TLB 미스나면 페이지테이블 참조하는건데..! 아는건데 잘못생각했었다.

정답

2번 문제: Belady의 역설

paging 기법을 사용하는데 page fault 의 발생 빈도가 더 늘어나는 현상. 원인과 방지하는 해결방법.

정답

3번 문제: Thrashing 현상이란

page 부재가 너무 많이 발생하여 cpu 성능이 떨어지는 현상

"프로세스가 페이지 부재를" 이라고 설명하면 더 좋겠다

정답

4번 문제: 운영체제가 anonymous page를 0으로 초기화 하는 이유

anonymous page는 이미 페이지와 파일이 맵핑되어있는 file backed page 혹은 memory mapped page와는 다르게 페이지가 아무런 파일과도 맵핑되어 있지 않는 페이지를 말하는데 이를 초기화하지 않으면 페이지에 쓰레기 값이 들어가 있기 때문에 0으로 초기화 하는것이 좋다는 것으로 알고있다.

정답

5번 문제: LRU 캐시 알고리즘

5-1. 요청순서 9번의 캐시상태를 쓰시오 -> 5967
5-2.

clock 알고리즘 LRU와 비슷하게 성능을 낼 수 있는데 현실적으로 cost가 더 적어서 LRU대신 많이 쓰이는 것으로 알고 있다.

알고리즘 작동 방식은 정확하게는 모르겠다..
2 [1, 2, 3, 4][1, 1, 1, 1]
5 [1, 5, 3, 4][0, 1, 0, 0]
1 [1, 5, 3, 4][1, 1, 0, 0]
2 [1, 5, 2, 4][0, 0, 1, 0]
3 [1, 2, 3, 4][1, 1, 1, 1]
4 [1, 2, 3, 4][1, 1, 1, 1]
5 [1, 2, 3, 4][1, 1, 1, 1]

정답

https://www.youtube.com/watch?v=C26qsPwf-Js

이 아저씨가 푸는 방식으로 풀면 엄청 쉽다.

rule 몇가지만 유의하면서 풀면 된다.

• 누굴 쫓아낼 필요 없을때

  • frame에 넣고 ref를 1로 set (나머지 애들의 ref를 바꿀 필요는 없다)

• 쫓아내야할 때 (second chance를 주는 것임을 기억하자) (page fault가 발)

  • victim frame의 page를 보고 1이면 기회를 한번 더 주는 의미로 0으로 바꾸고 다음걸로 넘어간다. (0을 만날때까지 반복)
  • 어떤 페이지의 ref가 0이면 킥하고 새로 넣은 page의 ref를 1로 set.
    • 나머지 프레임(아래로만 바꾸고 맨 위로 올라가진 않는다)들의 ref를 0으로 set
    • victim page를 하나 아래로 바꾼다.