[PintOS project] 1. Part 1: Threds - Priority Donation

@developer/takealittle.time·2024년 11월 10일
KAISTjunglekraftonpintos
0

KAIST PintOS Project

목록 보기
4/9

이전 글

00. Priority Inversion

  • 지난 시간까지 구현을 통해, 각 스레드들이 priority라는 속성을 기준으로 스케줄링 되게끔 pintOS를 작성했다.

  • 이 과정 속에서 semaphore, lock, condition variable도 각각의 동기화 도구들을 기다리고 있는 waiters 리스트 안에서 스레드들이 우선 순위를 기준으로 내림차순 정렬되게끔 구현했다.

  • 그런데, 이렇게 우선 순위를 기준으로 스케줄링을 하게 되면 다음과 같은 문제가 발생한다.

  1. H, M, L 이라는 세 개의 스레드가 존재한다.
    각 스레드의 우선 순위는 H>M>L 순이다.
    스레드 H와 L은 lock을 이용하는 스레드이다.

  2. 우선순위가 가장 낮은 Thread L이 먼저 도착해 실행 중이다.
    L은 lock을 acquire() 해서 가져간다.

  3. 아직 Thread L이 수행 중일 때, 우선순위가 가장 높은 Thread H가 도착한다.

  4. 우선순위는 H가 가장 높지만, 현재 lock을 L이 가지고 있는 상태이기 때문에, H는 대기하게 되고, L이 계속해서 실행된다.

  5. 이 때, M이 도착했다. 우선순위가 L보다 M이 높고, M은 lock을 필요로 하지도 않기 때문에 선점 된다.

  6. thread H는 앞의 thread M, thread L의 동작이 다 끝나고나서야 수행될 수 있다.
    우선 순위가 가장 높은데도 말이다!
    이러한 경우를 priority inversion(우선순위 역전) 이라고 한다.

01. Priority Donation

  • 그렇다면, 위의 문제를 어떻게 해결할 수 있을까?
    위의 예시와 같은 상황을 다시 한 번 생각해보자.

  1. 이전 예시와 같이, H, M, L 이라는 세 개의 스레드가 있다.
    우선순위도 역시나 H>M>L 순이다.

  2. 이번에도 스레드 L이 먼저 도착했고, 실행 중이다. lock을 먼저 가져갔다.

  3. Thread L이 아직 수행 중인 상태에서 Thread H가 도착했다.
    Thread H는 lock을 필요로 하는데, 이미 lock은 Thread L이 가져갔기 때문에 우선 순위가 높은데도 불구하고 선점이 불가능하다.
    이 때, Thread L에게 Thread H가 자신의 우선순위를 빌려준다.
    Thread L의 우선순위가 잠시 동안 Thread H의 우선순위로 바뀌는 것이다. → 이를 Priority Donation이라고 한다.

  4. 이렇게 되면, 이 다음에 Thread M이 도착하여도 Thread L의 우선 순위가 Thread M보다 높기 때문에 선점이 불가능 하다.

  5. 또, Thread L의 동작이 끝났을 때 Thread H가 ready_list로 돌아오면서 선점된다.

  6. 이렇게, Priority Donation을 이용하면 높은 우선순위의 스레드가 lock 때문에 다른 스레드들까지 기다려야 할 필요가 없어진다.

이러한 Priority Donation 개념을 이용하기 위해서는 몇 가지 케이스에 대한 이해가 필요하다.

01-1. 한 lock에 대해서 여러 개의 스레드가 대기 중일 때

  • 해당 lock을 사용하기 위해 대기 중인 (waiters 리스트에 있는) 스레드들 중 가장 높은 우선 순위를 가진 스레드에게서 priority를 빌려오도록 해야한다.

01-2. Nested Donation (중첩 Donation)

  • 위와 같이 하나의 lock을 기다리는 중에 현재 실행 중인 스레드보다 더 높은 우선순위를 가진 스레드가 waiters 리스트에 들어오면, 해당 스레드의 우선순위를 앞으로 전달하는 형식으로 Priority Donation을 수행한다.

01-3. Multiple Donation (다중 Donation)

  • 위와 같이 하나의 스레드가 여러 개의 lock을 가져갈 수도 있다.

  • 이러한 경우, 우선 갖고 있는 lock의 가장 우선순위가 높은 대기자의 우선순위를 빌리게 된다.

  • 단, 해당 lock을 반환했을 때는 다른 lock의 그 다음으로 우선순위가 높은 대기자의 우선순위를 빌리게 된다.

02. 구현

  • 비교적 간단했던 이전 Priority Scheduling에 비해, Donation의 기능 구현은 조금 복잡했다.

02-1. thread 구조체 수정

  • slide에 나와있는, donation을 구현한 스레드의 구조는 위와 같이 생겼다.

  • 이를 구현하기 위해서는 우선 thread 구조체에 다음과 같은 속성들을 만들어주어야 한다.

/* threads/thread.h */
struct thread
{
	...
    // donation 받기 전 스레드의 원래 priority
    int init_priority;
    // 해당 스레드가 대기 중인 lock의 포인터
    struct lock *wait_on_lock;
    // donations 리스트
    struct list donations;
    // donations 리스트의 요소
    struct list_elem d_elem;
    ...
}

02-2. init_thread() 수정

  • thread의 구조체에 새로운 속성을 추가했으므로, init_thread()에도 이러한 속성들을 초기화 해주는 내용을 추가해야 할 것이다.
static void
init_thread (struct thread *t, const char *name, int priority) {
	...
	
	// donation 구현을 위해 아래 코드들 추가
	t->init_priority = priority;
	t->wait_on_lock = NULL;
	list_init(&t->donations);
	
    ...

}
  • 앞으로도 사용하는 구조체의 속성을 수정하게 된다면, 그에 해당하는 초기화 함수에도 이러한 속성에 대한 초기화를 추가하는 내용을 꼭 추가하는 습관을 들이자.

* 참고 :: thread_init() 과 init_thread()의 차이

  • thread_init() : 모든 스레드들이 공유하는 변수들에 대해 초기화
    Init the global thread context.
  • init_thread() : 하나의 스레드에 대해 변수들 초기화.
    Does basic initialization of T as a blocked thread named
    NAME.

  • ~/threads/init.c 파일을 열어보면 스레드의 생성과 준비 단계에 대해 더 쉽게 이해할 수 있다.

02-3. lock_acquire()와 lock_release()의 수정

  • 우선, 수정 전의 lock_acquire()와 lock_release()를 살펴보자. 
void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));
    
    // 이 부분에 '① 이미 lock의 주인이 있을 때'
    // ② donations 리스트에 삽입 (우선순위 기준)
    // ③ priority donation 수행

	sema_down (&lock->semaphore);
	lock->holder = thread_current ();
}

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

	lock->holder = NULL;
    
    // 이 부분에 ① 해당 lock을 대기 중이던 스레드들 대기 해제
    // ② donations 리스트에 남은 lock을 기준으로 현재 스레드에 다시 donate.
	
    sema_up (&lock->semaphore);
}

  • 우리가 작성해야 할 코드들은 주석으로 작성해 놓은 것과 동일하다.

  • 아래와 같이 수정해주면 된다.

/* threads/synch.c */

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

	struct thread *curr = thread_current();
	// 이미 holder가 있는 경우 (사용 중인 경우)
	if (lock->holder){
		curr->wait_on_lock = lock;
		// 우선순위를 기준으로 donation 리스트에 삽입.
		list_insert_ordered(&lock->holder->donations, &curr->d_elem, cmp_delem_priority, NULL);
		// donation 실행
		do_donate();
	}
	// holder가 없는 경우 (lock의 주인이 되는 경우)
	sema_down (&lock->semaphore);
	// 현재 스레드의 wait_on_lock을 명시적으로 NULL로 변경
	curr->wait_on_lock = NULL;
	lock->holder = curr;
}

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));
	
	// 해당 lock의 holder를 NULL로 설정
	lock->holder = NULL;
	// 해당 lock을 기다리던 스레드들을 donations 리스트에서 해제
	remove_with_lock(lock);
	// donations 리스트에 남은 리스트로 다시 donate
	re_dona_priority();
	// lock 해제
	sema_up (&lock->semaphore);
}
  • 위에서 사용된 새로운 함수들은 다음과 같다.
/* threads/thread.c */
// donations 리스트의 정렬을 위한 비교 함수
bool
cmp_delem_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
	return list_entry(a, struct thread, d_elem)->priority > list_entry(b, struct thread, d_elem)->priority;
}
/* threads/thread.c */
// donations 리스트에서 현재 스레드의 wait_on_lock->holder 타고 올라가면서 우선순위 donate.

void
do_donate()
{
	int depth;
	struct thread *curr = thread_current();

	for (depth = 0; depth < 8; depth++){
		if (!curr -> wait_on_lock)
			break;
		struct thread * holder = curr -> wait_on_lock->holder;
		// holder의 priority를 현재 스레드의 priority로 수정
		holder->priority = curr->priority;
		curr = holder;
	}
}
/* threads/thread.c */

void
remove_with_lock (struct lock *lock)
{
	struct list_elem *e = NULL;
	// 현재 실행 중 스레드 가져오기
	struct thread* curr = thread_current();
	
	// 해당 lock을 요구하는 스레드들 모두 donation에서 풀어줌
	for (e = list_begin (&curr->donations); e!= list_end (&curr->donations); e = list_next(e)){
		struct thread *t = list_entry(e, struct thread, d_elem);
		if (t->wait_on_lock == lock)
			list_remove(&t->d_elem);
	}
}
  • 이렇게 구현해 준 함수들은 항상 헤더 파일에 프로토 타입으로 작성 해 놓아야 한다.
/* threads/thread.h */
bool cmp_delem_priority(const struct list_elem *, const struct list_elem *, void *);
void do_donate();
void remove_with_rock (struct lock *);
void re_dona_priority();

03. 실행 결과

  • mlfqs의 구현 이전에 7개의 테스트 케이스만이 남았다.

04. Trouble Shooting

  • Priority Donation 기능을 구현해주면, 사실상 스레드의 priority 값은 donation 상황에 따라 변할 것이다.
    따라서 ,thread_set_priority() 함수의 원래 목적을 생각하면, 우리는 이제 스레드의 priority 값이 아니라 init_priority 값을 수정해주어야 한다.
/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {

	struct thread *curr = thread_current();
	// thread의 init_priority를 수정하도록 함
	curr->init_priority = new_priority;
	// donation 정보를 바탕으로 priority 재설정
	re_dona_priority();
	// 우선순위를 기준으로 ready_list의 가장 앞 스레드로 선점
	schedule_by_priority();
}

  • 또한, thread_set_priority() 함수를 통해 init_priority()를 수정해주고 나서 어떤 동작이 필요한지 생각 해 볼 필요가 있다.

    • 우선, 현재 실행 중인 스레드의 init_priority가 낮아졌을 때를 생각해보면, donations 리스트 안에 있는 스레드들과 다시 한 번 비교하면서 donation을 다시 해 줄 필요가 있다.

    • donation을 다시 해 준 뒤, 스레드의 우선 순위를 기준으로 다시 선점해 줄 필요가 있다.

  • 당연한 얘기이지만, 위 동작의 순서를 바꾸면 안된다.

  • 필자는 위와 같은 내용들에 대해 생각을 짧게 해서 몇 시간을 날렸다..

참고 자료 / 이미지 출처

profile
@developer/takealittle.time
능동적으로 사고하고, 성장하기 위한. 🌱
이전 포스트

[PintOS project] 1. Part 1: Threds - Priority Scheduling

다음 포스트

[PintOS project] 1. Part 1: Threds - 4.4 BSD like scheduler

0개의 댓글

관련 채용 정보