이번 과제에서는 프로세스의 상태를 깊이 이해하는 것이 핵심이다.
아래 그림은 프로세스 상태의 흐름을 아주 잘 설명한 유명한 도식이다.

이를 pintos 코드로 해석하고 매핑해보자면,

이렇게 매핑될 수 있다.

thread.c 파일에 정의된 thread 관련 코드와 각 함수의 역할을 잘 이해한 후에 프로젝트를 시작하는 것이 훨씬 수월할 것이다.

요구사항

kaist pintos PROJECT1: THREADS / Alarm Clock
위 문서를 통해 확인한 요구사항이다.

호출 스레드의 실행을 최소 x만큼의 타이머 틱이 경과할 때까지 일시 중단시킨다.
시스템이 유휴 상태(idle)가 아니면 스레드가 정확히 x틱 이후에 깨어날 필요는 없으며, 적절한 시간 동안 기다린 후 ready queue에 넣어주면 된다.

devices/timer.c에 구현되어있는 timer_sleep() 을 수정할 것을 요구하고있다. 그 중에서도 아래 코드에 집중한다.

while (timer_elapsed (start) < ticks)
	thread_yield ();

현재는 busy wait 방법으로 thread_yield() 를 사용하여 구현되어 있다. 충분한 시간이 지날 때까지 running, ready 상태를 반복한다.

diff 만큼을 인자로 두고, 재귀호출

정리하는 지금 보니, 기존 코드를 제대로 분석하기 전의 아이디어라서 엉망이다.
다른 방법으로 busy wait을 구현하는 아이디어다(심지어 틀린 코드)

기존 코드가 while문을 사용하고 있어서, 다른 프로세스로 제어권을 넘겨주는 게 아니라 x 틱만큼이 지날 때까지 점유하고 있는 코드로 잘못 해석했다.

while (timer_elapsed (start) < ticks)
	thread_yield ();

그래서 if문 한 번으로 thread를 다시 ready 상태로 돌려주면 되겠다고 생각했다.
단순히 loop 보다 조건문이 좀 더 빠르겠다고 생각했던 거다.
(사실은 tick 수가 정확히 경과되었는지 반복 보장의 목적으로 while문을 사용한다.)

new → ready → running(시간 확인) → (아직이라면) → ready → running(시간 확인) → (경과 되었다면) → 완료
이 흐름을 코드로 구현했다.

/* Suspends execution for approximately TICKS timer ticks. */
void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();

	ASSERT(intr_get_level() == INTR_ON);

	int64_t diff = timer_elapsed(start) - ticks;
	if (diff) // 경과하였다면
	{
		thread_yield();
	}
	else // 경과하지 않았다면
	{
		thread_create("timer", PRI_DEFAULT, timer_sleep, &diff);
	}
	/*
	// Busy Wait
	while (timer_elapsed(start) < ticks)
		thread_yield();
	*/
}

엉망이다.
코드를 제대로 이해해야겠다는 생각을 했고,
busy wait이 아니면 도대체 어떻게 구현해야 하는 건지 도무지 감이 안 잡혔다.
tiemr tick에 대해 다시 공부하고 고민해야겠다.

---

현재 waiting(blocked) 상태를 전혀 사용하고 있지 않다.

조건에 맞지 않으면 무조건 ready 상태로 두고, 스케줄링에 따라 running 상태로 들어갈 수 있게 하고있다. 이런 과정은 불필요한 context switching을 발생시킨다.

타이머를 기다릴 동안에는 waiting 상태에 두고 타이머가 완료되면 다시 ready 상태로 이동시켜줘야 한다.

.
.

아니 근데 계속 모르겠는 거다.

어떻게 waiting 상태에 있는 쓰레드를 ready 상태로 옮겨주지??
조건을 판단해서 ready 상태로 옮겨주려면 어쨋든! 어떤 주체(커널이겠지)가 주기적으로 감시해야하지 않는가?
이건 성능 면에서 busy wait와 다를 바가 없지 않나?

다른 블로그들을 참고해도
waiting → ready 과정에서는 반드시 I/O 인터럽트가 발생하고, 현재 프로세스가 이 I/O 작업이 완료된 이후에 수행할 수 있다면 waiting 상태에서 I/O 작업 완료 신호(인터럽트) 를 기다려야 한다는 점만을 강조한다.

근데 내가 헤매는 부분은
특정 I/O 장치든, 타이머든 어떠한 조건이 충족되면, waiting 상태인 프로세스를 다시 ready 상태로 돌려주는 것 또한 스케쥴러가 주기적으로 감시하고 있어야 하는 게 아닌가? 싶은 거다.
그러면 위에서 busy wait 하는 거랑 뭔 차이가 있냐는 거다.

지금 구현 중인 타이머는 해당 시간 만큼의 tick을 계속 지켜보는 과정이 무조건 필요하지 않나? 그니까, waiting 상태여도 어쨋든 ready 상태로 이동시키려면 tick의 흐름을 보고있어야 하지 않나?

---

최대한 내 뇌로 고민해보려다가 GPT에게 물어본다.
.
.

🧭 스레드 상태: WAITING → READY 전환은 언제 일어날까?

스레드는 일반적으로 다음과 같은 상황에서 WAITING 상태에 들어가:

• read()나 recv()처럼 I/O 대기할 때
• sleep() 같이 타이머 기다릴 때
• pthread_cond_wait() 같은 조건변수 대기
• 락이 풀리길 기다릴 때

🧩 그럼 언제 READY로 돌아가?

👉 외부 이벤트가 발생하면 운영체제가 개입해서 바꿔줌!

상황	누가 감지하고 READY로 바꿔주나?
키보드/네트워크 입력	하드웨어 인터럽트 → 커널 ISR → 스레드 깨움
디스크 I/O 완료	DMA 완료 인터럽트 → 커널 → 해당 스레드 READY 전환
sleep 타이머 만료	시스템 타이머 인터럽트 → 커널 → READY 전환
조건변수 signal	다른 스레드가 pthread_cond_signal() → 커널이 대기 스레드 깨움

✅ 이 모든 경우에서 CPU는 직접 깨우지 않지만 스레드를 깨우고 상태를 변경하는 핵심 로직은 커널 안에 있는 코드가 수행

.
.

아하 인터럽트로.

아니 근데 자꾸 CPU와 커널을 분리하고 있는데, 어쨋든 커널도 CPU 위에서 실행되는 코드잖아. 커널 모드라는 것으로 권한을 분리할 것일 뿐이지

어쨋건 CPU가 그 타이머가 흘러가는 동안 감시하긴 해야하잖아?

GPT에게 또 물어본다.

.
.

✅ 타이머의 전체 흐름

📍 예: sleep(5)을 호출한 경우

1. 사용자 프로그램에서 sleep(5) 호출

   → 리눅스는 현재 프로세스를 WAITING 상태로 전환하고 커널로 진입

   → 타이머 하드웨어에 “5초 뒤 인터럽트 줘”라고 등록함

2. 타이머 하드웨어 칩이 카운트를 시작

   → CPU는 이걸 신경 안 쓰고 다른 작업 수행 중

3. 5초 뒤, 타이머 칩이 CPU에 인터럽트를 발생시킴

   → 이걸 timer interrupt 라고 함

4. CPU가 커널 모드로 진입, ISR 실행

   → 등록된 타이머 만료 → 해당 프로세스 READY 상태로 변경

5. 커널 스케줄러가 해당 프로세스를 다시 실행시킴

타이머	설명
PIT (Programmable Interval Timer)	오래된 기본 타이머, 일정 주기로 인터럽트 발생
HPET (High Precision Event Timer)	나노초 수준 정밀도, 최신 시스템에서 사용
APIC Timer	각 CPU 코어에 있는 고성능 타이머
TSC (Time Stamp Counter)	CPU 클럭 사이클을 세는 고정된 카운터

💡 이들은 모두 하드웨어 칩이고, OS는 이걸 소프트웨어적으로 제어해서 sleep, alarm, scheduler tick 등에서 사용

.
.

아하

그니까 타이머나 I/O 장치들은 별도의 하드웨어다. 하드웨어에 다 끝나면 알려달라고 등록을 해두는 거다.

내가 계속 고민했던 'CPU가 계속 들여다봐야하지 않나?' → 아니었던 것이다.
CPU가 소프트웨어적으로 제어하는 것이 아니라, 하드웨어에 맡기고 하드웨어에서 특정 조건에 만족했을 때 인터럽트를 일으키도록 하는 것이다.
인터럽트를 일으켰을 때, 소프트웨어적으로 인터럽트 핸들러를 정의하면 그 인터럽트에서 커널이 어떠한 처리를 할 수 있게 된다.

이를 이해하고 thread.c 파일이 아니라 timer.c 파일을 더 살펴보았다.
역시나 timer.c 파일에는 timer tick 관련 인터럽트가 정의되어있었다.
계속 쓰레드 단에서 수정을 봐야겠다고 생각했는데 잘못 생각하고 있던 것이었다.

waiting → ready로 상태를 변경하기 위해서는 커널이 처리하도록 인터럽트를 발생시켜야 한다.

하드웨어 장치(PIT; programmable interrupt timer)가 인터럽트를 발생시키고, tick에 관련된 인터럽트는 이미 구현되어있다.

PIT?
: 운영체제의 스케줄러에게 주기적인 인터럽트를 발생시키기 위한 타이머
컴퓨팅 및 임베디드 시스템에서 프로그래밍 가능 간격 타이머 ( PIT ) 는 프로그래밍된 카운트에 도달하면 출력 신호를 생성하는 카운터 입니다. 출력 신호는 인터럽트를 트리거할 수 있습니다.
참고 블로그, 위키피디아

10ms 간격의 출력 신호로 인터럽트를 발생시키는 타이머가 구현되어있다. 인터럽트는 OS가 부팅된 이후 tick을 1씩 증가시킨다.

이 인터럽트 핸들러에서 timer를 올바르게 정의하고 그 timer에 맞게 프로세스 상태를 변경해보면 어캐 되지 않을까?

timer_interrupt 인터럽트 핸들러 사용

1차

timer 인터럽트 핸들러에 sleep thread 정보를 넘겨야 한다.
→ 그러면 timer 인터럽트에서 모든 sleep thread를 알아야겠네?
--→ 아, sleep thread의 list를 만들어서 관리해야겠다.
----→ 이미 정의된 list 를 사용하면 되겠다.

그런데 sleep thread에서 필요한 정보는 1. thread 정보와 2. timer 정보이다.

방법은 두 가지가 떠오른다.
1. thread 구조체에 timer 정보를 추가하여 기존 list에 담아 사용할 방법이 있을테고,
2. 또 하나의 구조체를 만들어서 thread, timer 정보를 담고, 그 구조체의 list를 정의하여 사용하는 방법이다.

나는 1번 방법으로 기존 list를 보다 일관적으로 사용하기 위해 thread 정보를 저장하기로 하고,
추가로 필요한 timer의 정보는 thread 구조체에 추가하기로 한다.

그렇게 되면 timer_sleep() 호출과 동시에 처리되어야 하는 절차는 크게 세 가지이다.

1. 현재 thread의 timer 정보를 설정한다.
2. sleep list에 추가한다.
3. 현재 thread를 blocked(waiting) 상태로 변경한다.

(1번)
참고로 thread.c에서 thread를 초기화하는 코드도 일부 수정해야 한다.

struct thread
{
.
.
.
	int64_t timer; // sleep 상태를 위한 timer 정보 추가
.
.
    
}

(2번)

/* sleep 중인 쓰레드 목록을 관리 */
struct list sleep_list;

void timer_init(void)
{
	list_init(&sleep_list); // sleep_list 초기화
    .
    .
    .
    
}

(3번)

void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();

	ASSERT(intr_get_level() == INTR_ON);

	struct thread *curr = thread_current();
	// thread에 timer 추가
	curr->timer = timer_ticks() + ticks; // 깨어날 시간
	// sleep_list에 추가
	list_push_back(&sleep_list, &curr->elem);

	// 디버깅
	printf("\nthread_current: %p\n", thread_current());
	struct list_elem *e = list_begin(&sleep_list);
	while (e != list_end(&sleep_list))
	{
		printf("\nsleep_thread : %p\n", e);
		e = list_next(e);
	}

	// thread blocked state
	thread_block();
}

결과

• alarm-multiple.output

Kernel command line: -q run alarm-multiple
0 ~ 9fc00 1
100000 ~ 13e0000 1
Pintos booting with: 
	base_mem: 0x0 ~ 0x9fc00 (Usable: 639 kB)
	ext_mem: 0x100000 ~ 0x13e0000 (Usable: 19,328 kB)
Calibrating timer...  26,188,800 loops/s.
Boot complete.
Executing 'alarm-multiple':
(alarm-multiple) begin
(alarm-multiple) Creating 5 threads to sleep 7 times each.
(alarm-multiple) Thread 0 sleeps 10 ticks each time,
(alarm-multiple) thread 1 sleeps 20 ticks each time, and so on.
(alarm-multiple) If successful, product of iteration count and
(alarm-multiple) sleep duration will appear in nondescending order.
Kernel PANIC at ../../threads/thread.c:224 in thread_block(): assertion `intr_get_level() == INTR_OFF' failed.
Call stack: 0x80042132bb 0x8004206cef 0x800420cf01 0x8004216c44 0x8004216926 0x80042166f7 0x8004206636 0x8004206783 0x8004206120.
The `backtrace' program can make call stacks useful.
Read "Backtraces" in the "Debugging Tools" chapter
of the Pintos documentation for more information.
Timer: 56 ticks
Thread: 0 idle ticks, 56 kernel ticks, 0 user ticks
Console: 1

Kernel PANIC at ../../threads/thread.c:224 in thread_block(): assertion `intr_get_level() == INTR_OFF' failed.
커널 패닉.. 나도 패닉이다 진짜..

thread.c 244번째 줄을 보자.

void thread_block(void)
{
	ASSERT(!intr_context());
	ASSERT(intr_get_level() == INTR_OFF); // 이 부분이다.
	thread_current()->status = THREAD_BLOCKED;
	schedule();
}

아 그니까 thread를 block하려 할 때, 인터럽트 level이 off(인터럽트 비활성화 상태)여야 하는데 그 처리를 안 해줬다는 말이다.

thread의 상태를 변경할 때는 동시성을 위해 인터럽트 비활성화 상태에서 이루어져야 한다.

이 점을 참고하여 다시 작성!
동시성을 위해 인터럽트를 비활성화해주는 어떤 메서드가 있던 것 같다.

찾아보았더니 intr_disable() 이다. 보통 critical section을 다음과 같이 감싸서 사용하더라.

enum intr_level old_level = intr_disable();
/* Critical Section */
intr_set_level(old_level);

2차

void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();

	ASSERT(intr_get_level() == INTR_ON);

	struct thread *curr = thread_current();
	// thread에 timer 추가
	curr->timer = timer_ticks() + ticks; // 깨어날 시간
	// sleep_list에 추가
	list_push_back(&sleep_list, &curr->elem);

	// 디버깅
	printf("\nthread_current: %p\n", thread_current());
	struct list_elem *e = list_begin(&sleep_list);
	while (e != list_end(&sleep_list))
	{
		printf("\nsleep_thread : %p\n", e);
		e = list_next(e);
	}

	// thread blocked state
	enum intr_level old_level = intr_disable(); // 동기화 (interruption 비활성화)
	thread_block();
	intr_set_level(old_level);
}

결과

• alarm-multiple.output

Kernel command line: -q run alarm-multiple
0 ~ 9fc00 1
100000 ~ 13e0000 1
Pintos booting with: 
	base_mem: 0x0 ~ 0x9fc00 (Usable: 639 kB)
	ext_mem: 0x100000 ~ 0x13e0000 (Usable: 19,328 kB)
Calibrating timer...  26,188,800 loops/s.
Boot complete.
Executing 'alarm-multiple':
(alarm-multiple) begin
(alarm-multiple) Creating 5 threads to sleep 7 times each.
(alarm-multiple) Thread 0 sleeps 10 ticks each time,
(alarm-multiple) thread 1 sleeps 20 ticks each time, and so on.
(alarm-multiple) If successful, product of iteration count and
(alarm-multiple) sleep duration will appear in nondescending order.

thread_current: 0x8004000000
Kernel PANIC at ../../lib/kernel/list.c:78 in list_next(): assertion `is_head (elem) || is_interior (elem)' failed.
Call stack: 0x8004213376 0x80042135f2 0x800420d120 0x800420871c 0x8004208b3a 0x8004216cff 0x80042169e1 0x80042167b2 0x8004206636 0x8004206783 0x8004206120.
The `backtrace' program can make call stacks useful.
Read "Backtraces" in the "Debugging Tools" chapter
of the Pintos documentation for more information.
Timer: 62 ticks
Thread: 0 idle ticks, 62 kernel ticks, 0 user ticks
Console: 1

으아 또 Kernel PANIC이라니..

Kernel PANIC at ../../lib/kernel/list.c:78

자, 여기 list.c 78번째 줄을 보자

list_next (struct list_elem *elem) {
	ASSERT (is_head (elem) || is_interior (elem));
	return elem->next;
}

아하 list_next 부분에서 인자로 들어가는 노드가 list 범위 밖에 있는 노드인가보다.

오잉 왜지?

설마 또 동시성 문제인가?

is_head , is_interior 를 확인하자.

/* Returns true if ELEM is a head, false otherwise. */
static inline bool
is_head (struct list_elem *elem) {
	return elem != NULL && elem->prev == NULL && elem->next != NULL;
}

/* Returns true if ELEM is an interior element,
   false otherwise. */
static inline bool
is_interior (struct list_elem *elem) {
	return elem != NULL && elem->prev != NULL && elem->next != NULL;
}

그니까, 그 노드가 빈 노드이거나, 이전 혹은 이후 노드가 빈 노드였다는 얘기다.

초기화가 잘 되었다면 이런 일은 없을 것이다.
초기화 문제가 아니라면 진짜 연결되지 않은 노드가 리스트에 들어간 것이다.

흠… 초기화는 timer_init 에서 잘 해주고 있고, 리스트에 넣는 로직은 list.c 에서 구현된 함수를 사용하기 때문에 임의의 노드가 삽입될 일은 없다.

리스트에 넣고있는 와중에 인터럽트가 발생하면서 블록이 되지 않은 상태로 조회해버리는 게 아닐까?

3차

/* Suspends execution for approximately TICKS timer ticks. */
/* 약 TICKS 타이머 틱 동안 실행을 일시 중단합니다. */
void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();

	ASSERT(intr_get_level() == INTR_ON);
	enum intr_level old_level = intr_disable(); // 동기화 (interruption 비활성화)

	struct thread *curr = thread_current();
	// thread에 timer 추가
	curr->timer = timer_ticks() + ticks; // 깨어날 시간
	// sleep_list에 추가
	list_push_back(&sleep_list, &curr->elem);

	// 디버깅
	printf("\nthread_current: %p\n", thread_current());
	struct list_elem *e = list_begin(&sleep_list);
	while (e != list_end(&sleep_list))
	{
		printf("\nsleep_thread : %p\n", e);
		e = list_next(e);
	}

	// thread blocked state
	thread_block();

	intr_set_level(old_level);
}

디버깅 코드를 그대로 두었더니, 테스트 출력 형식과 맞지 않아서 에러가 생겼다.

테스트를 할 때 디버깅 코드를 삭제하는 것이 중요하다!
디버깅을 하고자 할 때는 ASSERT를 추가로 사용하는 방법도 좋을 듯 하다.

4차

/* Suspends execution for approximately TICKS timer ticks. */
/* 약 TICKS 타이머 틱 동안 실행을 일시 중단합니다. */
void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();

	ASSERT(intr_get_level() == INTR_ON);
	enum intr_level old_level = intr_disable(); // 동기화 (interruption 비활성화)

	struct thread *curr = thread_current();
	// thread에 timer 추가
	curr->timer = timer_ticks() + ticks; // 깨어날 시간
	// sleep_list에 추가
	list_push_back(&sleep_list, &curr->elem);

	// thread blocked state
	thread_block();

	intr_set_level(old_level);
}

오예~
priority는 다음 과제를 해결하면 자동으로 될 거 같다!