[PintOS 4주차] Day 0-1

munsik22 2025. 5. 28. 17:20

핀토스 3주차는 내부 사정으로 하루 일찍 발표 및 발제를 해서 4주차를 하루 먼저 시작하게 되었다.

작업 환경 설정

새로운 팀원들과 함께 새로운 레포지토리를 생성했다. clone도 새로 하고, make check가 잘 되는지 확인하려고 했는데 오류가 발생했다.

$ make check
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/args-none:args-none -- -q   -f run args-none < /dev/null 2> tests/userprog/args-none.errors > tests/userprog/args-none.output
../../tests/Make.tests:75: recipe for target 'tests/userprog/args-none.output' failed

지난 번에 pintos 경로 설정을 해줬는데, 레포지토리 이름이 바뀌었기 때문에 다시 설정해줘야 했다.

$ sudo rm /usr/local/bin/pintos
$ sudo ln -s ~/github/[레포이름]/utils/pintos /usr/local/bin/pintos

한편, Docker 환경을 사용하는 다른 팀원의 경우, clone받은 파일들의 줄바꿈 형식이 CRLF로 설정되어 있어서 전부 LF로 변경해야 했다.

Introduction #

🔹 User Memory Layout

🔹 Memory Terminology

▪ Page: Virtual Memory의 연속적인 영역
▪ Frame: Physical Memory의 연속적인 영역
▪ Page Table: 가상주소를 물리주소로(Page를 Frame으로) 변환하는 자료구조
▪ Eviction: Page를 Frame에서 제거하고 Swap Table이나 파일 시스템에 잠재적으로 write하는 것
▪ Swap Table: Swap partition에서 evicted pages가 written되는 곳

페이지

Page(= Virtual Page)는 길이가 4KB(= page size)인 연속적인 가상 메모리 영역이다.
페이지는 반드시 page-aligned되어야 한다: 즉, page size로 나누어 떨어지는 가상 주소에서 시작해야 한다.
64비트 가상 주소의 하위 12비트는 page offset(= offset)이다.
상위 비트는 페이지 테이블의 인덱스를 나타내는 데 사용된다. (곧 도입될 예정)
64bit 시스템에서는 4-level 페이지 테이블을 사용하고, 가상 주소는 다음과 같다.

각 프로세스는 가상 주소 KERN_BASE (0x8004000000) 아래에 있는 독립적인 user (virtual) page 세트를 가진다.
반면 kernel (virutal) page는 전역적이라서 실행 중인 스레드나 프로세스에 관계없이 동일한 위치를 유지한다.
커널은 user page와 kernel page 모두에 접근할 수 있지만, 유저 프로세스는 자신의 user page에만 접근 가능하다.

프레임

Frame(= physical frame, page frame)은 물리 메모리의 연속적인 영역이다.
페이지와 마찬가지로 프레임도 page size에 맞춰서 정렬돼야 한다.
64bit 시스템에서는 다음과 같이 frame number와 frame offset(= offset)으로 나눌 수 있다.

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

x86-64는 물리 주소의 메모리에 직접적으로 접근할 수 있는 방법을 제공해주지 않기 때문에, 핀토스는 커널 가상 메모리를 물리 메모리에 직접 매핑해서 이 문제를 해결한다. 즉, kernel virtual memory의 첫번째 페이지는 물리 메모리의 첫번째 프레임에 매핑되고, 두번째 페이지는 두번째 프레임에 매핑되는 식이다. 따라서 프레임은 커널 가상 메모리를 통해 접근할 수 있다.

페이지 테이블

Page table은 CPU가 가상 주소를 물리 주소로, 즉 페이지에서 프레임으로 변환하는 데 사용하는 데이터 구조다. 다음 그림은 페이지와 프레임의 관계를 나타낸 것이다.

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

왼쪽의 가상 주소는 페이지 번호와 오프셋으로 구성된다. 페이지 테이블은 페이지 번호를 프레임 번호로 변환하고, 이 프레임 번호는 수정되지 않은 오프셋과 결합돼서 오른쪽의 물리 주소를 얻는다.

스왑 슬롯

Swap slot은 swap partition에서 page size의 디스크 공간 영역이다. 슬롯 배치를 결정하는 HW 제약은 프레임보다는 더 유연하지만, 스왑 슬롯은 page-aligned 되어야 한다.

🔹 Resource Management Overview

리소스 관리 개요

다음 데이터 구조를 설계 및 구현해야 한다. (반드시 완전히 다른 세 개의 데이터 구조를 구현할 필요는 없다. 관련 리소스를 전체 또는 부분적으로 통합하여 하나의 통합된 데이터 구조로 만드는 것이 편리할 수 있다.)

Supplemental page table: 페이지 테이블을 보조해서 Page fault를 처리할 수 있게 한다.
Frame table: Physical frame의 eviction 정책을 효율적으로 구현할 수 있다
Swap table: Swap slot 사용을 추적한다.

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

구현 선택 (성능 관점)

구현 가능한 방법으로는 배열, 리스트, 비트맵, 해시 테이블 등이 있다.

배열은 대개 가장 간단한 방법이지만, 희박하게 채워진 배열은 메모리를 낭비한다.
리스트도 간단하지만, 긴 리스트를 순회하며 특정 위치를 찾는 데 시간이 낭비된다.
- 배열과 리스트 모두 크기 조절이 가능하지만, 리스트는 중간 삽입과 삭제를 더 효율적으로 지원한다.
비트맵은 각각이 true나 false가 될 수 있는 비트들의 배열이다.
- 일반적으로 (동일한) 리소스 세트 내에서 사용을 추적하는 데 사용된다.
- 리소스 n이 사용 중이라면 비트맵의 n번째 비트가 true가 된다.
- 기본적으로는 고정된 크기를 가지지만, 크기를 바꿀 수 있도록 구현할 수 있다.
해시 테이블은 다양한 범위의 테이블 크기에서의 삽입과 삭제를 효율적으로 지원한다.

🔹 Managing the Supplemental Page Table

보조 페이지 테이블의 관리

Supplemental page table은 각 페이지에 대한 보조적인 데이터(데이터의 위치, 대응하는 커널 가상 주소로의 포인터, active/inactive 등)를 추적하는 프로세스 별 자료구조다.

각 페이지에 대한 추가적인 데이터로 페이지 테이블을 보완한다.
페이지 테이블의 포맷으로 인해 생기는 제한들 때문에 필요하다.
종종 "page table"로도 불리는데, 헷갈리지 않기 위해 "supplemental"이라는 단어를 추가했다.

보조 페이지 테이블은 다음 두 가지 목적을 가진다:

Page falut에서, 커널은 어떤 데이터가 어디에 있어야 하는지 찾기 위해 보조 페이지 테이블의 가상 페이지를 조회한다.
프로세스가 종료되면 커널은 어떤 리소스를 free할 지 결정한다.

보조 페이지 테이블의 구조

세그먼트나 페이지 관점에서 구조에 접근할 수 있다. 여기서 segment는 페이지의 연속적인 그룹(실행 파일을 포함한 메모리 영역이나 memory-mapped된 파일 등)을 의미한다. 또는 보조 페이지 테이블의 멤버를 추적하기 위해 페이지 테이블 자체를 쓸 수도 있다(단, Pintos 페이지 테이블 구현을 수정해야 한다).

Page fault 다루기

지난 프로젝트에서는 Page fault가 항상 커널이나 유저 프로그램에서의 버그를 의미했다. 하지만 이제부터는, Page fault는 파일이나 스왑 슬롯으로부터 페이지를 가져와야 한다는 것을 의미한다. 이러한 케이스들을 다루기 위해서 더 정교한 page fault 핸들러 page_fault()를 구현해야 한다.

보조 페이지 테이블(SPT)에서 faulted된 페이지의 위치를 찾는다.
- 메모리 참조가 유효하면, 페이지에 들어가는 데이터(파일 시스템, 스왑 슬롯에 있거나, 아니면 all-zero 페이지일 수도 있다)를 찾기 위해 보조 페이지 테이블 엔트리(SPTE)를 사용한다.
- 공유(Copy-on-Write 등)를 구현한다면, 페이지의 데이터는 이미 페이지 프레임에는 있지만 페이지 테이블에는 없을 수도 있다.
- SPT가 유저 프로세스가 접근을 시도하던 주소에서 어떤 정보도 받을 수 없다거나, 페이지가 커널 VM단에 의존하거나, 또는 read-only 페이지에 쓰기를 시도하거나 할 때, 접근은 무효화된다.
- 어떤 무효한 접근은 프로세스를 종료시키고 모든 리소스를 free시킨다.
페이지를 저장하기 위한 프레임을 얻는다.
- 공유를 구현단다면, 필요한 데이터는 이미 (찾을 수 있어야 하는) 프레임 안에 있다.
파일 시스템이나 스왑으로부터 데이터를 읽거나 0으로 만들어서 프레임 내부에 데이터를 가져온다.
Faulting virtual address의 PTE를 물리 페이지를 가리키게 한다.

🔹 Managing the Frame Table

프레임 테이블 관리하기

프레임 테이블은 각 프레임에 대한 하나의 엔트리를 포함한다.
- 프레임 테이블 내의 각 엔트리는 페이지로의 포인터(현재 가지고 있는 경우) + 다른 데이터들을 포함한다.
- 프레임 테이블은 free되는 프레임이 없을 때 내쫓을 페이지를 골라줌으로써 핀토스가 효율적으로 eviction policy를 구현하도록 허용해준다.
유저 페이지에서 사용되는 프레임은 palloc_get_page(PAL_USER)를 호출해서 "user pool"에서 부터 얻어와야 한다.
프레임 테이블의 가장 중요한 동작은 사용되지 않은 프레임을 얻는 것이다: 프레임이 free 상태면 쉽지만, 아무것도 free 상태인 것이 없다면, 프레임은 몇 개의 페이지를 내쫓음으로써 free 상태를 만들어야 한다.
스왑 슬롯의 할당 없이 내쫓을 프레임이 없는데 스왑이 꽉 찬 상태하면 kernel panic이 발생한다. (실제 OS들은 이러한 상황을 해결하거나 막기 위해 더 넓은 범위의 정책을 사용한다.)
Eviction은 대략 다음 단계들을 거친다.
1. 페이지 교체 알고리즘을 사용해 내쫓을 프레임을 선택한다: 페이지 테이블의 "accessed", "dirty" 비트들이 유용할 것이다.
2. 그 프레임을 참조하는 페이지 테이블에서 참조를 제거한다: 공유를 구현하지 않았다면, 오직 하나의 페이지만 그 프레임을 참조하고 있어야 한다.
3. 필요한 경우 파일 시스템이나 스왑에 페이지를 write한다: 내쫓긴 프레임은 이후에 다른 페이지를 저장하는 데 사용될 것이다.

Accessed bit와 Dirty bit

x86-64 HW는 각 페이지의 PTE의 비트 쌍을 통해 페이지 교체 알고리즘을 구현하는 데 약간의 도움을 제공한다.
- 페이지를 read나 write할 때, CPU는 그 페이지의 PTE에서 accessed bit를 1로 설정한다.
- write할 때, CPU는 dirty bit를 1로 설정한다.
- CPU가 이 비트들을 0으로 리셋하지는 않지만, OS는 그럴 수도 있다.
aliases, 즉 같은 프레임을 참조하는 두 개 (또는 그 이상)의 페이지들을 인지해야 한다.
- aliased된 프레임이 접근될 때, accessed bit와 dirty bit는 (접근에 사용되는 페이지를 위한) 오직 하나의 PTE에서만 업데이트되어야 한다.
- 다른 aliases의 accessed bit와 dirty bit는 업데이트되지 않는다.
핀토스에서 모든 유저 가상 페이지는 커널 가상 페이지에 aliased된다. 어떻게든 이러한 aliases를 관리해야 한다.
- 예를 들어, 두 주소에 대해 accessed bit와 dirty bit를 확인하고 업데이트할 수 있어야 한다.
- 또는 커널이 오직 유저 가상 주소를 통해 유저 데이터에 접근하도록 해서 문제를 피할 수 있어야 한다.
다른 aliases는 공유를 구현한 경우, 또는 버그가 있는 경우에만 나타나야 한다.

🔹 Managing the Swap Table

스왑 페이지 관리하기

스왑 테이블은 사용 중/free 상태인 스왑 슬롯들을 추적한다.
- 페이지를 프레임에서 스왑 파티션으로 내쫓기 위해 사용하지 않는 스왑 슬롯을 고를 수 있게 해야 한다.
- 페이지가 read back되거나 페이지가 스왑된 프로세스가 종료되면 스왑 슬롯을 free할 수 있게 해야 한다.
스왑 슬롯은 lazy하게 할당되어야 한다: 즉, eviction에 의해 실제로 요구될 때에만 할당되어야 한다.
- 프로세스의 시작에 실행가능 파일에서 데이터 페이지를 읽고 스왑에 write하는 것은 lazy하지 않다.
- 스왑 슬롯은 특정한 페이지들을 저장하도록 정해지면 안된다.
스왑 슬롯의 내용이 프레임으로 read back될 때 스왑 슬롯을 free해줘야 한다.

🔹 Managing Memory Mapped Files

메모리 매핑된 파일 관리하기

파일 시스템은 일반적으로 read, write 시스템 콜을 통해 액세스된다. 두 번째 인터페이스는 mmap 시스템 콜을 사용해서 파일을 가상 페이지에 "map"하는 것이다. 이후 프로그램은 파일 데이터에서 직접 메모리 인스트럭션을 사용할 수 있게 된다.
파일 foo가 0x1000바이트(4KB, 1페이지) 길이라고 가정해보자. foo가 주소 0x5000에서 시작하는 메모리에 매핑되어 있다면, 0x5000에서 0x5fff까지로의 메모리 접근은 foo에 대응하는 바이트에 접근할 것이다.
다음은 콘솔에 파일을 출력하기 위해 mmap을 사용하는 프로그램의 예시다. 커맨드 라인으로부터 특정 파일을 열고, 가상 주소 0x10000000에 매핑하고, 콘솔에 매핑된 데이터를 쓰고(fd1), 파일의 매핑을 해제한다.

#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;
}

mmap()은 다음과 같은 경우에 error 상태를 리턴한다.
- 파일 사이즈가 0바이트
- 파일이 다른 이미 매핑된 페이지를 덮어씀
- 주소가 aligned된 페이지가 아님
구현한 결과물이 어떤 메모리가 메모리 매핑된 파일에 의해 사용되었는지 추적할 수 있어야 한다: 매핑된 영역에서 발생하는 page fault를 적절히 다루고 매핑된 파일이 프로세스의 다른 세드먼트들을 덮어쓰지 않게 하기 위해서 필요하다.

🤝 코어타임

🔹 x86-64 페이지 구조 요약

페이지 크기: 4KB
각 페이지 테이블 엔트리(PTE 등) 크기: 8바이트
각 테이블 엔트리 수: 512개 (2⁹ → 9비트로 인덱싱)
가상 주소 공간: 48비트 (이론상 64비트지만 현재 구현에서는 48비트 사용)

🔹 가상 주소 분할 구조 (48bit VA)

비트 범위	크기	의미
47–39	9비트	PML4 인덱스
38–30	9비트	PDPT 인덱스
29–21	9비트	Page Directory 인덱스
20–12	9비트	Page Table 인덱스
11–0	12비트	페이지 내부 오프셋 (4KB)

🔹 페이징 4단계 구조

PML4 (Page Map Level 4)
- 가상 주소 상위 9비트를 인덱스로 사용
- 각 엔트리: PDPT의 시작 물리 주소 + flags
PDPT (Page Directory Pointer Table)
- 인덱스: VA의 38–30비트
- 각 엔트리: Page Directory의 시작 물리 주소 + flags
Page Directory (PD)
- 인덱스: VA의 29–21비트
- 각 엔트리: Page Table의 시작 물리 주소 + flags
Page Table (PT)
- 인덱스: VA의 20–12비트
- 각 엔트리: 실제 4KB 물리 페이지의 시작 주소 + flags

🔹 PTE 구조 (Page Table Entry 예시)

비트	필드 이름	설명
0	P (Present)	페이지 존재 여부
1	R/W	읽기/쓰기 허용
2	U/S	유저/슈퍼바이저
3	PWT	페이지 쓰기 스루
4	PCD	캐시 비활성화
5	A (Accessed)	접근 플래그
6	D (Dirty)	쓰기 여부
7~11	기타	PAT, Global 등
12~51	Page frame 주소	물리 페이지 시작 주소
52~63	예약 또는 확장

🔹 전체 주소 변환 흐름

PML4E → PDPT 주소
PDPE → Page Directory 주소
PDE → Page Table 주소
PTE → 4KB 물리 페이지 주소
최종 물리 주소 = PTE.page_frame_base + (VA의 offset)

VA
↓
PML4[VA >> 39] → PDPT
  ↓
PDPT[VA >> 30] → PD
  ↓
PD[VA >> 21] → PT
  ↓
PT[VA >> 12] → Physical Frame
  ↓
+ VA의 마지막 12비트 offset → 최종 물리 주소