(2021.10.12) Priority Scheduling - preemption

1. 서론 및 필요 내용 설명

또 잠시 포스팅을 하지 않았다. 진짜 새 게임 나와도 좀 참아야 할 텐데... 그리고 코딩하는데는 1시간, 포스팅하는데는 4시간씩 걸리니 수지타산이 뭔가 잘못된 것 같다. 기록을 위해 지난 포스팅까지 진행된 사항을 깃에 푸시했다. 이제 시작하자.

 

우선 구현을 위해 매뉴얼에 있는 문단을 보도록 하자.

When a thread is added to the ready list that has a higher priority than the currently running thread, the current thread should immediately yield the processor to the new thread. Similarly, when threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be awakened first. A thread may raise or lower its own priority at any time, but lowering its priority such that it no longer has the highest priority must cause it to immediately yield the CPU.

 

어떤 이유가 되었든, priority 스케줄링을 할 때는, 현재 실행될 수 있는 Thread 중 priority가 가장 높지 않다면 CPU를 회수해서 가장 높은 priority를 가진 Thread에게 주어야 한다는 것이다. 즉, CPU를 강제로 회수할 상황이 생긴다는 것이다. 따라서 preemption, 번역하면 '선점'이라는 루틴이 필요하다. 선점이란 실행되고 있는 Task로부터 일시적으로 자원을 강제로 회수해서 다른 Task에게 넘기는 것이다. 여기서 강조해야 할 부분은 '강제로', 즉 실행되고 있던 Task의 동의가 없어도 임의로 자원을 회수할 수 있어야 한다는 점이다. 우리가 앞서 살펴본 priority 스케줄링에서 요구되는 사항과 일맥상통하는 부분이다.

따라서 우리는 preemption 루틴을 구현하고, 어떤 상황에서 이 루틴이 실행되어야 하는지 생각해보아야 한다. 일단 구현은 차치하고 어디서 이 루틴이 돌아가야 하는지를 살펴보자. 위에 문단에 나와 있듯, 가장 직관적인 사례는 다음과 같다. 여기서 선점 루틴이 돌아간다 하더라도, 내부에서 조건 충족이 안되면 선점 과정이 중단될 수 있도록 하면 선점 루틴 실행 이전에 priority를 비교하는 과정은 생략할 수 있다. 

 

1. 새로운 Thread가 추가되었을 때
2. 현재 실행되던 Thread의 priority가 변했을 때
3. 다른 Thread가 Unblock되어 Ready Queue에 새로운 Thread(s)가 생겼을 때

이 정도 상황에서 선점이 발생해야 할 것이다. 이제 선점 루틴을 구현을 해 보도록 하자. 선점을 위해서는 현재 실행되고 있는 Thread가 CPU를 포기하도록 하는 함수를 실행시켜야 하며, 이와 관련된 함수를 찾아보면 다음과 같다.

 

1. thread_yield
2. intr_yield_on_return

여기서 thread_yield이 일반적인 상황에서 CPU를 양보할 때 호출된다는 것은 Alarm Clock을 하면서 알 수 있었다. 그럼 intr_yield_on_return은 언제 호출되어야 할까? 함수 이름 그대로 인터럽트 상황에 인터럽트 핸들러가 실행되는 과정에서 CPU를 양보해야 할 일이 생길 때 호출된다. 기존 Pintos는 Round Robin 스케줄링으로 구현되어 있어, 일정 타임 슬라이스를 경과하면 해당 함수를 호출하는 것을 볼 수 있으며, 이를 호출하는 시점이 타이머 인터럽트가 발생하는 도중이라 일반적인 thread_yield가 아닌 해당 함수를 호출하는 것이다.

 

---

2. 구현해야 하는 것

• preemption 루틴
• 기타 priority 스케줄링을 위한 수정

 

---

3. 구현 과정

CPU를 양보하는 함수를 고려하여 preemption() 함수를 구현하면 다음과 같다.

bool
cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux) {
	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;
}

void
preemption (void) {
	enum intr_level old_level;
	struct thread *next_ready;

	old_level = intr_disable();
	list_sort (&ready_list, cmp_priority, NULL);

	// first deal with the original Round Robin case
	if (intr_context() && thread_ticks >= TIME_SLICE) {
		intr_yield_on_return();
	}

	else if (!list_empty(&ready_list))
	{
		next_ready = list_entry (list_front (&ready_list), struct thread, elem);

		if (next_ready->priority > thread_current()->priority) {
			if (intr_context()) intr_yield_on_return();
			else thread_yield();
		}
	}
	
	intr_set_level (old_level);
}

이에 맞춰서, thread.c의 thread_create(), thread_set_priority(), thread_tick()와 synch.c의 sema_up()을 수정한다. 

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

void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	preemption ();
}

void
thread_tick (void) {
	...
	/* Enforce preemption. */
	thread_ticks++;
	preemption ();
}

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;

	preemption ();
	intr_set_level (old_level);
}

Thread가 한 번에 여럿 Unblock되는 경우 또한 있을 수 있고, thread_unblock()이 intq에서도 불리는 함수이므로 어떤 영향을 줄 지 알 수 없기에 thread_unblock()에는 직접적으로 preemption()을 넣지 않았다.

 

이제 1차적으로는 priority 스케줄링이 거의 완성되었다. 이제 남은 수정 사항은, Thread가 priority가 높은 순서대로 ready_list에서 나오도록 하는 것이다. 현재 구현 상태를 보면, Thread를 ready_list에서 꺼내는 방법은 전부 list_pop_front 방식을 채택하고 있기 때문에, ready_list에 thread를 넣는 방법만 list_insert_ordered로 바꿔주면 priority 순서대로 Thread가 스케줄링 되도록 할 수 있다. ready_list에 직접적으로 Thread를 넣는 함수는 sema_down, thread_yield, thread_unblock이므로 이들을 수정한다.

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_insert_ordered (&sema->waiters, &thread_current ()->elem, cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

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, cmp_priority, NULL);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

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, cmp_priority, NULL);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

이제 기본적인 priority 스케줄링이 구현되었다.

 

---

4. 디버깅

여기까지 진행을 하면, 기본적인 테스트 케이스인 alarm_priority, priority_change, priority_preempt, priority_fifo가 작동해야 한다. make check를 좀 진행하면 잘 pass하는 것을 볼 수 있다.

 

전체 실행결과가 실패한 케이스들 때문에 너무 길어서 편집. 통과해야 할 케이스는 전부 통과한 것을 확인할 수 있다.

 

아직 이전 포스팅에서 다룬 priority inversion 현상에 대한 수정이 가해지지 않아, 이름에 "donate"가 붙은 주요 케이스들은 전부 실패한다. 이는 다음 포스팅에서 다룰 것이다.

 

---

5. 후기

포스팅 내에 코딩 과정을 좀 간소화해봤다. 포스팅이 좀 빨라지긴 했으니 이런 식으로 진행해야 하나...