우선순위 스케줄링(Priority Scheduling)과 우선순위 기부(Priority Donation) 구현
•
새로운 스레드가 ready list에 추가되었는데, 그 스레드의 우선순위가 현재 실행 중인 스레드보다 높다면, 현재 스레드는 즉시 CPU를 양보(yield) 필요
•
마찬가지로, 스레드들이 lock, semaphore, condition variable을 기다릴 때에는 대기 중인 스레드들 중 가장 높은 우선순위를 가진 스레드가 먼저 깨워져야함
•
스레드는 언제든 스스로 우선순위를 올리거나 내릴 수 있음. 하지만, 스스로 우선순위를 낮추었을 때 더 이상 최고 우선순위 스레드가 아니라면, 즉시 CPU를 양보해야함
스레드 우선순위 범위는 PRI_MIN (0) ~ PRI_MAX (63)
•
작은 값일수록 낮은 우선순위(즉, priority 0은 최저 우선순위, priority 63은 최고 우선순위)
•
초기 스레드 우선순위는 thread_create()의 인자로 전달됨
•
특별한 이유가 없다면 PRI_DEFAULT (31)을 사용
•
이 매크로들은 threads/thread.h에 정의되어 있으며 값을 변경하면 안됨
우선순위 역전 문제 (Priority Inversion)
우선순위 스케줄링에는 우선순위 역전(priority inversion) 문제 존재
예 : 스레드 H(높음), M(중간), L(낮음)이 있다고 가정
•
만약 H가 L을 기다려야 한다면(예: L이 H가 필요한 lock을 보유 중), 동시에 M이 ready list에 있다면, L은 CPU를 얻지 못해 실행되지 못함 → 그 결과 H도 영원히 실행되지 못함
이 문제를 부분적으로 해결하기 위해, H는 L이 lock을 보유하는 동안 자신의 우선순위를 L에게 "기부(donate)". 그리고 L이 lock을 해제하여 H가 lock을 획득하면, L은 다시 원래의 우선순위를 복구
우선순위 기부 구현
•
반드시 lock에 대해 priority donation을 구현
•
Pintos의 다른 동기화 구조체(semaphore, condition variable 등)에 대해서는 donation을 구현할 필요는 없음. 그러나 모든 경우에 대해 priority scheduling은 구현 필요
우선순위 기부를 구현할 때 고려해야 할 점:
•
여러 번의 donation을 처리할 수 있어야함(여러 스레드가 동시에 donation 하는 경우)
•
중첩 donation(nested donation)도 처리 가능해야함
◦
예: H가 M이 보유한 lock을 기다리고, M이 또 L이 보유한 lock을 기다린다면, M과 L 모두 H의 우선순위를 물려받아야함
•
필요하다면 중첩 donation 깊이에 제한을 둘 수 있음(예: 최대 8단계)
구현해야 할 함수
다음 함수들을 구현해야 하며, 기본 뼈대는 threads/thread.c에 제공됨
void thread_set_priority (int new_priority);
C
복사
•
현재 스레드의 우선순위를 new_priority로 설정
•
만약 현재 스레드가 더 이상 최고 우선순위 스레드가 아니라면, 즉시 CPU를 양보
int thread_get_priority (void);
C
복사
•
현재 스레드의 우선순위를 반환
•
우선순위 기부 상황에서는 기부받은 우선순위(더 높은 값)를 반환
기타
•
다른 스레드의 우선순위를 직접 수정하는 인터페이스는 제공할 필요가 없음
•
우선순위 스케줄러는 이후 프로젝트들(Project 2, 3, 4)에서는 사용되지 않음
정리
•
ready list 정렬 + yield 처리
•
lock 기반 priority donation 구현 (여러 번/중첩 donation 포함)
•
thread_set_priority()와 thread_get_priority() 구현