Alarm Clock 이란?

현재 PintOS 운영체제에서 다중 스레드 환경을 구현하기 위해 사용하는 방식은 busy-waiting이라는 방식이다.

busy - waiting

timer.c 함수 내에서 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자원을 엄청나게 쓴다. 말 그대로 기다리느라 바쁜 것이다.

따라서 CPU의 자원을 아끼고 싶다면 실행할 시간이 아직 아닌 스레드를 재우고, 시간이 지났다면 대기 상태로 바꾸는 방식을 사용할 수 있다. 이것이 Alarm-clock이다.

Sleep - Wake up

Alarm clock 을 구현하는 기본적인 아이디어는 위에서 언급한대로 스레드를 대기상태 ready state 가 아니라 잠든 상태 block state 로 보내고 깨어날 시간이 되면 깨워서 ready state 로 보내는 것이다.

우선, block state 에서는 스레드가 일어날 시간이 되었는지 계속 확인하지 않기 때문에 스레드마다 일어나야 하는 시간에 대한 정보를 저장하고 있어야 한다. wake_up_ticks 라는 멤버를 만들어 thread 구조체에 추가하였다.

/* include/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 wake_up_ticks;              //<=새로 만든 멤버

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */

그리고 대기 상태인 스레드를 저장하는 ready list 에 더해 잠든 상태인 스레드를 저장하기 위한 sleep list 를 추가하였다.

/* List of processes in THREAD_BLOCKED state.
   blocked because of timer */
static struct list sleep_list;

...

void thread_init (void) {
...
lock_init (&tid_lock);
list_init (&ready_list);
list_init (&sleep_list); //<= init에 추가
list_init (&destruction_req);
}
...

잠든 상태인 스레드를 기록하는 리스트도 만들었으니 이제 스레드를 재우는 함수와 깨우는 함수만 만들면 된다.

//thread.c
// list_insert_ordered() 함수를 사용하기 위한 정렬 기준 함수
static bool less_then_func(struct list_elem *a, struct list_elem *b, void *aux) {
	return list_entry(a, struct thread, elem)->wake_up_ticks < 
			list_entry(b, struct thread, elem)->wake_up_ticks;
}

/* current thread: set wake_up_time and sleep thread */
//일어나는 시간을 변수로 받아야 하기 때문에 thread_unblock 함수를 활용하는 대신
//새로운 함수를 만들어야 한다.
void thread_sleep(const int64_t wake_up_ticks) { 
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context());
	ASSERT (curr != idle_thread);

	curr->wake_up_ticks = wake_up_ticks;
	// list_remove(&curr->elem); // next_thread_to_run 에서 수행함
    //리스트에 요소를 맨 앞이나 맨 뒤에 추가하는 대신 정렬하여 추가하는 함수
    //대신에 정렬의 기준을 판단해 줄 함수를 앞에서 미리 선언해야 한다.
	list_insert_ordered(&sleep_list, &curr->elem, less_then_func, 0);

	old_level = intr_disable();
    //재우기
	thread_block();
	intr_set_level(old_level);
}

/* wake up threads if time is over */
void thread_wake_up(const int64_t ticks_now) {
	struct list_elem *ptr;
	struct thread *temp;

	ASSERT (intr_get_level() == INTR_OFF);

	while (!list_empty(&sleep_list)) {
		ptr = list_front(&sleep_list);
		temp = list_entry(ptr, struct thread, elem);

		if (temp->wake_up_ticks <= ticks_now) { //일어날 시간이 지났다면
			list_remove(ptr); // pop from blocked list
            //깨우기
			thread_unblock(temp);
		} else {
			break; // no more available threads
		}
	}
}

이렇게 재우고 깨우는 함수까지 만들었는데... 언제 알람시계를 확인해야 하는가?
timer.c의 timer_interrupt에 thread_wake_up() 함수를 추가해주면 timer_interrupt가 발동할 때, 즉 1틱이 지날때 마다 sleep_list의 스레드를 반복문으로 확인하고 일어날 시간이 된 스레드는 깨운다.

//device/timer.c
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	ASSERT(intr_get_level() == INTR_OFF);

	// move proper threads from blocked queue to ready queue
	thread_wake_up(timer_ticks());
}