2022/1/11 ~ 2022/1/24
Team 8 - 이후명, 조은우, 진승현

Gitbook - Introduction

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

• 제한없는 무한대의 메모리의 환상을 building 할꺼다.

• project 2에 버그가 있으면 고쳐놔야된다.(project3에서도 같은 버그가 생길 꺼임)

• VM 디렉토리에서 작업.

• 제공하는 템플릿에 따라 코드를 작성해야한다.

• DO NOT CHANGE 라고 써있는 것은 건들지마라.

Pages

• 페이지(=가상페이지)는 4096바이트의 길이를 가진 가상메모리의 연속된 영역. 페이지는 정렬되어야 한다. 즉, 페이지는 4Kb 로 균등하게 나눌 수 있는 가상 주소에서 시작되어야 한다. 64비트의 가상 주소의 마지막 12비트는 page offset(혹은 그냥 offset)이다. 그 앞쪽의 비트는 페이지 테이블의 인덱스를 나타내는데 사용되며 곧 소개할 예정이다. 64비트 시스템과 함께 핀토스는 4-level 페이지 테이블을쓰며 가상 주소는 요로케 생김:

• 각각의 프로세스는 독립적인 유저(가상)페이지들을 갖고있으며, 모든 페이지들은 KERN_BASE(0x8004000000) 밑에 있다. 이와는 다르게, 커널(가상)페이지들의 집합은 global하며, 어떤 프로세스, 쓰레드가 running 중이던 상관없이 같은 포지션에 있다. 커널은 유저,커널 페이지에 모두 접근 할 것이지만, 유저 프로세스는 오직 자신의 own user pages 에만 접근 가능할 것이다.

Frame

• 프레임(=피지컬 프레임 or 페이지 프레임)은 물리적 메모리의 연속된 영역. 페이지 처럼, 프레임들은 page-size와 같아야하고, page-aligned 되어있어야 한다. 그러므로, 64비트 물리 주소는 frame number 와 frame offset으로 나누어 질 수 있다. 요로케 :

• x86-64는 물리적 메모리에 다이렉트하게 접근하는 '어떠한' 방법도 제공하지 않는다. PintOS는 커널 가상 메모리를 물리적 메모리에 직접 매핑하여 이를 해결한다 - 커널 vm의 첫 페이지는 물리적 메모리의 첫 번째 프레임에 매핑된고, 두 번째 페이지는 두 번째 프레임에 매핑되고, and so on. 그러므로, 프레임은 커널 vm을 통해 접근될 수 있다.

• PintOS는 물리주소와 커널의 가상 주소 사이의 translating 기능을 제공한다.

Page Tables

• Page Table : data structure that the CPU uses to translate a virtual address to a physical address, that is, from a page to a frame.

• threads/mmu.c 에 Pintos 가 제공하는 page table management code 있음.

• Page Table은 Page number -> Frame number 로 translate 하고, offset과 컴파인 시킨다. (밑에 그림처럼)
  

Swap slots

• swap slot은 디스크 영역에 있는 스왑파티션의 page-size 영역이다. slot들은 frame들에 비해 하드웨어가 유연하게 배치할 수 있지만, swap-slot들은 page-aligned 되어야한다. 왜냐? page-align을 안할 이유가 없다. (딱히 단점이없음)

Resource Management Overview

우리가 구현(디자인)해야 할 data structure의 Component:

Components :

• Supplemental page table
• Frame table
• Swap table
• Modifying the page fault handler
• Stack growth
• mmap, munmap

큰 그림 :

• 물리 메모리의 제한이 있지만, 많은 프로세스들은 물리 메모리를 사용하고자 한다.
• 물리 메모리는 모든 프로세스의 페이지들을 계속 저장하고 있을만큼 크지 않다.
• 만약 페이지가 물리메모리에 필요없다면, 페이지는 paged out 된다. (스왑테이블이나 파일시스템에 기록되어있던)
• 물리메모리에 없는 페이지를 프로세스에서 필요로한다면, 그 페이지는 paged in 되어야 한다. (보통 다른 페이지를 page out 시키고 그 자리에 넣음 -> 이것도 여러가지 스케줄링 알고리즘이 있음.)

key word:

• Page: 가상메모리의 연속적인 영역.
• Frame: 물리메모리의 연속적인 영역.
• Page Table: data structure to translate page(va) to a frame(pa).
• Eviction: removing a page from its frame and potentially writing it to swap table of file system.
• Swap Table: where evicted pages are written to in the swap partition.
  

Supplemental page table

• page table을 보충해서 page fault 핸들링을 가능하게 해라!
• per-process data structure that tracks supplemental data for each page, such as location of data(frame/disk/swap), pointer to corresponding kernel virtual address, active vs inactive, etc.

Frame table

• Allows efficient implementation of eviction policy of physical frames.
• global data structure that keeps track of physical frames that are allocated/free.

Swap table

• keeps track of swap slots.

File mapping table

• keeps track of which memory-mapped files are mapped to which pages.

Choices of implementation (Performance perspective)

Possible choices : arrays, lists, bimaps, hash tables.

Array - simplest approach, 짜잘한 array들은 메모리를 낭비시킴.

List - simple, 특정 위치에 있는 것을 찾기위해 긴 리스트를 순회하게되면 낭비.
**Array, List 모두 resize될수 있지만, 리스트가 중앙에 있는 값에 대한 삽입과 삭제를 실행할 때 더 효율적이다.

> PintOS에서 bitmap data structure를 제공한다.

 lib/kernel/bitmap.c
 include/lib/kernel/bimap.h

bitmap - 비트맵은 bit들의 array이다. 각각의 비트는 true(1) 또는 False(0)값을 가질 수 있다. 비트맵들은 일반적으로 (동일한) 자원들의 집합의 사용 여부를 추적하는데 사용된다. PintOS 비트맵은 고정된 사이즈이지만, 너는 resize를 제공하기 위해 추가 구현할 수 있다.

Hash Table - Pintos는 hash table 데이터 structure를 제공하고있다. Pintos hash tables efficiently support insertions and deletions over a wide range of table sizes.

Although more complex data structures may yield better performance or other benefits, they may also needlessly complicate your implementation. Thus, we do not recommend implementing any advanced data structure (e.g. a balanced binary tree) as part of your design.