2025.05.16

TIL(TODAY I LEARN)

---

• 오늘한 내용 : PintOS - Project1: Threads - donate 구현 완료 - condvar 및 nest 처리

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

---

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)으로 들어감.

nested donation & multiple donation

• nested : a→ b→ c→ d 등 체인의 형태로 우선순위 기부가 일어남
• multiple : a가 L1 L2 락을 모두 소유중
  • b가 L1이 필요하고 c가 L2가 필요함
  • b, c가 a 보다 우선순위가 높을 때 b,c 둘 다 a에게 우선순위 기부가 일어남

수정한 함수

* 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() 추가, 우선순위 고래해서 unblock 직전 정렬 수행
cond_signal() : pop 진행 전 sort() 진행
	semaphore_priority_greater() : cond var 를 위한 대소비교 함수 
------------------
* 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 값을 재조정

조건 변수 (Condition Variable)

조건 변수는 스레드끼리 특정 조건을 기다릴 수 있게 도와주는 동기화 도구다. 조건이 만족되지 않으면 스레드를 잠들게 하고, 만족되면 다른 스레드가 깨워준다.

lock은 상호 배제를 보장하지만, 어떤 조건이 만족될 때까지 기다리는 기능은 없다. 그래서 조건 변수는 반드시 lock과 함께 써야 한다.

주요 함수

• cond_init(cond) : 조건 변수를 초기화한다.
• cond_wait(cond, lock) : lock을 잠깐 놓고 대기하다가 신호가 오면 다시 lock을 잡고 깨어난다.

  1. 전달받은 lock을 해제한 뒤,
  2. cond wait list에 현재 스레드를 블록 상태로 추가하고,
  3. 다른 스레드가 signal/broadcast 할 때까지 대기,
  4. 깨어나면 lock을 다시 획득한 뒤 반환.

• cond_signal(cond, lock) : 대기 중인 스레드 하나를 깨운다.
• cond_broadcast(cond, lock) : 대기 중인 모든 스레드를 깨운다.

cond_wait()는 내부적으로 lock을 해제하고 cond 대기열에 들어간 다음, 다시 lock을 잡고 깨어난다. 그렇기 때문에 조건을 확인할 때는 반드시 while 루프를 사용해야 한다. 깨어났을 때 조건이 여전히 false일 수 있기 때문이다.

lock_acquire(&lock);
while (!조건)
    cond_wait(&cond, &lock);
// 조건이 만족되면 작업을 수행한다.
lock_release(&lock);

조건을 바꾸는 쪽에서는 cond_signal() 또는 cond_broadcast()를 호출해 대기 중인 스레드를 깨워야 한다.