PintOS Project1: Threads

priority-change, priority-fifo, priority-preempt 케이스

우선순위 기반 스케줄링을 위해서는 먼저 삽입된 쓰레드의 우선순위가 더 높다면, 즉시 양보(yield)해줘야합니다.
만약, 동기화 도구를 사용한다면 우선순위의 쓰레드가 먼저 켜져야합니다.

이번 문제부터 세세하게 바뀌는 것도 있고 코드 순서대로 설명하는 것이 어렵습니다. 그러므로 제목에 있는 숫자 순서대로 설명을 참고하면 좋을 것 같습니다.

코드 순서는 밑에 나와있는 순서와 같습니다. 설명만 숫자를 참고하여 봐주세요. 사람마다 구현 순서는 다를 수 있습니다.

threads.c

2. thread_create

정렬 유지하는 priority_cmp 선언합니다.

// 추가된 우선순위 비교
bool priority_cmp (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);

밑에 있는 ready_list에 priority를 비교하여 우선순위가 큰 스레드가 앞에 위치하게 만들어주는 priority_cmp 를 어디서든 사용할 수 있게 전역변수로 선언합니다. 선언하지 않으면, 밑에 쪽에 위치하여 다른 함수에서 인식하지 못합니다.

5. thread_create

새로 생성되는 스레드도 CPU 스케줄링 원칙에 따라 양보하여야합니다.

tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;
	
	...
	
	thread_unblock (t);

  //////
	struct thread *T1 = list_entry(list_front(&ready_list), struct thread, elem);
	enum intr_level old_level;
	old_level = intr_disable ();   // 인터럽트를 비활성화하고 이전 인터럽트 상태를 반환합니다.
	if ((thread_current() != idle_thread) && (thread_current() -> priority < T1 -> priority))
	thread_yield (); // 우선순위를 바꼇다면, 우선순위에 따라 yield 해줘야한다.
	intr_set_level (old_level);   // 인터럽트 다시 받게 재세팅
  //////

	return tid;
}

현재 실행중인 스레드가 T1이라는 새로운 스레드보다 priority(우선순위)가 낮다면, 양보해 주어야합니다. 그러므로 스레드를 생성하는 thread_create 에도 양보해주는 코드를 추가합니다.

3. thread_unblock

unblock에서 우선순위에 따라 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_insert_ordered (&ready_list, &t->elem, priority_cmp, NULL);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

thread_yield 때와 마찬가지로,
list_push_back (&ready_list, &curr->elem); → list_insert_ordered (&ready_list, &curr->elem, priority_cmp, NULL); 로 우선순위에 따라 t라는 현재의 스레드가 비교를 통해서 ready_list 에서 priority에 따라 정렬할 수 있게 합니다.

1. thread_yield

우선순위에 따라 ready_list 정렬합니다.

양보를 하기 위한 ready_list에 삽입할 때, 새로 삽입되는 스레드의 우선순위 priority에 따라 큰것을 앞에 위치하도록 list_insert_ordered 을 사용합니다.

// 스레드 스트럭쳐 내부의 인자 가져옴(priority가져와야함)
bool priority_cmp (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *T_A = list_entry(a, struct thread, elem);
	struct thread *T_B = list_entry(b, struct thread, elem);

	return T_A -> priority > T_B -> priority;
}

/* CPU를 양보합니다. 현재 스레드가 sleep 모드로 전환되지 않았습니다
   스케줄러의 요청에 따라 즉시 다시 사용할 수 있습니다. */
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_insert_ordered (&ready_list, &curr->elem, priority_cmp, NULL);   // LIST의 끝에 ELEM을 삽입하여 LIST의 뒤에 위치하도록 합니다.
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

기존의 list_push_back (&ready_list, &curr->elem); → list_insert_ordered (&ready_list, &curr->elem, priority_cmp, NULL); 로 현재 실행중인 스레드와 ready_list 스레드의 priority(우선순위) 값을 순서에 맞게 정렬해서( priority_cmp 참고)삽입합니다.

thread_yield 의 9번째 줄부터 흐름은 다음과 같습니다.

1. 현재 실행 중인 스레드(curr)가 idle_thread가 아니면, ready_list에 다시 넣습니다.
2. 넣을 때는 priority_cmp()를 사용해서, 현재 스레드를 우선순위에 맞게 리스트에 정렬해서 삽입합니다.
3. 그 다음 do_schedule()을 호출해서 ready_list 안에서 다른 더 높은 우선순위 스레드를 고르고 context switch를 합니다.

priority_cmp : T_A(실행중인 스레드)가 T_B(ready_list 스레드)보다 priority가 크면 앞에 정렬합니다. → 우선순위가 높은 스레드가 리스트 앞쪽에 오도록 정렬하는 역할을 합니다.

4. thread_set_priority

해당 함수는 다음과 같은 역할을 수행해야합니다.

1. 우선순위 낮아진 스레드는 양보해야 하므로, 직접 체크 후 yield 합니다.
2. 현재 대기 중인 스레드보다 내가 낮은 우선순위면 CPU를 넘깁니다.
3. 중간에 리스트 바뀌지 않도록 인터럽트 비활성화 사용합니다.

/* 현재 실행 중인 스레드의 우선순위를 동적으로 변경합니다. */
void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	if (list_empty(&ready_list))  return;   // 리스트가 비었을때 그냥 종료
	struct thread *T1 = list_entry(list_front(&ready_list), struct thread, elem);
	enum intr_level old_level;

	old_level = intr_disable ();   // 인터럽트를 비활성화하고 이전 인터럽트 상태를 반환합니다.
	if ((thread_current() != idle_thread) && (thread_current() -> priority < T1 -> priority))
	thread_yield (); // 우선순위를 바꿨다면, 우선순위에 따라 yield 해줘야한다.
	intr_set_level (old_level);   // 인터럽트 다시 받게 재세팅
}

기존 코드의 thread_current ()->priority = new_priority; 은 그냥 현재 스레드의 우선순위만 바뀌고 양보를 하지 않습니다.

그러므로 앞에 서술한 기능을 수행하기 위해 if ((thread_current() != idle_thread) && (thread_current() -> priority < T1 -> priority)) thread_yield (); 를 통해 우선순위에 따라 양보를 합니다. 물론 전에 배운 내용처럼 중간 과정에 문제가 생기지 않게 인터럽트를 비활성화해주고 과정이 끝나면 되돌려야합니다.

→ 여기서 트러블 슈팅이 있었는데, FIFO를 구현하기 위해 if (list_empty(&ready_list)) return; 문을 추가해야했습니다. 왜냐하면, 리스트가 비는 경우에 비어 있는 리스트에서 꺼내면 assert failure 혹은 segmentation fault가 발생하기 때문입니다. (FIFO는 list_front() , list_pop_front() 사용으로 커널 패닉옴)

추가로 알아보기 (idle_thread)

지금 위의 코드들을 보면 눈치채셨겠지만, clock.c 와 다르게 ready_list 리스트를 넣기전 현재 실행중인 스레드인 thread_current 가 idle_thread 상태인지 확인하는 과정이 우선순위 비교전에 if문으로 위치합니다.

if (curr != idle_thread)
		list_insert_ordered (&ready_list, &curr->elem, priority_cmp, NULL);

그러면 왜 현재 실행중인 프로세스가 idle_thread 상태인지 확인할까요?
해당 질문에 대한 답을 알기 위해서는 idle_thread 상태가 무엇인지 알아야합니다.

idle_thread 는 Pintos에서 idle_thread는 아무 일도 하지 않는 특수한 스레드입니다.

• ready_list가 비었을 때 CPU가 놀지 않도록 하기 위해 존재합니다.
• thread_schedule()이 다음 스레드를 선택할 때, ready_list가 비면 idle_thread를 실행시킵니다.
• 이 스레드는 for (;;) 무한 루프를 돌며 HLT(휴면 명령) 상태에 들어가 CPU 리소스를 줄입니다.

idle_tread 는 ready_list에 넣으면 안 될까요? 다음과 같이 3가지 이유가 있습니다.

1. ready_list는 실제 "작업 스레드들"만 관리해야 합니다.

• ready_list는 "언제든 실행 가능한 스레드들의 대기열"입니다.
• idle_thread는 본질적으로 실행되면 안 되는 스레드입니다. (단, 다른 스레드가 없을 때만 예외적으로 실행돼야 합니다.)

→ 만약 idle_thread가 ready_list에 들어간다면, 정상적인 작업 스레드보다 먼저 선택될 수도 있고, 우선순위 스케줄링도 이상해집니다.

2. priority scheduling을 망칠 수 있습니다.

• idle_thread는 일반적으로 우선순위 0(가장 낮음)을 가지는데, ready_list에 들어가면 우선순위 비교에 혼선을 줄 수 있습니다.
• 특히 list_max() 같은 함수를 사용해서 최고 우선순위 스레드를 찾는 경우, idle_thread가 섞여 있으면 의도하지 않게 선택될 수 있습니다.

3. 디버깅, 로직 추적이 혼란합니다.

• idle_thread는 특별한 경우에만 실행되는 스레드이기 때문에, 일반 ready_list와 섞이면 스케줄링 상태를 추적하기 어렵게 만듭니다.

사실상 idle_thread 현상은 잘 일어나지 않는다고 합니다. 왜냐하면, 정말로 ready_list가 비어서 CPU가 정말 할게 없을때 일어나기 때문입니다. 그러나 지금 Pintos는 교육용으로 OS 철학적인 면을 요구하기 때문에 예외적 상황도 생각한다고 이해하면 편하실 것으로 생각됩니다.

이와 같이 여러가지 이유로 우선순위 리스트에 비교하여 삽입하기 전에 if문으로 idle_thread 인지 확인하게 됩니다.

테스트해보기

make tests/threads/priority-change.result VERBOSE=1

pintos / threads / build 폴더에서 위의 명령어를 통해 priority-change 테스트 케이스만 실행시킬 수 있습니다. 그러면 결과는 다음과 같이 나옵니다.

제가 보면 왔다 갔다하면서 코드를 작성하긴했는데, 제 식대로 구현하고 트러블 슈팅을 해결하려다 보니 그런것 같습니다. 좀 아쉬움이 남으며 막상 코드를 설명하려고 작성하니 애매한 부분이 있어 다시 공부를 하는 시간을 가졌습니다. 앞으로도 혼자 힘으로 해보며 Pintos에 대해서 더 알아보는 시간을 가지겠습니다.