Pintos Project 1-1. Busy Waiting vs. Sleep/Wakeup

인트로

크래프톤 정글 9주차, Pintos 프로젝트를 진행하며 배우고 느낀 점들을 공유하는 시리즈의 첫 번째 글입니다. Pintos 프로젝트는 이론으로만 배우던 운영체제의 핵심 개념들을 직접 코드로 구현해보면서 깊이 이해할 아주 좋은 기회인데요. 그 첫 번째 파트인 '알람 시계(Alarm Clock)' 구현에 대해 이야기해 보고자 합니다.

참고: 저희는 스탠포드대 CS 112/212의 오리지널 Pintos가 아닌, x86-64에 맞춘 Pintos-KAIST로 프로젝트를 수행하고 있으며, 포스트 또한 이를 기준으로 합니다.

---

과제 목표: timer_sleep() 개선

Credit: https://slideplayer.com/slide/13132371/

저희가 다룰 함수는 devices/timer.c에 정의된 void timer_sleep(int64_t ticks)입니다. 최초로 받았을 당시 기본 구조는 위와 같습니다. 이 함수의 역할은 현재 스레드의 실행을 ticks만큼의 타이머 틱(tick) 시간 동안 중단시키는 것입니다. 커서를 깜빡이거나 일정 시간 대기해야 하는 작업에 유용하지요. 문제는 timer_sleep()의 구현 방식입니다. 아래 코드를 봐주세요.

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

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

이것이 바로 Busy Waiting (바쁜 대기) 또는 Spin Waiting (스핀 대기)라는 비효율적인 방식입니다. 스레드는 자신이 깨어나야 할 시간(start+ticks)이 될 때까지 while 루프를 계속 돌면서 현재 시간을 확인하고, 시간이 되지 않았으면 thread_yield()를 호출하여 CPU를 다른 스레드에게 넘겨줍니다. 넘겨주기는 하지만, while문을 돌면서 저러니, 마치 어떠한 사람을 5분간 기다리게 할 때, 그냥 가만히 있는 게 아니라 계속 시계를 쳐다보게 만드는 것입니다. CPU는 자꾸 시계를 쳐다봐야 하니 다른 일을 할 수가 없습니다.

---

해결책: 스레드를 재워두고, 타이머 인터럽트로 깨우기

Credit: https://woonys.tistory.com/142

Busy Waiting을 피하기 위한 핵심 아이디어는 스레드를 블록(Block) 상태로 만들어서 스케줄링 대상에서 제외시키고, 정해진 시간이 되었을 때 누군가 이 스레드를 깨워서(Unblock) 다시 실행 가능한 상태로 만들어주는 것입니다. Pintos 환경에서 이 역할을 담당하기에 가장 적합한 것은 바로 타이머 인터럽트 핸들러입니다. 타이머 인터럽트는 일정한 간격(TIMER_FREQ, 기본값 100Hz)으로 발생하며, 이때마다 현재 시간이 1틱씩 증가합니다. 이 인터럽트가 발생할 때마다 잠들어 있는 스레드들 중 깨어날 시간이 된 스레드가 있는지 확인하고 깨워주면 됩니다.

타이머 인터럽트란?

타이머 인터럽트는 OS에서 시간을 관리하고 시간 기반 작업을 수행하는 데 필수인 구성요소입니다. 주로 하드웨어 타이머 칩(또는 CPU 내장 타이머)이 주기적으로 발생시키며, OS의 "심장 박동" 같은 역할입니다. 이 인터럽트가 발생할 때마다 OS는 미리 등록된 인터럽트 핸들러(ISR, Interrupt Service Routine)를 실행하여 다양한 시간 관련 작업을 수행합니다. 이번에 저희가 구현하는 alarm clock 같은 것도 마찬가지입니다.

실제 사례

현대 OS에서 타이머 인터럽트는 매우 중요합니다. 인터럽트 발생 주기는 설정에 따라 달라지지만 전통적으로 "Jiffy" 또는 "Tick" 이라는 시간 단위를 사용합니다. 이들도 기본적으로 Pintos와 동일하게 100 Hz, 즉, 10 ms당 1씩 오르는 구조입니다. 한편, Windows 9x 계열 (95, 98, Me 등) 역시 이런 기능이 있었는데, 이 과정에서 32비트 카운터 오버플로로 인한 유명한 문제가 발생했으니, 바로 그 49.7일 문제입니다.

Windows 9x는 당시 가정용 PC에 최적화된 가벼운 구조와 하위호환으로 많은 사랑을 받았으나 동시에 허술한 관리/보호, 불안정성, 써드파티 드라이버들의 부조화로 악명이 높았습니다. 그래서 요즘의 PC야 한번 켜놓고 며칠 몇달을 켜놓는 게 일상이라지만 9x는 특유의 불안정성으로 고작 수 시간만 켜놓아도 블루 스크린 때문에 재부팅이 필수였지요. 그러나 설령 버틴다 쳐도 결국 uptime이 49.7일은 넘길 수 없었으며, 이후 무조건 재부팅해야만 했었습니다. 

• Windows 9x는 시스템이 부팅된 이후 경과된 시간을 1 ms 당 1씩 올라 부호 없는(unsigned) 32비트 정수에 저장하고, 이를 GetTickCount()와 같은 API를 통해 애플리케이션에 제공했습니다.
• 부호 없는 32비트 정수가 표현할 수 있는 최댓값은 2^32−1, 즉, 4,294,967,295입니다. 이 카운터가 1 ms당 1씩 오르므로, 카운터가 최댓값에 도달하여 다시 0으로 돌아오기까지 걸리는 시간은 아래와 같습니다.
  • 최대 밀리초 수: 2^32−1 ≈ 4,294,967,295 ms
  • 1일 = 24 * 60 * 60 * 1000 = 86,400,000 ms
  • 카운터가 오버플로하기까지 걸리는 시간 (일) ≈ 4,294,967,295/86,400,000 ≈ 49.71 일

즉, 9x 계열을 49.7일씩 재부팅 없이 사용하면, GetTickCount() API가 반환하는 값이 0으로 오버플로하는 것입니다. 결과는 사실상 무조건적인 프리징이었습니다. 선술한 바와 같이 일반 유저들은 49.7일씩 써보기도 전에 컴퓨터가 먼저 뻗어버렸기에 실제로 알아채기가 대단히 어려웠습니다만 임베디드나 공장 자동화 설비 등에서 9x 계열을 사용하는 경우 상당한 요주의 문제이기도 했습니다.

Credit: https://learn.microsoft.com/en-us/windows/win32/api/sysinfoapi/nf-sysinfoapi-gettickcount64

NT 커널을 포함한 대부분의 현대 OS는 카운터를 unsigned 64비트 정수에 담으므로 이제는 사실상 없다고 볼 수 있을 것입니다.

thread.c/thread.h

아무튼, 해결책을 찾았으니 이제 실제로 구현할 차례입니다. 우선 Pintos의 스레드 관련 부분인 thread.h부터 보겠습니다.

wakeup_tick 변수 추가

아래와 같이 thread.h의 struct thread 선언부에서, int64_t wakeup_tick;를 추가합니다. 이는 해당 스레드의 깨울 시각을 저장하는 변수입니다.

슬립 리스트 전역 변수 추가

다음은 thread.c입니다. 아래와 같이 두 개의 전역 변수를 선언합니다.

• static struct list sleep_list; 깨울 순서. insert 시, list_insert_ordered()로 wakeup_tick 기준 오름차순을 유지합니다.
• static int64_t next_tick_to_awake; 최적화 요소. 모든 잠들어 있는 스레드들 중 가장 다음에 깨워야 할 스레드의 틱을 담는 변수입니다. 가령, 스레드 A, B, C, D가 잠들어 있고, 각각 다음 깨워야 할 시점이 1200틱, 1220틱, 1180틱, 1370틱이라면, next_tick_to_awake에는 1180이라는 값이 들어가 있을 것입니다. 이를 통해, 매 인터럽트마다 리스트를 순회하는 게 아니라, 이때만 잠든 스레드들을 확인하게 됩니다.

함수 추가

아래와 같이 필요한 함수들을 thread.c에 추가합니다.

/**
 * thread_sleep: Alarm clock 과제. 
 *   Thread를 sleep queue에 삽입하고 blocked 상태로 만들어 대기.
 * 
 * @param ticks: 해당 스레드의 틱
 */
void thread_sleep(int64_t ticks){
	struct thread* this;
	this = thread_current();

	if(this == idle_thread){
        ASSERT(0);
	}else{
		enum intr_level old_level = intr_disable();  // 인터럽트 일시중지
		update_next_tick_to_awake(this->wakeup_tick = ticks); // Awake ticks 업데이트
		list_push_back(&sleep_list, &this->elem); // sleep_list에 넣음
		thread_block(); // 해당 스레드를 블록
		intr_set_level(old_level); // 인터럽트 재개
	}
}

/** 
 * thread_awake - Alarm Clock 과제. wakeup_tick값이 인자로 받은 ticks보다 크거나 같은 스레드를 깨움.
 *   현재 대기 중인 스레드들의 wakeup_tick 중 최솟값을 next_tick_to_awake 전역변수에 저장.
 */
void thread_awake(int64_t wakeup_tick){
	next_tick_to_awake = INT64_MAX;
	struct list_elem* sleeping = list_begin(&sleep_list);  // 자고 있는 스레드 전체를 가져옴.

	while(sleeping != list_end(&sleep_list)){ // 리스트 끝까지
		struct thread* thr = list_entry(sleeping, struct thread, elem);

		if(thr->wakeup_tick <= wakeup_tick){ // 깨울 때면
			sleeping = list_remove(&thr->elem); // 해당 스레드를 삭제
			thread_unblock(thr); // 해당 스레드의 블록 해제
		}else{ // 아니면
			sleeping = list_next(sleeping); // 다음 자는 스레드로 넘어감
			update_next_tick_to_awake(thr->wakeup_tick); // wakeup_tick를 업데이트
		}
	}
}

/** 
 * update_next_tick_to_awake - Alarm Clock 과제.
 *   전역변수인 next_tick_to_awake를, ticks와 비교하여, 둘 중 더 작은 값으로 업데이트.
*/
void update_next_tick_to_awake(int64_t ticks) {
    next_tick_to_awake = (next_tick_to_awake > ticks) ? ticks : next_tick_to_awake; // 최솟값 가진 녀석
}

/** 
 * get_next_tick_to_awake - Alarm Clock 과제.
 *   전역변수인 next_tick_to_awake를 리턴.
*/
int64_t get_next_tick_to_awake(void) {
    return next_tick_to_awake;
}

함수 수정

void thread_init(void)를 아래와 같이 구성합니다.

void
thread_init (void) {
	ASSERT (intr_get_level () == INTR_OFF);

	/* Reload the temporal gdt for the kernel
	 * This gdt does not include the user context.
	 * The kernel will rebuild the gdt with user context, in gdt_init (). */
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);

	/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);
	
    /*-- Alarm Clock 과제 --*/
    list_init (&sleep_list); 
    /*-- Alarm Clock 과제 --*/

	/* Set up a thread structure for the running thread. */
	initial_thread = running_thread ();
	init_thread (initial_thread, "main", PRI_DEFAULT);
	initial_thread->status = THREAD_RUNNING;
	initial_thread->tid = allocate_tid ();
}

즉, thread.c의 전역 변수로 넣었던 슬립 리스트의 초기화가 포함되는 것입니다.

그 다음, tid_t thread_create()를 아래와 같이 구성합니다.

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;

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

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t) kernel_thread;
	t->tf.R.rdi = (uint64_t) function;
	t->tf.R.rsi = (uint64_t) aux;
	t->tf.ds = SEL_KDSEG;
	t->tf.es = SEL_KDSEG;
	t->tf.ss = SEL_KDSEG;
	t->tf.cs = SEL_KCSEG;
	t->tf.eflags = FLAG_IF;

	/* Add to run queue. */
	thread_unblock (t);
    
    /*-- Alarm clock 구현 --*/
	if(t->priority > thread_current()->priority)
		thread_yield();
    /*-- Alarm clock 구현 --*/
    
	return tid;
}

추가한 내용 자체는 두 줄에 불과하지만 설명이 다소 필요한 부분입니다. Pintos의 alarm clock 단계에서는 단순한 sleep/wakeup 기능뿐만 아니라, 스레드 우선순위 기반의 스케줄링이 동작함을 전제로 합니다. 즉, 현재 실행 중인 스레드보다 더 높은 우선순위를 가진 스레드가 새로 생성되었을 경우, 해당 스레드가 즉시 CPU를 사용할 수 있도록 양보(yield)해야 합니다.

기본 thread_create() 로직에서는 새 스레드를 ready queue에 추가(thread_unblock)한 뒤 바로 현재 스레드가 계속 실행되지만, 위와 같은 조건을 추가함으로써 스케줄러가 즉시 context switch를 일으킬 수 있도록 해줍니다. 이로써 우선순위 기반 선점 스케줄링(priority preemption)도 자연스럽게 구현되는 것입니다.

즉, 이 코드는 "새로 생성한 스레드가 현재 스레드보다 우선순위가 높다면, 자발적으로 양보(thread_yield)"하게 하여 커널이 새로 생성한 high-priority thread를 빠르게 실행할 수 있게 도와주는 역할을 합니다. 만약 이 부분이 없으면, thread_create() 이후 명시적인 yield 또는 blocking이 일어나기 전까지는 새 스레드가 실행될 기회를 갖지 못하게 되어, 선점형 스케줄링이 제대로 작동하지 않게 됩니다.

timer.c

timer_interrupt()를 아래와 같이 구성합니다.

/* Timer interrupt handler. */
/* 매 tick마다 timer 인터럽트 시 호출되는 함수
     sleep queue에서 깨어날 thread가 있는지 확인.
*/
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++; 
    thread_tick ();	

	if (get_next_tick_to_awake() <= ticks)
		thread_awake(ticks);
}

먼저, thread.c에서 추가했던 get_next_tick_to_awake()이 여기서도 호출됩니다. 이는 sleep list 안에서 가장 빨리 깨어나야 할 스레드의 wake‑up tick을 반환하는 헬퍼입니다. 

그리하여 매 tick마다 ticks(부팅 이후 누적 tick) 값과 비교해서, “지금 깨울 스레드가 있니?”를 O(1)로 판별합니다. <=를 쓰는 이유는 동일 tick에 깨워야 하는 스레드도 포함하기 위함입니다. 그 다음 sleep list에서 wake_up_tick <= ticks인 노드를 전부 빼서 ready list로 옮기고, 그 과정에서 next_tick_to_awake를 업데이트합니다.

마지막으로, timer_sleep()를 아래와 같이 구성합니다.

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

	ASSERT (intr_get_level () == INTR_ON);
	// while (timer_elapsed (start) < ticks)
	// 	thread_yield ();
	thread_sleep(start + ticks);
}

기존 방식은 앞서 언급한 바와 동일합니다. 수정된 방식은, ① thread_sleep()로 현재 스레드의 wake_up_tick 필드에 start + ticks 저장 ==> ② 자신을 sleep list에 삽입 ==> ③ next_tick_to_awake 갱신 ==> ④ thread_block()으로 블록하여, 스케줄러가 다른 스레드에게 CPU를 넘기는 과정을 거치게 됩니다.

---

결과 확인

Pintos의 thread 디렉토리에서 다시 컴파일 및 테스트합니다. 아래와 같이 alarm 관련한 것들 중 alarm-priority를 제외한 항목들에서 통과되어야 합니다 (alarm-priority는 priority scheduling 구현을 통해 자연스럽게 통과되게 됩니다).

(... 중략 ...)
make[1]: Leaving directory '/home/mihnsurk2/gitp/Mugen-Houyou/pintos-kaist/threads/build'
pintos -v -k -T 60 -m 20   -- -q   run alarm-single < /dev/null 2> tests/threads/alarm-single.errors > tests/threads/alarm-single.output
perl -I../.. ../../tests/threads/alarm-single.ck tests/threads/alarm-single tests/threads/alarm-single.result
pass tests/threads/alarm-single
pintos -v -k -T 60 -m 20   -- -q   run alarm-multiple < /dev/null 2> tests/threads/alarm-multiple.errors > tests/threads/alarm-multiple.output
perl -I../.. ../../tests/threads/alarm-multiple.ck tests/threads/alarm-multiple tests/threads/alarm-multiple.result
pass tests/threads/alarm-multiple
pintos -v -k -T 60 -m 20   -- -q   run alarm-simultaneous < /dev/null 2> tests/threads/alarm-simultaneous.errors > tests/threads/alarm-simultaneous.output
perl -I../.. ../../tests/threads/alarm-simultaneous.ck tests/threads/alarm-simultaneous tests/threads/alarm-simultaneous.result
pass tests/threads/alarm-simultaneous
pintos -v -k -T 60 -m 20   -- -q   run alarm-priority < /dev/null 2> tests/threads/alarm-priority.errors > tests/threads/alarm-priority.output
perl -I../.. ../../tests/threads/alarm-priority.ck tests/threads/alarm-priority tests/threads/alarm-priority.result
pass tests/threads/alarm-priority
pintos -v -k -T 60 -m 20   -- -q   run alarm-zero < /dev/null 2> tests/threads/alarm-zero.errors > tests/threads/alarm-zero.output
perl -I../.. ../../tests/threads/alarm-zero.ck tests/threads/alarm-zero tests/threads/alarm-zero.result
pass tests/threads/alarm-zero
pintos -v -k -T 60 -m 20   -- -q   run alarm-negative < /dev/null 2> tests/threads/alarm-negative.errors > tests/threads/alarm-negative.output
perl -I../.. ../../tests/threads/alarm-negative.ck tests/threads/alarm-negative tests/threads/alarm-negative.result
pass tests/threads/alarm-negative
pintos -v -k -T 60 -m 20   -- -q   run priority-change < /dev/null 2> tests/threads/priority-change.errors > tests/threads/priority-change.output
perl -I../.. ../../tests/threads/priority-change.ck tests/threads/priority-change tests/threads/priority-change.result
pass tests/threads/priority-change
(... 중략 ...)

---

마치며

Alarm clock 파트는 Pintos의 스레드 상태 전이(thread_block, thread_unblock), 스케줄링, 인터럽트 핸들링, 그리고 동기화 메커니즘의 기초를 이해하는 데 매우 중요한 과제였습니다. Busy Waiting이라는 비효율적인 방식을 이벤트 기반의 효율적인 Sleep/Wakeup 메커니즘으로 바꾸는 과정을 통해 운영체제가 시간을 어떻게 관리하고 스레드를 어떻게 제어하는지 감을 잡을 수 있습니다.  다음 글에서는 우선순위 스케줄링에 대해 이야기해 보겠습니다.