저번 크래프톤 정글 포스팅은 66일차였는데요. 갑자기 80일차가 되었네요.

왜냐하면 Pintos 프로젝트를 진행하는 것 만으로도 너무 어려워서 도저히 제가 공부하고 알아낸 것들을 잘 정리할 시간이 없었습니다. 다행히도 3주차가 끝나기 하루전인 지금 시간이 나서 3주동안 팀과 함께 공부한 내용들을 정리해보려고 해요.

총 2개의 Part threads와 userprog를 진행했는데 그 중 이번에는 1주차 과제인 threads에 대해서 정리하고, 그 테스트 케이스인 alarm기능과 priority-donation기능에 대해서 잘 정리해보려고 합니다.

💡1주차의 목표

우리는 모든 테스트 케이스를 통과하려고 Pintos 프로젝트를 진행하는 것이 아니예요.
그 과정에서 어떤 것들을 공부하고 체득했느냐가 더 중요해요. ( 테스트 케이스 다 통과 못해서 이러는거 진짜 아님 )

🔍 제가 생각하는 1주차의 중요한 키워드는 3가지 입니다.

1. threads의 상태에 대해서 이해하기
2. CPU의 thread scheduling에 대해서 이해하기
3. 동기화 문제 해결하기

이 과정을 핀토스에서 구현해나가는 순서대로 정리해볼게요. 다만, 핀토스는 Round-robin 스케쥴링 방식과 busy-waiting 으로 구현되어있기 때문에, 그 이전부터 살펴볼거예요.

---

threads의 상태는 여러가지가 있지만, Pintos 는 교육 목적 때문인지 4가지의 상태만으로 threads를 구분하고 있어요.

include/threads/thread.h

• THREAD_RUNNING : 현재 CPU에 할당되어 실행되고 있는 쓰레드예요.
• THREAD_READY : CPU에 할당되진 않았지만 스케쥴러에 의해 다음으로 할당될 수 있는 쓰레드예요.
• THREAD_BLOCKED : 실행이 가능해지는 이벤트를 기다리고 있어요.
• THREAD_DYING : 쓸모를 다하고 죽어버린 쓰레드입니다. 리소스 정리를 기다리고 있어요.

우리는 이 thread의 상태를 적절히 이용해서 알맞은 쓰레드를 CPU에 적재되어 실행되게 해줘야 해요.

우선 가장 쉬운 방법으로는 READY상태에 있는 쓰레드를 들어온 순서대로 CPU에 할당되어서 처리하게 해줄 수 있어요.

총 실행시간이 적혀있는 thread A, B, C, D가 있어요.

어렵게 생각할거 없이 쓰레드를 각각 순서대로 넣어서 실행이 끝나면 상태를 THREAD_DYING으로 바꿔주고 리소스 정리를 기다리게 하면 돼요.

빠른 이해를 돕게하기 위해 앞으로 실행시간은 tick 단위로 하겠습니다!
즉, thread 에 적혀있는 숫자는 이 쓰레드가 끝나는데 필요한 tick 이예요.

🤔 tick이 4가 되었기 때문에 thread A는 모든 실행을 끝마칠수 있었고 본인의 역할을 다한 thread A는 dying상태가 되었어요.

그리고 다음 순서로 ready_list 에 들어있던 thread B가 실행되었습니다.

그 뒤로는 ready_list 에 들어있던 thread를 running 중이던 쓰레드의 실행이 완료되면 순서대로 넣어줄 수 있었어요.

근데 이 방식에는 문제점이 있었습니다. ❌

• 큰 실행시간을 가진 쓰레드가 먼저 실행될 경우, 실행시간이 짧은 다른 쓰레드가 기다리는 시간이 너무 길었어요.

예를 들어 위의 예에서 thread D 가 가정 먼저 실행된다고 해볼게요.

thread D 는 2042라는 긴 실행시간을 가지고 있기 때문에 D가 완료되기 전까지 다른 thread는 실행되지 않아요. 그래서 사용자는 컴퓨터가 멈춘 것처럼 느낄 수도 있었어요.

사용자는 동시에 여러 작업

• 마우스를 이동시키고
• 어떤 파일을 다운로드하고
• 파일을 다운로드하면서 웹브라우저를 탐색하고

등등..을 동시에 수행하고 싶어할 수 있어요.
💡 그래서 Round-robin 이라는 새로운 스케쥴링 방식이 탄생했습니다.

여러분이 Pintos project에서 아무작업도 하지 않았다면 Round-robin 방식 ( 4 tick 마다 변경 ) 으로 구현되어있을 거예요.

원래는 실행시간이 모두 끝나야 다음 쓰레드를 실행할 수 있었는데요.

보시는 것처럼 CPU에서의 실행이 모두 끝났는데 아직 더 실행되어야 할 게 남아있다면
다시 ready_list 큐의 가장 뒤에 줄을 서시는 것을 확인할 수 있어요.

만약 더 이상 실행될 필요가 없다면, thread A처럼 죽으면 되겠죠?

이렇게 Round-robin 방식을 사용할 경우

• 긴 실행시간을 가진 쓰레드를 기다릴 필요가 없게 되었어요.
• 사용자는 마치 여러 작업이 동시에 되는 것처럼 생각해요

근데 Pintos에서는 여기서 한가지 문제점을 제시합니다.

busy waiting 으로 구현된 코드를 sleep으로 바꿔주세요.

만약 쓰레드 A가 어떤 조건을 만족해야 실행이 되어야한다고 생각해보세요.
예를 들면, 쓰레드 A는 60tick 이상에서만 실행되어야 한다 는 조건이예요.

근데 CPU에 할당이 되어서 실행이 되면 어떻게 될까요?
Pintos에서는 이렇게 구현되어 있어요.

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

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

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() 함수는 현재 실행중인 쓰레드를, 다시 ready_list의 마지막으로 보내는 함수예요.

근데 만약, 현재 실행가능한 쓰레드가 A밖에 없고, A는 60tick 이후에만 실행될 수 있다면?

굉장히 바빠보이네요. thread A는 할 것도 없는데 CPU를 계속 사용하면서 낭비하고 있어요.

이 문제를 sleep 방식으로 해결해달라고 Pintos는 요구하고 있습니다.

해결방법은 간단합니다. thread A가 깨어날 tick까지 재워주는 list를 하나 더 만들어주면 돼요.
ready_list 처럼 sleep_list를 하나 만들어주는 거예요. 그때 쓰레드의 상태는
THREAD_BLOCKED예요. 이제 우리는 특정 조건을 만족할 때까지 이벤트 트리거를 기다리는 THREAD_BLOCKED라는 쓰레드의 상태를 하나 더 알게되었네요.

A는 더이상 바쁘게 살지 않아도 돼요. sleep_list 에서 누군가 깨워줄 때까지 행복하게 살면 되거든요.

THREAD_RUNNING 에는 idle_thread 라는 특별한 쓰레드가 들어가 있어요.

static struct thread *
next_thread_to_run (void) {
	if (list_empty (&ready_list))
		return idle_thread;
	else
		return list_entry (list_pop_front (&ready_list), struct thread, elem);
}

thread.c의 next_thread_to_run함수는 다음 스케쥴될 쓰레드를 ready_list 에서 찾지만 만약 아무것도 없다면 idle_thread를 스케쥴해요.

🤔 CPU를 쉬게해준다면서 왜 idle_thread라는 걸 넣어요? 그냥 아무것도 안넣으면 되잖아요.

그럼 컴퓨터 죽은거임

운영체제는 다음 실행될 인스트럭션을 계속 지정해주고 어떤 동작을 계속 하게끔 만들어야 해요. 운영체제 입장에서는 아무것도 실행되지 않는 것 자체가 큰 오류사항입니다. 그래서 idle_thread라는 정말 최소한의 동작만 하는 thread를 만들어서 넣어주는 거예요.

여기까지의 alarm 코드는 다음과 같습니다.

/* thread.h 파일 */
struct thread {
	/* thread.c가 소유 */
	tid_t tid;                          /* 스레드 식별자 */
	enum thread_status status;          /* 스레드 상태 */
	char name[16];                      /* 이름 (디버깅 목적) */
    int priority;                       /* 실제 비교에 사용되는 priority */
	/* thread.c와 synch.c가 공유 */
	struct list_elem elem;              /* 리스트 요소 */
    
    /* project 1.1 alarm wakeup 을 위한 구조체 */
    int64_t ticks;                       /* wake up time */
}

/* project 1.1 alarm 을 위한 커스텀 함수 목록 */
void thread_sleep(int64_t ticks);
bool cmp_ticks(const struct list_elem *a, const struct list_elem *b, void * aux );
void thread_wakeup();
int64_t get_minimum_tick(void);
void set_minimum_tick(void);

---

/* timer.c 파일 */

void
timer_sleep (int64_t ticks) {
	ASSERT (intr_get_level () == INTR_ON);
	
    if ( ticks == 0 ) return;
    
    /* project 1.1 alarm 의 busy_waiting 을 해결하기 위한 thread_sleep */
    thread_sleep( timer_ticks() + ticks );
}

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
    
    /* project 1.1 alarm으로 쓰레드를 wake up 시키기 위한 함수 */
    if ( get_minimum_tick() <= ticks ) {
        thread_wakeup();
    } 

	thread_tick ();
}

---

/* thread.c 파일 */
static struct list sleep_list;

static int64_t minimum_tick = INT64_MAX; /* Sleep_list 에 있는 쓰레드 tick 중 가장 작은 값 */

void
thread_init (void) {
	/* 이외의 다른 코드..*/
	lock_init (&tid_lock);

	list_init (&ready_list);
    list_init( &sleep_list);
	list_init (&destruction_req);

	/* 이외의 다른 코드.. */
}

/* 
    project 1.1 alarm 을 위해 추가된 함수
    현재 쓰레드를 ticks 초 동안 쉬게 만듭니다. 
*/
void 
thread_sleep(int64_t ticks){
    struct thread *t = thread_current();

    /* 쓰레드 리스트를 조작할 때는 인터럽트를 비활성화 시키기 */
    enum intr_level old_level = intr_disable();

    /* 1. 현재 스레드가 idle 쓰레드가 아니라면 */
    if ( t != idle_thread) {
        /* 2. 깨울 시점의 tick 값을 저장 */
        t->ticks = ticks;
    
        /* 3. sleep list에 ticks 값 기준으로 정렬 */
        list_insert_ordered(&sleep_list, &t->elem, cmp_ticks, NULL);
        
        /* 4. minimum_tick 갱신 */
        set_minimum_tick(); 
        
        /* thread 를 sleep_list 로 */    
        thread_block();
    }
    
    intr_set_level(old_level);
}

/* 
    project 1.1 alarm을 위한 함수
    sleep_list 에서 조건에 맞는 thread를 ready_list로 옮겨줍니다. 
*/
void
thread_wakeup() {
    struct list_elem *e;

    enum intr_level old_level = intr_disable();

    e = list_begin(&sleep_list);

    while ( e != list_end(&sleep_list) ) {
        struct list_elem *next = list_next(e);
        struct thread *current = list_entry(e, struct thread, elem);

        if ( current->ticks <= timer_ticks()) {
            list_remove(e);
            thread_unblock(current);

            /* 
                thread_wakeup 은 무조건 timer interrupt 안에서 호출됩니다.
                따라서 thread_yield 가 아닌 intr_yield_on_return 을 사용해줘야 안전합니다.
            */
            intr_yield_on_return ();
        } else {
            break;
        }
        
        e = next;
    }

    /* sleep_list가 변경되었을 가능성이 있으므로 min_tick 을 갱신해줍니다. */
    set_minimum_tick();
    intr_set_level(old_level);
}

/* 
    project 1.1 alarm 을 위한 함수
    minimum_tick 을 sleep_list의 가장 작은 tick과 비교해서 갱신합니다. 
    set_minimum_tick 은 intr 을 멈춘 상황에서만 호출되기 때문에,
    사용하지 않아도 안전합니다.
    
    다만 더 보안에 신경쓰고 싶다면 intr 를 호출해도 상관 없습니다.
*/
void 
set_minimum_tick(void){
    ASSERT(intr_get_level() == INTR_OFF);

    minimum_tick = INT64_MAX;
    
    if (list_empty(&sleep_list)) {
        return;
    }
    
    struct thread *t = list_entry(list_begin(&sleep_list), struct thread, elem);
    minimum_tick = min ( minimum_tick , t->ticks );
}

/* 
    project 1.1 alarm 을 위한 함수
    minimum_tick 값을 반환합니다. 
*/
int64_t
get_minimum_tick(void){
    enum intr_level old_level = intr_disable();
    int64_t m = minimum_tick;
    intr_set_level(old_level);
    barrier();
    return m;
};

위 과정에서 언제 인터럽터를 활성화하고 비활성화하는지 잘 확인해보세요.
intr_disable()을 실행하면 tick 이 더 이상 올라가지 않아요!
쓰레드는 현재 4초마다 컨텍스트 스위칭되고 있기 때문에

컨텍스트 스위칭이 발생하면 안되는 상황에서 막아줘야 할 필요가 있어요.

생각보다 글이 길어져서 priority 는 다음에 이어서 작성하겠습니다.