PintOS #2 : Alarm Clock

PintOS의 코드를 구현하는 것은 상당히 난이도 있다. 여러가지 고생했고, 어디서 어떻게 막혔는지 하나하나 논하기엔 여러분들은 나의 고생이 그다지 궁금하지 않다. 그냥 GPT 없이 접근해보길 바란다. ㅋㅋ ㅠㅠ

2025.05.12 - [구현하기] - PintOS #1 : 진행 흐름도 파악하기

PintOS #1 : 진행 흐름도 파악하기

 

Alarm Clock은 정해진 시간 후에 쓰레드를 깨우고 재우는 내용을 구현하는 내용인데, 기존에 잘 작동하는 timer.c 파일에 위치한 timer_sleep() 함수의 최적화를 하는 것이 첫 번째 목표이다.

계속해서 반복문을 돌면서 현재 시간을 확인하고, 충분한 시간이 경과 할 때 까지 thread_yield() 를 호출하는데, 이것이 Busy Wait 방식으로, 앞으로 최적화 된 결과는, 상대적으로 자원을 덜 소모 한다.

카이스트 공식 문서에서 언급하는 구현 방향은 아래와 같다 :

• 실행 대기 중인 목록을 ready_list로 정의한다. 재우는 목록을 sleep_list로 정의한다.
  • 우리는 sleep_list에서 나와야만 ready_list에 들어가서 실제 실행이 일어나도록 정의 하는 것이 목표이다.
• thread는 특유의 sleep time을 부여 받은채로 이 sleep_list에 들어간다.
• sleep_list에 들어가며 sleep_list 중 가장 빨리 닿을 수 있는 시간을 따로 저장해둔다. 즉 min(item.sleepTime of Lists) 인 것
  • 이것을 min_tick 이라 하자.
• 이 min_tick이 넘는 경우에만 sleep_list의 갱신이 일어난다. 그러면서 min_tick은 다시 갱신된다.
• 이렇게 함으로써 기존의 방식보다 CPU 사용률, 전기, 모든 것을 아끼는 코드를 완성 할 수 있다.

수정 대상 코드는 thread.* 와 timer.* 이다.

timer.*

/*************************************************************
 * timer_interrupt - 타이머 인터럽트 핸들러
 *
 * 요구사항:
 * - 시스템 틱 수를 증가시켜 전체 시간 흐름을 관리
 * - 현재 실행 중인 스레드의 time slice를 갱신해야 함
 * - sleep_list에 등록된 스레드 중 깨어날 시간이 도래한 경우 깨워야 함
 * 
 * 기능:
 * - 전역 변수 ticks를 1 증가시킴
 * - thread_tick()을 호출하여 현재 스레드의 time slice 소모 체크
 * - closest_tick(다음 깨어날 시각)과 비교하여 thread_awake() 호출 여부 결정
 *
 * 주의:
 * - 인터럽트 컨텍스트에서 실행되므로 thread_block()과 같은 동작은 금지
 * - closest_tick은 sleep_list에 있는 가장 이른 wakeup_tick 값을 나타냄
 * 
 * [AS-IS]
 * - 단순히 ticks 증가 및 thread_tick() 호출만 수행
 * → sleep 상태의 스레드를 깨우는 기능이 없음
 * 
 * [TO-BE]
 * - closest_tick <= ticks일 때만 thread_awake()를 호출하여,
 *   sleep_list에서 깨어날 시각이 지난 스레드를 READY 상태로 전환
 * → 정확하고 효율적인 알람 기능 제공
 *************************************************************/
static void
timer_interrupt (struct intr_frame *args UNUSED) 
{
	ticks++;						// 전체 시스템 tick 수 증가
	thread_tick ();					// 현재 running 중인 thread의 tick 처리 및 time slice 만료 검사
	if (closest_tick() <= ticks)  	// 가장 이른 wakeup_tick(closest_tick)이 현재 tick보다 작거나 같다면
		thread_awake(ticks);		// → 깨어날 시간이 도래한 스레드가 존재할 수 있으므로 thread_awake() 호출
}

/*************************************************************
 * timer_sleep - 지정된 tick 수만큼 현재 스레드를 재움
 *
 * 요구사항:
 * - busy-wait 없이 정확한 시간 동안 스레드를 BLOCKED 상태로 전환
 * - 인터럽트를 활성화한 상태에서 호출해야 함
 * 
 * 기능:
 * - 현재 tick을 기준으로, 깨어날 tick을 계산하여 thread_sleep() 호출
 * - sleep_list에 현재 스레드를 추가하고 BLOCKED 상태로 전환
 * 
 * 반환:
 * - 없음 (void)
 * 
 * 주의:
 * - ticks가 0 이하일 경우 sleep을 수행하지 않음
 * - intr_get_level() == INTR_ON 상태에서만 호출 가능
 * - sleep 중인 스레드는 timer_interrupt()에 의해 주기적으로 체크됨
 * 
 * [AS-IS]
 * - busy-wait 방식 사용
 * - while 루프에서 timer_elapsed()로 경과 시간 확인 후 thread_yield() 호출
 * → RUNNING 상태 유지하며 CPU 자원 낭비
 * 
 * [TO-BE]
 * - thread_sleep(start + ticks)를 통해 BLOCKED 상태로 진입
 * - thread_awake()가 타이머 인터럽트 시점마다 sleep_list를 확인하고 깨어남
 * → 정확하고 효율적인 sleep 가능 (CPU 절약)
 *************************************************************/
void
timer_sleep (int64_t ticks) 
{
	if (ticks <= 0) return;
	int64_t wakeup_tick = timer_ticks() + ticks;
	thread_sleep(wakeup_tick);
}

 

thread.*

/*************************************************************
 * thread_awake - 슬립 리스트에서 깨울 시간이 지난 스레드들을 깨움
 *
 * 기능:
 * - sleep_list에 있는 스레드 중, current_tick ≤ 현재 tick인 스레드를 READY 상태로 전환
 * - list_remove() 및 thread_unblock()을 통해 스레드 깨움
 * - 남아 있는 스레드들의 current_tick 중 가장 이른 값으로 awake_closest_tick 갱신
 *
 * 동기화:
 * - 인터럽트 컨텍스트에서 실행되므로 별도 락 불필요
 * - list_remove() 시 반복자 갱신에 주의 필요
 *
 * 호출 위치:
 * - timer_interrupt() 내부에서, ticks ≥ awake_closest_tick일 때 호출
 *
 * 제약 조건:
 * - BLOCKED 상태가 아닌 스레드를 깨우면 안 됨 (thread_unblock 제약)
 * - thread_block() 호출 금지 (인터럽트 컨텍스트이므로)
 *
 * 요구사항:
 * - busy-wait 없이 정확한 tick 기반 sleep/wakeup 동작 보장
 * - awake_closest_tick 값을 매 tick마다 갱신하여 불필요한 검사 최소화
 *************************************************************/
void
thread_awake (int64_t current_tick)
{
    awake_closest_tick = INT64_MAX;  // 슬립 리스트를 순회하며 가장 빠른 wakeup_tick으로 초기화

    struct list_elem *sleeping = list_begin(&sleep_list);  // sleep_list 순회 시작

    while (sleeping != list_end(&sleep_list)) {
        struct thread *th = list_entry(sleeping, struct thread, elem);  // 요소를 thread 구조체로 변환

        if (current_tick >= th->wakeup_ticks && th->status == THREAD_BLOCKED) {
            struct list_elem *next = list_remove(sleeping);  // 리스트에서 제거 후 다음 요소 저장
            thread_unblock(th);  // BLOCKED 상태 → READY 상태로 전환
            sleeping = next;  // 다음 요소로 이동
        } else {
            update_closest_tick(th->wakeup_ticks);  // 남은 thread 중 가장 가까운 wakeup_tick 갱신
            break;  // 오름차순 정렬이므로 더 이상 확인할 필요 없음
        }
    }
}

/**********************************************************
 * thread_sleep - 현재 실행 중인 스레드를 지정한 틱 수만큼 재움
 *
 * 기능:
 * - idle_thread는 재우지 않음
 * - 현재 스레드를 sleep_list에 추가하고 BLOCKED 상태로 전환
 * - wakeup_ticks을 현재 시간 + ticks로 설정
 * - (global) awake_closest_tick 갱신
 * - thread_block() 호출로 스케줄러 대상에서 제외
 *
 * 동기화:
 * - 인터럽트를 비활성화한 상태에서 sleep_list에 접근
 *
 * 호출:
 * - timer_sleep() 함수에서 호출됨
 **********************************************************/
void
thread_sleep (int64_t wakeup_tick) 
{
    struct thread *cur = thread_current(); // 현재 실행중인 스리드 해석

    if (cur == idle_thread) return;       // idle 스리드는 잠을 할 필요 없음

    enum intr_level old_level = intr_disable(); // 동기화 복잡화 목적으로 인터럽트 비활성화

    cur->wakeup_ticks = wakeup_tick; // 지정된 잠을 기간의 종료 tick을 저장
    update_closest_tick(wakeup_tick); // 가장 보기 가까운 tick 갱신
    list_insert_ordered(&sleep_list, &cur->elem, cmp_wakeup_tick, NULL); // wakeup_tick 까지 정렬된 순서로 삽입
    thread_block(); // 현재 스리드를 BLOCKED 상태로 변경 후 스케줄러 대상\uc5d에서 제제

    intr_set_level(old_level); // 이전 인터럽트 상태로 복원

    /* ❌ 기존 busy-wait 구조에서 지정 (AS-IS)
    cur->wakeup_ticks = timer_ticks() + ticks;      // 현재 시간 + ticks 값 계산해서 wakeup_ticks 설정 */

    // // 중복 삽입 방지를 위해 무적가로써 이미 sleep_list에 포함되어 있는지 확인
    // if (list_contains(&sleep_list, &cur->elem))
    // 	list_remove(&cur->elem); // 포함되었다면 제거
}

static bool 
cmp_wakeup_tick(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct thread *ta = list_entry(a, struct thread, elem);
    struct thread *tb = list_entry(b, struct thread, elem);
    return ta->wakeup_ticks < tb->wakeup_ticks;
}

배경 지식을 다 설명하는게 마냥 쉽지가 않다. 신경써보려고 한다..