Project 1 : Alarm clock - BeAPro

Alarm clock

/* tests/thread/alarm-priority.c */

....
timer_sleep (wake_time - timer_ticks ());

alarm을 테스트하는 c파일에서는 timer_sleep() 함수를 불러온다.

 

현재 PintOS는 busy waiting 방식으로 알람이 구현되어 있다.

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

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

busy waiting 방식은 아무것도 하지 않는 쓰레드가 CPU를 점유하고 있는 매우 비효율적인 방식이다.

 

100초를 sleep하라고 명령을 내렸는데 100초가 지나지 않았음에도 ready_list에서 scheduler에 의해 호출되는 것을 확인할 수 있다.

따라서 100초를 뒤에만 확인 할 수 있도록 threads/thread.* 와 devices/timer.*를 변경하여 sleep/wakeup 방식의 alarm을 구현해야 한다.

 

---

 

timer_interupt()

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
}

Alarm clock을 구현하기 전에 /devices/timer.c 에 있는 timer_interupt()에 대해 알아볼 필요가 있다.

내부적으로 어떻게 동작하는지는 모르겠지만 PintOS에서 정한 일정한 시간마다 timer_interupt()가 호출된다.

이 함수를 통해 PintOS 전체에서 시간의 기준이 되는 ticks가 증가하게 된다.

 

---

Design

위는 자료에서 요구하는 sleep/wakeup 방식의 디자인이다.

sleep 명령어를 받은 쓰레드는 ready_list로 들어가는 것이 아니라 block 된 상태로 sleep_list에 삽입된다.

sleep_list에 들어갔기 때문에 더 이상 스케줄링되지 않아 cpu의 불필요한 소모를 막게 된다.

timer_interupt() 함수가 호출될 때마다 wakeup() 함수를 실행하여 sleep_list에서 깨어나야 할 쓰레드들을 고르고 이들을 ready_list에 넣어 다시 스케줄링될 수 있도록 한다.

 

쓰레드에 자신이 얼마나 잠들었는지 알 수 있는 변수 wakeup_ticks를 선언하여 sleep_list에서 잠든 시간을 파악할 수 있어야 한다.

---

Code

/* list.h */
/* Compares the value of two list elements A and B, given
   auxiliary data AUX.  Returns true if A is less than B, or
   false if A is greater than or equal to B. */
typedef bool list_less_func (const struct list_elem *a,
                             const struct list_elem *b,
                             void *aux);

/* thread.c */
/*
Project 1 : cmp_wakeup_ticks
Compare the wakeup ticks in sleep_list
*/
bool cmp_wakeup_ticks(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
    struct thread *st_a = list_entry(a, struct thread, elem);
    struct thread *st_b = list_entry(b, struct thread, elem);
    return st_a->wakeup_ticks < st_b->wakeup_ticks;
}

나는 sleep_list가 깨어날 시간이 적은 순으로 정렬되어 있길 원했다. 따라서 list.c에 있는 list_insert_ordered() 함수를 사용하고 싶었다. list_insert_ordered() 함수는 위 코드에 있는 list_less_func() 형식으로 비교 함수를 넣어주면 그 내용에 맞게 리스트에 삽입이 이루어진다. 나는 wakeup_ticks가 낮은 순으로 정렬되기를 원했기에 위처럼 cmp_wakeup_ticks코드를 짰다.

 

/* 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. */
    /* Project 1 */
	int64_t wakeup_ticks;
	...
};


/* thread.c */
/* Project 1 : Thread sleep list */
static struct list sleep_list;
/* 
Project 1 : thread_sleep
Update wakeup_ticks
Change thread status to THREAD_BLOCKED
Insert to sleep_list in ascending order
*/
void thread_sleep(int64_t ticks){
	struct thread *curr = thread_current();
	enum intr_level old_level = intr_disable();
	curr->wakeup_ticks = ticks;
	list_insert_ordered(&sleep_list, &curr->elem, cmp_wakeup_ticks, NULL);
	thread_block();
	intr_set_level(old_level);
}

thread.h에서 thread 구조체에 변수 wakeup_ticks를 추가해 주었다.

thread_sleep() 함수를 만든다. thread_sleep()에서는 호출되면 wakeup_ticks를 일어나야 하는 시간(ticks)으로 갱신해 주고 이를 sleep_list에 넣어주게 된다.

 

/* 
Project 1 : thread_wakeup
Delete wakeup thread in sleep_list and unblock
*/
void thread_wakeup(int64_t ticks){
    enum intr_level old_level;
    old_level = intr_disable();
    struct list_elem *curr_elem = list_begin(&sleep_list);

    while (curr_elem != list_end(&sleep_list))
    {
            struct thread *curr_thread = list_entry(curr_elem, struct thread, elem);
            if (curr_thread->wakeup_ticks <= ticks)
            {
                    curr_elem = list_remove(curr_elem); 
                    thread_unblock(curr_thread);
            }
            else
                    break;
    }
    intr_set_level(old_level);
}

thread_wakeup()  함수를 만든다. thread_wakeup() 함수는 현재 PintOS가 실행된 시간(ticks)을 인자로 받는다.

sleep_list를 돌면서 wakeup_ticks가 ticks보다 작은 쓰레드들을 모두 삭제하고 unblock 시켜 다시 스케줄링될 수 있게 한다.

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

	ASSERT (intr_get_level () == INTR_ON);
	
	/* Project 1 : Execute thread_sleep() when ticks is positive */
	if(timer_elapsed (start) < ticks) thread_sleep(start+ticks);
}

timer_sleep() 함수에서는 더 이상 while문을 사용할 필요가 없어진다.

thread_sleep() 함수에 현재 PintOS가 실행된 시간 + 잠이 들 시간(start+ticks)이 인자로 주어져야 한다.

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

 

timer_interrupt가 실행될 때마다 thread_wakeup() 함수를 호출하여 일어나야 할 스레드가 없는지 확인한다.

---

Result

pintos -- -q run alarm-multiple

수정 전에 결과 값이다. alarm-multiple은 object 파일 밖에 없어서 정확히 어떻게 구현되어 있는지는 모르지만 스레드를 sleep 시켰음에도 sleep 된 쓰레드가 계속 호출되어 idle thick이 한 번도 증가하지 않았다.

수정 후에 결과 값이다. 쓰레드가 sleep상태에 들어갔고 CPU는 더 이상 호출할 작업이 없어 idle thread를 호출한 것을 확인할 수 있다.