[PintOS] 핀토스 뽀개기 - Threads 4 - Priority Inversion

잘못된 내용은 댓글 부탁드립니다.

---

목표

Pintos에서 스레드는 우선순위 기반으로 스케줄링됩니다. 그러나 실제 운영체제에서는 우선순위 역전(Priority Inversion)이라는 문제가 발생할 수 있으며, 이를 해결하지 않으면 높은 우선순위의 스레드가 실행되지 못하고 무기한 대기하는 문제가 생깁니다.

이번 단계에서는 이 문제를 해결하기 위해 우선순위 기부(Priority Donation) 메커니즘을 구현합니다.

• 낮은 우선순위의 스레드(L)가 락을 잡고 있다.
• 높은 우선순위의 스레드(H)가 해당 락을 기다리며 BLOCKED 상태가 된다.
• 그런데 중간 우선순위의 스레드(M)가 계속 CPU를 점유하면 H는 CPU를 받지 못하고 계속 대기하게 됨.
• 결국 우선순위 높은 H가 낮은 L에게 의존해 대기하는 구조 = 우선순위 역전!

→ 높은 우선순위를 가진 스레드가 락을 기다리면, 락을 점유 중인 스레드에게 우선순위를 일시적으로 기부합니다.

---

수정 파일

/include/threads/thread.h

/threads/thread.c

/threads/synch.c

---

구현

1. thread 구조체에 필드 추가

1 2 3 4 5

/* include/threads/thread.h */ int init_priority;                // 초기 우선순위 struct lock *wait_on_lock;        // 현재 기다리는 락 struct list donations;            // 기부받은 우선순위 리스트 struct list_elem donation_elem;   // donations 리스트에서의 위치

init_priority: Priority donation은 일시적입니다. 락을 해제하면 원래 priority로 돌아가야 하므로, 초기 우선순위를 보존해야 합니다.

wait_on_lock: 현재 스레드가 획득하려는 락을 추적합니다. 이를 통해 중첩 기부(chain donation)을 구현할 수 있습니다.

donations: 다른 스레드들이 현재 스레드에게 기부한 우선순위 정보를 관리하기 위한 리스트입니다. 여러 스레드가 동시에 기부할 수 있으므로 리스트가 필요합니다.

donation_elem: 기부 리스트에 삽입될 때 사용할 리스트 노드입니다. struct thread는 donations 리스트의 원소가 되므로 필요합니다.

 

2. donate_priority() 함수 구현

1 2 3 4 5 6 7 8 9 10 11 12 13

/* threads/thread.c */ void donate_priority(void) {     struct thread *curr = thread_current();     int depth = 0;       while (curr->wait_on_lock && depth < 9) {         depth++;         struct thread *holder = curr->wait_on_lock->holder;         if (holder->priority < curr->priority)             holder->priority = curr->priority;         curr = holder;     } }

쓰레드의 우선순위 기부를 구현합니다. 현재 스레드가 기다리는 락의 보유자에게 자신의 priority를 기부합니다. 이렇게 하면 락을 빨리 해제할 수 있으므로 우선순위 역전을 해소할 수 있습니다. 깊이가 8을 초과하지 않도록 제한한 이유는, 중첩된 락 대기가 과도하게 이어질 경우 시스템 응답성을 저하시킬 수 있고, 순환 대기를 방지하기 위함입니다. 이는 최악의 경우에도 일정 시간 내 priority 전파가 마무리되도록 보장합니다.

holder->priority < curr->priority 조건을 통해, 이미 높은 우선순위를 가진 holder에게는 불필요한 기부를 하지 않도록 방지합니다. 이는 우선순위가 역전되지 않은 상황에서 불필요한 덮어쓰기를 방지하여 시스템의 안정성을 높입니다

기부 대상은 wait_on_lock을 따라 이동합니다. 단순히 현재 락의 holder뿐만 아니라, 그 락의 holder가 또 다른 락을 기다리고 있다면 재귀적으로 priority를 전달해야 합니다. 이를 통해 중첩 기부(nested donation)가 가능합니다.

 

3. lock_acquire() 수정

1 2 3 4 5 6

/* threads/synch.c */ if (lock->holder) {     curr->wait_on_lock = lock;     list_insert_ordered(&lock->holder->donations, &curr->donation_elem, cmp_donate_priority, NULL);     donate_priority(); }

현재 락의 holder가 있다면, 스레드는 그 락을 기다려야 하며, 이 정보를 wait_on_lock에 저장합니다. donations 리스트에 기부자(curr)를 삽입함으로써, 락 보유자가 어떤 스레드에게 기부를 받았는지를 추적할 수 있게 됩니다. 그 후 즉시 priority를 기부하여 우선순위 역전 문제를 사전에 방지합니다.

이 과정은 대기자 우선 처리뿐만 아니라 락 해제를 최대한 빨리 유도하기 위한 장치이기도 합니다.

 

4. lock_release()

1 2 3 4 5 6 7 8 9 10 11 12 13

/* threads/synch.c */ void lock_release (struct lock *lock) {     ASSERT (lock != NULL);     ASSERT (lock_held_by_current_thread (lock));       /* Priority Inversion */     remove_with_lock (lock);     refresh_priority ();       lock->holder = NULL;     sema_up (&lock->semaphore); }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

/* threads/synch.c */ void  refresh_priority (void) {     struct thread *curr = thread_current ();     struct list *donation_list = &curr->donations;                     int max_priority = curr->priority;       curr->priority = curr->init_priority;       if (!list_empty (donation_list)) {         struct list_elem *curr_elem = list_front (donation_list);         while (curr_elem != list_tail (donation_list)) {             struct thread *t = list_entry (curr_elem, struct thread, donation_elem);             max_priority = t->priority;             curr_elem = list_next (curr_elem);         }         curr->priority = max_priority;     }   }

remove_with_lock()은 현재 락을 기다리던 스레드가 donations 리스트에서 기부했던 정보를 회수합니다. refresh_priority()는 남아 있는 다른 기부자들 중 가장 높은 우선순위를 반영하거나, 기부자가 없다면 init_priority로 복원합니다. donations 리스트에 여러 스레드가 기부했을 수 있기 때문에, donations 리스트를 순회하여, 현재까지 유효한 기부자 중 가장 높은 priority만 반영합니다. 이를 통해 오래된 우선순위가 누적되거나, 기부자 제거 후에도 priority가 유지되는 오류를 방지합니다. 그중 최대 값을 찾아 현재 스레드의 priority에 반영합니다. 이는 기부자 중 하나라도 우선순위가 높을 경우 이를 놓치지 않기 위한 설계입니다.

기본 상태로 초기화한 후, 필요한 경우에만 도네이션 정보를 반영해야 하기 때문입니다. 이 방식은 항상 최신 상태의 우선순위를 유지하고, 여러 기부자가 있을 때 가장 높은 값만 반영되도록 합니다. 기부자 중 하나가 사라지더라도 우선순위가 계속 유지되는 버그를 막기 위한 안전한 설계입니다.

이렇게 하면 priority가 누적되거나 오래 남아있는 문제를 방지하고, 기부는 일회성이며 상황에 따라 동적으로 사라진다는 원칙을 지킵니다.

---

결과

우선순위 스케줄링 환경에서 발생할 수 있는 역전 문제를 해결하여 실제 OS의 스케줄링 공정성 및 실시간성 요구사항을 충족할 수 있는 기반을 마련했습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

pass tests/threads/alarm-single pass tests/threads/alarm-multiple pass tests/threads/alarm-simultaneous pass tests/threads/alarm-priority pass tests/threads/alarm-zero pass tests/threads/alarm-negative pass tests/threads/priority-change pass tests/threads/priority-donate-one pass tests/threads/priority-donate-multiple pass tests/threads/priority-donate-multiple2 pass tests/threads/priority-donate-nest pass tests/threads/priority-donate-sema pass tests/threads/priority-donate-lower pass tests/threads/priority-fifo pass tests/threads/priority-preempt pass tests/threads/priority-sema pass tests/threads/priority-condvar pass tests/threads/priority-donate-chain FAIL tests/threads/mlfqs/mlfqs-load-1 FAIL tests/threads/mlfqs/mlfqs-load-60 FAIL tests/threads/mlfqs/mlfqs-load-avg FAIL tests/threads/mlfqs/mlfqs-recent-1 pass tests/threads/mlfqs/mlfqs-fair-2 pass tests/threads/mlfqs/mlfqs-fair-20 FAIL tests/threads/mlfqs/mlfqs-nice-2 FAIL tests/threads/mlfqs/mlfqs-nice-10 FAIL tests/threads/mlfqs/mlfqs-block 7 of 27 tests failed.

---

GITHUB

깃허브 Merge pull request입니다.

https://github.com/laphayen/pintos-kaist/pull/5

Priority Inversion by laphayen · Pull Request #5 · laphayen/pintos-kaist