[크래프톤 정글] Pintos-project1-AlaramClock 구현 하기

Timer Interrupt 를 이용한 Aalram Clock 기능 구현 하기

본 포스트 는 Pint OS 의 Project1 의 기능중 Alaram Clock 구현에 대한 내용을 담고 있습니다. 관련 용어는 이전포스트에 작성되어 있으며 해당 기능에 대해 딥다이브 한 내용이 이기에 복잡 할 수 있습니다.

---

Timer Interrupt

• 알람 클락(Alarm Clock)의 구현에서 사용되는 타이머 인터럽트는 시스템 타이머 칩에 의해 일정 주기로 발생하는 하드웨어 인터럽트다.
• 타이머 인터럽트는 시스템이 시간을 기반으로 작업을 스케줄링하고 관리할 수 있도록 주기적으로 CPU에 신호를 보낸다.
• 타이머 칩이 발생시키는 일정한 주기의 인터럽트 덕분에, 운영체제는 특정 시간 간격마다 CPU에 접근하여 작업 전환, 문맥 전환, 대기 시간 관리 등을 할 수 있다.
• 타이머 인터럽트가 없다면 컴퓨터 시스템에는 시간에 따른 작업 스케줄링 개념이 존재할 수 없고, 모든 작업이 순차적으로만 실행되었을 것이다.

주요 역할

1. CPU 시간 분배 및 스케줄링: 일정 시간 간격으로 인터럽트가 발생해 현재 실행 중인 프로세스를 중단하고, CPU가 다른 프로세스에 할당될 수 있도록 한다. 이를 통해 멀티태스킹 환경을 제공한다.
2. 대기 시간 관리: 타이머 틱(tick)이라는 단위를 사용하여 특정 시간 동안 대기(sleep)하도록 설정된 스레드가 지정된 시간이 지나면 다시 실행될 수 있게 한다.
3. 시스템 타이밍: 시스템 부팅 후 경과 시간, 작업별 실행 시간 등의 관리도 타이머 인터럽트를 통해 가능하다.

---

ISR (Interrupt Service Routine)

타이머 인터럽트가 발생하면 CPU는 인터럽트 서비스 루틴(ISR)을 통해 해당 인터럽트를 처리한다. ISR은 인터럽트가 발생했을 때 CPU가 즉시 처리해야 할 핸들러 함수로, 타이머 인터럽트가 발생할 때마다 일정한 작업을 수행하도록 설정된다.

ISR의 동작 방식

1. 인터럽트 발생:
   • 타이머 칩 또는 다른 하드웨어가 인터럽트를 발생시키면 CPU는 현재 작업을 중단하고 인터럽트 벡터 테이블에서 해당 인터럽트에 맞는 ISR 주소로 이동한다.
2. 인터럽트 서비스 루틴 실행:
   • CPU는 지정된 ISR에 진입하여 필요한 작업을 수행한다. 타이머 인터럽트의 경우 ISR은 주로 타이머 틱 증가, 스케줄러 호출, 대기 중인 스레드 상태 갱신 등의 작업을 담당한다.
   • 예를 들어, ticks라는 전역 변수를 증가시키고, 대기 중인 스레드가 깨어나야 하는 조건에 해당하는지 검사한 후 준비된 스레드를 ready 큐에 추가하는 방식이다.
3. 인터럽트 종료 및 복귀:
   • ISR이 모든 작업을 완료하면, CPU는 원래 실행하던 코드로 복귀한다. 이때, ISR로 인해 저장된 문맥 정보를 복원하여 중단되었던 작업을 계속 수행할 수 있도록 한다.

---

thread 상태

enum thread_status
{
    THREAD_RUNNING, /* 현재 CPU에서 실행 중인 스레드 */
    THREAD_READY,   /* 실행 준비가 완료된 상태로, CPU 할당을 기다리는 스레드 */
    THREAD_BLOCKED, /* 특정 이벤트 발생을 기다리는 상태로, 현재 CPU에서 실행될 수 없음 (대기 중) */
    THREAD_DYING    /* 곧 제거될 스레드로, 스케줄러에 의해 삭제가 예정된 상태 */
};

각 상태의 역할 설명

1. THREAD_RUNNING:
   • 현재 CPU에서 실행 중인 스레드의 상태이다. 단일 CPU 시스템에서는 한 번에 하나의 스레드만이 이 상태를 가지며, 스케줄러에 의해 CPU가 할당되어 작업을 수행 중인 스레드이다.
2. THREAD_READY:
   • 실행 준비가 완료되어 언제든지 CPU를 할당받을 수 있는 상태로, ready 큐에서 대기 중인 스레드들이다.
   • CPU가 비거나 스케줄러에 의해 우선순위가 높아질 때, 이 상태의 스레드 중 하나가 THREAD_RUNNING 상태로 전환되어 실행된다.
3. THREAD_BLOCKED:
   • 특정 이벤트 발생을 기다리며 실행을 중단한 상태로, BLOCKED 상태에서는 CPU 할당이 불가능하다. 예를 들어, 알람 클락에서 timer_sleep()을 호출해 대기하는 동안 wake_up_time까지 기다리는 스레드는 이 상태로 전환된다.
   • 타이머 인터럽트가 발생하고, 대기 시간이 완료되면 THREAD_READY로 상태가 바뀌어 다시 CPU 할당을 받을 준비를 한다.
4. THREAD_DYING:
   • 스레드가 작업을 마치고 종료가 예정된 상태로, 곧 스케줄러에 의해 제거될 스레드이다.
   • 이 상태로 전환된 스레드는 모든 작업이 종료되었으므로 자원을 반환하며, 더 이상 CPU에서 실행되지 않는다.

---

작성해야 할 함수

1. timer_sleep(int64_t ticks)

• 역할: 상위 레벨 함수로서, 현재 스레드를 ticks만큼 대기시키는 인터페이스 함수 역할을 한다.
• 구현 내용:
  • 이 함수는 ticks 값을 받아 현재 스레드를 지정된 ticks만큼 대기시키는 역할을 한다.
  • 먼저 ticks 값이 유효한지 확인하고, 유효하지 않다면 함수 종료.
  • 현재 시점의 시스템 시간에 ticks를 더해 wake_up_time을 계산한다.
  • thread_sleep() 함수를 호출해 계산된 wake_up_time을 기준으로 스레드를 대기 상태로 전환한다.

2. thread_sleep(int64_t wake_up_time)

• 역할: timer_sleep에서 호출되는 내부 함수로, 스레드를 지정된 wake_up_time까지 BLOCKED 상태로 전환하고 대기 목록에 추가한다.
• 구현 내용:
  • timer_sleep() 함수에서 호출되며, 스레드를 지정된 wake_up_time까지 BLOCKED 상태로 만들어 대기 목록에 추가하는 역할을 한다.
  • 현재 실행 중인 스레드의 wake_up_time을 설정한다.
  • wake_up_time을 기준으로 정렬된 대기 목록(sleeping list)에 현재 스레드를 삽입한다.
  • thread_block()을 호출해 스레드를 BLOCKED 상태로 전환한다.

3. thread_awake(int64_t curr_ticks)

• 역할: sleeping list를 순회하여 wake_up_time이 도래한 스레드를 확인하고 깨운다.
• 구현 내용:
  • sleep_list의 스레드들이 일어날 시간이 되면 ready_list로 이동시킨다.
  • 현재 current_ticks보다 작거나 같은 wakeup_ticks를 가진 스레드는 모두 깨운다.
  • 여기서 ‘스레드를 깨운다’는 것은, 깨울 스레드를 sleep_list에서 제거하고 ready_list에 삽입하는 것을 의미한다.
  • 1) sleep_list에서 깨울 스레드를 제거한다. (list_remove)
  • 2) 깨울 스레드를 ready_list에 삽입하고, 상태를 THREAD_READY로 변경한다. (thread_unblock)

4. thread_wake_time_compare

• 역할: 두 스레드의 wake_up_time을 비교하여 빠른 시간 순서로 정렬될 수 있게 한다.
• 구현 내용:
  • 두 스레드의 wake_up_time을 비교하여, 시간이 더 빠른 스레드가 대기 목록의 앞쪽에 오도록 정렬을 유지하는 역할을 한다.
  • 이 비교 함수는 wake_up_time이 작은 스레드를 우선 배치해 대기 목록이 정렬되도록 한다.

---

수정해야 할 함수

1. timer_interrupt(struct intr_frame *args UNUSED)
   • 역할: 시스템의 ticks를 주기적으로 증가시키고, 알람 클락을 위한 대기 목록을 확인하여 일정 시간이 경과한 스레드를 깨우는 역할을 한다.
   • 수정 내용:
     • ticks++을 통해 현재 시스템 시간을 증가시킨다.
     • thread_awake()를 호출하여 깨어날 시간이 도래한 스레드들을 ready 큐에 이동시킨다.

---

Alarm Clock 실행 흐름

1. 스레드가 timer_sleep() 호출
   • 스레드는 일정 시간 동안 대기(sleep)하기 위해 timer_sleep(int64_t ticks) 함수를 호출한다.
   • 여기서 ticks는 스레드가 대기해야 하는 시간(예: 100 ticks)을 나타낸다.
2. 대기 종료 시간 계산
   • timer_sleep() 함수는 현재 시스템 ticks 값과 스레드가 대기하고자 하는 ticks 값을 더해 깨워야 할 시간(wake_up_time)을 계산한다.
   • 예를 들어, 현재 ticks가 500이고, 스레드가 100 ticks 동안 대기하고자 하면 wake_up_time은 600이 된다.
3. 대기 목록에 스레드 추가
   • 계산된 wake_up_time을 기준으로 스레드는 대기 목록(sleeping threads list)에 추가된다.
   • 이 대기 목록에는 wake_up_time이 빠른 순서대로 스레드가 정렬되어 있어, 타이머 인터럽트 발생 시 가장 먼저 깨어나야 할 스레드가 쉽게 식별될 수 있다.
4. 스레드를 대기 상태로 전환
   • thread_block() 함수를 호출해 해당 스레드를 대기 상태로 전환하고, 스케줄러가 다른 스레드를 실행하도록 한다.
   • 이제 이 스레드는 wake_up_time까지 실행되지 않으며, 다른 스레드들이 CPU를 사용할 수 있게 된다.
5. 타이머 인터럽트 발생
   • 시스템 타이머는 일정 주기로 인터럽트를 발생시킨다. Pintos에서는 타이머 인터럽트 핸들러(timer_interrupt())가 호출되어 ticks를 1 증가시키고, 시스템 전체의 시간이 경과했음을 알린다.
6. 타이머 인터럽트 핸들러가 대기 목록 체크
   • timer_interrupt() 내에서는 wake_up_time이 현재 ticks 값보다 작거나 같은 대기 중인 스레드들을 검사한다.
   • wake_up_time이 도달한 스레드가 있으면, 그 스레드는 대기 목록에서 제거되고 thread_unblock()을 호출하여 ready 상태로 전환된다.
7. 스레드가 ready 큐에 추가되고 실행 준비
   • ready 큐에 추가된 스레드는 다른 스레드가 CPU에서 실행을 마치거나 스케줄러가 해당 스레드의 우선순위를 높게 평가할 경우 CPU를 할당받아 다시 실행된다.
   • 이로써, 원래 timer_sleep()을 호출했던 스레드는 대기 시간을 마치고 다음 작업을 이어서 수행할 수 있게 된다.

---

선언 및 초기화

Alram Clock 을 구현 하기 위해서는 sleep 상태에 존재하는 스레드를 저장할 리스트와 준비 가 완료된 스레드를 저장할 스레드가 필요하다.

    /* thread.c */

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

    ...

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

    ...

        list_init (&sleep_list);

    ...

    }

---

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;       // 일어날 시각 추가

    ...

    };

thread_sleep

    /* 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); // 인터럽트 상태를 원래 상태로 변경
    }

thread_wake_time_compare

    /* thread.h */

    bool thread_wake_time_compare(const struct list_elem *a, const struct list_elem *b, void *aux);
    /* thread.c */

    // 두 스레드의 wakeup_ticks를 비교해서 작으면 true를 반환하는 함수
    bool thread_wake_time_compare(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;
    }

timer_interrupt

    /* timer.c */

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