(2021.10.02) Alarm Clock - timer_sleep() 수정

1. 서론 및 필요 내용 설명

지난 포스팅에서 개괄적인 로드맵을 설정했으니, 이번에는 두 가지 사항 중 첫 번째인 Thread를 재우는 루틴부터 완성하자. timer_sleep()은 현재 실행되던 Thread를 Block하고 Block된 Thread를 관리하도록 해야 한다. Pintos에서 Ready 상태의 Thread는 ready_list라는 list형 자료구조를 사용해 관리되고 있다. 이와 비슷하게 timer_sleep()이 호출되어 Block될 Thread를 일괄적으로 넣을 sleep_list 같은 자료구조를 만든다면, 관리가 용이할 것이다.

 

여기서 질문할 수 있다. 모든 Thread가 Block 될 때 timer_sleep()에 의해서 Block 되는 것은 아닐 텐데 그런 것들은 어떻게 관리하는가? 나머지 코드를 좀 더 보면 그 답을 알 수 있는데, 기본 구현의 Pintos에서 thread_block()이 호출되는 곳은 devices/intq.c와 threads/synch.c에서이다. 그중 intq.c에서는 자체적인 구조체를 활용해서 Block 되는 Thread를 관리하고 있으며, synch.c에서는 나중에 따로 다시 다루겠지만 semaphore의 waiters라는 독자적인 리스트에 Thread 구조체를 넣어 관리하고 있다. 따라서, 나머지 Thread가 Block 되는 경우를 제외하면 남은 경우는 timer_sleep()가 불리는 문제의 상황뿐이며, 이에 이들만을 따로 모은 sleep_list에 관리하는 것이 용이하다는 결론을 지을 수 있다.

 

이를 위해서 일단 Pintos에서 구현한 list 자료구조에 대해 자세히 짚어보고 넘어가도록 하자.

 

---

 

lib/kernel/list.c와 include/lib/kernel/list.h에 있는 코드를 살펴보면 list_elem 구조체가 list 구현 방식에 있어 핵심인 것을 알 수 있다. list_elem은 흔히 doubly linked list에서 보이는 구조인 prev, next 포인터를 가지고 있다. 특이하게도 보통 doubly linked list에서 이러한 구조체는 각 노드로 사용되기에, 각 노드에서 가지고 있어야 할 데이터 멤버를 포함하는데, 해당 구현 방식에서는 존재하지 않는다. 그리고 아이러니하게도 이러한 특징으로 인해 list_elem을 활용하면 list의 범용성을 확보할 수 있다.

/* List element. */
struct list_elem {
	struct list_elem *prev;     /* Previous list element. */
	struct list_elem *next;     /* Next list element. */
};

/* List. */
struct list {
	struct list_elem head;      /* List head. */
	struct list_elem tail;      /* List tail. */
};

Pintos의 list는 list_elem 내부에 데이터를 넣는 것이 아닌, 데이터를 가진 구조체 내부에 list_elem을 심어 연결고리로 사용한다. 즉, 특정한 구조체를 엮어 list로 만들기 위해서는 다음 그림과 같이 list_elem 구조체를 list로 만들고 싶은 구조체의 원소로 포함시킨다. 해당 구조체 내에서 list_elem은 다른 list_elem을 가리키는 포인터를 가지고 있기에 list 내의 연결을 담당하게 된다.

 

 

Pintos의 list 구현 방식

 

이 구조상 list_elem끼리는 서로 포인터를 사용해 접근할 수 있는 것을 알 수 있다. 하지만 우리가 궁극적으로 원하는 것은 각 노드의 데이터를 읽고 쓰는 것이며, 이는 노드를 가리키는 포인터를 통해서 접근할 수 있기 때문에 뭔가 연산이 더 필요하다. 이 때, list_elem이 항상 구조체의 맨 처음에 위치하고 있다고 보장할 수 없기 때문에 list_elem이 구조체 내에서 차지하고 있는 위치를 기반으로 구조체의 주소를 계산을 해 줄 필요가 있다. 이를 위해 Pintos에서는 list_elem을 활용해 해당 list_elem이 포함된 구조체의 포인터를 얻어내는 다음의 매크로를 제공한다.

/* Converts pointer to list element LIST_ELEM into a pointer to
   the structure that LIST_ELEM is embedded inside.  Supply the
   name of the outer structure STRUCT and the member name MEMBER
   of the list element.  See the big comment at the top of the
   file for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
	((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
		- offsetof (STRUCT, MEMBER.next)))

매크로에 접근하고자 하는 구조체의 list_elem 주소, 해당 구조체의 이름, 구조체 내에서의 list_elem의 이름(멤버명)을 넣으면 그 구조체를 가리키는 포인터로 변환한다. 이를 이용해 주어진 list에서 list_elem을 따라 전체를 순환하면서 각 구조체의 데이터를 읽고 수정하는 것이 가능해진다.

 

기타 list 관련 함수는 lib/kernel/list.c에서 찾아보면 된다. 큰 구조를 알았으니 나머지는 이해하기 쉬울 것이다. 이제 list의 구현 방식을 익혔으니 이를 활용해 sleep_list를 추가하자.

 

---

2. 구현해야 하는 것

• sleep_list의 추가 및 init
• sleep_list에 Thread를 넣는 루틴

 

---

3. 구현 과정

3-1. sleep_list 구현

논리적으로 생각했을 때, Block이 된 Thread는 Ready 상태가 아니며, Ready 상태일 때는 Block 상태가 아니므로 sleep_list와 ready_list는 그 원소를 공유하지 않는다. 따라서 현재 thread.h에 구현되어 있는 thread 구조체 내의 list_elem elem을 활용해 block_list를 관리해도 문제 되지 않는다는 것이다. 실제로 코드 위 주석에서도 이러한 점을 설명하며 이중의 목적으로 활용하라고 나와있으며, 다른 방식으로 Block 되는 코드에서도 elem을 활용해 list_push_back()을 호출하는 것을 볼 수 있다. 주석에서 semaphore에 관련된 내용은 일단 지금은 무시하자.

/* The `elem' member has a dual purpose.  It can be an element in
 * the run queue (thread.c), or it can be an element in a
 * semaphore wait list (synch.c).  It can be used these two ways
 * only because they are mutually exclusive: only a thread in the
 * ready state is on the run queue, whereas only a thread in the
 * blocked state is on a semaphore wait list. */
struct thread {
	...
    
	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
	...
};

이제 코드를 수정해보자. 우선 thread.c에 sleep_list 선언을 해주고

/* List of processes in THREAD_BLOCKED state, due to timer_sleep() */
static struct list sleep_list;

thread_init 에서 ready_list와 같이 list_init을 해준다.

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

이제 sleep_list를 활용하기 위한 준비는 끝났다. 여기서 문제는 sleep_list가 선언된 위치가 thread.c이기 때문에 timer.c에서는 직접 접근할 수 없다는 것이다. 그래서 이를 위해 sleep_list에 현재 실행되고 있는 thread를 넣은 뒤 thread_block을 호출하는 함수인 thread_sleep()을 새로 작성했다.

/* Wrapper function for blocking thread when timer_sleep() gets called.
   Used only for timer_sleep() */
void
thread_sleep () {
	struct thread *cur = thread_current ();
	list_push_back (&sleep_list, &cur->elem);
	thread_block ();
}

이제 이 thread_sleep()을 timer_sleep()에서 부르도록 수정만 하면 거의 끝날 것 같지만 그리 간단하지는 않다.

3-2. 인터럽트 조건 충돌 문제 해결

기본 구현된 timer_sleep()의 코드를 보면 반드시 인터럽트가 켜진 상태에서 호출되어야 한다고 나와 있다. 상식적으로 생각해도, 어떤 Thread가 잠들었다가 타이머 알람을 듣고 일어나기 위해서는 인터럽트가 켜진 상태여야 할 것이다.

void
timer_sleep (int64_t ticks) {
	...
	ASSERT (intr_get_level () == INTR_ON);
	...	
}

문제는 thread_block의 주석과 코드에서 반드시 인터럽트가 꺼진 상태에서 호출되어야 한다고 명시하고 있는 점이다. 인터럽트가 꺼진 상태여야 하는 것은 해당 코드가 방해받지 않고 한 번에 실행되어야 하는 atomic code이기 때문이다. 이에 대해서는 semaphore와 lock에 대해 설명할 때 다시 설명하도록 하겠다. 일단 지금으로서는 thread_block 이 실행되는 사이엔 다른 Thread가 CPU를 뺏어가면 안 되고, 이를 위해서는 인터럽트가 꺼진 상태가 전제되어야 한다고 이해하면 된다.

/* Puts the current thread to sleep.  It will not be scheduled
   again until awoken by thread_unblock().

   This function must be called with interrupts turned off.  It
   is usually a better idea to use one of the synchronization
   primitives in synch.h. */
void
thread_block (void) {
	...
	ASSERT (intr_get_level () == INTR_OFF);
	...
}

이 때문에 필요한 조건이 상충하기 때문에 timer_sleep()가 불린 이후와 thread_block()가 호출되기 이전에 무언가 조치가 이루어져야 한다. 

 

이를 해결하려면 현재의 인터럽트 상태를 저장한 다음, 인터럽트를 끄고, 필요한 함수가 모두 실행된 이후에 다시 인터럽트 상태를 처음과 같이 복원하는 일련의 과정이 필요하다. 이러한 코드 구조는 thread_unblock에서도 찾아볼 수 있다.

void
thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t));

	old_level = intr_disable ();
	ASSERT (t->status == THREAD_BLOCKED);
	list_push_back (&ready_list, &t->elem);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

간략히 설명을 하자면, intr_disable()을 통해 old_level에 기존의 인터럽트 상태를 저장함과 동시에 인터럽트를 해제하고, 필요한 모든 과정이 끝난 뒤 다시 intr_set_level (old_level) 을 통해 인터럽트 상태를 기존으로 복구하는 것이다. 이런 일련의 과정을 timer_sleep()이 호출되었을 때도 시행해주면 해결이 될 것이다. 인터럽트 조건 충돌을 해결하여 구현한 timer_sleep()의 흐름도는 이런 형태일 것이다.

 

timer_sleep() 호출 시의 흐름도 예시

 

여기까지의 과정을 종합해 수정한 timer_sleep()은 아래와 같다.

void
timer_sleep (int64_t ticks) {
	enum intr_level old_level;

	ASSERT (intr_get_level () == INTR_ON);
	old_level = intr_disable ();
	thread_sleep();

	intr_set_level (old_level);
}

허나 아직 중요한 것이 빠졌다.

3-3. wakeup_tick 추가

현재 구현 상태로는 파라미터로 넣어준 ticks 값이 반영이 안 되어 언제 Thread를 깨울지 알 수 없다. 이를 해결하기 위해서 Thread를 깨울 시간을 어딘가에는 저장해둘 필요가 있다. 물론 다양한 구현 방식이 있을 수 있겠지만 가장 간단한 방법이라고 생각한 것은 thread 구조체 내에 Thread를 깨울 시간을 저장하는 것이다.

 

이를 위해서 wakeup_tick이라는 변수를 thread 구조체에 추가하고, timer_sleep()가 불린 시점에서의 tick과 파라미터로 들어온 ticks를 더해 값을 저장하는 식으로 Thread를 깨울 시간을 표기한다. 물론 이에 맞춰서 thread_sleep()의 형태 또한 바꿔준다.

 

wakeup_tick을 활용하면 이점이 하나 더 생긴다. 바로 sleep_list에 Thread를 넣을 때 wakeup_ticks를 기준으로 빨리 깨어나야 하는 순으로 정렬하여 넣을 수 있다는 것이다. 이런 식으로 정렬을 하여 관리하면 나중에 타이머 인터럽트 핸들러가 깨울 Thread를 찾을 때 sleep_list 전체를 순환하지 않고 일정 기점이 지나면 바로 탐색을 멈출 수 있다. 그러하면 비교적 시간을 적게 소비해야 하는 인터럽트 작업 시에 이득을 볼 수 있다.

 

정렬을 하면서 list에 넣는 함수는 list_insert_ordered를 사용하며, 이를 위해서는 비교함수가 필요하기에 코딩해서 넣어준다. 여기까지 구현한 뒤, 주요한 함수들을 살펴보면 다음과 같다.

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

	ASSERT (intr_get_level () == INTR_ON);
	old_level = intr_disable ();

	int64_t wakeup_tick = timer_ticks () + ticks;
	thread_sleep(wakeup_tick);

	intr_set_level (old_level);
}

// thread.c
bool 
cmp_wakeup (const struct list_elem *a, const struct list_elem *b, void *aux) {
	struct thread *t_a = list_entry(a, struct thread, elem);
	struct thread *t_b = list_entry(b, struct thread, elem);
	return t_a->wakeup_tick < t_b->wakeup_tick;
}

/* Wrapper function for blocking thread when timer_sleep() gets called.
   Used only for timer_sleep() */
void
thread_sleep (int64_t ticks) {
	struct thread *cur = thread_current ();
	cur->wakeup_tick = ticks;
	list_insert_ordered(&sleep_list, &cur->elem, cmp_wakeup, NULL);
	thread_block ();
}

 

---

4. 디버깅

우선 이 시점에서는 아직 실행시킬 수 없으므로 디버깅은 할 수 없다. 다음 포스팅에서 타이머 인터럽트 핸들러에 Unblock하는 루틴을 넣은 뒤 디버깅하도록 한다.