[PintOs] Project 3 : Virtual Memory

 

 

PintOs의 세 번째 프로젝트 VM

 

구현 진행은 아래와 같다.

1. 보조 페이지 테이블 & frame 구조체 구현

2. Anonymous 페이지 & Lazy Loading & page fault 구현

3. Stack growth & 스택에 대한 page fault 처리 추가

4. File-backed 페이지 & mmap, munmap 구현

5. Swap In/Out 구현

 

 

기존에 사용하던 페이지 테이블 - pml4 이외에 pml4이 담지 못하는 정보를 위한 보조 페이지 테이블을 구현해야 한다.

보조 페이지 테이블은 배열, list, hash, bitmap 등 pintos에서 제공하는 자료구조 중 원하는 것을 선택해 사용하면 된다.

우리는 hash를 선택했다. gitbook에서 가볍게 추천하기도 했고, 늘어나는 크기에 대한 부담이 가장 적다고 판단했다.

 

 

  Supplemental Page Table

 

 

구조체 생성과 초기화

struct supplemental_page_table  
{
    struct hash hash_table;
};

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
    hash_init(&spt->hash_table, page_hash, page_less, NULL);
}

 

 

  참고 - Hash func에 대해서

 

hash 초기화에 사용하는 hash 함수들은 gitbook에 나와있는 그대로 사용하면 된다. 그래도 사용하면서 hash 함수가 어떤 구조로 동작하는지 알아두는 게 앞으로 보조 페이지 테이블을 구현하면서 헤매는 일이 적어진다. (경험담)

 

아래는 spt_find_page() 일부 코드이다.

struct page *spt_find_page(struct supplemental_page_table *spt, void *va)
{
    struct page *page = NULL;
    struct hash *hash = &spt->hash_table;

    page = (struct page *)malloc(sizeof(struct page));
    page->va = pg_round_down(va);
    struct hash_elem *e = hash_find(hash, &page->h_elem);
    
}

 

우리가 이 함수를 참고하고 들었던 의문이 있는데 

- 대체 어떻게 방금 할당한 page의 h_elem(hash elem)으로 hash find가 가능하냐 - 는 의문이다.

 

질문을 한 결과, 카이스트 조교님과 다른 정글러분께 답을 들을 수 있었다!

조교님이 알려주신 코드가 더 깔끔해보인다

 

위 이미지는 조교님께 들은 답 전문이다.

 

또, 정글러분께서 설명해주신건 hash 함수에 대해서였다.

unsigned page_hash(const struct hash_elem *p_, void *aux UNUSED)
{
    const struct page *p = hash_entry(p_, struct page, h_elem);
    return hash_bytes(&p->va, sizeof p->va);
}

 

hash에 저장되는 기준은 page가 갖고 있는 va를 기준으로 저장된다. va는 고유한 값이기 때문에 가능함.

hash에 저장되는 값은 page 구조체가 아니라 각 페이지의 va가 저장되는 것이었다.

 

그래서 hash_find()에 필요한 데이터는 va뿐이고, 더미 page 구조체를 만들어 find하고 싶은 va를 등록해주면 마치 내가 원하는 구조체 page인 것처럼 동작한다.

 

 

  spt insert & remove

 

자기가 사용할 자료구조에 맞게 구현하면 된다.

 

아래는 hash를 이용한 코드다. 필요하면 참고하시길...

bool spt_insert_page(struct supplemental_page_table *spt UNUSED,struct page *page UNUSED)
{
    int succ = false;
    struct hash *hash = &spt->hash_table;

    if (hash_insert(hash, &page->h_elem) != NULL)
    {
        return succ;
    }

    succ = true;
    return succ;
}

void spt_remove_page(struct supplemental_page_table *spt, struct page *page)
{
    hash_delete(&spt->hash_table, &page->h_elem);
    vm_dealloc_page(page);
    return true;
}

 

remove는 주의할 점이 있다.

  palloc과 malloc

 

지금은 page를 malloc으로 할당하지만, 만약 page를 palloc을 사용했다면 vm_dealloc_page()를 사용할 수 없다...

vm_dealloc_page()에서는 free()를 호출해 메모리 해제를 진행하므로 palloc으로 메모리 할당을 진행했다면 vm_dealloc_page()을 호출하는 대신 destroy()와 palloc_free_page()를 호출해야 한다.

 

그냥 편하게 malloc 쓰길 바란다...

우리팀은 malloc 대신 palloc을 사용했었다. page할당, frame할당 등에 모두 palloc을 이용했고, 추후 문제가 생겼다...

malloc은 미리 큰 크기로 페이지를 할당하지만, palloc을 이용하면 필요한 페이지 크기를 계산하던지, 하나의 페이지만 할당받아야 한다. 

 

그래서 초반에는 괜찮은데 후반의 큰 크기를 할당받아야 하는 케이스에서 palloc의 크기가 문제가 된다...잘 선택하시길!

 

 

 

 

  Page

bool vm_claim_page(void *va UNUSED)

 

보조 페이지 테이블에서 va에 해당하는 page를 반환받아 vm_do_claim_page()를 호출한다.

 

static bool vm_do_claim_page(struct page *page)

 

특정 페이지에 새로운 프레임을 할당하는 함수. 페이지와 프레임을 매핑시켜준다.

 

bool vm_claim_page(void *va UNUSED)
{
    struct page *page = NULL;
    struct supplemental_page_table *spt = &thread_current()->spt;

    page = spt_find_page(spt, va);
    if (page == NULL)
        return false;

    return vm_do_claim_page(page);
}

/* Claim the PAGE and set up the mmu. */
static bool vm_do_claim_page(struct page *page)
{
    struct frame *frame = vm_get_frame();

    frame->page = page;
    page->frame = frame;

    struct thread *cur = thread_current();
    pml4_set_page(cur->pml4, page->va, frame->kva, page->writable);


    return swap_in(page, frame->kva);
}

 

bool vm_alloc_page_with_initializer(enum vm_type type, void *upage, bool writable, vm_initializer *init, void *aux)

 

페이지는 세 타입이 있다. Uninit, Anonymous, File-backed. Uninit은 말 그대로 초기화되기 전의 상태를 말한다.

Uninit 페이지들은 어떤 타입으로 변화할 예정인지 타입을 갖고 있고, 변화할 타입에 맞는 initializer를 갖게 된다.

 

vm_alloc_page_with_initializer()에서는 새로운 Uninit 페이지를 생성하고 SPT에 삽입하는 역할을 한다.

 

 

 

  Lazy Loading

 

Lazy loading
프로그램이 실제로 해당 데이터를 필요로 할 때까지 데이터 로딩을 지연시키는 기법

Pintos에서는 데이터를 조회, 수정 등을 하기 전까지 물리 메모리에 적재하지 않다가 데이터에 대한 접근이 발생하면 PageFault를 발생시키는 lazy loading을 권장한다.

 

load_segment()로 페이지를 생성할 때는 실제 물리 메모리에는 데이터가 적재되지 않은 상태이고, 추후 해당 페이지에 접근할 때, 페이지 폴트가 발생해 lazy loading으로 데이터를 적재하는 방식이다.

 

static bool load_segment(struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable)

 

process.c에는 기존에 사용하던 load_segment()가 있다. 기존의 함수를 거의 똑같이 구현하면 된다.

다른 점은 페이지 할당을 위한 구간을 install_page() 대신 우리가 구현한 vm_alloc_page_with_initializer()를 사용해야 한다는 것이다. 바뀐 함수에 대한 조정이 필요하며, 보조 데이터에 대한 구조체를 생성해 lazy_load_segment()에 필요한 정보들을 전달해야 한다.

 

static bool load_segment(struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
    ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
    ASSERT(pg_ofs(upage) == 0);
    ASSERT(ofs % PGSIZE == 0);

    while (read_bytes > 0 || zero_bytes > 0)
    {
        size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
        size_t page_zero_bytes = PGSIZE - page_read_bytes;

        void *aux = NULL;

        struct necessary_info *nec = (struct necessary_info *)malloc(sizeof(struct necessary_info));
        nec->file = file;
        nec->ofs = ofs;
        nec->read_byte = page_read_bytes;
        nec->zero_byte = page_zero_bytes;
        aux = nec;

        if (!vm_alloc_page_with_initializer(VM_ANON, upage,
                                            writable, lazy_load_segment, aux))
            return false;
        /* Advance. */
        read_bytes -= page_read_bytes;
        zero_bytes -= page_zero_bytes;
        upage += PGSIZE;
        ofs += page_read_bytes;
    }
    return true;
}

 

 

우리가 lazy loading을 위해 구현해야 하는 함수는 lazy_load_segment()다.

bool lazy_load_segment(struct page *page, void *aux)

 

1. 전달받은 구조체에 담긴 정보를 활용한다.

2. 원하는 va에 정보를 적재한다.

3. 남은 자리를 초기화 시켜준다.

bool lazy_load_segment(struct page *page, void *aux)
{
    struct necessary_info *nec = (struct necessary_info *)aux;

    void *kpage = page->frame->kva;

    file_seek(nec->file, nec->ofs);

    if (file_read(nec->file, kpage, nec->read_byte) != (int)nec->read_byte)
    {
        palloc_free_page(kpage);
        printf("file read fail read byte %d\n", nec->read_byte);
        return false;
    }
    memset(kpage + nec->read_byte, 0, nec->zero_byte);
    return true;
}

 

 

  fork를 위한 작업 - SPT copy & kill

 

정확히는 fork를 위한 copy와 프로세스 종료를 위한 kill이다.

 

bool supplemental_page_table_copy(struct supplemental_page_table *dst, struct supplemental_page_table *src)

 

이 함수는 process.c의 do_fork()에서 호출된다.

호출할 때, 자식의 spt와 부모 spt를 매개변수로 전달하고, 이 두 테이블의 값을 똑같게 만드는 것이 우리 역할이다.

 

1. 페이지의 타입을 확인한다.

2. 자식의 테이블에 넣어줄 페이지를 생성한다.

3. 같은 물리 메모리를 바라볼 수 있게 kva를 변경한다.

bool supplemental_page_table_copy(struct supplemental_page_table *dst, struct supplemental_page_table *src)
{
    struct hash *src_hash = &src->hash_table;
    struct hash *dst_hash = &dst->hash_table;
    struct hash_iterator i;

    hash_first(&i, src_hash);
    while (hash_next(&i))
    {
        struct page *p = hash_entry(hash_cur(&i), struct page, h_elem);
        if (p == NULL)
            return false;
        enum vm_type type = page_get_type(p);
        struct page *child;

        if (p->operations->type == VM_UNINIT)
        {
            if (!vm_alloc_page_with_initializer(type, p->va, p->writable, p->uninit.init, p->uninit.aux))
                return false;
        }
        else
        {
            if (!vm_alloc_page(type, p->va, p->writable))
                return false;
            if (!vm_claim_page(p->va))
                return false;

            child = spt_find_page(dst, p->va);
            memcpy(child->frame->kva, p->frame->kva, PGSIZE);
        }
    }

    return true;
}

 

 

void supplemental_page_table_kill(struct supplemental_page_table *spt)

 

process.c 의 process_cleanup()에서 호출한다.

spt 테이블을 정리해주면 된다. 다만 테이블을 완전히 삭제하면 안 된다는 점을 명심!

process_cleanup은 프로세스 exit이외에도 init 등을 할 때 메모리 정리를 위해 사용하는데 spt를 삭제해버리면 init 이후에 사용할 테이블이 사라져버려 오류가 발생한다.

void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED)
{

    struct hash *hash = &spt->hash_table;
    hash_clear(hash, hash_elem_destroy);
}

 

 

  만약 hash를 이용해 구현했다면

 

hash를 destroy하든 clear하든 보조 함수를 구현해야 한다.

이 보조 함수에는 'hash 테이블에 있는 hash 요소 하나하나를 어떻게 처리할 것인가?' 에 대한 내용을 담으면 된다.

 

void hash_elem_destroy(struct hash_elem *e, void *aux UNUSED)
{
    struct page *p = hash_entry(e, struct page, h_elem);
    vm_dealloc_page(p);
}

 

 

 

  Stack glowth

 

process.c에서 setup_stack을 이용해 스택을 초기화한다. 이때는 1 PGSIZE만큼만 할당하기 때문에 프로그램을 사용하다보면 스택의 공간이 모자라게 된다. 이 때마다 스택을 추가로 할당하는 함수를 구현해야 한다.

 

static void vm_stack_growth(void *addr)

 

스택이 사용할 새 페이지를 할당해주면 된다.

static void vm_stack_growth(void *addr)
{
    vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), 1);
}

 

 

bool vm_try_handle_fault(struct intr_frame *f, void *addr, bool user, bool write, bool not_present)

 

page fault 발생시 호출되는 함수다. stack glowth에서 완전한 page fault 함수가 완성된다.

 

추가된 부분은 스택과 관련된 부분이다.

스택과 관련된 제한사항이 있는데,

1. 스택의 크기는 1MB를 넘어서는 안 된다.

2. rsp 위에서 일어난 페이지 폴트만 유효한 접근이다.

3. 페이지 폴트가 발생한 주소는 스택 내에 존재해야 한다.

 

이와 관련된 조건문을 작성하고 stack glowth 함수를 호출하면 된다.

 

  주의할 점

이전 project를 하면서 알게된 것 중 하나, 인터럽트 발생시 rsp가 가리키는 주소가 변경된다는 것이다. rsp를 가져올 때 이 점을 유의하자.

bool vm_try_handle_fault(struct intr_frame *f, void *addr, bool user, bool write, bool not_present)
{
    struct supplemental_page_table *spt UNUSED = &thread_current()->spt;
    struct page *page = NULL;
    if (is_kernel_vaddr(addr))
        return false;
    if (addr == NULL)
        return false;

    if (not_present)
    {
        void *rsp;
        if (user)
            rsp = f->rsp;
        else
            rsp = thread_current()->rsp_stack;

        if (rsp - 8 <= addr && USER_STACK - 0x100000 <= rsp - 8 && addr <= USER_STACK)
        {
            vm_stack_growth(pg_round_down(addr));
        }

        page = spt_find_page(spt, addr);

        if (page == NULL)
            return false;
        if (write == 1 && page->writable == 0)
            return false;
        return vm_do_claim_page(page);
    }

    return false;
}

 

 

  mmap & munmap syscall

 

void *mmap(void *addr, size_t length, int writable, int fd, off_t offset)

 

mmap 시스템 콜에서 do_mmap()을 호출한다. do_mmap()은 file.c에 있다.

mmap은 예외처리 조건이 많다.

 

void *mmap(void *addr, size_t length, int writable, int fd, off_t offset)
{
    // 파일의 시작점(offset)이 page-align되지 않았을 때
    if (offset % PGSIZE != 0)
        return NULL;
    
    // 가상 유저 page 시작 주소가 page-align되어 있는지 & user 영역인지 & 주소값이 null인지 & length가 0이하인지
    if (pg_round_down(addr) != addr || is_kernel_vaddr(addr) || addr == NULL || (long long)length <= 0)
        return NULL;
    
    // 매핑하려는 페이지가 이미 존재하는 페이지와 겹칠 때(==SPT에 존재하는 페이지일 때)
    if (spt_find_page(&thread_current()->spt, addr))
        return NULL;
    
    // 콘솔 입출력과 연관된 파일 디스크립터 값(0: STDIN, 1:STDOUT)일 때
    if (fd == 0 || fd == 1)
        exit(-1);
    
    // 찾는 파일이 디스크에 없는경우
    struct file *target = find_file_descriptor(fd)->file;
    if (target == NULL)
        return NULL;

    return do_mmap(addr, length, writable, target, offset);
}

 

void *do_mmap(void *addr, size_t length, int writable, struct file *file, off_t offset)

 

do_mmap은 파일에서 데이터를 가져와 va에 매핑하는 구조이므로 이전에 구현했던 load_segment()와 비슷한 구조로 구현할 수 있다.

주의할 점은 전달받은 file을 그대로 사용하지 않고, 다시 open한 file을 사용해야 한다.

인자로 받은 파일을 그대로 사용하면 외부에서 파일을 close 할 가능성이 있기 때문에 값을 복사하는 도중에 파일이 사라져버릴 수 있다. 안전하게 reopen을 사용하도록 하자.

void *do_mmap(void *addr, size_t length, int writable, struct file *file, off_t offset)
{
    // offset ~ length
    void *ret = addr;
    struct file *open_file = file_reopen(file);

    if (open_file == NULL)
        return NULL;

    size_t read_byte = file_length(file) < length ? file_length(file) : length;
    size_t zero_byte = PGSIZE - read_byte % PGSIZE;

    ASSERT((read_byte + zero_byte) % PGSIZE == 0);
    ASSERT(pg_ofs(addr) == 0);
    ASSERT(offset % PGSIZE == 0);

    while (read_byte > 0 || zero_byte > 0)
    {
        size_t page_read_bytes = read_byte < PGSIZE ? read_byte : PGSIZE;
        size_t page_zero_bytes = PGSIZE - page_read_bytes;

        struct necessary_info *nec = (struct necessary_info *)malloc(sizeof(struct necessary_info));
        nec->file = open_file;
        nec->ofs = offset;
        nec->read_byte = page_read_bytes;
        nec->zero_byte = page_zero_bytes;

        if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable, lazy_load_segment, nec))
            return NULL;

        read_byte -= page_read_bytes;
        zero_byte -= page_zero_bytes;
        addr += PGSIZE;
        offset += page_read_bytes;
    }

    return ret;
}

 

 

 

void do_munmap(void *addr)

 

mmap 했던 페이지에 대해 destroy를 진행한다. 직접 메모리 해제를 진행하지는 않고, file_backed_destroy를 호출한다.

void do_munmap(void *addr)
{
    while (true)
    {
        struct thread *curr = thread_current();
        struct page *find_page = spt_find_page(&curr->spt, addr);

        if (find_page == NULL)
        {
            return NULL;
        }

        struct necessary_info *nec = (struct necessary_info *)find_page->uninit.aux;
        find_page->file.aux = nec;
        file_backed_destroy(find_page);

        addr += PGSIZE;
    }
}

 

 

static void file_backed_destroy(struct page *page)

 

munmap할 페이지가 변경되었는지 확인하고, dirty한 페이지에 대해 처리를 해준다.

이후 pml4에서 페이지를 unmapping 한다.

static void file_backed_destroy(struct page *page)
{
    struct file_page *file_page UNUSED = &page->file;
    struct necessary_info *nec = file_page->aux;
    struct thread *curr = thread_current();

    if (pml4_is_dirty(curr->pml4, page->va))
    {
        file_write_at(nec->file, page->va, nec->read_byte, nec->ofs);
        pml4_set_dirty(curr->pml4, page->va, 0);
    }
    pml4_clear_page(curr->pml4, page->va);
}

 

 

  Swap In / Out

 

실제 물리 메모리보다 더 큰 것처럼 가상 메모리를 사용하기 위해 swap 시스템을 활용한다.

 

  Anonymous page Swap system

 

swap 테이블은 anonymous 페이지만 사용한다.

void vm_anon_init(void)

 

스왑 테이블을 어떤 자료구조를 사용할 지 결정한 후, disk를 받아온다.

우리는 hash table을 사용했다. bitmap을 사용하는 것도 괜찮아보인다. 우리는 익숙한 자료구조를 사용하고 싶어서 spt에서 사용했던 hash로 결정했다.

 

disk_get()을 이용해 디스크를 할당받을 수 있다. disk_get 함수의 주석 설명을 보면 아래와 같다.

Pintos uses disks this way:
0:0 - boot loader, command line args, and operating system kernel
0:1 - file system
1:0 - scratch
1:1 - swap
-devices/disk.c

 

디스크에 저장하기 위한 구조체를 만드는 것이 좋다. 우리는 slot이라는 이름의 구조체를 만들었다.

struct slot
{
    struct hash_elem swap_elem;
    int used; // 사용중 1, 사용가능 0
    int index;
    struct page *page;
};

 

각 슬롯은 page를 담을 수 있고, 고유한 index와 사용중인지 확인할 수 있는 비트를 갖는다.

void vm_anon_init(void)
{
    hash_init(&swap_table, anon_page_hash, anon_page_less, NULL);
    lock_init(&swap_lock);
    swap_disk = disk_get(1, 1); 

    disk_sector_t swap_size = disk_size(swap_disk) / 8;
    for (disk_sector_t i = 0; i < swap_size; i++)
    {
        struct slot *insert_disk = (struct slot *)malloc(sizeof(struct slot));
        insert_disk->used = 0;
        insert_disk->index = i;
        insert_disk->page = NULL;
        lock_acquire(&swap_lock);
        hash_insert(&swap_table, &insert_disk->swap_elem);
        lock_release(&swap_lock);
    }
}

 

  disk에 대해서

1개의 disk는 512 byte이고, 우리가 사용하는 page는 4096 byte다. 

하나의 disk는 하나의 page를 담지 못 하기 때문에 우리는 1 slot == 8 disk로 구성해야 한다.

disk size를 8로 나누면 slot를 몇 개 사용할 수 있는지 알 수 있다. swap size만큼 slot를 할당 및 초기화 시켜 준다.

 

slot에 page를 담는다면 page도 내가 어느 slot에 저장되어 있는지 알아야 한다.

anon_page 구조체에 slot_idx를 추가하고, -1로 초기화한다.

bool anon_initializer(struct page *page, enum vm_type type, void *kva)
{
    /* Set up the handler */
    page->operations = &anon_ops;

    struct anon_page *anon_page = &page->anon;

    anon_page->slot_idx = -1;

    return true;
}

 

---

 

 

static bool anon_swap_out(struct page *page)

 

swap 테이블에서 사용 가능한 슬롯을 찾고, disk에 페이지의 내용을 적재한다.

slot에 페이지에 대한 정보를 담은 뒤, 페이지를 사용할 수 있게 frame과의 매핑을 해제해야한다.

이때, 페이지에 슬롯 인덱스를 저장해줘야 swap_in 할 때 사용할 수 있다. 

static bool anon_swap_out(struct page *page)
{
    if (page == NULL)
        return false;
    struct anon_page *anon_page = &page->anon;
    struct slot *slot;
    struct hash_iterator i;
    hash_first(&i, &swap_table);
    lock_acquire(&swap_lock);
    while (hash_next(&i))
    {
        slot = hash_entry(hash_cur(&i), struct slot, swap_elem);
        if (slot->used == 0)
        {
            for (int i = 0; i < 8; i++)
            {
                disk_write(swap_disk, slot->index * 8 + i, page->va + DISK_SECTOR_SIZE * i);
            }

            anon_page->slot_idx = slot->index;
            slot->page = page;
            slot->used = 1;
            page->frame->page = NULL;
            page->frame = NULL;
            pml4_clear_page(thread_current()->pml4, page->va);
            lock_release(&swap_lock);
            return true;
        }
    }
    lock_release(&swap_lock);
    PANIC("full swap disk");
}

 

 

  disk 연산에 대한 간단한 설명

disk_write(swap_disk, slot->index * 8 + i, page->va + DISK_SECTOR_SIZE * i);

 

우리는 1 slot = 8 disk기 때문에 swap_size를 구하면서 나눴던 8을 지금 slot index에 곱해주는 것이다.

또, page는 4096 byte이기 때문에 disk의 크기에 맞게 offset을 이동해주며 8번 write연산을 한다. read도 같은 매커니즘으로 작성한다.

 

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

 

disk에서 메모리로 내용을 가져온다.

slot과 page에 저장되었던 서로의 정보를 초기화시켜 다음에 사용하기 용이하도록 만들어준다.

static bool anon_swap_in(struct page *page, void *kva)
{
    struct anon_page *anon_page = &page->anon;
    struct slot *slot;
    disk_sector_t page_slot_index = anon_page->slot_idx;

    struct hash_iterator i;
    hash_first(&i, &swap_table);
    lock_acquire(&swap_lock);
    while (hash_next(&i))
    {
        slot = hash_entry(hash_cur(&i), struct slot, swap_elem);
        if (slot->index == page_slot_index)
        {
            for (int i = 0; i < 8; i++)
                disk_read(swap_disk, page_slot_index * 8 + i, kva + DISK_SECTOR_SIZE * i);

            slot->page = NULL;
            slot->used = 0;
            anon_page->slot_idx = -1;
            lock_release(&swap_lock);
            return true;
        }
    }
    lock_release(&swap_lock);
    return false;
}

 

  swap hash table에서 주의할 점

 

해시 함수를 새로 만들어야 한다.

기존 해시 함수는 page->va를 기준으로 해시를 저장하기 때문에 우리가 사용할 slot의 정보를 토대로 함수를 수정해야한다. 우리는 slot의 index를 사용했다.

 

 

---

 

  File-backed page Swap system

 

파일에서 가져온 정보들이기 때문에 file-backed page는 파일로 swap out한다.

bool file_backed_initializer(struct page *page, enum vm_type type, void *kva)
{
    /* Set up the handler */
    page->operations = &file_ops;

    struct file_page *file_page = &page->file;

    file_page->aux = page->uninit.aux;

    return true;
}

 

swap in에 필요한 보조 구조체를 전달할 수 있게 file_page 구조체에 aux를 추가했다.

 

 

static bool file_backed_swap_out(struct page *page)

 

파일 갱신 여부를 확인하고, page - frame 맵핑을 해제해준다.

static bool file_backed_swap_out(struct page *page)
{
    struct file_page *file_page UNUSED = &page->file;
    if(page==NULL){
	    return false;
    }
    struct necessary_info *nec = file_page->aux;
    struct file* file = nec->file;
    lock_acquire(&file_lock);
    if(pml4_is_dirty(thread_current()->pml4,page->va)){
	    file_write_at(file,page->va, nec->read_byte, nec->ofs);
	    pml4_set_dirty(thread_current()->pml4, page->va, 0);
    }
    pml4_clear_page(thread_current()->pml4, page->va);
    lock_release(&file_lock);
    return true;
}

 

 

static bool file_backed_swap_in(struct page *page, void *kva)

 

파일에서 page로 데이터를 가져온다.

이때 aux를 사용해서 file 정보를 불러올 수 있다.

static bool file_backed_swap_in(struct page *page, void *kva)
{
    struct file_page *file_page UNUSED = &page->file;
    struct necessary_info *nec = (struct necessary_info *)file_page->aux;

    file_seek(nec->file, nec->ofs);
    lock_acquire(&file_lock);
    file_read(file_page->file, kva, nec->read_byte);
    lock_release(&file_lock);

    memset(kva + nec->read_byte, 0, nec->zero_byte);

    return true;
}

 

---

  페이지 교체 정책

 

우리는 FIFO와 Clock 알고리즘을 둘 다 구현했었다. 테스트 케이스를 돌려보면 FIFO보다 Clock이 눈에 띄게 빠르다.

 

프레임 테이블을 돌며 희생 페이지가 NULL이면 그 페이지를 바로 반환하고, NULL이 아니면 accessed 비트를 확인한다. accessed 비트가 1이면 0으로 바꿔주고, 0이면 그 페이지를 반환한다.

static struct frame *vm_get_victim(void)
{
    struct frame *victim = NULL;
    /* Clock Algorithm */
    struct list_elem *e;
    lock_acquire(&vm_lock);
    for (e = list_begin(&frame_table); e != list_end(&frame_table); e = list_next(e))
    {
        victim = list_entry(e, struct frame, f_elem);
        if (victim->page == NULL)
        {
            lock_release(&vm_lock);
            return victim;
        }
        if (pml4_is_accessed(thread_current()->pml4, victim->page->va))
            pml4_set_accessed(thread_current()->pml4, victim->page->va, 0);

        else
        {
            lock_release(&vm_lock);
            return victim;
        }
    }
    lock_release(&vm_lock);
    return victim;
}