Operating Systems: Three Easy Pieces는 마지막에 실습 과제를 포함하고 있다. 예전에 책을 보기는 했지만 실습을 스킵했더니 놓치는 게 많았던 거 같아서 하나씩 진행해보려고 한다.
과제는 MIT에서 교육용으로 만든 RISC-V OS Xv6를 기반으로 진행된다.
Copy-on-Write란?
Copy-on-Write(CoW)는 메모리 관리 기법 중 하나로, fork() 시점에 실제 메모리 복사를 지연시켜 성능을 향상시키는 방법이다.
전통적인 fork()는 부모 프로세스의 모든 메모리를 즉시 복사하는데, 이는 다음과 같은 문제가 있다:
- 실제로 사용하지 않는 경우에도 메모리 사용량이 두 배로 증가
- 복사 시간이 오래 걸림ㄴ
exec()를 바로 호출하는 경우 복사된 메모리가 낭비됨
CoW는 이 문제를 해결하기 위해 처음에는 메모리를 공유하다가, 실제로 쓰기가 발생할 때만 복사를 수행합니다.
H4 지시 사항
Copy-on-write Mappings
This project adds the ability to perform a lightweight fork(), called vfork(), to xv6. This new call doesn’t simply copy the mappings but rather sets up copy-on-write mappings to shared pages. Upon reference to such a page, the kernel must then create a real copy and update page tables accordingly.
진행한 내용
fork()를 하는 순간에 메모리 내용을 복사하지 않고 물리 메모리를 공유한다.
읽기 요청이 들어왔을 때는 공유하고 있는 물리 메모리에서 읽고, 쓰기 요청이 들어온다면 그때는 메모리 내용을 복사하여 각자의 메모리를 갖도록 한다(기존에 쓰기 가능한 페이지였다면).
다음의 내용을 고려하여 구현을 진행했다.
uvmcopy()에서 부모, 자식 페이지 테이블을 복사할 때 기존에는 물리 메모리 내용도 복사하여 맵핑했지만, 이제는 동일한 물리 주소를 맵핑하도록 한다.- 이 때 write 비트는 0으로 설정해야 충돌이 발생하는 것을 막을 수 있다.
- 기존에 write 비트가 1이었다면? 어딘가에 기존에 쓰기 가능했다는 사실을 기록해야 한다. 여기서는 PTE의 RSW 비트를 사용한다.
- 페이지마다 레퍼런스 카운트를 둬서 카운트가 0이 되면 메모리를 반환해주도록 한다.
- 페이지 갯수만큼의 길이의 배열을 만들어서 관리한다.
- 각 원소는 락과 카운트값을 지니고 있다. 락을 통해 레이스 컨디션을 방지하고자 한다.
copyout()(커널 -> 유저 메모리 복사 함수)에서도 CoW가 일어날 수 있도록 한다.- H3에서 만들었던
mprotect(),munprotect()도 필요한 경우 CoW가 일어날 수 있도록 한다.
uvmcopy() 수정
아래는 H4 이전의 uvmcopy() 코드이다.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
char *mem;
// invalid한 첫 페이지는 제외하고 카피
for(i = USERVASTART; i < sz; i += PGSIZE){
if((pte = walk(old, i, 0)) == 0)
continue; // page table entry hasn't been allocated
if((*pte & PTE_V) == 0)
continue; // physical page hasn't been allocated
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
if((mem = kalloc()) == 0)
goto err;
memmove(mem, (char*)pa, PGSIZE);
if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
kfree(mem);
goto err;
}
}
return 0;
err:
uvmunmap(new, USERVASTART, (i - USERVASTART) / PGSIZE, 1);
return -1;
}
기존에는 무조건 kalloc()을 통해 메모리를 할당하고 복사했다.
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
if((mem = kalloc()) == 0)
goto err;
memmove(mem, (char*)pa, PGSIZE);
if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
kfree(mem);
goto err;
}
대신 새롭게 플래그를 설정한 후(write 비트 0, 기존에 write 비트가 1이었다면 RSW 비트를 1로 설정) 맵핑한다.
flags = PTE_FLAGS(*pte);
if(flags & PTE_W)
flags |= PTE_RSW0; // RSW0 비트로 원래 쓰기 가능했음을 기록
flags &= ~PTE_W; // 쓰기 권한 제거로 페이지 폴트 유발
자식 프로세스의 페이지 테이블에 맵핑하고 참조값을 증가시킨다.
// 자식 프로세스의 페이지 테이블에 매핑한 후,
// 성공하면 참조 카운트 증가
if(mappages(new, va, PGSIZE, pa, flags) != 0)
goto err;
increment_ref((void*)pa); // 참조 카운트를 증가시키는 함수
그 뒤 부모 프로세스의 페이지 테이블도 플래그를 재설정하기 위해 기존 PTE를 unmap하고 다시 맵핑한다.
// 부모 프로세스의 페이지 테이블에서 기존 플래그 버전의 페이지 맵핑 제거
// 자식 프로세스에 먼저 맵핑하여 참조 카운트 증가시킨 후 호출해야,
// 참조 카운트가 0이 되어 물리 메모리가 해제되는 것을 방지할 수 있다.
uvmunmap(old, va, 1, UVMUNMAP_FREE);
// 부모 프로세스의 페이지 테이블에 새 플래그 버전의 페이지 맵핑
if(mappages(old, va, PGSIZE, pa, flags) != 0)
goto err;
increment_ref((void*)pa); // uvmunmap()에서 참조 카운트가 감소되도록 구현해놓았기 때문에 여기서 증가시켜줬다.
페이지별 레퍼런스 카운트 관리
다음과 같이 최대한 적은 곳에서 레퍼런스 카운트를 관리하고자 했다.
increment_ref(void *pa)를 통해 레퍼런스 카운트를 증가시킨다. 이를 호출하는 곳은 두 군데로 제한했다.kalloc()함수에서 free 상태였던 메모리를 유저에게 할당할 때.uvmcopy()함수에서 이미 할당된 메모리를 자식 프로세스가 공유하도록 할 때.
decrement_ref(void *pa)를 통해 레퍼런스 카운트를 감소시킨다. 카운트가 0이 되면 freelist로 메모리를 반환한다.- 기존
kfree()함수에서 메모리를 반환하던 부분을decrement_ref()함수로 대체했다.decrement_ref()함수에서 카운트가 0이 되면 freelist로 메모리를 반환하므로 기존kfree()함수를 호출하지 않아도 메모리를 반환할 수 있다.
- 기존
user_physical_page_ref struct (페이지별 레퍼런스 카운트 관리 구조체)
struct user_physical_page_ref {
uint32 ref;
struct spinlock lock;
};
전역으로 관리되는 레퍼런스 카운트 배열과 관련 매크로
// Total number of physical pages in the system
#define TOTAL_PAGES ((PHYSTOP - KERNBASE) / PGSIZE)
#define PA_TO_INDEX(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)
#define INDEX_TO_PA(idx) (KERNBASE + (idx * PGSIZE))
// Reference count for each physical page
struct user_physical_page_ref user_physical_page_refs[TOTAL_PAGES];
increment_ref() 함수
uint32
increment_ref(void *pa)
{
uint32 ref;
int idx;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("increment_ref");
idx = PA_TO_INDEX(pa);
acquire(&user_physical_page_refs[idx].lock);
ref = user_physical_page_refs[idx].ref++;
release(&user_physical_page_refs[idx].lock);
return ref;
}
decrement_ref() 함수
void
decrement_ref(void *pa)
{
uint32 ref;
int idx;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("decrement_ref");
idx = PA_TO_INDEX(pa);
acquire(&user_physical_page_refs[idx].lock);
if (user_physical_page_refs[idx].ref == 0)
panic("decrement_ref: ref is 0");
ref = --(user_physical_page_refs[idx].ref);
release(&user_physical_page_refs[idx].lock);
if (ref == 0)
kfree(pa);
}
기존 kalloc()함수에 increment_ref() 호출 추가
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r) {
kmem.freelist = r->next;
+ increment_ref(r);
}
...
copyout()에서 CoW 처리
기존에는 PTE의 write 비트가 0이면 오류를 반환했다.
if((*pte & PTE_W) == 0)
return -1;
대신 cow_vmfault()를 추가하여 CoW 페이지에 대한 처리를 하고, CoW가 필요한 게 아니라면 그 때 오류를 반환하도록 했다.
if((*pte & PTE_W) == 0) {
if(cow_vmfault(pagetable, va0) == 0) {
return -1;
}
pte = walk(pagetable, va0, 0); // CoW로 맵핑된 페이지가 있는지 확인
if((*pte & PTE_W) == 0) {
return -1;
}
}
cow_vmfault() 함수는 다음과 같다. valid한 PTE가 존재하고 RSW 비트가 1인 경우에만 기존에 쓰기 가능했던 페이지이므로, 이 경우에만 CoW를 수행한다. (RSW 비트는 0으로 되돌리고 write 비트는 1로 설정하여 복사한다.)
static uint64
cow_vmfault(pagetable_t pagetable, uint64 va)
{
pte_t *pte;
uint64 pa;
uint flags;
struct proc *p = myproc();
void *mem;
if(va < USERVASTART || va >= p->sz)
return 0;
va = PGROUNDDOWN(va);
if((pte = walk(pagetable, va, 0)) == 0)
return 0;
if((*pte & PTE_V) == 0)
return 0;
if((*pte & PTE_RSW0) == 0)
return 0;
pa = PTE2PA(*pte);
flags = (PTE_FLAGS(*pte) & ~PTE_RSW0) | PTE_W;
if((mem = kalloc()) == 0)
return 0;
memmove(mem, (void*)pa, PGSIZE);
uvmunmap(pagetable, va, 1, UVMUNMAP_FREE);
if(mappages(pagetable, va, PGSIZE, (uint64)mem, flags) != 0) {
decrement_ref(mem);
return 0;
}
return (uint64)mem;
}