(2022.02.17) Extend File Descriptor 구현 (1/3)

1. 서론 및 필요 내용 설명

일단 지금은 지난 번에 설명한대로 fd_allocate를 재수정해야 할 필요가 생겼다. 일단 롤백을 해서 시도를 해보고, 만약 TIMEOUT 실패가 된다면 지난 포스팅에 나온 것처럼 뭔가 더 해보도록 하자.

 

---

2. 구현해야 하는 것

fd_allocate의 정정

 

---

3. 구현 과정 & 디버깅

일단 fd_allocate 및 기타 함수에서 free_fd_list와 last_allocate를 제외하면서, 예전 형태로 롤백해본다. 대신, fd_allocate의 경우 탐색할 때 사용했던 요소를 활용해 list_insert_ordered 대신 list_insert를 활용함으로서, 추가적인 시간 낭비를 없앨 수 있다.

/* Inserts ELEM just before BEFORE, which may be either an
   interior element or a tail.  The latter case is equivalent to
   list_push_back(). */
void
list_insert (struct list_elem *before, struct list_elem *elem) {
	ASSERT (is_interior (before) || is_tail (before));
	ASSERT (elem != NULL);

	elem->prev = before->prev;
	elem->next = before;
	before->prev->next = elem;
	before->prev = elem;
}

fd_allocate에서 이전처럼 선형 탐색을 통해 비어있는 fd를 탐색할 경우, 루프를 돌면서 처음으로 연속되지 않은 fd에 해당하는 엔트리의 list_elem을 얻을 수 있다. 해당 list_elem과 list_insert를 같이 사용하면 새로 할당하는 fd를 정확한 위치에 정렬된 상태로 넣을 수 있다. 해당 방식대로 수정하도록 하자.

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

	int fd = 0;

	for (e = list_begin(&curr->fd_list); e != list_end(&curr->fd_list); e = list_next(e))
	{
		tmp = list_entry(e, struct fildes, fd_elem);
		if (tmp->fd == fd)
			fd++;
		else
			break;
	}

	fd_entry = (struct fildes *)malloc(sizeof(struct fildes));
	fd_entry->fd = fd;
	fd_entry->fp = fp;

	list_insert (e, &fd_entry->fd_elem);

	return fd;
}

다시 make check를 해 본다. 

...
pass tests/userprog/no-vm/multi-oom
...
All 95 tests passed.
make[1]: Leaving directory '/home/z3r0/pintos-kaist/userprog/build'

통과하네? 그럼 지지난 포스팅에서는 왜 그런 뻘짓을 한 걸까? 좀 허무하지만 끝났다.

 

---

4. 후기

뭐지? 그럼 TIMEOUT 나는 주요 원인은 fork에서 fd_list를 복사하는 과정에서 발생하는 시간이었다는 건가? 하긴 다시 생각해보니 O(n) 리스트를 순회하면서 각 insert마다 O(n)씩 걸리면 O(n^2)이라 비효율적이었을 것이다. 해당 과정은 기존에 없애놨으니 다른 곳에서의 optimize 여부와는 상관없이 통과할 수는 있었던 것이다.

 

뭐 아무튼 해당 fd_allocate는 이제 인위적인 fd의 유입 여부와는 관계 없이 fd를 잘 할당할 수 있게 되었다. 이제 다음 포스팅에서는 dup2에 필요한 구조체를 넣어보고 연결해보겠다.