PintOS_Alarm Clock

자 이제 첫번째 과제 시작해보겠어요

 

Pintos 프로젝트를 처음 시작하면 timer_sleep()이라는 함수를 마주하게 됩니다

그게 뭐시냐

이 함수는 스레드가 일정 시간(tick 단위) 동안 “잠들어 있도록” 만들어주는 함수입니다

 

기본 구현

int64_t start = timer_ticks();
while (timer_elapsed(start) < ticks)
    thread_yield();

언뜻보기엔 간단하고 직관적이지만 큰 문제점이 발생합니다

Busy Waiting!

위 코드에서 스레드는 sleep하는 동안 계속 thread_yield를 호출하면서 cpu를 차지한 채로 돌고 있습니다

실제로는 아무 일도 하지 않지만,

"계속 깨어나야하나?"를 확인하며 cpu를 소모하는 방식인데요

• cpu 자원 낭비
• 다른 스레드가 실행될 기회를 빼앗음
• 전력 소비 증가

등의 문제로 절대 비효율적인거죠

 

그래서 이 과제에서 원하는 것이 무엇이냐하면

스레드는 진짜로 자고 있을 땐 BLOCKED상태로 전환되어, 스케줄러가 cpu를 할당하지 않도록 만드는 것입니다

이렇게요

그럼 이제 대충 첫 과제(1-1) 내용은 파악했고 뭘 해야하느냐 라고 하면

일단 어떤 구조로 구현할지를 파악해봅시다

1. 스레드가 timer_sleep()을 호출하면
2. 지정한 시간이 될 때까지 BLOCKED 상태로 들어간다
3. 타이머 인터럽트가 매 tick마다 확인해서,
4. 깨어날 시간이 된 스레드를 다시 READY 상태로 전환시킨다

이렇게 하면 Busy Waiting 없이 진짜로 자고 있다가 깨어나는 구조가 됩니다

 

이제 좀 더 세부적으로 들어가볼까요

---

timer.c

 

일단 문제의 시발점이라 해야하나요..

암튼 timer_sleep를 수정해줍니다

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

	ASSERT (intr_get_level () == INTR_ON);
	if (timer_elapsed (start) < ticks)
		thread_sleep(start + ticks);	//현재 tick + 대기시간
}

 

 

timer_sleep()은 커널이 외부에서 호출하는 함수가 아니라,

현재 실행 중인 커널 스레드가 자기 자신을 지정된 시간 동안 BLOCK 상태로 전환하기 위해 직접 호출하는 함수입니다

 

실제 사용은 thread_create()를 통해 만들어진 스레드 내부에서 이루어지며,

이 스레드는 timer_sleep()을 통해 스스로 잠들고,

지정된 시간이 지나면 thread_awake()에 의해 다시 깨어나게 됩니다

 

주어진 tick 동안 스레드를 BLOCKED 상태로 전환시킵니다

내부에서는 현재 tick 기준으로 “언제 깨어나야 하는지” 계산하여

thread_sleep() 함수에 넘겨 실제로 BLOCK 처리하게 합니다

 

참고로 이 구조는 KAIST Pintos 슬라이드에서 제안한 구조를 따라 구현한 것입니다

 

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_awake(ticks);
}

• 이 함수는 매 tick마다 자동으로 호출되는 인터럽트 핸들러입니다
• 여기서 thread_awake()를 호출해, “시간이 된 애들을 깨우는 일”을 맡겨요

---

thread.c

 

암튼 이제! 스레드가 언제 깨어나야하는지를 기억해야겠죠?

struct thread에 wake_up_tick 필드를 추가해줍니다

int64_t wake_up_tick;

• 스레드가 언제 깨어나야 하는지 기억하기 위해서
• thread_sleep() 시 이 값을 세팅하고,
• thread_awake() 시 현재 tick과 비교하여 깨움

sleep_list도 사용해야 합니다

static struct list sleep_list;

왜 WHY?

• BLOCKED 상태의 스레드들을 따로 관리할 슬립 큐가 필요함
• 단순히 스레드 상태만 BLOCK으로 바꾸면 안 되고,
• 정확한 깨울 시간을 기준으로 리스트를 정렬해 관리해야 함

기존 busy waiting을 제거하고 진짜 block 시키기위한 함수를 추가해줍니다

void thread_sleep(int64_t wakeup_tick) {
    struct thread *cur = thread_current();  // 현재 실행 중인 스레드 가져오기

    // idle_thread는 절대 재우면 안 됨
    if (cur == idle_thread)
        return;

    enum intr_level old_level = intr_disable(); // 슬립 리스트 조작 전 인터럽트 비활성화 (race condition 방지)

    cur->wake_up_tick = wakeup_tick; // 스레드가 언제 깨어나야 할지 저장
    list_insert_ordered(&sleep_list, &cur->elem, compare_wake_up_tick, NULL); // 정렬된 채로 sleep_list에 삽입
    thread_block(); // 스레드 상태를 BLOCKED로 바꾸고 CPU 양보

    intr_set_level(old_level); // 인터럽트 상태 복원
}

• 현재 스레드의 wake_up_tick을 기록하고,
• sleep_list에 삽입 후 BLOCKED 상태로 전환

 

list_insert_ordered()함수를 사용하기 위해 비교 함수도 만들어줍니다

// 두 스레드의 wake_up_tick 값을 비교해서
// a가 b보다 먼저 깨어나야 하면 true를 반환한다.
// → list_insert_ordered()에 넘겨줄 비교 함수로 사용됨
static bool compare_wake_up_tick(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    // list_elem 포인터 a, b를 각각 thread 구조체로 캐스팅
    struct thread *t1 = list_entry(a, struct thread, elem);
    struct thread *t2 = list_entry(b, struct thread, elem);

    // 깨어나야 할 시각이 더 빠른 쪽이 앞으로 오게 정렬
    return t1->wake_up_tick < t2->wake_up_tick;
}

• 슬립 리스트에 들어가는 스레드들은 wake_up_tick 오름차순으로 정렬됨
• 그래야 thread_awake()에서 앞에서부터 효율적으로 검사 가능함

시간이 지난 애들을 대기 상태로 되돌려줄 함수도 필요하겠죠

// 현재 ticks 값을 기준으로
// sleep_list 안에 있는 스레드 중 wake_up_tick이 지난 애들을 READY 상태로 되돌린다.
void thread_awake(int64_t now_tick) {
    // sleep_list의 맨 앞부터 순회 시작 (정렬되어 있기 때문)
    struct list_elem *e = list_begin(&sleep_list);

    // 리스트 끝까지 순회 (또는 중간에 break될 수도 있음)
    while (e != list_end(&sleep_list)) {
        // e가 가리키는 요소를 thread 구조체로 변환
        struct thread *t = list_entry(e, struct thread, elem);

        // 깨어날 시간이 된 경우
        if (t->wake_up_tick <= now_tick) {
            // 리스트에서 해당 요소를 제거하고 다음 요소로 e 갱신
            e = list_remove(e);

            // 해당 스레드를 READY 상태로 전환
            thread_unblock(t);
        } else {
            // 리스트가 정렬되어 있기 때문에, 더 뒤에 있는 스레드는 아직 깰 시간이 아님
            break;
        }
    }
}

• 매 tick마다 호출되어 sleep_list를 순회하며 깨어날 스레드들을 READY 상태로 돌림
• wake_up_tick <= 현재 tick 조건만 만족하면 thread_unblock()
• 그래서 timer_interrupt 함수에 thread_awake가 추가 되었던 것입니다

---

정리하자면

[1] 사용자 코드에서 호출
    ↓
timer_sleep(ticks)
    ↓
thread_sleep(current_tick + ticks)
    ↓
┌────────────────────────────────────────────┐
│ 현재 스레드의 wake_up_tick 설정            │
│ sleep_list에 정렬 삽입                     │
│ thread_block() 호출 → BLOCKED 상태 전환    │
└────────────────────────────────────────────┘

                 ↓ (시간 흐름, 틱 증가)
      ┌────────────────────────────────┐
      │ 매 tick마다 호출됨 (인터럽트) │
      │ timer_interrupt()             │
      │   └── ticks++                 │
      │   └── thread_awake(ticks)     │
      └────────────────────────────────┘
                       ↓
   ┌─────────────────────────────────────────────┐
   │ sleep_list에서 wake_up_tick ≤ ticks 인 스레드 │
   │ → thread_unblock() 호출                      │
   │ → READY 상태로 전환, ready_list에 삽입        │
   └─────────────────────────────────────────────┘

                 ↓
         스케줄러가 READY 중 우선순위에 따라
         해당 스레드를 다시 RUNNING 상태로

 

단계	설명
timer_sleep()	외부 호출 인터페이스 (몇 틱 동안 자라)
thread_sleep()	현재 스레드의 깨울 시점 기록 + BLOCK
sleep_list	BLOCK된 스레드 저장, 깨울 시간 기준 정렬
thread_awake()	매 tick마다 sleep_list 순회 → 깨어날 스레드 READY로
thread_unblock()	BLOCK → READY 상태 전환
thread_block()	READY → BLOCK 상태 전환
timer_interrupt()	ticks++ & thread_awake() 호출 (핵심 루프)

 

 

이런 흐름입니다

그래서 예시로 alram_single 테스트 하나를 돌려보면

이런 결과를 받아볼 수 있습니다

 

대충 설명드리자면

5개의 스레드를 각각 다른 시간 간격으로 한 번씩만 잠들게 하고, 각 스레드가 정확한 시간에 깨어나는지 확인하는 테스트입니다

 

실제로는 각 스레드가 timer_sleep()을 호출하고,

내부적으로는 thread_sleep() → BLOCKED 상태 → 시간이 되면 thread_awake()로 복귀하는 구조입니다

 

실행 흐름

(alarm-single) Creating 5 threads to sleep 1 times each.
(alarm-single) Thread 0 sleeps 10 ticks each time,
(alarm-single) thread 1 sleeps 20 ticks each time, and so on.

• Thread 0: 10 ticks 후 깸
• Thread 1: 20 ticks 후 깸
• …
• Thread 4: 50 ticks 후 깸

실행 결과

(alarm-single) thread 0: duration=10, iteration=1, product=10
(alarm-single) thread 1: duration=20, iteration=1, product=20
(alarm-single) thread 2: duration=30, iteration=1, product=30
(alarm-single) thread 3: duration=40, iteration=1, product=40
(alarm-single) thread 4: duration=50, iteration=1, product=50

• duration: 몇 tick 동안 잠들었는지
• iteration: 몇 번째 반복인지 (여기선 모두 1)
• product: duration × iteration → 순서 확인용 수치

 

🟢 결과가 오름차순으로 출력됨 → 정확한 시간에 깨어남을 의미함

 

시스템 정보

Timer: 291 ticks
Thread: 250 idle ticks, 42 kernel ticks, 0 user ticks
Console: 1026 characters output

• 전체 291 ticks 동안 테스트 실행
• 대부분의 시간 동안 idle 상태 (스레드가 sleep 중이었다는 뜻)
• kernel thread만 사용됨 (user space 없음)