pintOS › pintOS 가상메모리 정리(Week11_day2)

오늘은 pintOS 마지막 Virtual Memory를 정리한다.

Virtual Memory

지금까지의 과제는 기기 환경의 메인 메모리 크기에 따라 돌릴 수 있는 프로그램의 수가 제한되어 있었다.
이번 과제를 통해 무한한듯한 메모리를 구현하여 그 제한을 없애 볼 것이다!

배경지식

문제상황

우선 pintOS에서는 대량의 템플릿 코드를 제공하고 있는데, 바꾸지 말라고 되어있는 부분을 바꾸거나 템플릿을 따르지 않으면 점수를 받을 수 없다. 주의할 것!

당연하겠지만, 물리메모리는 제한적인데 많은 프로세스들이 물리 메모리를 사용하려고 한다.
이 모든 프로세스들의 페이지를 동시에 물리 메모리에 저장하기에는 공간이 충분하지 않다.

• Page-Out(페이지 아웃) : 만약 페이지가 사용되지 않는다면, 물리메모리에서 제거되어 스왑 테이블 또는 파일 시스템에 기록되게 된다.
• Page-In(페이지 인) : 프로세스가 필요한 페이지가 물리메모리에 없다면 스왑에서 가져온다. 자리가 없으면 다른 페이지를 Page-Out 해야 할 수도 있다.

가이드라인

• Supplemental page table(보충 페이지 테이블 구현).
• Physical frame management(물리 프레임 관리).
• Modifying page fault handler for lazy loading(demand paging) : 페이지 폴트가 발생했을 때 스택 확장, 파일 매핑 처리 등의 동작.
• mmap, munmap : 파일을 메모리에 매핑하는 동작.
• swap in/out : 스왑 파티션에 기록된 페이지를 추적하는 자료구조.

용어 정리

가상메모리와 물리메모리는 같은 크기(보통 4KB)로 나누게 된다.

• Page : 가상메모리를 일정한 크기로 나눈 단위.
• Frame : 물리메모리를 일정한 크기로 나눈 단위.
• Page Table : 가상 주소를 물리 주소로 (페이지를 프레임으로) 바꿔주는 자료구조.
• Eviction : 페이지를 프레임에서 제거하고, 스왑테이블이나 파일 시스템에 기록하는 것(Swap out 보다 포괄적인 개념).
  정리하자면, Eviction이란 페이지와 프레임 사이의 매핑을 끊는 것으로 해당 페이지는 유효하지 않은 상태가 되며, 총 3가지의 경우의 수가 있다.
  메모리에 매핑 된 동안 수정사항이 있었다면, 익명 페이지일 경우 스왑영역에 기록, 파일 기반 페이지일 경우 파일 시스템에 기록하며, 수정사항이 없는 클린 페이지일 경우 물리 메모리와의 매핑만을 끊는다.
  이 경우에는 페이지 테이블에 엔트리는 존재하지만, 물리 메모리와의 매핑은 되지 않은 상태로 CPU가 접근하려하여 페이지 폴트가 발생하면 파일 시스템에서 다시 찾아오게 된다.
  물론 3가지 경우 모드 CPU가 접근을 시도할 시 페이지 폹트가 발생한다.
• Swap Table : 스왑 파티션에 기록된 페이지를 추적하는 자료구조

만들어야 할 자료구조

• Supplemental page table
  각 프로세스에 대해 페이지의 추가 데이터를 추적하는 자료구조, 데이터가 어디에 있는지(프레임, 디스크, 스왑), 커널 가상 주소에 대한 포인터, 페이지의 활성상태(안쓰는 건지) 등의 정보를 기록한다.
  페이지 테이블과의 차이점은 페이지 테이블은 물리 프레임과의 매핑 여부, 즉 유효성만을 관리하고, SPT는 유효하지 않은 페이지의 추가적인 정보들을 관리한다.
• Frame table
  물리 프레임을 관리하는 전역 자료구조로 할당 되었는지, 사용가능한지를 추적한다.
  추가적으로 사용 중인 프레임에는 어떤 페이지가 매핑되어있는지, 그 페이지가 Dirty page인지, 페이지 교체 정책에 필요한 정보도 가지고 있다.
• Swap table
  스왑 공간 내의 페이지 위치를 기록하고 추적하는 자료구조.
• File mapping table 메모리 매핑된 파일이 어떤 페이지에 할당되어있는지 추적하는 자료구조.
  추가적으로 처음 프로세스가 실행 될 때 필요한 코드와 데이터, 명시적으로(mmap() 등) 호출을 통한 매핑, 동적 라이브러리 파일 등이 가상 메모리와 매핑이 된다(모든 파일이 매핑되는 것은 아님).
  그렇기 때문에 프로세스의 실행 과정을 정리해 보면, 프로세스가 처음 실행될 때 위에서 언급한 필요한 파일의 일부가 가상메모리와 매핑이 되며, 해당 정보가 파일 매핑 테이블에 기록이 된다.
  이후 페이지 테이블에는 가상 주소 공간에 대한 엔트리들이 설정되고, 유효하지 않은 상태로 존재한다.
  CPU가 해당 가상 주소로 접근하려 하면, 페이지 폴트가 발생하고, 페이지테이블 엔트리의 정보를 바탕으로 해당 페이지가 익명 페이지 인지(동적 할당 된 힙, 스택 등 파일 시스템에 저장되어 있지 않은 데이터), 파일 매핑된 페이지인지를 확인하고, 각각의 경우에 따라 스왑테이블과 파일 매핑 테이블을 확인하여 해당 가상 주소와 매핑된 데이터를 물리 메모리에 올려서 정상적으로 접근이 가능하게 된다.

자료구조 선택지

• Arrays : 가장 간단한 접근법으로, 띄엄띄엄 채워질 경우 메모리를 낭비한다.
• Lists : 비교적 간단하지만 순회하는데 시간이 많이 든다.
• Bitmaps : 각 비트가 참 또는 거짓일 수 있는 배열로, 동일한 리소스에서 사용중인지 사용가능한지를 알기 좋다.
• Hash Tables : 해시 테이블을 사용해 빠르게 데이터를 찾을 수 있다.

Lazy loading 의 개념

가상 메모리가 생성될 때, pintOS는 struct page를 가상 주소에 할당한다.
각 가상 주소는 anonymous memory(익명 메모리), file-backed memory(파일 기반 메모리) 등으로 목적에 따라 사용된다. 이 정보는 page 구조체에 저장되어있고, page 구조체의 할당이 물리 페이지의 할당을 의미하지는 않는다.

페이지 구조체와, page_operations 구조체

페이지는 처음에 uninit_page 상태로 시작되고, 익명메모리인지 파일 기반 메모리인지에 따라 각각 anon_initializer, file_map_initializer의 초기화 함수가 호출되며, 초기화 함수는 페이지의 목적에 맞는 page_operations 구조체를 연결시켜 준다.
추후 운영체제가 작업을 수행해야 할때 목적에 맞는 swap_in, out, destroy 작업을 수행할 수 있다.

SPT

페이지 테이블을 직접 변경하지 않고, 페이지에 대한 추가 정보를 보충하기 위한 자료구조.

• spt_find_page : SPT에서 가상 주소에 해당하는 page 구조체를 찾는 함수.

SPT의 목적

• 페이지 폴트 발생 시 커널이 SPT에서 데이터를 찾아 어떤 페이지를 불러올지 결정
• 프로세스가 종료될 때 커널이 SPT에서 어떤 리소스를 해제해야 할 지 결정.

Frame Table

프레임이 가득 찼을 때 프레임을 확보하는 것이 Eviction인데, 프레임 테이블이 이를 관리한다.
페이지 교체 알고리즘은 LRU(가장 오랫 동안 사용하지 않은 페이지를 제거하는 알고리즘)에 근사하고, Clock 알고리즘 보다는 좋아야 한다.
또한 user page의 프레임만을 관리한다.

그렇다면 어떻게 페이지를 evict 할까?

• page replacement algorithm을 이용하여 대상 프레임을 고른다.
• 페이지 테이블에서 해당 프레임의 참조를 제거한다.
• 필요하다면 페이지를 파일시스템이나 스왑에 기록한다.
• Accessed 비트와, Dirty 비트는 CPU가 설정한다.

Swap Table

• 사용 중인 스왑 슬롯과 사용가능한 스왑 슬롯을 추적한다.
• 페이지를 evict해서 swap 영역으로 넣을 수 있도록 사용가능한 swap slot을 고를 수 있도록 해야한다.
• 지정 된 페이지가 다시 메모리로 읽혀오거나, 프로세스가 종료되었을 때 해당 스왑 슬롯을 해제 해주어야 한다.

동기화

여러 쓰레드에서 동시에 페이지 인, 아웃을 시도할 수 있기 때문에 자료구조 동기화에 주의해야 한다!

스택 확장

이전 프로젝트에서는 사용자 프로세스의 스택 공간을 미리 할당했었는데, 이번 프로젝트에서는 스택이 필요할 때마다 동적으로 페이지를 할당해야한다.
그렇기 때문에 유효한 스택의 접근도 페이지 폴트를 발생시킬 수 있고, 그 때마다 동적으로 새 페이지를 할당해 주어야 한다.

만약 프로그램이 스택을 더 사용하려고 하면, 스택의 하위주소에 접근하려 할 시 해당 주소에 페이지가 존재하지 않음을 알고 페이지 폴트를 발생시켜, 유효한 스택 접근인지 확인하고, 새로운 페이지를 할당하여 스택을 확장시킨다.
이 때 유효성의 의미는 %rsp 스택 포인터보다 아래 주소로의 접근인지를 의미한다.
페이지 폴트가 발생하면 intr_frame 구조체에 rsp 레지스터가 있음을 인지!

Memory Mapped Files

• mmap() : 파일을 메모리에 매핑하여 파일의 내용을 메모리 주소를 통해 직접 접근할 수 있도록 한다.

  • 파일의 크기가 0인 경우.
  • 매핑하려는 주소가 다른 페이지와 겹치는 경우.
  • 주소가 페이지 경계에 맞지 않는 경우.

  에러가 발생한다.

• munmap() : 파일의 메모리 매핑을 해제한다.
  실제로 메모리에 로드할 때는 lazy 하게 로드하여아한다.

메모리 매핑된 페이지를 교체 할 때는, 변경된 내용을 원본 파일에 기록해야 한다.
프로세스가 종료되면 모든 매핑은 암묵적으로 해제된다.