지난 포스팅에서는 메모리가 참조되는 과정을 알아보았다.
Pintos의 Project3은 3개의 테이블로 자원 관리 정책을 수행한다.

1. Supplemental Page Table
2. Frame Table
3. Swap Table

하나씩 간단하게 알아보고 어떻게 적용되는지 보자.

Supplemental Page Table: SPT

페이지 폴트 발생시, 운영체제가 해당 가상 주소에 어떤 타입(file/swap/zero)의 데이터를 적재해야 하는지 알려주는 메타데이터 테이블로 프로세스마다 하나씩 존재한다.

이 table이 중요하게 맡고있는 역할은 크게 두 가지이다.

1. 페이지 폴트 발생 시 커널이 SPT에서 폴트가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지 파악하는 것입니다.
2. 프로세스가 종료될 때 커널은 SPT을 참조하여 어떤 리소스를 해제할지 결정합니다.

Frame Table: FT

Frame Table은 RAM 상의 실제 물리 페이지 프레임들에 대한 정보를 저장하는 자료구조이다. 어떤 페이지가 어떤 프레임을 쓰고 있는지, 어떤 프레임을 교체할지를 결정한다.

등장하게 된 이유는 아래와 같다.
한정적인 RAM의 프레임 수로 인해, 어떤 페이지는 내려야 한다. 따라서, 어떤 프레임이 사용 중인지 알아야 한다.

FT의 중요한 두 가지 역할이다.

1. FT에서 가장 중요한 연산은 사용되지 않는 프레임을 가져오는 것입니다. 프레임이 비어 있을 때는 이 작업이 쉽지만, 비어 있는 프레임이 없을 때는 프레임에서 특정 페이지를 제거하여 프레임을 비워야 합니다.
2. 사용 가능한 프레임이 없을 때 제거해야할 페이지를 선택하는 데 효율적으로 지원할 수 있습니다.
   FT에는 각 프레임마다 하나의 엔트리가 있고 이 엔트리에는 현재 점유 중인 페이지에 대한 포인터, 그리고 기타 데이터가 포함됩니다.
   이 데이터를 보고 어떤 프레임을 교체할지 결정할 수 있습니다.

.
.

이렇게 프레임이 더 이상 안 남았을 때, 프레임을 하나 비워야 하는 과정을 eviction이라고 한다.

eviction?

1. 페이지 교체 알고리즘을 사용하여 제거할 프레임을 선택하세요.
   아래에 설명된 페이지 테이블의 "Accessed bit" 및 "Dirty bit"가 유용합니다.
2. 프레임을 참조하는 모든 페이지 테이블에서 해당 프레임에 대한 참조를 제거하세요.
   공유를 구현하지 않은 경우, 특정 시점에 하나의 페이지만 프레임을 참조해야 합니다.
3. 필요한 경우 해당 페이지를 파일 시스템이나 스왑 공간에 기록합니다.
   이렇게 제거된 프레임은 다른 페이지를 저장하는 데 사용될 수 있습니다.

Swap Table: ST

swap slot들의 사용 여부를 관리하는 자료구조이다.
어느 slot이 비어있는지, 어떤 페이지가 어디에 저장되었는지 추적한다.

스왑 테이블은 사용 중인 스왑 슬롯과 사용 가능한 스왑 슬롯을 추적합니다.

• 페이지를 프레임에서 스왑 파티션으로 내보내기 위해 사용되지 않는 스왑 슬롯을 선택할 수 있어야 합니다.
• 또한, 해당 페이지를 다시 읽거나 스왑된 페이지를 가진 프로세스가 종료될 때 스왑 슬롯을 해제할 수 있어야 합니다.

Lazy allocation
스왑 슬롯은 진짜 필요한 순간에만 할당해야 한다.(eviction)

항목	설명
할당 시점	프레임이 부족해서 페이지를 디스크로 내보낼 때만
해제 시점	스왑에서 다시 메모리로 불러오거나, 프로세스 종료 시
구현 자료구조	보통 bitmap 사용: 0=free, 1=used

자, 이제 이 테이블들이 구체적으로 어떻게 쓰이는지 알아보자.

메모리가 참조되는 과정

1. 가상 주소에서 VPN을 추출한다.

2. TLB를 확인하여 존재하는지 확인한다.
   (🙆‍♀️TLB hit!) 해당 물리 메모리를 바로 참조한다.

3. (🤦‍♀️TLB miss) Page Table에서 VPN을 인덱스로 PTE를 추출한다.

   • PTE가 유효한가? (present bit =1)
   • 해당 페이지가 물리 메모리에 존재하는가?
     (🙆‍♀️YES!) PTE에서 PFN 정보를 추출하여 TLB에 탑재하고 명령을 재시도한다.

4. (🤦‍♀️ PTE가 유효하지 않다) Page Fault 발생!

   • 운영체제의 Page Fault Handler로 제어가 넘어간다.

5. 커널은 해당 가상 주소의 정보를 Supplemental Page Table (SPT) 에서 찾는다.

   • 해당 주소가 유효한가?
     유효하다면 file-backed? anonymous? mmap?

6. Frame Table (FT) 을 조회하여 빈 물리 프레임을 확보한다.

   • (🙆‍♀️확보 성공!) 해당 페이지를 디스크에서 가져온다. → Swap in
   • 디스크 I/O가 완료되면 PTE의 PFN 값을 RAM 위치로 갱신한다.
   • 재실행하여 TLB miss가 발생하면서 TLB가 갱신된다.

7. (🤦‍♀️물리 프레임 확보 실패) 페이지 교체 알고리즘을 통해 물리 메모리의 특정 페이지를 디스크로 내보낸다. → Swap out

   • 이 때, 내보낼 페이지가 anonymous page라면 원본이 없기 때문에 반드시 Swap Table에 빈 슬롯을 찾아 저장해야 한다.
   • file-backed page라면, 파일에서 복원 가능하므로 dirty bit를 확인하여 필요시에만 Swap 한다.

8. 확보한 프레임에 SPT가 가리키는 출처에서 데이터를 읽어온다.

   • 실행파일? 파일에서 읽는다.
   • swap에 저장? Swap Table에서 위치를 확인하여 읽는다.→ Swap in
   • anonymous page? 0으로 초기화한다.

9. 메모리에 올라온 페이지 정보를 바탕으로 PTE를 업데이트한다.

10. 다시 명령을 재시도하며, TLB miss가 발생하면서 TLB가 갱신된다.