pintos - vm [anon (swap in, swap out, destroy)]

접은글 : 현재까지 진행한 내용 정리와 앞으로 해야할 전체적인 흐름 구조 나열... (보기가 어려우므로 요약)

page fault가 발생하면 커널은 먼저 fault가 난 유저 가상 주소가 supplemental page table에 등록되어 있는지 확인한다.

해당 주소의 page가 SPT에 존재한다면, 아직 실제 물리 프레임과 연결되지 않은 lazy page일 수 있으므로 vm_claim_page()를 통해 물리 프레임을 할당하고 가상 주소와 매핑한다.

 

물리 프레임을 할당할 때 user pool에 남은 공간이 없다면 vm_get_frame()은 frame table에서 희생 프레임을 선택한다.

선택된 victim frame이 이미 어떤 page와 연결되어 있다면, 그 page의 swap_out()을  호출해 현재 내용을 보존한 뒤 프레임을 비운다. anonymous page라면 swap_disk에 기록하고, file-backed page라면 dirty 여부에 따라 파일에 반영하거나 그냥 버릴 수 있다. 이후 비워진 frame을 새 page에 연결하고 swap_in()을 통해 page 내용을 메모리에 올린다.

 

처음 setup_stack, stack_growth, 또는 lazy_loading으로 생성된 페이지는 SPT에 VM_UNINIT 상태로 등록된다. 이 VM_UNINIT page는 아직 실제 내용이 메모리에 올라와 있지 않은 "대기 상태의 페이지"이다.

이후 page fault가 발생해 해당 page가 claim되면, uninit page의 swap_in인 uninit_initialize()가 호출된다. uninit_initialize()는 page가 원래 의도했던 타입에 따라 anon_initializer 또는 file_backed_initializer를 실행하고, 그 결과 page의 operations가 VM_UNINIT에서 VM_ANON 또는 VM_FILE 타입의 operations로 바뀐다.

즉, page fault 시점에 lazy page가 실제 사용할 page type으로 구체화되는 것이다.

 

마지막으로 유저 프로세스가 종료되면 SPT를 순회하면서 각 page를 제거한다.

이때 vm_dealloc_page()가 page_type에 맞는 destroy()를 호출하여 page가 들고 있던 자원을 정리한다.

예를 들어 swap slot을 사용 중인 anonymous page라면 swap slot을 해제하고, file-backed page라면 필요한 write-back이나 aux/free 같은 정리를 수행한다.

 

따라서 anon/file/uninit 각각의 swap_in, swap_out, destroy 흐름을 구현하기에 앞서, 먼저 anonymous page부터 구현을 시작할 예정이다.

(1) page fault 발생 -> SPT에 존재 확인 후 물리프레임 할당

(2) 물리 프레임 할당 시 남은 공간이 없다면 frame_table에서 희생자 프레임을 선택하고 swap_out을 호출

(3) 지금까지 한 stack 초기화와 lazy_loading으로 생성된 페이지들은 page가 claim되면 swap_in 호출

(4) 마지막으로 유저 프로세스가 종료되면 SPT를 순회하면서 각 page를 제거하면서 destroy 호출

따라서 anonymous page의 swap_in, swap_out, destory를 구현하는 것을 이 블로그에서 정리하고자 한다.

1. Anonymous Page Strategy (익명 페이지 전략)

먼저 anonymous page는 executable file처럼 다시 읽어올 원본 파일(backing file)이 존재하지 않는다.

따라서 eviction이 발생하면 페이지 내용을 반드시 swap disk에 저장해야 한다.

이를 위해

- 현재 페이지가 저장된 swap slot 위치

- 현재 swap disk에 저장된 상태인지 여부

를 관리하는 구조체가 필요

vm/anon.h 헤더 파일에 추가

- vm/anon.c 파일 제일 위에 추가

#define SECTORS_PER_PAGE (PGSIZE / DISK_SECTOR_SIZE)

static struct bitmap *swap_table;
static struct lock swap_lock;

 

swap_disk는 sector 단위로 읽고 쓴다.

ⓐ. 왜 SECTORS_PER_PAGE == 8일까

예를 들면, 4096Byte 이 페이지 한 개를 swap disk에 저장하려면 8개의 sector로 나눠 저장해야 한다. 따라서 8개로 나눠진 swap_disk를 반복문을 돌며 작동시키기 위해 매크로를 만들어 둔 것

ⓑ. bitmap swap_table은 왜 필요할까?

swap disk도 결국 저장 공간이다. -> OS가 알아야 하는 정보

1. 어느 sector들이 사용 중인가?
2. 어디가 비어있는가?

swap disk sector 상태

0 1 2 3 4 5 6 7 8 9 ...
1 1 1 1 1 1 1 1 0 0 ...​

[1: 사용중, 0: 비어 있음]

참고
희생자 프레임을 고를 때, 물리 프레임 테이블에서 골라 swap_out을 시켰다.
만약 희생자 프레임이 swap_disk에 들어가야 할 anon_type page 였다면 따로 swap table을 bitmap을 통해 관리해줘야 한다. 따라서 (이러한 swap_table이 필요한 것)

ⓒ. 왜 swap_lock이 필요할까?

VM은 여러 thread/process가 동시에 page fault를 발생시킬 수 있음

Thread A -> swap out 시도
Thread B -> swap out 시도
둘 다 동시에 bitmap_scan_and_flip()를 실행하면 둘 다 빈 공간을 발견할 수도 있음. (데이터 깨짐 방지)

2. vm_anon_init

접은글 : vm_anon_init() 구현

void vm_anon_init (void);

ⓐ. disk_get

- struct disk & struct channel

struct disk : 실제 디스크 1개를 의미
struct channel : 그 디스크들이 연결된 ATA 컨트롤러 / 채널 1개

- 관계도

channel "hd0"
 ├── devices[0] = disk "hd0:0"   // master
 └── devices[1] = disk "hd0:1"   // slave
 
disk.channel -> 자신이 속한 channel
channel.devices[0 or 1] -> 실제 disk

- struct disk

/**
 * 만약 hd0:1 이라는 디스크가 있으면
 * disk.name = "hd0:1"
 * disk.channel = &channels[0]
 * disk.dev_no = 1
 */
struct disk {
    char name[8];              // 디스크 이름, 예: "hd0:1"
    struct channel *channel;   // 이 디스크가 연결된 ATA 채널
    int dev_no;                // 0이면 master, 1이면 slave

    bool is_ata;               // 실제 ATA 디스크인지 여부
    disk_sector_t capacity;    // 디스크 크기, sector 단위

    long long read_cnt;        // 읽은 sector 수
    long long write_cnt;       // 쓴 sector 수
};

- struct channel

/**
 * channel은 디스크를 제어하는 컨트롤러 정보를 담음
 * ATA 채널 하나는 최대 두 개의 디스크를 제어할 수 있어서 struct disk devices[2];가 있음
 * 
 * channel에 lock이 있는 이유
 * 같은 채널의 두 디스크가 같은 컨트롤러 I/O포트를 공유하기 때문
 */
struct channel {
    char name[8];              // 채널 이름, 예: "hd0"
    uint16_t reg_base;         // ATA I/O 포트 시작 주소
    uint8_t irq;               // 사용하는 인터럽트 번호

    struct lock lock;          // 컨트롤러 접근 보호
    bool expecting_interrupt;  // 지금 인터럽트를 기다리는 중인지
    struct semaphore completion_wait; // 디스크 작업 완료 대기용

    struct disk devices[2];    // 이 채널에 연결된 디스크 2개
};

딱 봐도 느껴지지만,
ATA 디스크에서 swap 디스크를 골라 반환하기 위해 사용한다고 생각하면 된다.

ⓑ. disk_size

ⓒ. bitmap_create

- byte_cnt & elem_cnt

ELEM_BITS : 64

bit_cnt를 64 기준으로 몇개 필요한가를 정의한 것 (ex. bit_cnt = 50 : elem_cnt = 1 ----- bit_cnt = 100 : elem_cnt = 2)

즉, byte_cnt(bit_cnt)는 필요한 bit 개수에 맞춰 필요한 사이즈 크기를 구한 것

- bitmap_set_all & bitmap_set_multiple

- bitmap_size

- bitmap_set

- bitmap_mark & bitmap_reset

bitmap_mark : 특정 비트를 1/true로 만듦

bitmap_reset : 특정 비트를 0/false로 만듦

bitmap_create
필요한 bit 개수 만큼의 크기를 힙 커널 영역에 할당하고
처음 전달받은 bitmap의 비트들을 0/false로 다 초기화하는 단계다.

vm_anon_init 함수
1. Pintos에서 swap 영역으로 사용할 ATA disk를 가져와 전역 변수 swap_disk에 저장
2.swap_disk의 전체 sector 수를 page 하나가 차지하는 sector수로 나누어, swap disk 안에 몇 개의 page-sized swap slot이 존재하는지 계산 그리고 그 slot 개수만큼 bitmap을 생성
3. 여러 page fault나 eviction 과정에서 swap_table과 swap_disk 동시에 접근할 수 있으므로, swap slot 할당/해제 및 disk read/write를 보호하기 위한 swap_lock을 초기화

3. anon_initializer

bool anon_initializer (struct page *page, enum vm_type type, void *kva);

접은글 : anon_initializer 구현

1. page fault 발생

2. vm_try_handle_fault에서 vm_do_claim_page 호출

3. swap_in 호출

4. uninit_initializer 호출

5. uninit->page_initializer 과 init 호출 (anon_initializer 또는 file-backed_initializer) 과 lazy_load_segment 호출

접은글 : 위 내용의 코드 흐름을 보여주고 있음

anon_initializer는 실제로 페이지에 물리 프레임이 할당될 때, 페이지의 작동 방식을 anonymous page로 바꾸기 위한 과정을 하는 것이다.

1. page->operations = &anon_ops; [페이지 작동방식을 anon형태로 변경]

2. page->anon.swap_slot = BITMAP_ERROR; [현재 swap disk 어디에 저장되어 있지도 않으니 저장된 위치가 아무데도 없다는 초기화]

3. page->anon.in_swap = false; [현재 swap disk에 저장되어 있지 않다는 표시]

4. memset(kva, 0, PGSIZE); [새로 할당된 페이지 영역을 0으로 초기화하기 위해]

ⓐ. anon_ops

page->operations->swap_in

page->operations->swap_out

page->operations->destroy

page->operations->type

을 호출하면 위 함수들이 사용이 되는 형태로 객체 지향적인 코드로 만든 독특한 구조다.

4. anon_swap_in

static bool anon_swap_in (struct page *page, void *kva);

접은글 : anon_swap_in 구현

1. page가 swap disk에 저장된 상태가 아니면, 읽어올 backing store가 없으므로 kva가 가리키는 4KB frame을 0으로 초기화

2. 만약 현재 스왑디스크에 올라와 있는 상태라면, swap_disk에서 현재 위치한 파일을 섹터단위로 읽어서 kva에 복원한다.

3. swap_table에 1로 되어있는 부분들을 0으로 초기화해준다.

4. 다시 anon_page의 swap 상태를 초기화한다.

5. anon_swap_out

static bool anon_swap_out (struct page *page);

 

접은글 : anon_swap_out 구현

1.swap_table bitmap을 0번 위치부터 살펴보면서, false인 swap slot 1개를 찾고 true로 뒤집는 함수 [비어 있는 swap slot을 찾아 사용 중으로 표시]

예시

bitmap:
[1 1 0 0 0 1 0]

bitmap_scan(b, 0, 3, false) 호출
0이 3개 연속인 위치를 찾음

결과 : idx = 2, 찾지 못하면 BITMAP_ERROR

2. 빈 슬롯을 찾지 못하면 종료

3. 현재 page의 frame에 있는 kva 데이터를 swap_disk의 해당 slot 위치에 sector 단위로 나누어 기록

4. anon_page에 swap 위치를 저장하고, 이 page가 현재 swap disk에 나가 있는 상태라고 표시

6. anon_destroy

static void anon_destroy (struct page *page);

접은글 : anon_destroy 구현

현재 page가 swap_disk에 저장된 상태라면, 현재 swap_table bitmap에서 swap_slot을 다시 0(false)로 초기화해준다.