[PintOS] 1.1 Alarm Clock

1. Alarm Clock(알람 클록)

1.1 개념 및 특징

• Alarm Clock은 지정된 시간(tick)이 지난 후 스레드를 깨우는 운영체제 커널 내부 기능입니다. 
• 운영체제에서는 실행 중인 스레드를 잠시 재웠다가 일정 시간이 지나면 다시 깨우도록 하는 기능을 제공합니다.
• PintOS에서는 timer_sleep() 함수를 통해 이 기능을 구현합니다. 

1.2 현재 PintOS의 문제점 - Busy Waiting

현재 PintOS에 구현된 Alarm Clock 기능은 busy waiting 방식으로 구현되어 있어 매우 비효율적입니다. \

/* devices/timer.c */
void timer_sleep (int64_t ticks) {
  int64_t start = timer_ticks ();
  
  while (timer_elapsed (start) < ticks)
    thread_yield ();
}

Busy Waiting의 문제점:

• 스레드가 대기해야 할 때도 CPU를 계속 점유합니다. 
• thread_yield()로 CPU를 양보하더라도 곧바로 스케줄러에 의해 다시 선택될 수 있습니다. 
• 스레드가 실제로 아무것도 하지 않는데도 CPU 자원을 낭비합니다. 
• 배터리 소모, 발열 등 리소스 낭비 문제를 일으킵니다.

---

2. Sleep/Wakeup 방식으로 개선

2.1 개선 방향

Busy Waiting 대신 Sleep/Wakeup 방식을 적용하면 아래와 같은 이점이 있습니다. 

Busy Waiting 방식	Sleep/Wakeup 방식
CPU를 계속 점유하며 확인	스레드를 BLOCKED 상태로 전환하고 CPU 반환
스케줄러에 의해 반복 선택됨	타이머 인터럽트가 올 때만 상태 확인
CPU 자원 낭비 심함	CPU 자원 효율적 사용
idle tick ≈ 0	idle tick > 0

2.2 구현을 위한 필요 요소

1. 자료구조 추가
   • sleep_list : 잠든 스레드들을 관리할 리스트
   • thread 구조체에 wakeup_tick 필드 추가: 스레드가 깨어나야 할 시간
2. 함수 수정 및 추가 
   • timer_sleep() : busy waiting 대신 스레드를 재우는 방식으로 변경
   • thread_sleep() : 스레드를 BLOCKED 상태로 만들고 sleep_list에 추가
   • timer_interrupt() : 타이머 인터럽트마다 깨울 스레드가 있는지 확인
   • thread_awake() : 깨어날 시간이 된 스레드를 깨우는 함수

---

3. 구현 과정

3.1 thread 구조체 수정

/* threads/thread.h */
struct thread {
  tid_t tid;                  /* Thread identifier. */
  enum thread_status status;  /* Thread state. */
  char name[16];              /* Name (for debugging purposes). */
  int priority;               /* Priority. */
  int64_t wakeup_tick;        /* 깨워야 할 시각 */
  
  /* 나머지 필드들... */
};

3.2 전역 변수 및 리스트 선언

/* threads/thread.c */
static struct list sleep_list;  /* 잠든 스레드들의 리스트 */

3.3 timer_sleep() 함수 수정

/* devices/timer.c */
void timer_sleep (int64_t ticks) {
  int64_t start = timer_ticks ();
  
  if (timer_elapsed (start) < ticks)
    thread_sleep(start + ticks);
}

3.4 thread_sleep() 함수 구현

/* threads/thread.c */
// 현재 실행 중인 스레드를 지정한 시간(wakeup_tick)까지 잠재운다.
// sleep_list에 wakeup_tick 기준으로 정렬하여 추가한다.
void thread_sleep(int64_t wakeup_tick) {
    struct thread *cur = thread_current();  // 지금 실행 중인 스레드를 가져온다

    // idle_thread(항상 돌아가는 기본 스레드)는 절대 잠들면 안 되므로 바로 반환
    if (cur == idle_thread)
        return;

    // sleep_list를 조작하는 동안 인터럽트를 잠깐 꺼서 예기치 않은 동시 접근을 막는다
    enum intr_level old_level = intr_disable();

    // 이 스레드가 언제 깨어나야 할지 기록해둔다
    cur->wakeup_tick = wakeup_tick;

    // sleep_list에 이 스레드를 wakeup_tick 기준으로 정렬해서 삽입한다
    // (가장 빨리 깨어날 스레드가 sleep_list의 맨 앞에 오게 됨)
    list_insert_ordered(&sleep_list, &cur->elem, compare_wakeup_tick, NULL);

    // 현재 스레드를 BLOCKED 상태로 바꾸고 CPU를 양보한다(실행 중단)
    thread_block();

    // sleep_list 조작이 끝났으니 인터럽트 상태를 원래대로 돌려놓는다
    intr_set_level(old_level);
}

3.5 thread_awake() 함수 구현 

// 현재 시각(current_tick)보다 먼저 깨어나야 할 스레드들을 깨운다.
// sleep_list는 wakeup_tick 기준으로 정렬되어 있다고 가정한다.
void thread_awake(int64_t current_tick) {
    // sleep_list의 맨 앞 요소부터 차례로 확인하기 위해 반복문 시작
    struct list_elem *e = list_begin(&sleep_list);

    // sleep_list의 끝에 도달할 때까지 반복
    while (e != list_end(&sleep_list)) {
        // 현재 리스트 요소(e)가 가리키는 스레드 구조체를 가져온다
        struct thread *t = list_entry(e, struct thread, elem);

        // 이 스레드가 깨어나야 할 시간이 되었는지 확인
        if (t->wakeup_tick <= current_tick) {
            // 깨어날 시간이 되었으므로, sleep_list에서 제거하고
            // list_remove는 다음 요소의 포인터를 반환한다
            e = list_remove(e);

            // 스레드를 READY 상태로 전환하여 실행 대기열에 넣는다
            thread_unblock(t);
        } else {
            // sleep_list가 wakeup_tick 오름차순으로 정렬되어 있으므로,
            // 아직 깨어날 시간이 안 된 스레드를 만나면 이후는 모두 더 늦은 시간임
            // 따라서 반복문을 종료한다
            break;
        }
    }
}

 

---

4. 결과 확인

product가 순차적으로 나오고 Thread: 550 idle ticks, 30 kernel ticks, 0 user ticks → 원래 돌린 idle 보다 적어지면 정상적으로 작동이 된 것이다. 

alarm-single 실행 한 후

alarm-multiple 실행 후