[TIL][Project 1] Priority Donation

Implement priority scheduling and priority donation in Pintos.

실행 중인 스레드보다 우선순위가 높은 스레드가 ready list에 추가될 때 어떻게 해야 하는가?

Donation ? | Priority Inversion 

높은 우선순위를 가진 H가, 낮은 우선순위의 L이 가진 공유 자원(lock, acquired)을 사용해야 하는데 하지 못하고 대기할 때 우선순위 반전 현상이 발생한다. 아래 도표에서처럼, H는 blocked되어 대기 상태로 존재한다. 그런데 H가 대기하고 있는데 중간 우선순위를 가진 H가 ready list에 있다면, H는 또다시 밀린다. 즉, H가 밀리는 '반전 현상' 이 발생한다. 

 

어떻게 해결할까? 높은 우선순위를 가진 스레드가 낮은 우선순위를 갖고 있는 스레드에게 priority를 기부한다. 그리고 기부받은 우선순위를 갖게 된 L이 순리대로(반전 없이) CPU를 점령하고 일을 전부 마쳤을 때 기부받은 우선순위와 CPU 할당권을 높은 우선순위를 가진 스레드에게 되돌려주는 원리이다. 

 

즉, 현재 낮은 우선순위를 가진 스레드가 lock을 소유하고 있을 때, 대기 상태에 놓인 스레드들 중 가장 높은 우선순위를 가진 스레드가 자신의 우선순위를 현재 lock을 소유하고 있는 스레드에게 기부하는데, 이 와중에 중첩 현상이 발생할 수 있다.

 

Priority Donation 

H가 lock을 요청하며 L의 priority를 H와 동일한 값으로 변경한다. 

L이 H의 우선순위를 이어받아 실행되고, 종료 후 H가 lock을 얻는다.(우선순위가 높으니까)

이때 H보다 우선순위가 낮은 M은 H가 종료된 뒤에야 lock을 얻는다.

 

Nested Donation 

PRI가 14인 Thread 4가 들어와서, lock C를 요청하는 상황이다.

그런데 Lock C의 소유자인 T3은 Lock B를 기다리고 있고,

T2는 Lock A를 소유하고 있는 T1의 작업이 끝나기를 기다리고 있다. 

 

이 경우, 가장 높은 우선순위를 가진 T4의 우선순위가 중첩하여 T1의 우선순위까지 변경한다. 왜냐하면 우선순위가 높은 것이 가장 먼저 처리되어야 하는 원칙이 지켜져야 하기 때문이다. T3의 우선순위가 7에서 14로 변경되면, T3이 기다리고 있는 T2의 우선순위도 변경되고, T2의 우선순위가 변경되면 T1의 우선순위까지 변경되어야, T1의 작업이 14의 순위로 끝났을 때 T4를 실행할 수 있게 된다.  

 

Multiple Donation

T1은 현재 lock을 세 개 쥐고 있다. T1의 우선순위는 이 Lock을 기다리는(각 Lock이 잠그고 있는 공유자원을 사용할) 스레드 중 가장 높은 우선순위를 지니고 있는 스레드의 우선순위로 변경된다. 

이후 Lock C가 풀리면, T1의 우선순위는 그 다음으로 높은 우선순위로 변경될 것이다. 

 

Priority Donation in PintOS

thread 구조체

• 기부받기 이전의 기존 priority를 저장할 필드 
• 스레드를 기다리고 있는 lock을 저장할 필드 
• priority를 기부해 준 스레드들을 연결 리스트로 저장하는 필드. 
• donation 의 연결 리스트를 사용하기 위한 elem. lock 요청은 한번에 한 스레드만 가능하다.

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */
	
	...

	/* Priority donation */
	int original_priority;				/* boost 이전의 priority */
	struct lock *waiting_lock;			/* 이 스레드가 사용을 기다리고 있는 락 */
	struct list donations;				
	struct list_elem donations_elem;
    
    ...
    }

 

lock_acuire | Donation 

waiting_lock은 현재 thread가 사용을 기다리고 있는 lock을 담는 필드이다. (synch.c)

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

   struct thread *cur = thread_current();

   if (lock->holder != NULL) {
      // put signal that this thread is waiting for the lock
      cur->waiting_lock = lock;

      // 현재 스레드를 lock holder의 donation list에 추가
      list_insert_ordered(&lock->holder->donations, &cur->donations_elem, donations_priority_more, NULL);
	 
     donate_priority(); //priority를 기부
   }

   sema_down (&lock->semaphore);
   cur->waiting_lock = NULL; // rm signal

   lock->holder = thread_current();
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */

 

nested한 donation의 깊이는 최다 8이므로, lock의 holder가 존재할 시 그 holder의 priority도 기부해준다. (thread.c)

void 
donate_priority(void) {
    struct thread *curr = thread_current(); 
    struct thread *holder;					

    int priority = curr->priority;

    for (int i = 0; i < 8; i++) {
        if (curr->waiting_lock == NULL) {
            return;
		}
        holder = curr->waiting_lock->holder;
        holder->priority = priority;
        curr = holder;
    }
}

 

inversion 용 donaton시 priority 정렬을 위한 함수 (synch.c)

/* inversion */
bool
donations_priority_more (const struct list_elem *a_, const struct list_elem *b_,
            void *aux UNUSED) { 
	struct thread *a = list_entry (a_, struct thread, donations_elem);
	struct thread *b = list_entry (b_, struct thread, donations_elem);

	return a->priority > b->priority;
}

 

lock_realease | back to original priority

lock 해제시 기부받은 priority를 원래대로 되돌리는 과정. 

//synch.c
/* Releases LOCK, which must be owned by the current thread.
   This is lock_release function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to release a lock within an interrupt
   handler. */
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));
   

     remove_with_lock(lock);
     refresh_priority();


   lock->holder = NULL;
   sema_up (&lock->semaphore);
}

remove_with_lock은 현재 스레드의 donation list를 순회하며 인자로 받은 현재 반환될 lock을 요청한 thread를 찾고, 제거한다.

refresh priority는 기본적으로 현제 스레드의 original priority로 priority를 바꿔준다. 그러나, donation 이 비어있지 않다면, multiple한 경우의 donation일 때에는 원래 priority로 변경하지 않고 그 다음으로 큰 priority로 바꾸어 준다. 말그대로 새로고침하는 함수이다.

// thread.c
void
remove_with_lock (struct lock *lock) {
   struct list_elem *curr_donation_elem = list_begin(&thread_current()->donations);

   while (curr_donation_elem != list_tail(&thread_current()->donations)) {
      struct thread *curr_donation_thread = list_entry(curr_donation_elem, struct thread, donations_elem);
      
      if (curr_donation_thread->waiting_lock == lock) {
         curr_donation_elem = list_remove(curr_donation_elem);
      }
      else {
         curr_donation_elem = list_next(curr_donation_elem);
      }
   }
}


void 
refresh_priority (void) {
	thread_current()->priority = thread_current()->original_priority;

	if (!list_empty(&thread_current()->donations)) {
		struct thread *front_thread = list_entry (list_begin(&thread_current()->donations), struct thread, donations_elem);
		if (thread_current()->priority < front_thread->priority) {
			thread_current()->priority = front_thread->priority;
		}
	}
}