가상 메모리를 구현해야 하는 이유

• 운영체제는 실제 메모리를 직접 접근 x -> 가상의 주소 공간을 통해 간접적으로 접근
• 가상 메모리 덕분에, 각 프로세스는 독립적 메모리 공간을 가짐
• 가상 메모리 관련 기본 interface는 include/vm/vm.h 및 vm/vm.c에 위치

페이지의 종류

• (1) Uninitialized pages: VM_UNINIT / vm/uninit.c / include/vm/uninit.h
  • 모든 페이지는 처음엔 unitialized 상태
  • 이후 anonymous / file-backed page로 전환됨
• (2) Anonymous pages: VM_ANON / vm/anon.c / /include/vm/anon.h
  • 파일과 연결되지 않은 페이지, 모든 비트가 0으로 초기화되어 있음
• (3) File-backed pages: VM_FILE / vm/file.c / /include/vm/file.h
  • 파일과 연동되어 데이터를 관리하는 페이지

가상/물리 메모리

• 가상 페이지: 4,096바이트(PGSIZE)의 연속된 영역의 가상 메모리 영역
• 물리 프레임: 물리 페이지라고도 부름. 4,096바이트의 연속된 영역의 물리 메모리 영역.
• 페이지 테이블은, 가상주소를 물리주소로 변환하는 역할
  • 페이지테이블에 의해, 가상 페이지는 물리 프레임에 매핑됨
  • 다만 후술할 이유 때문에, 핀토스의 페이지테이블 관련 함수는 물리 주소 대신 커널영역 가상 주소를 사용/반환함
  • 그냥 커널영역 가상주소 라는 말이 나올 때마다, 물리 주소를 떠올리는게 속편함.

                          +---------- +
         .--------------->|페이지 테이블|------------.
        /                 +---------- +            |
        |   12 11 0                                V  12 11 0
    +---------+----+                         +---------+-----+
    | 페이지번호 | 오프셋 |                     |프레임번호 | 오프셋|
    +---------+----+                         +---------+----+
     가상주소    |                            물리주소       ^
                  \_______________________________________/

가상 주소

• 핀토스의 가상 주소는 64비트 (=8바이트)로 구성됨
  • 하지만 실제로는 하위 48비트(=6바이트)만 사용됨
  • Sign Extend (16비트): 64비트 구조 유지를 위한 잉여 비트. 47번째 비트의 값을 단순 복사함.

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    PML4 Offset |   PDPT Offset  |     PD Offset  |   PT Offset | Page Offset|
+-------------+----------------+----------------+----------------+-------------+------------+
               |      9 bits    |     9 bits     |     9 bits     |   9 bits    |  12 bits   |

• 가상 주소에서 물리 주소로 변환되는 과정
• CR3 레지스터: 현재 프로세스의 PML4 테이블 물리주소를 저장
• 이후 PML4 테이블 -> PDP 테이블 -> PD 테이블 -> PT (페이지 테이블) -> 물리 프레임 순서로 따라감
  • 현재 테이블의 Offset을 확인해 각 테이블의 특정 엔트리 선택
  • 해당 엔트리에 저장된, 다음 레벨 테이블의 물리 주소로 이동
  • 마지막 페이지 테이블의 엔트리에선, 물리 프레임의 번호가 저장됨
  • 해당 프레임 번호에 Page Offset을 더해 최종 물리 주소 계산
• PML4 Offset ~ Page-Table Offset: 4개의 필드를 합쳐 가상 페이지 번호라고도 함
  • 9비트인 이유? $2 ^ 9 = 512$, PML4/PDP/PD/PT 테이블엔 총 512개의 테이블 엔트리 존재
  • Offset을 보고 512개의 엔트리 중 하나를 선택하는 식
• Page Offset
  • 가상 페이지 / 물리 프레임 내 정확한 위치를 지정
  • 12비트인 이유?: $2 ^ 12 = 4,096$, 페이지 / 프레임의 크기와 동일

물리 주소

                          12 11         0
    +-----------------------+-----------+
    |      Frame Number     |   Offset  |
    +-----------------------+-----------+

• 가상 주소와 동일하게 64비트.
• Frame Number: Page Table 엔트리에서 확인한 프레임 반호
• Offset은 변환 이전의 가상 주소와 동일.

가상 주소 -> 물리 주소 예제

• 아래와 같은 가상주소가 존재할 때...

필드명	비트 범위	값
Sign Extend	16비트	0x0000
PML4 Offset	9비트	0x1FF (=511)
PDP Offset	9비트	0x1FF (=511)
PD Offset	9비트	0x1FF (=511)
PT Offset	9비트	0x1FF (=511)
Page Offset	12비트	0xFFF (=4095)

• (1) CR3 레지스터: 현재 프로세스의 PML$ 테이블의 물리 주소 가리킴
• (2) PML4 Offset: PML4 테이블의 511번째 엔트리를 읽어, PDP 테이블의 물리 주소 확인
• (3) PDP Offset: PDP 테이블의 511번째 엔트리를 읽어, PD 테이블의 물리 주소 확인
• (4) PD Offset: PD 테이블의 511번째 엔트리를 읽어, 페이지 테이블의 물리 주소 확인
• (5) PT Offset: 페이지 테이블의 511번째 엔트리를 읽어, 물리 프레임의 주소 확인
• (6) 찾은 물리 프레임의 주소에, Page Offset (0xFFF)을 붙여 최종 물리 주소 계산

페이지테이블 엔트리에 포함된 정보

• 페이지 테이블 엔트리에 포함된 정보?
• Present bit: 페이지가 물리 프레임에 매핑되어 있으면 1, 없으면 0
  • 0인 경우 Page Fault
• Writable bit: 1이면 쓰기 가능, 0이면 읽기 전용
  • is_writable(pte)로 확인
• User/Supervisor bit: 1이면 사용자모드에서도 접근 가능, 0이면 커널 전용
  • is_user_pte(pte), is_kern_pte(pte)로 확인
• Accessed bit: CPU가 읽거나 쓴 적 있으면 1, 없으면 0
• Dirty bit: CPU가 페이지에 쓰기를 한 적 있으면 1, 없으면 0
• 페이지가 매핑된 물리 프레임의 시작주소 (우리가 찾는 것)
  • 가상주소 변환 시, 최종적으로 찾는 값

메모리 할당과 사용자/커널 영역

user vs kernel pages

• user virtual pages: 주소가 KERN_BASE (0x8004000000) 미만
  • 각 프로세스 / 쓰레드는 제각기 다른 user page 공간을 가짐
• kernel virtual pages: 주소가 KERN_BASE (0x8004000000) 이상
  • 모든 프로세스 / 쓰레드가 공유하는 커널 영역의 가상 페이지
• 주소가 사용자 / 커널 영역 어디에 위치해 있는지 확인할 땐...
  • is_user_vaddr(vaddr), is_kern_vaddr(vaddr) 사용
• 커널은 user page, kernel page 모두 접근 가능
• 사용자 프로세스는 자기 자신의 user page에만 접근 가능

물리 주소 vs 커널 가상주소

• x86-64에선 물리 주소로 직접 메모리에 접근할 수 없음
• 대신 핀토스에선, 가상 메모리의 커널 영역이 물리 메모리와 1:1 매핑됨
  • PML4 테이블 초기활 때 일괄적으로 매핑됨 (paging_init)
• 물리 주소 + KERN_BASE = 커널 가상주소가 됨에 유의
  • ptov(paddr), vtop(vaddr)로 계산 가능
• PTE 자체에는 물리 주소가 저장되나, 핀토스 함수에서 커널 가상주소로 변환함에 유의
• palloc_get_page() 역시 물리 메모리에서 페이지를 할당하지만, 실제론 이에 대응되는 커널 가상주소 반환

메모리 할당

• palloc, 즉 page allocator는 물리 메모리에서 page(4096바이트)만큼의 물리 프레임을 할당
• 이때 물리 메모리의 두 pool 중 한쪽에서 할당됨
  • user pool: 사용자 프로세스가 사용하는 프레임 할당에 사용
    • 이후 pml4_set_page 등 사용해 페이지 테이블에서 user 영역의 가상 주소와 매핑되며, supervisor 비트는 1이 됨
  • kernel pool: 커널 자체가 사용하는 프레임 할당에 사용
    • 이미 PML4 테이블 초기화 과정에서, 물리 메모리와 1:1 매핑된 상황. 추가 조치를 할 필요 없음.
• void *palloc_get_page(enum palloc_flags flags): 할당된 프레임(의 커널 가상) 주소 반환
  • PAL_ZERO: 물리 프레임의 모든 바이트를 0 처리
  • PAL_USER: USER POOL에서 할당. 없을 시 KERNEL POOL에서 할당됨.
• malloc(), calloc() 등 함수도 핀토스 커널에서 사용 가능 -> 무조건 kernel pool에서 할당

핀토스 내 페이지 테이블 관련 함수

• 매개변수 pml4는 pml4 테이블의 포인터.

• 매개변수 uaddr, upage, vpage는 가상 주소로, 페이지 테이블에 의해 물리 주소와 매핑됨

  • uaddr은 아무런 주소든 상관없지만, upage/vpage는 무조건 페이지의 시작주소여야 함

• void * pml4_get_page(uint64_t *pml4, const void *uaddr)

  • PML4 테이블 pml4에서 가상 주소 uaddr에 매핑된 물리 프레임(의 커널 가상)주소 반환
    • 반환값은 물리 주소가 아닌, 이에 대응하는 커널가상주소 (물리주소 + KERN_BASE)
  • uaddr이 속한 페이지에 물리 프레임이 매핑되지 않은 경우, NULL 반환 (present bit로 확인)

• bool pml4_set_page(uint64_t *pml4, void *upage, void *kpage, bool rw)

  • pml4 테이블에 가상 페이지 upage와 믈리 프레임 kpage의 매핑 추가
    • kpage는 물리 주소가 아닌, 이에 대응하는 커널가상주소 (물리주소 + KERN_BASE)
  • upage는 이미 매핑된 페이지여선 안됨 (valid bit로 확인)
  • kpage는 palloc_get_page()로 user pool에서 할당된 커널 가상 주소여야 함
  • rw가 true면 쓰기 가능, false면 읽기 전용 (writable bit 수정)

• void pml4_clear_page(uint64_t *pml4, void *upage)

  • 가상 페이지 upage에 대응하는 페이지 테이블 엔트리의 present 비트를 0으로 설정 -> 매핑을 해제하는 용도
  • 이미 매핑되지 않은 경우 효과가 없음

• bool pml4_is_dirty(uint64_t *pml4, const void *vpage)

  • 가상 페이지 vpage에 대응하는 페이지 테이블 엔트리의 dirty 비트 확인
  • void pml4_set_dirty(uint64_t *pml4, const void *vpage, bool dirty)로 재설정

• bool pml4_is_accessed(uint64_t *pml4, const void *vpage)

  • 가상 페이지 vpage에 해당하는 페이지 테이블 엔트리의 accessed 비트 확인
  • void pml4_set_accessed(uint64_t *pml4, const void *vpage, bool dirty)로 재설정

구현할 것들

• 아래 자료구조들을 구현해야 함
• 배열? 리스트? 비트맵? 해시?
• 구현의 난이도와, 성능은 반비례...

Supplemental page table / page fault

• 각 페이지의 부가 정보를 저장하는 자료구조
  • 하드웨어의 page table이 메모리에 실제 매핑한 페이지만 관리한다면
  • 소프트웨어의 S.P.T.는 가상 메모리의 모든 페이지 정보를 관리
• 해당 페이지의 상태를 저장
  • A. in memory: 페이지가 물리 프레임에 적재되어 있음 (즉, 하드웨어 page table에 매핑되어 있음)
  • B. swapped out: 메모리에 존재했으나, 현재는 내려가 디스크의 스왑 공간에 저장되어 있음
  • C. not loaded: 파일 시스템에 존재하지만, 아직 메모리에 로드되지 않은 상태
  • D. Anonymous Page: 실제 파일/스왑 공간이 없고, 읽으면 0으로 채워져야 하는 페이지
• 사용이유 (1) Page Fault 발생시, 해당 페이지에 대응되는 데이터의 위치 확인
• 사용이유 (2) 프로세스 종료 시, 어느 자원의 메모리 할당을 해제해야 하는지 확인

page fault 발생 시

• [구현] vm/vm.c의 vm_try_handle_fault() 수정해야 함

• (1) Supplemental P.T.에서 page fault가 발생한 가상 주소를 확인

  • 유효한 사용자 영역의 주소인 경우
    • S.P.T. 이용해, 페이지에 들어갈 데이터의 위치 (파일 / 스왑영역 / anonymous) 확인
  • invalid memory 주소인 경우
    • e.g., 사용자 영역 중 접근불가 영역에 접근 OR 커널영역에 접근 OR 읽기전용 페이지에 쓰기 시도
    • 프로세스 종료하고, 할당된 자원을 해제해야 함

• (2) 물리 메모리에서 프레임 할당

• (3) 할당된 프레임에 데이터 로딩

  • 파일 시스템에서 읽든, 스왑영역에서 읽든, 0으로 초기화하든

• (4) 페이지테이블 엔트리 갱신

  • page fault가 발생한 가상페이지와, 새로 할당된 프레임을 연결
  • threads/mmu.c 사용하기

frame table / eviction policy

• 페이지 테이블은 가상 페이지마다 엔트리가 존재하고, 매핑된 물리 프레임 번호를 저장했다면
• 프레임 테이블은 물리 프레임마다 엔트리가 존재하고, 해당 프레임에 할당된 가상 페이지의 포인터를 저장함
  • 추가적으로, 프레임에 로딩된 페이지 데이터의 위치 (파일, 스왑 등)도 저장 가능
• 사용하는 이유: page fault가 발생했을 때, 어느 프레임에 페이지를 적제할 지 판단하기 위함
  • 남은 프레임이 있는 경우: frame table 중 빈 테이블 엔트리를 찾아 거기에 할당
  • 모든 프레임이 꽉 찬 경우: frame table을 순회하며, 현재 메모리에 로딩된 프레임 중 어떤 프레임을 스왑 아웃할지 결정
• [구현] eviction policy
  • (1) Least Recently Used 등 알고리즘을 이용해, 교체할 프레임을 결정함
  • (2) 해당 프레임을 가리키는 페이지 테이블 엔트리에서, 참조 정보 삭제
  • (3) 페이지가 수정된 경우, 파일 시스템 / 스왑 영역에 수정된 데이터 저장
  • (4) 새 페이지를 프레임에 로드하고, 페이지 테이블 / 프레임 테이블 갱신

Accessed / Dirty Bit

• 페이지에 읽거나 쓴 경우, 해당 페이지 테이블 엔트리의 두 비트가 갱신될 수 있음
  • accessed(Read/Write 하면 1 됨) / dirty bit (Write 하면 1 됨)
• 두 페이지가 동일 프레임을 가리키는 경우, 한쪽 페이지 테이블 엔트리에만 업데이트될 수 있음
  • e.g., 실제 접근에 사용되는, 사용자 영역의 페이지 엔트리 / 해당 물리 주소와 매핑된 커널 영역의 페이지 엔트리
  • 전자의 dirty/accessed 비트만 수정됨. 후자도 수정해야 함!

swap table

• 스왑 영역의 slot 관리
  • 사용 중인 slot / 가용 slot을 구분해서 관리
• 프레임 eviction 발생 시, 스왑 영역으로 swap out 수행
  • 쫓겨난 프레임을 스왑 slot 중 하나에 저장
  • lazy allocation: swap slot은 필요할 때만 동적으로 할당됨. 즉, swap out 시점에 할당하면 됨.
• 다시 swap in되거나, 해당 페이지의 process가 종료된 경우, swap slot을 free해야 함

managing memory mapped files

• mmap 시스템 콜을 구현하게 됨
• 파일을 가상 페이지에 매핑하는 시스템 콜