[Project3] Virtual Memory(1) - Introduction

OS는 적절한 동기화를 통해 여러 스레드를 적절히 처리할 수 있고, 사용자 프로그램을 한번에 로드할 수있다.

하지만 실행할 수 있는 프로그램 수와 크기는 컴퓨터의 기본 메모리 크기에 따라 달라진다. 이 과제는 가상 메모리(Virtual Memory)를 구축하여, 크기 제한을 제거한다.

 

과제 시작 전에 project2가 완벽하게 마무리되어야 한다. 

 

Background

Source Files

vm 폴더 참고!!!

• include/vm/vm.h, vm/vm.c
  
  • virtual memory 기본 인터페이스를 제공한다.
  • 헤더 파일에서는 가상 메모리 시스템이 지원하는 다양한 vm_ 유형(VM_UNIT, VM_ANON, VM_FILE, VM_PAGE_CACHE)를 확인할 수 있다. (VM_PAGE_CACHE는 project4에 해당하는 내용이니 지금은 무시해도 괜찮다.)
  • 이 부분에서 우리가 앞으로 다룰 supplemental page table을 구현할 것이다.
• include/vm/uninit.h , vm/uninit.c (vm_type = VM_UNINIT)
  • 초기화되지 않은 페이지를 관리한다.
  • 현재 디자인은 모든 페이지들은 처음에 초기화되지 않은 페이지로 설정된다.
  • 이후 Anonymous page 또는 file-backed page로 변환된다.
• include/vm/anon.h, vm/anon.c (vm_type = VM_ANON)
• include/vm/file.h, vm/file.c (vm_type = VM_FILE)
• include/vm/inspect.h , vm/inspect.c
  • 점수 계산하기 위해 있는 코드니까 바꾸지 말 것!
• include/devices/block.h, devices/block.c
  • 블록 장치에 sector 기반 읽기 및 쓰기를 제공한다.
  • 블록 장치는 일정 크기(block) 단위로 접근하는 장치로, 하드 디스크와 같은 대용량 저장 장치를 말한다.
  • sector는 디지털 미디어의 트랙에 저장된 순차적 데이터의 고정 크기 단위로, 일반적으로 512바이트이다. (출처: 위키백과)

 

Memory Terminology

 

memory와 storage 관련 용어들을 알아보자.

Pages

페이지(virtual page 라고도 함!)는 길이가 4096 바이트(페이지 크기)인 가상 메모리의 연속적인 영역을 말한다.

페이지는 항상 페이지 정렬된 상태여야 한다. 예를들어, 가상 주소가 4096으로 페이지 크기가 4096이라면 페이지 정렬의 마지막 12비트는 페이지 오프셋이 된다. 상위 비트는 페이지 테이블의 인덱스를 나타내는데 사용된다.

각각의 프로세스는 독립적인 사용자(가상) 페이지 세트가 있고, 이 페이지는 가상 주소 KERN_BASE(0x8004000000) 아래에 있는 페이지이다. 반면에 kernel(virtual) 페이지는 전역이므로, 실행 중인 스레드나 프로세스에 관계없이 동일한 위치에 있다.

커널은 사용자 페이지와 커널 페이지에 모두 접근할 수 있지만 사용자 프로세스는 자신의 페이지에만 접근할 수 있다.

 

Pintos 프로젝트에서는 가상 주소 접근과 관련된 유용한 함수들을 제공한다.

 

Frames

frame은 physical frame과 page frame이라고도 불리는데, 물리적 메모리의 연속적인 영역을 말한다.

페이지처럼 frame도 페이지 크기와 페이지 정렬이 일치해야 한다. 따라서 64비트 물리 주소는 frame 번호와 frame offset으로 구분된다.

x86-64 운영체제는 실제 물리 주소에 바로 접근할 수 있는 방법을 제공하지 않는다. 하지만 Pintos는 kernel virtual memory를 바로 physical memory로 맵핑하는 방식으로 실제 물리 주소 접근을 구현한다.

 

Page Tables

페이지 테이블은 CPU가 가상 주소를 물리 주소(페이지에서 프레임)로, 변환하는데 사용하는 데이터 구조를 말한다. 페이지 테이블 형식은 x86-64 아키텍처에 따라 결정된다.

threads/mmu.c 함수에서 page table 결정에 관한 코드를 확인할 수 있다.

다음 그림은 page와 frame 사이의 관계를 표현한다.

가상 주소는 page number와 offset으로 구성되어 있다. 페이지 테이블은 page number를 frame number로 변환하고, 수정되지 않은 오프셋과 결합하여 오른쪽의 물리 주소를 얻는다.

 

Swap Slots

swap slot은 swap 파티션에서 disk 공간의 page size 영역이다. frame보다 하드웨어 제약이 유연하지만, swap slot도 페이지 정렬이 필요하다.

---

Resource Management Overview

다음 자료 구조를 설계 및 구현해야 한다.

 

Supplemental page table

page table을 추가하여 page fault를 관리할 수 있다.

 

Frame table

물리 프레임을 꺼내는 것을 효율적으로 구현하게 한다.

 

Swap table

swap slot 사용을 측정한다.

 

세 가지 데이터 구조를 모두 구현하기보다, 공통된 리소스를 찾아 구현해라.

이를 위해 각 데이터 구조가 어떤 정보를 포함해야하는지 결정하고, 데이터 구조의 범위를 로컬(프로세스 별) 또는 전역(시스템 전체)으로 결정하고 범위 내에 필요한 인스턴스 수를 결정한다.

 

설계를 단순화하기 위해 데이터 구조를 페이징할 수 없는 메모리에 저장할 수 있다.(calloc 또는 malloc으로 할당된 메모리) 페이징할 수 없는 메모리에 할당된 데이터들은 메모리 페이지로 나누어지지 않고 연속적으로 저장되므로, 포인터를 통해 참조하거나 연결될 수 있다.

---

Choices of implementation (Performance perspective)

table을 구현할 수 있는 방식은 array, list, bitmap, hash table 등이 있다.

 

array

• 구현이 간단하지만, 사이사이 비어있는 부분들은 메모리를 낭비한다. 

List

• 구현이 간단하지만, 특정 위치를 찾기 위해 리스트의 크기만큼 탐색해야한다.

⇒ 두 방식 모두 크기 조정이 가능하다. 다만 리스트가 중간에 원소 삽입, 삭제 등을 더 효율적으로 제공한다.

 

bitmap(lib/kernel/bitmap.c, include/lib/kernel/bitmap.c 참고)

• bitmap은 true 또는 false인 bits의 집합을 말한다.
• 보통 (동일한) resource 집합 사용량을 추적하는데 사용된다. 예를들어, 리소스 n이 사용 중이면 비트맵 비트 n은 참이 된다. 비트맵의 크기는 고정되어있지만 크기를 조절할 수 있는 기능을 추가해도 된다.

hash table(lib/kernel/hash.c, include/lib/kernel/hash.h 참고)

• pintos 해시 테이블은 테이블 크기에 상관없이 삽입, 삭제를 지원한다.

 

데이터 구조는 복잡할수록 성능이 향상될 수 있지만, 구현이 복잡해진다.

---

Managing the Supplemental Page Table

페이지 테이블은 가상 페이지에 대한 물리 메모리 주소 맵핑 정보를 포함한 데이터 구조이다.

보통 매우 간단하고 제한된 크기로 설계되기 때문에 정보가 제한되어있고 특정 요구사항을 구현하려면 추가 데이터가 필요하다.

 

Supplemental Page Table은 추가 데이터를 저장하고, 필요한 정보를 제공해 페이지 테이블이 갖고 있는 한계점을 보완한다.

장점은 다음과 같다.

• Page fault가 발생하면 커널이 SPT에서 오류가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지 알아낼 수 있다.
• 커널은 프로세스가 종료될 때 SPT를 참고하여 어떤 리소스를 해제할지 결정할 수 있다.

Organization of Supplemental Page Table

SPT는 segment 기반 또는 page 기반으로 구성할 수 있다.

• 세그먼트 기반
  • 세그먼트는 연속된 페이지 영역, 즉 하나의 세그먼트는 하나의 실행 가능한 프로그램이나 메모리 맵핑된 파일을 말한다.
• 페이지 기반
  • 개별 페이지에 대한 정보를 추적하고 매핑한다. 즉 페이지의 상태, 소유자, 권한 정보를 포함할 수 있다.
  • SPT의 멤버를 추적할 수 있는데, 이 방식은 테이블 엔트리를 이해하여 페이지 테이블과 SPT 관계를 구축해야 한다.
  • 꼭 하지 않아도 된다. 자신있는 사람은 해보기~

Handling page fault

지금까지 page fault는 커널 또는 사용자 프로그램 버그를 의미했다.

 

앞으로 나오는 page fault는 페이지를 file 또는 swap slot에서 가져와야 한다는 것을 말한다.

userprog/exception.c 의 page_fault() 함수는 vm/vm.c 의 vm_try_handle_fault()를 호출하여 성공 여부를 반환한다.

page_fault() 에서 구현해야하는 것은 다음과 같다.

1. SPT에서 오류가 발생한 페이지를 찾는다.
   • 메모리 참조를 확인할 수 있다면, SPT에서 file이나 swap slot에 있거나 all zero page인 데이터를 찾는다.
     • all-zero page는 메모리에 할당된 페이지에 데이터가 존재하지 않음을 말한다.
   • sharing(copy on write)를 구현했다면 페이지의 데이터가 page frame에 있지만, page table에 없을 수도 있다.
   • SPT에 사용자 프로세스가 접근하려는 주소에 데이터가 없는 경우, 페이지가 kernel virtual memory에 있거나 read only page에 쓰기를 시도할 때 접근이 유효하지 않다고 표시된다면 해당 접근은 유효하지 않다.
   • 유효하지 않은 접근이 들어오면 프로세스를 중단하고 즉시 자원을 반환한다.
2. 페이지를 저장할 프레임을 가져온다.
   • 공유 기능은 여러 프로세스가 동일한 라이브러리 함수를 호출할 때, 해당 함수의 코드와 데이터가 공유되는 것을 말한다. 이때 여러 프로세스가 같은 데이터를 참조하려면 해당 데이터가 프레임에 저장되어야 한다.
3. file이나 swap에서 데이터를 읽거나 zero로 데이터를 초기화하여 데이터를 프레임으로 가져온다.
   • 공유 기능을 구현했다면 이미 필요한 페이지가 프레임에 있을 수 있어, 추가 작업이 필요 없다.
4. faulting 가상 주소를 실제 페이지로 가리킨다. (threads/mmu.c 함수 참고)

 

Managing the Frame Table

프레임 테이블은 각 프레임에 하나의 항목이 포함된다.

프레임 테이블은 사용 중인 페이지 포인터(있다면)와 사용자가 추가한 기타 데이터를 포함한다. 이를 통해 사용할 수 있는 프레임이 없을 때, 어떤 프레임을 제거할지 결정하는 방식을 구현할 수 있다.

User page에서 사용되는 프레임은 palloc_get_page(PAL_USER) 를 호출하여 ‘유저 풀’에 가져와야 한다. ‘커널 풀’에서 할당하지 않으려면 PAL_USER를 사용해야 한다. 프레임 테이블을 구현할 때 palloc.c를 수정한다면 두 풀을 잘 구분해야 한다.

+) pool은 메모리 할당을 위해 사전에 미리 할당된 메모리 영역을 말한다.

 

프레임 테이블은 사용하지 않은 프레임을 획득하는 것이 중요하다.

만약 프레임이 비어있지 않다면, 프레임 제거 정책을 통해 프레임을 일부 제거하여 사용 공간을 얻으면 된다.

 

특정 프레임을 제거하는 기능을 구현하려면, swap slot 할당이 필요하다. swap slot이 가득차면 커널이 패닉 상태에 빠지기 때문에, OS는 이 상황을 복구하기 위해 다양한 정책을 사용한다. 이 과정에서는 여기까지 고려하지 않아도 된다.

 

프레임 제거 단계는 다음과 같다.

1. 페이지 교체 알고리즘을 이용하여 제거할 프레임을 결정한다.
   • accessed, dirty 비트를 사용한다.
2. 프레임을 참조하는 모든 테이블에서 프레임 참조를 제거한다. 공유 기능이 구현되지 않은 상태에서는 한번에 하나의 페이지만 프레임을 참조해야 한다.
3. 페이지를 파일 시스템에 쓰거나 바꾼다.

 

Accessed and Dirty Bits

x86-64 하드웨어는 각 페이지의 PTE에 있는 쌍으로 된 비트로 페이지 교체 알고리즘을 구현한다.

페이지에 읽기나 쓰기 작업을 할 때, CPU는 페이지의 PTE의 accessed bit을 1로 수정한다. 만약 수정하는 작업을 한다면 dirty bit를 1로 바꾼다. CPU는 절대 bit를 0으로 바꿀 수 없지만, OS는 가능하다.

 

alias 는 동일한 프레임을 참조하는 두 개 이상의 페이지를 말한다(공유). 만약 aliased 프레임에 접근하면, 접근된 비트와 더티 비트는 하나의 페이지 테이블 항목(access에 사용된 페이지에 대한 항목)에만 업데이트된다. 즉, 동일한 프레임을 참조하는 다른 alias에 대한 비트들은 업데이트되지 않는다.

 

Pintos에서 모든 user virtual memory가 kernel virtual page에 alias로 지정되므로, 이를 관리하는 것이 필요하다. 예를 들어, 두 주소 모두 accessed bit와 dirty bit를 확인하거나 커널이 사용자 가상 주소를 통해 사용자 데이터에 접근하도록 한다.

 

Managing the Swap Table

스왑 테이블은 사용 중인 스왑 슬롯과 사용 가능한 스왑 슬롯을 찾는다. 사용하지 않은 스왑 슬롯을 선택하면 된다. 따라서 페이지를 다시 읽거나 페이지가 스왑된 프로세스가 종료될 때 스왑 슬롯을 해제해야 한다.

vm/build 경로에서, pintos-mdisk swap.sk --swap-disk=n 을 사용한다. 이 명령은 n-MB사이즈의 swap 파티션을 포함하고 있는 swap 디스크를 생성한다.

swap slot은 페이징 교체 과정에서 필요할 때만 할당된다. 프로세스를 시작할 때, 실행 파일에서 데이터 페이지를 읽어와 즉시 기록하는 것은 레이지 로딩이 아니다. 만약 스왑 슬롯에 저장된 페이지 내용이 다시 프레임으로 읽혀질 때, 스왑 슬롯을 해제해야 한다.

 

이를 통해 스왑 공간을 효율적으로 사용할 수 있고, 필요하지 않은 스왑 슬롯 예약을 방지한다.

 

Managing Memory Mapped Files

file system은 read와 write 시스템 콜로 접근된다.

mmap 시스템 콜은 파일을 가상 메모리에 맵핑한다. 프로그램은 파일 데이터에 직접 메모리 명령을 사용할 수 있게 된다.

 

예를 들어, 파일 foo의 길이가 0x1000바이트(4KB)라면 foo는 주소 0x5000에서 시작하는 주소에 매핑되었을 때, 0x5000 ~ 0x5fff 위치에 있는 모든 메모리는 foo의 해당 바이트에 액세스하게 된다.

다음은 mmap로 콘솔에 파일을 인쇄하는 프로그램이다.

#include <stdio.h>
#include <syscall.h>
int main (int argc UNUSED, char *argv[])
{
  void *data = (void *) 0x10000000;                 /* Address at which to map. */
  int fd = open (argv[1]);                          /* Open file. */
  void *map = mmap (data, filesize (fd), 0, fd, 0); /* Map file. */
  write (1, data, filesize (fd));                   /* Write file to console. */
  munmap (map);                                     /* Unmap file (optional). */
  return 0;
}

메모리 매핑된 파일에서 어떤 메모리를 사용하고 있는지 찾을 수 있어야 한다. 이 기능은 페이지 오류를 처리하고 매핑된 파일이 프로세스 내에 다른 세그먼트와 겹치지 않도록 하기 위해 필요하다.