정글 [week9] WIL + PintOS Threads

1. 이번 주 목표

이번 주의 가장 큰 목표는 PintOS의 thread 실행 흐름을 코드 기준으로 이해하는 것이었다. 특히 thread_create()로 생성된 thread가 바로 실행되는 것이 아니라 ready_list에 들어가고, 이후 scheduler가 선택해야 실제로 실행된다는 흐름을 잡는 데 집중했다.

구현 측면에서는 alarm clock을 중심으로 봤다. 기존 busy waiting 방식이 왜 비효율적인지 이해하고, 잠든 thread를 sleep_list에 넣었다가 timer interrupt에서 깨우는 구조를 따라가려고 했다. 추가로 ready_list를 priority 기준으로 정렬하는 기본적인 priority scheduling 흐름도 확인했다.

처음에는 커널 코드 흐름이 낯설었다. 함수 하나를 봐도 이 함수가 언제 호출되는지, 호출 후 thread 상태가 어떻게 바뀌는지 바로 감이 오지 않았다. 지난주까지 배운 포인터, 구조체, 리스트 개념이 이번 주에 직접 이어졌다. struct thread, list_elem, list_entry를 이해하지 못하면 ready_list나 sleep_list의 흐름을 따라가기 어려웠다.

2. 시도한 접근 방식

처음부터 전체 코드를 보려고 하기보다 실행 흐름을 기준으로 쪼개서 봤다.

```plain text thread_create -> thread_unblock -> ready_list -> schedule -> next_thread_to_run

이 순서로 따라가면서 thread가 생성되고 준비 상태가 되고, 실제 실행 대상으로 선택되는 과정을 확인했다.

alarm clock은 `timer_sleep()`부터 시작해서 봤다. 현재 tick을 기준으로 thread가 깨어나야 할 절대 시간을 `wake tick`으로 저장하고, `thread_sleep()`에서 `sleep_list`에 정렬 삽입한 뒤 block 상태로 만든다. 이후 `timer_interrupt()`가 발생할 때마다 `thread_wakeUp()`이 호출되고, 깨어날 시간이 된 thread를 `sleep_list`에서 꺼내 `thread_unblock()`으로 다시 `ready_list`에 넣는 흐름이다.

이번 주에 실제로 확인한 구현은 다음 범위였다.

- alarm clock
- `sleep_list`
- `ready_list` 우선순위 정렬
- 기본 semaphore
- lock
- condition variable 흐름

priority donation과 MLFQS는 `dev` 브랜치 기준으로 아직 구현되어 있지 않아, 구현했다기보다는 개념과 앞으로 필요한 흐름을 정리하는 수준에 머물렀다. preemption도 priority donation과 연결된 완성 구현으로 다룬 것은 아니고, 현재 코드에서 `thread_yield()`가 필요한 시점과 timer 기반 흐름을 이해하는 정도로 봤다.

AI는 주로 함수 흐름을 확인하는 용도로 사용했다. 코드를 대신 작성하게 하기보다는 다음과 같은 질문으로 흐름을 이해하려고 했다.

- 왜 `timer_sleep()`에서 block을 해야 하는가?
- `sleep_list`를 왜 wake tick 기준으로 정렬해야 하는가?
- `ready_list`에 들어간 thread는 언제 실행되는가?

## 3. 문제와 해결 과정

### busy waiting을 없애는 구조

가장 오래 붙잡았던 부분은 alarm clock에서 busy waiting을 없애는 구조였다. 처음에는 `timer_sleep()`이 단순히 일정 시간 동안 반복문을 돌면서 기다리는 함수라고 생각했다. 하지만 그렇게 하면 자고 있어야 할 thread가 CPU를 계속 사용하게 된다.

그래서 sleep 상태의 thread는 CPU를 점유하지 않도록 block시키고, 나중에 timer interrupt에서 깨우는 방식이 필요하다는 것을 이해했다.

```plain text
timer_sleep
-> sleep_list에 삽입
-> thread_block
-> timer_interrupt
-> thread_wakeUp
-> thread_unblock

sleep_list에 들어간 thread가 다시 실행되는 과정

처음에는 sleep_list에 넣은 thread가 어떻게 다시 실행되는지 헷갈렸다. thread_sleep()에서 현재 thread를 sleep_list에 넣고 thread_block()을 호출하면, 그 thread는 scheduler 대상에서 빠진다.

이후 매 tick마다 timer_interrupt()가 발생하고, thread_wakeUp()이 sleep_list의 앞쪽부터 확인해서 깨어날 시간이 지난 thread를 thread_unblock()한다. 이때 다시 ready_list에 들어가지만, 이것도 바로 실행을 의미하는 것은 아니다. scheduler가 선택해야 실행된다.

즉 흐름은 다음과 같이 이해할 수 있었다.

plain text BLOCKED -> wake time 도달 -> READY -> scheduler 선택 -> RUNNING

ready_list는 단순 큐가 아니다

ready_list도 처음에는 단순 큐처럼 생각했지만, priority scheduling을 위해서는 우선순위가 높은 thread가 앞에 오도록 관리해야 했다.

그래서 thread_unblock()이나 thread_yield()에서 list_insert_ordered()를 사용해 priority 기준으로 삽입하는 구조를 확인했다. 이 방식은 다음 실행 thread를 고를 때 ready_list의 front를 꺼내면 되기 때문에 scheduler 쪽 로직을 단순하게 만든다.

priority donation은 아직 남아 있는 과제

반면 priority donation은 아직 구현되어 있지 않다. 그래서 이번 주에는 lock을 잡은 낮은 priority thread 때문에 높은 priority thread가 기다릴 수 있다는 문제 상황, 즉 priority inversion이 왜 생기는지만 개념적으로 정리했다.

실제 donation 전파나 lock release 시 priority 복구 같은 구현은 다음 과제로 남았다.

4. 새롭게 배운 점

이번 주에 가장 크게 느낀 점은 운영체제의 thread가 단순한 함수 실행이 아니라 상태 전이로 관리된다는 것이다. thread는 RUNNING, READY, BLOCKED 같은 상태를 오가고, 어느 리스트에 들어가 있는지에 따라 scheduler가 볼 수 있는 대상인지 아닌지가 달라진다.

동기화 개념의 구분

동기화 개념도 조금 더 구분할 수 있게 되었다.

sema_down()은 semaphore 값이 0이면 현재 thread를 waiters list에 넣고 block한다.
sema_up()은 값을 올리고 기다리는 thread가 있으면 하나를 깨운다.
lock은 내부적으로 semaphore를 사용하지만 holder 개념이 있어서 “누가 lock을 가지고 있는가”를 표현할 수 있다.

다만 현재 구현은 기본 lock 동작까지이고, priority donation까지 연결되어 있지는 않다.

Scheduling에서 ready_list의 의미

Scheduling에서는 ready_list가 핵심이었다. 실행 가능한 thread들이 모이는 곳이고, priority scheduling을 하려면 이 리스트를 priority 기준으로 관리해야 한다.

thread_create()로 새 thread가 만들어져도 바로 실행되는 것이 아니라 thread_unblock()을 통해 ready_list에 들어간 뒤 scheduler 흐름을 타야 한다는 점이 중요했다.

MLFQS는 아직 개념 단계

MLFQS는 아직 구현하지 못했다. 다만 priority를 고정값으로만 보는 방식과 다르게, recent_cpu, nice, load_avg 같은 값을 바탕으로 동적으로 priority를 계산한다는 개념은 잡았다. 아직 수식과 갱신 시점을 코드로 연결하는 데는 부족함이 남아 있다.

팀 활동에서 느낀 점

팀 활동에서는 같은 PintOS 코드를 보더라도 각자 막히는 지점이 다르다는 점이 인상 깊었다. 나는 특히 thread 상태 변화와 리스트 이동을 따라가는 데 시간이 걸렸고, 이를 그림처럼 정리해야 흐름이 보였다.

5. 다음 주 계획

다음 주에는 PintOS Project 2 - User Programs를 진행한다. 이번 주 Threads에서 thread 생성, scheduling, synchronization의 흐름을 따라갔다면, 다음 주에는 user program이 커널 위에서 어떻게 실행되고 system call을 통해 커널 기능을 요청하는지 이해하는 데 집중할 계획이다.

가장 큰 목표는 Project 2의 필수 테스트 케이스를 통과할 수 있도록 구현하는 것이다. 단순히 코드를 추가하는 것보다, user program 실행 흐름, argument passing, system call 처리, process wait/exit 관계를 하나씩 따라가면서 왜 해당 구현이 필요한지 이해하려고 한다.

특히 user 영역과 kernel 영역이 분리되어 있기 때문에, 잘못된 포인터 접근이나 예외 처리 흐름을 꼼꼼히 봐야 할 것 같다.

이번 주까지는 팀원들과 논의는 함께 했지만 코드는 각자 작성하는 방식에 가까웠다. 다음 주부터는 팀 repository에서 개인 branch로 작업하고, 매일 코어타임에 PR을 올려 서로 코드를 검토한 뒤 master branch에 병합하는 방식으로 진행된다.

그래서 구현 자체뿐 아니라 내가 작성한 코드의 의도와 트러블슈팅 과정을 팀원에게 설명할 수 있는 것도 중요한 목표가 될 것 같다.

실습 환경은 Ubuntu 22.04 LTS 또는 Docker 기반 PintOS 환경을 사용하고, 테스트 검증에는 필요하면 pintos-util도 활용할 예정이다. 테스트가 실패했을 때는 바로 코드를 수정하기보다, 어떤 syscall 또는 process 흐름에서 깨졌는지 먼저 좁혀 보고 원인을 말로 설명한 뒤 고치는 방식으로 공부하고 싶다.

정리하면 다음 주 목표는 두 가지다.

Project 2 - User Programs의 필수 구현을 팀 코드로 완성하기
user program과 kernel 사이의 경계가 어떻게 관리되는지 이해하기

또한 PR 기반 협업을 통해 내 코드가 팀의 최종 결과물에 안전하게 합쳐질 수 있도록 구현 이유와 변경 범위를 명확히 설명하는 연습을 할 계획이다.