[크래프톤 정글/Week 08/PintOS] Priority Scheduling ( 높은 우선순위 먼저 실행하기 )

🖐️Priority Scheduling ( 높은 우선순위 먼저 실행하기 )

 

1️⃣ 우선순위 정렬 함수 만들기

// thread.c

bool compare_priority(const struct list_elem* a, const struct list_elem* b, void* check UNUSED)
{
	struct thread *thread_a = list_entry(a, struct thread, elem);
	struct thread *thread_b = list_entry(b, struct thread, elem);
	return thread_a->priority > thread_b->priority;
}

// thread.h

bool compare_priority(const struct list_elem*, const struct list_elem*, void*);

• ready_list를 우선순위 기준으로 내림차순 정렬해주어야 한다.
• 정렬에 필요한 함수를 구현한다.

 

2️⃣ ready_list 값 추가 방법 변경

void thread_yield(void)
{
	...
	if (curr != idle_thread)
		list_insert_ordered(&ready_list, &curr->elem, compare_priority, NULL);
	...
}

void thread_unblock(struct thread *t)
{
        ...
	list_insert_ordered(&ready_list, &t->elem, compare_priority, NULL);
	...
}

 

• ready_list 삽입은 thread_yield 함수와 thread_unblock 함수에서 일어난다.
• 우선순위를 기준으로 내림차 정렬 할 수 있게, list_insert_ordered 함수로 기존 추가 방식을 변경한다.

 

3️⃣ CPU 선점 확인 함수 만들기

// thread.c

void check_preempt()
{
	if(list_empty(&ready_list) || thread_current() == idle_thread)
		return;

	struct thread *curr = thread_current();
    struct thread *front = list_entry(list_front(&ready_list), struct thread, elem);
    if (curr->priority < front->priority)
        thread_yield();
}

// thread.h

void check_preempt();

• 1, 2번의 작업을 통해서 ready_list는 0번째 Index에 가장 높은 우선순위의 스레드가 존재함을 알 수 있다.
• ready_list의 0번째 Index 우선순위와 현재 실행중인 스레드의 우선순위를 비교해야 한다.
  • 새롭게 삽입된 스레드가 실행중인 스레드보다 우선순위가 높다면, 문맥교환이 일어나야 한다.

 

4️⃣ 선점 확인 함수 적용하기

tid_t thread_create(const char *name, int priority,
					thread_func *function, void *aux)
{
	...
	/* Add to run queue. */
	thread_unblock(t);
	check_preempt();
	...
}

void thread_set_priority(int new_priority)
{
	...
	check_preempt();
}

• Priority가 변경될 수 있는 함수들을 찾아서 위와 같이 넣을 수 있다.
• thread_create 함수는 스레드가 생성되는 함수기 때문에, 현재 실행중인 스레드보다 높은 우선순위의 값이 들어올 수 있다.
  • 이 경우를 고려해서 선점 확인 함수를 추가한다.
• thread_set_priority 함수는 현재 실행중인 스레드의 우선순위를 변경한다.
  • ready_list의 0번째 index 스레드보다 낮은 우선순위로 변경되었을 가능성을 고려해서 선점 확인 함수를 추가한다.

 

▶️ Wakeup 함수에 추가하지 않는 이유
: sleep_list의 정렬 기준은 남은 수면 시간이 적은 스레드를 우선으로 가진다. 그렇기 때문에 sleep_list에서 ready_list로 옮겨주는 Wakeup 함수에도 추가해주어야 한다고 생각할 수 있다. 실제로 본인도 처음에는 그렇게 생각하고 선점 확인 함수를 추가했는데, 이후 팀원의 이야기를 듣고 Wakeup 함수에서 선점 확인 함수를 제거했음에도 선점 관련 TC에서 동일한 PASS 수를 얻었다.

지금 글을 쓰고 있는 시점까지 팀원들과 여러 이야기를 나눠봤고 가장 큰 의문은 다음과 같았다.
- 인터럽트 발생 시, 컨텍스트 스위칭이 일어나기 때문에 Wakeup 함수에서 제외한다면, thread_create 함수에서도 선점 확인 함수를 제거해도 괜찮지 않은가? -> 선점 관련 TC 통과 실패

현재까지의 생각은 다음과 같다.

⭐ thread_create 함수에 선점을 추가하는 것은 명확한 컨텍스트 스위칭을 호출해야 하기 때문이다.
: 인터럽트로 인한 컨텍스트 스위칭은 우리가 기대하는 시점에 발생하지 않기 때문에 명확한 지점을 정의해야 한다.

정확한 사유를 알고 있으신 분이 있다면, 댓글 부탁드립니다🙏