Project 3. Introduction

Project 3: Virtual Memory

• 지난 과제의 코드 위에 이번 과제를 빌드해야한다. 프로젝트 3에서도 프로젝트 2의 테스트 프로그램이 동작해야한다.
• 프로젝트 2의 버그를 고치는 게 좋다.
  → 그러한 버그들이 프로젝트 3에서도 같은 문제를 일으킬 가능성이 높기 때문이다.

 

 

---

Source Files

• 이번 프로젝트에서는 vm 디렉토리에서 작업하게 될 것이다.
• Makefile은 -DVM 세팅을 포함하여 설계되어있다.
• 엄청난 양의 템플릿 코드를 제공한다.
  • 반드시 주어진 템플릿을 따라야한다.
  • “DO NOT CHANGE.” 라고 적혀있는 부분의 코드는 절대 수정하면 안된다.

vm
├── Make.vars
├── Makefile
├── anon.c
├── file.c
├── inspect.c
├── targets.mk
├── uninit.c
└── vm.c  # ⭑

• vm.c
  • 가상 메모리의 기본적인 인터페이스를 제공한다.
  • 헤더 파일(vm.h)에서는 vms가 지원해야하는 다른 vm_type 의 정의와 설명을 볼 수 있다.
    • VM_UNINIT
    • VM_ANON
    • VM_FILE
    • VM_PAGE_CACHE (프로젝트 4에서 쓰므로 지금은 무시하라.)
• uninit.c
  • 초기화되지 않은 페이지들을 위한 기능을 제공한다.
    • vm_type = VM_UNINIT
  • 현재 디자인 하에는 모든 페이지가 초기화되지 않은 페이지로 설정되고 이후에 anonymous pages 나 file-backed pages로 변환된다.
• anon.c
  • anonymous pages를 위한 기능을 제공한다.
    • vm_type = VM_ANON
• file.c
  • file-backed pages를 위한 기능을 제공한다.
    • vm_type = VM_FILE
• inspect.c
  • 메모리 검사 기능을 포함하고 있다.
  • ❌ 수정금지 ❌

💡 이번 프로젝트에서 작성해야하는 코드들은 대부분 vm 디렉토리 또는 이전 프로젝트에서 소개된 파일들에 있다. (+ devices/disk.c 추가로 수정해야한다.)

 

devices
├── disk.c
├── input.c
├── intq.c
├── kbd.c
├── serial.c
├── targets.mk
├── timer.c
└── vga.c

• disk.c
  • 블록 디바이스로 접근하기 위한 섹터 기반 읽기, 쓰기 기능을 제공한다.
  • 블록 디바이스로 스왑 파티션에 접근할 때 사용할 것이다.

 

 

---

Memory Terminology

• 메모리와 저장소에 관련한 몇 가지 용어들
• Virtual Memory Layout 참고

 

Pages

• 페이지(= 가상 페이지)는 4,096 bytes(=페이지 사이즈) 가상 메모리의 연속된 공간이다.
• 페이지는 반드시 ‘page-aligned' 되어 있어야한다.
  • 페이지 사이즈로 균등하게 나눠지는 가상 주소로 시작해야한다.
• 64-bit 가상 주소의 마지막 12비트는 페이지 오프셋(또는 그냥 오프셋)이다.
  • 상위 비트들은 페이지 테이블의 인덱스를 나타내기 위해 사용한다.
  • 64-bit 시스템에서는 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 (0x8004000000) 미만의 가상 주소를 가진다.
• 반면에 커널 (가상)페이지는 전역적이며 어느 스레드나 프로세스가 실행중이던 간에 모두 같은 위치로 남아있다.
• 커널은 유저 페이지와 커널 페이지 모두에 접근할 수 있지만, 유저 프로세스는 본인의 유저 페이지에만 접근할 수 있다.

 

• 💡 핀토스는 가상 주소들을 다루는 데 유용한 몇몇 함수들을 제공한다.
  • Virtual Address

 

 

Frames

• 프레임(= 물리 프레임 or 페이지 프레임)은 물리 메모리상의 연속적인 공간이다.
• 페이지와 마찬가지로 프레임은 페이지 사이즈(4,096 bytes)여야하고 ‘page-aligned’ 되어야 한다.
• 64-bit 물리주소는 프레임 넘버와 프레임 오프셋(또는 그냥 오프셋)으로 나뉘어질 수 있다.

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

• x86-64 시스템은 물리 주소에 직접적으로 접근하는 방법을 제공하지는 않는다.
• 핀토스는 커널 가상 메모리를 물리 메모리로 직접 매핑하는 방법을 통해 해결한다.
  • 커널 가상 메모리는 물리 메모리와 일대일 매핑되어 있기 때문에, 커널 가상 메모리를 통하면 프레임들에 접근할 수 있다.
  • Example
    • 커널 가상 메모리의 첫 페이지 ↔ 물리 메모리의 첫 프레임
    • 커널 가상 메모리의 두 번째 페이지 ↔ 물리 메모리의 두 번째 프레임
• 💡 핀토스는 물리 주소 ↔ 가상 주소 변환을 위한 함수들을 제공한다.
  • Virtual Address

 

 

Page Tables

• 페이지 테이블은 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

• 스왑 파티션 내의 디스크 공간에 있는 페이지 크기의 영역이다.
• 비록 하드웨어적인 제한들로 인해 슬롯의 배치를 강제하는 건 프레임에서보다 더욱 유연한 편이지만, 스왑 슬롯을 page-aligned 된다고 해서 별다른 불이익이 없기 때문에 page-aligned 되어야한다.

 

---

Resource Management Overview

• 당신은 아래와 같은 자료구조들을 설계하고 구현해야한다.

 

Supplemental page table

• 페이지 테이블을 보조해서 페이지 폴트 핸들링이 가능하도록 해준다.

 

Frame table

• 물리 프레임의 “eviction policy”를 효율적으로 구현하도록 해준다.

Swap table

• 스왑 슬롯의 사용을 추적한다.
  • ⭐ ”Manaing the Swap Table” 참조

 

📢 위의 세 가지 자료구조를 구현하는 것이 필수는 아니다.

• 서로 연관된 자원들을 통합된 자료구조로 전부 또는 부분적으로 합치는 게 더 편할 수 있다.
• 각 자료구조에서 각각의 원소가 어떤 정보를 담을 지를 정해야한다.
• 자료 구조의 범위를 정해야한다.
  • 지역적인지(프로세스 별 존재), 전역적인지(전체 시스템 내에 존재)
  • 해당 범위에 필요한 인스턴스의 수도 정해야한다.
• 설계를 단순화하기 위해, 이러한 자료구조들을 non-pageable 메모리에 저장할 수 있다.
  • non-pageable 메모리 : calloc, malloc
  • 자료 구조들간의 포인터가 유효한 상태로 유지될 거란 사실을 보장한다.

 

Choices of Implementation

• 배열
  • 가장 단순한 접근법이지만 밀도가 희박한 배열은 메모리를 낭비 시킨다.
• 리스트
  • 단순하지만 특정 위치를 찾기 위해 긴 리스트를 순회하는 건 시간 낭비이다.
  • 💡 배열과 리스트 둘 다 크기의 재조성이 가능하지만 중간 부분의 삽입과 삭제에 있어서는 리스트가 더 효율적이다.
• 비트맵
  • lib/kernel/bitmap.c 내에 존재
  • 각각이 true 또는 false의 값을 가지는 비트들로 이루어진 배열이다.
  • 비트맵은 일반적으로 자원 집합 내부의 사용을 추적하기 위해 사용된다.
  • eg. 만약 자원 “n”이 사용중이라면 비트맵의 비트 “n”은 true 값을 가진다.
  • 핀토스의 비트맵들은 크기가 고정되어 있지만 구현을 통해 리사이징을 지원하도록 할 수 있다.
• 해시 테이블
  • 다양한 테이블 크기에서의 삽입과 삭제를 효율적으로 지원한다.
  • Ref. Hash Table

⭐ 구현이 불필요한 복잡성으로 인해, 균형 이진 트리와 같은 자료구조를 설계에 사용하는 건 추천하지 않는다.

 

 

---

Managing the Supplemental Page Table

• 보조 페이지 테이블은 각 페이지에 대한 추가 데이터를 이용해, 페이지 테이블을 보조한다.
• 페이지 테이블의 포맷으로 인해 생기는 제한들 때문에 보조 페이지 테이블이 필요하다.

⭐ “페이지 테이블”이라고도 불리는 데, 혼란을 방지하기 위해 “보조”라는 단어를 붙였다.

💡 보조 페이지 테이블?

• 프로세스마다 존재하는 자료구조로, 각각의 페이지에 대한 보조 데이터의 테이블
• 페이지가 존재하는 곳(frame, disk, swap) 이에 상응하는 커널 가상 주소를 가리키는 포인터 정보, active/inactive 여부
• 보조 페이지 테이블의 목적
  1. 페이지 폴트가 발생했을 때, 그곳에 어떤 데이터가 있었어야 했는지를 알아내기 위해 커널은 보조 페이지 테이블에서 폴트가 발생한 가상 페이지를 탐색한다.
  2. 커널이 프로세스가 종료될 때 어떤 자원을 해제(free)할 지 결정하기 위해 조사한다.

 

Organization of Supplemental Page Table

• 2가지 구성 방법
  • 세그먼트 : 연속된 페이지 그룹
    • eg. 실행파일을 포함하는 메모리 영역, 메모리에 매핑된 파일
  • 페이지 : 페이지 테이블 자체를 보조 페이지 테이블로 사용할 수 있다.
  • threads/mmu.c 에 있는 페이지 테이블 구현을 수정해야한다.

 

Handling page fault

• 페이지 폴트 핸들러에서 보조 페이지 테이블을 핵심적으로 사용한다.
• 프로젝트 2에서 페이지 폴트는 항상 커널이나 유저 프로그램의 버그를 의미했다.
• 프로젝트 3에서의 페이지 폴트는 파일이나 스왑 플롯에서 페이지를 가져와야 한다는 사실을 나타낸다.
• 이 경우들을 다루기 위해서는 더 복잡한 페이지 폴트 핸들러를 구현해야한다.
• userprog/exeception.c -> page_fault() 는 vm/vm.c -> vm_try_handle_fault() 를 호출한다.
• 페이지 폴트 핸들러가 해야하는 대략적인 일
  1. 보조 페이지 테이블에서 폴트가 발생한 페이지를 찾는다. 
     만약 메모리에 대한 참조가 유효하다면 보조 페이지 테이블 엔트리를 사용해서 데이터가 들어갈 페이지를 찾는다.
     페이지는 파일 시스템에 있거나 스왑 슬롯에 있거나 또는 단순히 0으로만 이루어져 있을 수도 있다.
     만약 당신이 공유(Copy-on-Write)를 구현한다면 페이지의 데이터는 페이지 테이블이 아니라 이미 페이지 프레임에 존재할 것이다.
     보조 페이지 테이블이 아래와 같은 정보를 나타낸다면, 그 접근은 유효하지 않다는 것이다.
     
     
     • 유저 프로세스가 접근하려던 주소에서 아무것도 얻을 수 없다.
     • 페이지가 커널 가상 메모리에 놓여있다.
     • read-only 페이지에 쓰기를 시도하는 접근이다.
     • 유효하지 않은 접근은 프로세스를 종료시키고 프로세스의 모든 자원을 해제한다.
  2. 페이지에 저장하기 위해 프레임을 얻는다.
     만약 당신이 공유(Copy-on-Write)를 구현한다면 페이지의 데이터는 페이지 테이블이 아니라 이미 페이지 프레임에 존재할 것이다.
     만약 공유(Copy-on-Write)를 구현한다면 이미 프레임 내에 원하는 데이터가 있을 것이다. 이 경우에는, 프레임의 위치를 찾을 수 있어야 한다.
  3. 파일 시스템이나 스왑으로부터 읽어들이거나 0으로 초기화하는 등의 작업을 통해 데이터를 프레임으로부터 가져온다.
     만약 공유(Copy-on-Write)를 구현한다면 이미 프레임 내에 원하는 데이터가 있을 것이다. 이 경우에는, 해당 단계에서 아무런 동작도 필요하지 않다.
  4. 폴트가 발생한 가상 주소에 대한 페이지 테이블 엔트리가 물리 페이지를 가리키도록 한다.
     threads/mmu.c 에 있는 함수를 사용해서 구현할 수 있다.

 

 

---

Managing the Frame Table

• 프레임 테이블에는 각 프레임의 엔트리 정보가 담겨 있다.
  • 페이지를 가리키는 포인터
  • 현재 해당 엔트리를 차지하고 있는 페이지에 대한 포인터(만약 있다면)
  • 그 밖의 데이터들(프로그래머의 선택에 따른)
• 비어있는 프레임이 없을 때 쫓아낼 페이지를 골라줌으로써, 핀토스가 효율적으로 eviction policy를 구현할 수 있도록 한다.

 

• 유저 페이지를 위해 사용된 프레임들은 palloc_get_page(PAL_USER) 를 호출함으로써 유저 풀에서 획득된 것 이어야한다.
• 커널 풀로부터 할당하는 것을 피하기 위해 PAL_USER 를 사용해야한다.
  • 이것은 몇몇 TC를 예기치 못하게 실패하게 할 수 있다.
• 만약 프레임 테이블 구현의 일부로 palloc.c 파일을 수정하게 된다면 유저 풀과 커널 풀 간의 구분을 명확하게 해야한다.

 

• 프레임 테이블에서 가장 중요한 작업은 사용되지 않은 프레임을 획득하는 것이다.
• 프레임이 free 상태라면 간단하지만 만약 free 상태인 프레임이 없다면 몇몇 페이지들을 프레임에서 쫓아내어 free 상태로 만들어야한다.

 

• 만약 스왑 슬록의 할당 없이 쫓아낼 수 있는 프레임이 없는데, 스왑 슬롯도 꽉 차있다면 커널을 패닉시킨다.
• 실제 OS들은 이런 상황을 막기 위해 다양한 정책을 적용하고 있지만 이러한 정책들은 이 프로젝트의 범위를 벗어난다.

 

• 프로세스 eviction의 절차
  1. 재배치 알고리즘을 사용하여 쫓아낼 프레임을 고른다.
     1. 페이지 테이블의 “accessed”, “dirty” 비트
  2. 해당 프레임을 참조하는 모든 페이지 테이블에서 참조를 제거한다.
     공유(Copy-on-Write)를 구현하지 않았을 때 해당 프레임을 참조하는 페이지는 항상 한 개만 존재해야한다.
  3. 필요하다면 페이지를 파일 시스템이나 스왑에 쓴다.
     쫓아내어진 프레임은 이제 다른 프레임을 저장하는 데 사용할 수 있다.

 

Accessed and Dirty Bits

• x86-64 하드웨어는 각 페이지 테이블 엔트리에 있는 비트 쌍을 통해 페이지 재배치 알고리즘 구현을 위한 도움을 준다.
• 페이지에 read 또는 write를 할 때, CPU는 페이지의 PTE에 있는 accessed 비트를 1로 설정한다.
• write를 할 때 CPU는 dirty 비트를 1로 설정한다.
  • CPU는 절대 이러한 비트들을 0으로 되돌리지 않고 OS가 0으로 되돌리는 작업을 수행할 수 있다.
• 같은 프레임을 참조하는 두 개의 페이지들인 aliases 를 조심해야한다.
• aliased 프레임이 accessed 될 때, accessed와 dirty 비트는 하나의 페이지 테이블 엔트리에서만 업데이트 된다.
• 💡 aliased : 동일한 주소를 다른 이름으로 불리는 상황을 alias 된다고 한다.
• 모든 유저 가상 페이지는 커널 가상 페이지에 alias 되어 있다.
  • 즉 커널과 유저가 같은 페이지를 참조할 수도 있다.
    But, 유저 va를 통해서만 유저 데이터에 접근하게 함으로써 커널은 해당 문제를 피할 수 있다.
  • 하나의 페이지 테이블 엔트리에 대해서만 ‘accessed’와 ‘dirty’ 비트가 업데이트된다.