[TIL] 쓰레드 sleep 시 CPU 효율성 개선하기 - sleep_list 추가

pintos 운영체계에 대해 학습하며 얻는 과제들이 어려운 점은 

 

무엇이 잘못되고 있는지 파악하는 것부터 시작이기 때문인 것 같다.

 

밥 먹으며 동료들과 얘기를 나누면서 든 생각은

 

핀토스에서는 문제의 질문부터 찾아내는 것이 시작인 것 같다.

 

 

그래서 그 첫번째 문제점인 쓰레드가 sleep할 때, CPU를 점유하면서 쉬고 있는 상황을 개선해 보았다.

---

 

문제 인식

 

현재 쓰레드가 timer_sleep 될 경우 해당 쓰레드가 격리되는 방식에 대해 살펴보기 위해 초기 timer_sleep() 함수를 살펴보자.

 

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

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

 

어제 포스팅한 내용처럼 현재 핀토스는 타이머 인터럽트를 통해 시분할(time-sharing) 시스템 방식으로 쓰레드를 매 틱마다 전환하고 있다.

 

현재 이 코드에서의 문제 상황을 그려보면 다음과 같다.

 

 

각 쓰레드는 500 틱 동안 쉬는 timer_sleep() 함수에 들어가면 CPU를 점유하지 않는 것이 효율적이다.

 

근데 현재는 이런 식으로 CPU를 점유한 상태에서 while문을 무한히 읽으며 서로를 양보하고 있다.

 

이런 식으로 하지 않고 sleep list에다 재우고 굳이 CPU를 점유시키지 않도록 바꿔보았다.

 

 

아래부터는 이 쓰레드를 잠재우는 함수의 잠자는 방식을 변경한 코드 들이다.

 

---

 

변경된 timer_sleep ()

 

 

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();
	enum intr_level old_level;

	old_level = intr_disable ();
	struct thread *t = thread_current ();
	t->wake_time = ticks + start;
	thread_sleep_and_yield();
	intr_set_level (old_level);
}

////////////////////////////////////////////////////////////////////

/* States in a thread's life cycle. */
enum thread_status {
	THREAD_RUNNING,     /* Running thread. */
	THREAD_READY,       /* Not running but ready to run. */
	THREAD_BLOCKED,     /* Waiting for an event to trigger. */
	THREAD_DYING,        /* About to be destroyed. */
	THREAD_SLEEPING,    /* 일정기간동안 쓰레드 재우기*/
};

 

쓰레드가 몇 틱동안 자게하는 함수이다.

 

이 함수에서 while문을 제거한 뒤

 

쓰레드를 sleep_list에 집어넣은 뒤 현재 스레드를 yield하도록 했다.

 

이 과정에서 쓰레드가 타이머 인터럽트에 의해 전환되어서는 안되기 때문에 인터럽트를 끔으로써 원자 단위로 수행되도록 했다.

 

그리고 쓰레드 구조체에 wake_time이라는 멤버를 추가하여 깨어나야 할 미래의 시간을 기억하도록 했다.

 

 

 + thread_sleep_and_yield() 추가

/* 쓰레드를 sleep_list에 넣어주자 */
void thread_sleep_and_yield(void) {
	struct thread *curr = thread_current();
	
	if (curr != idle_thread)
		list_insert_ordered(&sleep_list,&curr->elem,thread_less,NULL);
		if (list_begin(&sleep_list) == &curr->elem){
			min_wake_ticks = curr->wake_time;
		}
		curr->status = THREAD_SLEEPING;
		schedule ();
}

/* a가 작으면 true 를 보내주는 함수로, list_insert_ordered()에서 오름차순 정렬을 위해 사용 */
static bool
thread_less (const struct list_elem *a_, const struct list_elem *b_,
            void *aux UNUSED) 
{
  const struct thread *a = list_entry (a_, struct thread, elem);
  const struct thread *b = list_entry (b_, struct thread, elem);
  
  return a->wake_time < b->wake_time;
}

 

sleep한 thread를 재우는 list로 삽입시키는 함수이다.

 

 

밑의 thread_less 함수를 보면 삽입한 thread를 wake_time이 오름차순 상 배치되어야 하기 때문에

 

a가 작을 때 true를 반환하는 함수를 사용해서 list_insert_ordered()로 sleep_list에 추가했다.

 

 

그리고 만약에 삽입한 현재 쓰레드가 일어나야 할 가장 가까운 미래라면

 

지역 변수인 min_wake_ticks에 일어나야 할 시간을 적어놓는다.

 

 

이후 해당 로직을 위해 thread status 멤버에 추가한 sleeping 상태로 전환해 준 뒤, schedule()을 수행하도록 했다.

 

여기서 중요한 것은 do_schedule이 아닌 바로 context_switching을 하는 schedule()함수로 넘어가는 것이다.

 

do_schedule은 지난 포스팅 때 살펴봤듯이, 상태를 변환하는 로직이 있지만, 쓰레기통을 비우는 로직이 존재한다.

 

 

이 로직은 해당 상황에서는 전혀 불필요하며, 쓰레기통을 비우는 로직은 매 타이머 인터럽트마다 발생하는 yield()에서 수행할 로직이다.

 

따라서 이 do_schedule()은 건너 뛰면서 schedule()로 가도록 했다.

 

 

 

여기까지 진행하면 timer_sleep()을 통해 잠자게 된 쓰레드는 ready_list로 들어가지 않아 CPU를 점유하지 않게 된다.

 

 

---

 

하지만 wake_time이 지나면 해당 쓰레드 들은 sleep_list로 부터 준비상태로 변환된 후 ready_list로 이동되어야 할 것이다.

 

따라서 잠자고 있는 쓰레드들을 깨워주는 로직을 추가해 보았다.

 

변경된 timer_interrupt()

 

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

 

잠자게 된 쓰레드가 깰 시간인지 확인하기 위해 time_to_wake() 함수를 매 타이머 인터럽트마다 확인하는 함수를 추가했다.

 

해당 함수는 아래에 자세히 설명하고 지금은 매 인터럽트마다 발생시키기 위해 이 곳에 추가했다는 것을 확인할 수 있다.

 

 

 

 

time_to_wake()

 

/* 일어나야 하는 쓰레드를 전부 깨워보자.*/
void time_to_wake (void){
	int64_t now_time = timer_ticks();
	if (min_wake_ticks > timer_ticks){
		return;
	}

	struct thread *t;
	struct list_elem *telem;

	for(telem=list_begin(&sleep_list); telem!=list_end(&sleep_list);) {
		t = list_entry (telem, struct thread, elem);
		if(t->wake_time <= now_time){
			telem = list_remove(telem);
			list_push_back (&ready_list, &t->elem);
			t->status = THREAD_READY;
			t->wake_time = 0;
		}
		else {
			struct list_elem *min_wake_elem = list_begin(&sleep_list);
			struct thread *min_wake_thread = list_entry(min_wake_elem, struct thread, elem);
			min_wake_ticks = min_wake_thread->wake_time;
			break;
		}
		
	}
}

 

맨 처음에 지역변수로 기억해두었던 깨어야 하는 최소 시간을 확인하고

 

현재시간보다 아직 미래라면 해당 함수를 실행하지 않도록 했다.

 

 

이후 thread가 리스트에 저장되어있는 상태인 elem 멤버를 하나씩 확인하는 for문을 돌면서

 

깨어야 하는 thread라면 해당 쓰레드를 ready_list에 넣고 READY 상태로 변환시킨 후 wake_time을 초기화한다.

 

 

만약 다음 쓰레드를 검사했을 때 아직 깰 시간이 안됬다면 오름차순으로 정렬되었기 때문에 그 이후의 쓰레드는 모두 확인할 필요가 없다.

 

따라서 지역변수 min_wake_ticks를 가장 가까운 미래로 변경시켜준 뒤 break문을 넣어 for문을 탈출했다.

 

 

++ 그 외의 신경써야 할 것들

 

 

thread_init() 에 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 (&sleep_list);
	list_init (&destruction_req);

	/* 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 ();
}

 

list_init으로 sleep_list를 추가해야만 해당 리스트에 저장이 가능한 것은 당연하다.

 

 

 

2. thread.h

 

enum thread_status {
	THREAD_RUNNING,     /* Running thread. */
	THREAD_READY,       /* Not running but ready to run. */
	THREAD_BLOCKED,     /* Waiting for an event to trigger. */
	THREAD_DYING,        /* About to be destroyed. */
	THREAD_SLEEPING,    /* 일정기간동안 쓰레드 재우기*/
};


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_time;
	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */


void thread_sleep_and_yield(void);
void time_to_wake (void);

 

추가 된 함수는 declaration하여야 하며, 추가된 멤버와 요소들은 수정해 주어야 한다.