Photographed by ProdMoon
Changes in Project 3
- Project2까지 메모라 관리 기법 방식은 프로세스 전체가 메모리 내에 올라와야 한다는 것 을 전제로 하고 있다.
- 즉 유저프로그램이 실행되기 위해 필요로 하는 메모리들 (ex. code segment/data segment/stack segment)이 모두 physical memory에 다 있어야 된다라는 가정하에서 실행되어 왔다.
- 그렇기 때문에 Page Fault는 항상 커널 또는 유저 프로그램의 버그를 의미했다.
- Project3부터는 물리 메모리로부터 분리된 가상 메모리를 구현하여 주 메모리를 균일한 크기의 저장 공간으로 구성된 배열로 추상화한다.
- 이러한 가상 메모리를 페이징 기법으로 구현한다.
- 가상메모리를 통해 프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능해진다.
가상메모리가 가능한 이유는?
프로그램은 Locality(지역성)를 가지고 있기 때문에 메모리가 모두 물리 메모리에 존재할 필요가 없다.
Principle of Locality (Locality of Reference)란?
프로그램이 가장 최근에 접근했던 데이터에 다시 접근(Temporal Locality)하거나, 최근에 참조했던 데이터 근처의 주소를 참조(Spatial Locality)하는 경향이 있음.
Principle of Locality
동일한 주소 또는 해당 주소에 관계된 주소가 자주 참조 되는 특성.
지역성의 3가지 기본형 : 시간, 공간, 순차 지역성1) 공간(spatial) 지역성 : 특정 주소영역에 대한 참조가 집중적으로 이루어지는 경향. 참조된 메모리의 근처의 메모리를 참조하는 경향.
2) 시간(temporal) 지역성 : 최근 사용되었던 메모리가 집중적으로 참조되는 경향. 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높다.
3) 순차(sequential) 지역성 : 데이터가 순차적으로 참조되는 경향. 프로그램 내의 코드가 순차적으로 구성되어 실행되는 것.
locality로 인해 프로세스의 모든 공간을 물리 메모리에 할당하기보다 필요한 만큼 적재하는 것이 효율적이다. -> Demanding Paging
What is Demanding Paging?
Demanding Page은 필요한 프로그램만 메모리에 적재하는 방법으로 가상 메모리 시스템에서 많이 사용된다. Demanding Page을 사용하는 가상메모리에서는 페이지들이 실행 과정에서 실제로 필요해질 때 적재 된다. - lazy loading.
이 기법은 일종의 Swapping 기법이라 볼 수 있는데, 프로세스 전체가 메모리에 올라가지 않기 때문에 그 페이지의 주소에 접근하지 않는 한 메모리에 load되지 않는다.
In PintOS
Pintos의 bogus page fault 중 하나가 lazy loading으로 인한 page fault이다.
lazy loading으로 인해 가상 메모리 주소가 존재하는 유효한 페이지이지만 물리 메모리와 맵핑이 되어있지 않은 상태이다. 따라서 이 page fault가 유효하지 않은 페이지에 접근한 fault인지 확인하고 아닐 경우 lazy-loading으로 인한 fault로 판단하여 해당 메모리에 대한 loading을 실행한다.
page_fault() 발생 -> vm_try_handle_fault()-> vm_do_claim_page() -> swap_in() -> uninit_initialize()->
Design of Demanding Page
1 ~ 2. 프로세스의 모든 공간이 메모리에 존재하지 않기 때문에 페이지 테이블에 세팅되지 않은 가상 주소에 접근할 때 하드웨어적으로 exception이 발생한다. -> lazy loading으로 인한 page fault
- 페이지 폴트가 발생하면 제어권이 사용자 영역(어플리케이션)에서 커널로 이동한다. 커널을 보고 페이지폴트가 일어난 가상주소를 확인한다. 그 주소는 cr2 레지스터에 저장되어 있다.
프로세스마다 Page table을 갖고 있으며 이는 thread 구조체 안에 존재한다.
fault_addr = (void *)rcr2();
struct thread
{
//...(omit)
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
//...(omit)
}4 ~ 5. Pintos에서는 물리 메모리에 올라와 있지 않은 page들의 주소가 저장되어있는 공간, Supplemental Page Table을 구현한다. SPT를 참조해서 유효한 가상 페이지인지 확인한다.
The process of eviction comprises roughly the following steps:
- Choose a frame to evict, using your page replacement algorithm. The "accessed" and "dirty" bits in the page table, described below, will come in handy.
- Remove references to the frame from any page table that refers to it. Unless you have implemented sharing, only a single page should refer to a frame at any given time.
- If necessary, write the page to the file system or to swap. The evicted frame may then be used to store a different page.
6. 각 페이지 유형에 따라 swap in/out을 수행한다.
물리 메모리에 비어있는 프레임(Free Frame)이 존재한다면 그곳에 페이지를 읽어온다. 이때 만약 비어있는 프레임이 없다면 페이지 교체 알고리즘(Page Replace Algorithm)을 통해 교체할 페이지를 골라야 한다.- Anonymous Page
익명 페이지에는 백업 저장소가 없다. 익명 페이지의 swap을 지원하기 위해 스왑 디스크라는 임시 백업 저장소를 제공합니다. 스왑 디스크를 활용하여 익명 페이지에 대한 스왑을 구현한다.
swap table 구현
swap table은 swap disk에서 사용 가능한 영역과 사용 중인 영역을 구분하기 위한 테이블로, 비트맵 형식으로 구현한다.
- File Backed page Page
디스크로부터 file의 내용이 변화없이 읽어져 와서 따로 변화를 백업해 둘 swap file을 만들지 않아도 되는 page. disk에 파일의 실체가 있고, 해당 파일을 가상메모리에 맵핑한 페이지는 file backed page로 분류한다.
7 ~ 8. 물리 메모리가 swap되면서 update되고 해당 page table도 update하고 다시 프로세스를 실행한다.
