[Pintos-KAIST] Project 1 :: Alarm Clock (Sleep-Awake 방식의 Alarm Clock 구현하기)

Alarm Clock

💡 스레드를 잠시 재웠다가 일정 시간이 지나면 깨우는 기능인
Alarm Clock을 Busy-waiting 방식에서 Sleep-Awake 방식으로 변경하자!

 

1) Busy-waiting과 Sleep-Awake의 차이

Busy waiting은 특정 조건이 매우 빠르게 충족될 것으로 예상될 때 사용되는 것이 적합하며,
Alarm clock은 일정 시간 이후에 수행해야 하는 작업이 있을 때 사용된다.

 

Busy waiting

• 프로그램이 다른 작업을 수행하며 기다리는 대신, 특정 조건이 충족될 때까지 반복적으로 체크를 하면서 기다리는 것을 말한다.
• 이러한 방식은 CPU 자원을 낭비하고, 다른 스레드가 실행되는 기회를 줄여 성능 저하를 야기할 수 있다.

 

Alarm Clock

• 프로그램이 일정 시간이 지난 후에 다음 작업을 수행하도록 예약하는 것이다.
• 이 경우, 프로그램은 대기 상태에 들어간 동안 CPU 사이클을 사용하지 않기 때문에, Busy waiting 방식에 비하여 CPU 자원을 절약할 수 있다.

 

2) Busy-waiting 방식으로 구현된 기존의 코드

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_sleep() 함수는 스레드를 ticks만큼 일시 중지하는 함수이다.
• 현재 구현된 방식으로는, 현재 타이머 시간과 ticks를 비교해서 아직 ticks에 도달하지 않았으면 thread_yield() 함수를 호출하여 다른 스레드에게 CPU를 양보한다.
• 하지만 CPU를 양보 받은 스레드도 아직 ticks에 도달하지 않은 경우에는, CPU를 양보 받자마자 바로 다시 다른 스레드에게 양보를 해야 한다. (즉, 불필요한 Context switching이 많이 일어날 수 있다.)
• 따라서 아직 ticks에 도달하지 않은 스레드가 깨워지는 것이 큰 비효율을 발생시키고, 이것을 해결하는 것이 이번 과제의 목적이다.

 

🤔 tick이란?

• tick은 일정 시간 간격으로 발생하는 시스템의 기본적인 시간 단위이다.
• 시스템 타이머는 이러한 틱을 생성하며, 일반적으로 운영 체제는 이러한 틱을 사용하여 시스템 상태를 유지하고 다양한 작업을 스케줄링한다.
• 예를 들어, 시스템 타이머가 100번의 틱을 초당 생성한다면, 운영 체제는 1초를 100개의 틱으로 나누어 시스템 상태를 업데이트하고 작업을 스케줄링한다.
• 이러한 방식으로 시스템이 일관된 방식으로 동작할 수 있도록 한다.

 

tick을 사용하는 이유

1) 틱은 고정된 간격으로 발생하기 때문에, 운영 체제가 특정 작업을 실행하기 위해 기다리는 시간을 정확히 계산할 수 있다.

  - 예를 들어, 운영 체제가 특정 작업을 5초 후에 실행하도록 스케줄링했다면, 운영 체제는 틱이 발생하는 시간을 이용하여 정확한 시간을 측정한다. 이를 통해 운영 체제는 특정 작업이 정확히 5초 후에 실행될 것임을 보장할 수 있다.

2) 시간 단위를 사용하는 경우, 시스템이 다른 작업을 수행하면서 시간이 흐를 때마다 시간을 업데이트해야 하기 때문에 부하가 커질 수 있다.

  - 따라서, 틱 단위로 시간을 추적함으로써 시스템의 부하를 줄이고 일관성을 유지할 수 있다.
  - 틱을 업데이트하는 것도 일정한 부하를 발생시키지만, 이 부하는 대부분 무시할 수준이다. 틱은 하드웨어에서 매우 빠르게 처리될 수 있는 단위이기 때문이다.

3) 틱을 사용하여 CPU 사용률을 조절할 수 있다.

  - 틱의 간격을 더 작게 조정하면, 시스템은 더 자주 인터럽트를 처리하여 작업을 스케줄링할 수 있게 된다.
  - 이는 우선순위가 높은 작업이 더 빠르게 실행될 수 있도록 하여 시스템의 반응성을 향상시키는 데 도움이 된다.

 

3) Sleep-Awake 방식

변경 방안

현재
스레드가 잠들면 모두 스케줄링 대기열인 ready_list에 추가하고 있어서,
아직 깰 시간이 되지 않은 (ticks에 도달하지 않은) 스레드가 깨워지는 일이 발생한다!

 

변경안
새로운 방식에서는 잠든 스레드가 깰 시간(ticks에 도달할 때)까지는 ready_list에 추가하지 않고,
깰 시간(ticks)에 도달한 경우에만 ready_list에 추가하는 방식으로
아직 ticks에 도달하지 않은 스레드가 깨워지는 일을 없게 만들 것이다!

 

구현 방법

(1) sleep list 선언 & 초기화

• ticks에 도달하지 않은 스레드를 담을 연결 리스트 sleep_list를 선언하고 thread_init에서 초기화한다.

    /* thread.c */

    // 1. sleep_list 선언
    static struct list sleep_list;

    ...

    // 2. sleep_list 초기화
    void thread_init (void) {

    ...

        list_init (&sleep_list);

    ...

    }

 

(2) thread 구조체에 필드 추가

• 스레드 구조체에 일어날 시각인 ticks를 저장할 wakeup_ticks 필드를 추가한다.

    /* thread.h */

    struct thread
    {
        /* Owned by thread.c. */
        tid_t tid;                   /* Thread identifier. */
        enum thread_status status; /* Thread state. */
        char name[16];               /* Name (for debugging purposes). */
        int priority;               /* Priority. */

        int64_t wakeup_ticks;       // 일어날 시각 추가

    ...

    };

 

(3) 스레드 재우기 로직 변경

timer_sleep

• 기존 코드에 있는 thread_yield() 함수를 호출하면 잠든 스레드가 ready_list에 삽입된다.
• 잠든 스레드는 ready_list가 아닌 sleep_list에 삽입하는 thread_sleep() 함수를 호출한다.
  • thread_sleep() 함수는 아래에서 새로 선언한다.

    /* timer.c */

    void timer_sleep(int64_t ticks)
    {
        int64_t start = timer_ticks(); // 현재 시각
        ASSERT(intr_get_level() == INTR_ON);
        thread_sleep(start + ticks); // 현재 시각 (start) + 잠들 시간 (ticks)
    }

thread_sleep

• 잠든 스레드를 sleep_list에 삽입하는 함수를 새로 선언한다.
• 스레드 구조체에 일어날 시각인 ticks를 저장한다.
• sleep_list에 ticks가 작은 스레드가 앞부분에 위치하도록 정렬하여 삽입한다.
  • 정렬에 활용할 cmp_thread_ticks() 함수는 아래에서 새로 선언한다.
• 현재 스레드는 잠들어야 하니 thread_block() 함수를 호출한다.

    /* thread.h */

    void thread_sleep (int64_t ticks);

    /* thread.c */

    void thread_sleep(int64_t ticks)
    {
        struct thread *curr;
        enum intr_level old_level;
        old_level = intr_disable(); // 인터럽트 비활성

        curr = thread_current();     // 현재 스레드
        ASSERT(curr != idle_thread); // 현재 스레드가 idle이 아닐 때만

        curr->wakeup_ticks = ticks;     // 일어날 시각 저장
        list_insert_ordered(&sleep_list, &curr->elem, cmp_thread_ticks, NULL); // sleep_list에 추가
        thread_block(); // 현재 스레드 재우기

        intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
    }

cmp_thread_ticks

• sleep_list에 일어날 시간이 이른 스레드가 앞부분에 위치하도록 정렬할 때 사용할 정렬 함수를 새로 선언한다.

    /* thread.h */

    bool cmp_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux);

    /* thread.c */

    // 두 스레드의 wakeup_ticks를 비교해서 작으면 true를 반환하는 함수
    bool cmp_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
    {
        struct thread *st_a = list_entry(a, struct thread, elem);
        struct thread *st_b = list_entry(b, struct thread, elem);
        return st_a->wakeup_ticks < st_b->wakeup_ticks;
    }

 

(4) 스레드 깨우기 로직 추가

timer_interrupt

• 매 tick마다 발생하는 타이머 인터럽트 핸들러를 활용해서 매 tick마다 깨울 스레드가 있는지 확인다.
• 일어날 시간이 된 스레드를 ready_list로 이동시키는 함수 thread_wakeup()을 호출한다.

    /* timer.c */

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

thread_wakeup

• sleep_list의 스레드들이 일어날 시간이 되면 ready_list로 이동시킨다.
• 현재 current_ticks보다 작거나 같은 wakeup_ticks를 가진 스레드는 모두 깨운다.
  • 여기서 ‘스레드를 깨운다’는 것은, 깨울 스레드를 sleep_list에서 제거하고 ready_list에 삽입하는 것을 의미한다.
  • 1) sleep_list에서 깨울 스레드를 제거한다. (list_remove)
  • 2) 깨울 스레드를 ready_list에 삽입하고, 상태를 THREAD_READY로 변경한다. (thread_block)

    /* thread.h */

    void thread_wakeup (int64_t global_ticks);

    /* thread.c */

    void thread_wakeup(int64_t current_ticks)
    {
        enum intr_level old_level;
        old_level = intr_disable(); // 인터럽트 비활성

        struct list_elem *curr_elem = list_begin(&sleep_list);
        while (curr_elem != list_end(&sleep_list))
        {
            struct thread *curr_thread = list_entry(curr_elem, struct thread, elem); // 현재 검사중인 elem의 스레드

            if (current_ticks >= curr_thread->wakeup_ticks) // 깰 시간이 됐으면
            {
                curr_elem = list_remove(curr_elem); // sleep_list에서 제거, curr_elem에는 다음 elem이 담김
                thread_unblock(curr_thread);        // ready_list로 이동
            }
            else
                break;
        }
        intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
    }

 

Sleep-Awake 방식의 Alarm Clock 구현 끝 ~ 💖

 

Test

/* Test: /threads/build에서 입력 */

pintos -- -q run alarm-multiple

👇🏻 구현 전

👇🏻 구현 후

0이었던 idle tick이 550으로 증가했다!