개요
페이징(Paging)은 운영체제에서 가상 메모리를 구현하는 중요한 부분으로, 메인 메모리를 페이지(Page)라고 불리는 일정한 크기의 블록으로 구성하고, 이를 필요에 따라 2차 저장 장치에 저장하고 불러오는 방식으로 메모리를 관리합니다. 이러한 방식을 통해 운영체제는 현재 가지고 있는 메모리보다 더 많은 메모리 요청을 처리할 수 있습니다.
Page
페이지(page) 또는 가상 페이지(virtual page)는 프로세스에서 사용하는 연속적인 가상 메모리 영역을 뜻합니다.
32bit 운영체제에서 가상 메모리 주소의 크기는 32bit이며, 이중에서 20bit는 페이지 번호로 사용하고, 12bit는 오프셋으로 사용합니다.
프로세스는 고유한 가상 메모리 공간을 할당 받습니다. pintos에서는 프로세스의 각 영역(segment)이 시작되는 가상 메모리 주소가 있습니다. code segment는 가상 메모리 0x8048000에 저장되고, user stack은 PHYS_BASE(0xc0000000)에서 시작하여 메모리 주소가 낮아지는 방향으로 확장됩니다.
Frame
프레임(frame) 또는, 물리 프레임(physical frame) 또는, 페이지 프레임(page frame)은 연속적인 물리 메모리 영역을 뜻합니다.
32bit 운영체제에서 물리 메모리 주소의 크기는 32bit이며, 이중에서 20bit는 페이지 번호로 사용하고, 12bit는 오프셋으로 사용합니다.
Page Table
페이지는 프로세스에게 할당된 가상의 메모리 공간입니다. 따라서 실제 메모리에 데이터를 쓰려면 물리 메모리와 연결을 시켜야합니다. 이를 위해서 만들어진 자료구조가 페이지 테이블입니다. 운영체제는 프로세스가 요청한 가상 메모리 주소를 가지고 해당 프로세스의 페이지 테이블에 연관된 프레임을 찾습니다. 그렇게 찾은 프레임의 물리 메모리 주소에 데이터를 씁니다.
Swap Slots
스왑 슬롯(swap slots)은 page와 같은 크기를 갖는 디스크 공간들의 연속적인 집합을 말합니다. 스왑 슬롯은 운영체제에서 현재 사용하지 않는 페이지를 저장하는 역할을 합니다.
구현
1. Makefile.build 수정
virtual memory는 vm 폴더에 구현을 하는데 여기에 있는 파일들은 빌드를 할 때 포함되지 않습니다. 따라서 src/Makefile.build 파일을 수정해서 해당 파일들을 추가합니다.
수정 전
...
# No virtual memory code yet.
#vm_SRC = vm/file.c # Some file.
...수정 후
...
vm_SRC = vm/page.c
vm_SRC += vm/frame.c
vm_SRC += vm/swap.c
...2. Supplemental Page Table
pintos에서 기본적으로 page table을 구현해서 제공합니다. (userprog/pagedir.c) 하지만 기본 구현만으로는 페이지 교체를 구현할 수 없기 때문에 추가적인 정보를 저장할 SPT(Supplemental Page Table) 자료구조를 구현합니다.
자료 구조
SPT는 해시 테이블(hash table)로 구현했으며, 가상 메모리 주소를 키(key)로 사용합니다.
/* page.h */
typedef struct hash page_table_t;
enum segment
{
SEG_CODE,
SEG_STACK,
SEG_MAPPING,
};
struct page
{
struct hash_elem elem;
void *address;
enum segment segment;
bool writable;
struct file *file;
off_t position;
uint32_t read_bytes;
uint32_t zero_bytes;
mapid_t mapid;
};
void page_table_init (page_table_t *table);
void page_table_destroy (page_table_t *table);
void page_table_insert (page_table_t *table, struct page *page);
struct page * page_table_lookup (page_table_t *table, const void *address); 3. Frame Table
Frame Table은 현재 운영체제에서 사용 중인 프레임(frame)을 관리합니다. frame_table_get_frame() 함수를 통해서 비어있는 프레임을 할당 받습니다. 만약 비어있는 프레임이 없다면 swapping을 통해서 프레임을 확보합니다.
/* frame.h */
void frame_table_init (void);
void * frame_table_set_frame (void *upage);
void * frame_table_get_frame (void *upage);
void frame_table_clear_frame (void *upage);
void frame_table_lock_frame (void *kpage);
void frame_table_unlock_frame (void *kpage);
자료 구조
Frame Table은 list로 구현하였으며 전역 데이터입니다(frame_list). 따라서 경쟁 조건을 피하기 위해서 frame_table_lock을 사용합니다.
Frame Table의 구성 요소는 프레임을 사용 중인 스레드의 아이디(tid), page directory(pagedir)와 supplemental page table(extra_page_table), 그리고 프레임에 연관된 가상 메모리 주소(upage), 물리 메모리 주소(kpage)가 있습니다.
Frame Table에서 비어있는 프레임이 없는 경우, 사용 중인 프레임 중에 가장 사용되지 않은 프레임을 선택합니다(LRU). 그런데 디스크 입출력 같이 외부 장치가 사용 중인 경우에는 LRU 알고리즘에 교체 대상이 될 수 있습니다. 따라서 이런 경우에는 locked_frame_list에 넣어서 교체 알고리즘 대상에서 제외합니다. 디스크 입출력이 끝나면 다시 frame_table 추가합니다.
/* frame.c */
struct frame
{
struct list_elem elem;
tid_t tid;
uint32_t *pagedir;
page_table_t *extra_page_table;
void *upage;
void *kpage;
};
static struct list frame_table = LIST_INITIALIZER (frame_table);
static struct list locked_frame_list = LIST_INITIALIZER (locked_frame_table);
static struct lock frame_table_lock;
...
프레임 교체 알고리즘
Frame Table에서 프레임을 할당할 때마다 frame_list를 갱신합니다. 이때 리스트를 순회하면서 해당 프레임에 접근한 기록이 있다면 리스트의 맨 앞으로 보냅니다.
static void
frame_table_update (void)
{
if (list_empty (&frame_table))
return;
lock_acquire (&frame_table_lock);
struct list_elem *cursor = list_begin (&frame_table);
while (cursor != list_end (&frame_table))
{
struct frame *f = list_entry (cursor, struct frame, elem);
if (f->pagedir != NULL && pagedir_is_accessed (f->pagedir, f->upage))
{
struct list_elem *prev = cursor;
cursor = list_remove (prev);
list_push_front (&frame_table, prev);
}
else
cursor = list_next (cursor);
}
lock_release (&frame_table_lock);
}프레임 얻기
가상 메모리 주소(upage)를 물리 메모리 주소(kpage)와 연결 시키기 위해 frame_table_set_frame() 함수를 호출합니다. 여기서 palloc_get_page() 함수를 사용해서 프레임을 얻어오는데 NULL을 받았다면 더이상 할당할 프레임이 없다는 뜻입니다. 그러면 이제 Frame Table에서 가장 오래 사용되지 않은 프레임을 얻어옵니다. 그리고 이 프레임을 사용 중인 페이지 정보를 가져옵니다. 프레임을 사용 중인 페이지가 code 또는 stack인 경우에는 먼저 쓰기 가능한지를 살펴봅니다. 만약 읽기 전용인 경우에는 해당 프레임을 Swap Table에 쓸 필요가 없습니다. code 영역이 이에 해당하는데, code 영역에 해당하는 데이터는 프로그램 파일에 저장되어 있기 때문에, 다시 필요할 경우 프로그램의 해당 영역을 읽으면 됩니다. 그 외에는 swapping이 필요한 경우 swap in을 합니다. memory mapped file의 경우에는 해당 프레임에 수정이 발생한 경우에만 연관된 파일을 갱신합니다.
이렇게 프레임에 있던 데이터를 백업했다면, 프레임 사용자 정보를 갱신합니다. 그리고 해당 프레임의 물리 메모리 주소를 반환합니다.
void *
frame_table_set_frame (void *upage)
{
void *kpage = palloc_get_page (PAL_USER);
struct frame *f;
if (!kpage)
{
frame_table_update ();
lock_acquire (&frame_table_lock);
f = list_entry (list_back (&frame_table), struct frame, elem);
list_remove (&f->elem);
lock_release (&frame_table_lock);
struct page *p = page_table_lookup (f->extra_page_table, f->upage);
switch (p->segment)
{
case SEG_CODE:
case SEG_STACK:
if (p->writable)
{
if (pagedir_is_dirty (f->pagedir, f->upage) || !swap_table_is_swapped (f->tid, f->upage))
p->position = swap_table_swap_in (f->tid, f->upage, f->kpage);
}
break;
case SEG_MAPPING:
if (pagedir_is_dirty (f->pagedir, f->upage))
{
file_seek (p->file, p->position);
file_write (p->file, p->kpage, PGSIZE);
}
break;
}
pagedir_clear_page(f->pagedir, f->upage);
}
else
{
f = malloc (sizeof (struct frame));
f->kpage = kpage;
}
struct thread *t = thread_current ();
f->tid = t->tid;
f->pagedir = t->pagedir;
f->extra_page_table = &t->extra_page_table;
f->upage = upage;
lock_acquire (&frame_table_lock);
lish_push_front (&frame_table, &f->elem);
lock_release (&frame_table_lock);
return f->kpage;
}4. Swap Table
프레임(frame)은 모든 프로세스가 나누어 쓰기 때문에 모자랄 수 밖에 없습니다. 따라서 운영체제는 프로세스가 현재 사용 중이지 않은 프레임 정보를 Swap Table이라는 데이터에 보관합니다. 이 Swap Table은 보통 2차 저장 장치에 있습니다.
/* swap.h */
void swap_table_init (void);
void swap_table_remove (tid_t tid, void *upage);
off_t swap_table_swap_in (tid_t tid, void *upage, void *kpage);
void swap_table_swap_out (tid_t tid, void *upage, void *kpage, off_t position);
bool swap_table_is_swapped (tid_t tid, void *upage);
자료 구조
Swap Table은 리스트로 구현하였습니다(swap_table). 그리고 Swap Table은 전역 데이터이기 때문에 swap_table_lock을 통해서 경쟁 상태를 방지합니다.
Swapping을 할 때, 디스크에서 빈 공간을 찾아야 하는데, 이를 빨리 찾기 위해서 bitmap 자료구조인 slot_map을 사용합니다. 이를 통해서 디스크를 직접 읽지 않고 현재 비어있는 공간의 인덱스를 빠르게 찾을 수 있습니다.
/* swap.c */
struct slot
{
struct list_elem elem;
tid_t tid;
void *upage;
size_t index;
};
static struct list swap_table;
static struct lock swap_table_lock;
static struct bitmap *slot_map;
static size_t slot_count;
Swap In (Memory -> Disk)
스왑을 하기 위해서 먼저 slot_map을 통해 비어있는 디스크의 인덱스를 찾습니다. 그리고 해당 디스크의 위치를 계산합니다. pintos에서 디스크의 경우 단위가 BLOCK_SECTOR_SIZE입니다. 그리고 Swap Slot은 프레임 하나를 저장하고, 프레임은 페이지와 같은 크기를 같기 때문에, "position = (PGSIZE * index) / BLOCK_SECTOR_SIZE"가 됩니다. 그리고 그 위치부터 PGSIZE만큼 데이터를 디스크에 복사합니다. 복사가 완료되었으면, 해당 정보를 slot 구조체를 만들어서 저장합니다. 그리고 디스크에 써진 시작 위치를 반환합니다. 이 값은 나중에 swap out을 할때 사용합니다.
/* swap.c */
off_t
swap_table_swap_in (tid_t tid, void *upage, void *kpage)
{
lock_acquire (&swap_table_lock);
struct block *b = block_get_role (BLOCK_SWAP);
size_t index = bitmap_scan (slot_map, 0, 1, false);
ASSERT (index != BITMAP_ERROR);
off_t start = (PGSIZE * index) / BLOCK_SECTOR_SIZE;
off_t ofs = start;
size_t write_bytes = PGSIZE;
uint8_t *buffer = kpage;
while (write_bytes > 0)
{
block_write (b, ofs, buffer);
++ofs;
write_bytes -= BLOCK_SECTOR_SIZE;
buffer += BLOCK_SECTOR_SIZE;
}
struct slot *s = malloc (sizeof (struct slot));
s->tid = tid;
s->upage = upage;
s->index = index;
list_push_back (&swap_table, &s->elem);
bitmap_set (slot_map, index, true);
lock_release (&swap_table_lock);
return start;
}
Swap Out (Disk -> Memory)
먼저 tid와 upage를 사용해서 slot 구조체를 찾습니다. slot 구조체가 있으면 swap이 되어 있는 상태이니 해당 위치로부터 데이터를 읽습니다. 데이터를 읽어왔으면 slot 구조체를 제거하고, slot_map에서 해당 위치를 사용 가능하다고 표시합니다.
/* swap.c */
void
swap_table_swap_out (tid_t tid, void *upage, void *kpage, off_t position)
{
lock_acquire (&swap_table_lock);
struct slot *s = find_swap_slot (tid, upage);
if (s != NULL)
{
struct block *b = block_get_role (BLOCK_SWAP);
size_t read_bytes = PGSIZE;
uint8_t *buffer = kpage;
while (read_bytes > 0)
{
block_read (b, position, buffer);
++position;
read_bytes -= BLOCK_SECTOR_SIZE;
buffer += BLOCK_SECTOR_SIZE;
}
list_remove (&s->elem);
bitmap_set (slot_map, s->index, false);
free (s);
}
lock_release (&swap_table_lock);
}
