PintOS Project 1.1 - Alarm clock (정글사관학교 56일차 TIL)

대망의 핀토스 프로젝트가 시작됐다. 오늘은 시작한지 5일차. 운영체제 이론 공부(~데드락)를 마치고 과제를 보니까 이건 뭐 또다른 신세계.. 하지만 조급해하지 않고 차근차근 공부해보자.

 

과제 설명부터 보겠다. (과제 링크는 여기)

Reimplement timer_sleep(), defined in devices/timer.c.

현재 코드는 작동하나, 지금 코드는 busy-wait 방식이다. 이는 현재 시간(tick)을 계속 체크한 뒤, 충분한 시간이 지나기 전까지 계속해서 thread_yield() 함수를 호출하는 루프를 돈다. 이러한 busy waiting을 피하기 위해 코드를 다시 짜라.

쓰레드 호출을 최소한 x 시간이 지난 후에 진행할 수 있도록 지연해라. 만약 시스템이 idle 상태가 아니라면, thread는 정확히 x tick 후에 일어날 필요가 없다. 그냥 충분한 시간 동안 재운 다음, 일정 시간이 지나면 ready queue에 넣어라.

 

이를 위해 timer_sleep()을 비롯하여 thead 디렉토리 내부에 thread.c와 devices 디렉토리 내 timer.c 내부에 정의된 함수를 수정하라는 것이 첫번째 과제.

 

정답 코드야 어찌어찌 찾으면 널려있다. 중요한 건 이를 어떻게 해결하는지 흐름을 그려가는 것.

 

1. 현재 구현방식(busy wait) 소개: 왜 비효율적인가?

 

먼저 busy-wait 방식이 무엇인지부터 보자. 이를 이해하려면 synchronization에 대한 개념이 필요한데, 간략하게만 설명한다. 서로 다른 두 프로세스가 공유 가능한 자원에 동시에 접근하면 어떻게 할까? 예를 들어 커널 코드가 수행 중이고 커널에서 Count라는 변수에 1을 더하라는 명령을 내리고 있는 상황이라고 하자. 이때, 갑자기 인터럽트가 들어와서 Count를 1만큼 빼라는 명령을 수행하려 한다면? 커널에 있는 데이터를 양쪽에서 건드리게 된다. 이와 같이 공유 데이터에 동시 접근을 허용하면 데이터 불일치 문제가 발생한다.

 

이를 해결하기 위한 방식 중 하나가 busy-wait이다. 즉, 어떤 프로세스 A가 CPU를 점유하고 공유 데이터를 만지작하던 와중에 할당 시간이 만료되어 프로세스 B로 CPU를 빼앗겼다고 하자. 이때, 프로세스 B가 공유 자원에 접근하기 위해서는 특정 조건을 만족해야 한다. 조건을 만족하면 running으로 넘어가는데, 그렇지 못하면 ready 상태로 넘어가 ready queue에서 대기해야 한다. 여기까지 보면 별 이상한 점이 없어 보이나, 아래 과제 관련 코드를 보도록 하자.

 

timer_sleep()

@/devices/timer.c
 
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks (); // start: 시작 시 시간(tick)
 
	ASSERT (intr_get_level () == INTR_ON); // 인터럽트가 들어왔을 때에만 실행
	while (timer_elapsed (start) < ticks) // start로부터 ticks만큼 시간이 지나기 전까지 
		thread_yield (); // CPU를 양보한다.
}

위 함수 timer_sleep()은 시작 시간 start를 기준으로 매 tick(100분의 1초를 뜻하며 시스템 내 timer가 알아서 시간을 잰다)마다 ticks

와 timer_elapsed(start)를 비교한다. timer_elapsed()는 start를 기점으로 얼마나 시간이 지났는지(변화량)를 반환한다. 매번 while문을 돌면서 현재 시간이 주어진 ticks보다 작다면 아래 thread_yield()를 수행한다. 

 

즉, timer_sleep() 함수의 역할은 "특정 시간(start)으로부터 일정 시간 ticks만큼 지나기 전까지는 CPU를 양보하고 스레드를 활성화시키지 않는" 것이다. 곧바로 thread_yield()를 보면 아래와 같다.

thread_yield()

@/thread/thread.c
/* 현재 running 중인 스레드를 비활성화 시키고 ready_list에 삽입.*/
void
thread_yield (void) {
	struct thread *curr = thread_current (); //현재 실행 중인 스레드
	enum intr_level old_level; //인터럽트 level: on/off

	ASSERT (!intr_context ()); // 외부 인터럽트가 들어왔으면 True / 아니면 False

	old_level = intr_disable (); // 인터럽트를 비활성하고 이전 인터럽트 상태(old_level)를 받아온다.
	if (curr != idle_thread) // 현재 스레드가 idle 스레드와 같지 않다면
		list_push_back (&ready_list, &curr->elem); // ready리스트 맨 마지막에 curr을 줄세워.
	do_schedule (THREAD_READY); // context switch 작업 수행 - running인 스레드를 ready로 전환.
	intr_set_level (old_level); // 인자로 전달된 인터럽트 상태로 인터럽트 설정하고 이전 인터럽트 상태 반환
}

thread_yield()는 현재 running 중인 스레드를 비활성화 시킨 뒤 ready_list에 삽입하는 함수이다. 현재 스레드가 idle thread(유휴 스레드로, CPU가 유휴 스레드에 할당되면 놀고 있는 상태가 된다)가 아니면, 즉 CPU가 일을 해줘야 하는 쓰레드라면 ready_list에 현재 스레드를 줄세운다. 그 다음, 현재 running 상태인 스레드를 ready 상태로 전환하기 위해 context switch 작업을 수행한다.

 

이쯤에서 thread의 상태도(아래 이미지)를 보자. thread_yield()는 현재 스레드를 ready_list 맨 뒤에 줄세운 다음 상태를 running에서 ready로 바꾼다. (do_schedule()은 현재 스레드를 인자로 받은 상태로 바꾸고 ready_list에서 기다리던 그 다음 스레드를 running으로 바꾼다. 즉, 두 스레드의 상태를 샤샥 바꾸는 함수) 얘기가 길어지는데 양해 부탁,,

 

다시 핀토스 첫 문제로 가보자. 한양대 핀토스 자료에서는 기존의 busy waiting 방식을 아래와 같이 보여주고 있다. 위의 두 함수를 종합해서 아래 이미지를 해석하면,

 

1. timer_sleep()에서는 start 시점에서 ticks만큼의 시간이 지나기 전까지 매 tick마다 thread_yield()를 호출한다.

2. thread_yield()는 현재 running 중인 스레드를 ready_list의 맨 마지막(tail)에 넣는다(현재 주황색 블록).

3. 그 다음, thread_yield() 내에서 do_schedule()을 호출해 현재 thread(주황색)의 상태를 ready로 변경하고 ready_list의 맨 앞(head)에 있는 애를 running 상태로 변경한다. 밑의 그림에서라면 head에 있는 가장 맨앞 블록이 running 블록이 된다.

4. 그런데 while문을 돌면서 매 tick마다 1-3이 반복되니까, 결과적으로는 ticks만큼의 시간이 지날 때까지 head에 있는 블록을 빼서 tail에 넣는 작업을 반복하는 게 된다.

이래서 무의미하게 CPU를 낭비한다는 것. ready_list에 넣는다는 것 자체가 지금 cpu를 할당하지 않겠다는 것인데, 그렇게 하기 위해 매번마다 재워야 할 애를 깨우고 다시 재우고의 반복이니..이를 해결하는 방법이 바로 아래 소개할 sleep & awake 방식.

 

2. Sleep-awake solution: 왜 효율적인가?

위에서 발생하는 문제는 ready_list 하나로 스레드를 관리하려다보니 생기는 것이다. 따라서, 우리는 우리가 sleep시키고 싶은 시간 동안 스레드를 따로 줄세우는 공간으로써 sleep_list를 하나 더 만든다. 이렇게 해놓으면, 각 스레드 안에 일어나야 하는 시간을 기록해두고 재운 다음, 해당 시간이 됐을 때 그 애를 찾아 깨워서 ready_list에 넣는 방식으로 운영할 수 있다. 이때의 장점은, 위에서는 CPU가 쉼 없이 일해야 하다보니 전력소모가 엄청 심한 반면 아래의 케이스에는 재우고 깨우는 이외의 시간에는 CPU가 idle thread를 잡고서 쉴 수 있어서 전력 소모가 훨씬 덜하다는 장점이 있다.

 

 

이 방식의 솔루션은 다음과 같다.

1. timer_sleep() 호출 시 thread를 ready_list에서 제거한 뒤 sleep_queue에 추가한다.

2. wakeup 함수를 수행한다(새로 설계). wakeup 함수는 timer_interrupt가 발생할 시 tick을 체크한다. 시간이 다 된 thread는 queue에서 삭제하고 ready_list에 추가한다.

 

1) 전역변수 추가

thread.h

@/threads/thread.h

/*----project 1------*/

/* 실행 중인 스레드를 슬립으로 재운다. */
void thread_sleep(int64_t ticks);
/* 슬립 큐에서 깨워야 할 스레드를 깨운다. */
void thread_awake(int64_t ticks);
/* 최소 틱을 가진 스레드를 저장한다. */
void update_next_tick_to_awake(int64_t ticks);
/* thread.c의 next_tick_to_awake 반환 */
int64_t get_next_tick_to_awake(void);

 

thread.c

/* --------- Project 1 ----------*/

/* sleep list: thread blocked 상태의 스레드를 관리하기 위한 리스트 자료구조 */
static struct list sleep_list;
/* next tick to awake: 슬립 리스트에서 대기 중인 스레드들의 wakeup_tick 값 중 최솟값을 저장 */
static int64_t next_tick_to_awake;

static long long next_tick_to_awake;

thread_init()

• thread를 초기화할 때 sleep_list와 next_tick_to_awake를 각각 초기화해준다.
• next_tick_to_awake 전역 변수: sleep_list에서 대기 중인 스레드들의 wakeup_tick 값 중 최솟값을 저장

thread_init (void) {
    ...
    
    /* ------ Project 1 -------- */
	/* 슬립 큐 & next tick to awake 초기화 코드 추가 */
	list_init (&sleep_list);
	next_tick_to_awake = INT64_MAX; // 최솟값 찾아가야 하니 초기화할 때는 정수 최댓값.
	/* ------ Project 1 -------- */
    }

 

timer_sleep()

• 기존 busy waiting 유발하는 while문 코드 삭제
• sleep_list를 이용하도록 함수를 수정

@/devices/timer.c

/*----project 1 ----*/
/* 기존 busy waiting 유발 코드: while 문에서 계속 뱅글뱅글 돌아.*/
/* thread_sleep()을 사용한다.*/
void
timer_sleep (int64_t ticks) { // 인자로 주어진 ticks 동안 스레드를 block
	int64_t start = timer_ticks (); // 현재 진행되고 있는 tick 값 반환

	ASSERT (intr_get_level () == INTR_ON); // 인터럽트를 켜놨는지 체크.
	thread_sleep(start+ticks); //start 타임에서 원하는 tick만큼 재워
}

 

thread_sleep()

• thread를 sleep_list에 삽입하고 blocked 상태로 만들어 대기
• 해당 과정 중에는 인터럽트를 받지 않는다.
• devices/timer.c

@/threads/thread.c

/* thread_sleep: thread_yield를 기반으로 만든다. */
void thread_sleep(int64_t ticks) {
	struct thread *curr = thread_current();
	enum intr_level old_level;

	/* Thread를 blocked 상태로 만들고 sleep queue에 삽입해서 대기 */
	ASSERT (!intr_context ()); // 외부 인터럽트 프로세스 수행 중이면 True, 아니면 False
	//ASSERT (intr_get_level () == INTR_OFF); 얘는 여기서 필요 없음. 이건 
	
	old_level = intr_disable();

	curr->wakeup_tick = ticks; // 현재 스레드를 깨우는 tick은 인자로 받은 tick만큼의 시간이 지나고서!
	/* thread를 sleep queue에 삽입 */
	if (curr != idle_thread) { // idle_thread: 유휴 스레드. running하지 않는.
		list_push_back (&sleep_list, &thread_current()->elem);
	}
	
	update_next_tick_to_awake(ticks); // 다음 깨워야 할 스레드가 바뀔 가능성이 있으니 최소 틱을 저장.
	do_schedule(THREAD_BLOCKED); // context switch: 이번에는 blocked(sleep) 상태로 바꿔줘.
	intr_set_level(old_level);
}

timer_interrupt()

• 매 tick마다 timer 인터럽트 시 호출되는 함수
• sleep queue에서 깨어날 thread가 있는지 확인
  • sleep queue에서 가장 빨리 깨어날 thread의 tick 값을 확인
  • 있다면 sleep_list를 순회하면서 쓰레드를 깨운다. 이때 사용하기 위해 thread_awake() 함수를 짠다

@/devices/timer.c

/* Timer interrupt handler. */
/* ---project 1---*/

/*
timer_interrupt: 매 tick마다 timer 인터럽트 시 호출하는 함수.
- sleep queue에서 깨어날 스레드 있는지 확인
	- sleep queue에서 가장 빨리 깨어날 스레드의 tick값을 확인
	- 있다면 sleep queue를 순회하며 스레드를 깨운다.
	- 이때 thread_awake()를 사용.

	timer_interrupt가 들어올 때(시간이 증가할 때),
	현재 ticks보다 작은 wakeup_tick(깨어나야 할 시간)이 있는지 판단.
	있다면 
*/
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++; // 틱 올리고
	thread_tick (); // 코드 제출했을 때 검사하는 함수. 신경 니니.
	int64_t next_tick;
	next_tick = get_next_tick_to_awake(); // next_tick에 깨워야 할 다음 tick을 받아와.
	
	/* --- pjt 1 --- */
	if (ticks >= next_tick) { // 현재 ticks가 next_tick보다 크면 깨워야지.
		thread_awake(ticks);
	}
}

 

thread_awake()

• wakeup_tick값이 인자로 받은 ticks보다 크거나 같은 스레드를 깨운다.
• 현재 대기 중인 스레드들의 wakeup_tick 변수 중 가장 작은 값을 next_tick_to_awake 전역 변수에 저장한다.

@/threads/thread.c

void thread_awake(int64_t ticks) {
	/* Sleep queue에서 깨워야 할 thread를 찾아서 wakeup */
	next_tick_to_awake = INT64_MAX;
	struct list_elem *e = list_begin(&sleep_list); // sleep list의 첫번째 elem
	struct thread *t;

	/* 역할 1: sleep_list의 스레드를 모두 순회하면서 wakeup_tick이 ticks보다 작으면 깨워야!*/
	for (e; e != list_end(&sleep_list);)
	{
		t = list_entry(e, struct thread, elem); // sleep list에 들어있는 엔트리 중에서 계속 돌아.
		if (t->wakeup_tick <= ticks) // 깨워달라 한 시간(wakeup_tick)보다 지금 시간(ticks)이 지났다면
		// 이때 지금 시간(ticks)은 thread_awake()를 실행하기 직전의 next_tick_to_awake.
		{
			e = list_remove(&t->elem); // 얘네들은 다 깨워야지. 현재 t는 sleep_list에 연결된 스레드.
			thread_unblock(t); // 리스트에서 지우고 난 다음 unblock 상태로 변경!
			// 여기서는 list_remove에서 이미 다음 리스트로 연결해주니 list_next가 필요 X.
		}
		/* 역할 2: 위에서 thread가 일어났다면 sleep_list가 변했으니 next_tick_to_awake가 바뀜.
		현재 ticks에서 일어나지 않은 스레드 중 가장 작은 wakeup_tick이 next_tick_to_awake. 얘를 갱신. 
		즉, 아직 깰 시간이 안 된 애들 중 가장 먼저 일어나야 하는 애를 next_tick_to_awake!*/
		else {
			update_next_tick_to_awake(t->wakeup_tick);
			e= list_next(e); //위에서는 애를 리스트에서 지우니까 for문 돌고 나면 알아서 갱신. 여기는 그게 아니니 list_next로 갱신.
		}
	}
}

 

 

update_next_tick_to_awake() / get_next_tick_to_awake()

void update_next_tick_to_awake(int64_t ticks) {
	next_tick_to_awake = MIN(next_tick_to_awake, ticks);
}

int64_t get_next_tick_to_awake(void) {
	return next_tick_to_awake;
}

 

3. 결과

와..한 번에 다 정리하려니까 돌아버리겠네..

보다 자세한 내용은 불냥이 블로그를 참조하시길.. 낼모레까지 pjt 1 다 마무리하면 마저 쓰겠다...

 

 

4. 추가 함수 정리(함수 흐름대로 따라가면 위의 내용을 보다 더 잘 이해할 수 있습니다)

 

do_schedule():

새로운 프로세스를 스케쥴링하는 함수. 현재 running 중인 스레드 상태를 status(ready일 수도 있고 종료시킬 수도 있고 등등)로 바꾸고 ready_list 맨 앞에 줄서있던 스레드를 running으로 바꾼다. 인터럽트가 없으며 현재 스레드 상태가 running일 때 실행한다.

 

*destruction_req 리스트에 있는 스레드는 제거 요청이 들어온 스레드로, 제 할일을 다했던 뭘 했던 제거해줘야 할 스레드이다. 이 제거해야 할 스레드 리스트 destruction_req 맨 앞에 있는(=list_pop_front) 스레드를 victim으로 지정하고 얘에 할당된 page를 해제한다. 즉, 스레드를 제거하고 걔한테 줬던 메모리를 받아오는 것. 이 작업이 끝나면 현재 스레드 상태를 status로 바꾸고 schedule()로 새 스레드를 할당시킨다.

/* Schedules a new process. At entry, interrupts must be off.
 * This function modify current thread's status to status and then
 * finds another thread to run and switches to it. */

static void
do_schedule(int status) { // 현재 running 중인 스레드를 status로 바꾸고 새로운 스레드를 실행.
	ASSERT (intr_get_level () == INTR_OFF); //현재 인터럽트가 없어야 하고 
	ASSERT (thread_current()->status == THREAD_RUNNING); // 현재 스레드 상태가 running일 때 실행.
	while (!list_empty (&destruction_req)) {destruction_req 리스트가 빌 때까지
		struct thread *victim =
			list_entry (list_pop_front (&destruction_req), struct thread, elem);
		palloc_free_page(victim);
	}
	thread_current ()->status = status;
	schedule ();
}

schedule():

현재 running 중인 스레드를 빼내고 줄 서있는 스레드 중 다음에 running해야 할 스레드를 running 상태로 변경해준다. 즉, 다음 차례에 있는 스레드에 CPU를 할당해주는 것. 이때, 만약 다음에 줄 서있는 스레드가 없다면 쉬어도 된다는 뜻이니 idle_thread를 잡고 놀게 된다.

 

마지막에 next에 있는 다음 스레드에 대해 thread_launch() 실행하는데, CPU 제어권을 넘기는 context switching을 수행한다.

static void
schedule (void) { // running인 스레드를 빼내고 next 스레드를 running으로 만든다.
	struct thread *curr = running_thread ();
	struct thread *next = next_thread_to_run ();

	ASSERT (intr_get_level () == INTR_OFF);
	ASSERT (curr->status != THREAD_RUNNING);
	ASSERT (is_thread (next));
	/* Mark us as running. */
	next->status = THREAD_RUNNING;

	/* Start new time slice. */
	thread_ticks = 0;

#ifdef USERPROG
	/* Activate the new address space. */
	process_activate (next);
#endif

	if (curr != next) {
		/* If the thread we switched from is dying, destroy its struct
		   thread. This must happen late so that thread_exit() doesn't
		   pull out the rug under itself.
		   We just queuing the page free reqeust here because the page is
		   currently used bye the stack.
		   The real destruction logic will be called at the beginning of the
		   schedule(). */
		if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
			ASSERT (curr != next);
			list_push_back (&destruction_req, &curr->elem);
		}

		/* Before switching the thread, we first save the information
		 * of current running. */
		thread_launch (next);
	}
}

 

thread_launch():

스레드를 context switching한다. 즉, 현재까지 작업을 문맥에 저장하고 CPU 제어권을 다음으로 선택한 프로세스에게 넘기는 작업이다. 아무래도 여기서는 하드웨어까지 건드려야 하니 어셈블리어가 나온다. 스위칭 로직만 간단히 소개하면

 

- 첫번째로 전체 실행 문맥을 intr_frame에 저장한다.

- 그 다음에는 다음 스레드에게 스위칭해준다. 스위칭이 끝나기 전까지는 스택을 사용해서는 안된다.

- 스위칭이 끝나면 레지스터를 저장한다.

static void
thread_launch (struct thread *th) {
	uint64_t tf_cur = (uint64_t) &running_thread ()->tf;
	uint64_t tf = (uint64_t) &th->tf;
	ASSERT (intr_get_level () == INTR_OFF);

	/* The main switching logic.
	 * We first restore the whole execution context into the intr_frame
	 * and then switching to the next thread by calling do_iret.
	 * Note that, we SHOULD NOT use any stack from here
	 * until switching is done. */
	__asm __volatile (
			/* Store registers that will be used. */
			"push %%rax\n"
			"push %%rbx\n"
			"push %%rcx\n"
			/* Fetch input once */
			"movq %0, %%rax\n"
			"movq %1, %%rcx\n"
			"movq %%r15, 0(%%rax)\n"
			"movq %%r14, 8(%%rax)\n"
			"movq %%r13, 16(%%rax)\n"
			"movq %%r12, 24(%%rax)\n"
			"movq %%r11, 32(%%rax)\n"
			"movq %%r10, 40(%%rax)\n"
			"movq %%r9, 48(%%rax)\n"
			"movq %%r8, 56(%%rax)\n"
			"movq %%rsi, 64(%%rax)\n"
			"movq %%rdi, 72(%%rax)\n"
			"movq %%rbp, 80(%%rax)\n"
			"movq %%rdx, 88(%%rax)\n"
			"pop %%rbx\n"              // Saved rcx
			"movq %%rbx, 96(%%rax)\n"
			"pop %%rbx\n"              // Saved rbx
			"movq %%rbx, 104(%%rax)\n"
			"pop %%rbx\n"              // Saved rax
			"movq %%rbx, 112(%%rax)\n"
			"addq $120, %%rax\n"
			"movw %%es, (%%rax)\n"
			"movw %%ds, 8(%%rax)\n"
			"addq $32, %%rax\n"
			"call __next\n"         // read the current rip.
			"__next:\n"
			"pop %%rbx\n"
			"addq $(out_iret -  __next), %%rbx\n"
			"movq %%rbx, 0(%%rax)\n" // rip
			"movw %%cs, 8(%%rax)\n"  // cs
			"pushfq\n"
			"popq %%rbx\n"
			"mov %%rbx, 16(%%rax)\n" // eflags
			"mov %%rsp, 24(%%rax)\n" // rsp
			"movw %%ss, 32(%%rax)\n"
			"mov %%rcx, %%rdi\n"
			"call do_iret\n"
			"out_iret:\n"
			: : "g"(tf_cur), "g" (tf) : "memory"
			);
}