PintOS. Virtual Memory 구현하기

Moon·2022년 11월 30일
0

🌻구현 예정 리스트🌼
1. Memory Management
2. Anonymous Page
3. Stack Growth
4. Memory Mapped Files
5. Swap in/out

0. 들어가기에 앞서서

  1. 페이지 : 4096바이트의 길이를 갖는 가상메모리의 연속된 영역. 페이지는 반드시 정렬되어 있어야함. 각 페이지는 페이지 크기로 나눠지는 가상주소에서 시작해야 함. 64비트 가상주소의 마지막 12비트는 페이지 오프셋(오프셋이 뭘까?)입니다. 상위 비트들은 페이지 테이블의 인덱스를 표시하기 위해 쓰인다.
  • pml4 -> 페이지 디렉터리 포인터 오프셋 -> 페이지 디렉토리 -> 페이지 테이블 -> 피지컬 페이지 오프셋(위에서 말한 12비트)
  1. 프레임 : 페이지 프레임(물리프레임)은 물리 메모리 상의 연속적인 영역. 페이지와 동일하게, 프레임은 페이지 사이즈여야 하고 페이지 크기로 정렬되어 있어야한다. 64비트 물리주소는 프레임 넘버와 프레임 오프셋으로 나뉘어진다. 64비트 시스템은 물리주소로 메모리에 직접 접근하는 방법을 제공하지 않음. Pintos는 커널 가상 메모리를 물리 메모리에 직접 매핑해서, 물리주소로 메모리에 직접 접근하는 방법을 제공한다. 커널 가상메모리의 첫 페이지는 물리메모리의 첫 프레임에 매핑, 두 번째 페이지는 두 번째 프레임에 매핑. 이후로 쭉 매핑해서 프레임에 접근. 핀토스는 물리주소와 커널 가상 주소 사이를 변환해해주는 함수를 제공.
#define ptov(paddr) : Returns the kernel virtual address corresponding to physical address pa
#define vtop(vaddr) : Returns the physical address corresponding to va
  1. 페이지 테이블 : CPU가 가상주소(페이지)를 물리주소(프레임)로 변환하기 위해 사용하는 자료구조. 가상주소는 페이지 넘버와 오프셋을 포함한다. 페이지 테이블은 페이지 넘버를 프레임 넘버로 변환하고, 오른쪽에 보이는 것처럼 물리주소를 획득하기 위해서 수정되지 않은 오프셋과 결합함.
  1. 스왑슬롯 : 스왑 파티션 내 디스크 공간에 있는 페이지 크기의 영역. 하드웨어적 제한들로 인해 배치가 강제되는 것이 프레임에서보단 슬롯에서 더 유연한 편이지만, 스왑 슬롯들은 페이지 크기로 정렬되는 것이 좋다.

1. 자원관리개요

관계된 자원들을 통합된 자료구조로 전부, 또는 부분적으로 합치는 것이 더 편리할 수 있음. 각 자료구조에서 각각의 원소가 어떤 정보를 담을 지를 정해야한다. 자료구조의 범위를 지역(프로세스별)으로 할지, 전역으로 할지 정해야하며, 해당 범위에 필요한 인스턴스의 수도 결정해야 한다. 설계를 단순화하기 위해, non-pageable memory(malloc, calloc)에 이러한 자료구조들을 저장할 수 있다. 즉, 이는 자료구조들의 포인터가 유효한 상태로 남아있을 거라는 사실을 보장할 수 있다.

  1. 보조 페이지 테이블 : 페이지 테이블을 보충해서, 페이지 폴트 핸들링이 가능하도록 해라.
  2. 프레임 테이블 : 물리 프레임의 eviction policy를 효율적으로 구현해라.
  3. 스왑 테이블 : 스왑 슬롯 사용을 추적해라.

2. 구현의 선택지

구현을 위한 가능한 선택지로는 배열, 리스트, 비트맵, 해시 테이블이 있다.

  1. 배열 : 단순한 접근법, 밀도가 희박한 배열은 메모리를 낭비
  2. 리스트 : 단순한 접근법, 특정 위치를 찾기 위해 긴 리스트 순회하는 것은 시간 낭비

공통점과 차이점 : 둘 다 크기의 재조정이 가능하나, 중간 부분의 삽입과 삭제는 리스트가 효율적

  1. 비트맵 : Bitmap.c 와 bitmap.h를 가보면, 비트맵 자료구조를 포함하고 있다. 비트맵은 각각이 true 또는 false값을 가지는 비트들로 이루어진 배열이다. 비트맵은 동일한 자원 집합 내부에서 사용 현황을 추적하기 위해 사용한다. 만약, 자원 n이 사용 중이라면, 비트맵의 비트 n은 true값을 갖는다. 비트맵의 구현을 확장하여 resizing을 지원할 수 있지만 핀토스 비트맵의 크기는 고정되어 있다.

  2. 해시 테이블 : 핀토스는 해시 테이블 자료구조를 포함하고 있다. 핀토스 해시 테이블은 광범위한 테이블 크기에 걸친 삽입과 삭제를 효율적으로 지원한다.

3. 보조 페이지 테이블의 관리

보조 페이지 테이블은 각 페이지에 대한 추가 데이터를 이용해 페이지 테이블을 보충한다. 페이지 테이블 포맷으로 인해 생기는 제한들 때문에 보조 페이지 테이블이 필요하다. 이런 자료구조는 종종 ‘페이지 테이블’로도 불리는데 우리는 혼란을 방지하기 위해 ‘보조’라는 말을 썼다.(각 페이지에 대해 데이터가 어디 존재 하는지(frame, disk, swap 중 어디인지), 이에 상응하는 커널 가상주소를 가리키는 포인터 정보, active or inactive 여부 등)

보조 페이지 테이블은 최소 두 가지 목적으로 쓰인다.

  1. 페이지 폴트가 발생했을 때, 어떤 데이터가 있었어야 했는 지를 알아내기 위해 커널은 보조 페이지 테이블에서 페이지 폴트가 발생한 가상 페이지를 찾는다
  2. 커널이 프로세스가 종료될 때 어떤 자원을 해제할지 고르기 위해 보조 페이지 테이블 사용

😃보조 페이지 테이블의 구조
보조 페이지 테이블을 원하는 대로 구성할 수 있다. 구조에 접근하는 두 가지 기본 방법이 있다. 세그먼트 측면 또는 페이지 측면이다. 여기서 세그먼트는 연속된 페이지 그룹을 이야기한다. 예를 들어, 실행 파일을 포함한 메모리 영역이나, 메모리-맵핑된 파일이 있다.

😃페이지 폴트 다루기
보조 페이지 테이블을 사용하는 핵심 사용자는 페이지 폴트 핸들러. 프로젝트2에서는 페이지폴트는 항상 커널 또는 유저 프로그램의 버그를 의미. 그러나 프로젝트 3에서는 아님!! 이제 페이지 폴트는 오직 페이지를 file 또는 스왑 슬롯에서 가져와야한다는 것을 의미함 이런 경우들을 다루기 위해 더 복잡한 페이지 폴트를 구현해야한다. userprog/exception.c에 있는 페이지 폴트 핸들러는 vm/vm.c 에 있는 vm_try_handle_fault()를 호출함

페이지 폴트 핸들러가 해야 하는 일들을 대략적으로 설명하면 다음과 같다

  1. 보조 페이지 테이블에서 폴트가 발생한 페이지를 찾는다. 만약 메모리 참조가 유효하다면, 보조 페이지 테이블 엔트리를 이용해서 페이지에 들어가는 데이터를 찾아라. 이 데이터는 파일 시스템 안에 있거나 스왑 슬롯에 있거나 단순히 0으로만 채워진 페이지에 있을 수 있다. 만약, copy-on-write와 같은 공유를 구현한다면, 페이지 데이터는 이미 페이지 테이블에 없고 페이지 프레임에 들어가 있을 것. 만약 보조 테이블이 다음과 같은 정보를 보여준다면 유효하지 않은 접근이다.
    1) 유저 프로세스가 접근하려던 주소에서 데이터를 얻을 수 없다.
    2) 페이지가 커널 가상 메모리 영역에 존재한다
    3) 읽기 전용 페이지에 대해 쓰기를 시도한다.

  2. 페이지를 저장하기 위해 프레임을 획득한다. 만약, 공유를 구현했다면 필요한 데이터는 이미 프레임 안에 있다. 이 경우 해당 프레임을 찾을 수 있어야 한다.

  3. 데이터를 파일 시스템 또는 스왑에서 읽거나 0으로 초기화하는 방식 등을 통해 프레임으로 가져온다. 만약 공유를 구현한다면, 필요한 페이지가 이미 프레임 안에 있기 때문에 지금 단계에서는 다른 조치가 필요하지 않다.

  4. 폴트가 발생한 가상주소에 대한 페이지 테이블 엔트리가 물리 페이지를 가리키도록 지정한다. threads/mmu.c에 있는 함수를 사용한다.

😃프레임 테이블의 관리
프레임 테이블에는 각 프레임의 엔트리 정보가 담긴다. 프레임 테이블의 각 엔트리에는 현재 차지하고 있는 페이지에 대한 포인터(있을 때만), 선택에 따라 기타 데이터들이 담긴다. 프레임 테이블은 비어있는 프레임이 없을 때 쫓아낼 페이지를 골라줌으로써, 효율적으로 eviction policy를 구현한다.
유저 페이지를 위해 사용된 프레임들은 palloc_get_page(PAL_USER)을 호출하여 유저 풀에서 획득된 것이어야 한다. 커널 풀에서 할당했다가 예상치 못 하게 테스트 케이스를 종료시키지 못하게 하기 위해 반드시 PAL_USER를 사용해야한다.
프레임 테이블에서 가장 중요한 작업은 사용되지 않는 프레임을 획득하는 것. 프레임이 free 상태라면 간단한 일이다. 하지만 free 상태인 프레임이 없다면, 몇몇 페이지들을 프레임에서 쫓아내어서 그 프레임을 free 상태로 만든다.
만약 스왑 슬롯의 할당없이 쫓아낼 수 있는 프레임이 없는데, 스왑 슬롯 마저 꽉 차 있다면 커널을 패닉 시킬 거다. 실제 OS들은 이런 상황을 막거나 복구하기 위해 다양한 정책들을 적용하고 있지만 이는 프로젝트 범위 벗어나니까 하지마라.

👋Eviction policy👋는 다음과 같다

  1. 페이지 재배치 알고리즘을 이용해 쫓아낼 프레임을 고른다. 아래 설명할 “accessed”, “dirty”비트들이 유용할 거다.

  2. 해당 프레임을 참조하는 모든 페이지 테이블에서 참조를 제거한다. 공유를 구현하지 않았다면, 해당 프레임을 참조하는 페이지는 항상 한 개만 존재해야 한다.

  3. 필요하다면, 페이지를 파일 시스템이나 스왑에 write한다. 쫓아내어진 프레임은 이제 다른 페이지를 저장하는데 사용할 수 있다.

👏Accessed and Dirty Bits👏
X86-64 하드웨어는 각 페이지의 페이지 테이블 엔트리(PTE)에 있는 비트쌍을 통해 페이지 재배치 알고리즘 구현을 위한 도움을 제공한다. 페이지에 read 하거나 write할 때, CPU는 페이지의 PTE에 있는 accessed 비트를 1로 설정한다. 그리고 write할 때 cpu는 dirty bit를 1로 설정한다. CPU는 절대 이 비트들을 0으로 되돌리지 않고, 대신 OS가 되돌린다.

같은 프레임을 참조하는 두 개(또는 그 이상의)의 페이지들인 aliases들을 조심해야한다. 동료 프레임이 accessed 될 때, accessed 와 dirty 비트는 (access에 쓰인 페이지만) 오직 한 페이지 테이블 엔트리에서만 업데이트된다. 다른 aliases의 accessed and dirty 비트는 업데이트 되지 않는다.
핀토스에서 모든 유저 가상 페이지는 커널 가상 페이지와 동료(aliased)로 맺어져있다. 당신은 반드시 이 동료관계를 관리해야한다. 예를 들어, 코드가 양쪽 주소 모두를 위한 accessed와 dirty 비트를 확인하고 업데이트 할 수 있어야한다. 다른 방법으로는 커널이 오직 유저 가상주소를 통해서만 유저 데이터에 접근하게 하여 이 문제를 피할 수 있다.

😃스왑 테이블의 관리😃
스왑테이블은 사용중인 스왑 슬롯과 빈 스왑 슬롯들을 추적한다. 프레임에 있는 페이지를 스왑 파티션으로 쫓아내기 위해, 스왑 테이블은 미사용된 스왑 슬롯을 고를 수 있도록 해줘야한다. 페이지가 다시 읽혀서 돌아가거나, 페이지 주인인 프로세스가 종료되어 버릴 경우에는 스왑 테이블이 스왑 슬롯을 free 해줄 수 있어야 한다.
N-MB 스왑 파티션을 포함하는 swap.dsk 라는 이름을 가진 디스크를 생성하기 위해서는 vm/build 경로에서 pintos-mkdisk swap.dsk --swap-size=n 이라는 명령어를 사용해라. 그러면 swap.dsk는 pintos를 실행할 때 자동으로 추가 디스크로 연결된다. 또는 --swap-size=n 명령어를 사용하여 n-MB의 임시 스왑 디스크를 일회성 실행을 위해 사용할 수 있다.
스왑슬롯은 느긋하게 할당되어야한다. 이 말은 eviction에 실제로 필요할 때만 해당되어야 한다는 말이다. 프로세스가 시작될 때 실행파일에서 데이터 페이지들을 읽고 스왑에 곧바로 쓰는 행위는 느긋하지 못한 행위다. 특정 페이지를 저장하기 위해 스왑 슬롯이 예약되어서는 안된다.
스왑 슬롯의 내용물이 프레임으로 읽혀 돌아오면 그 때 스왑 슬롯을 free해주자.

😃메모리-맵핑 파일 관리😃
파일 시스템은 read와 write 시스템 콜에 의해 가장 많이 접근 된다. 두 번째로 많은 인터페이스는 mmap 시스템콜을 사용해 파일을 가상 페이지에 매핑하는 것이다. 그러면 프로그램은 메모리 인스터럭션을 사용할 수 있게 된다. 파일 foo가 0x1000 바이트 크기를 가졌다고 가정하자. 만약 foo가 0x5000주소에서 시작하는 메모리에 맵핑되었다면, 0x5000 ~ 0x5fff 공간에 메모리 접근을 하면 그에 대응되는 foo 파일의 바이트들에 접근 할 것이다.
여기 파일을 콘솔에 출력하기 위해 mmap을 사용하는 프로그램이 있다. 이 프로그램은 커맨드라인에 명시된 파일을 열고, 가상 주소 0x10000000에 맵핑해서 맵핑된 데이터를 콘솔에 write하고(fd1) 파일을 언맵핑한다.

너의 코드는 어떤 메모리가 메모리-맵핑 파일에 의해 사용되었는지를 반드시 추적 할 수 있어야한다. 이는 맵핑된 영역에서 발생하는 페이지 폴트를 적절히 다루는 것이 필요하다. 또한 맵핑된 파일이 프로세스내 어떤 다른 세그먼트들을 덮어 쓰지 않는 것을 보장하는 것이 필요하다.

4. Memory Management

가상 메모리 시스템이 제대로 돌아가기 위해서는 가상페이지와 물리프레임을 효과적으로 관리해야한다. 즉, 사용된 메모리 영역을 어떤 목적으로, 누가 사용했는 지 등을 기록해야 한다. 먼저 보조 페이지 테이블을 다루고 물리 프레임을 다뤄야한다. 우리는 page라는 단어는 가상 페이지를 의미하는 것이며, frame이라는 단어는 물리 페이지를 위한 것이다.

→ spt를 다루고, 물리 프레임을 다루기.
→ struct supplemental_page_table(미구현)
→ spt_find_page(미구현), spt_insert_page(미구현), spt_remove_page
→ initd : supplemental_page_table_init(미구현)
→ do_fork : supplemental_page_table_copy(미구현)
→ process_cleanup : supplemental_page_table_kill(미구현)

😃페이지 구조와 작동(Page Structure and Operations)😃
Struct page : vm.h에 정의되어 있는 page는 가상 메모리에서의 페이지를 의미하는 구조체다. 이 구조체는 page에 대해 우리가 알아야하는 모든 필요한 정보를 담고 있다.
page를 보면 구조체 struct가 아닌 공용체 union을 사용함.
구조체 : 멤버 변수마다 각각 메모리를 할당
공용체 : 멤버 변수 중 가장 메모리 할당량이 큰 변수 하나의 공간만 할당되어 그 메모리 공간을 공유. 메모 리 공간을 공유하기 때문에 유니온은 멤버 변수를 하나씩밖에 사용 못 함. 만약 uninit_page가 사용중이면, anon_page는 사용할 수 없음.

page구조체는 page operation, virtual address, physical frame을 갖는다. 추가적으로 이 구조체는 union멤버도 갖는다. 유니언 자료형은 하나의 메모리 영역에 다른 타입의 데이터를 저장하는 것을 허용하는 특별한 자료형이다. 하나의 유니온은 여러 개의 멤버를 가질 수 있지만, 한번에 하나의 멤버만 값을 갖는다. 즉, 페이지는 우리 시스템 상 uninit_page, anon_page, file_page 또는 page_cache 중 하나다. 예를 들어, 만약 페이지가 anonymous page라면 page struct는 멤버로서 struct anon_page anon의 영역을 가질 것이다. anon_page는 anonymous page 구성을 위한 모든 필요한 정보들을 포함하고 있다.

😃페이지 작동(Page Operations)
페이지는 VM_UNINIT, VM_ANON, VM_FILE 중 하나다. 페이지는 swap in, swap out, 또는 페이지 삭제 등 다양한 액션을 취한다. 페이지의 각 타입별로 필요한 과정과 task는 액션마다 다르다. 달리 말하면, VM_ANON 페이지와 VM_FILE 페이지에서 발생하는 destroy 함수는 다르다. 각각의 케이스를 다루기 위해 switch-case 구문을 사용하는 방법이 있다. 이 문제를 해결하는 방법으로 객체지향 프로그래밍 “클래스 상속”이 있다. C언어에는 클래스나 상속이라는 개념이 없지만 우리는 ‘함수 포인터’를 사용해 리눅스 os코드와 비슷하게 클래스 상속을 구현한다.
함수 포인터는 단지 함수 혹은 메모리에 있는 실행 가능한 코드를 가르키는 포인터다. 함수 포인터는 검사 없이 런타임에 결정되는 값을 바탕으로 특정한 함수를 호출하는 간단한 방법을 제공하기 때문에 유용하다. 우리의 케이스에서 코드레벨에서 destroy(page)를 호출하는 것만으로 충분하다. 컴파일러는 적절한 함수 포인터를 호출하여 페이지 타입에 따라 적절한 destroy 루틴을 선택할 것이다.
→ 페이지는 uninit, anon, file 세 가지 종류 중 하나. 하나의 페이지가 여러 동작을 하기 때문에 클래스 상속을 구현해서 각 다른 동작을 행하게 해야 함.

Page 구조체의 멤버인 struct page_operations는 include/vm/vm.h에 정의되어 있다. 이 구조체를 3개의 함수 포인터를 포함한 하나의 함수 테이블로 이해해라.

Vm/file.c에 가보면, page_operations 구조체인 file_ops가 함수 프로토 타입들을 선언하기 전에 선언되어 있다. 이는 file-backed 페이지에 대한 함수 포인터 테이블이다. destroy필드는 file_backed_destroy라는 값을 갖는데 이는 페이지를 삭제하는 함수고 같은 파일 안에 정의되어있다.

함수 포인터로 어떻게 file_backed_destroy가 호출되는지 보자. vm_dealloc_page(page)는 인자로 받은 페이지가 file-backed page(VM-FILE)가 된다. 함수 안에서 destroy(page)를 호출하고 destroy는 다음과 같다.
#define destroy(page) if ((page)->operations->destroy) (page)->operations->destroy (page)

보조 페이지 테이블 구현하기(Implement Supplemental Page Table)
가상 메모리와 물리 메모리를 맵핑하는 것을 관리하는 pml4라는 페이지 테이블이 있을 것이다. 하지만 이걸로는 충분하지 않다. 페이지 폴트와 자원 관리를 처리하기위해서는 각 페이지에 대한 추가 정보를 담고 있는 보조 페이지 테이블이 필요하다. 보조 페이지 설계를 마친 후, 아래 3가지 함수를 구현해라!
Void supplemental_page_table_init
→ 보조 페이지 테이블 초기화 함수. 어떤 자료 구조로 구현할지 선택해라. 새로운 프로세스가 initd 함수로 시작하거나 do_fork로 생성될 때 위의 함수가 호출된다.
Struct page spt_find_page
→ 인자로 넘겨진 보조 테이블 페이지로부터 가상 주소와 대응되는 페이지 구조체를 찾아서 반환한다. 실패했을 경우 NULL로 반환한다.
Bool spt_insert_page
→ 위의 함수는 인자로 주어진 보조 테이블 페이지에 페이지 구조체를 삽입한다. 이 함수는 주어진 보조 페이지 테이블에서 가상 주소가 존재하지 않는 지 체크한다.

프로세스마다 각 페이지에 대한 보조 데이터를 추적할 수 있는 데이터 구조가 필요함. 예를 들어 데이터의 위치(frame, disk, swap), kva를 가르키는 포인터, active 상태인지 inactive상태인지.(데이터 구조는 뭐로하지?)

😃프레임 관리(Frame Management)
지금부터 모든 페이지는 페이지가 처음 만들어졌을 때의 메모리에 대한 메타 정보만을 갖지 않습니다. 그래서 우리는 물리 메모리를 관리하는 다른 방식이 필요하다. frame 구조체는 오직 2개의 멤버를 갖는다. kva는 커널 가상 주소, page는 페이지 구조체를 담기 위한 멤버다.
Frame은 멤버로 kva와 page를 갖는다. 프레임 관리 인터페이스를 구현하는 과정에서 다른 멤버들을 추가할 수 있다.

static struct frame *vm_get_frame (void)

→ palloc_get_page 함수를 호출하여, 메모리 풀에서 새로운 물리 메모리 페이지를 가져온다. 유저 메모리 풀에서 페이지를 성공적으로 가져오면, 프레임을 할당하고 프레임 구조체 멤버들을 초기화하고 해당 프레임을 반환한다. frame *vm_get_frame 함수를 구현한 후에는 모든 유저 공간 페이지들을 이 함수를 통해 할당해야 한다. 지금은 페이지 할당이 실패했을 떄, swap out를 할 필요 없고 일단은 PANIC(”todo”)으로 해라.

Bool vm_do_claim_page(struct page *page)

→ 인자로 주어진 page를 물리 메모리 프레임에 할당한다. vm_get_frame 함 수를 호출하여 프레임을 얻고 그 이후 MMU를 세팅해야 한다. 이는 페이지 테이블에 있는 가상 메모리 주소와 물리 메모리 주소를 맵핑해야한다. 추가가 성공했다면, true를 반환하고 그렇지 않다면 false를 반환해라.

profile
Moon
안녕하세요. Moon입니다!
이전 포스트

PintOS. User Program 구현하기

다음 포스트

PintOS. Virtual Memory 구현하기(Anonymous Page)

0개의 댓글