🖐️Alarm Clock ( Busy-Waiting을 Sleep/Wakeup으로 바꿔보자 )

지금 PintOS에서 구현된 Alarm Clcok을 Busy-Waiting에서 Sleep/Wakeup으로 변경하라.

 

아무 생각이 없다가 이번 주차를 맞이하고서 크래프톤 정글의 마지막이 가까워지는 게 느껴진다. 드디어 대망의 PintOS가 시작됐다. 모든 자료들이 영문으로 되어있어서 접근이 어려운 부분이 있지만, 제공되는 Gitbook을 본다면 어렵지 않게 해야 할 일들을 생각할 수 있다.

 

이번 게시글만 과제에 접근한 순서대로 작성해보려고 한다.

 

☑️ STEP 0. 키워드 정리

아직 블로그에 올리지는 않았지만, 해당 주차를 시작하고 과제의 갈피를 잡지 못해서 우선적으로 키워드를 정리하는 시간을 가졌다. 정글에서 제공하는 키워드는 항상 주차의 과제와 연관성이 있었고 키워드를 미리 학습해야 과제를 하면서 다시 복습할 수 있기 때문이다.

 

☑️ STEP 1. 찾은 자료 읽기

키워드에 대해서 정리하고 정글에서 제공해준 자료와 앞 기수분에게 받은 자료 읽었다. 

 

 

▶️ PintOS GitBook - 공식(영문)

 

Introduction · GitBook

No results matching ""

casys-kaist.github.io

 

▶️ PintOS GitBook 한글 번역 - 비공식

 

KAIST PINTOS 과제 설명서 | Notion

프로젝트가 진행되면서 점점 과제설명서 스압이 심해져서 페이지로 분리했습니다! 만약 바꾸기 전 상태가 더 편하다면 댓글로 알려주세요!

yjohdev.notion.site

 

노션의 내용을 우선 읽는 것 보다는 GitBook을 참고하면서 AI의 도움을 받았다. 그럼에도 불구하고 읽히지 않았던 내용은 노션에서 참고해서 개념을 잡고 다시 GitBook을 읽으면서 이해한 것이 올바른지 참고했다.

 

▶️ KAIST Pintos Youtube 강의

 

EE415: Introduction to Operating Systems (KAIST)

 

www.youtube.com

 

▶️ KAIST Pintos Slides

 

Pintos Slides - KAIST OS Lab

[vc_column width="1/1"]

oslab.kaist.ac.kr

 

마지막으로 KAIST에서 제공하고 있는 PintOS 강의 자료가 있어서 참고했다. 유튜브 강의는 영어로 진행돼서 정말 조금만 해석할 수 있었다. 그래서 추가로 제공하는 PPT 자료를 집중적으로 참고했다. 영어는 어려워

 

☑️ STEP 2. 내용을 정리하자.

다음은 과제를 풀때, 필요한 내용들을 정리했다.

 

⭐ Alarm Clock?  

과제의 목표는 Alarm Clock을 구현하는 것이 아니라, 개선하는 것!

 

과제의 목표는 구현이 아니라 개선이다. 그러면 당연하게도 개선할 수 있는 방법을 찾아야 한다. 그리고 더욱이 당연하게 Alarm Clock에 대해서 알아야 한다.

 

Alarm Clock은 시간을 정해두고 해당 시간마다 이벤트를 발생시킨다. 그러면 이벤트를 통해서 특정한 무언가를 실행할 수 있도록 한다. 우리가 실생활에서 사용하는 알람과 동일하다.

 

⭐ Busy Waiting?  

Alarm Clock을 구현하기 위해서 다양한 기법을 사용할 수 있고 Busy Waiting도 그중 하나다. 지금 PintOS에서 구현된 알고리즘은 다음과 같다.

/* 
    Path // devices/timer.c 
*/
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

위 함수의 알고리즘은 다음과 같이 동작한다.

  • 현재 Timer의 Tick을 가져오고 start에 대입한다.
  • 현재 Timer의 Tick - start 값과 인자로 받은 ticks의 값을 비교한다.
    • 함수가 실행되고 있는 중에도 현재 Tick 값은 증가하고 있다.
    • ticks의 값은 sleep하기 원하는 시간을 의미한다.
  • ticks의 값이 더 크다면, 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);
}

thread_yield 함수는 다음과 같이 동작한다.

  • 현재 thread를 얻어온다.
  • 인터럽트를 비활성화한다.
  • 현재 thread가 idle_thread인지 확인한다.
    • 아닐 경우, ready_list의 뒤에 넣어준다.
  • 다음 thread를 실행하는 do_schedule 함수를 실행한다.
  • 인터럽트를 활성화한다.

 

구현된 코드로 알 수 있는 내용은 Busy Waiting은 Thread가 쉬는 시간이라면, 다음 쓰레드에게 CPU 권한을 양도하고 다시 탐색 리스트(Ready_list)의 후위에 들어가 똑같이 반복된다는 것이다. 즉, 쉬고 있어야 할 Thread에 반복하여 접근해서 깨우고 계속 조건 만족 여부를 확인하는 것을 의미한다.

 

▶️ 왜 인터럽트를 비활성화 하는가?
: 인터럽트를 통해서 특정한 이벤트가 실행된다. 함수가 실행되는 시점에서 인터럽트가 발생한다면 예상하지 못한 이슈가 나타날 수 있기 때문에 인터럽트를 중단하고 모든 과정이 종료되었을 때, 인터럽트를 시작하는 것이 좋다.

 

⭐ Sleep/Wakeup ?  

계속 CPU를 낭비하는 Busy Waiitng을 Sleep/Wakeup 방식을 사용해서 개선할 수 있다. Sleep/Wakeup은 2가지로 나눠서 생각하자.

⭐ Sleep ?  

현재 Thread가 CPU 사용을 중단하고 BLOCKED 상태로 전환하는 것을 의미한다. BLOCKED 상태의 Thread는 스케쥴링 대상에서 제외된다. 그렇기 때문에 Busy-Waiting과 다르게 순회될 걱정이 없다.

 

⭐ Wakeup ?  

BLOCKED 상태(Sleep)의 Thread를 깨운다. 어떻게? Tick이 발생할 때, 지정된 조건을 확인해서 깨운다. 다시 깨운다는 것은 스케쥴링 대상에 다시 포함시키는 것을 의미한다.

 

⭐ 다시 정리하기   

 

  • ready_list는 스케쥴링에 포함되어 있는 Thread들이 존재하는 리스트를 의미한다.
  • sleep_list는 스케쥴링에 포함되면 안 되는 Thread들이 존재하는 리스트를 의미한다.

 

그러면 Sleep은 Ready_List에서 빼내고 Sleep_List로 옮겨주는 행위이며, Wakeup은 반대로 Sleep_List에서 빼내고 Ready_List로 옮겨주는 행위를 의미하는 게 아닐까?

 

☑️ STEP 3. 필요한 범위의 PintOS 코드 분석하기

thread.*
timer.c

 

위 항목과 같이 구현을 위해서 연관성 있는 파일들을 살펴봤다. 전체적으로 주석을 처리하면서 자세하게 접근하는 것보다는 다음과 같은 생각을 통해서 함수의 역할을 이해했다.

  • 매개변수는 어떤 역할을 하는가?
  • 함수는 반환 값으로 무엇을 주는가?
  • 매개변수와 반환 값이 없으면, 어떤 로직을 가지고 있는가?

함수의 로직을 아는 것도 중요하겠지만, 코드 양이 많아서 모든 코드를 깊숙하게 이해하는 것은 잠시 내려놨다. 구현이 끝나고도 시간은 있으니까.

 

/* 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. */
// 현재 Thread를 Block하는 함수구나
// 깨우는건 내가 구현해야하나???
void thread_block(void)
{
	ASSERT(!intr_context());
	ASSERT(intr_get_level() == INTR_OFF);
	thread_current()->status = THREAD_BLOCKED;
	schedule();
}

/* Transitions a blocked thread T to the ready-to-run state.
   This is an error if T is not blocked.  (Use thread_yield() to
   make the running thread ready.)

   This function does not preempt the running thread.  This can
   be important: if the caller had disabled interrupts itself,
   it may expect that it can atomically unblock a thread and
   update other data. */
// 변수 t를 깨우고 ready_list에 추가한다 -> 다시 깨우는거네
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);
}

위 두 개의 함수를 통해서 BLOCKED 상태와 READY 상태로 전환할 수 있음을 찾았다. 또, thread_unblock 함수에서 ready_list를 사용하는 방법을 보고 list를 어떻게 구현해야 하는지 알 수 있었다.

 

☑️ STEP 4. 알고리즘 구현

🔥주의사항🔥

AI에 질문하면 바로 구현 가능한 코드를 전달한다.
의사코드(혹은 코드 없이)를 통한 설명을 요청하자.
▶️ AI 활용 방법
: 나는 Claude AI를 사용한다. Sleep/Wakeup 방식에 대한 개념을 잡기 위해서 AI한테 물어보자마자.. 바로 구현 가능한 코드가 나타나는 참사를 겪었다. 그래서 나는 다음과 같이 AI를 활용했다.

* 프롬프트 : 내가 작성한 코드를 리뷰해 주고 설명할 때, 의사코드로 말해줘.
활용 방법 : [코드 구현] -> [AI한테 코드 리뷰]

 

⭐ Thread 구조체에 Tick 추가하기  

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

 

  • 쓰레드는 일어날 시간 정보를 가지고 있어야 한다.
  • 구조체에 wakeup_tick 변수를 추가한다.

 

⭐ Sleep_list 생성 및 초기화  

// Sleep_List 선언
static struct list sleep_list;


void thread_init(void)
{
	...

	// Sleep_List 초기화
	list_init(&sleep_list);
    
    ...
}

 

  • Sleep 상태(BLOCKED)의 쓰레드를 관리할 List를 선언한다.
  • List를 사용하는 방법은 기존의 Ready_List 사용 방법을 참고했다.

 

⭐ Timer_Sleep 함수 수정하기  

/* Suspends execution for approximately TICKS timer ticks. */
// ticks 만큼 타이머 실행을 중지한다.
void timer_sleep(int64_t ticks)
{
	// 현재 시간을 받아온다.
	int64_t start = timer_ticks();

	ASSERT(intr_get_level() == INTR_ON);

	// 현재 시간보다 ticks이 더 크다
	// 지정된 시간이 미래일 때.
	if(timer_elapsed(start < ticks))
		// 현재 시간에서 ticks까지 재워.
		thread_sleep(start + ticks);

	// // start 이후, 경과한 시간이 ticks보다 더 적다면
	// while (timer_elapsed(start) < ticks)
	// 	// 스레드는 현재 CPU를 양보한다.
	// 	thread_yield();
}
  • 기존 함수의 작동 방식은 Busy-Waiting을 위한 로직이 작성되어 있었다.
  • Sleep 상태의 쓰레드를 Sleep_List로 옮길 수 있도록 코드 로직을 수정했다.

 

⭐ Thread.h에 함수 추가  

struct thread {
    ...
    
    void thread_sleep(int64_t);
    void thread_wakeup(int64_t);
    bool compare_sleep_list(const struct list_elem*, const struct list_elem*);
    
    ...
}
  • Thread 구조체에 상태를 관리할 수 있는 함수를 추가한다.
  • 쓰레드를 재우기 위한 Sleep 함수와 쓰레드를 깨우기 위한 Wakeup 함수를 추가했다.
  • compare_sleep_list 함수는 아래에서 설명한다.

 

⭐ 추가한 함수 구현하기  

함수들을 구현하기 위해서 각 함수에 주석을 통해서 의사 코드를 작성해 생각을 정리하고 구현에 들어갔다.

 

void thread_sleep(int64_t tick)
{
	// [생각]
	// 인터럽트 Disable을 해준다.
	// 현재 Thread에 Tick Time만큼 지정해준다.
	// 지정한 친구는 Sleep List로 넣어준다.
	// 인터럽트를 재발생 시킨다.
	// AI 도움 -> Insert를 Insert_Ordered로 써보라.

	// [구현]
	enum intr_level intr_lv = intr_disable();
	struct thread* current_thread = thread_current();

	current_thread->wakeup_tick = tick;
	list_insert_ordered(&sleep_list, &current_thread->elem, compare_sleep_list, NULL);
	thread_block();

	intr_set_level(intr_lv);
}

 

  • thread_sleep 함수는 일정 시간 동안 쓰레드를 재운다.
    • 재우는 행위는 위에서 봤던 것과 같이 스케쥴링 대상에서 제외하는 것.
    • ready_list -> sleep_list로 옮기는 행위로 볼 수 있다.
  • list_insert_ordered 함수를 사용해서 정렬을 통해서 쓰레드를 sleep_list에 삽입했다.
    • 일어날 시간이 가까운 쓰레드가 앞에 있으면 완전 탐색을 할 필요가 없기 때문에 효율적이다.
    • 초기 구현은 Insert 함수를 통해서 구현했으나, AI에게 도움을 받아서 Ordered로 변경할 수 있었다.

 

// 순회 사용 방법
/*
 * for (e = list_begin (&foo_list); e != list_end (&foo_list);
 * e = list_next (e)) {
 *   struct foo *f = list_entry (e, struct foo, elem);
 *   ...do something with f...
 * }
*/

void thread_wakeup(int64_t tick)
{
	// [생각]
	// 1. 인터럽트를 중지한다
	// 2. WakeUp < Tick에 해당하는 Thread 깨우기
	// 3. 만약 Wakeup > Tick이면 중지
	// 4. 인터럽트 재시작
	// [순회를 어떻게 하는가?]
	// list_entry 활용하기

	// [구현]
	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)
		{
			iter = list_remove(&current_thread->elem);
			thread_unblock(current_thread);
		}
		else
			break;
	}

	intr_set_level(intr_lv);
}
  • wakeup 함수는 sleep 함수와 반대로 작동한다.
    • sleep_list에 위치한 쓰레드를 ready_list로 옮긴다.
    • 이때, 상태는 BLOCKED -> READY로 전환되어야 한다.
  • List 순회 방법은 함수 앞부분 주석에 있는 것과 같이 List.c에서 찾을 수 있다.
    • List.c 파일을 분석하면서 찾을 수 있었다!

 

bool compare_sleep_list(const struct list_elem *a, const struct list_elem *b)
{
	// list_entry 매크로를 사용하는 것만으로도 충분함.
	// b는 단수만 비교, a는 모든 것을 순회 비교.
	struct thread *thread_a = list_entry(a, struct thread, elem);
	struct thread *thread_b = list_entry(b, struct thread, elem);
   	return thread_a->wakeup_tick < thread_b->wakeup_tick;
}
  • 서로의 tick을 비교하고 True/False로 값을 반환한다.
  • 이런 상태로 작성된 이유는 list_insert_oredered 함수의 매개변수에 이유가 있다.
    • 시간이 된다면, 찾아보자! 생각보다 재미있는 실험을 할 수 있다.

 

☑️ 결과

 

강의 자료에 나온 것과 같이 Sleep/Wakeup 결과를 얻을 수 있었다.

'활동 > 크래프톤 정글' 카테고리의 다른 글

[크래프톤 정글/Week 08/PintOS] Priority Scheduling ( 정리 )  (1) 2024.11.07
[크래프톤 정글/Week 08] 키워드 정리  (3) 2024.11.05
[크래프톤 정글/Week 07] 키워드 정리  (1) 2024.10.29
[TIL/크래프톤 정글] Day 40 ~ 42  (4) 2024.10.12
[TIL/크래프톤 정글] Day 39  (8) 2024.10.09

티스토리툴바