2025.05.14

TIL(TODAY I LEARN)

---

• 오늘한 내용 : PintOS - Project1: Threads - donate 구현 중

• WEEK 09 : 정글 끝까지(PintOS) - Threads

---

donate 구현 완료 글

Priority Donation

항목	작성 예시
nested donation은 어떻게 처리하나요?	최대 깊이 제한 설정 (예: 8), 재귀적으로 priority 전달
어떤 구조체 수정하나요?	struct lock, struct thread에 waiting_lock, donors 리스트 추가
어떤 함수에서 donation 발생하나요?	lock_acquire(), lock_release(), thread_set_priority()
주의할 점은?	donation 제거 시 원래 priority 복구 필요

구현 목표

• 낮은 priority의 스레드가 락을 점유했을 때, 높은 priority 스레드가 우선 실행되도록 donation

설계

• struct thread에 original_priority, waiting_lock, donors 리스트 추가
• struct lock에 holder 필드 활용
• lock_acquire() 시 락의 holder에게 priority 전달
• nested donation은 재귀적으로 처리 (깊이 제한 필요)
• thread_set_priority()에서 donation 취소 시 원래 priority 복원

수정 함수

• lock_acquire()
• lock_release()
• thread_set_priority()

테스트

테스트 이름	의미
priority-donate-one	하나의 락에 대해 donation이 제대로 되는지
priority-donate-multiple	여러 스레드가 하나의 락에 nested donation 시도
priority-donate-chain	중첩된 락 대기 상황에서 donation이 전달되는지
priority-donate-lower	donation 후 priority 복원이 정확히 되는지

우선순위 기부(Priority Donation)

• 목표: 우선순위 역전 상황에서 락 보유 스레드에 일시 기부
• 수정 파일: threads/synch.c (lock_acquire(), lock_release())
  • lock_acquire()
    1. 대기 중인 락의 holder가 있으면
       • cur->waiting_lock = lock
       • donate_priority(cur, lock->holder) (재귀적 중첩 기부 허용)
  • lock_release()
    1. sema_up(&lock->semaphore)
    2. 해당 락 관련 기부자 제거 (remove_donations_for_lock())
    3. current_thread->priority = max(base_priority, highest_donation())

우선순위 조정 API

• 수정 파일: threads/thread.c
  • void thread_set_priority(int new_priority)
    • cur->base_priority = new_priority → refresh_priority(cur) → 양보 조건 시 thread_yield()
  • int thread_get_priority(void)
    • return current_thread->priority;

---

donation 흐름 정리

1. 스레드 준비 → 스케줄러가 선택 → 실행 시작

   • thread_unblock()이나 thread_yield()로 ready 큐에서 뽑혀서
   • 실제로 CPU 위에서 thread_current()가 실행.

2. CPU 위에서 락 요청

   lock_acquire(&L);

   이때 메모리나 레지스터에 L.holder를 검사.

   • L.holder == NULL 이면 바로 sema_down()도 성공하고 락 획득.
   • L.holder != NULL 이면 경쟁 발생으로 넘어감.

3. 경쟁이 감지된 바로 시점

   if (L.holder != NULL && cur->priority > L.holder->priority) {
     cur->waiting_lock = &L;
     donate_priority();
   }

   여기서 기부가 일어나고, 아직 블록되기 전이므로 holder(다른 스레드)가 즉시 높은 우선순위를 받아 CPU를 더 빨리 쓰게 됨.

4. 기부 후 실제 블록

   sema_down(&L.semaphore);  // 블록 대기
   lock->holder = cur;       // 락 획득
   cur->waiting_lock = NULL; // 대기 중 아님

요약:

• 락 요청(lock_acquire)은 이미 CPU에서 실행 중일 때만 일어나고,
• 그 즉시 기부(donate_priority)가 실행된 뒤에야 블록(sema_down)으로 들어감.

수정한 함수

* thread.h

struct thread : donate를 위한 필드 추가
---------------
* thread.c

init_thread() : 필드 추가 했으니 초기화 수정
thread_donate_priority() : donation
thread_remove_donations_for_lock() : lock 해제 시 해당 기부 제거
thread_update_prioriy() : base_p / donation_list의 최댓값 중 큰값으로 priority 갱신
thread_set_priority() : 유저가 직접 우선순위 변경 가능하게
thread_create() : preempt() 추가
---------------
* synch.c
lock_acquire() : 락 요청이 들어왔을때 thread_donate_priority() 검사 및 실행
lock_release() : 기부받은 스레드가 락 끝났을 때 기부삭제 및 업데이트 추가
sema_up() : preempt() 추가
------------------
* timer.c
timer_interrupt() : preempt() 추가

HOW?

• lock_acquire()

  1. 스레드가 락 요청을 할때 검사 및 기부 진행
     • 락 소유자가 있고 내가 더 높은 우선순위면 기부
  2. sema_down()을 통해세마포어를 얻으려 시도
     • 락이 없을 때 - 세마포어가 1 → 락 획득 성공
     • 락이 있을 때 - 세마포어가 0 → 현재 스레드는 블락

• thread_donate_prioity()

  • while을 돌면서 연속적인 nest donation 검사
  • 현재 스레드가 기다리는 락이 있는지, 그 락의 소유자를 보고
    • 우선순위 역전을 판단
      • 우선순위 역전 → 우선순위를 기부 및 기부자 리스트에 추가

• lock_release()

  • 락을 해제할 때:
    • thread_remove_donations_for_lock() 호출로 해당 락에 대해 기부받은 우선순위 제거
    • 남은 donation 중 최대 우선순위로 자신의 우선순위 다시 계산 (thread_update_priority() 호출)

• thread_remove_donations_for_lock()

  • donation_list에서 현재 락과 관련된 기부자들을 제거

• thread_update_priority()

  • 기부가 제거된 이후:
    • base priority와 donation_list의 최대값을 비교하여 현재 스레드의 priority 갱신

• thread_set_priority()

  • 사용자가 직접 priority를 바꾸려 할 때:
    • base_priority를 갱신하고
    • donation 상태를 고려하여 실제 priority 값을 재조정