[pintos] 1주차 - Alarm Clock 구현 과정

일단 키워드 공부를 가벼운 수준으로 끝내고, 막대한 양의 코드를 해석하기 시작했다. (이전 글 참고)

코드가 조금 숙지되고 나서 구현을 시작하려니 어디서부터 뭘 구현해야 할지 감이 안 잡혔다.

구현 요구사항 파악이 덜 되었기 때문이다..! 

그래서 내가 뭘 구현해야 할지부터 차근차근 정리했다.

이번 포스팅은 내가 alarm clock 프로젝트를 어떻게 구현했는지에 대한 내용이다.

 

 

📌 구현 요구 사항

timer_sleep()은 현재 스레드를 ticks 만큼의 시간 동안 재우는 함수이다. 원래 busy-wait으로 구현되어있었던 코드를 살펴보자.

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();[pintos] 3일차 - Alarm Clock 코드 정리
	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

인자로 넘겨준 ticks 만큼의 시간이 되지 않았으면 일단 cpu를 양보(yield)하고 본인은 계속 ticks 만큼의 시간이 지났는지 확인하고 있다.

즉 ticks 만큼의 시간 동안 실제로 스레드를 blocked 상태로 전환시켜서 그 동안은 cpu를 사용하는 일이 없게 만들어야 효율적인데, 그렇게 하지 않고 스레드를 ready 상태로 전환시켜서 자꾸 cpu를 할당받고 time slice 동안 cpu를 사용하면서 ticks 만큼의 시간이 지났는지 확인하게 만든다. (running → ready → running → ready를 반복하며 계속 ticks 만큼의 시간이 지났는지 확인)

따라서 지금 running → waiting → ready 로직을 만들어서 스레드가 ticks 시간 동안은 cpu를 아예 사용하지 못 하게 재워야 한다. sleep_list를 하나 만들어서 waiting 상태의 스레드를 재워두고 timer interrupt가 발생할 때마다 sleep_list에서 ticks 만큼의 시간 동안 잠들었던 스레드를 깨워보자.

 

📌 구현 방법과 헷갈렸던 부분들

• 구현 요구사항을 파악하기 위해 timer_sleep()이 돌아가는 과정을 파악하는 것도 어려웠다.
  • while문이 어떤 일을 하고 있는지 파악하기 어려웠음. 설명은 ‘구현 요구사항’ 참고
  • timer_sleep() 안에 wake까지 구현해야 한다고 생각하고
  • wake 조건을 이렇게 두 가지로 생각했었다.
    • wake 조건 1 : TIME_SLICE에 도달한 스레드
    • wake 조건 2 : sleep_list에 저장된 스레드 중 남은 실행 시간이 가장 긴 스레드
  • 당연히 아니었고! end_time 즉 스레드가 끝나는 시간이 되었는지만 확인하도록 해야 했다.
  • 내가 생각해낸 이유는 다음과 같다.
    • 깨우는 건 time_slice랑 상관 없다. time_slice만큼 지나면 발생되는 것은 wake가 아니라 yield(즉 문맥 교환)이다. (참고로 time_slice에 도달했는지 확인하고 yield하는 작업은 thread_tick()에서 한다.)
    • sleep_list에 저장된 스레드 중 남은 시간이 가장 긴 스레드를 깨우는 게 아니라 정해진 tick시간 동안 sleep한 스레드를 깨워야 한다.

• timer_sleep()함수의 역할을 분명히 파악하는 과정
  • 인자로 넘겨준 ticks 만큼의 시간이 되지 않았으면 스레드를 재웠다가(blocked 상태로 전환했다가), ticks 만큼의 시간이 지나면 다시 깨우기까지 하는 함수라고 생각했는데 깨우는 건 timer_sleep()에서 하지 않는다. timer_interrupt()에서 한다. 왜냐하면 timer_interrupt라는 것은 시스템 전체에서 tick이 한 번 지날 때마다 호출되는 인터럽트 핸들러인데 그 때마다 잠들었던 스레드들 중 ticks만큼 다 기다렸는지 확인하고 다 기다린 스레드들을 모두 깨워줘야 하기 때문이다. timer_sleep()은 그냥 호출되면 무조건 현재 스레드를 재우는 함수이다.
• struct thread의 변수 end에 어떤 값이 들어가야 할 지 정하는 과정
  • 현재 스레드에 ticks 시간 동안 자야 한다는 정보가 저장되어야 하므로 struct thread 구조체에 end라는 변수를 하나 추가했다. end에는 해당 스레드가 깨어야 할 시간이 저장되어있다. 즉 end값은 ‘timer_sleep()함수가 호출된 시점의 시스템 시간 (start) + 해당 스레드가 잠든 채로 유지되어야 하는 시간 (ticks)’ 으로 정의된다. end값을 이렇게 정의함으로써 timer_iterrupt()가 현재 시스템 tick과 end를 비교하여 나중에 timer_interrupt()에서 스레드를 언제 깨워야 하는지 쉽게 판단 가능하다. curr→end = end로 구조체 값을 할당해줬다.
• 임계 영역으로 지정해줘야 하는 부분을 파악하는 과정
  • list_insert_ordered()와 thread_block()을 함께 임계 영역으로 감쌌다.
    1. 공유 자원인 자료구조를 읽고 쓸 때 임계영역으로 감싸야 함 → list_insert_ordered()는 공유 자원인 sleep_list에 스레드를 하나 추가할 때 race condition이 발생되지 않게 하기 위해 임계 영역 설정이 필요하다.
    2. 여러 처리 과정이 atomic해야 할 때 그 처리 과정들을 모두 임계영역으로 감싸야 함 → sleep_list에 스레드를 하나 추가한 뒤 해당 스레드의 상태를 blocked로 바꾸는 과정은 atomic해야 한다. sleep_list에 들어간 스레드의 상태가 blocked로 바뀌지도 않았는데 그 사이에 timer_interrupt가 발생하면, sleep_list에 들어갔지만 blocked 상태의 스레드가 아닌 상태가 되므로 list_insert_ordered()함수와 thread_blocked()함수를 같이 임계영역 안에 포함시켜주었다.

❌ 잘못된 코드 1

timer_sleep()은 무조건 현재 스레드를 재우는 함수이므로 조건문이 필요 없다. 그리고 sleep_list에 스레드를 넣을 때 마다 스레드가 끝나는 시간이 짧은 순서 대로 정렬하는 list_insert_ordered()함수를 사용하면 나중에 다시 깨울 때 앞에서부터 하나씩 peek하면서 조건을 만족하면 pop할 수 있다.

/* 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 ();
	
	//현재 스레드 저장
	struct thread *curr = thread_current ();
	
	if(timer_elapsed(start) == ticks){
		//sleep list에 스레드 넣기
		list_push_back (&sleep_list, &curr->elem);
		//현재 실행 중인 스레드를 sleep상태(blocked 상태)로 바꿔주기
		thread_block();
	}
}

❌ 잘못된 코드 2

thread_wake()에 인자를 전달할 때 더블포인터 문제

thread_wake()는 내가 구현한 함수인데 인자로 포인터를 받았으므로 list_front(), list_pop_front(), list_empty()에 list를 넘겨줄 때는 앰퍼샌드를 안 붙여줘도 된다. 이 문제 때문에 무한 루프가 돌아 timeout이 발생했었다.

 

 

새벽 네 시에 이 문제로 다 같이 디버깅해준 분들에게 무한 감사를...🔥

/* tick이 한 번 지나서 타이머 인터럽트가 호출될 때마다 
	sleep(blocked)상태인 스레드 중 어떤 스레드를 깨워야 할지 
	조건문을 확인해 골라서 깨우기 */
static void
thread_wake(struct list *list){ 			//인자로 sleep_list 받기
	
	struct list_elem *e;
	// for (e = list_begin (list); e != list_tail (list); e = list_next (e)){
	// while (e != list_tail(list))
	while(!list_empty(list)){
		e = list_front(list);

		struct thread *t_now = list_entry(e, struct thread, elem);
		int64_t end_time = t_now->end;

		if(end_time > ticks) 				//wake 조건 : 스레드가 끝나는 시간이 현재 시간보다 크거나 같을 때 
			break;
		
		// list_remove(e); 				//해당 스레드를 그 스레드가 포함된 리스트에서 제거
		list_pop_front(list);
		thread_unblock(t_now); 			//스레드를 ready_list에 넣기

		// e = list_next(e);
	}
}

⭕️ 정답 코드

위에서 설명했던 것과 같이 구현하였고 스레드가 깨야 하는 시스템 시간인 end값을 비교해서 남은 sleep 시간이 가장 적은 순서대로 sleep_list가 구성되도록 list_less_endtime()이라는 함수를 추가로 구현했다. 이 함수는 list_insert_ordered()의 세 번째 인자로 들어가는 함수인데, pintos-kaist/include/lib/kernel/list.h 에 typedef로 ‘함수 형태’만 정의되어있는 함수이다. 실제로 들어가보면 아래처럼 정의되어 있는데, list_elem타입의 인자 두 개와 void 포인터를 하나 받고 bool 타입을 반환하는 함수를 직접 구현하여 list_insert_ordered()의 인자로 주면 된다. 나는 list_less_endtime()이라는 이름으로 함수를 생성해서 인자로 전달해주었다.

typedef bool list_less_func (const struct list_elem *a,
                             const struct list_elem *b,
                             void *aux);

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	enum intr_level old_level;
	int64_t start = timer_ticks ();												//timer_sleep()이 호출된 시점의 시간
	int64_t end = start + ticks;												//스레드의 sleep이 끝나는 시간

	ASSERT (intr_get_level () == INTR_ON);										//인터럽트가 발생하면 그 다음 코드를 실행함

	struct thread *curr = thread_current ();									//현재 스레드 저장
	curr->end = end;															//현재 스레드의 end값 초기화

	old_level = intr_disable();													//인터럽트를 disable시킴 (임계영역 보호)
	list_insert_ordered (&sleep_list, &curr->elem, list_less_endtime, NULL);	//sleep list에 스레드 넣기
	thread_block();																//현재 실행 중인 스레드를 sleep상태(blocked 상태)로 바꿔주기 
	intr_set_level(old_level);													//임계 영역 해제
}

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

/* 인자로 들어온 a, b 스레드 중 끝나는 시간(end)이 a가 더 크면 true, b가 더 크면 false를 리턴 */
bool
list_less_endtime(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);
	
	//a<b이면 true, a>=b이면 false 리턴
	return t_a->end < t_b->end;
}

 

🥹 오답 노트 🥹

• 타이머 인터럽트가 발생하면 context switch가 발생하는 줄 알고 sleep 중인 스레드를 깨우는 게 아니라 ready queue에서 우선 순위가 가장 높은 스레드로 전환해야 하는 것 아닌가 생각했는데 타이머 인터럽트 개념에 대해 잘못 알고 있었다. 타이머 인터럽트는 시스템 tick이 하나 증가될 때마다 호출되는 인터럽트 핸들러이며 시스템 tick 시간을 하나씩 증가시킨다. sleep-wait를 구현할 때 sleep_list에 자고 있는 스레드들의 endtime과 현재 시스템 시간을 비교하여 깨울 스레드를 모두 깨운다. sleep_list는 이미 endtime 기준 오름차순으로 정렬된 채 삽입되기 때문에 깨울 스레드를 앞에서부터 꺼내서 깨울 시간이 되었는지 검사한다.

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

 

• sleep_list를 선언만 하고 초기화하지 않아서 컴파일 에러가 발생했었다. timer_init()에 list_init(&sleep_list)로 리스트를 초기화해야 한다.

void
timer_init (void) {
	/* 8254 input frequency divided by TIMER_FREQ, rounded to
	   nearest. */
	uint16_t count = (1193180 + TIMER_FREQ / 2) / TIMER_FREQ;

	outb (0x43, 0x34);    /* CW: counter 0, LSB then MSB, mode 2, binary. */
	outb (0x40, count & 0xff);
	outb (0x40, count >> 8);

	intr_register_ext (0x20, timer_interrupt, "8254 Timer");
	list_init(&sleep_list);
}

• thread_wake에서 end_time < ticks인데 end_time ≥ ticks로 구현해서 컴파일 에러가 발생했다.

/* tick이 한 번 지나서 타이머 인터럽트가 호출될 때마다 sleep(blocked)상태인 스레드 중 
어떤 스레드를 깨워야 할지 조건문을 확인해 골라서 깨우기 */
static void
thread_wake(struct list *list){ 			//인자로 sleep_list 받기
	
	struct list_elem *e;

	while(!list_empty(list)) { 
		e = list_front(list);

		struct thread *t_now = list_entry(e, struct thread, elem);
		int64_t end_time = t_now->end;

		if(end_time > ticks) 				//wake 조건 : 스레드가 끝나는 시간이 현재 시간보다 크거나 같을 때 
			break;
		
		list_pop_front(list);				//해당 스레드를 그 스레드가 포함된 리스트에서 제거
		thread_unblock(t_now); 				//스레드를 ready_list에 넣기
	}
}

• 그리고 또 자주 발생했었던 컴파일 에러는 새로운 함수를 만들었지만 프로토타입을 맨 위쪽에 선언해주지 않아서 다른 함수에서 호출 시 인식할 수 없었던 문제, .c 파일에 구현한 함수를 .h 파일에 선언해주지 않아서 다른 파일에서 인식할 수 없었던 문제 정도였던 것 같다.

 

🤯 테스트 에러 🤯

 

alarm-simultaneous 테스트가 fail이 떴다.

 

먼저 alarm-simultaneous 테스트 코드가 뭘 테스트 하는지 파악해야 했다.

/* Creates N threads, each of which sleeps a different, fixed
   duration, M times.  Records the wake-up order and verifies
   that it is valid. */

#include <stdio.h>
#include "tests/threads/tests.h"
#include "threads/init.h"
#include "threads/malloc.h"
#include "threads/synch.h"
#include "threads/thread.h"
#include "devices/timer.h"

static void test_sleep (int thread_cnt, int iterations);

void
test_alarm_simultaneous (void) 
{
  test_sleep (3, 5);
}

/* Information about the test. */
struct sleep_test 
  {
    int64_t start;              /* Current time at start of test. */
    int iterations;             /* Number of iterations per thread. */
    int *output_pos;            /* Current position in output buffer. */
  };

static void sleeper (void *);

/* Runs THREAD_CNT threads thread sleep ITERATIONS times each. */
static void
test_sleep (int thread_cnt, int iterations) 
{
  struct sleep_test test;
  int *output;
  int i;

  /* This test does not work with the MLFQS. */
  ASSERT (!thread_mlfqs);

  msg ("Creating %d threads to sleep %d times each.", thread_cnt, iterations);
  msg ("Each thread sleeps 10 ticks each time.");
  msg ("Within an iteration, all threads should wake up on the same tick.");

  /* Allocate memory. */
  output = malloc (sizeof *output * iterations * thread_cnt * 2);
  if (output == NULL)
    PANIC ("couldn't allocate memory for test");

  /* Initialize test. */
  test.start = timer_ticks () + 100;
  test.iterations = iterations;
  test.output_pos = output;

  /* Start threads. */
  ASSERT (output != NULL);
  for (i = 0; i < thread_cnt; i++)
    {
      char name[16];
      snprintf (name, sizeof name, "thread %d", i);
      thread_create (name, PRI_DEFAULT, sleeper, &test);
    }
  
  /* Wait long enough for all the threads to finish. */
  timer_sleep (100 + iterations * 10 + 100);

  /* Print completion order. */
  msg ("iteration 0, thread 0: woke up after %d ticks", output[0]);
  for (i = 1; i < test.output_pos - output; i++) 
    msg ("iteration %d, thread %d: woke up %d ticks later",
         i / thread_cnt, i % thread_cnt, output[i] - output[i - 1]);
  
  free (output);
}

/* Sleeper thread. */
static void
sleeper (void *test_) 
{
  struct sleep_test *test = test_;
  int i;

  /* Make sure we're at the beginning of a timer tick. */
  timer_sleep (1);

  for (i = 1; i <= test->iterations; i++) 
    {
      int64_t sleep_until = test->start + i * 10;
      timer_sleep (sleep_until - timer_ticks ());
      *test->output_pos++ = timer_ticks () - test->start;
      thread_yield ();
    }
}

timer_sleep()함수가 동시에 sleep한 여러 스레드를 정확히 같은 tick에 깨우는지 5번 반복 확인하는 테스트 코드이다.

세 개의 스레드(thread 0, 1, 2)가 동시에 timer_sleep(10)을 호출했으므로 다음과 같은 결과가 5번 연속으로 출력되어야 한다.

iteration 0, thread 0: woke up after 10 ticks
iteration 0, thread 1: woke up 0 ticks later
iteration 0, thread 2: woke up 0 ticks later

 

thread 0이 제일 먼저 측정되었고 thread 1, 2는 직후 정확히 깨어났기 때문에 0 tick later로 출력되었으므로 세 스레드가 동시에 깨어난 것을 의미한다. 

iteration 0, thread 0: woke up after 10 ticks
iteration 0, thread 1: woke up 1 ticks later
iteration 0, thread 2: woke up 1 ticks later

만약 스레드 1, 2가 원래 일어나야 할 시점보다 1 tick 늦게 깨어난다면 위와 같이 출력될 것이다.