[Pintos] Project 3 : Virtual Memory

1. Supplemental Page Table과 Lazy Loading

• Eager Loading은 가상 페이지가 할당됨과 동시에 물리 메모리에 올라가는 것. 당장 읽거나 쓸 일이 없는 페이지도 물리 메모리에 올라가버림. (플젝 3 이전의 핀토스)
• 물리 메모리 공간은 한정적이기 때문에, 당장 써야 할 페이지가 올라오려면, 누군가는 내려가야 함 = Swapping
• Swap in/Swap out은 오버헤드가 상당히 큼 (디스크에 읽기/쓰기를 시도하는 것이기 때문에)
• 따라서 우리의 핀토스는, 페이지가 진짜로 필요할 때에 물리 메모리로 올리는 지연 로딩, 즉 Lazy Loading을 채택했고, 이를 직접 구현하는 것이 플젝 3의 목표 
• 레이지 로딩을 구현하기 위해서, 페이지 할당 요청이 오면, 일단 uninit page로 만들고, page fault가 발생했을 때 비로소 애초에 요청되었던 type에 맞게 initialize를 해주고, 메모리로 로딩해오도록 코드를 작성했음.
• uninit = 초기화되지 않았다 = 물리 메모리에 올라가지 않았다
• supplemental page table이 필요한 이유 : lazy loading을 구현하기 위해
  • pml4는 virtual address와 physical address의 매핑을 관리
  • lazy loading의 경우, virtual page가 생성된다고 바로 physical frame이 할당되지 않으므로, 페이지 할당 시점에서는 pml4의 엔트리가 업데이트되지 않음 -> 따라서 할당된 페이지의 va에 접근하려고 하면 page fault가 발생함
  • page fault가 발생했을 때, page가 가지고 있어야 할 실질적인 data를 물리 메모리로 올려줘야 하는데, pml4에 page에 대한 메타데이타를 저장할 수는 없으므로, page와 관련된 여러 정보를 저장한 page struct가 필요하고, 이 page struct를 관리하기 위한 자료구조, supplemental page table이 필요함
  • supplemental page table의 구현: hash table (lib/kernel/hash.c에 정의되어 있음)
    • hash table을 선택한 이유 : array, list의 경우 탐색을 위해 iteration이 필요하므로 검색 속도가 느린 반면, hash table은 거의 상수 시간으로 원하는 데이터를 찾을 수 있음.
    • hash fucntion이 va를 해시값으로 변환하고, 해시값을 이용해서 hash_elem을 빠르게 탐색해서, 해당하는 page를 찾아옴 (spt_find_page())
• vm_alloc_page_with_initializer()
  • 페이지를 만들고, supplemental page table에 페이지를 삽입하는 함수, 추후 page fault가 발생했을 때 미리 설정해둔 타입으로 변환함과 동시에 물리메모리로 올라올 수 있도록 (물리 프레임을 할당받을 수 있도록) initializer를 설정해줌.
• vm_claim_page()
  • 가상 페이지를 위한 물리 프레임을 할당 -> 프레임과 페이지를 연결시킴 -> pml4의 엔트리를 업데이트 -> swap-in
• lazy_load_segment()
  • page_fault()가 발생했을 때, 파일을 읽어서 세그먼트를 물리 메모리로 읽어올 수 있도록 vm_alloc_page_with_initializer의 4번째 인자 (init)에 함수 포인터로 넣어줌. 파일에 대한 데이터(read bytes, offset)등은 load segment 실행될 시 aux에다가 넣고, page struct 내에 저장해두었음

2. Frame Table과 Swap-in/Swap out

• 물리 프레임 할당 요청이 왔으나 남은 프레임이 없는 경우, 할당된 프레임들 중 하나를 물리 메모리에서 내리고, 당장 써야하는 페이지를 물리 메모리로 읽어와야 함. 
• 내쫓을 프레임을 정하는 eviction policy를 정해야 함
• Eviction Policy : Clock Algorithm (LRU와는 다름! LRU를 사용하지 않는 이유는 구현이 어렵기 때문)
  • 참고 :
  • https://www.cs.jhu.edu/~huang/cs318/fall21/lectures/lec12_replacement.pdf
  • https://kouzie.github.io/operatingsystem/%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC/#thrashing
• 프레임 테이블이 필요한 이유
  • pml4와 spt는 프로세스마다 가지고 있는 자료구조 -> 전역적이지 않음.
  • 따라서 프레임이 부족해서 pml4나 spt를 탐색하며 쫓아낼 프레임을 찾는다? -> 물리 메모리의 모든 프레임을 탐색할 수 없음. pml4 혹은 spt에는 현재 프로세스에 할당되어 있는 페이지의 프레임들만 존재하므로
  • 따라서 물리 메모리의 모든 프레임을 탐색하여 victim page를 선정하기 위해, 프레임 테이블이 필요하다
  • linked list + clock algorithm으로 구현

 

3. Swap Table과 Swap-in/Swap out

• Anonymous page의 경우, 백업 파일이 없음 -> 물리 메모리에서 swap-out 될 때 돌아갈 (저장할 ) 파일이 없음! -> 따라서 swap disk라는 swap-out page 전용 디스크에 백업해둠. 
• 마찬가지로, swap-in 될 때는 스왑 디스크에서 다시 불러옴
• swap table이 필요한 이유
  • 빈 swap slot을 찾고, 해당 섹터에 접근하기 위해서 swap slot의 alloc/free 여부를 관리하는 자료구조가 필요함 
  • bitmap으로 구현 - 이유: 크기가 작고, alloc/free status만을 표현하면 되므로 0/1로 표현 가능한 bitmap이 적당 

 

 

가상메모리