Pintos Project 3-2) VM- Memory mapped file, Swap

Jisu·2023년 5월 25일
0

PintOS

목록 보기
5/6
post-thumbnail

이 글은 핀토스 가상메모리 메모리 매핑, 스와핑에 관한 글입니다.

  • Memory Mapped File

    • File I/O 방식(vs read/write와 비교)
    • mmap
    • munmap
    • Pintos test case

  • Swap In/Out

    • 개념 (무엇을 어디로 스왑)
    • ANON / FILE 타입 각각 구현
    • 비트맵 자료구조
    • LRU algorithm

 

Memory Mapped File (mmap)

파일 입출력 방법에는 크게 두 가지가 있다.

  • read, write 시스템콜
  • Memory-mmaped I/O

오늘날 많은 컴퓨팅 아키텍처들이 memory-mmapped I/O를 지원하는데, mmap은 디스크 파일을 메모리처럼 다이렉트로 읽고 쓸 수 있는 장점을 제공한다.

mmap은 메모리 페이지에 디스크 블록을 매핑시켜버린다.
read, write()처럼 buffer에 쓰고 그것을 메모리-디스크간 복사할 필요 없이, mmap은 처음에 파일이 들어갈 가상주소만 매핑해두면 거기를 자기 메모리처럼 읽고 쓸 수 있다.
즉, 그 위치의 가상주소를 읽으면 '파일 내용'이 읽혀진다.

mmap()

디멘드 페이징으로 파일 데이터를 메모리로 로드하는 함수

  • 파일 내용을 디스크에서 즉시 읽지 않고 처음에는 물리적 RAM을 전혀 사용하지 않음
  • 디스크에서 실제 읽기는 특정 위치에 액세스한 후에 지연 방식으로 수행

mmap이 다이렉트로 파일에 접근할 수 있다고 생각하면 만사형통 같지만, 실제로 그렇지는 않다.
핀토스에서 구현할 mmap() 은 VM_FILE 타입으로 변환될 가상페이지(현재는 uninit)만 만들어놓고, 이것이 물리 프레임과 실제 연결되는 타이밍은 page fault로 do_claim()이 호출될 때다.

mmap 구현

  • mmap(): 매핑하려는 주소(addr)가 유효한지 체크 후 do_mmap() 인자로 전달
  • do_mmap(): addr, file, offset 등 나중에 파일을 로드할 때 필요한 정보들을 받아서 load_aux 구조체에 저장.
  • vm_alloc_page_with_initialize(): uninit_new로 VM_FILE 타입에 맞게 초기화, SPT 해시테이블에 삽입
  • 추후 page fault 발생 시 do_claim에서 프레임을 받아와 가상주소 page와 연결
  • lazy_load_segment에서 실제 디스크 파일을 물리 프레임으로 로딩

do_mmap

void *
do_mmap (void *addr, size_t length, int writable,
		struct file *file, off_t offset) {
		//obtain a separate and independent reference to the file for each of its mappings.

	// 얼마나 읽을 것인가: 주어진 파일 길이와 length 비교: 읽고자 하는 length와 file 사이즈 중 작은 것
	struct file *file_ = file_reopen(file);
	size_t read_bytes = length > file_length(file) ? file_length(file) : length;
	size_t zero_bytes = PGSIZE - (read_bytes % PGSIZE);
	off_t offset_ = offset ;

	// 시작 주소 : 페이지 확장시 리턴 주소값 변경 방지
	void *start_addr = addr;
	if (file_ == NULL || read_bytes == 0) return NULL;

	/* 가상 페이지 매핑 */
	while (read_bytes > 0 || zero_bytes > 0) {	// 둘 다 0이 될 때까지 반복.
		// 파일을 페이지 단위로 잘라 load_aux에 저장 
		size_t page_read_bytes = read_bytes > PGSIZE ? PGSIZE : read_bytes;		// 마지막에만 read_bytes
		size_t page_zero_bytes = PGSIZE - page_read_bytes;		// 중간에는 0, 마지막에 padding

		struct load_aux *load_aux = (struct load_aux *)malloc(sizeof(struct load_aux));
		load_aux->file = file_;
		load_aux->offset = offset_;
		load_aux->page_read_bytes = page_read_bytes;

		// 대기중인 오브젝트 생성 - 초기화되지 않은 주어진 타입의 페이지 생성. 나중에 UNINIT을 FILE-backed로. 
		if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable, lazy_load_segment, load_aux)) {
			return NULL;
		}
		// 다음 페이지로 이동
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;	// 마지막엔 0
		addr += PGSIZE;
		offset_ += page_read_bytes;
	}
	// 매핑 시작 주소 반환
	return start_addr;
}

munmap()

mmap보다 중요한 건 munmap이다.
보통 메모리를 해제하는 free, clear, cleanup과 같은 이름을 지닌 함수들과 달리,
munmap은 매핑된 주소의 변경된 내용들을 디스크 파일에 반영해준다.
즉, 애초에 mmap을 호출한 이유가 파일에 쓰기 위함이었다면 munmap을 해주지 않으면 말짱도루묵인 셈이다.

ANON 페이지와 달리, memory-mapped page는 FILE 기반 페이지다.
디스크와 상호작용이 중요할 수밖에 없으며,
do_munmap()은 process_exit()에서 호출되어 SPT의 모든 vm_entry 페이지들을 돌면서 그들의 변경내용을 디스크에 반영한 후 프로세스를 종료해야 한다.
file_write_at()은 struct page의 uninit.aux 필드에서 받은 정보로 올바른 파일 위치를 찾아가 변경내용을 써준다.

do_munmap

void
do_munmap (void *addr) {
	struct thread *t = thread_current();
	// traverse 
	while (true) {
		struct page *page = spt_find_page(&t->spt, addr);
		if (page == NULL)
			return;
		// 파일 변경사항을 반영할 수 있도록 aux를 받아옴
		struct load_aux *load_aux = (struct load_aux *)page->uninit.aux;

		if (pml4_is_dirty(t->pml4, page->va)) {
			// Writes SIZE bytes from BUFFER into FILE
			file_write_at(load_aux->file, addr, load_aux->page_read_bytes, load_aux->offset);
			pml4_set_dirty(t->pml4, page->va, 0);			
		}
		addr += PGSIZE;		
	}
}

process_exit

void process_exit (void) {
	struct thread *curr = thread_current ();
    
    // Close all Opened file by for loop
    for (int i=0; i<FDCOUNT_LIMIT; i++)
        close(i);

    palloc_free_multiple(curr->fd_table, FDT_PAGES);
    file_close(curr->running);

	/* munmap - file-backed 경우 매핑 해제 */
	struct supplemental_page_table *spt = &curr->spt;
	if (!hash_empty(&spt->spt_hash)) {
		struct hash_iterator iter;

		hash_first(&iter, &spt->spt_hash);
		while (hash_next(&iter)) {
			struct page *page = hash_entry(hash_cur(&iter), struct page, hash_elem);
			if (page->operations->type == VM_FILE) {
				do_munmap(page->va);
			}
		}
	}   
    sema_up(&curr->wait_sema); // unblock parent
    sema_down(&curr->free_sema); 

    process_cleanup ();
}

 

(Test case) mmap-exit

테스트 케이스를 보면 mmap()이 어떤 식으로 사용되는지 알수 있다.
'mmap-exit.c'는 디스크 파일을 가상주소에 매핑하고
매핑 해제 후 내용이 제대로 반영되었는지 확인하는 테스트다.

  1. mmap-exit.c : 자식 스레드를 fork하여 'child-mm-wrt' 실행
  2. child-mm-wrt.c : 디스크 파일을 열어 해당 파일 디스크립터를 가상주소 ACTUAL(0x10000000)에 매핑
  3. memcpy(dst, src)로 char 타입 변수 sample을 ACTUAL에 덮어씀(copy)
  4. 자식이 프로세스를 종료할 때 process_exit()에서 do_munmap()으로 해당 주소의 변경내용을 디스크 파일에 반영
  5. 자식 프로세스가 종료되면 부모가 check_file()로 'sample.txt' 파일과 sample 텍스트 비교
  6. 변경된 "sample.txt" 파일 내용이 원래 프로세스 text 세그먼트에 있던 sample 텍스트와 동일하면 통과(제대로 반영)

mmap-exit.c

void
test_main (void)
{
  pid_t child;
  /* Make child write file. */
  quiet = true;
	child = fork("child-mm-wrt");
	if (child == 0) {	// 자식 스레드만 실행
		CHECK ((child = exec ("child-mm-wrt")) != -1, "exec \"child-mm-wrt\"");
	} else {			// 부모 스레드만 실행
		CHECK (wait (child) == 0, "wait for child (should return 0)");
		quiet = false;
		
		/* Check file contents. */
		check_file ("sample.txt", sample, sizeof sample);
	} 
}

child-mm-wrt.c

#define ACTUAL ((void *) 0x10000000)

void
test_main (void)
{
  CHECK (create ("sample.txt", sizeof sample), "create \"sample.txt\"");
  CHECK ((handle = open ("sample.txt")) > 1, "open \"sample.txt\"");
  CHECK (mmap (ACTUAL, sizeof sample, 1, handle, 0) != MAP_FAILED, "mmap \"sample.txt\"");
  memcpy (ACTUAL, sample, sizeof sample);
}

테스트 결과 출력

  (mmap-exit) begin
  (child-mm-wrt) begin
  (child-mm-wrt) create "sample.txt"
  (child-mm-wrt) open "sample.txt"
  (child-mm-wrt) mmap "sample.txt"
  (child-mm-wrt) end
  (mmap-exit) open "sample.txt" for verification
  (mmap-exit) verified contents of "sample.txt"
  (mmap-exit) close "sample.txt"
  (mmap-exit) end

 

Swap In/Out

스와핑(Swapping)

  • 스와핑이란 주기억장치(RAM)에 적재한 하나의 프로세스를 보조기억장치(Disk)에 잠시 적재했다가 필요할 때 다시 꺼내어 사용하는 메모리 교체 기법
  • 메모리에 적재되어 있으나 현재 사용되고 있지 않은 프로세스 이미지가 있으면
    - 프로세스 이미지를 하드디스크 특정 부분으로 몰아냄
    - 메모리 활용도를 높이기 위해 Backing store(=swap device)로 몰아내기

목표

  • 페이징, 세그멘테이션은 메모리를 어떻게 효율적으로 쓸 것인가에 대한 고민이었다면
  • 스와핑은 메모리 크기가 다 찼을 때 프로세스를 실행시킬 수 있는 방법

페이지 종류와 스와핑

  • Anonymous Page
    • ANON 페이지는 어떤 백업 공간도 갖지 않기 때문에 ANON 페이지 스와핑을 구현하기 위해 swap disk라는 임시 공간을 제공
  • File-backed Page
    • 하드디스크가 backing store 역할
    • 파일 기반 페이지를 evict 하려면 디스크에 다시 써줘야 함(PTE dirty bit 확인)

어디로 몰아낼 것인가(evict to where)?

  • 교체할 페이지 타입별로 다름
    • 유저 스택 페이지(ANON): 스왑 디스크로 스왑아웃
    • 파일 페이지(FILE-backed): 파일시스템으로 스왑아웃

 

무엇을 스왑할 것인가

우리가 스왑하고자 하는 것은 물리 페이지다.
프로세스가 커널에 요청하여 할당받은 물리 프레임을 리스트로 관리하기 위해 frame_table 연결리스트 구조체를 사용하였다.
frame_table은 LRU_list라 볼 수 있으며, 여기서 교체할 페이지를 선택하게 된다.

frame_table (LRU_list)

  • page 구조체의 리스트로, 프로세스에 할당된 물리 페이지를 관리

 
스왑의 목적은 메모리 가동률을 높이는 것.
자주 쓰는 메모리는 남겨두고 안쓰는 메모리 구역은 디스크로 보내
제한된 메모리 자원으로 최대한의 효용을 내는 것

주기억장치(RAM) <-> 보조기억장치(disk)간 스왑 인/아웃이
핀토스에서는 frame_talbe(메모리)과 swap_disk(디스크)로 구현하게 되어있으며
그 흐름은 다음과 같이 도식화할 수 있음

  • vm_get_frame()에서 물리 프레임을 요청할 때
    • 남아있는 frame이 있으면 할당받고 frame_table에 추가
    • 남아있는 frame이 없으면 vm_evict_frame()으로 교체할 페이지를 선정, swap_out()으로 디스크로 보냄
      • 비워준 공간은 pml4_clear_page()로 해당 페이지를 'not present'로 표시

 
vm_get_frame

static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
	frame = (struct frame *)malloc(sizeof(struct frame));
	/* palloc() and get frame */
	frame->kva = palloc_get_page(PAL_USER); 	// RAM user pool -> kernel va로 1 page 할당

	frame->page = NULL; 	// @ for debug

	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
    
	/* If there is no available page, evict the page and return it */
	if (frame->kva == NULL) {
		frame = vm_evict_frame();
		frame->page = NULL;
		return frame;
	}
	list_push_back(&frame_table, &frame->frame_elem);
	
	return frame;
}

vm_evict_frame

static struct frame *
vm_evict_frame (void) {
	struct frame *victim UNUSED = vm_get_victim ();
	/* swap out the victim and return the evicted frame. */
	swap_out(victim->page);

	return victim;
}

 

Anonymous Page Swap

Swap-out

  • 메모리가 가득찼을 때 운영체제가 선택한 메모리 페이지를 디스크의 스왑 영역으로 옮기는 함수

  • anon 스왑아웃 루틴

  1. bitmap_scan: 비트맵을 순회하며 false값을 갖는(=해당 swap slot이 비어있다는 표시) 비트를 찾아 리턴
  2. disk_write: 해당 섹터에 페이지 크기만큼 써줌
  3. bitmap_set: 해당 스왑 슬롯에 페이지가 채워졌음을 표시.
  4. pml4_clear_page: 교체할 페이지를 물리 프레임에서 지움
  5. anon_page의 swap_index 설정

anon_swap_out

static bool
anon_swap_out (struct page *page) {
	struct anon_page *anon_page = &page->anon;

	int page_no = bitmap_scan(swap_table, 0, 1, false);
	if (page_no == BITMAP_ERROR) return NULL;

	for (int i = 0; i < SECTORS_PER_PAGE; ++i) {
		// Convert swap slot index to writing sector number
		disk_write(swap_disk, page_no * SECTORS_PER_PAGE + i, 
        			    page->va + DISK_SECTOR_SIZE * i);
	}
	bitmap_set(swap_table, page_no, true);
	pml4_clear_page(&thread_current()->pml4, page->va, 0);

	anon_page->swap_index = page_no;
	return true;
}

 

Swap-in

  • 스왑 영역에 있는 페이지를 메모리로 다시 불러오는 과정
  • 스왑디스크로 보낼 때 그 위치(swap slot)을 page 구조체에 저장해두었는데(anon_page->swap_index = page_no)
  • 다시 읽어들일 때 page_no * SECTORS_PER_PAGE + i로 스왑디스크 내 섹터 넘버를 계산
    • SECTOR_PER_PAGE = 4KB/512byte (페이지당 8개 섹터)
  • 해당 섹터 넘버를 읽어 물리 메모리에 DISK_SECTOR_SIZE (512byte) 만큼 써줌

anon_swap_in

static bool
anon_swap_in (struct page *page, void *kva) {
	struct anon_page *anon_page = &page->anon;
	int page_no = anon_page->swap_index;

	if (anon_page->swap_index == INVALID_SLOT_IDX) return false;
	if (bitmap_test(swap_table, page_no) == false) return false;

	for (int i = 0; i < SECTORS_PER_PAGE; ++i) {
		disk_read(swap_disk, page_no * SECTORS_PER_PAGE + i, kva + DISK_SECTOR_SIZE * i);
	}
	bitmap_set(swap_table, page_no, false);
	return true;
}

 

스왑디스크를 비트맵으로 구현

  • 비트맵은 array of bits로, 각 비트는 true or false를 나타냄

    • 동일 리소스 내 사용여부를 나타내는 데 용이.
    • 비트연산으로 수많은 경우의 수를 하나의 integer 표현 가능

  • Swap disk의 경우 bit = 0: 비어있음 / 1 : 차있음 표시

  • bitmap_scan()

    • 비트맵을 스캔하며 bit 0인 비트를 찾음
    • 연속적인 cnt개의, bit 0 조건을 만족하는 그룹이 있으면 그 시작점 인덱스를 리턴
size_t
bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool val){
    ASSERT (start <= b->bit_cnt) // start: 비트맵 몇 번째부터? 

    if (cnt <= b->bit_cnt) {
        size_t last = b->bit_cnt - cnt;
        size_t i;
        for (i=start; i<=last, i++)
            if (!bitmap_contains (b, i, cnt, !value))
                return i;
    }
    return BITMAP_ERROR;
}

/* (참고) 비트맵 구조체 */
struct bitmap {
    size_t bit_cnt;     // number of bits
    elem_type *bits;    // 0 or 1 
}

 

비트연산 활용

page_no는 스왑 인으로 Swap disk에서 읽어들일 때 중요하게 사용된다.
스왑디스크에서 DISK_SECTOR_SIZE 만큼 읽을 때,
가상주소의 최하위 12비트를 >> 로 없애면 page number(인덱스)를 구할 수 있다.

한편 page_round_down(va)은 가장 가까운 페이지 경계 주소를 리턴한다.

/* Page offset (bits 0:12). */
#define PGSHIFT 0                          /* Index of first offset bit. */
#define PGBITS  12                         /* Number of offset bits. */
#define PGSIZE  (1 << PGBITS)              /* Bytes in a page. */
#define PGMASK  BITMASK(PGSHIFT, PGBITS)   /* Page offset bits (0:12). */

/* Page number (the most significant bits) */
#define pg_no(va) ((uint64_t) (va) >> PGBITS)

/* Round down to nearest page boundary. */
#define pg_round_down(va) (void *) ((uint64_t) (va) & ~PGMASK)

 

LRU 알고리즘으로 페이지 교체 매커니즘 구현

Accessed bit vs Dirty bit

  • 페이지 테이블의 accessed bit는 페이지가 참조될 때마다 하드웨어에 의해 1로 설정됨
  • 하드웨어는 accessed bit를 다시 0으로 만들지 않음
    • 참조 비트가 '0'이면 해당 페이지를 victim으로 선정
    • 참조 비트가 '1'이면 '0'으로 재설정하고 다음 페이지로 포인터 이동
  • dirty bit가 '1'인 페이지가 victim으로 선정되었을 때, 변경내용을 항상 디스크에 저장해야

page <-> frame 구조체 활용

우리는 frame_table에서 교체할 물리 프레임을 찾고 있지만,
필요한 것은 page table entry(PTE)에 저장된 accessed bit다.
어떻게 주어진 frame만 가지고 어떻게 accessed bit를 알 수 있을까?
이는 frame 구조체 멤버인 page->va로 pml4 페이지 테이블을 순회하며 해당 페이지 엔트리를 찾음으로써 가능하다.

LRU algorithm

  1. 페이지 폴트 발생, 남은 프레임이 없어서 할당받을 수 없는 상황
  2. frame_table을 현 시점(start)부터 순회하면서 accessed bit가 0인 프레임을 찾음
  3. 해당 페이지의 dirty bit가 0이면 변경되지 않았으므로 바로 disk로 내보내고, 1이면 disk로 written한 후 내보냄
  4. start 포인터를 계속 이동시키며
    start~ end of the list까지 돌면, 다시 begin of the list 부터 돌면서 찾음

 
vm_get_victim()

static struct frame *
vm_get_victim (void) {
	/* Get the struct frame, that will be evicted. */
	struct frame *victim = NULL;
	struct thread *curr = thread_current();
	struct list_elem *e = start;

	/* initialize start to first element of the frame_table */
	if (!start) {
		start = list_begin(&frame_table);
	}
	for (start = e; start != list_end(&frame_table); start = list_next(start)) {
		victim = list_entry(start, struct frame, frame_elem);
		if (pml4_is_accessed(curr->pml4, victim->page->va)) { 
			pml4_set_accessed(curr->pml4, victim->page->va, 0);
		}	
		else 		// refer bit is 0 
			return victim;
	}
	
	/* If no victim is found from start to end, search from beginning to start */
	for (start = list_begin(&frame_table); start != e; start = list_next(start)) {
		victim = list_entry(start, struct frame, frame_elem);
		if (pml4_is_accessed(curr->pml4, victim->page->va)) {
			pml4_set_accessed(curr->pml4, victim->page->va, 0);
		}
		else 
			return victim;
	}
	return victim;	  // frame을 다 돌아도 refer bit 0이 안나오면 현재 페이지를 evict
}
profile
Jisu
.
이전 포스트

Pintos Project 3-1) VM- Lazy loading

다음 포스트

Pintos Project 4. File System

0개의 댓글

관련 채용 정보