[pintos] Project 1_alarm

[pintos] Project 1_alarm

 

pintos는 기본 기능들만 구현된 작은 운영체제이다. 마치 tiny web server처럼

 

 

이 운영체제에는 실행중인 스레드를 잠시 재우고 다른 스레드에서 진행하는 하는 기능이 있는데, 처음에는 busy waiting 방식으로 구현되어 있다. 이를 Sleep / Awake로 구현하는 것이 첫 번째 과제이다.

 

Busy waiting 구현

 

busy waiting은 매 시간 자고 있는 스레드를 깨워 시간을 확인한 후 아직 깨울 시간이 안됐으면 다시 재운다. 이를 계속 반복하다 꺠어날 시간이 되었을 때 깨우는 방식이다. 이는 매우 비효율적인 방식으로 많은 CPU 시간을 낭비한다. 

 

busy waiting은 아래와 같이 구현되어 있다. thread_yield 함수로 schedule 함수가 실행되어 scheduling이 된다.

running 에서 sleep 명령을 받은 스레드는 ready state가 되어 ready_list에 추가되고 이 ready_list에 있는 스레드들은 자신의 차례가 되면 일어날 시간이 되었는지에 상관없이 깨워져 running state가 된다. 이렇게 running state가 된 스레드는 자신이 일어날 시간이 되었는지 확인 후 아직 안되었으면 다시 ready state로 전환된다.

이 부분은 while 문에 구현되어 있으며 thread_yield 함수는 schedule 함수를 실행하고 이를 통해 scheduling (running <-> ready) 이 된다.

* devices/timer.c */
void timer_sleep (int64_t ticks) {
  int64_t start = timer_ticks ();
  while (timer_elapsed (start) < ticks) 
    thread_yield ();
}

 

Sleep / Awake 구현

 

비효율을 개선하기 위해서는 잠든 스레드를 ready state가 아닌 block state로 만들어 깨어날 시간 이전에는 건드리지 않다가(스케쥴링에 포함 x) 그 시간 이후 ready state로 바꿔 주면 된다. 이는 thread_sleep이라는 함수로 구현할 수 있다.

먼저 스레드가 깨어날 시간에 대한 변수를 thread 구조체에 추가한다.

 

/* thread/thread.h */
struct thread{
...
/* 깨어나야 할 tick을 저장할 변수 추가 */
int64_t wakeup_tick;
...
}

 

그 이후 잠자는 스레드들의 리스트가 필요하다. 그리고 깨울 스레드를 찾기 위해 매번 접근하기 번거로우니 가장 먼저 일어날 스레드를 변수 next_tick_to_awake 를 추가한다. 그리고 sleep_list에서 사용할 수 있도록 thread_init함수에서 sleep_list 초기화 작업은 진행한다.

물론 상단에 변수 선언도 해야한다.

 

/* thread/thread.c */

static struct list sleep_list;
static int64_t next_tick_to_awake;

...

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

출처: https://bowbowbow.tistory.com/20 [멍멍멍]

 

이제 next_tick_to_awake 변수를 업데이트 하여 번거롭게 누굴 깨울지 매번 확인하지 않게 만든다

 

/* ----- project1: alarm clock ----- */
void
update_next_tick_to_awake(int64_t ticks){
	// find smallest tick
	next_tick_to_awake = (next_tick_to_awake > ticks) ? ticks : next_tick_to_awake; 
}

int64_t
get_next_tick_to_awake(void){
	return next_tick_to_awake;
}
/* ----- project1: alarm clock end -----*/

 

이제 thread_sleep을 통해 스레드를 재워야한다. 재울 스레드를 sleep_list에 추가하고 block 상태로 만든다. 그런데 이 과정에서 인터럽트의 방해를 받으면 안된다. 

 

/* ----- project1: alarm clock ----- */
void
thread_sleep (int64_t ticks) { // from timer_sleep (start + ticks)
	struct thread *cur;
	cur = thread_current();

	// idle -> stop: idle_thread cannot sleep
	if (cur == idle_thread) {
		ASSERT(0);
	}
	else {
		enum intr_level old_level;
		old_level = intr_disable(); // interrupt off
		
		update_next_tick_to_awake(cur->wakeup_tick = ticks); // 일어날 시간 저장
		list_push_back(&sleep_list, &cur->elem); 			  // sleep_list에 추가
		thread_block();										  // block 상태로 변경
		
		intr_set_level(old_level);  // interrupt on
	}
}

 

이제 깨우는 함수 thread_awake 가 필요하다. sleep_list를 순회하며 현재 th->tick이 깨워야 할 tick보다 작다면 sleep_list에서 제거하고 unblock을 해준다. 만약 깨워야 할 tick보다 크다면 update_next_tick_to_awake를 호출하여 tick을 업데이트 해준다.

 

/* ----- project1: alarm clock ----- */
// from timer_interrupt. 즉 매 초마다 awake 할 게 있는지 확인후 있으면 이 함수 실행
void
thread_awake (int64_t wakeup_tick){
	next_tick_to_awake = INT64_MAX;

	// take a sleeping thread
	struct list_elem *sleeping;
	sleeping = list_begin(&sleep_list);

	// sleep_list 순회 -> 깨워야 할 스레드를 sleep_list에서 제거하고 unblock
	while (sleeping != list_end(&sleep_list)){
		struct thread *th = list_entry(sleeping, struct thread, elem);

		// 일어날 시간이 된 스레드
		if (wakeup_tick >= th->wakeup_tick) {	// 스레드가 일어날 시간이 되었는지 확인
			sleeping = list_remove(&th->elem); // sleep_list에서 제거 후 next를 가리킴
			thread_unblock(th);	// unblock thread -> ready_list에 넣는다
		}
		// 일어날 시간이 안된 스레드
		else {
			sleeping = list_next(sleeping); 	// move to next sleeping thread
			// 순회하면서 가장 작은 wakeup_tick으로 갱신한다
			// 바로 다음에 깨울 스레드 시간
			update_next_tick_to_awake(th->wakeup_tick);
		}
	}
}

 

thread.h에 프로토타입을 선언한다.

 

/* thread/thread.h */

//스레드를 ticks시각까지 재우는 함수.
void thread_sleep(int64_t ticks);
//푹 자고 있는 스레드 중에 깨어날 시각이 ticks시각이 지난 애들을 모조리 깨우는 함수
void thread_awake(int64_t ticks);

// 가장 먼저 일어나야할 스레드가 일어날 시각을 반환함
int64_t get_next_tick_to_awake(void);
// 가장 먼저 일어날 스레드가 일어날 시각을 업데이트함
void update_next_tick_to_awake(int64_t ticks);

 

이제 스레드를 실제로 잠재우는 함수인 timer_sleep가 불렸을 때 반복문을 돌면서 기다는 부분을 지우고 방금 만들어준 thread_sleep함수를 호출하도록 변경합니다.

 

void
timer_sleep (int64_t ticks) {

	int64_t start = timer_ticks (); // os 부팅 후 ticks
	ASSERT (intr_get_level () == INTR_ON);

	/* ----- project1: alarm clock ------ */
	thread_sleep(start + ticks);	// 현재 진행중인 스레드를 재운다(일어날 시간: start + ticks로 지정)
}

 

timer 하드웨어 의해 매 틱마다 타이머 인터럽트가 걸리는데 그 때 timer_interrupt 함수가 호출된다.

 

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	/* 1 tick마다 timer_interrupt 수행됨 --> 
	 * timer_interrupt에 awake함수 포함시키면 깨워야 할 스레드 찾고 깨울 수 있음 */

	ticks++;		// Number of timer ticks since OS booted. 매 tick 마다 호출되므로
	thread_tick ();	// 스레드 tick 통계 + 스레드 양보 시간 확인(4 tick마다 교체)

	/* ----- project1: alarm clock ----- */
	// 매 tick마다 sleep_list를 체크하며 깨어날 thread가 있는지 확인
	// 다음으로 깨어나야 할 thread의 tick과 현재의 ticks값을 비교
	if (get_next_tick_to_awake() <= ticks){ 
		thread_awake(ticks);
	}
}

 

결과

make로 컴파일 후 pintos -- -q run alarm-multiple을 실행하면 다음과 같이 나온다.

 

 

참조

https://bowbowbow.tistory.com/20

https://poalim.tistory.com/28?category=758538