[Operating System] xv6 Copy on Write (CoW)

운영체제 과제로 진행한 xv6 project4에 대한 설명입니다.
정확하지 않은 내용일 수 있으므로 참고만 하시길 바랍니다.

전체 코드는 아래 링크에서 확인하실 수 있습니다.

https://github.com/LeeHyo-Jeong/HYU-ELE3021

[Design]

Virtual memory

기존의 메모리 관리 기법은 프로세스가 실행되려면 프로세스의 전체 address space를 메모리에 로드해야 했다.
그러나 프로세스의 address space에는 프로그램을 실행하는 동안 실행되지 않을 부분이 존재하며,
배열이나 테이블과 같은 자료구조들은 실제로 필요한 양보다 더 많은 양의 메모리를 할당 받는다.
이러한 상황들을 보았을 때 CPU가 참조하는 영역은 매우 제한적이며, 프로세스의 모든 부분이 항상 동시에 필요하지는 않다는 것을 알 수 있다.
따라서 Virtual memory가 도입되었다.

Virtual memory란, 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안된 메모리 기법이다.
실제 메모리에는 프로세스의 address space 중 CPU가 접근하는 부분만 올리고, 현재 접근 되지 않는 부분은 올리지 않는다.
프로세스와 CPU는 logical address space만 알고 있고, OS가 virtual memory 기법을 통해 프로그램의 logical address space에서 필요한 부분만 physical addres space에 적재하고 직접적으로 필요하지 않은 부분은 디스크에 저장하게 된다.
따라서 프로세스의 logical address space와 physical address space가 분리된다.

Copy on Write

Virtual memory의 장점 중 하나는 프로세스 생성이 매우 효율적으로 일어난다는 점이다.
기존의 fork는 자식 프로세스가 부모 프로세스의 address space를 생성해야 했다. 이러면 메모리에 두 프로세스의 내용이 같은 address space가 중복으로 올라가게 되어 공간을 낭비하게 되고, memory copy가 일어나므로 매우 느리다.
그러나 virtual memory를 사용하면 이 문제를 해결할 수 있게 된다.
fork 호출 시 부모 프로세스의 address space를 복사하는 것이 아니라 page table을 복사한다. 그러면 두 프로세스의 page table이 같은 physical address를 가리키게 된다. 따라서 부모와 자식 프로세스의 각 logical address space에서는 서로 자신만의 독립적인 address space가 있는 것처럼 보이지만, 실제로는 메모리에 올라가있는 부모 프로세스의 read only로 설정한 후 그 address space를 자식 프로세스가 공유하게 된다.

이후 부모 또는 자식 프로세스에서 memory에 write할 때 바로 page table이 가리키는 physical address에 write하게 되면 한 프로세스에서 바꾼 값이 다른 프로세스에서도 반영이 되므로 문제가 생긴다. 따라서 Copy on Write이 도입되었다.

Copy on Write란 부모 또는 자식 프로세스가 공유된 페이지에 write를 시도할 때 그 페이지의 복사본을 만들어 그 곳에다 값을 쓰게 하도록 하는 메커니즘이다. CoW의 자세한 과정은 다음과 같다.

• 공유 페이지에 write를 시도하면 page fault가 발생한다.
• page fault handler는 공유 페이지의 복사본을 만들어 메모리에 할당한다.
• 새롭게 복사한 페이지에 write한다.
• write를 시도한 프로세스의 page table entry를 업데이트 하여 새로운 페이지를 가리키도록 한다.

프로세스들이 페이지를 공유하는 상황

 

페이지 C에 write 하기 위해 C의 copy를 생성한 후 copy된 페이지에 write

 

[Implement]

Macro

PGSHIFT

mmu.h에 다음과 같이 정의했다.

#define PGSHIFT 12

xv6에서 한 페이지의 크기는 4KB = 2^12 byte 이므로 PGSHIFT 값을 12로 정의했다.

Variables

pageref

kalloc.c에 페이지 참조 횟수를 나타내는 전역변수 pageref 배열을 선언하였다.

int pageref[PHYSTOP >> PGSHIFT];

PHYSTOP은 최대로 사용 가능한 물리 메모리의 끝 주소를 나타낸다.
이전에 언급했듯, xv6에서 한 페이지의 크기는 4KB이므로
PHYSTOP >> PGSHIFT, 즉 PHYSTOP / PGSHIFT = 전체 사용 가능한 페이지 개수를 나타낸다.

pageref의 각 element는 해당 페이지를 가상 주소 공간에 매핑한 프로세스의 수 (페이지 참조 횟수)를 나타낸다.
페이지 참조 횟수는 free page가 어떤 프로세스에 의해 할당될 때 1로 설정되고, 추가 프로세스가 이미 존재하는 페이지를 가리킬 때 참조 횟수가 증가한다.
프로세스가 더 이상 페이지를 가리키지 않아 pageref가 0이 되었을 때만 페이지를 free할 수 있다.

fp

kalloc.c에 free page의 개수를 나타내는 fp 변수를 선언하였다.
처음에는 시스템에 존재하는 free page가 없으므로 fp의 초깃값은 0이다.

int fp = 0;

Functions

freerange

freerange 함수는 physical memory의 특정 범위를 초기화 하여 free list에 추가하는 역할을 한다.
freerange는 시스템 초기화 시점에 호출되어 physical memory를 관리할 수 있도록 한다.

void
freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE){
    pageref[V2P(p) >> PGSHIFT] = 0;
    kfree(p);
  }
}

p는 vstart를 페이지 경계로 반올림 처리해서 얻어진 커널 가상 주소이다.
V2P 매크로를 이용해 커널 가상 주소를 물리 주소로 변환한 후 PGSHIFT만큼 right shift해서 페이지 번호로 변환한다.
얻어진 번호에 해당하는 페이지의 참조 횟수를 0으로 초기화하고 kfree 함수를 호출해 free list에 추가한다.

kfree

kfree 함수는 사용되지 않는 페이지를 free list에 반환하는 함수이다.

void kfree(char *v)
{
  ...

  if(pageref[V2P(v) >> PGSHIFT] > 0)
    pageref[V2P(v) >> PGSHIFT]--;

  if(pageref[V2P(v) >> PGSHIFT] == 0){
    memset(v, 1, PGSIZE);

    r = (struct run*)v;
    r->next = kmem.freelist;
    kmem.freelist = r;

    fp++;
  }
  ...
}

현재 시스템에서는 Copy on Write를 사용하므로 kfree가 호출되었다고 해서 바로 페이지를 해제하면 안 된다.
해당 페이지에 대한 reference count를 1만큼 줄인 다음 그 값이 0이 되면 페이지를 참조하는 프로세스가 없다는 뜻이므로 해제한다.
만약 그 페이지가 해제되었다면 시스템에 free page의 개수가 하나 늘어난 것이므로 fp를 1 증가시킨다.

kalloc

kalloc 함수는 free list에서 사용 가능한 페이지를 새로운 페이지를 요청한 프로세스나 커널에 메모리 페이지를 할당한다.
할당 후 free page의 개수가 줄어드므로 fp를 1 감소시킨다.

copyuvm

copyuvm 함수는 가상 메모리 공간을 복사하는 역할을 한다.
기존의 copyuvm 함수는 fork 내부에서 호출되어 부모 프로세스의 테이블 내용을 복사한 후 새 물리 페이지를 할당하여 부모 프로세스의 내용을 그대로 복사한 후 새로 생성한 물리페이지의 주소를 자식 프로세스의 가상 주소와 매핑한다.

그러나 CoW를 구현하기 위해 페이지를 read only로 바꾸어서 그 페이지를 공유하고 있는 프로세스 중 하나가 write를 시도했을 때 page fault를 발생 시켜 page를 복사한 후 복사된 페이지에 write를 할 수 있도록 한다.

    pa = PTE_ADDR(*pte);
    *pte &= (~PTE_W);
    flags = PTE_FLAGS(*pte);

새롭게 메모리를 할당하지 않고 부모와 동일한 페이지를 참조하도록 해야 한다.

    // share pages, do not copy
    if(mappages(d, (void*)i, PGSIZE, pa, flags) < 0) goto bad;

이후 그 페이지에 대한 reference가 증가했으므로 reference count를 1 증가시킨다.

    incr_refc(pa);

페이지 테이블 엔트리를 읽기 전용으로 변경하였으므로 페이지 테이블 엔트리를 캐시하는 TLB를 flush하여 최신 상태로 업데이트 해주어야 한다.

  lcr3(V2P(pgdir));
  return d;

incr_refc

주어진 페이지의 참조 횟수를 1 증가 시킨다.
참조 횟수는 여러 프로세스에서 동시에 접근할 수 있는 공유 자원이므로 참조 횟수를 증가시키는 것은 atomic하게 이루어져야 한다.
따라서 메모리 할당과 관련된 상태를 관리하는 kmem 구조체에 포함되어 있는 kmem.lock을 이용해 동기화 해준다.

void incr_refc(uint pa){
        acquire(&kmem.lock);
        pageref[pa >> PGSHIFT]++;
        release(&kmem.lock);
}

decr_refc

주어진 페이지의 참조 횟수를 1 감소 시킨다.
incr_refc 함수에서와 같은 이유로 kmem.lock을 이용해 동기화 해준다.

void decr_refc(uint pa){
        acquire(&kmem.lock);
        pageref[pa >> PGSHIFT]--;
        release(&kmem.lock);
}

get_refc

주어진 페이지의 참조 횟수를 반환한다.
공유 자원에 대한 접근이므로 kmem.lock을 이용해 동기화 한다.

int get_refc(uint pa){
        acquire(&kmem.lock);
        int ref = pageref[pa >> PGSHIFT];
        release(&kmem.lock);
        return ref;
}

CoW_handler

여러 프로세스에서 공유하고 있는 페이지는 read only이므로 그 페이지에 값을 쓰려고 하면 page fault가 발생한다.
page fault가 발생할 시 page fault handler인 CoW_handler 함수가 호출된다.

void trap(struct trapframe *tf)
{
        ...
        switch(tf->trapno){
                ...
                case T_PGFLT: // page fault handler
                        CoW_handler();
                        break;
        }
        ...
}

countfp

countfp 함수는 시스템에 존재하는 free page의 총 개수를 반환하는 시스템 콜이다.
전역 변수로 선언한 fp 변수를 리턴한다.
공유 변수에 대한 접근이므로 동기화 해준다.

int countfp(){
        acquire(&kmem.lock);
        int ref = fp;
        release(&kmem.lock);
        return ref;
}

countvp

countvp는 현재 프로세스의 user memory에 할당된 가상 페이지의 수를 반환하는 시스템 콜이다.
가상 주소 0부터 프로세스의 가상 주소 공간 크기까지의 가상 페이지 수를 세어야 한다.
커널 주소에 매핑된 페이지는 포함하지 않는다.

countpp

countpp는 현재 프로세스의 페이지 테이블을 탐색하고, 유효한 물리 주소가 할당된 page table entry의 수를 반환한다.
xv6에서는 demand paging을 사용하지 않으므로, countvp()의 결과와 동일해야 한다.

xv6는 2-level page table의 구조를 갖는다. outer table인 page directory은 inner table인 page table들의 시작 주소를 entry로 갖는다.
유효한 물리 주소가 할당된 page table entry의 수를 찾기 위해 inner page table에서 유효한 page의 수를 세야한다.
따라서 2중 loop를 돈다.

• Outer loop: page directory entry가 유효한지 확인한다.

        for(int i = 0 ; i < NPDENTRIES ; i++){
                if(pgdir[i] & PTE_P){

• Inner loop: page table entry가 유효한지 확인한다.

                        pte_t *pgtab = (pte_t*)P2V(PTE_ADDR(pgdir[i]));
                        for(int j = 0 ; j < NPTENTRIES ; j++){
                                if(pgtab[j] & PTE_P){

  두 조건을 모두 통과한다면 유효한 물리 주소가 할당된 page table entryd이므로 count를 1 증가시킨다.

countptp

프로세스의 페이지 테이블을 위해 할당된 페이지의 수를 반환한다.
페이지 테이블과 페이지 디렉토리 저장을 위해 사용된 페이지를 센다.
user level의 PTE mapping을 저장하는 페이지 테이블 뿐 아니라 커널 페이지 테이블 매핑을 저장하는 페이지 테이블도 포함되어야 한다.

page directory를 순회하며 page table을 위해 page directory entry가 할당되었다면 count를 1 증가시킨다.

        for(int i = 0 ; i < NPDENTRIES ; i++){
                if(pgdir[i] & PTE_P){
                        cnt++;
                }
        }

page directory(4KB)를 저장하기 위해 하나의 페이지가 사용되었을 것이므로 1만큼 증가시킨 값을 리턴한다.

        return ++cnt;

[Trouble Shooting]

xv6가 실행되지 않음

쉘을 실행했을 때 xv6가 실행되지 않고 무한 부팅이 걸렸었다.
kalloc.c서 처음 countvp를 구현할 때 virtual page의 개수를 프로세스 구조체 내에 저장해서 그 값을 리턴하려 했다.
그러나 vm.c에는 proc.h 헤더 파일이 include 되어있지 않아 myproc() 함수를 사용할 수 없어서 현재 프로세스를 얻을 수 없었기 때문에 proc.h 헤더 파일을 include 한 후 사용하였다. 그랬더니 xv6 자체가 실행 되지 않았다. 따라서 countvp 함수를 proc.h 헤더파일이 포함되어 있는 vm.c에서 구현해주었더니 해결되었다.

매우 큰 countpp의 값

커널 주소에 매핑된 페이지까지 세주어서 countpp의 리턴값이 매우 컸다.

uint va = (i << PDXSHIFT) | (j << PTXSHIFT);
if(va < KERNBASE) ref++;

KERNBASE는 커널이 시작하는 가상 주소의 기준점이다. xv6에서 KERNBASE는 0X80000000이다.
가상 주소가 KERNBASE보다 작으면 프로세스의 address space이고, KERNBASE보다 크면 kernel space이다.
따라서 해당 조건을 추가해 프로세스의 virtual address space에 매핑된 페이지만 셀 수 있도록 하여 해결하였다.

[Result]

Test0

시스템 콜 countfp, countvp, countpp, countptp을 사용하여 현재 프로세스의 페이지 정보를 확인한다.
sbrk(4096)을 호출하여 추가적인 페이지가 알맞게 할당되었는지 확인한다.

Test1

fork 시스템 콜을 통해 자식 프로세스를 생성한다.
자식 프로세스와 부모 프로세스가 같은 물리 페이지를 가리키고 있는지 페이지 개수의 차이를 통해 확인한다.

Test2

fork 시스템 콜을 통해 자식 프로세스를 생성한다.
자식 프로세스가 부모 프로세스와 공유하고 있는 변수를 수정하여 새로운 물리 페이지를 할당 받는지 확인한다.
즉, Copy on Write가 제대로 일어나고 있는지 확인한다.

Test3

fork 시스템 콜을 통해 자식 프로세스를 생성한다.
10개의 자식 프로세스를 생성하고, 각각의 자식 프로세스는 Test2와 유사하게 부모 프로세스와 공유하는 변수를 수정한다.
자식 프로세스의 종료 이후 free page의 적절한 회수가 이루어졌는지 확인한다.

모든 테스트를 정상적으로 통과하였다.