[정글] PintOS Project1 #1 Alarm Clock

PintOS 는 스탠포드에서 만들어진 교육용 mini OS 이다 

우리는 카이스트 전산학과 운영체제 수업의 카이스트 PintOS Project 를 진행한다 

Kaist PintOS Project GitHub 

GitHub - casys-kaist/pintos-kaist

1) 키워드 정리 

구현을 시작하기 전에 먼저 키워드를 정리하면서 OS 에 대한 감을 잡았다 

[정글] Week08 키워드 정리 하지만 아직도 내가 뭘 구현해야할지는 모르겠다 

[정글] Week08 키워드 정리

2) 참고 자료

1. Kaist GitBook 정글6기 분들이 번역해 놓은 자료를 참고하며 GitBook 을 먼저 읽었다 

Introduction · GitBook

2. Kaist PintOS Slides 컬러로 프린트했더니 8만6천원 나옴^_^,......ㅎ 고이고이 보관해서 대대손손 물려줘야지 

Pintos Slides - KAIST OS Lab

Slide Set 의 강의는 영어로 되어 있긴 하지만, 귀중한 PPT 프린트물^_^와 함께 차근차근 몇 번씩 다시 봤다 

Project 1 에서 구현해야 할 것 

1. Alarm Clock

2. Priority Scheduling 

3. Advanced Scheduler 

1. Alarm Clock

운영체제에서 실행 중인 스레드를 재웠다가, 일정 시간이 지나면 다시 깨우는 기능을 Alarm Clock 이라고 한다 

현재 PintOS 의 Alarm Clock (timer_sleep) 는 Busy Waiting 으로 구현되어 있다, 이 방법은 while 문으로 무한 반복하면서

비효율적으로 많은 CPU 시간을 낭비하고 있다, 이것을 Sleep/ Wakeup 방법으로 개선하는 것이 우리의 첫번째 과제이다 

 

Alarm Clock 현재 방식 

1) timer_sleep (현재 방식 Busy Waiting) 

// path - devices/timer.c
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks (); // 현재 시간을 받아온다 
    
    // 인터럽트 수준이 INTR_ON 인지 확인 
	ASSERT (intr_get_level () == INTR_ON);
    // 경과 시간이 ticks 보다 작으면
	while (timer_elapsed (start) < ticks)
		thread_yield (); // Thread 양보
}

2) thread_yield 

// path - threads/thread.c
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level; /* 인터럽트 비활성화 */

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
	do_schedule (THREAD_READY); /* 컨텍스트 스위칭 */
	intr_set_level (old_level); /* 인터럽트 원상복구 */
}

 

Alarm Clock 개선 방향 

Blocked List (sleep_list) 를 추가해서 일어나지 않아도 되는 시간에 Running State 가 되지 않고

timer_sleep() 호출 시에 Blocked 상태가 되고, OS 가 wakeup 해주는 방식으로 개선해야 한다 

timer_sleep(ticks) - sleep_list 에 쓰레드 삽입 

wakeup() - sleep_list 에서 ready_list 로 쓰레드 이동 

 

기존에 구현된 Thread Sleep/ Wakeup 을 활용할 예정

void // thread 를 Block 하는 함수 
thread_block (void) {
	ASSERT (!intr_context ());
	ASSERT (intr_get_level () == INTR_OFF);
	thread_current ()->status = THREAD_BLOCKED;
	schedule ();
}

void // Thread 를 깨우는 함수 Wakeup
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);
}

 

 

Alarm Clock 개선 구현하기 

1) Thread 구조체에 tick 추가 thread.h

thread 구조체에, 일어날 시간 정보 wakeup_tick 을 추가한다 

struct thread {
	...
	int64_t wakeup_tick; /* Wakeup 시점을 가지기 위한 ticket 추가 */
    ...
}

2) sleep_list 생성 및 초기화 thread.c

Sleep 상태 (BLOCKED) 쓰레드를 관리할 sleep_list 를 생성하고 초기화한다 

ready_list 사용 방법을 참고하여 sleep_list 도 동일하게 구현하였다 

static struct list sleep_list; /* sleep_list 생성 */

void
thread_init (void) {
	...
	list_init (&sleep_list); /* sleep_list 초기화 */
    ...
}

3) thread_sleep() 함수 생성 thread.c 

일어날 시간을 저장한 다음에 재워야 할 Thread 를 sleep_list 에 추가하고 Thread 상태를 Block State 로 만들어준다 

/* Thread Sleep, Ready List -> Sleep List 로 이동하여 대기 상태로 만든다 */
void thread_sleep(int64_t tick) { 
	enum intr_level intr_lv = intr_disable(); /* 인터럽트 비활성화 */
	struct thread* current_thread = thread_current(); /* 현재 실행 중인 thread 를 가져온다 */

	current_thread->wakeup_tick = tick; /* 현재 thread 가 깨어날 시간을 tick 으로 설정 */
	
	/* Sleep List 에 현재 thread 삽입 + compare_sleep_list 를 이용하여 순서 정렬 */
	list_insert_ordered(&sleep_list, &current_thread->elem, compare_sleep_list, NULL);
	thread_block(); /* 현재 thread 를 차단 상태로 변경해서 Ready List 에서 제거 */

	intr_set_level(intr_lv); /* 인터럽트 원상복구 */
}

4) 기존 Busy-Waiting 방식을 Sleep/ Wakeup 방식으로 변경 timer.c 

 timer.c 의 timer_sleep() 함수에서 새로 만든 thread_sleep() 함수를 적용해준다 

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks (); // 현재 시간을 받아온다 

	// 인터럽트 수준이 INTR_ON 인지 확인 
	ASSERT (intr_get_level () == INTR_ON);
	// while (timer_elapsed (start) < ticks)
	// 	thread_yield (); 

	// start 이후 얼마나 시간이 지났는지 측정 
	// 경과 시간이 tickets 보다 작으면 start+ticks 만큼 잠들게 한다 
	if (timer_elapsed (start) < ticks)
		thread_sleep(start + ticks); 
}

5) thread_wakeup() 함수 생성 thread.c

자고 있는 Thread 들이 일어날 시간이 되었을 때 깨워주는 thread_wakeup() 을 추가한다

sleep_list 를 돌면서 일어날 시간이 지난 Thread 들을 찾아 Ready List 로 옮겨주고, Thread 상태도 Ready State 로 변경해준다 

/* Thread Wakeup */
void thread_wakeup(int64_t tick) {
	enum intr_level intr_lv = intr_disable(); /* 인터럽트 비활성화 */

	struct list_elem *iter;
	struct thread* current_thread;

	for(iter = list_begin(&sleep_list); iter != list_end(&sleep_list);){
		current_thread = list_entry(iter, struct thread, elem);

		if(current_thread->wakeup_tick <= tick){ /* Thread 가 일어날 시간인지 확인 */
			iter = list_remove(&current_thread->elem); /* Sleep List 에서 제거. */
			thread_unblock(current_thread); /* Thread 를 Ready 상태로 전환 */
		}
		else
			break;
	}
	intr_set_level(intr_lv); /* 인터럽트 원상복구 */
}

+ thread.h 에 함수 원형 추가 

void thread_sleep(int64_t);
void thread_wakeup(int64_t);
bool compare_sleep_list(const struct list_elem*, const struct list_elem*);

6) timer_interrupt() 에 wakeup 작업 추가 timer.c

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick (); // update the cpu usage for running process

	/* code to add: 
	check sleep list and the global tick.
	find any threads to wake up,
	move them to the ready list if necessary.
	update the global tick.
	*/
	thread_wakeup(ticks); /* ticks 가 증가할 때마다 wakeup */
}

7) compare_sleep_list() 함수 추가 

/* wakeup_time을 기준으로 리스트를 정렬하기 위한 비교 함수 */
bool compare_sleep_list(const struct list_elem *a, const struct list_elem *b)
{
	/* list_entry 매크로를 사용하여 b는 단수만 비교, a는 모든 것을 순회 비교 */
	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;
}

+ 환경 변수 추가

코드를 시험해 보려고, source ./activate 도 해주고 make 도 해줬는데 pintos 를 찾을 수 없다고 했다 

helloahram@9aca6e15b4da:~/krafton-jungle-Pintos-Threads/threads$ pintos -- -q run alarm-multiple
bash: pintos: command not found

방법을 찾아보다가 룸메 ㅅㅎ님의 도움을 받아 ~/.zshrc 맨 아래 줄에 pintos 경로를 추가해줬다 

export PATH=$PATH:/home/helloahram/krafton-jungle-Pintos-Threads/utils/pintos

pintos 파일에 실행 권한도 추가해줬다

chmod +x /home/helloahram/krafton-jungle-Pintos-Threads/utils/pintos

그리고 ~./zshrc 파일 다시 로드하고 실행해 봤는데

source ~/.zshrc

하지만 코드에 문제가 있는지 실행되지 않았다고 한다

helloahram@9aca6e15b4da:~/krafton-jungle-Pintos-Threads/threads$ pintos -- -q run alarm-multiple
qemu-system-x86_64: warning: TCG doesn't support requested feature: CPUID.01H:ECX.vmx [bit 5]

뭐가 문제일까, 벌써 목요일인데 Alarm Clock 도 아직 못 해서 큰일이다 😢

---

여기 참고한 블로그에서 /thread 에서 make 컴파일하고 명령어 실행했다고 해서 그렇게 한 거였는데

ㅈㅎ이가 봐주더니 thread/build 폴더까지 들어가서 해야된다고 했다 

그랬더니,.... 두구두구두구

됐다!!!!!! 야호~~~~~~~!

 

idle Thread 는 다른 어떤 Thread 도 실행되지 않는 상태일 때 실행되는 Thread 로,

Thread: 550 idle ticks 는 idle Thread 가 550 ticks 동안 실행되었다는 의미이고

550 ticks 동안의 쉬는 시간이 발생했다는 뜻이다 

 

기존 Busy-Waiting 방식에서는 Ready List 는 비어 있는 순간이 없기 때문에 

idle Thread 가 실행될 일이 없어서 0 idle Thread 가 출력되었다

반면에, Sleep/ Wakeup 방식은 필요할 때만 깨워 Thread 가 실행되기 때문에

Busy-Waiting 방식에 비해 시스템 자원의 낭비가 줄어든다고 볼 수 있다 

 

계속 돌려본 카이스트 교수님의 강의 https://www.youtube.com/watch?v=myO2bs5LMak