[PintOS] Project 1.1 Alarm Clock

1. 과제 소개

Alarm clock은 프로세스나 스레드를 재우거나 깨우는 역할을 합니다. 일정 시간 동안 스레드를 일시 정지 시킨 후에  프로세스, 스레드를 다시 깨워 실행을 재개합니다.
스레드를 재우고 깨우는 데에 timer-interrupt를 사용합니다.
PintOS는 현재 busy-waiting 방식으로 alarm clock을 구현하고 있습니다.

2. 목표

이번 과제는 busy-waiting 방식으로 구현 된 alarm clock을 sleep awake 방식으로 바꾸는 것이 목표입니다.
busy waiting 방식은 cpu 에게는 그다지 효율적인 방법이 아닙니다. busy-waiting방식에서 스레드는 ready state와 running state를 반복해서 왔다갔다하기 때문입니다.

sleep/awake 방식은 스레드에 block state를 별도로 만들어서 잠든 스레드를 스케줄링하지 않고 별도의 sleep list에 보관해둡니다. cpu는 스레드를 실행할 지 여부를 결정하기 위해서 일일이 스레드를 확인하지 않아도 되어서 전력과 성능을 아낄 수 있습니다.

3. 구현 전

아래는 busy-waiting 방식으로 구현된 코드 모음입니다.

3.1 timer_sleep()

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

• 정해진 시간(ticks)가 지나기 전까지는 현재 스레드는 cpu를 양보합니다.
• 스레드는 ready에서 running으로 상태를 왔다갔다합니다.

3.2 timer_elapsed()

/* devices/timer.c */
int64_t timer_elapsed (int64_t then) {
  return timer_ticks () - then;
}

• 특정시간(then)을 기준으로 흘러간 시간을 계산합니다.

4. 구현 후

4.1 struct thread

/* thread/thread.h */
struct thread{
    ...
    int64_t wakeup; // 깨어나야 하는 ticks 값
    ...
}

• sleep/awake 방식에서는 스레드는 ready ⇄ block 상태로 변합니다.
• 깨어나야하는 시간을 저장하기 위한 멤버 wakeup이 필요합니다.

4.2 threads/thread.c

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

void
thread_init (void) 
{
  ...
  list_init (&ready_list);
  list_init (&all_list);
  list_init (&sleep_list);
  ...
}

• sleep_list: block 상태의 스레드 정보 보관합니다.
• thread_init()
  • 역할: 스레드 시스템 초기화합니다.
  • 추가할 동작: list의 초기화합니다.
    • ready_list: ready 상태의 스레드 리스트
    • all_list: 모든 상태의 스레드를 담은 리스트
    • sleep_list: block 상태의 스레드를 담은 리스트

4.3 thread_sleep()

/* thread/thread.c */
void
thread_sleep (int64_t ticks)
{
  struct thread *cur;
  enum intr_level old_level;

  old_level = intr_disable ();	// 인터럽트 off
  cur = thread_current ();
  
  ASSERT (cur != idle_thread);

  cur->wakeup = ticks;			// 일어날 시간을 저장
  list_push_back (&sleep_list, &cur->elem);	// sleep_list 에 추가
  thread_block ();				// block 상태로 변경

  intr_set_level (old_level);	// 인터럽트 on
}

• ticks: 스레드를 재울 시간입니다.
• idle_thread: 실행할 스레드가 없을 경우 cpu가 중단되는 것을 막기 위해 사용하는 스레드입니다.
• 스레드를 block 상태가 되기 전후로 인터럽트를 끄고 켜야합니다. 그 이유는 다음과 같습니다.
  - 원자성 보장: 스레드의 상태변경 과정은 방해를 받아서는 안됩니다.
  - 경쟁상태 방지: 다른 스레드가 동일한 자원에 접근하는 것을 막기 위함입니다.
  - 데이터의 일관성 보장을 하기 위함입니다.

4.4 timer_sleep()

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

• 역할: 스레드를 잠재우는 타이머의 기능입니다.

4.5thread_awake()

/* thread/thread.c */
void
thread_awake (int64_t ticks)
{
  struct list_elem *e = list_begin (&sleep_list);

  while (e != list_end (&sleep_list)){
    struct thread *t = list_entry (e, struct thread, elem);
    if (t->wakeup <= ticks){	// 스레드가 일어날 시간이 되었는지 확인
      e = list_remove (e);	// sleep list 에서 제거
      thread_unblock (t);	// 스레드 unblock
    }
    else 
      e = list_next (e);
  }
}

• 역할: sleep_list를 순회하면서 시간이 된 스레드를 깨웁니다.

4.6 선언한 함수 프로토타입에 추가

/* thread/thread.h */
...
void thread_sleep(int64_t ticks);
void thread_awake(int64_t ticks);
...

• 함수를 정의했으므로 헤더파일에 가서 함수를 선언합니다.

4.7 timer_interrupt() 수정

/* devices/timer.c */
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
  ticks++;
  thread_tick ();
  thread_awake (ticks);	// ticks 가 증가할때마다 awake 작업 수행
}

• timer_interrupt()를 수정해줍니다. 
• tick이 증가할 때마다 thread_awake를 실행합니다.

5. 테스트 결과