[pintos] Week2~3: User Program 외전 - Linked List를 이용한 FD관리

이전 포스팅까지 해서 FDT를 사용한 Pintos UserProgram 구현과 내용 정리를 진행했다.

2025.05.26 - [크래프톤 정글] - [pintos] Week2~3: User Program Part.8 - exec, wait

[pintos] Week2~3: User Program Part.8 - exec, wait

하지만 우리 팀이 처음부터 FDT를 이용해 구현했던 것은 아니었다. 

Kojaewoong0504/jungle-pintos

---

1. 최초 10일간 있었던 일

우리 팀은 코치님의 제안 대로 구현해야 하는 기능 혹은 테스트 단위로 협업 혹은 티켓이라 불리는 일정관리를 진행해 보았다. Jira를 이용해 스프린트를 만들고 하루 단위로 스크럼을 통해 매일 구현할 기능 혹은 진행할 테스트 등을 선택하는 등 각자 구현하는 기능을 맡아서 진행했다.

그렇게 나는 wait, fork 를 담당하게 되었었다. 이때 다른 팀원이 open을 비롯한 파일 디스크립터관련된 구현을 진행하고 그 결과물을 올렸다. 이때 나는 UserProgram과 관련된 ppt나 여러 자료를 보고 있었는데 저료들에서는 FDT 방식으로 파일디스크립터를 구현했는데 팀원이 링크드리스트를 이용해 구현을 해서 주었을 때 정석? 아니면 다른 사람들이 일반적으로 사용하는 FDT 방식이 아니라 두려움과 동시에 만약 이를 이용해 모든 테스트를 통과할 수 있으면 좋을 것 같다는 생각을 하며 수용하기로 했다. 그렇게 우리 팀은 95개의 테스트 코드 중 94개의 테스트를 통과하고 마지막 multi-oom 만 남겨두었다. 하지만 그 multi-oom이 우리 팀의 발목을 잡았다. 우리 팀은 하나의 테스트를 통과하기 위해 4일 이상을 투자했고 그럼에도 multi-oom 테스트를 잡지 못했다.

그렇게 실의에 빠진 팀과 의욕을 잃어버리고 결국 대세를 따라 FDT 방식의 코드를 구현하기 시작했지만 초반의 페이스와 열기?는 일어나지 않았다. 그렇게 어찌어찌 구현을 하다 보니 FDT에서 ALL PASS를 볼 수 있었다. 하지만 FDT를 이용해 구현을 했다고 해서 우리가 이 전에 구현했던 Linked List 가 아주 터무니없는 접근은 아닐 것 같다는 생각이 ALL PASS 한 FDT 코드는 Git Hub Branch에 올려두고 다시 Linked List로 구현하던 시점으로 돌아와 다시 코드를 수정하기 시작했다. 하지만 여전히 Multi-OOM이 문제가 있었고 디버깅을 위해 printf를 여기저기 찍어 해당 테스트가 일어날 때 무슨 일이 있는지 확인하기 시작했다.

나는 처음에 FD 가 너무 많이 복사되는 것을 보고 특히 자식이 생성되면서 기하급수적으로 복사되는 FD 개수를 보며 나는 이 부분이 문제일 것이라 생각했다(하지만 이게 정상이었다.)

---

2. 각종 시행착오의 연속 

FD 개수 제한

처음에는 복사하는 FD를 강제로 제한하기도 했다. 무슨 말이냐면 자식도 무조건 128개의 FD만 가지게 제한 하는 등의 방법을 사용했는데 이렇게 하는 것은 당연히 안 되는 것이었다.

수동 디버깅

다음으로는 직접 디버거로 흐름을 체크하기도 했는데 multi-oom의 경우 자식의 자식을 생성하는 등 극한?의 조건이 포함되어 있어 디버깅이 매우 어려웠고 결국 포기했다. 

FDT 코드 재 분석

multi-oom에서 계속 통과가 되지 않자 나는 FDT 코드를 블로그에 정리하기 위해 다시 살펴 보고 이해한 내용을 확인하는 과정에서 FDT의 경우 4KB의 페이지를 3개를 이용해 multi-oom을 위해 사용한다는 것을 발견했고 그 크기만큼의 fd를 허용하는 것을 발견했다. 기존 코드에서 이런 제한이 없기 때문에 특히 힙에 malloc을 이용해 구현을 하는 현재 방식에서 차이가 발생했다는 가설을 세울 수 있었다.

코치님의 조언

그리고 이런 발견을 했던 날 코치님께서 진행사항을 체크하시면서 현재 상황에 대해 설명하니 내 가설과 비슷한 설명을 해 주셨다. multi-oom 이 자식의 자식을 생성하며 부모의 fd에 추가로 fd를 생성하다 보니 fd가 많아지는 것이고 그렇게 보이는 것이 문제가 아니라 현재 테스트에서 정상적인 상황이라는 것이며 multi-oom은 그렇게 해서 생성된 fd들을 메모리가 버틸 수 있는지 그리고 각종 종료 상황을 잘 처리하는지에 대한 테스트라는 것이고 그 과정을 10번을 반복할. 수 있어야 통과를 하는 테스트라는 것을 다시 깨닫게 되었다. 

---

3. 새로운 가설

코치님의 조언을 듣고 생각해보니  FDT 방식은 고정 크기 배열 방식이다. 즉 스레드 생성 시 스레드 구조체 내부에 고정된 크기의 배열을 palloc_get_page()로 할당하고 있으며 그 덕에 인덱스를 FD로 사용하여 접근 가능하다.

하지만 우리가 구현하고 있던 링크드리스트 방식은 FD를 구조체로 만들고 필요할 때 malloc으로 동적으로 할당한다. 그 때문에 필요한 만큼만 사용하지만 FD 수에 제한이 없어서 multi-oom 테스트에서 메모리가 엄청나게 소모된 것 같았다.

결국 FDT에서는 메모리 12KB로 스레드 마다 제한을 하고 있으니 링크드 리스트 방식에서 FDT와 비슷한 수준의 개수만 malloc을 통해 생성할 수 있도록 제한을 두어야겠다는 생각이 들었다.

---

4. 재구현

파일 디스크립터 구조체 선언

• include/threads/thread.h

struct file_descriptor {
    int fd;                  /* 할당된 FD 번호 */
    struct file *file_p;     /* 실제 파일 포인터 */
    struct list_elem fd_elem;/* fd_list 에 들어갈 elem */
};

파일 디스크립터 제한 코드

• include/threads/thread.h

#define FDT_PAGES     3     
#define FDCOUNT_LIMIT FDT_PAGES * (1 << 9)

thread 구조체 정의 수정

• include/threads/thread.h

struct thread {
    /* Owned by thread.c. */
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging). */
    int priority;                       /* Priority. */
    .
    .
    .
#ifdef USERPROG
	/* Owned by userprog/process.c. */
	struct list child_list;
	struct list_elem child_elem;
	struct thread *parent;
    struct file *running;

	struct intr_frame parent_if;

	int exit_status;
    uint64_t *pml4;                     /* 페이지 맵 레벨 4 포인터 */

    struct semaphore wait_sema;
	struct semaphore exit_sema;
	struct semaphore fork_sema;
    /* File descriptor management (항상 사용) */
    int last_created_fd;                /* 다음 발급할 FD 번호 */
    struct list fd_list;                /* file_descriptor 리스트 */
#endif
    .
    .
    .
}

thread_create() 함수 수정

• threads/thread.c

tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;

	ASSERT (function != NULL);

	/* Allocate thread. */
	t = palloc_get_page (PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;
	struct thread *curr = thread_current();

	/* Initialize thread. */
	init_thread (t, name, priority);
	tid = t->tid = allocate_tid ();

#ifdef USERPROG
	/* 파일 디스크립터 리스트 초기화 */
	list_init(&t->fd_list);
	t->last_created_fd = 3; // stdin(0), stdout(1), stderr(2) 이후부터 할당
	
	for (int i = 0; i < 3; i++) {
		struct file_descriptor *fd_entry = malloc(sizeof(struct file_descriptor));
		if (fd_entry == NULL) {
			/* 이전에 할당된 fd_entry들 해제 */
			while (!list_empty(&t->fd_list)) {
				struct list_elem *e = list_pop_front(&t->fd_list);
				struct file_descriptor *cleanup_fd = list_entry(e, struct file_descriptor, fd_elem);
				free(cleanup_fd);
			}
			palloc_free_page(t);
			return TID_ERROR;
		}

		fd_entry->fd = i;
		fd_entry->file_p = NULL;  // 실제 파일이 없으므로 NULL
		list_push_back(&t->fd_list, &fd_entry->fd_elem);
	}
	t->exit_status = 0;
	list_push_back(&curr->child_list, &t->child_elem);

#endif
.
.
.
}

• thread_create에 0부터 3번 fd의 경우 이미 예약되어 있으니 NULL 값으로 초기화 하는 과정이다.
• 이때 malloc에 실패했을 경우 즉 메모리가 부족해서와 같은 이유로 할당되지 않으면 기존에 할당된 내용을 모두 해제한다.

 

for (int i = 0; i < 3; i++) {
    struct file_descriptor *fd_entry = malloc(sizeof(struct file_descriptor));
    if (fd_entry == NULL) {
        /* 이전에 할당된 fd_entry들 해제 */
        while (!list_empty(&t->fd_list)) {
            struct list_elem *e = list_pop_front(&t->fd_list);
            struct file_descriptor *cleanup_fd = list_entry(e, struct file_descriptor, fd_elem);
            free(cleanup_fd);
        }
        palloc_free_page(t);
        return TID_ERROR;
    }

    fd_entry->fd = i;
    fd_entry->file_p = NULL;  // 실제 파일이 없으므로 NULL
    list_push_back(&t->fd_list, &fd_entry->fd_elem);
}
t->exit_status = 0;
list_push_back(&curr->child_list, &t->child_elem);

보조 함수 수정

이 전에 FDT에서 사용했던 함수들이 있을 것이다. 이 함수를 링크드리스트용으로 수정할 것이다. 최초에 구현할 때는 각자 구현을 해서 합치다 보니 이런 재사용되는 함수를 파악하지 못했고 이로 인하여 비슷하지만 그 사용이 겹쳐서 재 구현을 하는 등 미세한 차이가 문제를 찾고 고치는 데 방해가 되었다.

• userprog/process.c

int process_add_file(struct file *f) 
{
    struct thread *curr = thread_current();

     // 1. 리스트 크기 제한 검사
    if (list_size(&curr->fd_list) >= FDCOUNT_LIMIT) {
        return -1;
    }

    // 2. FD 번호 제한 검사  
    if (curr->last_created_fd >= FDCOUNT_LIMIT) {
        return -1;
    }

    // file_descriptor 구조체 동적 할당 - malloc 사용
    struct file_descriptor *fd_entry = malloc(sizeof(struct file_descriptor));
    if (fd_entry == NULL)
        return -1;

    fd_entry->fd = curr->last_created_fd++;
    fd_entry->file_p = f;
    list_push_back(&curr->fd_list, &fd_entry->fd_elem);

    return fd_entry->fd;
}

• 위 함수는 FD를 할당하는 함수인데 리스트 사이즈가 FDCOUNT_LIMIT를 초과하는지 체크해서 넘긴다면 return -1을 수행한다.
• 또한 생성된 FD의 번호도 검사를 한다.
• 이 후 FD를 malloc으로 동적 할당하여 리스트에 저장한다.

---

• userprog/process.c

struct file *process_get_file(int fd) {
    struct thread *curr = thread_current();

    if (fd < 0 || fd >= FDCOUNT_LIMIT)
        return NULL;

    struct list_elem *e;
    for (e = list_begin(&curr->fd_list); e != list_end(&curr->fd_list); e = list_next(e)) {
        struct file_descriptor *fd_entry = list_entry(e, struct file_descriptor, fd_elem);
        if (fd_entry->fd == fd)
            return fd_entry->file_p;
    }

    return NULL;  // 해당 FD를 찾지 못한 경우
}

• 위 함수는 FD 리스트 내에 등록된 FD 가 있는지 확인하고 있는 경우 해당하는 파일을 반환한다.

---

• userprog/process.c

int process_close_file(int fd) {
    struct thread *curr = thread_current();

    if (fd < 0 || fd >= FDCOUNT_LIMIT)
        return -1;

    struct list_elem *e;
    for (e = list_begin(&curr->fd_list); e != list_end(&curr->fd_list); e = list_next(e)) {
        struct file_descriptor *fd_entry = list_entry(e, struct file_descriptor, fd_elem);
        if (fd_entry->fd == fd) {
            list_remove(&fd_entry->fd_elem);  // 리스트에서 제거

            if (fd_entry->file_p != NULL)
                file_close(fd_entry->file_p);  // 파일 닫기

            free(fd_entry);  // malloc으로 할당된 메모리 해제
            return 0;
        }
    }

    return -1;  // 해당 FD를 찾지 못한 경우
}

• 위 함수는 fd_list 내를 돌며 요청한 FD가 있는지 찾고
• 찾은 파일을 닫은 뒤 해당 FD를 free로 자원을 해제한다.

---

void remove_all_fd(struct thread *t) {
     if (t == NULL)
        return;

    while (!list_empty(&t->fd_list)) {
        struct list_elem *e = list_pop_front(&t->fd_list);
        struct file_descriptor *fd_entry = list_entry(e, struct file_descriptor, fd_elem);

        if (fd_entry != NULL) {
            if (fd_entry->file_p != NULL)
                file_close(fd_entry->file_p);
            free(fd_entry);
        }
    }
}

• 해당 프로세스(스레드)의 모든 파일을 닫고 FD를 자원해제한다.

---

__do_fork() 함수 수정

static void
__do_fork (void *aux) {
    struct intr_frame if_;
    struct thread *parent = (struct thread *) aux;
    struct thread *current = thread_current ();
    struct intr_frame *parent_if = &parent->parent_if;
    bool succ = true;
    .
    .
    .
    .
#endif
    /* FD 수 제한 검사: 복제 시 개수 초과 방지 */
    if (list_size(&parent->fd_list) >= FDCOUNT_LIMIT)
        goto error;

    /* 자식 프로세스의 FD 초기화 */
    current->last_created_fd = parent->last_created_fd;

	/* 부모의 fd_list 순회하며 복사 - malloc 사용 */
    struct list_elem *e;
    for (e = list_begin(&parent->fd_list); e != list_end(&parent->fd_list); e = list_next(e)) {
        struct file_descriptor *parent_fd = list_entry(e, struct file_descriptor, fd_elem);

        // malloc으로 메모리 할당
        struct file_descriptor *child_fd = malloc(sizeof(struct file_descriptor));
        if (child_fd == NULL)
            goto error;

        child_fd->fd = parent_fd->fd;
        child_fd->file_p = parent_fd->file_p ? file_duplicate(parent_fd->file_p) : NULL;
        if (parent_fd->file_p != NULL && child_fd->file_p == NULL) {
            free(child_fd);  // 실패 시 메모리 해제
            goto error;
        }

        list_push_back(&current->fd_list, &child_fd->fd_elem);
    }
    .
    .
    .
    .
error:
    remove_all_fd(current);
    sema_up(&current->fork_sema);  // 복제에 실패했으므로 현재 fork용 sema unblock
    exit(TID_ERROR);
}

• __do_fork()에서 부모의 FD를 복사해 가던 기능을 리스트 방식으로 수정한다. 이때 에러가 발생하는 조건을 잘 체크한다.
• 에러가 발생하거나 원하는 값이 없는 경우에 실패하기 때문에 적절히 에러 처리를 한다.
• 이 때 앞에서 구현한 remove_all_fd() 함수를 이용해 모든 FD를 제거한 뒤 에러처리를 한다. 

process_exit() 함수 수정

• userprog/process.c

void
process_exit (void) {
	struct thread *curr = thread_current ();
	/* TODO: Your code goes here.
	 * TODO: Implement process termination message (see
	 * TODO: project2/process_termination.html).
	 * TODO: We recommend you to implement process resource cleanup here. */

	remove_all_fd(curr);

    if (curr->running != NULL)
        file_close(curr->running);

    process_cleanup();

    sema_up(&curr->wait_sema);      // wait() 중인 부모를 깨운다
    sema_down(&curr->exit_sema);    // 부모가 정리할 때까지 대기 (메모리 해제)
}

---

결과

---

후기

정말 힘들었다. 하나의 테스트를 통과하기 위해 몇 시간이나 코드를 고치거나 처음부터 다시 구현을 하거나 디버깅을 하는 등 많은 수정을 하기도 했다. 하지만 결국 ALL PASS를 봤을 때의 희열이 있었다. 하지만 이 과정을 통해 느낀 것은 최대한 많은 자료를 보고 교차 검증을 하자!