Swap In/Out

Memory swapping is a memory reclamation technique to maximize the usage of physical memory. When frames of the main memory is allocated, the system cannot handle any more memory allocation requests from user programs. One solution is to swap out memory frames that are not being currently used to disk. This frees some memory resources and makes available to other applications.

메모리 스와핑은 물리 메모리의 사용을 극대화할 수 있는 메모리 확보 기법이다.

물리 메모리의 프레임이 할당되었을 때, 운영체제는 더 이상의 유저 프로그램으로부터 메모리 할당 요청을 받아들일 수 없다.

이러한 상황에 대한 해결 방안은 디스크에서 사용되지 않는 물리 메모리 프레임을 스왑-아웃하는 방법이다.

메모리 스와핑은 메모리 리소스를 해제하여 다른 응용 프로그램이 사용할 수 있도록 한다.

Swapping is done by the operating system. When the system detects that it has run out of memory but receives a memory allocation request, it chooses a page to evict out to swap disk. Then, the exact state of the memory frame is copied to the disk. When a process tries to access a swapped out page, OS recovers the page by bringing the exact content back to the memory.

스와핑은 운영체제에 의해 실행된다.

운영체제가 메모리가 부족하다는 것을 감지하지만 메모리 할당 요청을 받아들이고 스왑 디스크에서 교체할 페이지를 선택한다.

그런 다음 메모리 프레임의 상태가 디스크에 기록된다.

프로세스가 스왑-아웃된 페이지를 접근하려 할 때, 운영체제는 페이지의 저장된 상테를 메모리로 불러와 복구한다.

The page chosen for eviction may be an anonymous page or a file-backed page. In this section, you will handle each case.

교체되기로 정해진 페이지는 anonymous 페이지 혹은 file-backed 페이지이다. VM_TYPE에 따라 페이지를 다루는 방식이 다르다.

All the swapping operations are not called explicitly, but as function pointers. They are members of struct page_operations file_ops, which will be registered as operations for each page's initializer.

모든 스와핑 명령은 함수 포인터와 같이 명시되지 않는다.

스와핑 명령은 page operations file_ops 구조체에 포함되며 페이지 초기화 함수로 등록된다.

스와핑 및 페이지 교체 정책 개요

• 스와핑 지원

• victim으로 선정된 페이지가 프로세스의 데이터 영역 혹은 스택에 포함될 때 이를 스왑 영역에 저장
• swap-out 된 페이지는 요구 페이징에 의해 다시 메모리에 로드
• LRU 기반 알고리즘을 이용한 페이지 교체 메커니즘을 동작하도록 수정

page 자료구조 추가

• 유저에게 할당된 물리 페이지 하나를 표현하는 자료구조

• kaddr: 페이지의 물리주소
• vme: 물리 페이지가 맵핑된 가상주소의 vm_entry 포인터
• thread: 해당 물리 페이지를 사용중인 쓰레드의 포인터
• lru: 리스트 연결을 위한 필드

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

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

• 하드웨어는 accessed bit를 다시 0으로 만들지 않는다.
• 현재 포인터가 가리키고 있는 페이지의 참조비트(reference bit)를 검사한다.
• 참조 비트의 값이 0이면 해당 페이지를 victim으로 선정하고, 1이면 참조 비트를 0으로 재설정한다.

페이지 풀 관리

• page 구조체의 리스트로 프로세스에게 할당된 물리 페이지를 관리한다.
• lru_list: 전역 변수로 선언한다.

Dirty Bit

• 페이지 테이블의 dirty bit는 해당 메모리 영역에 쓰기시 하드웨어에 의하여 1로 설정된다.
• dirty bit의 값이 1인 페이지가 victim으로 선정되었을 때, 변경된 내용을 항상 디스크에 저장해야 한다.

페이지 스왑 아웃

1. victim 페이지를 선정한다.
2. (dirty bit의 값이 1인 페이지가 victim으로 선정되었을 경우) 필요하다면 디스크에 기록한다.
3. 페이지 테이블의 엔트리를 무효화한다.

LRU 리스트 초기화, 삽입 및 삭제 함수 구현

• void lru_list_init(void)

• lru_list를 초기화한다.
• lru_list_lock을 초기화한다.
• lru_clock의 값을 NULL로 설정한다.

• void add_page_to_lru_list(struct page *page)

• LRU 리스트의 끝에 유저 페이지를 삽입한다.

• void del_page_from_lru_list(struct page *page)

• LRU 리스트에 유저 페이지를 제거한다.

LRU 리스트 삽입/삭제를 위한 페이지 할당/해제 함수 추가

• struct page *alloc_page(enum palloc_flags flags)

• palloc_get_page()를 통해 페이지를 할당한다.
• page 구조체를 할당 및 초기화한다.
• add_page_to_lru_list()를 통해 LRU 리스트에 page 구조체를 삽입한다.
• page 구조체의 주소를 리턴한다.

• void free_page(void *kaddr)

• 물리주소 kaddr에 해당하는 page 구조체를 LRU 리스트에서 검색한다.
• 매치하는 항목을 찾으면 __free_page()를 호출한다.

• void __free_page(struct page *page)

• LRU 리스트를 제거한다.
• page 구조체에 할당받은 메모리 공간을 해제한다.

alloc_page() 함수 구현

• struct page *alloc_page(enum palloc_flags flags)

• palloc_get_page()를 통해 페이지를 할당한다.
• page 구조체를 할당 및 초기화한다.
• add_page_to_lru_list()를 통해 LRU 리스트에 page 구조체에 삽입한다.
• page 구조체의 주소를 리턴한다.

page 구조체 해제 함수 구현

• void free_page(void *kaddr)

• 물리주소 kaddr에 해당하는 page 구조체를 LRU 리스트에서 검색한다.
• 매치하는 항목을 찾으면 __free_page()를 호출한다.

• void __free_page(struct page *page)

• LRU 리스트를 제거한다.
• page구조체에 할당 받은 메모리 공간을 해제한다.

get_next_lru_clock() 함수 구현

• static struct list_elem *get_next_lru_clock()

• clock 알고리즘의 LRU 리스트를 이동하는 작업을 수행한다.
• LRU 리스트의 다음 노드의 위치를 반환한다.
• 현재 LRU 리스트가 마지막 노드일 때 NULL 값을 반환한다.

스와핑

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

스왑 파티션 공간 관리

• 스왑 파티션은 swap slot(4KB) 단위로 관리한다.
• swap bitmap(메모리에 존재): swap slot의 사용가능 여부를 표시한다.
• 여유 swap slot을 탐색: bitmap을 first_fit 알고리즘을 이용하여 탐색한다.

스왑 관련 함수 추가

• void swap_init(size_t used_index, void *kaddr)

• 스왑 영역을 초기화한다.

• void swap_in(size_t used_index, void *kaddr)

• used_index의 swap slot에 저장된 데이터를 논리주소 kaddr로 복사한다.

• size_t swap_out(void *kaddr)

• kaddr 주소가 가리키는 페이지를 스왑 파티션에 기록한다.
• 페이지를 기록한 swap slot 번호를 리턴한다.

스와핑 및 페이지 교체 정책 과제 구현 항목

• LRU 리스트 생성

• 할당/해제를 위해 alloc_page()/free_page()를 사용한다.
• 가상 메모리 및 memory mapped file 과제에서 유저 메모리 할당/해제하는 부분도 alloc_page() 및 free_page()를 사용하도록 수정한다.

• 물리 페이지가 부족할 때, victim 페이지를 디스크로 swap out함으로써 여유 메모리 확보

• clock 알고리즘을 이용하여 victim page를 선정하도록 구현한다.

• 스와핑 지원을 위한 페이지 폴트 핸들러 수정

• void try_to_free_pages(enum palloc_flags flags)

• 물리 페이지가 부족할 때 clock 알고리즘을 이용하여 여유 메모리를 확보한다.

• bool handle_mm_fault(struct vm_entry *vme)

• 스와핑을 지원하도록 수정한다.

alloc_page() 및 free_page() 함수 추가

alloc_page() 내에서 palloc_get_page()를 통해 메모리를 할당 받을 수 없을 때, 여유 공간을 확보하기 위해 try_to_free_pages()를 호출한다.

유저 메모리 할당 및 해제 시 방법 수정

• 할당 함수 변경

• palloc_get_page() 함수를 alloc_page() 함수로 변경한다.

• 해제 함수 변경

• palloc_free_page() 함수를 free_page() 함수로 변경한다.

try_to_free_pages() 함수 구현

• void *try_to_free_pages(enum palloc_flags flags)

• clock 알고리즘을 이용하여 victim page를 선정하고 방출하여, 여유 메모리 공간을 확보하고 여유 페이지의 커널 가상 주소를 리턴하도록 한다.

물리 메모리 방출

• victim 페이지의 방출은 vm_entry의 type에 따라 다른 방식이 요구된다.

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

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

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

• void pagedir_clear_page(uint32_t pd, void upage)

• 페이지 테이블에서 upage에 해당하는 주소의 엔트리를 제거한다.

스왑 영역 요구 페이징 구현

페이징 할당 여부를 확인하여 VM_TYPE에 따라 다른 방식으로 물리 메모리를 방출한다.

vm_entry의 타입이 VM_ANON일 시 스왑-인 할 수 있도록 handle_mm_fault() 함수를 수정한다.