busy waiting

현재 pintos는 busy waiting 방식으로 구현되어 있다.

한 블로그의 예시를 비리자면 busy waiting 방식은 다음과 같다.

낮잠 자기 시작 -> 1분후 깸 -> 1분 지났네..? -> 다시 자야지 -> 1분후 깸 -> 2분 지났네..? -> 다시 자야지 -> … -> 1분 후 깸 -> 2시간 59분 지났네..? -> 다시 자야지 -> 1분 후 깸 -> 3시간 지났네? 이제 낮잠이 끝났구나…

즉 너무 비효율적이라는 말이다.

busy waiting 코드

기존 핀토스에 구현된 busy waiting 방식을 이용한 timer_sleep() 함수이다.

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

이를 알기위해 함수를 하나하나 뜯어보자

1. timer_ticks()

/* Returns the number of timer ticks since the OS booted. */
int64_t
timer_ticks (void) {
	enum intr_level old_level = intr_disable ();
	int64_t t = ticks;
	intr_set_level (old_level);
	barrier ();
	return t;
}

요약 : 현재 ticks 값을 반환하는 함수이다.

1. timer_elapsed()

/* Returns the number of timer ticks elapsed since THEN, which
   should be a value once returned by timer_ticks(). */
int64_t
timer_elapsed (int64_t then) {
	return timer_ticks () - then;
}

요약 : 인자로 받은 시간 이후로 경과된 시간을 반환

1. thread_yield()

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

요약 : 현재 running중인 스레드를 비활성화시키고 ready_list에 삽입한다.

다시 timer_sleep 함수를 봐보자

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

즉, busy waiting 방식으로 구현된 timer_sleep() 함수는 ready_list에서 자신의 차례가 된 스레드는 while문의 조건에 의해 start 이후 경과된 시간이 ticks보다 커질때까지 thread_yield()를 호출하여 ready_list의 맨 뒤로 이동하기를 반복한다. → 회전목마라고 생각하면 쉽다!

sleep/awake를 통한 alarm clock

그래서 이 힘들게 잠을 자는 친구들(핀토스의 프로세스들)을 알람 시계를 이용해 깨우는 방법을 고안하였다.

이는 sleep/awake 방식의 방법이다.

즉 기존의 alarm clock은 busy waiting 방식으로 구현되어 있어서 이를 sleep/awake 방식으로 구현하여 개선하는 것이다.

핵심 아이디어는 sleep_list를 만들고 자야할 친구들을 sleep_list에 넣어두어 깰시간에 깨워주는 방식이다.

sleep/awake 코드

1. thread 구조체에 wakeup_tick 추가

깨어나야할 tick을 저장할 변수를 추가해준다.

struct thread{
    ...
    /* 깨어나야 할 tick을 저장할 변수 추가 */
    int64_t wakeup_tick;
    ...
}

1. sleep_list, next_tick_to_awake를 추가, sleep_list는 초기화

block 상태인 스래드를 관리하기 위한 리스트 자료구조인 sleep_list를 선언해준다.

sleep_list에서 대기중인 스레드들의 wakeup_tick 값중 최소값을 저장하기 위한 변수 next_tick_to_awake 을 선언해준다.

static struct list sleep_list; 
static int64_t next_tick_to_awake;

...

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

1. next_tick_to_awake를 관리하는 함수들 생성

void update_next_tick_to_awake(int64_t ticks){
  /* next_tick_to_awake 가 깨워야 할 스레드의 깨어날 tick값 중 가장 작은 tick을 갖도록 업데이트 함 */
  next_tick_to_awake = (next_tick_to_awake > ticks) ? ticks : next_tick_to_awake;
}

int64_t get_next_tick_to_awake(void){
  return next_tick_to_awake;
}

update_next_tick_to_awake() 함수는 먼저 깨어나야할 스레드를 갱신시켜주는 함수이다.

next_tick_to_awake 와 인자로 받은 ticks중에 작은 값을 next_tick_to_awake 에 넣는다.

1. thread_sleep() 함수 구현

//스레드를 ticks시각 까지 재우는 함수
void thread_sleep(int64_t ticks){
  struct thread *cur;

  // 인터럽트를 금지하고 이전 인터럽트 레벨을 저장함 
  enum intr_level old_level;
  old_level = intr_disable();

  cur = thread_current();   // idle 스레드는 sleep 되지 않아야 함 
  ASSERT(cur != idle_thread);
  //awake함수가 실행되어야 할 tick값을 update
  update_next_tick_to_awake(cur-> wakeup_tick = ticks);

  /* 현재 스레드를 슬립 큐에 삽입한 후에 스케줄한다. */
  list_push_back(&sleep_list, &cur->elem);

  //이 스레드를 블락하고 다시 스케줄될 때 까지 블락된 상태로 대기 
  thread_block();

  /* 인터럽트를 다시 받아들이도록 수정 */
  intr_set_level(old_level);
}

thread sleep() 함수는 스레드를 인자로 받은 ticks 시각까지 재우는 함수이다.

먼저 현재 스레드가 idle 스레드는 sleep되면 안된다.

idle 스레드가 무엇인지 알면 그 이유를 알 수 있다. idle 스레드는 말 그대로 게으른 스레드이다. 심지어는 거의 아무일도 안하는 스레드이다.

idle 스레드는 운영체제가 초기화되고 ready_list가 생성되는데 이때 ready_list에 첫번째로 추가되는 스레드이다. 굳이 이 스레드가 필요한 이유는 CPU가 실행상태를 유지하기 위해 실행할 스레드 하나가 필요하기 때문이다.

CPU는 할 일이 없으면 아예 꺼져버렸다가 할일이 생기면 다시 켜는 방식에서 소모되는 전력보다 무의미한 일이라고 하고 있는게 더 적은 전력을 소모하기 때문에 idle 스레드가 존재한다.

1. thread_awake() 구현

/* 
잠자는 스레드를 깨우는 함수
wakeup_tick값이 ticks(인자)보다 작거나 같은 스레드를 깨움
 */
void thread_awake(int64_t ticks)
{
	next_tick_to_awake = INT64_MAX;
	struct list_elem *e;
	e = list_begin(&sleep_list);
	while(e != list_end(&sleep_list)){
		struct thread *t = list_entry(e, struct thread, elem);

		if(ticks >= t->wakeup_tick){
			e = list_remove(&t->elem);
			thread_unblock(t);
		} else {
			e = list_next(e);
			update_next_tick_to_awake(t->wakeup_tick);
		}
	}
}

잠자는 친구들을 깨워주는 thread_awake 함수이다. sleep_list의 모든 entry를 순회하면서 현재 tick이 깨워야할 tick보다 작다면 슬립 큐에서 제거하고 unblock 해준다. 그렇지 않다면 list_elem을 다음으로 갱신해주고 update_next_tick_to_awake 를 호출하여 next_tick_to_awake 변수를 갱신해준다.

1. timer_sleep 변경

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

	ASSERT (intr_get_level () == INTR_ON);
	
	thread_sleep(start+ticks);
}

기존에는 busy-waiting 방식으로 구현이 되었기 때문에 원래 있던 while문을 지우고 thread_sleep() 함수를 호출한다.

1. timer_interrupt 변경

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	if(get_next_tick_to_awake() <= ticks)
	{
		thread_awake(ticks);
	}
}

이제 sleep/awake 방식에서는 매 틱마다 깨울필요가 없다.

get_next_tick_to_awake() 함수를 통해 현재 깨워야할 스레드가 있는지 정보를 얻고, 있다면 thread_awake(ticks) 함수를 호출하도록 한다.

참고자료

[pintos] 1. Alarm System Call