😇 정리 되지 않음. 주의!😇

Project3: Virtual Memory

구현하면서 중요한 점은 주어진 템플릿을 따라야 한다.
"DO NOT CHANGE" 라고 쓰여있는 부분은 절때 건드리면 안됨.

수정해야 할 템플릿 리스트는 다음과 같음.

1. include/vm/vm.h, vm/vm.c
   해당 파일은 가상메모리의 기본적인 인터페이스이다. 해더파일을 보면 몇가지 가상메모리 타입을 볼 수 있음.
   VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE
   이 타입들은 가상메모리 시스템을 서포트함.
   그 다음 가상 페이지 테이블을 구현해야함.

   • include/vm/anon.h, vm/anon.c
     anonymous pages 제공 (vm_type = VM_ANON).
   • include/vm/file.h, vm/file.c
     file-backed pages 제공 (vm_type = VM_FILE).
   • include/vm/inspect.h, vm/inspect.c
     Contains memory inspection operations for grading. Do not change this files.

   대부분 vm 디렉토리에 있는 파일이나,이전 프로젝트에서 수정했던 부분들을 write 할거임. 그런데 몇가지 처음 만나는 파일이 있을 거임.

   • include/devices/block.h, devices/block.c
     블록 장치에 대한 섹터 기반 읽기 및 쓰기 액세스를 제공함.
     이 인터페이스를 사용하여 스왑 파티션에 블록 디바이스로 액세스한다.

Memory Terminology
Pages
page(혹은 virtual page)는 4096 bytes 길이이고, 가상메모리에 연속적으로 있음.
페이지는 반드시 정렬 되어있어야하고, 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작함.
따라서, 64비트 시스템에서, 마지막 12비트는 page offset이다. 그 upper 비트들은 곧 도입될 페이지 테이블의 인덱스를 나타내는 데 사용함. 64비트에서는 4가지 레벨의 페이지 테이블을 사용함.

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

각 프로세스는 독립적인 유저페이지의 묶음을 가진다. 각 페이지들은 가상메모리 KERN_BASE 아래에 있다.
커널 페이지들의 묶음은 반대로 글로벌이고, 어떤 쓰레드 또는 프로세스가 러닝하는지에 관계없이 같은 포지션에 남아있다.

커널은 유저와 커널 페이지에 둘다 접근가능하다. 그러나 유저 프로세스는 유저페이지에만접근이 가능하다.

Pintos는 몇가지 유요항 함수들을 제공한다. 가상메모리를 구동하기 위해. https://casys-kaist.github.io/pintos-kaist/appendix/virtual_address.html 여기에 더 자세하게 나옴.

Frames
A frame(혹은 physical frame or a page frame)은 물리메모에서 불림.
page와 같이 frame은 페이지 사이즈와 같아야 하고, 균등해야 한다. 따라서 64비트에서 physical 주소는 frame number와 frame offset으로 나누어질 수 있다.

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

x86-64는 물리 메모리 주소를 직접 접근 할수 있도록 제공하지 않는다.
Pintos는 커널 가상 메모리와 물리 메모리를 맵핑해서 작동된다. 즉, 커널 가상메모리의 첫번째 페이지는 물리 메모리의 첫번째 프레임과 맵핑된다. 따라서 프레임은 커널 가상 메모리를 통해서 접근 할수 있다.

핀토스는 물리주소와 커널 가상 주소사이를 변환하는 함수들을 제공한다.
https://casys-kaist.github.io/pintos-kaist/appendix/virtual_address.html 여기서 볼 수 있음

Page Tables
페이지 테이블은 data structure 이다 that cpu가 이는 가상주소를 물리주소로 변환하는데 사용하는.
페이지테이블 포맷은 x86-64 아키텍처에 의해 결정됨.
핀토스는 페이지테이블 매니지먼트 코드를 threads/mmu.c에서 제공.

아래는 페이지와 프래임 사이에 관계를 보여주는데, 페이지 넘버와 프레임 넘버는 변환됨. 하지만 오프셋은 변환되지 않음.

                        +----------+
         .--------------->|Page Table|-----------.
        /                 +----------+            |
        |   12 11 0                               V  12 11 0
    +---------+----+                         +---------+----+
    | Page Nr | Ofs|                         |Frame Nr | Ofs|
    +---------+----+                         +---------+----+
     Virt Addr   |                            Phys Addr    ^
                  \_______________________________________/

Swap Slots
Swap Slot은 스왑 파티션에서 디스크 공간의 페이지 크기 영역이다. 슬롯 배치를 결정하는 하드웨어 제한이 프레임보다 더 유연하지만 스왑 슬롯은 정렬되어야 한다. 안할 이유가 없음ㅎ

Resource Management Overview
다음과 같은 데이터 구조의 디자인이나 구현을 따라야함!!!!
아니면 빵쩜임ㅎ ㅎ헤헤헤

Supplemental page table
페이지 테이블을 보완하여 페이지 오류 처리를 활성화해야함.

Frame table
물리적 프레임의 제거 정책을 효율적으로 구현할 수 있음.

Swap table
스왑 슬롯 사용량을 추적

완전한 세개의 데이터 구조를 구현할 필요가 없음. 관련 리소스를 전체 또는 부분적으로 통합된 데이터 구조로 통합하는 것이 편리할 수 있음.
--> 하나만 정해서 통합해서 사용하라라는 뜻인가..?

각 데이터 구조에 대해서 어떤 element를 포함할지 결정해야한다. 더불어 어떤 데이터 구조 scope를 결정할 필요가 있다. 지역변수, 전역변수 그리고 얼마나 많은 instance 들이 해당 스코프에 요구되는지..
--> 잘 struct 를 짜라.

디자인을 간단하기 위해, 아마 데이터 구조를 저장해야한다, in non-pageable memory.
(calloc, malloc 에 의해 메모리는 할당되어짐) 이 뜻은, 포인터 간의 포인터가 계속 유효하게 유지된다는 것을 확인할 수 있습니다. --> 포인터.. 사용?

Choices of implementation (Performance perspective)
arrays, lists, bitmaps, and hash tables 이 구현 가능한 선택지 들임.

array는 가장 접근이 간단하지만 wasted memory 일 수 있음
list 또한 simple! 하지만 특정 위치를 찾기 위해 긴 목록을 통과하는 것은 시간을 낭비.
array랑 list 는 둘다 크기 조절이 가능, 하지만 list 가 삽입 삭제에 좀 더 효과적이다.

Pintos 는 bitmap 제공함 lib/kernel/bitmap.c , include/lib/kernel/bitmap.h 여기에!
bitmap은 array of bits 임. true or False 로 나타냄. 일반적으로 일련의 (동일한) 리소스에서 사용을 추적하는 데 사용됨. 리소스 n이 사용 중이면 비트맵의 비트 n이 True.
핀토스 비트맵은 크기가 고정되어 있지만 크기 조정을 지원하도록 구현을 확장할 수 있음

Pintos 는 hashtable 제공함.
Pintos hashtable은 삽입삭제가 효과적이다. over a wide range table size에서.

더 복잡한 데이터 구조는 아마 더 좋은 퍼포먼스나 이점을 나타낼 수 있지만, 불필요하게 구현을 복잡하게 만들 수도 있음. 따라서 any advanced 한 데이터 구조는 추천하지 않음.
(e.g. a balanced binary tree)
-> 위에서 언급한 것 중에 사용해라.

Managing the Supplemental Page Table
Supplemental Page Table은 각 페이지의 추가적인 데이터들을 포함하는 페이지 테이블임.
페이지 테이블 형식에 따라 적용되는 제한 때문에 필요함
--> 잘 이해가 안가네.. 무슨 적용되는 제한?
혼용을 막기 위해 보조라는 단어를 추가헤서 말할거임.

Supplemental Page Table 두가지 목적을 가지고 있음. 가장 중요한건 Page fault임. 커널은 페이지 폴트 났을때, Supplemental Page Table 에서 falut 난 데이터를 찾음. 커널은 프로세스가 종료될 때 Supplemental Page Table 을 참조하여 어떤 리소스를 해제할지 결정함.

Organization of Supplemental Page Table
적어도 두가지 기본 접근 방법이 있다. supplemental page table을 구성하는 방법으로.
세그먼트 또는 페이지 측면에서, 여기서 세그먼트는 연속적인 페이지 그룹, 즉 실행 파일 또는 메모리 매핑된 파일을 포함하는 메모리 영역을 나타냄.

optionally, 페이지테이블을 사용해서 supplemental page table의 맴버들을 track 을 위해 사용할 수 있다.
그렇게 하려면 스레드/mmu.c에서 Pintos 페이지 테이블 구현을 수정해야 합니다. 잘하면 고고. 못하면 하지마셈.. 난 안해!!!!!!

Handling page fault

Page fault handler 가 supplemental page table 를 사용하는 가장 중요한 유저임.
프로젝트 2에서는 page fault는 버그를 나타냈음. 프로젝트3에서는 더이상 그렇지 않음. 이제 page fault는 파일 또는 스왑 슬롯에서 페이지를 가져와야 한다는 것만 나타낼 수 있습니다. 이러한 경우를 처리하려면 보다 정교한 페이지 오류 처리기를 구현해야함.

he page fault handler, which is page_fault() in userprog/exception.c, calls your page fault handler, vm_try_handle_fault() in vm/vm.c. Your page fault handler needs to do roughly the following:

1. faulted 된 page는 supplemental page table에 locate!
   만약 그 메모리가 vaild 하면(참조가 유효한다면), supplemental page table entry를 사용하여, 페이지에 들어갈 데이터를 찾아본다.
   해당 페이지는 파일 시스템에 있거나 스왑 슬롯에 있거나 단순히 0 페이지일 수 있음..!
   --> 만약에 스왑 슬롯에 있으면 참조가 유효하지 않은게 아닌가..?
   만약 sharing(copy on write)을 구현한다면, 페이지 데이터는 이미 페이지 프레임에 있지만 페이지 테이블에는 없을 수도 있다.
   supplemental page table이 사용자 프로세스에 접근하려는 주소에 어떠한 데이터도 없어야 한다고 나타내거나, 페이지가 가상메모리에 있고나, 접근이 읽기 전용 페이지를 쓰려는 시도라면, 그 접근은 유효하지 않음. 그럴땐, 프로세스를 종료시키고, 모든 자원을 해제해야함.

2. Obtain a frame to store the page.
   --> 이말이 잘 이해가 안가는데, 다음 문장에 문맥을 보면, frame 에 페이지 정보를 저장할 때 라는 말인 것 같음.
   만약 sharing 을 구현할 때, 데이터는 이미 frame 안에 있어야 하고, 이 케이스에서 나는 항상 frame에 Locate 가 가능해야함. ..?
   --> 전반적으로 잘 이해가 안가는 문장이긴한데, copy on wirte는 옵션.. 구현이란다.
   우선 넘어가!

3. 파일 시스템에서 데이터를 읽거나 스왑, zeroing 등을 통해 데이터를 프레임으로 가져옵니다. 공유를 구현하는 경우, 필요한 페이지가 이미 프레임에 있을 수 있으며, 이 경우 이 단계에서 수행할 작업이 필요하지 않습니다.

4. 장애가 발생한 가상 주소에 대한 페이지 테이블 항목을 실제 페이지로 가리킵니다. 스레드/mmu.c에서 기능을 사용할 수 있습니다.

Managing the Frame Table
Frame table은 하나의 엔트리가 하나의 프레임을 포함한다. 각 엔트리는 page에 대한 포인터, 그리고 현재 차지하고 있는 데이터 그리고 다른 내가 선택한 다른 데이터를 포함함. frame table은 pintos는 퇴거 정책을 효율적으로 실행할수 있음, free할 프레임이 없을 경우 페이지 선택에 의해. ?
--> 뭔가 딱히 free할 페이지가 없을때, 퇴거 정책에 의해서 효과적으로 free한다는 말 같은데.. 어떻게인지는 모르겠음..

사용자 페이지에 사용되는 프레임은palloc_get_page(PAL_USER) 호출해서 "user pool" 가져와야 함. PAL_USER을 사용해야만함, kernel pool에서 allocating 되는걸 피하기 위해서.
만약 palloc.c 의 frame table 구현을 수정하게 된다면, two pools 의 차이를 잘 보고 써야함?

frame table 을 구동하는 가장 중요한 점은 사용하지 않는 frame을 얻는 것임.
이것은 frame을 free할때 쉽다. free할 프레임이 없으면 프레임에서 일부 페이지를 제거하여 프레임을 비워 두어야 함.

만약 스왑 슬롯을 할당하지 않고 프레임을 추방할 수 없는 상황이고, 스왑이 가득 차 있는 상태라면, 커널을 패닉 상태로 만듬. 실제 운영체제들은 여러 방법이 있음. 하지만 이 프로젝트는 노상관

퇴거(evict) 방법 스텝 ㅋㅋㅋ 말이 좀 웃기네요..:
1. 퇴거할 frame 선택, 페이지 교체 알고리즘를 사용한다. 아래에 설명된 페이지테이블에 accessed 와 dirty 비트가 도움이 될 것임.?
2. 프레임을 참조하는 페이지 테이블에서 프레임에 대한 참조를 제거합니다. 공유를 구현하지 않은 경우, 지정된 시간에 한 페이지만 프레임을 참조해야 합니다.
3. 만약 필요한 경우 page에 write 하거나 스왑 할수 있다. 제거된 프레임은 다른 페이지 저장하는데 사용 될 수 있음.

Accessed and Dirty Bits
x86-64 하드웨어는 PTE의 pair of bits를 통해서 페이지 교환 알고리즘을 구현할 수 있게 assistance를 제공한다. 페이지를 Read and write 때, cpu는 해당 페이지의 PTE의 accessed bit 를 1 로 설정하고, 쓰기 위해서는 dirty bit 를 1로 설정한다. CPU는 절때 이 비트들을 리셋하지 않는다. 하지만 운영체제는 수행 가눙

--> 지피티가 설명 도와줌! "이 문장은 x86-64 하드웨어가 페이지 테이블 엔트리에 있는 accessed bit와 dirty bit 를 통해 페이지 교체 알고리즘을 구현하는데 도움을 준다는 것을 설명하고 있습니다. 이러한 비트들은 페이지에 대한 읽기나 쓰기 작업이 발생했을 때 CPU에 의해 설정되며, 운영 체제는 필요에 따라 이들 비트를 재설정할 수 있움"

aliases 에 대해 알아야함. 이거는 두개 이상의 페이지들을 참조하는 페이지들임. aliased frame 에 접근될때, accessed 와 dirty 비트는 오직 하나의 페이지 테이블 엔트리에만 업데이트 되어야 함.
---> 왜지?

In Pintos, every user virtual page is aliased to its kernel virtual page.

Managing the Swap Table
스왑 테이블은 사용 중인 스왑 슬롯과 사용 가능한 스왑 슬롯을 추적한다.
스왑 테이블은 사용하지 않는 스왑 슬롯을 고르는 것을 허용한다.
페이지를 다시 읽거나 페이지가 스왑된 프로세스가 종료될 때 스왑 슬롯을 해제할 수 있습니다.

Swap Partition: 스왑 파티션은 하드 디스크의 특정 부분으로서, 물리적 메모리가 부족할 때 시스템에서 사용되는 추가적인 메모리 영역입니다. 시스템이 물리적 메모리를 모두 사용하고도 더 많은 메모리를 필요로 할 때, 운영체제는 일부 페이지를 스왑 파티션으로 이동시킴으로써 물리적 메모리의 공간을 확보합니다. 이런 과정을 페이지 아웃 혹은 스왑 아웃이라고 합니다.

Swap Slot: 스왑 슬롯은 스왑 파티션 내에서 특정 페이지를 저장하는 데 사용되는 공간입니다. 스왑 파티션은 일반적으로 여러 개의 스왑 슬롯으로 나뉘며, 각각의 스왑 슬롯은 메모리 페이지 하나를 저장할 수 있는 크기로 설정됩니다.

Swap Table: 스왑 테이블은 어떤 페이지가 어떤 스왑 슬롯에 저장되어 있는지를 추적하는 데이터 구조입니다. 스왑 파티션 내의 페이지 위치를 효율적으로 관리하기 위해 사용되며, 페이지가 스왑 아웃될 때 해당 페이지의 메타데이터와 스왑 슬롯의 위치 정보가 스왑 테이블에 저장됩니다. 이 정보는 페이지가 다시 물리적 메모리로 스왑 인되어야 할 때 사용됩니다.

vm/build 디렉토리로부터 해당 커멘드를 사용하면, swap.dsk 디스크가 생성된다. 그리고 이 디스크는 n-MB 스왑 파티션을 포함한다.

intos-mkdisk swap.dsk --swap-size=n

swap.dsk는 자동적으로 extra disk 로서 attached 된다.

swap slots은 느리게 allocated 되어야 한다.
--> 스왑 슬롯이 실제로 필요한 시점(즉, 메모리에서 페이지를 제거해야 할 때)에만 스왑 슬롯을 할당해야 함을 의미합니다.

Managing Memory Mapped Files

파일 시스템은 보통 read 와 write 시스템 콜과 함께 접근된다.
secpmdary 인터페이스는 mmap 시스템콜을 사용해서 파일을 가상페이지로 매핑한다.

-> 아마 직접 주소랑 파일을 직접 매핑하는 함수같고.. 만들어야 되는거 같고..
어렵고...

더불어 매핑된 주소는 잘 추적해야함....!!!