[Pintos-KAIST] Project 1 : Priority Donation

👩🏻‍💻 GITHUB 레포지토리
👩🏻‍💻 GITHUB Priority Donation 이슈

과제 설명

Priority Inverstion Problem은 thread가 두 개 이상의 lock보유가능할 때, 높은 priority의 thread가 낮은 priority의 thread보다 늦게 실행될 수 있는 문제점을 말한다.

✔️ 자세한 Priority Inversion Problem 설명 확인하기

• 유튜브 영상 참고하기
  🖥️ CS450: Priority Donation 1 (Pintos Project)
  🖥️ CS450: Priority Donation 2 (Pintos Project)
  🖥️ CS450: Priority Donation 3 (Pintos Project)

Priority Inverstion

간단하게 설명하자면,

H (high), M (medium), L (low) 라는 세 개의 스레드가 있고 각각의 우선순위는 H > M > L 이다. H 가 L 을 기다려야 하는 상황(예를 들어, H 가 lock 을 요청했는데 이 lock 을 L 이 점유하고 있는 경우)이 생긴다면 H 가 L 에게 CPU 점유를 넘겨주면 M 이 L 보다 우선순위가 높으므로 점유권을 선점하여 실행되어서 스레드가 마무리 되는 순서가 M->L->H 가 된다. 따라서 M 이 더 높은 우선순위를 가진 H 보다 우선하여 실행되는 문제가 발생한다.

구현 목표

priority donation

이를 해결하기 위해 priority donation을 구현하여야 한다.

priority donation 이란 위의 상황에서 H 가 자신이 가진 priority 를 L 에게 일시적으로 양도하여서 H 자신의 실행을 위해 L 이 자신과 동일한 우선순위를 가져서 우선적으로 실행될 수 있도록 만드는 방법이다.

핀토스 documents 에서는 priority donation 이 일어난 수 있는 모든 상황을 고려해야 한다고 하면서 Multiple donation, Nested donation 두 가지를 언급한다.

1. Multiple donation

• lock을 여러 개 점유한 스레드는 lock을 요청한 스레드의 priority 중 가장 높은 priority로 갱신한다.
• lock을 반환할 경우에는, 반환한 lock을 획득한 스레드를 제외한 lock을 요청한 스레드들의 priority 중에서 가장 높은 priority로 갱신한다.

2. Nested donation

• Donation은 재귀적으로 이어진다.
  • T1이 점유한 lockA를 T2가 요청하면 (T2가 더 높을 경우) T2의 priority로 갱신한다.
  • 위 상황에서, T2가 점유한 lockB를 T3이 요청하면 (T3이 더 높을 경우) T1과 T2를 T3의 priority로 갱신한다.

수정 함수 및 자료구조

• void lock_acquire (struct lock *lock) : lock을 점유하고 있는 스레드와 요청 하는 스레드의 우선순위를 비교하여 priority donation을 수행하도록 수정
• void lock_release (struct lock *lock) : donation list 에서 스레드를 제거하고 우선순위를 다시 계산하도록 remove_with_lock(), refresh_prioriy() 함수를 호출
• void thread_set_priority (int new_priority) : 스레드 우선순위 변경시 donation의 발생을 확인 하고 우선순위 변경을 위해 donation_priority()함수 추가
• struct thread

추가 함수

• void donate_priority(void) : priority donation을 수행
• void remove_with_lock(struct lock *lock) : donation list에서 스레드 엔트리를 제거
• void refresh_priority(void) : 우선순위를 다시 계산

사전 환경 설정

동작 순서 중 Source ./activate 안치게 하는법!!

1. 루트 디렉토리로 이동

2. code .bashrc 입력
   

3. 파일 제일 밑에 본인의 source activate 경로 추가

테스트 방법

1. /pintos 경로에서 source ./activate (사전 환경 설정을 했다면 안해줘도 된다!)

2. threads 폴더 들어가서 make clean make check를 수행하면 Test Case들에 대해서 채점을 수행한다.

3. Test Case 한가지만 돌리고 싶다면, pintos/(프로젝트명)/build에 들어가서 아래 명령어를 수행하면 된다.
   pintos -T (Timout이 걸리는 시간) -- -q -run (Test case 이름)
   ex) `pintos -T 30 -- -q run donate-one

구현

struct thread에 prioriry donation관련 항목 추가

• include/threads/thread.h

  • donation 이후 우선순위를 초기화하기 위해 초기 우선순위 값을 저장할 필드
  • 해당 쓰레드가 대기하고 있는 lock 자료구조의 주소를 저장할 필드
  • multiple donation을 고려하기 위한 리스트 추가
    • 해당 리스트를 위한 elem도 추가

.
.
.
	/** project1-Priority Inversion Problem */
	int original_priority;
    struct lock *wait_lock;
    struct list donations;
    struct list_elem donation_elem;
.
.
.

init_thread() 함수 수정

• threads/thread.c

  Priority donation 관련 자료구조 초기화 코드 삽입

static void
init_thread (struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);

	/** project1-Priority Inversion Problem */
    t->priority = t->original_priority = priority;
    list_init(&t->donations);
    t->wait_lock = NULL;

	t->magic = THREAD_MAGIC;
}

lock_acquire() 함수 수정

• threads/synch.c

  • 해당 lock의 holder가 존재하여 wait을 하게 되면 아래 동작을 수행.
    • wait을 하게 될 lock 자료구조 포인터 저장
      • 쓰레드 디스크립터에 추가한 필드
    • lock의 현재 holder의 대기자 list에 추가
    • priority donation을 수행하는 코드 추가
      • 구현하게 될 함수인 donate_priority()
    • lock 획득 후 lock의 holder 갱신

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

   /** project1-Priority Inversion Problem */
   struct thread *t = thread_current();
    if (lock->holder != NULL) {
        t->wait_lock = lock;
        list_push_back(&lock->holder->donations, &t->donation_elem);
        donate_priority();
    }

	sema_down (&lock->semaphore);

   /** project1-Priority Inversion Problem */
   t->wait_lock = NULL;
   lock->holder = t;
}

구현할 함수 선언

• include/threads/thread.h

.
.
.
/** project1-Priority Inversion Problem */
void donate_priority(void);
void remove_with_lock(struct lock *lock);
void refresh_priority(void);
.
.
.

donate_priority() 함수 추가

• threads/thread.c

  • void donate_priority(void)
  • priority donation을 수행하는 함수
  • Nested donation을 고려하여 구현
    • 현재 쓰레드가 기다리고 있는 lock과 연결된 모든 쓰레드들을 순회하며 현
      재 쓰레드의 우선순위를 lock을 보유하고 있는 쓰레드에게 기부
    • nested depth는 8로 제한

/** project1-Priority Inversion Problem */
void 
donate_priority() 
{
    struct thread *t = thread_current();
    int priority = t->priority;

    for (int depth = 0; depth < 8; depth++) 
	{
        if (t->wait_lock == NULL)
            break;

        t = t->wait_lock->holder;
        t->priority = priority;
    }
}

lock_release() 함수 수정

• threads/synch.c

  • lock을 해제한 후, 현재 쓰레드의 대기 리스트 갱신 (remove_with_lock() 사용)
  • priority를 donation 받았을 수 있으므로 원래의 priorit로 초기화 (refresh_priority() 사용)

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

	lock->holder = NULL;

   /** project1-Priority Inversion Problem */
   remove_with_lock(lock);
   refresh_priority();

	sema_up (&lock->semaphore);
}

remove_with_lock() 함수 추가

• threads/thread.c

  • lock을 해지 했을 때, waiters 리스트에서 해당 엔트리를 삭제 하기 위한 함수를 구현
  • 현재 쓰레드의 waiters 리스트를 확인하여 해지할 lock을 보유하고 있는 엔트리를 삭제

/** project1-Priority Inversion Problem */
void remove_with_lock(struct lock *lock) 
{
    struct thread *t = thread_current();
    struct list_elem *curr = list_begin(&t->donations);
    struct thread *curr_thread = NULL;

    while (curr != list_end(&t->donations)) 
	{
        curr_thread = list_entry(curr, struct thread, donation_elem);

        if (curr_thread->wait_lock == lock)
            list_remove(&curr_thread->donation_elem);

        curr = list_next(curr);
    }
}

refresh_priority() 함수 추가

• threads/thread.c

  • 스레드의 우선순위가 변경 되었을 때, donation을 고려하여 우선순위를 다시 결정하는 함수
  • 현재 쓰레드의 우선순위를 기부 받기 전의 우선순위로 변경
  • 현재 쓰레드의 waiters 리스트에서 가장 높은 우선순위를 현재 쓰레드의 우선순위와 비교 후 우선순위 설정

/** project1-Priority Inversion Problem */
void refresh_priority(void) 
{
    struct thread *t = thread_current();
    t->priority = t->original_priority;

    if (list_empty(&t->donations))
        return;

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

    struct list_elem *max_elem = list_front(&t->donations);
    struct thread *max_thread = list_entry(max_elem, struct thread, donation_elem);

    if (t->priority < max_thread->priority)
        t->priority = max_thread->priority;
}

thread_set_priority() 함수 수정

• threads/thread.c

• refresh_priority() 함수를 사용하여 우선순위의 변경으로 인한 donation 관련
  정보를 갱신
• donation_priority(), test_max_priority() 함수를 적절히 사용하여 priority
  donation을 수행하고 스케줄링

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

	/** project1-Priority Inversion Problem */
    thread_current()->original_priority = new_priority;

	/** project1-Priority Inversion Problem */
    refresh_priority();

	/** project1-Priority Scheduling */
	test_max_priority();
}

테스트 결과

통과되어야하는 테스트

• donate-one
• donate-multiple
• donate-multiple2
• donate-nest
• donate-sema
• donate-lower

참고

• [PintOS, Project1] Priority Inversion Problem
• [Pintos] Project 1 : Thread(스레드) - Priority Inversion(donation)