PintOS - Project 3: Virtual Memory (Review)

PintOS의 메모리 주소공간은 4개의 세그먼트로 구성되어 있다: Stack, Initialized Data, Uninitialized Data, Code 영역이 존재하며 Heap 영역은 존재하지 않는 상태이다.

각 세그먼트가 물리 페이지에 탑재되고 페이지 테이블이 초기화 되는 방식으로 프로세스의 메모리 탑재 과정이 이뤄진다.

기존의 PintOS 프로세스 주소공간은 가상주소와 물리주소를 맵핑하는 페이지 테이블을 통해 물리 메모리에 접근하여 디스크로부터 텍스트(파일)와 데이터를 불러온다.

기존의 PintOS 주소공간은 요구 페이징과 스왑을 사용할 수 없으며 가상 메모리가 구현되어 있지 않다.

요구 페이징

요구 페이징이란 프로세스가 요청한 페이지들만 저장 공간으로부터 물리 프레임을 할당하여 물리 메모리에 로드하는 기법이다.

먼저 인스트럭션이 실행되면 가상주소로부터 가상 페이지 번호를 추출한다.

추출한 가상 페이지 번호를 통해 페이지 테이블을 참조하여 맵핑된 물리 프레임이 존재하는지 확인한다.

물리 프레임이 존재하지 않을 시 페이지 폴트가 발생한다.

페이지 폴트가 발생하면 물리 프레임을 할당하고 페이지 테이블을 갱신한다.

해당 페이지를 디스크에서 생성된 프레임에 탑재한다.

페이지에 대한 정보를 포함하는 vm_entry를 해시 테이블의 형태로 관리한다.

가상주소 페이지 별 자료구조 vm_entry를 정의한다.

vm_entry는 페이지 당 하나씩 존재하며 각 페이지의 파일 포인터, 오프셋, 크기를 저장한다.

프로그램 초기 탑재시 가상 주소공간 각 페이지에 vm_entry를 할당한다.

프로그램 실행시 페이지 테이블을 탐색하고 페이지 폴트가 발생하면 가상주소에 해당하는 vm_entry를 탐색한다.

vm_entry가 존재하지 않는 가상주소를 세그멘테이션 폴트가 발생한다.

vm_entry가 존재할 경우 페이지 프레임을 할당하고 vm_entry에 저장된 파일 포인터, 읽기 시작할 오프셋, 읽어야 할 크기 등을 참조해서 물리 프레임을 로드한다.

물리 프레임을 로드하면 페이지 테이블을 갱신한다.

load_segment() 함수는 코드 및 데이터 세그먼트를 읽어들인다.

setup_stack() 함수는 스택에 물리 프레임을 할당한다.

디스크 이미지의 세그먼트를 전부 탑재하는 것은 물리 메모리를 비효율적으로 사용하는 방식이다.

물리 메모리를 할당하는 대신 가상 페이지마다 vm_entry를 통해 적재할 정보들만 관리한다.

요구 페이징을 사용하여 요청한 페이지에 대해서만 물리 페이지 할당을 수행한다.

페이지 폴트가 발생하면 해당 페이지의 vm_entry의 존재 유무를 확인한다.

vm_entry의 가상주소에 해당하는 물리 프레임을 할당한다.

vm_entry 정보를 참조하여 디스크에 저장되어 있는 실제 데이터를 물리 메모리에 로드한다.

thread 구조체의 멤버인 해시 테이블 구조체 vm의 buckets 각 bucket은 vm_entry들을 저장한다.

vm_entry

가상 메모리 가상 페이지 상의 가상주소를 접근하여 페이지 테이블을 참조한다.

프레임 번호와 유효 비트를 확인하여 맵핑이 되어있지 않은 경우 페이지 폴트가 발생한다.

가상주소는 페이지 테이블 인덱스와 페이지 오프셋으로 구성되어 있다.

페이지 오프셋은 해당 프레임의 첫 주소를 0으로 봤을 때의 주소를 의미한다.

프레임 넘버와 페이지 오프셋을 더한 값은 물리 주소와 일치한다.

thread 구조체는 페이지 디렉토리 pagedir(pml4)를 포함하고 있으며 페이지 디렉토리는 페이지 테이블을 효율적으로 관리하기 위한 구분이다.

가상주소 페이지는 3가지 타입으로 분류되며 vm_entry의 type 필드에 가상주소의 타입을 정수 값으로 저장한다.

VM_BIN은 바이너리 파일로부터 데이터를 로드한다.

VM_FILE은 맵핑된 파일로부터 데이터를 로드한다.

VM_ANON은 스왑 영역으로부터 데이터를 로드한다.

uint8_t type은 가상주소 페이지의 타입을 저장한다.

void *vaddr은 vm_entry가 관리하는 가상 페이지의 번호를 저장한다.

bool writable은 해당 주소의 쓰기 가능 여부를 저장한다.

bool is_loaded 물리 메모리의 탑재 여부를 저장한다.

struct file *file 가상주소와 맵핑된 파일을 저장한다.

size_t offset 읽어야 할 파일의 오프셋을 저장한다.

size_t read_bytes 가상 페이지에 쓰여져 있는 데이터의 크기를 저장한다.

size_t zero_bytes 0으로 채울 남은 페이지의 바이트를 저장한다.

struct hash_elem elem 해시 테이블의 element를 저장한다.

메모리를 접근할 시 해당 주소의 가상 페이지를 표현하는 vm_entry를 탐색한다.

탐색이 빠른 해시 테이블의 형태로 vm_entry를 관리하며 vaddr로 해시 값을 추출한다.

thread 구조체에 해시 테이블 자료구조 vm 추가한다.

프로세스 생성 시 해시 테이블을 초기화하고 vm_entry들을 해시 테이블에 추가하도록 수정한다.

프로세스 실행 중 페이지 폴트 발생 시 vm_entry를 해시 테이블에서 탐색하도록 수정한다.

프로세스 종료 시 해시 테이블의 bucket 리스트와 vm_entry들을 제거하도록 수정한다.

프로세스마다 가상주소 공간이 할당되므로 가상 페이지들을 관리할 수 있는 자료구조인 해시 테이블을 정의한다.

가상 주소공간 초기화

1. 디스크로부터 물리 메모리에 물리 페이지를 할당한다.

2. 4KB 크기의 파일의 내용을 읽어서 물리 메모리에 적재한다.

3. 페이지 테이블에 가상주소와 물리주소를 맵핑한다.

파일의 포인터, 파일의 오프셋, 읽어야 할 크기 등 정보를 vm_entry에 저장한다.

물리 프레임은 가상주소에 접근할 때 할당한다.

가상주소 접근 시, 물리 프레임이 맵핑되어 있지 않다면 해당 가상주소에 해당하는 vm_entry 탐색 후 vm_entry 정보들을 참조하여 디스크의 데이터를 읽어 물리 프레임에 탑재한다.

• static bool load_segment(struct file file, off_t ofs, uint8_t upage, uint32_t read_bytes, uint32 zero_bytes, bool writable)

load_segment()는 ELF 포맷 파일의 세그먼트를 프로세스 가상 주소공간에 탑재하는 함수이다.

프로세스 가상 메모리 관련 자료구조를 초기화하는 기능을 추가한다.

프로세스 가상 주소공간에 메모리를 탑재하는 부분을 제거하고, vm_entry 구조체의 할당, 필드값 초기화, 해시 테이블 삽입을 추가한다.

• bool setupstack(struct intr_frame *if)

setup_stack()은 스택 초기화하는 함수이다.

단일 페이지를 할당하고 페이지 테이블과 스택 포인터 esp를 설정하는 부분을 제거하고 4KB 스택의 vm_entry를 생성하고 생성한 vm_entry의 필드값을 초기화하고 vm 해시 테이블에 삽입하도록 변경한다.

가상주소 유효성 검사

가상주소 유효성 검사란 가상주소에 해당하는 vm_entry가 존재하는지 검사하는 것을 의미한다.

시스템 콜(read()/write()) 사용 시 인자로 주어지는 문자열이나 버퍼의 주소에 해당하는 vm_entry기 존재하는지 검사한다.

esp에 대한 유저 메모리 영역을 확인하는 check_address() 함수를 수정한다.

vm_entry를 사용하여 유효성 검사 작업을 수행하고 vm_entry를 반환하도록 변경한다.

read() 시스템 콜의 버퍼의 주소가 유효한 가상주소인지 검사하는 check_valid_buffer() 함수를 추가한다.

요구 페이징 구현

1. 물리 메모리 접근 및 페이지 폴트 page_fault()

2. vm_entry 확인 spt_find_page()

3. 메모리 할당 vm_try_handle_fault()

4. 디스크에서 물리 메모리로 데이터 로드 load()

5. 페이지 테이블 설정 install_page()

page_fault()는 페이지 폴트 발생 시 처리를 위한 함수이다.

fault_addr의 유효성을 검사하고 페이지 폴트 핸들러 함수를 호출한다.

• static bool load(const char file_name, struct intr_frame if_)

load()는 디스크에 존재하는 페이지를 물리 메모리로 로드하는 함수이다.

vme의 <파일, 오프셋>으로 한 페이지를 file_read() + file_seek() 함수를 이용하여 kaddr로 읽어 들이는 함수를 구현한다.

4KB의 크기를 전부 write하지 못했다면 나머지를 0으로 채운다.

• static bool install_page(void upage, void kpage, bool writable)

install_page()는 페이지 테이블에 물리주소와 가상주소를 맵핑시키는 페이지 주소 맵핑 함수이다.

인자로 입력 받은 물리 페이지 kpage와 가상 페이지 upage를 맵핑한다.

PintOS는 페이지 테이블과 페이지 디렉토리를 이용해서 물리주소와 가상주소의 맵핑을 관리한다.

페이지 디렉토리는 페이지 테이블의 주소를 갖고 있는 테이블이다.

페이지 테이블은 가상주소에 맵핑된 물리주소를 갖고 있는 엔트리들의 집합이다.

• void *palloc_get_page(enum palloc_flags flags)

palloc_get_page() 함수는 4KB 크기의 페이지를 할당하고 페이지의 물리주소를 리턴한다.

인자 flags는 PAL_USER, PAL_KERNEL, PAL_ZERO 세 가지 타입을 가진다.

PAL_USER: 유저 메모리풀에서 페이지 할당
PAL_KERNEL: 커널 메모리 풀에서 페이지 할당
PAL_ZERO: 페이지를 '0'으로 초기화

• void palloc_free_page(void *page)

palloc_free_page() 함수는 페이지의 물리주소를 인자로 사용하고 페이지를 다시 여유 메모리 풀에 넣는다.

Memory Mapped File

요구 페이징에 의해 파일 데이터를 메모리로 로드하는 mmap() 함수와 파일 맵핑을 제거하는 munmap() 함수를 구현한다.

Treat file I/O as routine memory access by mapping a disk block to a page in memory

파일 입출력을 디스크 블록과 페이지의 맵핑을 통한 메모리에 대한 접근으로 생각한다.

A file is initially read using demand paging

파일은 요구 페이징을 이용해 읽도록 한다.

Simplifies file access by treating file I/O through memory rather than read() and write() system calls

파일에 대한 접근을 read() 또는 write() 시스템 콜이 아닌 메모리를 통한 파일 입출력으로 생각한다.

Also allows several processes to map the same file allowing the pages in memory to be shared

여러 프로세스가 같은 파일을 맵핑하도록 하고 페이지가 메모리에 공유되는 것을 가능하게 한다.

To allow more convenient access to I/O devices, many computer architectures provide memory-mapped I/O.

입출력 장치에 대한 접근을 용이하게 하기 위해 많은 컴퓨터 아키텍쳐는 메모리 맵핑 입출력을 제공한다.

In this case, ranges of memory addresses are set aside and are mapped to the device registers.

Read and writes to these memory addresses cause the data to be transferred and from the device registers.

메모리 주소를 읽고 쓰는 것은 장치 레지스터로부터 데이터의 이동을 유발한다.

This method is appropriate for devices that have fast response times, such as video controllers.

이러한 방식은 빠른 response time을 요구하는 비디오 컨트롤러와 같은 장치에 적합하다.

• mapid_t mmap(int fd, void *addr)

• fd: 프로세스의 가상 주소공간에 맵핑할 파일

• addr: 맵핑을 시작할 주소 (페이지 단위 정렬)

• 맵핑에 성공하면 mapping id를 리턴한다.

• 요구 페이징에 의해 파일 데이터를 메모리로 로드한다.

• void munmap(mapid_t mapping)

• mmap()의 리턴 값을 통해 파일 맵핑을 제거한다.

read()/write() 시스템 콜 대신 메모리 접근(load/store)을 통해 파일에 접근하여 프로세스 주소공간에 파일을 맵핑한다.

파일 맵핑의 과정은 vm_entry을 생성한 후 해시 테이블에 삽입하고 요구 페이징을 통해 이뤄진다.

• struct mmap_file

맵핑된 파일의 정보를 저장하기 위해 mmap_file 자료구조를 추가한다.

• mapid: mmap() 성공 시 리턴된 mapping id

• file: 맵핑하는 파일의 파일 오브젝트

• elem: mmap_file들의 리스트를 연결하기 위한 구조체

• vme_list: mmap_file에 해당하는 모든 vm_entry들의 리스트

• munmap()

1. mmap_list에서 해제할 mmap_file을 검색한다.

2. vme_list 내 모든 vm_entry를 해제한다.

3. mmap_file을 해제한다.

• void munmap(int mapping)

• mmap_list 내에서 mapping에 해당하는 mapid를 갖는 모든 vm_entry을 해제한다.

• 인자로 입력된 mapping 값이 CLOSE_ALL인 경우 모든 파일의 맵핑을 제거한다.

• 페이지 테이블에서 엔트리를 제거한다.

• 맵핑을 제거할 시 do_munmap() 함수를 호출한다.

• void do_munmap(struct mmap_file *mmap_file)

• mmap_file의 vme_list에 연결된 모든 vm_entry들을 제거한다.

• 페이지 테이블 엔트리를 제거한다.

• vm_entry가 가리키는 가상주소에 대한 물리 페이지가 존재하고, dirty하면(dirty bit가 1인) 디스크에 메모리 내용을 기록한다.

Swapping

victim으로 선정된 페이지가 프로세스의 데이터 영역 혹은 스택에 포함될 때 이를 스왑 영역에 저장한다.

swap_out 된 페이지는 요구 페이징에 의해 다시 메모리에 로드한다.

LRU 기반 알고리즘을 이용한 페이지 교체 메커니즘을 동작하도록 수정한다.

유저에게 할당된 물리 페이지 하나를 표현하는 자료구조인 page 구조체를 추가한다.

• kaddr: 페이지의 물리주소

• vme: 물리 페이지가 맵핑된 가상주소의 vm_entry 포인터

• thread: 해당 물리 페이지를 사용 중인 쓰레드의 포인터

• lru: 리스트 연결을 위한 필드

• 페이지 교체 정책 알고리즘: Clock 알고리즘

페이지 테이블의 accessed bit는 페이지가 참조될 때마다 하드웨어에 의해 1로 설정된다.

하드웨어는 accessed bit를 다시 0으로 만들지 않기 때문에 현재 포인터가 가리키고 있는 페이지의 참조비트를 검사한다.

참조 비트의 값이 0이면 해당 페이지를 victim으로 선정하고 1이면 참조 비트를 0으로 재설정한다.

페이지 테이블의 dirty bit는 해당 메모리 영역에 쓰기 시 하드웨어에 의하여 1로 설정된다.

dirty bit가 1인 페이지가 victim으로 선정되었을 경우 변경된 내용을 항상 디스크에 저장해야 한다.

• 페이지 스왑-아웃

1. victim 페이지를 선정한다.

2. dirty bit가 1인 페이지가 victim으로 선정되는 경우 디스크에 기록한다.

3. 페이지 테이블 엔트리를 무효화한다.

PintOS는 스왑 파티션을 스왑 스페이스로 제공한다.

스왑 파티션은 swap slot 단위로 관리된다.

메모리에 존재하는 swap bitmap는 swap slot의 사용가능 여부를 나타낸다.

first-fit 알고리즘을 이용해 swap bitmap을 탐색하여 사용 가능한 swap slot을 찾는다.

물리 페이지가 부족할 경우 clock 알고리즘을 이용하여 victim으로 선정된 페이지를 디스크로 swap-out함으로써 여유 메모리를 확보한다.

victim으로 선정된 물리 프레임의 방출은 vm_entry의 타입에 따라 다른 방식으로 이뤄진다.

VM_BIN: dirty bit가 1이면 스왑 파티션에 기록한 후 페이지를 해제한다. 페이지를 해제한 후 요구 페이징을 위해 타입을 VM_ANON으로 변경한다.

VM_FILE: dirty bit가 1이면 파일에 변경 내용을 저장한 후 페이지를 해제한다. dirty bit가 0이면 바로 페이지를 해제한다.

VM_ANON: 항상 스왑 파티션에 기록한다.

Stack

현재 스택의 크기는 4KB로 고정되어 있기 때문에 현재 스택의 크기를 초과하는 주소에 접근이 발생했을 때, 스택 포인터 esp가 스택 영역을 벗어나면 세그멘테이션 폴트가 발생한다.

유효한 스택 접근인지 세크멘테이션 폴트인지 판별하는 휴리스틱을 적용하도록 수정해야 한다.

현재 스택 포인터로부터 grow limit 이내에 포함되는 접근은 유효한 스택 접근으로 간주하여 스택을 최대 8MB까지 확장한다.

STACK_HEURISTIC 휴리스틱을 적용하여 스택 확장 여부를 판단한다.

스택 확장이 필요하다고 판단하면 expand_stack()를 호출하여 스택을 확장한다.

• bool expand_stack(void *addr)

• addr 주소를 포함하도록 스택을 확장한다.

• alloc_page()를 통해 메모리를 할당한다.

• vm_entry를 할당하고 초기화한다.

• install_page()를 호출하여 페이지 테이블을 설정한다.

• bool verify_stack(void *sp)

• sp 주소가 포함되어 있는지 확인한다.

• sp 주소가 존재할 시 handle_mm_fault()를 호출한다.