Project1: Threads - Alarm Clock

⏰ Alarm Clock 구현:

1. 목표

timer_sleep() 함수의 기존 Busy-Waiting(적극적 대기) 방식을 Blocking(수동적 대기) 방식으로 변경하여 CPU 효율성을 향상시킵니다.

2. 핵심 아이디어: Busy-Waiting vs. Blocking

기존 timer_sleep()은 스레드가 잠들지 않고, while 루프를 계속 돌며 시간이 다 됐는지 검사했습니다.

• 기존 방식 (Busy-Waiting):

  • 스레드는 READY 상태를 유지합니다.
  • 시간이 안 됐으면 thread_yield()를 호출하여 'Ready List'의 맨 뒤로 갑니다.
  • CPU를 받으면 다시 while 루프에서 시간을 검사합니다.
  • 이 과정이 반복되며 CPU가 불필요하게 낭비됩니다.

• 개선 방식 (Blocking):

  • 스레드의 상태를 BLOCKED로 변경합니다.
  • 'Sleep List'에 "깨어날 시간(awake_tick)"과 함께 스레드를 삽입합니다. (이때 리스트는 awake_tick 기준으로 정렬됩니다.)
  • 스레드는 스케줄링 대상에서 제외되어 CPU를 전혀 사용하지 않습니다.
  • 이후 타이머 인터럽트가 발생할 때마다 'Sleep List'를 검사하여, 시간이 다 된 스레드를 'Ready List'로 옮겨 깨웁니다.

📊 방식 비교 요약

특징	1. thread_yield() 방식	2. thread_sleep() 방식
대기 방식	적극적 대기 (Busy-Waiting)	수동적 대기 (Blocking / Passive-Waiting)
스레드 상태	READY (준비 큐에 계속 남아있음)	BLOCKED (준비 큐에서 제거됨)
CPU 사용	낭비가 심함 (계속 스케줄링됨)	효율적 (대기 중 CPU 사용 안 함)
용도	(비효율적)	Pintos의 알람 시계 (정확한 구현)

---

3. 구현 과정 및 주요 코드

1. 'Sleep List' 선언 및 초기화

BLOCKED 상태의 스레드 중 '시간 대기' 중인 스레드만 따로 관리할 sleep_list를 선언하고 초기화합니다.

// thread.c (전역 변수)
static struct list sleep_list;

// thread.c - thread_init() 내부
void
thread_init (void) {
    ...
    list_init (&sleep_list);
    ...
}

2. 'thread' 구조체에 'awake_tick' 필드 추가

스레드가 깨어나야 할 절대적인 시각(awake_tick)을 저장할 필드를 추가하고 초기화합니다.

// thread.h - struct thread 내부
struct thread {
    ...
    int64_t awake_tick;         /* 깨어날 시간 (ticks) */
    ...
};

// thread.c - init_thread() 내부
static void
init_thread (struct thread *t, const char *name, int priority) {
    ...
    t->awake_tick = 0;
    ...
}

3. 'timer_sleep()' 수정

기존 thread_yield() 루프를 제거하고, 새로 만들 thread_sleep()함수를 호출하도록 변경합니다.

기존 로직:

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

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

수정된 로직:

// timer.c
void 
timer_sleep (int64_t ticks) {
    // 자야 할 시간이 0 이하면 즉시 리턴
    if (ticks <= 0) {
        return;
    }

    // 현재 시각 + 자야 할 기간 = 깨어날 시각
    int64_t awake_tick = timer_ticks () + ticks;

    // 스레드를 '깨어날 시각'까지 재운다.
    thread_sleep(awake_tick);
}

4. thread_sleep() 및 정렬 함수 구현

스레드를 BLOCKED 상태로 만들고 sleep_list에 삽입하는 핵심 함수와, 리스트 정렬에 필요한 비교 함수를 구현합니다.

// thread.c

/* awake_tick이 더 작은 스레드가 리스트의 앞에 오도록 비교 */
bool 
thread_awake_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct thread *t_a = list_entry(a, struct thread, elem);
    struct thread *t_b = list_entry(b, struct thread, elem);

    return t_a->awake_tick < t_b->awake_tick;
}

/* 현재 스레드를 'awake_tick'까지 재운다. */
void 
thread_sleep(int64_t awake_tick) {
    struct thread *cur = thread_current();

    // Race Condition 방지를 위해 인터럽트 비활성화
    enum intr_level old_level = intr_disable();

    // idle 스레드는 잠들면 안 됨
    ASSERT(cur != idle_thread);
    
    // 1. 스레드에 깨어날 시간 저장
    cur->awake_tick = awake_tick;
        
    // 2. 'Sleep List'에 정렬하여 삽입 (가장 빨리 깰 스레드가 맨 앞)
    list_insert_ordered(&sleep_list, &cur->elem, thread_awake_less, NULL);

    // 3. 스레드를 BLOCKED 상태로 변경 (잠들기)
    thread_block();
    
    // 4. (나중에 깨어난 후) 인터럽트 상태 복원
    intr_set_level(old_level);
}

5. timer_interrupt() 수정

매 틱마다 ticks를 증가시키고, thread_wake_up() 함수를 호출하여 sleep_list를 검사하도록 수정합니다.

기존 로직:

/* 타이머 인터럽트 핸들러 */
static void timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
}

수정된 로직:

/* 타이머 인터럽트 핸들러 */
static void timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++; // 전역 틱 증가

    // 'Sleep List'를 검사하여 깨울 시간이 된 스레드를 깨움
    thread_wake_up(ticks); 
    
    thread_tick (); // 스케줄링 관련 처리
}

void thread_wake_up(int64_t current_ticks)
{
	while (!list_empty(&sleep_list)) {

		struct list_elem *e = list_begin(&sleep_list);
		struct thread *t = list_entry(e, struct thread, elem);

		if (t->awake_tick > current_ticks)
		{
			break;
		}

		list_remove(e);
		thread_unblock(t);
	}
}