메모리 스와핑

문건우·2024년 5월 28일

메모리 스와핑은 물리 메모리 사용을 최적화하기 위한 가상 메모리 관리 기법이다.
프로세스의 메모리 요구량이 물리 메모리 크기를 초과하면, 운영체제는 일부 페이지를 디스크의 스왑 영역으로 내보내어 물리 메모리 공간을 확보한다.

스와핑 과정은 다음과 같다:

운영체제가 메모리 부족을 감지하고 메모리 할당 요청을 받는다.
운영체제는 스왑 디스크로 내보낼 페이지를 선택한다.
선택된 페이지의 정확한 메모리 상태가 스왑 디스크에 복사(swap out)된다.
이후 해당 페이지에 접근하려 할 때, 운영체제는 스왑 디스크에서 페이지 내용을 다시 메모리로 읽어온다(swap in).

내보내는 페이지는 익명 페이지(anonymous page) 또는 파일 매핑 페이지(file-backed page)이다.

익명 페이지: 프로세스의 힙, 스택, 데이터 영역 등의 페이지로, 스왑 디스크에 저장된다.
파일 매핑 페이지: 실행 파일이나 매핑된 파일에 해당하는 페이지로, 디스크에 저장됩니다.

스와핑 작업은 명시적으로 호출되지 않고, 페이지 구조체의 operations 멤버에 등록된 함수 포인터를 통해 간접적으로 호출된다.

이를 통해 운영체제는 한정된 물리 메모리를 효율적으로 활용하고, 프로세스의 가상 메모리 공간을 실제 메모리보다 크게 사용할 수 있다.

Page Replacement Policy 프로세스가 가상 페이지를 통해 물리 메모리에 접근하려 시도할 때, 물리 프레임이 모두 꽉 차 있으면 물리 메모리에서 적당한 하나의 프레임을 골라 디스크로 Swap Out 한다. 이 때 swap out할 적당한 프레임을 고르는 정책을 Page Replacement Policy라고 한다.

프레임을 연결 리스트로 관리해주기 위해

// vm/vm.h
struct frame {
	void *kva;
	struct page *page;
	struct list_elem frame_elem; // 프레임을 연결 리스트로 관리하기 위한 요소
};

// vm/vm.c
//frame들을 관리하는 frame table 리스트와 해당 리스트를 순회해주기 위한 start 변수를 선언.
struct list frame_table;
struct list_elem *start;

맨 처음 가상 메모리에 대한 서브 시스템들을 초기화해주는 vm_init() 함수에서 프레임 테이블 초기화.
- vm_init()은 언제 실행되나? init.c → main() → vm_init()의 순서로 실행된다. 핀토스의 메인 프로그램이 실행될 때 같이 실행된다.
```
void vm_init(void) {
    vm_anon_init();
    vm_file_init();
#ifdef EFILESYS /* For project 4 */
    pagecache_init();
#endif
    register_inspect_intr();
    // 프레임 테이블 초기화 
    list_init (&frame_table);
}
```

먼저 malloc()을 사용하여 새로운 프레임 구조체를 동적으로 할당하고, 이를 기반으로 palloc_get_page()를 사용하여 물리 메모리 페이지를 할당한다. 물리 메모리 할당에 실패한 경우 페이지 교체 함수를 호출하여 희생 프레임을 가져오고, 새로운 프레임이나 희생 프레임은 프레임 테이블에 추가되고 반환한다.

static struct frame *vm_get_frame(void) {
    // struct frame *frame = NULL;

    // 새로운 프레임 구조체 동적 할당
    struct frame *frame = (struct frame *)malloc(sizeof(struct frame));

    // 물리 메모리 페이지 할당
    frame->kva = palloc_get_page(PAL_USER); 

    // 물리 메모리 할당에 실패한 경우
    if (frame->kva == NULL) 
    {
        // 페이지 교체 함수 호출하여 희생 프레임 가져오기
        frame = vm_evict_frame();
        // 희생 프레임에 매핑된 페이지 초기화
        frame->page = NULL;
        // 프레임 테이블에 새로운 프레임 추가
        list_push_back(&frame_table, &frame->frame_elem);
        
        return frame; // 희생 프레임 반환
    }    

    // 프레임 테이블에 새로운 프레임 추가
    list_push_back(&frame_table, &frame->frame_elem);

    // 구조체 멤버 초기화
    frame->page = NULL;

    // ASSERT를 사용하여 프레임 구조체와 매핑된 페이지가 유효한지 확인
    ASSERT(frame != NULL); // 프레임이 NULL이 아닌지 확인
    ASSERT(frame->page == NULL); // 프레임에 매핑된 페이지가 없는지 확인

    return frame; // 새로운 프레임 반환
}

페이지 교체 정책을 실제로 구현하는 함수 구현. vm.c/vm_get_victim()

/* 희생될 프레임을 선택합니다. */
static struct frame *vm_get_victim(void) {
    struct frame *victim = NULL;

    /* 페이지 추방 정책은 여러분이 정합니다. */

    // 현재 스레드 가져오기
    struct thread *curr = thread_current();
    // 리스트 순회를 위한 노드
    struct list_elem *e = start;

    // 원형 리스트를 순회하는 두 번의 반복문
    // 두 가지 경우를 모두 고려하여 희생 프레임 선택
    // 1. 현재 위치부터 끝까지
    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
            return victim; // 접근 비트가 설정되지 않은 경우 희생 프레임 반환
    }

    // 2. 시작 위치부터 현재 위치까지
    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; // 희생 프레임 반환
}

함수는 페이지 교체를 위해 희생 프레임을 선택하는 역할을 함. 함수는 원형 리스트를 순회하여 희생 프레임을 선택하며, 접근 비트를 확인하여 사용 여부를 판단한다. 두 번의 반복문을 사용하여 리스트의 처음부터 끝까지 또는 현재 위치부터 끝까지 순회하여 희생 프레임을 선택한다. 선택된 희생 프레임을 반환.

vm_evict_frame() 구현

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

vm_get_victim() 함수를 호출하여 프레임 테이블에서 적당한 프레임을 찾아낸 다음, 해당 프레임을 swap out 해주는 함수.

anon_page
- 디스크 안에 페이지에 대한 Backing Store(페이지 임시 저장 공간)가 없음. → 디스크로 swap_out 시에 저장할 공간이 디스크 내에 없다는 뜻이다.
- 따라서 디스크 내에 swap_disk를 만들고 swap_out된 anon_page를 저장해야 한다.
1. struct anon_page의 swap_idx 멤버 변수는 해당 익명 페이지가 스왑 디스크의 어느 위치에 저장되어 있는지를 나타내는 인덱스 값을 저장한다.
```
// include/vm/anon.h
struct anon_page {
  int swap_idx;
};
```
2. 디스크에서 사용 가능 Swap Slot과 불가능 Swap Slot을 관리하는 Swap_Table을 선언한다.(비트맵 객체로)
```
// vm/anon.c
struct bitmap *swap_table
```
3. ANON 페이지를 위한 디스크 내 스왑 영역을 생성하고 이를 관리하는 스왑 테이블을 만들어준다
  
  여기서 swap_disk_size는 스왑 디스크 안에서 만들 수 있는 스왑 슬롯의 개수를 의미합니다.
  
  스왑 디스크 공간 내의 총 스왑 슬롯 개수는 다음과 같이 계산된다 :
  
  pintos -v -k -m 10 --fs-disk=10 -p tests/vm/swap-anon:swap-anon --swap-disk=30 --gdb -- -q -f run swap-anon
  
  스왑 디스크가 왜 필요함 ?
  
  모든 프로세스가 실행되기에 물리 메모리는 부족하다. 따라서 추가적인 메모리 공간을 확보할 수 있게 하는 것이 스왑 디스크 영역. 프로세스가 계속 실행될 수 있도록 하기위해
  
  디스크의 크기 = 디스크의 섹터 수 * 섹터 크기 (바이트)
  
  디스크의 사이즈 = 60480 * 512
  
  → 약 30MB
```
// vm/anon.c
void vm_anon_init(void) {
    swap_disk = disk_get(1, 1); 
    size_t swap_disk_size = disk_size(swap_disk) / 8; 
    swap_table = bitmap_create(swap_disk_size);
}
```
4. swap_idx로 페이지의 스왑 상태를 추적하기 위해 익명 페이지 구조체의 swap_idx 멤버를 -1로 초기화해준다. -1로 설정하는 것은 해당 페이지가 아직 스왑 디스크에 저장되어있지 않음을 의미한다.
```
// vm/anon.c
bool anon_initializer(struct page *page, enum vm_type type, void *kva) {
    page->operations = &anon_ops;

    struct anon_page *anon_page = &page->anon;
    anon_page->swap_idx = -1; // 추가된 코드
}
```
5. anon_swap_out 함수는 페이지를 스왑 디스크로 내보내는 역할을 한다.
6. 빈 스왑 슬롯 검색:
  - bitmap_scan(swap_table, 0, 1, false)를 사용하여 빈 스왑 슬롯(사용 가능한 슬롯)을 검색합니다.
  - 빈 슬롯을 찾으면 slot_num에 슬롯 번호를 저장하고, 슬롯이 없으면 BITMAP_ERROR를 반환하여 false를 리턴합니다.
7. 페이지 데이터 스왑 디스크에 기록:
  - 찾은 슬롯 번호를 기준으로 페이지 데이터를 스왑 디스크에 기록합니다.
  - 한 페이지는 8개의 섹터로 나뉘며, 각 섹터에 데이터를 순차적으로 기록합니다.
  - disk_write(swap_disk, slot_num * 8 + i, page->va + DISK_SECTOR_SIZE * i)로 페이지의 물리 메모리 주소에서 데이터를 읽어와 스왑 디스크에 씁니다.
8. 스왑 테이블 업데이트:
  - 스왑 테이블에서 해당 슬롯의 비트를 true(사용 중)로 설정합니다.
  - bitmap_set(swap_table, slot_num, true)를 사용합니다.
9. 페이지 매핑 해제:
  - 현재 페이지의 물리 메모리와의 매핑을 해제합니다.
  - pml4_clear_page(thread_current()->pml4, page->va)를 호출하여 현재 스레드의 페이지 맵 레벨 4(pml4)에서 페이지를 제거합니다.
10. 스왑 인덱스 업데이트:
  - 익명 페이지 구조체의 swap_idx에 사용한 슬롯 번호를 저장하여 페이지의 위치를 추적합니다.
11. 결과 반환:
  - 모든 작업이 성공적으로 완료되면 true를 반환하여 스왑 아웃이 성공했음을 나타냅니다.
  - 만약 빈 슬롯을 찾지 못하면 false를 반환합니다.
```
static bool anon_swap_out(struct page *page) {
    struct anon_page *anon_page = &page->anon;
		int slot_num = bitmap_scan(swap_table,0,1,false); 

		if (slot_num == BITMAP_ERROR)
			return false;
		
		for (int i = 0; i < 8; ++i) {
			disk_write(swap_disk, slot_num * 8 + i, page->va + DISK_SECTOR_SIZE * i);
		}

    bitmap_set(swap_table, slot_num, true);
		pml4_clear_page(thread_current()->pml4, page->va);
		
		anon_page->swap_idx = slot_num;
		return true;
}
```
12. anon_swap_in 함수는 스왑 디스크에서 페이지를 읽어와 메모리에 적재하는 역할을 한다.
  1. 스왑 슬롯 확인:
  - bitmap_test(swap_table, anon_page->swap_idx)를 사용하여 anon_page에 저장된 swap_idx에 해당하는 슬롯이 사용 중인지 확인합니다.
  - 해당 슬롯이 사용 중이 아니면 false를 반환합니다.
  2. 스왑 디스크에서 데이터 읽기:
  - anon_page->swap_idx에 저장된 슬롯 번호를 기준으로, 디스크내에 해당 데이터의 위치를 찾을 수 있음 → 해당 슬롯의 데이터를 스왑 디스크에서 읽어옵니다.
  - 각 페이지는 8개의 섹터로 구성되어 있으므로, 8번 반복하여 데이터를 읽어옵니다.
  - disk_read(swap_disk, anon_page->swap_idx * 8 + i, kva + DISK_SECTOR_SIZE * i)를 사용하여 스왑 디스크에서 각 섹터의 데이터를 읽어 kva(물리 메모리 주소)에 저장합니다.
  3. 스왑 테이블 업데이트:
  - 페이지가 메모리에 적재되었으므로, 스왑 테이블에서 해당 슬롯을 비어있음으로 표시합니다.
  - bitmap_set(swap_table, anon_page->swap_idx, false)를 사용하여 해당 슬롯의 비트를 false로 설정합니다.
  4. 결과 반환:
  - 모든 작업이 성공적으로 완료되면 true를 반환하여 스왑 인이 성공했음을 나타냅니다.
  - 스왑 슬롯이 사용 중이 아니거나 다른 문제가 발생하면 false를 반환합니다.
```
/* Swap in the page by read contents from the swap disk. */
static bool anon_swap_in(struct page *page, void *kva) {
    struct anon_page *anon_page = &page->anon;
		
		if (bitmap_test(swap_table, anon_page->swap_idx) == false) // anon_page에 저장한 slot 정보를 통해 swap_disk에 내용가져오기
			return false; 
		
		for (int i = 0; i < 8; ++i)
		{
			disk_read(swap_disk, anon_page->swap_idx * 8 + i, kva + DISK_SECTOR_SIZE * i); // 디스크 swap_disk 에서 섹터 SEC_NO를 읽어 BUFFER에 저장
		}

		bitmap_set(swap_table,anon_page->swap_idx,false);
		
		return true;

}
```

File_backed_page File-Backed_Page의 경우 디스크에 backed file이 있으므로, swap out될 때 해당 파일에 저장하면 된다. swap_out되면 해당 페이지의 PTE의 Present Bit은 0이 되고, 해당 페이지에 프로세스가 접근하면 페이지 폴트가 일어나고 디스크의 파일 데이터를 다시 물리 메모리에 올리면서 swap_in된다.

file_backed_swap_out()구현
1. 페이지 정보를 가져온다.
2. pml4_is_dirty 를 사용해서 페이지가 수정되었는지(dirty)를 확인한다.
3. 페이지가 수정됐다며면 file_write_at을 호출해서 데이터를 파일에 기록한다.

    pml4_set_dirty를 사용해 페이지를 클린 상태로 설정하고
    
4. pml4_clear_page를 호출하여 페이지의 매핑을 제거한다. 이는 페이지를 스왑 아웃하여 디스크에 내려놓음을 의미한다.

/* Swap out the page by writeback contents to the file. */
static bool file_backed_swap_out(struct page *page) {
    // victim의 페이지가 들어옴
    struct file_page *file_page UNUSED = &page->file;
    struct aux* aux = (struct aux *)page->uninit.aux; // file의 aux를 가져옴

    // 페이지가 dirty인지 확인
    if (pml4_is_dirty(thread_current()->pml4, page->va)) {   
        // buffer(page->va)에 있는 데이터를 size만큼, file의 file_ofs부터 써줌
        file_write_at(aux->file, page->va, aux->page_read_bytes, aux->ofs);  // 변경 사항을 파일에 다시 기록
        pml4_set_dirty(thread_current()->pml4, page->va, 0); // 페이지를 클린 상태로 변경
    }

    // 페이지 매핑 해제
    pml4_clear_page(thread_current()->pml4, page->va);  // present 비트를 0으로 설정하여 페이지를 스왑 아웃
    return true;
}

file_backed_swap_in 파일로부터 페이지를 읽어와 메모리에 적재하는 함수 구현
1. 페이지 정보 가져오기
2. 파일 위치 설정:
- file_seek(aux->file, aux->ofs);를 사용하여 파일의 읽기/쓰기 오프셋을 설정합니다. aux->ofs는 파일에서의 오프셋을 나타냅니다.
3. 파일에서 데이터 읽기:
- file_read(aux->file, kva, aux->page_read_bytes);를 사용하여 파일에서 페이지 데이터를 읽어와 kva(물리 메모리 주소)에 저장합니다.
- 읽은 바이트 수를 read_bytes에 저장하고, 이 값이 aux->page_read_bytes와 일치하지 않으면 false를 반환하여 읽기에 실패했음을 나타냅니다.
4. 남은 부분 초기화:
- memset(kva + aux->page_read_bytes, 0, aux->page_zero_bytes);를 사용하여 페이지의 나머지 부분을 0으로 초기화합니다. 이는 페이지의 일부만 파일에서 읽혔을 때 나머지 부분을 초기화하는 역할을 합니다.
5. 결과 반환:
- 모든 작업이 성공적으로 완료되면 true를 반환하여 스왑 인이 성공했음을 나타냅니다.
- 파일에서 데이터를 읽어오는 데 실패하면 false를 반환합니다.
```
/* Swap in the page by reading contents from the file. */
static bool file_backed_swap_in(struct page *page, void *kva) {
    struct file_page *file_page UNUSED = &page->file;
    struct aux *aux = (struct aux *)page->uninit.aux;

    // 파일 위치 설정
    file_seek(aux->file, aux->ofs);
    
    // 파일에서 데이터 읽기
    off_t read_bytes = file_read(aux->file, kva, aux->page_read_bytes);
    if ((int)read_bytes != (int)aux->page_read_bytes)
        return false;

    // 남은 부분 초기화
    memset(kva + aux->page_read_bytes, 0, aux->page_zero_bytes);

    return true;
}
```

문건우

반드시 해내야지

이전 포스트

[Pintos-Kaist] Project 3 : Virtual Memory

다음 포스트

메모리 스와핑

[Pintos-Kaist] Project 3 : Virtual Memory

LeetCode 14

0개의 댓글