Project_1 : Threads - Alarm Clock

첫 번째 Pintos 프로젝트는 스레드와 관련한 것으로 Alarm Clock, Priority Scheduling, Advanced Scheduler 세 가지로 구분된다.

그중 Alarm Clock의 목표는 아래와 같다.

 

Pintos 기본 스레드 시스템의 Alarm Clock은 busy waiting으로 구현되어 있다.

busy waiting이란 CPU를 계속해서 사용하며 특정 조건을 만족할 때까지 대기하는 방식을 의미한다. 이는 CPU 자원 낭비를 유발한다.

따라서 busy waiting을 피하기 위해 이미 구현되어 있는 아래의 timer_sleep( ) 함수를 수정하는 것이 Alarm Clock의 목표이다.

(사실 timer_sleep( ) 함수 이외에도 코드를 수정하거나 추가해야 할 함수들이 있다.)

/* /devices/timer.c */

/* 수정하지 않은 timer_sleep( ) 함수는 실시간으로 작동하는 스레드에 유용하다.
   해당 함수의 인수 TIMER_FREQ는 devices/timer.h 에 정의된 매크로로 그 기본값은 100이다. 
   변경할 경우, 많은 테스트가 실패할 수 있어서 변경하지 않는 것이 좋다. */

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

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)	// <- busy wating 유발 
		thread_yield (); 
}

그런데 코드를 수정 및 추가하려면 Pintos 스레드 상태에 대한 이해가 필요하다.

busy waiting이라는 것은 특정 조건을 만족할 때까지 아래 그림의 RUNNIG과 READY 상태의 전환을 반복하는 것이라 할 수 있다.

따라서 특정 조건이 만족하지 않을 경우, READY 상태로의 전환이 아닌 BLOCKED 상태로 전환하도록 코드를 구현해야 한다.

이후, 시간이 지나 조건을 만족할 경우에는 BLOCKED 된 스레드를 깨워서 READY 상태로 만들어야 한다.

 

구체적인 구현 과정은 다음과 같다.

우선, Alarm Clock에서 사용할 기상 정보 변수를 thread 구조체에 추가한다.

/* /include/threads/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. */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
    
    /* PROJECT1: THREADS - Alarm Clock */
	int64_t	wakeup;						/* time to wake up */

Pintos에서는 스레드들을 리스트로 관리하고 있다.

예를 들어, ready_list에는 READY 상태의 스레드들이 들어있다.

BLOCKED 된 스레드들을 담기 위한 sleep_list를 만들고 thread_init( ) 함수에 추가한다.

/* /threads/thread.c */

/* PROJECT1: THREADS - Alarm Clock */
static struct list sleep_list;

void thread_init (void) {
	ASSERT (intr_get_level () == INTR_OFF);

	/* Reload the temporal gdt for the kernel
	 * This gdt does not include the user context.
	 * The kernel will rebuild the gdt with user context, in gdt_init (). */
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);

	/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);

	/* PROJECT1: THREADS - Alarm Clock */
	list_init (&sleep_list);

	/* Set up a thread structure for the running thread. */
	initial_thread = running_thread ();
	init_thread (initial_thread, "main", PRI_DEFAULT);
	initial_thread->status = THREAD_RUNNING;
	initial_thread->tid = allocate_tid ();
}

이제 스레드 생성 시 기상 정보를 담을 수 있게 된 것은 물론, sleep_list를 만들어 BLOCKED 상태의 스레드를 관리할 수 있게 되었다.

다음으로는 스레드를 BLOCKED 상태로 변환하는 함수를 만들어야 한다.

해당 함수에는 스레드에 기상 정보를 저장하는 과정, sleep_list에 추가하고 스레드 상태를 BLOCKED로 만드는 과정이 포함되어야 한다.

한 가지 중요한 점은 idle 스레드는 제외해야 한다는 것이다.

이는 CPU의 실행 상태를 유지하기 위하여 idle 스레드는 특별히 관리되어야 하기 때문이다.

/* /threads/thread.c */

/* PROJECT1: THREADS - Alarm Clock */
/* Make the running thread sleep. */
void thread_sleep(int64_t ticks) {
	struct thread *cur;
	enum intr_level old_level;

	old_level = intr_disable(); 				/* turn off interupt */
	cur = thread_current();
	
	ASSERT(cur != idle_thread);

	cur -> wakeup = ticks;						/* set time to wake up */
	list_push_back(&sleep_list, &cur->elem);	/* push to sleep_list */
	thread_block();								/* make thread blocked */

	intr_set_level(old_level);					/* turn on interupt */
}

이제 앞서 수정이 필요하다고 했던 timer_sleep( ) 함수로 돌아가 busy waiting이 발생하는 부분을 삭제한다.

그리고 스레드를 BLOCKED 상태로 전환할 수 있는 함수를 추가한다.

/* /devices/timer.c */

/* PROJECT1: THREADS - Alarm Clock */
void timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

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

앞으로 timer_sleep( ) 함수가 호출되면, 해당 스레드는 READY 상태가 아닌 BLOCKED 상태로 전환된다.

이렇게 BLOCKED 상태로 전환된 스레드들은 기상 시간이 되었을 때 일어나야 한다. 

sleep_list내의 스레드를 하나 씩 확인하면서 일어나야 할 스레드들을 찾아 sleep_listd에서 삭제한다.

/* /threads/thread.c */

/* PROJECT1: THREADS - Alarm Clock */
/* Makes the sleeping thread wake up. */
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);
			thread_unblock(t);
		}
		else 
			e = list_next(e);
	}
}

타이머는 기준 시간이 경과할 때마다 인터럽트가 발생한다. 따라서 timer_interrupt 함수에 awake 작업을 포함시킨다.

/* devices/timer.c */


/* Timer interrupt handler. */
static void timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_awake(ticks); /* PROJECT1: THREADS - Alarm Clock */
}

마지막으로 thread.h에 새로운 함수, thread_sleep( )과 thread_awake( )의 프로토타입을 선언해준다.

/* /threads/thread.c */

/* PROJECT 1 : Threads - Alarm Clock */
void thread_sleep(int64_t ticks);
void thread_awake(int64_t ticks);

코드를 수정 및 추가하고나서터미널에 다음과 같이 입력한다.

 

아래와 같이 Thread: 550 idle ticks로 변화했다면 성공이다.

 

 

 

기타 정보)

사실 Alarm Clock 구현은 프로젝트 2, 3에서는 필요하지 않다. 다만 프로젝트 4에서는 유용할 수 있다.