PintOS Project 3 : Virtual Memory(3) - swap in & swap out LRU

이번 포스팅은 효율적으로 메모리 관리를 하기 위해 물리메모리에서 frame을 swap_out 하는 것을 할 것이다.

 

LRU(Least Recently Used)는 페이지 교체 알고리즘중 하나로, 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식입니다. 이 알고리즘은 메모리에서 사용되지 않은 페이지를 교체하여, 효율적인 메모리 관리와캐시 히트율 향상을 목표로 합니다.

LRU 알고리즘의 기본 개념

• 가장 최근에 사용된 페이지는 계속 유지하고, 오랫동안 사용되지 않은 페이지는 교체 대상으로 선정합니다.
• Least Recently Used*라는 이름 그대로, 가장 최근에 사용되지 않은 페이지를 교체합니다.
• LRU는 사용된 페이지의 시간 순서를 유지하면서, 오래 사용되지 않은 페이지를 찾기 위한 정보를 기록하는 방식입니다.

 

swap out을 할 때는 어떤 페이지(프레임)를 희생으로 선정할 것이냐를 정해야 하며 이는 LRU알고리즘을 사용한다.

 

Swap out

// clock 방식으로 victim page를 선택
static struct frame *vm_get_victim (void) {
    struct frame *victim = NULL;
    /* TODO: The policy for eviction is up to you. */
    struct thread *curr = thread_current();

    // Second Chance 방식으로 결정
    struct list_elem *e = list_begin(&frame_table);
    for (e; e != list_end(&frame_table); e = list_next(e)) {
        victim = list_entry(e, struct frame, frame_elem);
        if (pml4_is_accessed(curr->pml4, victim->page->va))
            pml4_set_accessed(curr->pml4, victim->page->va, false); // accessed가 true인 페이지를 통과하면서 false로 교체하여 다음에 선정될 수 있도록 한다.
        else
            return victim;
    }

    return list_entry(list_begin(&frame_table), struct frame, frame_elem);
}

 

 

선정된 희생 페이지(프레임)를 swap_out

 

// file backed page swap out
static bool file_backed_swap_out (struct page *page) {
    struct file_page *file_page UNUSED = &page->file;
    if (pml4_is_dirty(thread_current()->pml4, page->va)) {
        file_write_at(file_page->file, page->va, file_page->length, file_page->offset);
        pml4_set_dirty(thread_current()->pml4, page->va, false);
    }

    page->frame->page = NULL;
    page->frame = NULL;
    pml4_clear_page(thread_current()->pml4, page->va);

    return true;
}


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

    size_t free_idx = bitmap_scan_and_flip(swap_table, 0, 1, false);

    if (free_idx == BITMAP_ERROR)
        return false;

    size_t sector = free_idx * SECTORS_IN_PAGE;

    for (size_t i = 0; i < SECTORS_IN_PAGE; i++)
        disk_write(swap_disk, sector + i, page->va + DISK_SECTOR_SIZE * i);

    anon_page->slot = free_idx;

    page->frame->page = NULL;
    page->frame = NULL;
    pml4_clear_page(thread_current()->pml4, page->va);

    return true;
}

 

file backed page를 설명하자면 페이지 테이블 엔트리에서 dirty bit를 확인하여 수정된 파일이면 파일에서 위치를 찾아 write를 실행하고 dirty bit를 0으로 설정한다. 이후 가상 메모리 물리 메모리 매핑을 해제하고 pml4에서 지운다.

 

anonymous page는 swap table에서 비어있는 슬롯의 인덱스를 찾아서 페이지에서 swap_disk로 저장한다.

이후 swap_table에 인덱스를 anon_page slot에 설정하고 다음에 읽을 때 어디서 읽을 지를 저장해둔다. 페이지 - 프레임의 매핑을 해제하고 pml4에서 지운다.

 

 

 

 

destroy

 

static void anon_destroy (struct page *page) {
    struct anon_page *anon_page = &page->anon;

    /** Project 3: Swap In/Out - 점거중인 bitmap 삭제 */
    if (anon_page->slot != BITMAP_ERROR)
        bitmap_reset(swap_table, anon_page->slot);
        // 스왑 테이블에서 해당 슬롯을 해제하여 다시 사용할 수 있도록 합니다.

    /** Project 3: Anonymous Page - 점거중인 frame 삭제 */
    if (page->frame) {
        list_remove(&page->frame->frame_elem);
        page->frame->page = NULL;
        free(page->frame);
        page->frame = NULL;
    }

    /** Project 3: Copy on Write (Extra) - destroy 시 pml4 clear하여 참조하던 kva들을 모두 해제한다.
     * 그렇지 않으면 자식에서 `exit`시 참조한 부모의 kva가 파괴되어 자식이 부모에서 해당 kva에 접근할 수 없기 때문이다. */
    pml4_clear_page(thread_current()->pml4, page->va);
}


static void file_backed_destroy (struct page *page) {
    struct file_page *file_page UNUSED = &page->file;

    if (pml4_is_dirty(thread_current()->pml4, page->va)) {
        file_write_at(file_page->file, page->va, file_page->length, file_page->offset);
        pml4_set_dirty(thread_current()->pml4, page->va, false);
    }

    if (page->frame) {
        list_remove(&page->frame->frame_elem);
        page->frame->page = NULL;
        page->frame = NULL;
        free(page->frame);
    }

    pml4_clear_page(thread_current()->pml4, page->va);
}