[Pintos] Project 1 : Thread(스레드) - Alarm Clock

이번 포스트에서는 핀토스의 첫 번째 과제인 Alarm Clock 을 구현해보도록 한다.

Alarm Clock

운영체제에는 실행중인 스레드를 잠시 재웠다가 일정 시간이 지나면 다시 깨우도록 하는 기능이 있는데, 이 기능을 Alarm Clock 이라고 한다. 현재 핀토스에 구현되어 있는 Alarm Clock 기능은 busy-waiting 방식으로 구현되어 있는데 이는 매우 비효율적으로 많은 CPU 시간을 낭비하게 한다. busy-waiting 방식에서 sleep 명령을 받은 스레드의 진행 흐름은 아래와 같이 진행된다.

잠이듬 -> 깨어남 -> 시간확인 -> 다시잠 -> 깨어남 -> 시간확인 -> ... -> 깨어남 -> 시간확인(일어날시간) -> 깨어남

이러한 문제가 발생하는 내면을 살펴보면 스레드의 상태가 running state 와 ready state 를 반복함을 볼 수 있다. running state 에서 sleep 명령을 받은 스레드는 ready state 가 되어 ready queue 에 추가되고 ready queue 에 있는 스레드들은 자신의 차례가 되면 일어날 시간이 되었는지에 상관없이 깨워져 running state 가 된다. 이렇게 running state 가 된 스레드는 자신이 일어날 시간이 되었는지 확인하고 아직 일어날 시간이 안 됐다면 다시 ready state 로 전환한다.

busy-waiting 에서 thread 의 상태

이러한 비효율을 해결하려면 잠이 든 스레드를 ready state 가 아닌 block state 로 두어서 깨어날 시간이 되기 전까지는 스케줄링에 포함되지 않도록 하고, 깨어날 시간이 되었을 때 ready state 로 바꾸어 주면 된다.

개선된 thread 상태변화

 

Busy-waiting 코드

기존 핀토스에 구현되어 있는 busy-waiting 을 이용한 timer_sleep() 코드는 아래와 같다.

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

ticks 란 핀토스 내부에서 시간을 나타내기 위한 값으로 부팅 이후에 일정한 시간마다 1 씩 증가한다.

/* devices/timer.h */
/* Number of timer interrupts per second. */
#define TIMER_FREQ 100

1 tick 의 시간을 설정하여 줄 수 있는데, 위 코드에서 볼 수 있듯이 현재 핀토스의 1 tick 은 1ms 로 설정되어 있다. 이에 따라 운영체제는 1ms 마다 timer 인터럽트를 실행시키고 ticks 값을 1 씩 증가시킨다.

 

timer_sleep() 함수를 분석하여 보자. timer_ticks() 함수는 현재 ticks 값을 반환하는 함수로 start 에 현재 시간(ticks)을 저장한다. timer_elapsed() 함수는 특정시간 이후로 경과된 시간(ticks) 를 반환한다. 즉, timer_elapsed(start) 는 start 이후로 경과된 시간(ticks)을 반환한다.

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

 

이에 따라, ready list 에서 자신의 차례가 된 스레드는 while 문의 조건에 의해 start 이후 경과된 시간이 ticks 보다 커질때까지 thread_yield () 를 호출하여 ready list 의 맨 뒤로 이동하기를 반복한다.

반응형

Sleep / Awake 구현

Alarm clock 을 개선하는 기본적인 아이디어는 위에서 언급한대로 잠이 들 때 ready state 가 아니라 block state 로 보내고 깨어날 시간이 되면 깨워서 ready state 로 보내는 것이다. 이를 구현해보자.

우선, block state 에서는 스레드가 일어날 시간이 되었는지 주기적으로 확인하지 않기 때문에 스레드마다 일어나야 하는 시간에 대한 정보를 저장하고 있어야 한다. wakeup 이라는 변수를 만들어 thread 구조체에 추가하겠다.

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

현재 핀토스에서 스레드들을 관리하는 리스트는 ready list 와 all list 두 개만 존재한다. 잠이 들어 block 상태가 된 스레드들은 all list 에 존재하지만, sleep 상태의 스레드들로만 이루어진 리스트를 만들어 관리하면 훨씬 편해진다. sleep_list 를 추가하고 초기화까지 시켜준다.

/* 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 state 로 만들어주는 것으로 충분할 것 같다. 한 가지 주의할 점은 CPU 가 항상 실행 상태를 유지하게 하기 위해 idle 스레드는 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
}

스레드를 재우는 함수를 만들었으니 timer_sleep() 함수의 while 문을 새로운 함수로 바꾸어 주자.

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

 

이제 timer_sleep() 함수가 호출되면 스레드가 block 상태로 들어가게 되었다. 이렇게 block 된 스레드들은 일어날 시간이 되었을 때 awake 되어야 한다. sleep_list 를 돌면서 일어날 시간이 지난 스레드들을 찾아서 ready list 로 옮겨주고, 스레드 상태를 ready state 로 변경시켜주도록 하자.

/* 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, awake 함수를 추가하였으므로 thread.h 에 프로토타입을 선언해주어야 한다.

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

 

위에서 1 tick 이 경과할 때마다 timer 인터럽트가 실행된다고 하였다. 이 timer interrupt 작업에 awake 작업을 포함시키면 ticks 가 증가할때마다 깨워야 할 스레드가 있는지 찾고, 깨워줄 수 있다. timer_interrupt handler 함수는 devices/timer.c 에 구현되어 있다.

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

 

결과

pintos/src/thread 폴더에서 make 명령으로 컴파일을 하고, pintos -q run alarm-multiple 명령을 실행하면 아래와 같은 결과를 확인할 수 있다.

처음에 구현되어 있던 busy-waiting 방식으로 실행 시 Thread: 0 idle ticks 로 나오던 부분이 550 idle ticks 로 바뀌었다. 이것은 idle 스레드가 550 ticks 동안 실행되었다는 것이고, idle 스레드는 다른 어떤 스레드도 실행되지 않는 상태일 때 실행되는 스레드로 550 ticks 동안의 쉬는 시간이 발생했다는 뜻과 같습니다. busy-waiting 방식일 때 ready list 가 비어있는 순간이 없기 때문에 idle 스레드가 실행될 일이 없어 0 idle ticks 로 출력된 것과 달리 sleep/awake 방식에서 시스템 자원의 낭비가 줄어든 것을 볼 수 있다.