[Pintos-Kaist] Project 1 - 1 : Alarm clock 구현하기 ⏰

💡과제 목표

• Alarm은 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수이다.
• 핀토스에서는 알람 기능이 Busy-Waiting 을 이용해 구현 되어 있음.
• Busy-Waiting 방식의 문제점을 해결하고, Sleep-awake 방식의 장점을 활용하여 구현.

Busy-Waiting 방식에는 어떤 문제점이 있을까?

• 스레드가 계속 CPU를 점유하고 있어 다른 스레드의 실행을 방해할 수 있으며, CPU 리소스를 낭비한다.

그렇다면 Sleep-awake는 어떻게 문제를 해결하지?

• 스레드가 대기 상태일 때 CPU를 해제하여 다른 스레드가 실행될 수 있도록 하며, 자원과 에너지를 효율적으로 관리한다.

---

🔎 기존 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 ();
}

• time_sleep()함수는 주어진 시간 만큼 대기하는 역할을 합니다.
• timer_ticks()함수를 호출해 현재 시간을 가져와 변수 'start'에 저장합니다.
• while문을 돌며 현재 시간과 호출시간 사이의 차이가 주어진 대기 시간보다 작은 동안 반복합니다.
• timer_elapsed함수로 start로부터 경과한 시간을 반환합니다.
• thread_yield 함수로 현재 스레드가 대기 상태로 들어가고, 다른 스레드가 실행될 수 있도록 한다.

---

😴Sleep-awake🫨 구현하기

(1) Sleep list 선언 / 초기화

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

/* thread.c */ 
static struct list sleep_list;  // sleep_list 선언

...

void thread_init(void) 
{

...

	list_init(&sleep_list); // sleep_list 초기화
    
...

}

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

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

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. */

    /* Shared between thread.c and synch.c. */
    struct list_elem elem; /* List element. */
    int64_t wakeup_tick;   /* Wake up tick */
    
...

};

(3) thread 재우기 변경

thread_sleep 함수를 호출하여 현재 스레드를 대기 상태로 전환. 대기 상태로 전환된 스레드는 ticks 시간이 경과한 후에 다시 실행됨. 이때, CPU를 해제하고 다른 스레드에게 실행 기회를 양보하여 CPU와 시스템 자원을 효율적으로 관리!

/* timer.c */

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

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

    // sleep wake
    thread_sleep(start + ticks);
}

이 함수는 스레드를 대기 상태로 전환하여 특정 시간(ticks)까지 실행을 중지시키는 역할을 함.

/* thread.c */

void thread_sleep(int64_t ticks) {  // ticks 만큼 sleep
    struct thread *t = thread_current();    // 현재 스레드
    enum intr_level old_level;  // 인터럽트 레벨

    ASSERT(intr_get_level() == INTR_ON); // 인터럽트가 켜져있는지 확인
    old_level = intr_disable(); // 인터럽트 끄기
    t->status = THREAD_BLOCKED; // 스레드 상태를 BLOCKED로 변경
    t->wakeup_tick = ticks; // 깨어날 tick 설정
    list_push_back(&sleep_list, &t->elem); // sleep_list에 추가

    schedule(); // 스케줄링
    intr_set_level(old_level); // 인터럽트 레벨 복구
}

• 현재 실행 중인 스레드를 가져옴.
• 인터럽트가 활성화되어 있는지 확인.
• 현재 인터럽트 상태를 저장하고, 인터럽트를 비활성화.
• 이렇게 함으로써 스레드 상태를 변경하는 동안 다른 인터럽트가 발생하지 않도록 합니다.
• 현재 스레드의 상태를 BLOCKED로 변경하여 대기 상태로 전환합니다.
• 깨어날 시간을 설정. 현재 시간에서 주어진 대기 시간(ticks)을 더한 값으로 설정합니다.
• 스레드를 대기 리스트에 추가합니다.
• 스케줄러를 호출하여 다음으로 실행될 스레드를 선택.
• 이전에 저장한 인터럽트 상태를 복원하여 다시 활성화.

(4) thread 깨우기 추가

타이머 인터럽트가 발생할 때마다 현재 시간을 업데이트하고, 이에 따라 대기 중인 스레드를 깨우고 스레드 스케줄링을 수행.

/* timer.c */

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

특정 시간(ticks)에 도달한 스레드들을 대기 상태에서 깨우고 실행 가능한 상태로 변경.

void thread_wakeup(int64_t ticks) { // ticks가 되면 깨우기
    struct list_elem *e;   // 리스트 엘리먼트
    struct thread *t;   // 스레드
    enum intr_level old_level;  // 인터럽트 레벨

    ASSERT(intr_get_level() == INTR_OFF);   // 인터럽트가 꺼져있는지 확인
    old_level = intr_disable(); // 인터럽트 끄기
    for (e = list_begin(&sleep_list); e != list_end(&sleep_list);) {    // sleep_list 순회
        t = list_entry(e, struct thread, elem); // 스레드 가져오기
        if (t->wakeup_tick <= ticks) {  // 깨어날 시간이 되었으면
            e = list_remove(e); // 리스트에서 제거
            thread_unblock(t);  // unblock
        } else {    // 깨어날 시간이 아직 안되었으면
            e = list_next(e);   // 다음 엘리먼트로
        }
    }
    intr_set_level(old_level);  // 인터럽트 레벨 복구
}

• 현재 인터럽트 상태를 확인하여 인터럽트가 비활성화되어 있는지 확인.
• 현재 인터럽트 상태를 저장하고, 인터럽트를 비활성화하여 스레드 상태 변경 동안 다른 인터럽트가 발생하지 않도록 함.
• 대기 중인 스레드들을 순회하면서 각 스레드의 깨어나야 하는 시간을 확인.
• 주어진 시간(ticks)에 도달한 스레드를 대기 상태에서 깨워서 실행 가능한 상태로 변경.
• 스레드가 깨어날 때마다 대기 리스트에서 해당 스레드를 제거.
• 모든 작업이 완료되면 이전에 저장한 인터럽트 상태를 복원하여 다시 활성화.

---

📌 결과

Test 하는 법

/* Test: /threads/build에서 입력 */
pintos -- -q run alarm-multiple

idle틱이 550으로 증가한 것을 확인할 수 있다! 🙊

"Idle 틱"은 시스템이 어떤 작업도 수행하지 않고 대기 상태인 시간을 나타냄.
대기 중인 스레드가 깨어나서 실행될 때, CPU가 대기 상태에서 벗어나고 스레드가 실행되면서 "Idle 틱"이 발생!!