pintOS | Project 3 | Introduction

 

pintos-kaist project 3 gitbook ↓

Introduction · GitBook

 

※ 해석 내 멋대로임. 수정 및 보완 부분 있으면 알려주세여

 

Project 3: Virtual Memory

프로젝트 2까지 완료했으면 os는 적절한 동기화로 실행하는 여러 스레드들을 다룰 수 있고, 여러 유저 프로그램을 로드시킬 수 있다. 그러나, 실행할 수 있는 프로그램의 수와 사이즈는 머신의 메인 메모리 사이즈에 따라 제한된다. 이번 프로젝트에서는 이 제한을 없애야 한다.

 

프로젝트 3을 하기 전에 프로젝트 2에서의 문제는 해결해야 한다.

 

Source Files

이번 프로젝트는 vm 디렉토리에서 진행한다. 주의할 점은 주어진 템플릿을 반드시 따라야 한다는 것. 그렇지 않다면 pass 안 될 것이다. 또한 "DO NOT CHANGE"라고 적힌 부분은 절대 바꾸지 마라.

 

우리가 수정해야 할 부분:

• include/vm/vm.h, vm/vm.c
  가상 메모리의 일반적인 인터페이스 제공하는 파일
  헤더 파일에서 vm_type -- VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE의 정의와 설명을 볼 수 있음
  (VM_PAGE_CACHE는 project 4에서 다룰 것. 지금은 무시)
  또한 page table 구현도 여기서 할 것임
• include/vm/uninit.h, vm/uninit.c
  초기화되지 않은 페이지(vm_type = VM_UNINIT)에 대한 작업을 제공
  현재까지 코드에서 모든 페이지들은 초기화 되어 있지 않은 상태로 세팅되어 있고, anonymous pages나 file-backed pages로 변환됨
• include/vm/anon.h, vm/anon.c
  anonymous pages에 대한 작업을 제공(vm_type = VM_ANON)
• include/vm/file.h, vm/file.c
  file-backed pages에 대한 작업을 제공(vm_type = VM_FILE)
• include/vm/inspect.h, vm/inspect.c
  메모리 검사 작업. Do not change this file!!!

 

수정해야 할 파일들은 대부분 vm 디렉토리에 있다. 아마 이런 파일들이 발생할 수도 있다.

• include/lib/kernel/bitmap.h, include/lib/kernel/bitmap.c
  bitmap device에 대한 섹터 기반의 읽기과 쓰기 제공. swap partition에 bitmap device로 접근하기 위해 이 인터페이스를 사용할 것

 

 

메모리 관련 용어 설명

| Pages

가상 페이지라고도 불리는 page는 가상 메모리의 연속적인 영역이며, 페이지 사이즈는 4,096 bytes이다. 페이지는 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작해야 한다. 따라서 64비트 가상 주소의 마지막 12비트는 page offset이다. 그 위의 비트는 페이지 테이블의 인덱스를 나타내는 데 사용된다. 64비트 시스템에서 우리는 4-level-page table을 사용한다. 

 

 

각각의 프로세스는 유저 페이지의 독립적인 집합을 가지고 있다. 이 페이지들은은 가상 주소 KERN_BASE(0x8004000000) 아래에 있다.

 

반면에 커널 페이지의 집합은 전역적이며, 어떤 프로세스가 실행되든 상관 없이 같은 위치에 남아 있다. 커널은 유저 페이지나 커널 페이지에 접근하지만 유저 프로세스는 오직 자신의 유저 페이지에만 접근한다.

 

 

| Frames

프레임(called a physical frame or a page frame)은 물리 주소의 연속적인 영역이다. 페이지처럼 프레임도 페이지 사이즈로 균등하게 나누어져야 한다. 따라서, 64비트 물리 주소는 frame number와 frame offset으로 분할될 수 있다.

 

 

x86-64 는 물리 주소에 어떤 직접적인 접근도 제공하지 않는다. pintos는 물리 메모리에 커널 가상 메모리를 매핑하면서 작업한다. 커널 가상 메모리의 첫 페이지는 물리 메모리의 첫 번째 프레임과 매핑되고 두 번째 페이지는 두 번째 프레임... 이런 식으로 매핑된다. 따라서 프레임은 커널 가상 메모리를 통해 접근할 수 있다.

 

 

| Page tables

페이지 테이블은 CPU가 가상 주소를 물리주소로 변환하는데 사용하는 자료 구조이다. 페이지 테이블 포맷은 x86-64 아키텍처에 의해 결정된다. pintos는 페이지 테이블을 관리하는 코드를 threads/mmu.c에서 제공한다.

 

아래 그림은 페이지들과 프레임들의 관계를 보여준다. 왼쪽의 가상 주소는 page number와 offset으로 구성된다. 페이지 테이블은 페이지 번호를 프레임 번호로 변환하며, 오른쪽에 물리 주소를 얻기 위해 수정되지 않은 offset과 결합된다.

 

 

 

| Swap slots

swap slot은 swap partition에서 디스크 공간의 페이지 사이즈 영역이다. 슬롯 배치를 결정하는 하드웨어 제한이 프레임보다 유연하더라도, swap slots는 페이지를 정렬해야 한다. (단점이 없음??)

 

 

| Resource management overview

아래의 자료 구조를 따라 구현해야 한다.

 

Supplemental page table

Enables page fault handling by supplementing the page table. See Managing the Supplemental Page Table below.

Frame table

Allows efficient implementation of eviction policy of physical frames See Managing the Frame Table below.

Swap table

Tracks usage of swap slots. See Managing the Swap Table below.

이 세 가지 자료 구조를 구현할 필요는 없다.

 

각 데이터 구조에 대해 각각의 요소가 포함해야 하는 정보를 결정할 필요가 있다. 또한 로컬, 글로벌 데이터 구조의 범위와 해당 범위에 필요한 인스턴스 수를 결정해야 한다.

 

구현을 쉽게 하려고 non-pageable memory(e.g. calloc, malloc)에 자료 구조를 저장할 수도 있다. 그것은 그들 중 포인터가 유효하게 남아있다는 것을 확인할 수 있다 (????)

 

 

| Choices of implementation (Performance perspective)

구현을 위해 선택 가능한 것은 arrays, lists, bitmaps, hash tables이다. 

• array: 단순한 접근이지만 희박한? 배열은 메모리를 낭비한다.
• lists: 리스트 역시 심플하지만 길이가 긴 리스트에서 특정한 위치를 찾게 되면 시간이 낭비된다. 배열과 리스트 둘다 리사이즈할 수 있지만, 리스트가 삽입과 삭제에 더 효율적이다.
• bitmap: 비트맵 자료 구조는 lib/kernel/bitmap.c와 include/lib/kernel/bitmap.h에 있다. 비트맵은 비트의 배열이고, 이것은 각각 true거나 false가 될 수 있다. 비트맵은 전형적으로 일련의 자원 사용량을 추적하는데 사용된다.
  (만약 자원 n이 사용이라면, bit n은 true)
  pintos에서 비트맵은 사이즈가 고정되어 있다.
• hash table: 핀토스에서 해시 테이블은 넓은 범위의 테이블 사이즈에서 삽입과 삭제를 효율적으로 지원한다.

필요 이상으로 복잡해질 수 있기 때문에 이 자료구조들은 따로 구현하지 않는 것이 좋다.

 

 

| Managing the supplemental page table

supplemental page table은 각각의 페이지에 대해 추가적인 데이터로 페지이 테이블을 보완한다. 이는 페이지 테이블 형식으로부터 부과된 제한 때문에 필요하다. 이 자료 구조는 가끔 page table로 불리지만, 혼동을 줄이기 위해 supplemental을 붙힌다.

 

 

supplemental page table은 최소 두 가지 용도로 사용된다.

1. page fault 상황에서 커널은 supplemental page table에서 fault된 가상 페이지를 찾는다. 
2. 페이지가 종료될 때, 자원 할당을 해제하기 위해 커널은 supplemental page table을 설계한다.

 

 

| Organization of supplemental page table

supplemental page table은 원하는대로 구성할 수 있고, 세그먼트 측면, 페이지 측면 등 최소 두 가지 방식으로 접근한다. 여기서 세그먼트는 연속적인 페이지들의 그룹(실행파일 또는 메모리 매핑 파일이 포함된 메모리 영역)을 나타낸다.

 

선택적으로 supplemental page table의 멤버들을 추적하기 위해 페이지 테이블 자체를 사용할 수도 있다. 이를 위해서 threads/mmu.c에서 pintos page table을 수정해야 한다.

 

 

| Handling page fault

supplemental page table의 가장 중요한 사용자는 page fault handler이다. 프로젝트 2에서 페이지 폴트는 항상 커널이나 유저 프로그램에서 나타나는 버그였다. 프로젝트 3에서는 더 이상 그러지 않다. 페이지 폴트는 오직 오직 파일이나 스왑 슬롯에서 페이지를 가져와야 한다는 것을 나타난다. 이러한 사례들을 처리하기 위해서 더 정교한 페이지 폴트 핸들러는 구현해야 한다. 페이지 폴트 핸들러(page_fault() in userprog/exception.c)는 너의 페이지 폴트 핸들러(vm_try_handle_fault() in vm/vm.c)를 호출한다. 뭔 소리여 시부레

너의 페이지 폴트 핸들러(your page fault handler?)는 다음과 같은 작업들을 수행할 필요가 있다.

1.  supplemental page table에서 폴트난 페이지를 찾는다. 메모리 참조가 유효하다면, 페이지에 있는 데이터(파일 시스템이나 스왑 슬롯에 있거나, all-zero 페이지일지도 모름)를 찾기 위해 supplemental page table의 엔트리를 사용한다. 만약 공유(i.e. copy on write)하는 것을 구현한다면, 데이터의 페이지는 이미 페이지 프레임 안에 있을 수 있지만 페이지 테이블에는 없을 수 있다. 만약 supplemental 페이지 테이블이 유저 프로세스가 접근하려는 주소에 어떤 데이터도 없어야 한다고 하는 경우, 또는 페이지가 커널 가상 메모리 내에서 있는 경우, 또는 접근이 read-only page에 write하는 것을 시도하는 경우, 그 접근은 유효하지 않다. 유효하지 않은 접근은 프로세스를 종료하고 모든 자원들을 확보한다.   누가 번역 수정 좀;;
2. 페이지 저장을 위한 프레임을 얻는다. 만약 공유하는 것을 구현한다면, 필요로 하는 데이터는 이미 프레임 안에 있을 수 있으며, 이러한 경우 그 프레임을 찾을 수 있어야 한다.
3. file system, swap, zeroing it 등으로부터 프레임에 데이터를 가져온다. 만약 공유하는 것을 구현한다면, 필요로 하는 데이터는 이미 프레임 안에 있을 것이며 이 경우 따로 작업을 할 필요가 없다.
4. 폴트가 있는 가상 주소에 대한 페이지 테이블 엔트리를 물리 페이지로 가리킨다. threads/mmu.c에 있는 함수를 사용할 수 있다.

 

 

Frame table 관리

프레임 테이블은 각각의 프레임에 하나의 엔트리를 가진다. 프레임 테이블에 있는 각각의 엔트리는 현재 해당 페이지를 점유하고 있는 페이지의 포인터와 우리가 선택한 기타 데이터를 가진다. 그 프레임 테이블은 사용 가능한 프레임이 없을 때 제거할 페이지를 선택함으로써 pintos가 enviction policy를 효율적으로 구현하도록 한다. 

 

유저 페이지에 사용되는 프레임들은 palloc_get_page(PAL_USER) 호출을 통해 "user pool"로부터 차지되어야 한다. "kernel pool"으로부터 할당되는 것을 피하기 위해 반드시 PAL_USER를 사용해야 한다. palloc.c를 수정한다면, 유저풀과 커널풀 간의 차이를 유지해야 한다. (건드리지 말라는 얘긴가?)

 

프레임 테이블에서 가장 중요한 작업은 사용되지 않는 프레임을 가지는 것이다. 프레임이 비어 있다면 쉽다. 프레임이 비어 있지 않다면, 프레임은 프레임의 일부 페이지를 제거하여 비할당 공간을 만들어야 한다.

 

만약 프레임이 swap slot을 할당하지 않고 제거될 수 없는데 스왑이 가득 찼다? 커널 패닉.

(이런 경우는 이번 프로젝트 벗어남 ㅇㅋ)

 

process of eviction은 다음과 같은 단계로 구성된다.

1. 페이지 교체 알고리즘을 사용하여 제거할 프레임을 선택한다. 페이지 테이블에 있는 "accessed" 및 "dirty" 비트는 유용할 것이다.
2. 프레임을 참조하는 페이지 테이블로부터 프레임에 대한 참조를 제거한다. 공유를 구현하지 않는다면 싱글 페이지만 특정 시간에 프레임을 참조할 수 있다.
3. 필요하다면 파일 시스템이나 스왑에 페이지를 쓴다(write). 제거된 프레임은 다른 페이지를 저장하는 데 사용될 것이다.

 

 

| Accessed and dirty bits

x86-64 하드웨어는 각 페이지의 페이지 테이블 엔트리(PTE)에 있는 한 쌍의 비트를 통해 페이지 교체 알고리즘 구현에 일부 지원을 제공한다. 페이지를 읽기나 쓰기에서 CPU는 페이지의 PTE에서 엑세스한 비트를 1로 설정하고, 쓰기에서 CPU는 dirty 비트를 1로 재설정한다. CPU는 이러한 비트를 0으로 재설정하지 않지만 OS는 재설정할 수 있다.

 

같은 프레임을 참조하는 두개 이상의 페이지들인 aliases를 인지할 필요가 있다. aliased frame이 접근될 때, accessed and dirty bits는 오직 하나의 페이지 테이블 엔트리에 업데이트된다. 다른 aliases에 대한 accessed 비트와 dirty 비트는 업데이트 되지 않는다. 

 

pintos에서 모든 유저 가상 페이지는 커널 가상 페이지와 aliased 관계가 있다. aliases를 관리해야 한다.

(예를 들어, 코드는 두 주소에 대한 액세스 비트와 더티 비트를 확인하고 업데이트할 수 있습니다. 또는 커널은 사용자 가상 주소를 통해서만 사용자 데이터에 액세스하여 문제를 방지할 수 있습니다.)

 

다른 aliases는 공유를 구현하거나 코드에 버그가 있는 경우 발생한다.

 

 

| Managing the swap table

swap table은 사용 중인 스왑 슬롯과 사용 가능한 스왑 슬롯을 추적한다. 프레임에서 스왑 파티션으로 페이지를 제거할 때 사용되지 않는 스왑 슬롯을 선택해야 한다. 페이지를 다시 읽거나 페이지가 스왑된 프로세스가 종료될 때 스왑 슬롯을 비워도록 해야 한다.

 

VM/build 디렉토리에서 pintos-swap.dsk --swap-size=n 명령을 사용하여 n-MB 스왑 파티션이 포함된 swap.dsk 디스크를 만든다. 나중에 핀토스를 실행하면 swap.dsk가 추가 디스크에 자동으로 연결된다. 또는 핀토스에게 --devol-size=n으로 단일 실행에 일시적인 n-MB 스왑 디스크를 사용하도록 지시할 수 있다.

 

스왑 슬롯은 실제로 퇴출에 필요한 경우에만 lazily하게 할당되어야 한다. 실행 파일에서 데이터 페이지를 읽고 프로세스 시작 시 즉시 스왑할 수 있도록 쓰는 것은 lazy하지않다. 특정 페이지를 저장하기 위해 스왑 슬롯을 예약하면 안 된다.

 

스왑 슬롯의 콘텐츠가 다시 프레임으로 읽게 되면 스왑 슬롯을 비운다.

 

 

| Managing memory mapped files

파일 시스템은 대부분 read, write 시스템 콜과 함께 접근된다. 부차적인 인터페이스는 mmap 시스템 콜을 사용하여 파일을 가상 페이지로 매핑하는 것이다. 그러고 나서 프로그램은 파일 데이터에 직접 메모리 인스트럭션을 사용할 수 있다.

foo 파일이 0x1000 byte(4KB, or one page)라고 가정해보자. 만약 foo 파일이 0x5000 주소에서 시작하는 메모리에 매핑되었다면, 다른 메모리는 foo 파일의 바이트에 상응하는 0x5000.. 0x5fff 위치에 접근한다.(이 부분 해석 제대로 된 건지 모르겠다.)

 

다은은 mmap을 사용하여 콘솔에 파일을 프린트하는 프로그램이다. 이것은 커맨드 라인에서 지정된 파일을 열고 가상 주소 0x10000000에서 매핑하고, 매핑된 데이터를 콘솔(fd1)에 write한 다음 파일 매핑을 해제한다.

 

#include <stdio.h>
#include <syscall.h>
int main (int argc UNUSED, char *argv[])
{
  void *data = (void *) 0x10000000;                 /* Address at which to map. */
  int fd = open (argv[1]);                          /* Open file. */
  void *map = mmap (data, filesize (fd), 0, fd, 0); /* Map file. */
  write (1, data, filesize (fd));                   /* Write file to console. */
  munmap (map);                                     /* Unmap file (optional). */
  return 0;
}

 

제출 시 메모리 매핑 파일에서 사용되는 메모리를 추적할 수 있어야 한다. 이것은 매핑된 영역의 페이지 폴트를 올바르게 처리하고 매핑된 파일이 프로세스 내의 다른 세그먼트와 겹치지 않도록 하기 위해 필요하다.