• 1215 금요일 - 10시 출근 (1시간 커피챗)
• kaist gitbook Project3 Virtual Memory 읽기
• kaist gitbook Project3 FAQ, Appendix Memory Allocation, Virtual Address, Page Table 읽기
• 공부 키워드 TIL 정리

---

by metamong

---

gitbook Project3 Virtual Memory - Intro

https://casys-kaist.github.io/pintos-kaist/project3/introduction.html

Source files

• include/devices/block.h, devices/block.c

Provides sector-based read and write access to block device. You will use this interface to access the swap partition as a block device.

이라고 나와있는데 이상함. 경로에 해당 파일 없음

아, 깃북 업뎃이 안된거라고 한다. 현재 위치는 아래임
include/devices/disk.h, devices/disk.c

Memory Terminology

pages

• 페이지, 때로 가상 페이지라고도 불리는 것은 길이가 4,096바이트(페이지 크기)인 가상 메모리의 연속된 영역이다.

• 페이지는 무조건 'page-aligned' 되어야하며, 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작해야 한다.

• 64비트 가상 주소의 마지막 12비트는 페이지 오프셋(또는 단순히 오프셋)이다. (상위 비트는 페이지 테이블에서의 인덱스를 나타냄)

• 각 프로세스는 하나의 독립적인 set of user(virtual)pages 를 가진다. which 가상주소 KERN_BASE(0x8004000000) 아래에 있는

• set of kernel (virtual) pages는 전역이므로 어떤 스레드나 프로세스가 실행 중이든 위치가 동일함

• 커널은 유저페이지 & 커널페이지에 접근 가능. but 유저페이지는 자신의 사용자 페이지에만 접근 가능

Frames

• 프레임(physical frame or a page frame)은 물리 메모리의 연속된 영역임

• 페이지와 마찬가지로 프레임은 page-size이며 page-aligned 되어야 함. (noticed point: 뭔가 프레임 사이즈? 라고 할 것 같은데 프레임도 페이지 사이즈, 페이지 얼라인 되어야한다고 한다)

• x86-64 아키텍처에서는 물리 주소에 직접적으로 접근할 수 있는 방법을 제공하지 않음.

• Pintos는 이를 우회하기 위해 커널 가상 메모리를 물리 메모리에 직접 매핑함.

TLB (translation look-aside buffer)

• 직역하면 변환 색인 버퍼라는 이름. 특수한 작은 고속 룩업 하드웨어 캐시를 사용함. (기능이 캐시랑 거의 비슷한듯)

• TLB가 가득 차 있으면 기존 내역을 하나 골라서 새로 넣을 걸로 교체해야함(LRU, RR, or Random 정책들 중에서 골라서. tmi: LRU연산은 너무 비싸서 잘 안한다고 하고, 랜덤 정책은 은근 hit ratio가 평균값 나오기 때문에 자주 쓰인다고 함)

Page Tables

• 페이지테이블 관리 코드 @ threads/mmu.c

• 페이지 테이블은 CPU가 가상 주소를 물리 주소로 변환하는 데 사용하는 데이터 구조. 페이지에서 프레임으로 변환하는 도구. Virt Addr -> Phys Addr

흐름 정리

• case(1) cpu ➡️ TLB @MMU ➡️ HIT! ➡️ Phys Addr

• case(2) cpu ➡️ TLB @MMU ➡️ MISS! ➡️ Page Table @MainMemory ➡️ HIT! ➡️ Phys Addr

• case(3) cpu ➡️ TLB @MMU ➡️ MISS! ➡️ Page Table @MainMemory ➡️ MISS! ➡️ Page Fault

Resource Management Overview

Supplemental page table

supplementing 페이지 테이블을 제공해서 페이지 폴트 핸들링이 작동할 수 있게 함.

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.

근데 이 세 개의 독립적인 데이터구조를 구현할 필요는 없음. 관련 리소스를 완전히 아님 부분적으로 통합해서 통일된 제이터 구조로 구성하는 것이 편리할 수 있음

내가 해야할 것은 각 엘리먼트에 어떤 정보가 담겨야 하는지, 데이터 구조의 스콥(local or global), 몇개의 인스턴스가 스콥 안에 필요로 할지 임.

설계를 간단하게 하기 위해서 non-pageable memory (e.g., memory allocated by calloc or malloc)에 자료구조를 저장하면 좋다.

구현시 고를 수 있는 옵션

• 리스트나 배열은 비효율적이라 추천하는건 비트맵 or 해시테이블. (Pintos에는 lib/kernel/bitmap.c 및 include/lib/kernel/bitmap.h에 비트맵 데이터 구조가 포함되어 있음)

• 비트맵은 참 또는 거짓이 되는 비트의 배열임.

• 비트맵은 보통 동일한 리소스의 사용을 추적하는데 사용됨.

• 핀토스의 비트맵은 크기가 고정되어있음. 하지만 크기 조정가능하게 확장도 가능함.

• 해시테이블은 다양한 크기의 테이블에서 효율적인 삽입 삭제를 지원함

Managing the Supplemental Page Table

• "보충 페이지 테이블" why 보충?

왜 Page Table 이라고 안하고 Supplemental Page Table 라고 하냐면,

보충 페이지 테이블은 페이지 테이블의 형식에 따른 제약으로 인해 각 페이지에 대한 추가 데이터를 제공하는 데이터 구조인데 이게 주로 "페이지 테이블" 이라고 불려서 혼란을 막기 위해 앞에 "보충" 이라는 말음 붙였다.

• Supplemental Page Table의 목적 주요 두 가지

첫 째로, (주요 목적) 페이지 폴트가 났을 때, Supplemental Page Table에서 부재가 발생한 가상 페이지를 조회하여 해당 위치에 어떤 데이터가 있어야 하는지 확인 하는 것이다.

둘 째로, 프로세스가 종료될 때, 어떤 자원을 해제할지 결정하기 위해 Supplemental Page Table를 참고한다.

Organization of Supplemental Page Table

• Supplemental Page Table를 꾸리는 두 가지 방법
  • 세그먼트를 기준으로
    • 여기서 말하는 세그먼트는 연속된 페이지 그룹을 말함. 예를들어, 실행 가능한 파일이나 메모리 맵핑 파일을 포함하는 메모리 영역
  • 페이지를 기준으로
  • (Optionally) 역설적이긴 한데 보충 테이블 페이지의 멤버를 tracking하기 위해 페이지 테이블을 사용하는 것도 가능. (잘하는 학생들에게만 추천요)

Handling page fault

Supplemental Page Table의 vip 손님은 page fault handler 임.

• 페이지 폴트 핸들러가 의미하는 바

프로젝트 2 에서는 페이지 폴트는 항상 커널이나 유저 프로그램의 버그를 나타냄.
프로젝트 3 에서는 더이상 저것만을 의미하지는 않는다. (좀 더 명확해졌다)

이제 페이지 폴트는 단순히 파일이나 스왑슬롯에서 페이지를 가져와야 한다는 뜻, 아니면 단순히 모든 비트가 0인 페이지 라거나. (페이지 폴트가 의미하는 경우의 수는 줄어들었지만 이제 이렇게 바뀌기 위해서는 우리(학생)가 page fault handler를 좀 더 손봐야 한다.)

• 페이지 폴트 핸들러는 누가 호출?

userprog/exception.c 에 있는 page_fault() 가 vm/vv.c 에 있는 vm_try_handle_fault()라는 이름을 가진 페이지 폴트 핸들러를 호출한다.

• 페이지 폴트 핸들러가 해야하는 일들(more like orders)
  1. supplemental page table에서 부재가 발생한 페이지 찾기.
  2. 페이지를 저장하기 위해 프레임을 획득하기.
  3. 데이터를 파일시스템이나 스왑에서 읽어오기. (읽어오거나 0으로 초기화하는 방식으로 만들어서 프레임으로 가져옴)
  4. 폴트가 발생한 가상 주소에 대한 PTE가 물리 페이지를 가리키도록 지정하기.

Managing the Frame Table

• 하는 일
  비어있는 프레임이 없을 때 쫓아낼 페이지를 골라줌. 즉, eviction policy를 구현할 수 있도록 해줌

• 구성

  • 프레임 테이블 안의 각 프레임은 하나의 엔트리 정보를 갖음
  • 각 엔트리에는 해당 엔트리를 차지하고 있는 페이지에 대한 포인터(있으면)와 내가 선택해서 넣을 수 있는 기타 데이터들이 있음

• 사용 방법

  • 유저 페이지를 위해 프레임을 사용하고 싶으면 palloc_get_page(PAL_USER) 호출.(이렇게 해야 유저 풀에서 획득된 것임이 확실함)
  • 사용되지 않은 프레임을 획득하는 것이 중요. 근데 free상태인 프레임이 없으면 몇몇 페이지들을 쫓아내서 그 프레임을 free 상태로 만들어 줘야 함

• eviction 절차

  1. 페이지 재배치 알고리즘 이용해서 victim 고르기. 페이지 테이블에 있는 "accessed", "dirty" 비트들이 유용.
  2. 해당 프레임을 참조하는 모든 페이지 테이블에서 참조를 제거. (공유를 구현하지 않았을 경우는 해당 프레임을 참조하는 페이지는 항상 한 개만 존재 해야 함)
  3. (if necessary) 페이지를 파일 시스템이나 스왑에 write하기. (쫓겨난 프레임은 이제 다른 페이지를 저장하는 데에 사용할 수 있음)

Accessed and Dirty Bits

• 페이지에 read 하면 CPU는 페이지의 PTE에 있는 accessed bit를 1로 설정한다.

• write 할 때는 accessed bit 와 dirty bit 를 1로 설정한다.

• CPU는 절대 이 비트들을 0으로 되돌릴 수 없음. only the OS can.

• 같은 프레임을 참조하는 두 개이상의 페이지들인 aliases 를 유의해야한다. aliased 프레임이 accessed 될 때, accessed 비트와 dirty 비트는 하나의 페이지 테이블 엔트리에서만 업데이트됨

• pintos에서 모든 유저 가상 페이지는 커널 가상 페이지에 alias 되어있음. 내가 이 alias들을 관리해야 함

• alias 관리 예시

  • 내 code가 accessed 와 dirty 비트를 업데이트 할 때 양쪽 주소 모두를 확인하고 업데이트 해야함
  • 유저 가상 주소를 통해서만 유저 데이터에 접근하게 함으로써 커널이 이 문제를 피하게 할 수 있음

Managing the Swap Table

• 역할
  • 스왑테이블은 사용중인 스왑 슬롯과 빈 스왑 슬롯들을 추적하기.
  • 페이지가 다시 읽히거나 페이지 주인인 프로세스가 종료되어 버릴 경우엔 스왑 테이블이 스왑 슬롯을 free 하는거 승낙해주기.

• n-MB swap partition을 포함하는 디스크 생성 방법
  • swap.dsk를 생성하려면 vm/build 경로에서 pintos-mkdisk swap.dsk --swap-size=n 명령어를 사용
  • swap.dsk를 만들면 pintos 실행할 때 자동으로 추가 디스크로 연결됨.