[Pintos] Priority Scheduler

문제 상황:

• Pintos의 스케쥴러는 리스트에 삽입되는 순서대로 스레드를 스케쥴링한다.
• 우선순위에 따라 스레드를 정렬해서 우선순위가 높은 스레드를 먼저 스케쥴링 할 수 있도록 한다.

개선 사항 1 - Priority Scheduling :

🔖 스케쥴링되는 스레드는 ready_list에서 가장 우선순위가 높은 스레드여야 한다.
이를 위해 리스트 안에 스레드를 삽입할 때마다 스레드를 우선순위에 따라 정렬되도록 만들었다.
이렇게 되면 리스트의 가장 앞에 우선순위가 가장 높은 스레드가 위치하게 된다.
그리고 스케쥴링은 리스트의 맨 앞의 스레드를 대상으로 하게 된다

🔖 리스트 안에 스레드가 삽입되는 경우는 총 3가지이다.
1. 스레드가 생성될 때
2. CPU를 점유하고 있던 스레드가 대기상태로 돌아갈 때
3. block 상태의 스레드가 다시 unblock될 때

주요 코드

void list_insert_ordered(struct list *list, struct list_elem *elem,
						 list_less_func *less, void *aux)
{
	struct list_elem *e;

	ASSERT(list != NULL);
	ASSERT(elem != NULL);
	ASSERT(less != NULL);

	for (e = list_begin(list); e != list_end(list); e = list_next(e))
		if (less(elem, e, aux))
			break;
	return list_insert(e, elem);
}

해당 함수의 3번째 인자로 list_less_func *less가 들어가는 데 이는 두 요소를 비교하는 조건 함수가 된다. 해당 인자로 cmp_priority 함수를 사용하는데 해당 함수는 두 인자의 우선순위를 비교하는 함수이다.

bool cmp_priority(const struct list_elem *a_,
				  const struct list_elem *b_, void *aux UNUSED)
{
	struct thread *a = list_entry(a_, struct thread, elem);
	struct thread *b = list_entry(b_, struct thread, elem);

	if (a->priority > b->priority)
		return 1;
	else
		return 0;
}

🔖 Prority Preemption
스레드가 새로 생성되거나 우선순위가 변경될 경우 ready list에서 가장 높은 우선순위를 가진 스레드와 현재 CPU를 점유하고 있는 스레드의 우선순위를 비교하여 대기중인 스레드가 더 높은 우선순위를 가지게 될 경우 CPU를 우선 점유하는 것.

🔖 락, 세마포어, 조건변수를 얻기위해 스레드가 기다릴 경우에도 우선순위가 가장 높은 스레드가 점유할 수 있도록 한다. 이 경우에도 이전과 동일하게 리스트에 삽입할 때 우선순위 순으로 정렬하는 방식을 사용했다.

주요 코드

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);
}

개선 사항 2 - Prority Inversion :

• 우선순위 역전 상황 문제를 개선하여야 한다.
• 해당 상황은 lock A를 보유하고 있는 스레드 low, lock B를 보유하고 있는 스레드 mid, lock A를 보유하고자 하는 스레드 high가 있는 상황을 가정한다.
• lock은 점유할수 있는 공유자원이 1개밖에 없는 세마포어이다.
• 그래서 high는 더 높은 우선순위를 가지고 있음에도 low가 이미 락을 할당받고 있기에 락의 할당을 해제할 때까지 기다려야 한다.
• 그런데 스레드mid는 다른 공유자원을 점유하여 우선순위가 더 높기 때문에 priority preemption이 발생한다.
• 이로 인해 high는 우선순위가 더 높음에도 불구하고 더 늦게 CPU를 점유하게 된다. 우선순위 역전 - **priority inversion**

🔖 스레드 high가 원하는 lock을 보유하고 있는 스레드 low에게 high가 보유하고 있는 우선순위를 기부(donation)한다. 이로 인해 low는 high의 우선순위를 보유하게 되고 mid에 의해 선점당하지 않게된다. → inversion 해결

🔖 기부할 스레드들을 모아놓는 리스트를 구성하였다. lock 구조체에는 해당 lock을 보유하고 있는 스레드의 주소가 저장되어 있다.
lock_acquire를 통해 해당 lock을 얻으려고 할 때, 이미 점유하고 있는 스레드 A가 있는 경우 해당 스레드의 donations에 해당 스레드를 저장한다. 이때 스레드를 우선순위 순으로 정렬한다.
그러면 donations에는 스레드A가 가지고 있는 lock을 기다리는 스레드들이 모여있게 된다.

🔖 여러 lock을 보유하고 있을 때 lock을 기다리면서 우선순위를 기부하고자 하는 스레드들을 모아놓으면 효과적으로 기부 스레드들을 관리할 수 있다.

🔖 만약 lock을 release 할 경우에는 donations를 순회하면서 해당 lock을 기다리고 있는 스레드를 donations에서 제거하면 된다. → multiple donations

void remove_with_lock(struct lock *lock)
{
	struct list *donation_list = &lock->holder->donations;
	if (!list_empty(donation_list))
	{
		struct list_elem *s;

		s = list_begin(donation_list);
		while (s != list_end(donation_list))
		{
			struct thread *t = list_entry(s, struct thread, donation_elem);
			if (t->wait_on_lock == lock)
			{
				s = list_remove(s);
				continue;
			}
			s = list_next(s);
		}
	}
}

🔖 만약 스레드의 우선순위가 변경 되었을때 donation 을 고려하여 우선순위를 다시 결정한다.
가장 우선수위가 높은 donations 리스트의 스레드와 현재 점유 중인 스레드의 우선순위를 비교하여 높은 값을 현재 스레드의 우선순위로 설정한다

void refresh_priority(void)
{
	/* 스레드의 우선순위가 변경 되었을때 donation 을 고려하여
	우선순위를 다시 결정 하는 함수를 작성 한다. */

	/* 현재 스레드의 우선순위를 기부받기 전의 우선순위로 변경 */
	thread_current()->priority = thread_current()->init_priority;

	/* 가장 우선수위가 높은 donations 리스트의 스레드와
	현재 스레드의 우선순위를 비교하여 높은 값을 현재 스레드의
	우선순위로 설정한다. */
	if (!list_empty(&thread_current()->donations))
	{
		struct thread *max_t = list_entry(list_begin(&thread_current()->donations), struct thread, donation_elem);
		if (thread_current()->priority < max_t->priority)
			thread_current()->priority = max_t->priority;
	}
}

🔖 해당 구조는 lock을 원하는 스레드들의 연결 구조가 재귀적으로 이어지는 경우이다. 노랑 스레드는 주황 스레드가 보유하고 있는 락을 기다리고 있다. 그런데 주황스레드는 빨간 스레드가 보유하고 있는 락을 기다리고 있다. 빨간 스레드는 초록 스레드가 보유하고 있는 락을 기다리고 있다. … 이렇게 꼬리물기 형태로 lock을 기다리고 있는 경우를 감안하여 기부를 진행하여야 한다.

주요 코드

lock_acquire

void lock_acquire(struct lock *lock)
{
	ASSERT(lock != NULL);
	ASSERT(!intr_context());
	ASSERT(!lock_held_by_current_thread(lock));

	if (lock->holder != NULL)
	{
		thread_current()->wait_on_lock = lock;
		list_insert_ordered(&lock->holder->donations, &thread_current()->donation_elem, cmp_priority, NULL);
		donate_priority();
	}
	sema_down(&lock->semaphore);
	thread_current()->wait_on_lock = NULL;
	lock->holder = thread_current();
}

donate_priority

void donate_priority(void)
{
	struct thread *a = thread_current();
	struct thread *b;
	int depth = 0;
	while (depth < 8)
	{
		if (a->wait_on_lock == NULL)
			break;
		b = a->wait_on_lock->holder;
		if (&a->priority > &b->priority)
			b->priority = a->priority;
		else
			break;
		a = b;
		depth++;
	}
	/* priority donation을 수행하는 함수를 구현한다.
현재 스레드가 기다리고 있는 lock 과 연결된 모든 스레드들을 순회하며
현재 스레드의 우선순위를 lock을 보유하고 있는 스레드에게 기부한다.
(Nested donation 그림 참고, nested depth는 8로 제한한다.
*/
}