WIL - PintOS:Project1 / Priority Scheduling

⚽️ Main Goal

❗ FIFO Scheduling으로 구현되어 있는 PintOS를 Priority Scheduling으로 개선하기.

• Ready List의 스레드를 우선순위에 따라 정렬하기
• 동기화를 위해 사용하는 Wait List를 우선순위에 따라 정렬
• 선점 (Preemption), 스레드가 Ready List로 들어갈 때 선점을 고려한다.

크게 현재 OS 구동방식에서 우선 순위를 추가한 후, 우선 순위 양도 (Nested, Multiple)을 구현하는 순서로 진행했다.

📈 구현하기

⚙️ FIFO Scheduling → Priority Scheduling

이번 과제에 있어서 스레드에 한해서 새로운 데이터가 추가되기 떄문에 thread struct를 수정해야한다.

// thread.h
struct thread {
	...
	
	int original_priority;			/* 우선순위 양도에 의해 변경되지 않는 원본 우선순위 */
	int priority;               /* 우선순위 양도를 반영한 현재 우선순위 */
    struct lock *wait_on_lock;  /* 현재 스레드가 필요로 하는 Lock */
	struct list donations;			/* 스레드가 락을 가지고 있는 경우, 현재 스레드에 우선순위를 양도할 수 있는 스레드의 리스트 */

	...
}

static void init_thread (struct thread *t, const char *name, int priority) {
	...
	
	t->priority = priority; // 우선순위 초기화
	t->original_priority = priority; // 우선순위 원본 초기화
	t->wait_on_lock = NULL; // LOCK 관련 데이터 초기화
	list_init(&t -> donations); // donations list 초기화
}

스레드가 생성되었을 때, 아래의 thread_create 함수를 따라 실행된다.

// thread.c
tid_t thread_create (const char *name, int priority, thread_func *function, void *aux) {
	
	...

	/* Add to run queue. */
	thread_unblock (t);

	/* Compare the priorites of the currently running thread and the newly instered one.
	*  Yield the CPU if the newly arriving thtead has higher priority */
	check_preemption();

	return tid;
}

thread_create 함수 내에서 스레드가 생성되고 thread_unblock에서 ready_list에 삽입된다. 이번 과제의 목표 중 하나인 선점을 구현하기 위해서 대기 상태에 스레드가 들어간 뒤에, 현재 스레드와의 우선순위를 비교하고, 우선순위에 따른 Running Thread를 지정하는 과정이 필요하다.

void check_preemption (void) {
	struct list_elem *begin = list_begin(&ready_list);
	struct thread *t = list_entry(begin, struct thread, elem);

	if ( !list_empty(&ready_list) && thread_current() -> priority < t -> priority )
		thread_yield();
}

check_preemption()에서 ready_list를 확인하고, 현재 스레드의 우선순위와 비교해서 높은 우선순위의 스레드가 실행되도록 해준다.

선점 여부를 판단하기 이전에 스레드가 Ready List로 삽입된다고 했다.

그 때, 삽입할 때도 정렬된 상태로 삽입되어아 이후 check_preemption에서 가장 우선순위가 높은 맨 앞의 스레드와 우선순위를 비교할 수 있게 된다.

// thread.c
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, compare_priority, NULL);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

삽입 및 정렬은 list_insert_ordered에서 발생하는데 이때, 비교 연산 함수를 인자로 넘겨줘야하는데, 그 함수 내부에서 어떤 데이터를 정렬 기준으로 사용할지 명시할 수 있다.

// thread.c
bool compare_priority(const struct list_elem *a, const struct list_elem *b, void *aux) {

	struct thread *a_thread = list_entry(a, struct thread, elem);
	struct thread *b_thread = list_entry(b, struct thread, elem);

	return a_thread -> priority > b_thread -> priority;
}

compare_priority내부에서 각 스레드에 대해서 priority를 사용하여 정렬을 구현해주었다.

우선 순위를 임의로 변경하는 경우에 대해서도 처리를 해주어야하는데, 우선순위 변경은 현재 스레드를 기준으로 적용되기 때문에, 변경 후 앞서 했었던 preemption 과정을 반복해서 선점이 발생하는 경우가 있는지 확인해야한다.

// thread.c
void thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;

	check_preemption();
}

⚙️ waiters 정렬

이제 semaphore 내부에서 관리하는 waiters들을 정렬해야한다.

그 전에 동기화를 위해 사용하는 conditon과 lock, semaphore이 어떤 구조로 되어있느지 알아야한다. ( 물론 개념도… )

// synch.h
struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

struct condition {
	struct list waiters;        /* List of waiting threads. */
};

언뜻 보기에 semaphore의 waiters와 condition의 waiters이 어떤 타입의 원소들을 가지는지 알기 어렵다. 그래서 아래와 같이 사용되는 상황을 확인하여 어떤 식으로 구조를 가지고 있는지 확인하는 작업이 필요하다.

sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);

먼저 condition의 waiters로 부터 요소를 하나 앞에서 빼는 과정이 포함된 코드이다. 이때 리스트 요소 구조체(elem)에서 리스트 데이터 구조체로 변환하는 함수인 list_entry()의 인자로 semaphore_elem을 사용하고 있다. 이를 통해서 conditon 구조체의 waiters는 semaphore struct 임을 알 수 있다.

thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));

마찬가지 semaphore struct의 waiters에서는 list_elem을 활용해서 실제 데이터로 변환하고 있기 때문에, semaphore의 waiters에는 스레드들이 들어있다고 생각할 수 있었다.

그래서 이후 cond_wait, cont_signa에서는 semphore_elem요소에 대한 정렬을 해야하고, sema_down, sema_up에서는 list_elem에 대한 정렬을 수행하면 된다.

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, compare_priority, NULL); // priority-preempt
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

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

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters)){
		list_sort(&sema->waiters, compare_priority, NULL); 
		thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
	}
	
	sema->value++;
	check_preemption();

	intr_set_level (old_level);
}

기존 우선순위를 판별하는 함수에서는 list_entry에 대한 우선순위 비교 로직이기 때문에 semaphore_elem에 대한 비교 로직을 새로 만들어야한다.

elem을 인자로 받아서 기존의 로직을 최대한 활용하는 방향으로도 생각해봤지만 중간 과정을 거쳐야하는 struct의 차이가 많아서 새롭게 로직을 작성하는 방향으로 진행했다.

bool semaphore_elem_less(struct list_elem *a, struct list_elem *b, void *aux) {
    struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

		struct list_elem *la = list_begin(&(sa->semaphore.waiters));
		struct list_elem *lb = list_begin(&(sb->semaphore.waiters));

		struct thread *a_thread = list_entry(la, struct thread, elem);
		struct thread *b_thread = list_entry(lb, struct thread, elem);

		int priority_a = a_thread -> priority;
		int priority_b = b_thread-> priority;

		return priority_a > priority_b;
}

void cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_insert_ordered(&cond->waiters, &waiter.elem , &semaphore_elem_less, NULL); // priority-condvar

	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters)) {
    list_sort (&cond->waiters, &semaphore_elem_less, NULL); // priority-condvar, sema_up 하기 전에 priority donation이 발생할 수 있기 때문에 정렬로 우선순위에 따른 정렬
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}
}

지금까지 수정한 부분에 대해서 테스트를 돌리면 donation이 포함되지 않은 priority_* 테스트를 통과할 수 있다.

⚙️ Lock (Acquire, Release, Priority Donation)

앞서 구현한 우선순위 스케줄링에서 Lock에 대한 구현을 추가하면 해당 미션을 마무리할 수 있다.

크게 Lock Acquire, Lock Relase를 구현하는 것이고, 그에 따른 우선 순위 양도( Priority Donation )의 여러 형태( Multiple, Nested )를 고려하여 각 스레드가 적절한 우선순위를 가질 수 있도록 구현해야한다.

먼저 Lock Acquire를 살펴보면 ,

현재 필요한 리소스에 대한 Lock을 차지할 수 있는지에 따라 처리를 다르게 해야한다.

Lock을 차지할 있는 경우 해당 Lock의 Holder를 해당 스레드로 지정해주면 된다.

lock -> holder = t; //  해당 락의 홀더에 스레드 할당

하지만 그렇지 않은 경우,

• 스레드는 해당 Lock을 대기하고 있어야한다.
• Lock의 대기열에 해당 스레드가 포함되어야한다.
• Lock을 가지고 있는 스레드는 새로운 대기 스레드에 의해 우선순위를 다시 계산해야한다.

holder = lock -> holder;
t -> wait_on_lock = lock; // 대기할 Lock을 할당
list_insert_ordered( &(holder -> donations), &t -> d_elem, compare_priority, NULL ); // 스레드와 연관있는 doantions을 우선순위 순으로 정렬
holder -> priority = get_donation_priority(holder); // lock의 Holder가 가장 높은 우선순위를 양도 받아 스레드에 저장
donate_nested_priority (holder);

그리고 스레드가 우선순위 양도를 계산하여 새로운 우선순위를 받았을 수도 있다.

그 우선순위가 현재 실행중인 스레드의 우선순위에도 영향을 줄 수 있기 떄문에 현재 스레드에 대한 우선순위 계산을 다시 한 번 해준다.

위 구현 단계를 종합하면 아래와 같은 lock_acquire 함수를 만들 수 있다.

// synch.c
void lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	struct thread *holder;
	struct thread *t = thread_current(); // 현재 스레드

	if ( lock -> holder == NULL ) { // 현재 Lock이 없다면 
		lock -> holder = t; //  해당 락의 홀더에 스레드 할당
	}
	else {
		holder = lock -> holder;
		t -> wait_on_lock = lock; // 대기할 Lock을 할당
		list_insert_ordered( &(holder -> donations), &t -> d_elem, compare_priority, NULL ); // 스레드와 연관있는 doantions을 우선순위 순으로 정렬
		holder -> priority = get_donation_priority(holder); // lock의 Holder가 가장 높은 우선순위를 양도 받아 스레드에 저장
		donate_nested_priority (holder);
	}

	t -> priority = get_donation_priority(t); // 현재 스레드의 우선순위 갱신
	donate_nested_priority (t);

	sema_down (&lock->semaphore);
	lock->holder = thread_current();
	t -> wait_on_lock = NULL;

	// sema_down은 해당 락이 사용가능할 때까지 스레드를 대기 상태로 만든다.
	// 그래서 sema_down 이후 코드에 대해서는 해당 스레드가 락을 소유한 상태로 간주해도 되기 때문에
	// sema_down 이후에 한번더 명시적으로 lock을 설정해야한다.
}

sema_down 이후 존재하는 두 줄의 함수는 sema_down의 동작 이후에 lock_holder를 분명하게 명시하기 위해서 다시 한번 할당을 해준다.

Lock Release의 경우 Acquire와 반대로 Lock Holder가 Lock을 놓으면서 발생하는 과정을 단계적으로 구현하면 된다.

Lock Holder를 먼저 해제해주면 혹여나 Holder Thread를 참조하는 것에 있어서 문제가 발생할 수 도 있어 가장 마지막에 Lock Holder를 해제해주었다.

Lock을 해제하는 것은 현재 Lock을 기다리고 있던 스레드들이 더 이상 우선순위를 양도하지 않기 때문에 스레드의 donation 리스트에서 먼저 Lock과 관련있는 스레드를 모두 제거한다.

for (struct list_elem *e = list_begin (&(t -> donations)); e != list_end (&(t -> donations)); e = list_next(e)) {

		struct thread *nt = list_entry (e, struct thread, d_elem);

		if ( nt -> wait_on_lock == lock ) {
			list_remove(e); // lock과 관련된 donation thread를 donation list에서 제거
		}
	}

그 후, 해당 스레드의 donation 변경으로 인해서 새로운 우선순위 계산이 필요하다.

list_sort(&(t->donations), compare_priority, NULL);
t -> priority = get_donation_priority(t); // 기존 Lock Holder에게 새로운 우선 순위 양도
donate_nested_priority (t);

위 과정을 종합하면 다음과 같은 lock_release 함수를 구현할 수 있다.

// synch.c
void lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	struct thread *t = lock -> holder;

// holder의 donation에서 M을 빼내기
	for (struct list_elem *e = list_begin (&(t -> donations)); e != list_end (&(t -> donations)); e = list_next(e)) {

		struct thread *nt = list_entry (e, struct thread, d_elem);

		if ( nt -> wait_on_lock == lock ) {
			list_remove(e); // lock과 관련된 donation thread를 donation list에서 제거
		}
	}

	list_sort(&(t->donations), compare_priority, NULL);

	t -> priority = get_donation_priority(t); // 기존 Lock Holder에게 새로운 우선 순위 양도
	donate_nested_priority (t);

	lock->holder = NULL;
	sema_up (&lock->semaphore); // 수정 전에 semaphore value 수정
}

Lock에 대한 우선순위 양도를 구현할 때 두가지 Lock 구조 형태를 고려해야한다.

📊 Multiple

우선 위 그림처럼 T1이라는 스레드가 여러개의 Lock을 가지고 있는 경우 해당 Lock을 필요로하는 스레드들로 부터 우선순위를 양도받아야한다.

그 스레드들은 T1의 donations에 존재하며 donations를 순회하면서 가장 큰 우선순위를 찾아 양도해주면된다.

이때 Donation 리스트 자체가 삽입 단계에서부터 list_insert_ordered 함수를 활용해 정렬하며 삽입하고 있는 경우, 맨 앞의 스레드가 가장 우선순위가 높은 스레드임을 보장할 수 있기 때문에 그 때는 가장 앞의 스레드의 우선순위를 받으면 된다.

/* 우선순위 양도를 고려하여 가장 높은 우선순위를 return */
int get_donation_priority(struct thread *t) {
	// struct list_elem *e = list_max(t -> donations, check_priority, NULL);
	// struct thread *dpt = list_entry(e, struct thread, elem);

	// return dpt -> priority;

	if (list_empty(&(t -> donations)))  {
		return t -> original_priority;
	}// donation이 비어있을 경우에 대한 방어 코드

	
	struct list_elem *e = list_front(&(t -> donations)); // 도네이션의 첫번째 요소 get
	struct thread *dt = list_entry(e, struct thread, d_elem); // elem을 통해서 스레드 생성

	return t -> original_priority < dt -> priority ? dt -> priority : t -> original_priority; // 우선순위 원본과 donations의 최대 우선순위를 비교해서 할당
}

⛓️ Nested

여러 스레드가 연쇄적으로 리소스를 필요로하는 경우 위와 같은 그림으로 표현할 수 있다. 이때도 우선순위 양도가 발생하는데 이때 스레드가 필요로하는 Lock의 Holder에게 우선순위를 전달하기 위해서는 wait_on_lock에 저장되어 있는 lock 포인터의 holder를 참조해야한다.

wait_on_lock을 반복해서 참조하며 다른 Lock을 필요로하지 않는 스레드가 나올때 까지 순회하며 우선순위를 양도한다.

void donate_nested_priority(struct thread *t) {
	struct thread *nt;
	// struct thread *t = thread_current;
	int root_priority = t -> original_priority;

	while ( t -> wait_on_lock != NULL ) {
		nt = t -> wait_on_lock -> holder;

		if ( nt -> priority < root_priority ) {
			nt -> priority = root_priority;
		}

		t = nt;
	}
}

마지막으로, thread_set_priority 함수를 통해 임의로 우선순위가 변경되었을때 위 두 우선순위 양도 로직을 활용해서 기존 스레드들의 우선순위를 변경해주어야 한다.

void thread_set_priority (int new_priority) {
	struct thread *t = thread_current();

	t -> original_priority = new_priority; // 스레드의 원래 우선순위를 갱신
	t -> priority = get_donation_priority(t); // 우선순위 양도를 고려한 우선 순위 갱신

	donate_nested_priority (t);

	check_preemption();
}

🎉 결과