IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)

[PintOS] Project 3 : Virtual Memory 이해

eezy 2025. 6. 4. 14:04

[Gitbook] Project 3 : Virtual Memory

PintOS-KAIST gitbook을 기반으로 Project 3에 들어가기 전에 필요한 용어를 정리해보았다. 이해 중인 단계로 틀린 내용이 있다면 언제든지 알려주시면 감사하겠습니다. 😊

PintOS Virtual Memory Structure

이동석 코치님의 Virtual Memory 자료에 내가 이해한 Virtual Memory, Frame의 구조를 추가한 자료이다. 위 그림에서는 우리가 앞으로 배울 내용에 대하여 자료가 어디에 저장되는지, 어떤 과정을 통해 변환 되는지를 살펴 보았다.

Pintos는 x86-64 아키텍처 기반의 4단계 페이지 테이블 구조를 따른다. 이 구조를 통해 사용자 프로그램의 가상 주소(Virtual Address)는 실제 물리 메모리(Physical Memory)의 프레임(Frame)으로 매핑된다.

Pintos에서 커널 가상 메모리(Kernel Virtual Memory)는 물리 메모리와 1:1로 매핑되어 있다. 따라서 커널은 페이지 테이블을 거치지 않고도 직접 물리 메모리에 접근할 수 있으며, 이는 운영체제 구조 설계에 있어 중요한 전제가 된다.

Virtual Address Structure

x86-64 시스템에서 가상 주소는 64비트이지만, 실제로 사용하는 공간은 중간의 48비트이다. 상위 16비트는 sign-extension 영역으로, 유효한 주소인지 여부를 판단하는 데 사용된다. 주소의 47번째 비트를 기준으로 나머지 상위 비트를 모두 동일하게 맞추지 않으면 CPU가 General Protection Fault를 발생시킨다.

가상 주소는 다음과 같은 5단계 계층으로 구성되어 있다.

  • Sign Extend (상위 16비트): 주소 유효성 판단에 사용된다.
  • PML4 (9비트): Page Map Level 4. 최상위 페이지 테이블이다.
  • PDPT (9비트): Page Directory Pointer Table
  • PD (9비트): Page Directory
  • PT (9비트): Page Table
  • Offset (12비트): 페이지 내 오프셋으로, 하나의 페이지는 4KB이며 이 하위 12비트는 해당 페이지 내부에서의 byte 위치를 의미한다.

이러한 계층 구조를 통해 CPU는 페이지 테이블을 단계적으로 탐색하여 해당 가상 주소가 어떤 물리 프레임에 매핑되어 있는지를 확인한다.

PML4부터 PT까지 총 36비트는 Virtual Page Number(VPN)를 구성한다. VPN은 고유한 가상 페이지를 식별하는 번호이며, 페이지 테이블은 이 VPN을 기반으로 해당 페이지에 어떤 물리 프레임이 연결되어 있는지를 기록한다.

따라서 하나의 가상 주소는 VPN과 Offset으로 나눌 수 있으며, 페이지 테이블은 이 VPN을 통해 빠르게 대응되는 물리 주소를 탐색하고, Offset을 결합하여 최종적인 물리 주소를 완성하게 된다.

Memory Terminology

  1. Page
    • 크기: 4,096바이트 = 4KB
    • 정렬 조건: 페이지 정렬됨(page-aligned) → 시작 주소가 4096의 배수여야 함
      • 예: 0x804000, 0x400000, 0x8000 등은 올바른 페이지 시작 주소
    • 용어 정리:
      • Offset: 페이지 내에서의 위치 (하위 12비트)
      • Page number: 가상 주소에서 페이지를 식별하는 상위 비트
    • KERN_BASE = 0x8004000000 (512GB 영역 기준)
    • 사용자 주소 공간: 0 ~ KERN_BASE 미만
      • 각 사용자 프로세스마다 독립적인 주소 공간
    • 커널 주소 공간: KERN_BASE 이상
      • 모든 프로세스에서 공통된 가상 주소 공간
      • 커널은 user + kernel 접근 가능
      • 유저 프로세스는 user 영역만 접근 가능
    • 기본적으로 페이지는 공유되지 않는다. 각 프로세스는 독립된 가상 주소 공간을 가지고, 그 가상주소는 각자의 물리 프레임으로 매핑된다. 각 프로세스가 독립적으로 실행되고, 서로의 주소 공간을 읽거나 쓰지 못하도록 막기 위함이다.
      • 하지만 공유를 구현할 수 있다. 파일 매핑, 공유 라이브러리, COW 등을 통해.
  2. Frame
    • 물리 메모리 상에서 연속된 4KB 크기의 메모리 블록
    • 페이지 크기의 단위로 반드시 페이지 정렬 되어야 한다 → 즉 주소가 4096으로 나누어떨어지는 위치에서 시작해야 한다
    • 64비트 물리 주소는 다음과 같이 나뉜다
      • 상위 비트 : 프레임 번호
      • 하위 12비트 : 오프셋
    • x86-64 아키텍처에서는 물리 주소를 직접 접근할 수 없습니다.
    • Pintos는 이를 우회하기 위해 커널 가상 주소 영역을 물리 메모리에 일대일로 매핑했다. 즉, 물리 프레임은 커널 가상 주소를 통해 접근할 수 있다.
  3. Page Table
    • 가상 주소를 물리 주소로 변환해주는 자료 구조
    • 프로세스가 사용하는 가상 페이지 번호를 실제 물리 메모리의 프레임 번호로 매핑한다
    • 변환 과정 :
      • 가상 주소 = 페이지 번호 + 오프셋
      • 페이지 테이블이 페이지 번호를 프레임 번호로 변환
      • 변환된 프레임 번호 + 원래의 오프셋 = 물리 주소
    • Pintos에서는 x86-64 구조를 따르며, 4단계 페이지 테이블을 사용. 관련 코드는 threads/mmu.c에 있으며, 가상 주소 할당, 해제, 매핑 등을 담당하는 함수들이 있다
  4. Swap Slot
    • 스왑 파티션에 있는 페이지 크기(4KB)의 디스크 영역으로 물리 메모리가 부족할때 디스크에 페이지를 임시 저장하는 공간이다
    • 스왑 슬롯 역시 페이지 정렬되어야 한다
    • 일반적으로 페이지 단위의 읽기/쓰기가 가능하도록 설계되어 있다.

FYI : Pintos에서 제공하는 주소 관련 함수

  • is_user_vaddr() : 가상 주소가 사용자 영역인지 확인
  • is_kernel_vaddr() : 커널 영역 주소인지 확인
  • pg_round_up() / pg_round_down() : 페이지 단위로 주소 정렬
  • pg_ofs() : 주소의 페이지 오프셋 반환
  • pg_no() : 주소가 속한 페이지 번호 반환

Choices of Implementation

가능한 구현 방식으로는 배열(array), 리스트(list), 비트맵(bitmap), 해시 테이블(hash table) 등

  • 배열(array) 은 가장 단순한 방식이지만, 배열이 희소하게 채워질 경우 메모리가 낭비될 수 있습니다.
  • 리스트(list) 도 단순하지만, 특정 위치를 찾기 위해 긴 리스트를 순회해야 한다면 시간이 낭비됩니다.
  • 배열과 리스트는 모두 크기를 조정(resizing)할 수 있지만, 리스트는 중간 삽입과 삭제를 더 효율적으로 처리할 수 있습니다.
  • 비트맵
    • Pintos는 lib/kernel/bitmap.c와 include/lib/kernel/bitmap.h에 비트맵 자료구조를 포함
    • 비트맵은 true 또는 false 값을 가지는 비트의 배열입니다.
    • 보통 동일한 종류의 자원을 관리할 때 사용 → n번 자원이 사용중일때 n번째 비트가 True
    • Pintos의 비트맵은 크기가 고정되어 있으며, 필요하다면 이를 확장하여 크기 조절(resizing)을 지원하도록 구현 가능
  • 해시테이블
    • Pintos의 해시 테이블은 다양한 크기에서 삽입과 삭제를 효율적으로 지원

Supplemental Page Table (SPT)

  1. 개념
    • 기본 page table은 MMU가 직접 관리해서 소프트웨어가 쉽게 볼 수 없음
    • 그래서 각 프로세스마다 page fault 발생 시 어떤 데이터를 어떻게 로딩해야 할지를 저장하는 보조 자료구조가 필요함
    • 이 자료구조가 있어야 지연 할당(lazy allocation), 스왑, mmap 파일 등을 구현할 수 있다
  2. 구성 요소
    • 가상 주소 (page 단위, aligned)
    • vm_type (UNINIT, ANON, FILE 등)
    • 초기화 함수 포인터 (lazy load용)
    • Frame 구조체 포인터 (frame 할당된 경우)
    • File 정보 (file-mapped page 인 경우)
    • Swap 슬롯 인덱스
    • Writable 여부
  3. 구성 방식
    • 페이지 단위 구성 (추천): 개별 페이지 주소마다 엔트리를 갖는 방식
    • 세그먼트 단위 구성: ELF 등에서 연속된 주소 범위를 의미하는 세그먼트 기준으로 묶는 방식
    • 구현 방식으로는 주로 해시 테이블을 사용 → Pintos는 lib/kernel/hash.c를 제공
  4. 범위
    • 프로세스 단위로 관리
    • struct thread 안에 struct hash spt; 로 표현
  5. 역할
    • 페이지 폴트 처리
    • 프로세스 종료 시, SPT를 참고하여 점유 중인 자원(프레임, 스왑 슬롯 등)을 정리
  6. 페이지 폴트 처리 절차
    1. 폴트 주소 확인 및 SPT 조회
      • vm_try_handle_fault() (vm/vm.c)
      • SPT에서 faulting address를 검색하여 해당 페이지 정보를 찾는다
      • 주소가 유효하지 않거나 커널 영역이거나, 읽기 전용 페이지에 쓰기 요청한 경우 → 프로세스 종료
    2. 프레임 확보
      • 페이지를 올릴 물리 프레임(frame)을 확보한다
      • 프레임 테이블에서 사용 가능한 프레임이 없으면 eviction 필요
    3. 데이터 로딩
      • SPT에 따라 파일에서 읽거나, 스왑에서 복구하거나, zero page로 초기화한다.
      • Copy-on-Write 구현 시 이미 존재하는 프레임을 참조할 수도 있다
    4. 페이지 테이블에 매핑
      • pml4_set_page() 등 mmu.c의 API를 사용하여 가상 주소 → 물리 프레임을 매핑한다

Frame Table

  1. 개념
    • 프레임은 실제 RAM의 한 페이지(4KB) 단위 블록
    • 이 프레임은 커널에 의해 관리되고, 어떤 프로세스의 어떤 가상 주소에 매핑되어 있는지 기록해야 하고
    • 이 기록하는 곳이 프레임 테이블 (즉 물리 메모리에 대한 추상화)
  2. 역할
    • 모든 물리 프레임을 추적해서, 페이지를 메모리에 올릴 때 어디에 올릴지 결정하고
    • eviction (쫓아내기) 시 어떤 frame을 제거할지 정책 기반으로 선택
  3. 구성 요소
    • kernel virtual address
      • palloc_get_page(PAL_USER)로 얻은 주소
      • 이 프레임이 물리 메모리의 어디를 가리키는지를 나타낸다
    • 해당 프레임을 참조하는 SPT 엔트리 포인터
    • 소유자 스레드 or 프로세스 포인터
      • 어떤 스레드/프로세스가 이 프레임을 사용하는지 나타냄 → 소유자를 알아야 eviction 시 해당 프로세스의 페이지 테이블 수정 가능
      • struct thread *owner
    • Eviction 우선순위 정보
      • 어떤 프레임이 최근에 사용됐는지 알기 위해 accessed 비트 저장
      • CLOCK 알고리즘 등 구현 시 필요
    • 락
      • 선택사항으로 다중 스레드 환경에서 동시 접근 방지용
  4. 범위
    • 시스템 전역으로 관리
    • 하나의 global frame table 필요
  5. Eviction 절차
    1. Eviction 대상 프레임 선택
      • Accessed bit, Dirty bit을 사용하여 판단
      • Second-chance algorithm, clock algorithm 구현 필요
    2. Page table에서 매핑 제거
      • 해당 프레임을 참조 중인 모든 페이지 테이블 항목에서 연결 해제
      • 일반적으로 한 프레임은 하나의 페이지와 매핑됨
    3. 스왑 또는 파일 시스템에 백업
      • 익명 페이지 → 스왑으로
      • 파일 매핑 페이지 → 다시 파일에 저장 (Dirty만)
      • 스왑이 가득 찬 경우 → 커널 패닉
    4. 해당 프레임 재활용
      • 다른 페이지가 사용할 수 있도록 준비

Swap Table

  1. 역할
    • swap partition 을 페이지 단위로 쪼개서 어떤 슬롯이 사용 중인지 추적
    • 페이지가 evict될 때 디스크에 저장하고 다시 필요할 때 불러온다
  2. 구성 요소
    • 비트맵 (slot 사용 여부)
    • 필요 시, 각 슬롯에 어떤 페이지가 들어있는지 역추적 가능한 메타데이터 추가
  3. 범위
    • 시스템 전역으로 관리

 

Page Fault Handling
Eviction Process

 

 

Accessed & Dirty Bits

x86-64 아키텍처에서 page replacement 알고리즘 구현에 도움이 되는 Accessed 및 Dirty 비트의 사용 방식에 대해 알아보자

 

Page Table Entry(PTE) 안에 존재하는 두 개의 중요한 상태 비트이다

  • Accessed bit
    • 페이지에 읽기 또는 쓰기 접근이 있었을 때 CPU가 자동으로 1로 설정한다
  • Dirty bit
    • 페이지에 쓰기(write)가 있었을 때 CPU가 자동으로 1로 설정한다

CPU는 이 비트를 직접 초기화(0으로 리셋)하지 않으며, 운영체제가 수시로 비트를 확인하고 수동으로 초기화해야 한다. 이 동작은 페이지 교체 알고리즘 (예: Clock, LRU 근사) 등에 사용된다.

활용 함수 : pml4_is_dirty() & pml4_is_accessed()

Alias 문제

하나의 물리 프레임을 여러 가상 주소가 참조할 때를 aliasing이라 한다


PintOS 에서 사용자 주소 공간과 커널 주소 공간이 같은 물리 프레임을 참조할 경우 alias가 발생하고

→ 이 때 Accessed / Dirty 비트는 오직 접근된 PTE에만 갱신되며 다른 alias된 PTE들에는 반영되지 않는것이 문제다.

✅ 해결 방안

  1. 두 PTE 모두에 대해 Accessed / Dirty 상태를 수동으로 동기화한다
    • 커널이 사용자 페이지를 접근할 일이 있다면,
    • 접근 전에 사용자 쪽 PTE를 조회해서 상태를 읽거나
    • 접근 후 수동으로 user 쪽 PTE에 Accessed/Dirty 비트를 설정
  2. 항상 사용자 주소(user virtual address)를 통해서만 접근하도록 한다
    • 커널이 사용자 데이터에 접근할 때도 copy_from_user(), get_user() 등을 사용하여 항상 user VA를 통해 접근하도록 한다