[WEEK12] Pintos _ Project3 Virtual Memory 정리 및 회고

0. Gitbook과 Github Link

해당 블로그 글에는 코드를 따로 올리지 않으므로 대신하여 Github Link를 올립니다.

수정이 필요한 부분이나 틀린 부분은 댓글로 지적해주시면 감사하겠습니다.

 

Gitbook

Introduction · GitBook

 

Github Link (Implementation)

 

GitHub - simons-pintos/pintos-kaist

---

1. 큰 그림 잡아보기

Project 2와 Project 3 비교

 

이번 프로젝트의 경우 처음 메모리 구조와 전체적인 큰 그림을 잡는 것이 중요한데,

우리 조에는 든든한 팀원(HJ, JS)이 있어서 전체적인 그림을 잘 잡고 시작할 수 있었다.

 

• Project 2의 경우 page를 가상메모리를 올릴 때 install_page 함수를 통해
  가상메모리에 올리는 동시에 해당 페이지를 물리메모리 상에도 올려준다.
  
  
• 반면 Project 3의 경우 최초의 setup_stack만 physical memory 상에 바로 올려주고
  그 후에 늘어나는 스택에 대해서는 lazy_load 방식을 사용하여 물리메모리에 올려준다.
  
  
• (load_segment → lazy_load 방식으로 설정해놓음 (vm_alloc_page_with_initializer) → … →
  페이지 폴트가 일어나면 vm_try_handle_fault → vm_stack_growth 및 vm_do_claim_page )
  
  
• 해당 차이는 소스코드를 보면 좀 더 차이점을 쉽게 알 수 있음 (링크)

Project 2와 Project3의 차이를 간단한 도식화로

 

2. Lazy Loading 방식

 

물리메모리는 공간적으로 한계가 있기 때문에 lazy loading을 통해서 필요한 시점이 되어서야 메모리에 로딩을 시키는 방식이다.
물론 가상메모리의 경우 일종의 환상(illusion)이기 때문에 우리는 페이지에 대한 접근을 위해서는 가상메모리를 거쳐 물리메모리로의 접근이 필수적이다.

메모리의 크기가 매우 크다면 Disk가 필요없고 물리메모리에만 모든 페이지를 올려놓으면 되겠지만 안타깝게도 우리의 메모리는 한정되어 있다. 멀티프로세싱 등의 발전으로 다양한 프로세스들에 대한 데이터를 물리메모리로 올리고 내리는 작업을 수행하게 되었으며, 그러한 작업을 효율적으로 해주는 것이 lazy loading 방식이라고 할 수있다.

lazy load 방식을 작동시키기 위해서는 가득찬 물리메모리를 비워주는 eviction이 필요하다.
이러한 eviction을 수행하기 위해서는 FIFO, Optimal Condition, LRU, Random 등의 방식이 있다.

 

Project 2에서는 Load segment를 하는 동시에 pml4에 가상메모리와 물리메모리를 올려주는 작업을 진행하였지만, 
Project 3에서는 page fault가 일어나고 vm_try_handle_fault를 통해서 가상메모리와 물리메모리를 올려준다.

(process.c의 load_segment()와 vm.c의 vm_try_handle_fault() 함수를 참고)

 

3. Gitbook을 따라서 구현시작

1) Anonymous Page 

(vm.c, uninit.c, anon.c, process.c를 참고)

- vm_alloc_page_with_initializer

• pending page를 initialized와 함께 구현하는데 Git book 내용에서와 같이 uninit page의 swap-in handler가
  자동적으로 페이지의 type, init, aux에 맞춰서 해당 페이지를 initialized 시켜준다.
  
  
  1. spt에서 페이지를 찾아 페이지가 없으면 새로운 페이지를 할당해주는 구현을 한다.
     
     
  2. malloc으로 새로운 페이지를 할당받고 VM_Type에 따라 type에 맞는 uninit_new를 실행한다.
     
     
  3. new_page를 writable로 바꿔준다.
     
     
  4. spt page에 해당 new_page를 삽입한다.

- uninit_initialize

• 따로 변경사항을 가지지 않았다.
  (uninit page가 initialize 할 때 page_initializer를 통해 anon page나 file page로 변환 후 init을 통해 lazy_load를 수행)

- vm_anon_init

• swap_in & out을 구현하기 전이라 아직까지는 구현을 하지 않았다.

- anon_initalizer

• uninit_page 구조체에 대해 0으로 memset을 해주고 해당 페이지의 operation을 anon_ops로 수정한다.

- load_segment

• vm으로 load를 할 때 page 단위로 load를 하며 처음 load의 경우 vm_alloc_page_with_initializer로 allocation 한다.
  (우선 uninitialized 된 상태의 page를 alloc하고 lazy_load_segment 및 file_info를 함께 인자로 넘기며 alloc)

- lazy_load_segment

• lazy loading을 위해 필요한 함수이다.
  핵심적인 개념은 vm_alloc_page_with_initializer를 통해서 aux (file_info)를 받고 info를 읽어서 파일 → 버퍼로 씀 (물리메모리)

- setup_stack

• USER_STACK에 페이지를 create 하여 해당 위치에 vm_alloc_page_with_initializer 를 해주되
  이번에는 lazily loading이 아닌 일반적인 loading을 한다.

 

2) Supplement Page Table

(vm.c, uninit.c, anon.c, process.c를 참고)

 

우리 조는 기존에 구현이 되어 있는 hash table을 가지고 spt를 구현하기로 하였다.

hash table에 대해서는 정확한 개념 이해를 위해서 Do it 자료 구조 책의 개념과 Googling을 통해

해당 핵심 개념들을 빠르게 숙지하고 다시 구현에 들어갔다.

 

 

• 일단 supplemental_page_table_init 구현을 위해 supplemental_page_table, spt_hash, spt_less 를 구현했고 supplemental_page_table_copy와 supplemental_page_table_kill을 구현하였다.
  
  
• supplemental_page_table_copy는 hash_iterator를 활용하여 구현하였는데
  여기서 어려웠던 점은 VM_UNINIT과 그러지 않은 type을 나누는 과정을 알아차리는게 쉽지 않았던 것 같다.
  
  
• 생각해보면 우리는 UNINIT의 경우 vm_alloc_page_with_initializer 를 통해서 init을 일단 보류시키고,
  다른 값들에 대해서는 바로 claim_page를 해줘야한다. 이는 spt_copy에서도 똑같이 발생하는 바이다.
  
  
• supplemental_page_table_kill의 경우 spt에 있는 모든 mmap_file에 대해 munmap을 시켜주고, 해시테이블에 대해 destroy를 시키는 과정을 거친다. destroy의 destructor 함수 포인터를 통해서 hash에 있는 dealloc_page(page를 free 시키고 destroy) 시키는 과정을 거친다.

 

3) Page Cleanup

다 짜고 보니 uninit_destroy와 anon_destroy 는 안 짰는데 다 돌아감..?

 

4) Stack Growth

(vm.c, exception.c를 참고)

 

page fault가 났을 때 page fault는 거의 대부분은 소프트웨어적으로 처리가 된다.

H/W 적으로 처리가 가능하지만 S/W 적으로 처리를 하는 이유는 H/W에서 Page Fault로 인한 처리가 너무 느리기 때문이고 하드웨어가 스왑공간 구조, 디스크에 I/O를 요청하는 방법 등의 세부사항을 모두 알아야하는데 이러한 점이 비효율적이고 간편하지 못하기 때문에 S/W 적으로 처리하게 되었다.

 

우리의 코드에서는 page_fault라는 함수를 통해 page fault를 처리해주고 vm_try_handle_fault를 통해서 해당 폴트를 처리해주게 된다. 위에서 말했듯이 페이지 폴트가 Bogus Fault일 경우도 있으므로 해당 사항의 경우 stack_growth 해야하는 조건들을 확인하여 stack_growth를 실시한다.

 

vm_stack_growth의 경우 addr을 pg_round_down 해주고, vm_alloc_page를 통해 page를 not lazily하게 할당받은 다음 user_rsp를 addr로 내려주는 일련의 과정을 진행하게 된다.

 

5) Memory Mapped File

(vm.c, file.c, syscall.c를 참고)

 

mapped된 파일에 대해 vm에 alloc을 시행하며 (load_segment와 거의 유사한 과정) 마지막에는 addr값을 리턴해준다.

 

다만 조금 다른 점은 mmap_list와 page_list를 추가해서 list_push_back의 과정을 거쳐주는데 list를 관리해줘야 추후 munmap에서 적절한 unmap이 가능하다.

 

 

munmap의 경우 위에서 만들어준 mmap_list, page_list를 검색하여 해당 page→ va를 pml4_clear_page 해줘야한다.

 

매핑해제를 해주면서 유념해야할 점은 pml4_is_dirty를 확인하여 page가 dirty할 경우 file_write_at을 통해 변경된 사항에 대해 파일에 다시 적어줘야한다.

 

6) Swap In / Out

(vm.c, anon.c, file.c를 참고)

 

Swap In & Out을 활용하여 물리메모리의 크기 제한을 효율적으로 사용할 수 있다.

여기서 필요한 점은 eviction 정책인데, eviction 정책을 통해 물리메모리가 꽉 차 있을 때 disk로 다시 swap out할 수 있기 때문.

 

운영체제는 swap in과 out을 통해 물리메모리와 디스크 사이를 왔다갔다 하며 필요한 페이지를 메모리에 올려 사용한다.

여기에서는 ANON과 File-mapped가 다르게 구현될 것

 

Swap In & Out을 위해서는 Swap Disk에 대한 구현이 필요하고 우리는 swap disk를 bitmap을 통해서 구현하였다.

swap_disk(swap partition)은 말 그대로 disk에서 swap을 위해 필요한 공간이고,

swap_table는 이러한 swap_disk를 사용하기 위해 설정되는 메모리에 존재하는 bitmap이다.

 

각 swap_partition과 swap_table은 사용 중이거나 사용 중이지 않음을 표시해놓고 하나의 swap_slot은 하나의 페이지가 된다.

하나의 페이지는 8개로 나누고 해당 영역을 sector라고 부른다.

 

 

• Swap In & out을 구현하기 위해서는 eviction 정책을 수립할 필요가 있고,
  
  
• vm.c 파일의 vm_get_victim, vm_evict_frame, vm_get_frame을 통해서 victim을 찾고
  victim이 차지하고 있는 물리메모리를 evict한다.
  page fault가 날 경우 vm_try_handle_fault를 통해 페이지 폴트를 처리한다. (vm_do_claim_page)
  
  
• 가장 간단한 FIFO를 기준으로 구현하였으나 디스크 접근 속도가 성능에 큰 차이를 보이기 때문에
  최적 혹은 LRU 정책을 통해 좀 더 효율적인 구현이 수행되면 좋을 듯 하다.
  
  
• FIFO와 LRU의 차이? (이전 포스팅 참고)

 

4. Pintos Project 3 회고

길고도 짧았던 2주 반의 시간이 흘렀다.

이번 프로젝트는 내용이 어렵기도 하고 양이 많다는 소식을 많이 들어서 꽤나 긴장이 되었다.

다행히 좋은 팀원들 덕분에 모르는 개념을 손쉽게 알아내고 여러 이야기들을 해나가며 지식을 확장시킬 수 있었던 것 같다.

혼자서 묵묵히 공부하는 것보다 남들과 얘기하면서 공부를 하다보면 

내가 제대로 몰랐던 개념을 다시금 깨닫게 되고, 알았던 개념들을 다시 한번 다지는 기회가 되는 것 같다.

 

 

이번 프로젝트에는 코로나, 독감, 감기 등으로 동료들이 아픈 동료들이 많아 걱정도 되고 분위기가 조금은 가라앉았었던 것 같다 😷

그래도 별 탈없이 무사히 지나가고 프로젝트의 마무리도 얼추 잘 되어가는 것 같다.

 

 

이번주차에서 어려웠던 점은 처음에 큰 그림을 잡는 것, 깊이 있는 디버깅 과정, 정확한 원인을 모르고 테스트케이스가 돌아가지 않는 문제들이 가장 어려웠던 것 같다. 어려울수록 도식화를 해보고, 코드를 한줄한줄 이해하며 천천히 읽어내려가며, 디버깅을 하면서도 계속해서 기록했던 것들이 그나마 그러한 어려움을 조금이나마 해소해주지 않았나 라는 생각을 한다.

 

 

최근 들어 좀 더 높고 넓은 시야를 가져야겠다라는 생각을 하게 되는 것 같다.

지금의 나는 개발을 한창 배우고 있는 예비 개발자이지만,

일에 있어서는 마음가짐이나 행동을 주니어 혹은 시니어 개발자로 지내기 위해 노력하려고 한다.

 

 

또한, 현재는 핀토스라는 일련의 과제를 수행 중이지만

이게 과제가 아니라 실제 시장에 출시할 운영체제의 일부분이라면? (지금 상태로는 판매 불가..) 이라는

상상력을 동원해 좀 더 꼼꼼하고 전문성 있게 코드를 해석하거나 짜보려고 마인드를 다진다. 

 

 

현재의 수준보다 좀 더 탁월해지기 위해서 거쳐나가는 나만의 훈련? 같은 것이다.

물론 마음만 그렇게 먹는다고 모든 것이 해결되지는 않지만 좀 더 자세나 마음가짐을 바로 잡고 집중을 하게 되는 것 같다.

 

 

정글에서의 생활도 이제 얼마 남지 않았다.

정글을 다시 한번 더 하면 더 잘 할 자신이 있는데.. 라고 생각하며 하루하루 지나가는 시간들을 아쉬워하는 것 같다.

 

 

정글에서는 각기 특색은 다르지만 각자의 뚜렷한 장점을 가지고 있는 동료들이 많아

그것들을 나의 것으로 만들어나가려고 노력하는 과정에서도 큰 성장을 할 수 있는 여건이 되는 것 같다.

많이 배우고 익히고 즐기자.

 

 

이제 1주일 뒤면 나만무를 하게 된다.

좋은 동료들과 함께 즐겁고 재미있게 의미있는 결과물을 만들어내고 싶은 것이 나의 자그마한 바람이다.