⸻
Pintos Priority Scheduling 구현 체크리스트
Alarm Clock (timer_sleep 개선)
- thread_sleep() 함수 구현
• 현재 스레드를 BLOCKED 상태로 만들고 sleep_list에 넣음.
• 각 스레드는 언제 깨어나야 할지 wakeup_tick을 저장함. - thread_awake() 함수 구현
• 타이머 인터럽트마다 호출되어 sleep_list를 확인하고,
• 현재 tick 이상이 된 스레드를 깨움. - timer_interrupt()에서 thread_awake() 호출
• 매 tick마다 깰 스레드가 있는지 확인하도록 추가.
⸻
Priority Scheduling (우선순위 기반 스케줄링)
- 레디 리스트 삽입 방식 변경
• list_push_back() 대신 list_insert_ordered() 사용해서 우선순위 기준 정렬되도록 변경. - cmp_priority() 함수 추가
• 우선순위 비교 함수 작성해서 정렬 시 사용. - thread_unblock() 수정
• READY 상태로 전환할 때 우선순위 기준으로 ready_list에 삽입. - thread_yield() 수정
• CPU 양보 시 ready_list에 우선순위 기반으로 삽입. - 새로운 스레드가 현재 실행 중인 스레드보다 우선순위 높으면 양보 (thread_preemption)
• thread_create, sema_up, thread_set_priority 등에서 이 함수를 호출해서 선점 발생.
⸻
Synchronization Primitives (우선순위 고려)
세마포어 (semaphore)
- sema_down()
• sema->waiters 리스트에 현재 스레드를 우선순위 기준 정렬하여 삽입. list_insert_ordered() - sema_up()
• 가장 우선순위 높은 스레드를 깨움.
- list_sort() 사용 후 가장 높은 우선순위 스레드 깨움 (thread_unblock() 호출)
⸻
락 (lock)
- lock_acquire()
• 내부적으로 sema_down()을 호출하므로 우선순위 기반 대기가 적용됨. - lock_release()
• 내부적으로 sema_up()을 호출하여 가장 높은 우선순위 스레드를 깨움.
⸻
조건 변수 (condition variable)
- cond_wait()
• cond->waiters 리스트에 세마포어 엘리먼트를 우선순위 기준 정렬하여 삽입. list_insert_ordered() - cond_signal()
• waiters 리스트 중 우선순위 가장 높은 세마포어를 선택하여 그 안의 스레드를 깨움.
• 정렬 함수 작성 필요 (waiters 내부는 semaphore_elem을 감싸므로 내부 thread priority 기준)
⸻
thread_set_priority():
• 우선순위 변경 시, ready_list에 더 높은 우선순위 스레드가 있으면 양보.
thread_preemption():
• ready_list에 있는 스레드와 현재 스레드의 우선순위를 비교해서 선점이 필요한지 확인.
- thread_create() , thread_set_priority (int new_priority)
- sema_up()
⸻
Donation
Multiple Donation
• 여러 스레드가 동시에 같은 스레드에게 priority를 기부할 수 있는 구조
• 예: 여러 스레드가 하나의 락을 기다릴 때
Nested Donation
• 기부가 연쇄적으로 이어짐
• 예: H → M → L (H가 B 기다림 → M이 B holder이자 A도 기다림 → L이 A holder)
H (priority 50) ──waits──> Lock B ──held by──> M (priority 30) ──waits──> Lock A ──held by──> L (priority 10)⸻
- struct thread 확장
• 각 스레드가 기다리는 락을 저장하는 필드 추가
→ struct lock *wait_on_lock;
• 다른 스레드에게 받은 priority donation 목록 관리할 리스트 추가
→ struct list donations;
• donation 리스트에 들어갈 때 사용할 리스트 엘리먼트 추가
→ struct list_elem d_elem;
⸻
- init_thread(struct thread t, const char name, int priority)
• 위에서 추가한 wait_on_lock을 NULL로 초기화
• donations 리스트 초기화
• d_elem은 리스트 삽입 시 사용됨 (초기화 불필요)
⸻
- lock_acquire(struct lock *lock)
락을 획득하지 못한 경우 (락을 이미 다른 스레드가 점유 중인 경우):
• 현재 스레드의 wait_on_lock에 해당 락 주소 저장
• 락의 holder 스레드에게 priority를 기부 (donation)
• 단일이 아니라 다중 기부가 가능해야 하므로, holder의 donations 리스트에 현재 스레드 삽입
• donation을 전파 (nested 구조이면 재귀적으로)
⸻
- lock_release(struct lock *lock)
• 해당 락을 기다리며 기부했던 스레드들을 donation 리스트에서 제거
• 예: donations 리스트에서 wait_on_lock == lock인 스레드만 제거
• 나의 priority를 원래 값 또는 아직 남아 있는 donation 중 가장 높은 값으로 복원
⸻
- thread_set_priority(int new_priority)
• 자신의 기본 우선순위를 변경
• 하지만 donation 중인 우선순위가 더 높으면 그걸 유지해야 함
• donations 리스트 중 가장 높은 priority와 비교하여 현재 우선순위 재조정
⸻
✅ 함수별 정리 (코드 수정 요약)
함수 해야 할 일
init_thread() wait_on_lock = NULL, list_init(&donations)
lock_acquire() wait_on_lock 설정, holder에게 priority donation, list_insert_ordered(&holder->donations)
lock_release() donations 리스트에서 해당 락 대기자들 제거, priority 복원
thread_set_priority() 기본 priority 변경, donation 고려하여 재계산
⸻
📌 보충 팁
• donate_priority() 같은 헬퍼 함수 만들어서 priority 전파 재귀적으로 구현하면 좋음
• 락 release 후에도 donation 남아 있을 수 있으니 항상 donation 리스트 확인 후 max priority 계산 필요
⸻
