XV6 운영체제 개선해 보기 <swapin, swapout 구현하기>

Home Post About

2023.09.06.

해당 포스트는 MIT의 교육용 운영체제 XV6를 활용하며, 코드 저작권은 MIT에 있음을 밝힙니다.

목표

FS swapin, swapout 구현하기

과정

0. types.h 수정

...(생략)
typedef uint pte_t;

kalloc()의 새로운 함수들에서 사용하게 되는 walkpgdir() 등을 위해 pte_t 자료형을 추가해준다.

1. defs.h 수정

...(생략)
void            manage_pages(int, pde_t*, char*);
pte_t *         walkpgdir(pde_t *pgdir, const void *va, int alloc);

vm.c 에서 kalloc.c에 있는 새로운 함수 manage_pages()와 기존의 walkpgdir를 호출할 수 있도록 만들어준다.

2. mmu.h 수정

...(생략)
#define PTE_A           0x020

PTE_A를 추가해주었다.

3. vm.c 수정

pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{

기존의 static을 없애서 다른 곳에서도 쓸 수 있도록 하였다.

static int
mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
...(생략)

    if ((*pte & PTE_U)) {
      manage_pages(1, pgdir, (char*)a);
    }

...(생략)
  return 0;
}

기존의 mappages를 할때 그 사이에 page를 관리하는 직접 만든 함수 manage_pages()를 추가하였다. 여기서 첫번째 인자 1은 더하기 동작을 지시하는 인자이다. 나머지 두 인자는 pgdir와 가상주소를 전달한다.

int
deallocuvm(pde_t *pgdir, uint oldsz, uint newsz)
{
 ...(생략)      
manage_pages(0, pgdir, (char*)a);
...(생략)
  return newsz;
}

deallocuvm()에서 메모리를 해제할때 manage_pages()함수를 추가하였다. 첫번째 인자 0은 제거하는 동작을 지시하는 인자이다. 나머지 두 인자는 pgdir와 가상주소를 전달한다.

4. kalloc.c 수정

char*
kalloc(void)
{
  struct run *r;

try_again:
  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = kmem.freelist;
  
  if(!r){
    if(kmem.use_lock) release(&kmem.lock);
    if(reclaim()) {
      goto try_again;
    }
    else{
      cprintf("error: OOM!\n");
      return 0;
    }
    if(kmem.use_lock) acquire(&kmem.lock);
  }

  if(r)
    kmem.freelist = r->next;
  if(kmem.use_lock)
    release(&kmem.lock);
  return (char*)r;
}

우선 기존의 코드에서는 r = kmem.freelist 가 발생했을시 오류가 생겼지만. 이 경우에는 우선 reclaim()을 시도해본다. 여기서 성공으로인해 1이 리턴될 경우 tryagain으로 돌아가서 해제된 메모리를 다시 받을 수 있도록 한다. 만약 0이 리턴될 경우 실패(더이상 LRU에 공간이 없음)로, error: OOM! 메세지를 호출한다.

int find_free_page(){
  int i;
  for (i=0;i<PHYSTOP/PGSIZE;i++){
    if(pages[i].vaddr == 0 && pages[i].pgdir == 0){
      break;
    }
  }
  if (i==PHYSTOP/PGSIZE){
    return -1;
  }
  return i;
}

위의 함수는 현재 pages 중에서 비어있는 page를 찾아 인덱스를 리턴한다. 없을경우, -1을 리턴한다.

int find_page(pde_t* pgdir, char* va){
  int i;
  for (i=0;i<PHYSTOP/PGSIZE;i++){
    if(pages[i].pgdir == pgdir && pages[i].vaddr == va){
      break;
    }
  }
  if (i==PHYSTOP/PGSIZE){
    return -1;
  }
  return i;
}

위의 함수는 현재 pages 중에서 인자로 전달된 pgdir과 va를 가지는 페이지의 인덱스를 리턴한다. 없을경우, -1을 리턴한다.

void manage_pages(int ope, pde_t* pgdir, char* va){
  if (ope == 1){ // add ------------------------------------------

    int idx = find_free_page();
    if (idx == -1) return;
    struct page* tmp = &pages[idx];
    
    if(num_lru_pages == 0){// first add
      page_lru_head = tmp;
      tmp->vaddr = va;
      tmp->pgdir = pgdir;
      tmp->prev = page_lru_head;
      tmp->next = page_lru_head;
    }
    else{
      //print_lru();
      tmp->vaddr = va;
      tmp->pgdir = pgdir;

      struct page* cur = page_lru_head;
      while(cur->next != page_lru_head){
        cur = cur->next;
      }

      tmp->next = page_lru_head;
      page_lru_head->prev = tmp;

      tmp->prev = cur;
      cur->next = tmp;

    }
    num_lru_pages++;
    num_free_pages--;
  }

  if (ope == 0){ // remove --------------------------------------------------
    //cprintf("remove %x %x\n", pgdir, va);
    int idx = find_page(pgdir, va);
    if (idx == -1) return;
    struct page* tmp = &pages[idx];
    //cprintf("temp %x %x %x\n", tmp, tmp->pgdir, tmp->vaddr);
    if (!tmp) {
      //cprintf("tmp is zero\n");
      return;
    }
    //cprintf("tmp is not zero\n");
    if (num_lru_pages == 1){
      tmp->vaddr = 0;
      tmp->pgdir = 0;
      tmp->prev = 0;
      tmp->next = 0;
      page_lru_head = 0;
    }
    else{
      struct page* prev_tmp = tmp->prev;
      struct page* next_tmp = tmp->next;
      prev_tmp->next = next_tmp;
      next_tmp->prev = prev_tmp;

      if (tmp == page_lru_head){
        page_lru_head = page_lru_head->next;
      }

      tmp->vaddr = 0;
      tmp->pgdir = 0;
      tmp->prev = 0;
      tmp->next = 0;
    }
  }
  //print_lru();
}

위의 함수는 deallocuvm(), manage_pages() 등에서 호출하여, LRU와 FREE PAGE를 관리하는 코드이다. 우선 페이지가 새로 생기는 경우, 최로 LRU에 추가되는 상황이라면 비어있는 페이지 중에서 가장 앞에 있는 것을 찾은다음 pgdir과 va를 채워주고 page_lru_head 로 만든다. 그 다음부터 추가 될 경우 page_lru_head의 직전에 tail로 추가하게 된다. 물론 이때 prev와 next를 새롭게 연결해주게 된다. 다음으로 기존의 페이지가 해제되는 경우, 해당하는 페이지를 우선 pages에 찾은다음 LRU에서 제거하게 된다. 여기서 LRU의 prev 와 next등을 재연결 해주고, 삭제한 페이지는 vaddr, pgdir, prev, next 값등을 0으로 만든다. 만약 head가 사라지게 될 경우에는 head 포인터를 다음으로 넘겨준다.

int reclaim(){
  //cprintf("\nreclaim().... now head is : pgdir: %x pgaddr: %x --------------------- \n", page_lru_head->pgdir, page_lru_head->vaddr);
  if(num_lru_pages == 0){
    return 0;
  }
  //print_lru();

  int find = 0;
  pte_t* pte;
  char* va;
  pde_t* pgdir;

  while(!find){

    va = page_lru_head->vaddr;
    pgdir = page_lru_head->pgdir;
    pte = walkpgdir(pgdir, va, 0);

    if(*pte & PTE_A) { // 한번 넘어감
      //cprintf("pgdir: %x pgaddr: %x is PTE_A ok .. pass\n", page_lru_head->pgdir, page_lru_head->vaddr);
      *pte = ((*pte) & (~PTE_A));
      page_lru_head = page_lru_head->next;
    }
    else{
      //cprintf("pgdir: %x pgaddr: %x is PTE_A not ok .. find!\n", page_lru_head->pgdir, page_lru_head->vaddr);
      find = 1;
    }
  }

  //evict 시작
  num_lru_pages--;
  num_free_pages++;

  struct page* old_head = page_lru_head;
  struct page* prev_head = page_lru_head->prev;
  page_lru_head = page_lru_head->next;

  prev_head->next = page_lru_head;
  page_lru_head->prev = prev_head;

  pte = walkpgdir(old_head->pgdir, old_head->vaddr, 0);
  //cprintf("old_head->pgdir: %x old_head->vaddr: %x\n",old_head->pgdir,old_head->vaddr);

  uint pa = PTE_ADDR(*pte);
  int offset = find_free_offset();
  bitmap[offset] = 1;
  //cprintf("offset: %x P2V(pa): %x\n",offset,P2V(pa));
  swapwrite((char*)P2V(pa), offset);
  kfree(P2V(pa));
  //cprintf("\npte=%x\n", *pte);

  *pte = ((*pte) & (~PTE_P));
  *pte = (*pte & 0xfff) | (offset << 12);

  //cprintf("\npte=%x\n", *pte);
  old_head->vaddr = 0;
  old_head->pgdir = 0;
  old_head->prev = 0;
  old_head->next = 0;
  //print_lru();
  return 1;
}

reclaim() 함수에서는 kalloc에서 페이지가 모자랄때 여러 페이지 중 하나를 골라서 free한다. 여기서 evict 될 페이지는 LRU와 clock 알고리즘을 활용한다. 우선 num_lru_pages == 0 인 경우는 더이상 free가 불가능한 경우이므로 0을 리턴한다. 만약 LRU에 가능한 페이지들이 존재할 경우, page_lru_head 부터 순회하면서 *pte & PTE_A를 확인한다. 만약 PTE_A가 설정되어 있는 경우 *pte = ((*pte) & (~PTE_A)) 를 통해서 PTE_A를 없애주고 다음 페이지로 head를 넘기며 탐색한다. 만약 PTE_A가 설정되어있지 않으면 해당 page를 evict 대상으로 선정하고 LRU에서 제거해 주는 과정을 거친다. 또한, bitmap을 설정해주고 swapwrite() 함수를 통해 해당 page를 스왑영역 블록에다가 쓰게 된다. 이때, *pte = ((*pte) & (~PTE_P)) 를 통해 PTE_P flag를 설정해주고 offset 까지 저장해준다.

5. trap.c 수정

trap.c의 경우에는, case T_PGFLT: 의 경우에 대하여 swapin기능을 구현한다. 여기서 rcr2()를 활용하며, PGFLT가 난 pte에 대하여 해당 page가 만약 swapwrite()를 통해 swapout 된 상황인지 판단하게된다. 만약 실제로 swapout이 된 경우라면, 기존에 저장했던 offset, PTE_P 등을 활용하여 읽어 들여야 하는 블록의 정보를 찾고 swapread()를 통해 읽어오게 된다.

Source

mit-pdos/xv6-public
https://github.com/mit-pdos/xv6-public

목표
- FS swapin, swapout 구현하기
과정
Source