struct anon_page
{
/* 음수이면 스왑 아웃 상태가 아님 */
int swap_idx;
};그러면 이제 mmap 구현에 이어 swap in/out 구현기를 정리하겠다.
내가 구현을 맡은 파트는 아니라서 조금 설명이 부족할 수도 있지만 감안하고 보십쇼
그전에 모든 테스트를 통과한 우리의 깃 레포를 첨부해주겠다. 어떻게 작성했는지 보고싶으면 여기로 와라
https://github.com/Week12-13-GOAT
Week12-13-GOAT
Week12-13-GOAT has one repository available. Follow their code on GitHub.
github.com
swap이 무엇인가?
구현에 앞서 먼저 개념을 아는 것이 중요하다. 현재 우리가 사용하는 전자기기들의 메모리 용량은 상당히 넉넉하다. 내가 사용하는 노트북의 메모리만 해도 32GB나 된다. 하지만 옛날에는 1GB도 큰 용량이라고 부르던 시절이 있었다. 이 때도 여러 프로세스를 실행하고 있었을 텐데, 메모리가 부족해지면 어떻게 되는걸까?
당연히 메모리에서 공간을 확보한 다음 적재해줘야겠지? 공간을 확보하려면 메모리를 차지하고 있던 다른 프로세스의 페이지 중 하나를 쫓아내야 한다. 이 과정을 swap-out이라고 한다.
그런데 컨텍스트 스위칭으로 다른 프로세스가 실행 중일 때 쫓아낸 페이지가 필요하면 어떻게 할까? 이 페이지를 다시 가져와야 할 텐데 다시 disk를 뒤져서 그 정보를 가져오려면 너무 느리지 않을까? 그래서 swap-out된 페이지만 따로 저장해두는 곳이 swap-disk이다. 이 disk에 어디에 저장되어있는지에 대한 정보를 저장해두는 것이 swap-table이다.
그리고 swap-table에서 백업되어있는 필요 페이지를 다시 메모리에 적재하는 것이 swap-in이다.
그러면 필요한 구조체는 swap-disk와 swap-table 이 두개일 텐데 어떻게 만들면 될까?
그전에 먼저 !! 우리는 vm에서 페이지의 종류가 3개였다. 미초기화, 익명, 파일 페이지. 파일 페이지 같은 경우에는 swap-in/out을 위해 따로 swap-disk를 둘 필요가 없다 !! 왜냐? 이미 파일 그 자체가 백업 디스크이기 때문이다.
그럼 미초기화 페이지는? 애초에 초기화가 진행되지 않아서 매핑된 프레임 자체가 없다. 물리 메모리에 실제 데이터가 차지하는 공간 자체가 없다는 것이다. 따라서 swap-in/out 자체가 필요가 없다.
swap-disk와 swap-table을 사용하는 건 오직 익명 페이지 뿐이다. 이를 확실히 알고 가자.
swap-in/out 흐름
그러면 pintos에서 swap은 어디서부터 시작되는걸까? 우리는 vm_get_frame을 통해 필요한 물리 공간을 할당받는다. vm_get_frame 내부에서는 palloc_get_page를 통해 할당받은 실제 물리 주소를 가져오는데, 이 때 NULL을 반환하면 유저 풀에서 더 이상 할당해줄 공간이 없다는 뜻이다. 이때 vm_evict_frame으로 희생자 프레임을 찾아 swap_out을 진행하고, 희생된 프레임의 주소를 할당해주면 되는 것이다. 그러면 이 때 희생자 프레임을 찾을 때는 어떻게 찾을 것인가? 할당받준 프레임을 추적하는 자료구조가 있어야 가능하지 않을까? 우리 팀은 이것을 list로 구현했다. 할당받을 때는 이 list에 등록해주고, swap-out 될 때는 이 list에서 remove만 해주면 된다.
당연히 이 자료구조는 pintos 내에 하나만 존재해야 한다. swap-out이 될 때는 다른 프로세스의 프레임을 쫓아내줘야 하니까 !
// vm용 프레임 테이블
struct list frame_table;먼저 이렇게 전역적인 장소에 list를 만들어두자. 우리는 이를 thread.c에 만들어두었다. 당연히 초기화도 진행해주어야 한다.
list_init(&frame_table);어디에 하든 시스템이 초기화될 때 진행해주면 된다. 우리는 thread_init에 해주었다.
이제 자료구조도 만들었으면 흐름을 한번 따라가보자. 먼저 미초기화된 페이지나 swap-out된 프레임에 접근하면 페이지 폴트가 발생해서 exception.c의 page_fault가 호출된다.
#ifdef VM
/* For project 3 and later. */
if (vm_try_handle_fault(f, fault_addr, user, write, not_present))
return;
#endif그리고 vm_try_handle_fault를 호출하게 된다.
handle_fault 함수 내부에서는 이 폴트를 검증하고, vm_do_claim_page를 호출하게 된다.
bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED,
bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
...
return vm_do_claim_page(page);
}vm_do_claim_page에서는 이 페이지에 프레임을 할당해주기 위해 vm_get_frame을 호출한다.
static bool
vm_do_claim_page(struct page *page)
{
void *temp = page->operations->swap_in;
struct frame *frame = vm_get_frame();
...
}그러면 vm_get_frame에서는 위에서 작성해둔 바와 같이 palloc_get_page를 호출하고, 여기서 실패하면 이미 모든 물리 프레임 공간이 할당되어있다는 소리이니 swap_out을 진행한다.
static struct frame *
vm_get_frame(void)
{
struct frame *frame = malloc(sizeof(struct frame));
ASSERT(frame != NULL);
frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);
if (frame->kva == NULL)
{
struct frame *victim1 = vm_evict_frame();
ASSERT(victim1 != NULL);
frame->kva = victim1->kva; // victim의 물리 페이지를 재활용
free(victim1);
}
frame->page = NULL;
frame_table_insert(&frame->elem);
ASSERT(frame->page == NULL);
return frame;
}vm_evict_frame은 내부적으로 어떤 역할을 할까?
/* 한 페이지를 교체(evict)하고 해당 프레임을 반환합니다.
* 에러가 발생하면 NULL을 반환합니다.*/
static struct frame *
vm_evict_frame(void)
{
struct frame *victim = vm_get_victim();
if (victim == NULL)
return NULL;
struct page *victim_page = victim->page;
if (victim_page == NULL)
return NULL;
if (!swap_out(victim_page))
return NULL;
pml4_clear_page(thread_current()->pml4, victim_page->va);
list_remove(&victim->elem);
return victim;
}여기서는 또 vm_get_victim으로 희생될 페이지를 찾아야 한다 !! 그래야만 해당 페이지에 적재된 swap_out 함수를 호출할 수 있다... 진짜 흐름이 너무나도 깊다...
희생자 페이지에 대한 swap_out이 진행되고 나면 해당 페이지가 가지고 있던 가상 주소(va)의 PTE는 pml4_clear_page로 깔끔하게 청소해줘야 한다. 아니면 swap_out을 진행했더라도 이 페이지가 가지고 있던 물리 주소를 계속 가리킬 수 있다. 우리는 이 물리 주소를 재활용해줘야하는데, 희생자 페이지가 계속 그 물리 주소를 가리키고 있으면? 당연히 엄청난 에러가 발생할 것이다.
그리고 swap_out되었으므로 frame_tabe에서 remove 해준다.
마지막으로 vm_get_victim인데... swap_out을 진행할 대상을 선정하는 알고리즘이 구현되어있다. 복잡하게 구현하기 싫으면 FIFO로 단순하게 만들어도 된다. 우리 팀은 clock 알고리즘을 만들어 구현했는데, 설명은 나중에 기회가 되면 자세히 포스팅하겠다.
vm_get_victim 코드는 더보기에 !!
static struct frame *vm_get_victim(void)
{
struct list_elem *clock_now;
struct frame *victim;
ASSERT(victim != NULL);
if(clock_start == NULL || clock_start == list_end(&frame_table))
clock_start = list_begin(&frame_table);
clock_now = clock_start;
do{
victim = list_entry(clock_now,struct frame, elem);
bool success = pml4_is_accessed(thread_current()->pml4,victim->page->va);
if(success == false){
clock_start = list_next(clock_now);
return victim;
}
pml4_set_accessed(thread_current()->pml4,victim->page->va, false);
clock_now = list_next(clock_now);
if(clock_now == list_end(&frame_table))
clock_now = list_begin(&frame_table);
} while(clock_now != clock_start);
victim = list_entry(clock_now,struct frame, elem);
clock_start = list_next(clock_now);
return victim;
}여기까지 흐름이 끝났으면 다시 vm_do_claim_page로 돌아와서, swap_in 매크로를 호출한다. 이 페이지가 미초기화 페이지라면 uninit_initialize가 실행되고, 파일 페이지라면 file_backed_swap_in이, 익명 페이지라면 anon_swap_in이 호출될 것이다.
미초기화 페이지는 단순히 초기화 작업일 뿐이니까... 우리가 이 포스팅에서 볼 것은 아니다.
자 이제 swap_out과 swap_in 매크로를 호출했을 때, 각자 어떤 로직이 작동하는지 확인해보자 !! 익명 페이지와 파일 페이지만 보면 된다 !!
익명 페이지 swap
pintos에서 swap-disk는 이미 disk라는 구조체를 사용하라고 뼈대가 만들어져 있다. 그러면 swap-table은? 여러 자료구조를 사용할 수 있겠지만, bitmap이라는 자료구조가 가장 좋아보인다.
bitmap은 단순한 비트의 나열이다. 디스크의 영역과 비트를 일대일 매핑시켜서, 비트가 1이라면 이미 사용중이고, 0이라면 비어있음을 나타내면 된다.
bitmap 사용법은 다음을 참고
https://github.com/Week12-13-GOAT/pintos-vm/wiki/Bitmap-%EC%82%AC%EC%9A%A9-%EB%B0%A9%EB%B2%95
Bitmap 사용 방법
미니준혁이에게 짬때리는 레포. Contribute to Week12-13-GOAT/pintos-vm development by creating an account on GitHub.
github.com
그 전에 먼저 주의해야 할 점 !! 우리는 page 단위로 swap-in/out을 진행할 것이다. 하지만 disk의 단위는 sector이다. page는 4KB, sector는 512B이다. 1페이지 = 8섹터가 성립하는 것이다.
그러면 1비트도 당연히 8섹터를 가리키는 것이겠지? 그림으로 보면 다음과 같다
0번 비트는 1로 set 되어있다. 이는 swap-disk의 0~7번 섹터에 데이터가 존재한다는 뜻이다.
1번 비트와 2번 비트는 0으로 set되어 있다. 이는 swap-disk의 8번 섹터부터 23번 섹터까지 비어있다는 뜻이다.
우리는 이와 같이 비트 번호로 (비트 번호) * 8번 섹터부터 (비트 번호) * 8 + (8-1)섹터까지 데이터가 존재하는지 아니면 비어있는지를 알 수 있게 되었다.
그러면 페이지가 swap-out될 때 몇 번 섹터에 저장되어있는지 확인하기 위한 필드가 필요하다. 당연히 swap-table의 비트 번호를 추가하면 페이지 구조체에 저장해두면 되겠지?
초기화 과정
struct anon_page
{
/* 음수이면 스왑 아웃 상태가 아님 */
int swap_idx;
};하지만 이 익명 페이지가 아직 swap-out되지 않고 메모리에 적재되어 있다면? 그 때는 swap_idx가 음수인 것으로 구분하자.
bool anon_initializer(struct page *page, enum vm_type type, void *kva)
{
...
/* Set up the handler */
page->operations = &anon_ops;
/* uninit을 anon으로 변환 */
struct anon_page *anon_page = &page->anon; // page->anon은 포인터가 아니라 구조체 자체여서 항상 유효한 주소를 반환함
/* swap index 초기화 */
anon_page->swap_idx = -1;
...
}이렇게 익명 페이지 초기화 함수에서 swap_idx를 -1로 초기화해주자 !
anon_swap_in
먼저 이 페이지의 swap_idx가 음수인지 아닌지를 체크해보자. 음수라면 swap된 적이 없으므로 그냥 바로 false를 리턴해주면 된다.
struct anon_page *anon_page = &page->anon;
int swap_idx = anon_page->swap_idx;
if (swap_idx < 0)
{
return false;
}위 검사를 통과했다면, swap-out 되어있는 상태이므로 디스크에서 해당 크기만큼 읽어서 메모리에 적재해주자 !!
for (int i = 0; i < 8; i++)
{
disk_read(swap_disk, // 스왑 디스크에서 데이터를 읽어옴
(swap_idx * 8) + i, // 8개의 연속된 섹터에 페이지가 저장되어 있으므로, i를 더해가며 읽음
kva + (DISK_SECTOR_SIZE * i)); // 읽어온 데이터를 커널 가상 주소 kva에 512B 단위로 복사
}
// 스왑 테이블에서 해당 스왑 슬롯을 비어있다고 표시 (해당 슬롯 재사용 가능하도록)
bitmap_reset(swap_table, swap_idx);
// 페이지가 더 이상 스왑 영역에 존재하지 않음을 나타내기 위해 swap_idx를 -1로 초기화
anon_page->swap_idx = -1;
return true;위에서 설명했듯이 swap_idx(비트 번호) * 8부터 시작해서 + 7까지 순회하며 disk_read를 진행한다. 512바이트씩 읽어오므로 적재할 물리 주소도 DISK_SECTOR_SIZE(512)만큼 증가시켜주면서 적재해주면 된다.
이후 bitmap_reset으로 swap_table의 해당 swap_idx를 0으로 만들어서 swap_disk의 해당 영역은 사용 가능하다고 표시해주자.
그 다음 이 페이지의 swap_idx를 -1로 바꿔서 swap_out 되어있지 않음을 나타내주자.
전체 코드는 더보기
/* 스왑 디스크에서 내용을 읽어와 페이지를 스왑인합니다. */
static bool
anon_swap_in(struct page *page, void *kva)
{
struct anon_page *anon_page = &page->anon;
int swap_idx = anon_page->swap_idx;
// 예외 처리 → swap_idx가 -1이면 페이지가 스왑아웃된 적이 없거나 이미 복구되었으므로 스왑 인 생략
if (swap_idx < 0)
{
return false;
}
// disk_read에서 사용할 버퍼
// void *buffer[PGSIZE];
/** TODO: 페이지 스왑 인
* disk_read를 데이터를 읽고 kva에 데이터 복사
* swap_idx를 -1로 바꿔주어야 함
* 프레임 테이블에 해당 프레임 넣어주기
* 프레임하고 페이지 매핑해주기
*/
// 한 섹터는 512바이트이고, 한 페이지는 4KB(4096바이트)이므로
// 총 8개의 섹터를 순차적으로 읽어야 전체 페이지 데이터를 복원할 수 있음
// swap_idx는 스왑 테이블 상의 페이지 단위 인덱스를 의미하며,
// 실제 섹터 번호는 swap_idx * 8부터 시작함
for (int i = 0; i < 8; i++)
{
disk_read(swap_disk, // 스왑 디스크에서 데이터를 읽어옴
(swap_idx * 8) + i, // 8개의 연속된 섹터에 페이지가 저장되어 있으므로, i를 더해가며 읽음
kva + (DISK_SECTOR_SIZE * i)); // 읽어온 데이터를 커널 가상 주소 kva에 512B 단위로 복사
}
// 스왑 테이블에서 해당 스왑 슬롯을 비어있다고 표시 (해당 슬롯 재사용 가능하도록)
bitmap_reset(swap_table, swap_idx);
// 페이지가 더 이상 스왑 영역에 존재하지 않음을 나타내기 위해 swap_idx를 -1로 초기화
anon_page->swap_idx = -1;
return true;
}anon_swap_out
그러면 swap_disk에 백업은 어떻게 할까? swap_in이랑 비슷하게 하면 될 것 같다.
size_t swap_idx = bitmap_scan_and_flip(swap_table, 0, 1, false);먼저 bimap_scan_and_file을 통해 0으로 세트되어있는 비트 한개의 위치를 가져오자.
for (int i = 0; i < 8; i++)
{
disk_write(swap_disk, (swap_idx * 8) + i, page->frame->kva + (DISK_SECTOR_SIZE * i));
}그리고 순회를 돌며 swap_disk에 swap_idx * 8부터 + 7까지, 해당 페이지의 물리 주소를 512바이트 만큼 저장해준다. 당연히 512바이트만큼 저장했으니 다음에 저장할 주소도 512만큼 증가해야한다.
page->frame->page = NULL;
page->frame = NULL;
anon_page->swap_idx = swap_idx;마지막으로, swap_out된 frame과 페이지 간의 연결을 끊어주고, 어느 영역에 저장되어있는지 swap_idx를 업데이트한다.
코드 전체는 더보기
/* 페이지의 내용을 스왑 디스크에 기록하여 스왑아웃합니다. */
static bool
anon_swap_out(struct page *page)
{
// page 인자의 예외 처리
if (page == NULL)
{
return false;
}
struct anon_page *anon_page = &page->anon;
/** TODO: disk_write를 사용하여 disk에 기록
* 섹터 크기는 512바이트라 8번 반복해야합니다
* 비어있는 스왑 슬롯을 스왑 테이블에서 검색
* 검색된 스왑 슬롯 인덱스를 anon_page에 저장
* disk_write를 통해 해당 디스크 섹터에 저장
*/
size_t swap_idx = bitmap_scan_and_flip(swap_table, 0, 1, false);
if (swap_idx == BITMAP_ERROR)
{
ASSERT(bitmap_test(swap_table, swap_idx) == false);
return false;
}
// swap in에 자세히 주석을 달아 놓았음 잘 살펴 보셈
for (int i = 0; i < 8; i++)
{
disk_write(swap_disk, (swap_idx * 8) + i, page->frame->kva + (DISK_SECTOR_SIZE * i));
}
// 페이지와 프레임 간의 연결을 끊음 (프레임은 더 이상 이 페이지를 참조 하지 않음)
page->frame->page = NULL;
page->frame = NULL;
// 스왑 슬록 인덱스를 anon_page에 저장해 나중에 다시 swap_in할 수 있게 함
anon_page->swap_idx = swap_idx;
return true;
}파일 페이지 swap
그러면 파일 페이지는 어떻게 하면 될까? 파일 페이지는 파일 그 자체가 swap_disk와 같은 역할을 하기 때문에 file에 write_back만 잘 해주면 된다.
이전 포스팅에서, file_page에 백업 정보를 저장해두었다.
struct file_page
{
int mapping_count;
struct file *file;
off_t offset;
size_t read_byte;
size_t zero_byte;
};우리는 이 정보를 이용해서 스왑을 진행해주면 된다 !!
file_backed_swap_in
static bool
file_backed_swap_in(struct page *page, void *kva)
{
struct file_page *file_page UNUSED = &page->file;
struct file *file = file_page->file;
off_t offset = file_page->offset;
size_t read_byte = file_page->read_byte;
// 파일에서 데이터를 읽어와 kva(페이지가 매핑된 커널 가상 주소)에 저장
if (file_read_at(file, kva, read_byte, offset) != (off_t)read_byte)
{
// 읽은 바이트 수가 기대치와 다르면 오류 처리
return false;
}
// 파일에서 읽어오지 못한 나머지 페이지 영역을 0으로 초기화
memset(kva + read_byte, 0, page->file.zero_byte);
return true;
}사실 특별히 설명할만한 로직은 없다. file_read_at을 정확히 어떻게 사용하는지만 알아두면 될 것 같다.
file_backed_swap_out
파일 페이지를 스왑 아웃할 때 무조건 파일에다가 내용을 덮어쓰는게 좋은 일일까? 아니다. 해당 파일 페이지 내용이 아예 바뀌지도 않았는데 덮어쓰는건 성능의 낭비다. 따라서 우리는 PTE를 검사해서 이 가상 주소에 담긴 물리 주소 데이터가 변경되었음을 알려주는 dirty_bit를 알아내어 사용할 것이다.
bool dirty_bit = pml4_is_dirty(curr->pml4, page->va);pml4_is_dirty는 이 가상 주소에 있는 PTE의 제어 비트 중 PTE_D를 검사해서 bool 자료형을 넘겨준다. true라면 변경된 것이다.
if (dirty_bit == true)
{
lock_acquire(&filesys_lock);
if (file_write_at(file_page->file, // mmap된 파일 객체
page->frame->kva, // 페이지의 실제 물리 주소
file_page->read_byte, // 실제로 파일에 기록할 바이트 수
file_page->offset) // 파일 내 시작 위치
!= (off_t)file_page->read_byte)
{
lock_release(&filesys_lock);
return false;
}
lock_release(&filesys_lock);
pml4_set_dirty(curr->pml4, page->va, false);
}dirty_bit가 참이라면, 파일과의 내용 일관성이 꺠진 것이므로 write_back을 진행해준다. 이 작업도 write 작업이니까 lock을 걸고 진행해준다. 이후에 pml4_set_dirty로 일관성이 보장되었다는 것을 dirty-bit로 PTE에 저장한다
page->frame->page = NULL;
page->frame = NULL;마지막으로는 swap_out이 진행되었으므로 프레임과 페이지 간의 연결을 끊어주자.
코드 전문은 더보기에
/* 페이지의 내용을 파일에 기록(writeback)하여 스왑아웃합니다. */
static bool
file_backed_swap_out(struct page *page)
{
// file_page는 file-backed 페이지에 대한 메타데이터를 담고 있는 구조체
struct file_page *file_page UNUSED = &page->file;
/** TODO: dirty bit 확인해서 write back
* pml4_is_dirty를 사용해서 dirty bit를 확인하세요
* write back을 할 때는 aux에 저장된 파일 정보를 사용
* file_write를 사용하면 될 것 같아요
* dirty_bit 초기화 (pml4_set_dirty)
*/
struct thread *curr = thread_current();
bool dirty_bit = pml4_is_dirty(curr->pml4, page->va);
// dirty bit가 true이면, 즉 메모리에서 수정된 경우
if (dirty_bit == true)
{
// 공유 자원 접근 → 락 걸고 접근
lock_acquire(&filesys_lock);
if (file_write_at(file_page->file, // mmap된 파일 객체
page->frame->kva, // 페이지의 실제 물리 주소
file_page->read_byte, // 실제로 파일에 기록할 바이트 수
file_page->offset) // 파일 내 시작 위치
!= (off_t)file_page->read_byte)
{
// write 실패하면 lock 해제 해야겠지?
lock_release(&filesys_lock);
return false;
}
// 파일 쓰기 완료 후 락 해제
lock_release(&filesys_lock);
// 더티 비트 클리어(쓰기 완!)
pml4_set_dirty(curr->pml4, page->va, false);
}
// 초기화는 victim에서
page->frame->page = NULL;
page->frame = NULL;
return true;
}정말 길고 긴 흐름이었다. 훌륭하게 코드를 작성해준 팀원들에게 존경과 감사를 !!
'크래프톤 정글' 카테고리의 다른 글
| [pintOS] 파일 시스템 찍먹하기 (4) | 2025.06.08 |
|---|---|
| [pintOS] Copy-on-write 구현기 (4) | 2025.06.07 |
| [pintOS] mmap 구현기 (0) | 2025.06.05 |
| [pintOS] vm 트러블슈팅 (1) | 2025.06.04 |
| [pintOS] stack_growth 구현기 (0) | 2025.06.03 |