(2022.02.16) System Calls 구현 (4/4)

1. 서론 및 필요 내용 설명

4번째 포스팅까지 할 줄은 몰랐다. 그것도 디버깅만으로 분량 절반을 채우면서. 이제 multi-oom (out of memory의 약자)를 깨보자. 이름에서 대충 감이 오겠지만 해당 프로그램은 메모리를 쳐먹는 용도로 구성이 된 프로그램이다. 메모리가 부족한 상황을 만들고, 메모리가 한계점에 다다르면 모든 메모리를 커널이 회수했다가 다시 메모리를 소비하는 방식으로 구성이 된다.

 

코드 레벨에서 좀 더 자세히 살펴보자. main은 다음과 같이 구성되어 있는데,

int
main (int argc UNUSED, char *argv[] UNUSED) {
  msg ("begin");

  int first_run_depth = make_children ();
  CHECK (first_run_depth >= EXPECTED_DEPTH_TO_PASS, "Spawned at least %d children.", EXPECTED_DEPTH_TO_PASS);

  for (int i = 0; i < EXPECTED_REPETITIONS; i++) {
    int current_run_depth = make_children();
    if (current_run_depth < first_run_depth) {
      fail ("should have forked at least %d times, but %d times forked", 
              first_run_depth, current_run_depth);
    }
  }

  msg ("success. Program forked %d iterations.", EXPECTED_REPETITIONS);
  msg ("end");
}

make_children을 1세트로 해서, 총 EXPECTED_REPETITIONS(설정된 값은 10)만큼의 세트만큼 반복을 시킨다. make_children의 반환값이 가장 처음 실행했던 값보다 떨어지면 안 된다는 것은 메모리 누수가 생겨 자식 생성이 이전만큼 되지 않는가를 검사하는 것이다. 메모리 누수란 malloc을 해놓고 반환을 안하는 경우 등 사소한 경우에도 발생할 수 있는 만큼 코드 전반에 걸쳐 주의가 필요하다. 그럼 make_children은 어떻게 반환값을 산정하는 것일까? 실제로 코드를 보면 아래와 같으며,

int
make_children (void) {
  int i = 0;
  int pid;
  char child_name[128];
  for (; ; random_init (i), i++) {
    if (i > EXPECTED_DEPTH_TO_PASS/2) {
      snprintf (child_name, sizeof child_name, "%s_%d_%s", "child", i, "X");
      pid = fork(child_name);
      if (pid > 0 && wait (pid) != -1) {
        fail ("crashed child should return -1.");
      } else if (pid == 0) {
        consume_some_resources_and_die();
        fail ("Unreachable");
      }
    }

    snprintf (child_name, sizeof child_name, "%s_%d_%s", "child", i, "O");
    pid = fork(child_name);
    if (pid < 0) {
      exit (i);
    } else if (pid == 0) {
      consume_some_resources();
    } else {
      break;
    }
  }

  int depth = wait (pid);
  if (depth < 0)
	  fail ("Should return > 0.");

  if (i == 0)
	  return depth;
  else
	  exit (depth);
}

자식이 생성되는 방식을 도식으로 정리하면 아래 그림과 같다.

 

각 노드는 프로세스이며, edge로 연결된 프로세스는 부모-자식 관계를 의미한다. 끝에 X가 붙는 프로세스는 모두 consume_some_resource_and_die라는 자명한 이름을 갖고 있는 함수를 실행하고 비정상 종료하게 되고, 끝에 O가 붙는 프로세스는 다음 자식(들)을 생산하는 역할과 함께 consume_some_resource를 실행한다. 이런 식으로 타고 들어가다보면 메모리 상의 문제로 인해 child_n_O가 생성이 불가한 경우가 온다. 그 때 해당 n을 받아서 initial_process까지 올리는 것이 해당 코드이며, 그런 과정 속에 모든 자식 프로세스들은 종료된다.

 

지금까지 multi-oom의 실행 과정을 살펴보았고 이제 실행을 시키면서 문제가 되는 부분을 찾자.

 

---

2. 디버깅

실행을 시켜본 뒤에 깨달은 것은 자식이 생각보다 많이 생성된다는 것이었다. 각 실행에서 46단계까지 치고 내려간다. 문제는 각 실행에 있어 시간을 너무 많이 잡아 먹는다는 것이다. 600초 제한 시간동안 첫 번째 실행을 제외하고 10번 세트 실행 중 단 5번 밖에 끝내질 못한다. 실제로 지금까지 fail한 이유를 살펴보면 전부 TIMEOUT이었다.

 

시간을 무작정 늘려도 인정이 될지는 불분명하기에 최적화가 필요한 시점이라고 생각했다. 가장 느려질만한 구간의 코드를 최적화한다면 600초 안에는 통과할 수 있을 것이다. 그렇게 생각하고 계속 돌려보다가 흥미로운 양상을 발견했다. 각 세트에서 처음에는 자식의 생성 및 종료가 빠른 느낌인데, 아래로 내려갈수록 느려지는 것 같았다.

 

이러한 양상을 보인 것은 아마 open 때문일 것이다. open에서는 fd_allocate를 위해 비어있는 fd를 탐색하는데, 탐색하는 과정에서 정렬을 사용하도록 코드가 구현되어있다. 정렬에 소모되는 시간 복잡도가 nlog(n)이지만 fork를 통해 계속 대물림되는 fd_list를 생각할 때 이를 정렬하는 것은 무시할 수 없을 정도의 시간 소모를 낳을 것이라 생각했다.

 

또다른 가능성을 생각한다면 fork에서 파일들을 복사 할 때 list_insert_ordered를 사용하면서 시간 낭비가 발생하는 것이다. 해당 함수는 주어진 인자를 리스트의 처음부터 비교하면서 리스트의 위치를 찾는데, 지금 방식으로는 주어진 인자가 항상 마지막에 위치하게 되므로 비효율적인 것이다. 항상 정렬 상태를 유지한다면 해당 코드도 list_push_back으로 바꿔주도록 한다.

 

또 한 가지 의심했던 부분은 process를 종료하면서 nowait_terminate가 호출될 때 모든 프로세스를 순회할 때 발생하는 시간이었다. 그러나 많아봤자 100개를 넘지 않는 thread를 순회하는 것이기에 시간 소모가 크지 않을 것이며, 해당 가능성은 적을 것이다.

 

해결 방법을 찾는 뻘짓을 거쳐...

 

1. 우선 되도록 자료구조는 건들이지 않고 해결해보려고 했다. list_sort를 제외하고 fd_list가 항상 정렬 상태에 있을 수 있도록 넣을 때 list_insert_ordered를 활용한다. 다시 실행해보았다. 여전히 느리다.
2. multi_oom는 open을 지속적으로 부를 때 빈 fd가 존재하지 않는다. 때문에 현재 방식으로는 0부터 빈 fd를 탐색하기 때문에 fd_list 전체를 강제로 순회하게 된다. 마지막에 open한 fd를 기억한다면 거기서부터 탐색을 하면 된다.
3. 위의 방식대로 할 경우 일반적인 프로세스에서 마지막으로 open을 하고 현재 open을 하기 전에 몇 개의 fd가 close로 할당이 해제됐을 가능성도 있다. 이 경우, 할당 해제해준 fd를 따로 관리할 리스트를 만들어 fd 순서대로 넣어둔다. (free_fd_list) 이 리스트가 비어있을 때는 마지막으로 open해준 fd에서 1 증가시켜서 할당하며, 비어있지 않을 때는 해당 리스트에서 꺼내서 fd를 할당한다.

해당 방식을 구현해보자. 이 방식으로도 안된다면 다른 자료구조를 생각할 수 밖에 없다. free_fd_list는 단순 integer를 엮은 리스트로 구현하고, 파일이 close가 되면 해당 리스트에 엔트리를 만들어 넣는다. 파일을 open할 때 해당 엔트리를 사용하면 자원을 반환한다. 프로세스 종료시에는 각 엔트리의 자원을 모두 반환한다.

int fd_allocate (struct file *fp)
{
	struct list_elem *e;
	struct free_fildes *ffd;
	struct fildes *fd_entry;
	struct thread *curr = thread_current();

	int fd;

	if (list_empty(&curr->free_fd_list))
	{
		fd = curr->last_allocated + 1;
		curr->last_allocated += 1;
	}

	else 
	{
		e = list_pop_front(&curr->free_fd_list);
		ffd = list_entry(e, struct free_fildes, ffd_elem);
		fd = ffd->fd;
		free(ffd);
	}

	fd_entry = (struct fildes *)malloc(sizeof(struct fildes));
	fd_entry->fd = fd;
	fd_entry->fp = fp;
	list_insert_ordered(&curr->fd_list, &fd_entry->fd_elem, cmp_fd, NULL);
	
	return fd;
}

void _close(int fd)
{
	filesys_enter();

	struct fildes *fd_entry = fd_search(fd);
	struct free_fildes *ffd;
	struct file *fp;

	if (fd_entry == NULL) // not valid fd
		goto close_done;

	list_remove (&fd_entry->fd_elem);
	fp = fd_entry->fp;
	free (fd_entry); // always free what you malloc-ed;

	ffd = (struct free_fildes *) malloc (sizeof(struct free_fildes));
	ffd->fd = fd;
	list_insert_ordered(&thread_current()->free_fd_list, &ffd->ffd_elem, cmp_fd, NULL);

	if (fp != 0 && fp != 1)
		file_close (fp);

close_done:
	filesys_exit();
}

또한 해당 사항에 맞춰 __do_fork와 process_exit도 바꿔야 한다.

void
process_exit (void) {
	...
	while (!list_empty (&curr->free_fd_list))
	{
		e = list_pop_front (&curr->free_fd_list);
		struct free_fildes *ffd = list_entry (e, struct free_fildes, ffd_elem);
		free (ffd);
	}
	...
}

static void
__do_fork (void *aux) {
	...
	filesys_enter();

	current->last_allocated = parent->last_allocated;

	/* copy free fd list */
	for (e = list_begin(&parent->free_fd_list); e != list_end(&parent->free_fd_list); e = list_next(e))
	{
		ffd = list_entry(e, struct free_fildes, ffd_elem);
		ffd_copy = (struct free_fildes *)malloc(sizeof(struct free_fildes));
		if (ffd_copy == NULL) 
		{
			succ = false;
			goto file_copy_done;
		}
		ffd_copy->fd = ffd->fd;
		list_push_back(&current->free_fd_list, &ffd_copy->ffd_elem);
	}
	...
}

해당 사항들을 모두 수정하고 다시 돌려보았다. 속도가 확실히 빨라졌다. 이제 10번의 루프를 도는데 성공한다. 나머지 테스트 케이스들을 전부 돌려본다. 드디어 all pass다. 하....

pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
pass tests/userprog/read-bad-ptr
pass tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
pass tests/userprog/read-bad-fd
pass tests/userprog/write-normal
pass tests/userprog/write-bad-ptr
pass tests/userprog/write-boundary
pass tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
pass tests/userprog/fork-once
pass tests/userprog/fork-multiple
pass tests/userprog/fork-recursive
pass tests/userprog/fork-read
pass tests/userprog/fork-close
pass tests/userprog/fork-boundary
pass tests/userprog/exec-once
pass tests/userprog/exec-arg
pass tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
pass tests/userprog/exec-read
pass tests/userprog/wait-simple
pass tests/userprog/wait-twice
pass tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
pass tests/userprog/multi-recurse
pass tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
pass tests/userprog/rox-child
pass tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
pass tests/userprog/bad-read2
pass tests/userprog/bad-write2
pass tests/userprog/bad-jump
pass tests/userprog/bad-jump2
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
pass tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
pass tests/filesys/base/syn-write
pass tests/userprog/no-vm/multi-oom
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
All 95 tests passed.

인간적으로 너무 많은 거 아닙니까? 

 

근데 놀라운 건 아!직!도! 안 끝났다. Extra 프로젝트 하러 가야지... 이건 다음 포스팅에 가이드라인과 함께 살펴보겠다.

 

---

3. 후기

그래도 multi-oom를 최적화 이슈 때문에 실패하고 있던거면 싸게 먹힌거다. 이제 대망의 dup2를 영접할 차례이다.