따라서 이를 해결하기 위해 우선순위 기부(Priority Donation)기법을 핀토스에서 사용한다.
높은 우선순위의 쓰레드가 낮은 우선순위의 쓰레드에 의해 블록될 때, 낮은 우선순위의 쓰레드가 높은 우선순위의 쓰레드의 우선순위를 일시적으로 donation 받는 것!
주의
- 쓰레드가 2개 이상의 lock을 보유하게 되면 각 lock에 의해 priority donation이 발생할 수 있다.
따라서 구현할 때 우리는 쓰레드의 이전 상태의 우선순위를 기억하고 있어야 한다.
- 쓰레드 L(priority: 31)이 Lock A, Lock B 점유
- 쓰레드 M(priority: 32)이 Lock A 요청, priority Donation 발생 (L priority = 32)
- 쓰레드 H(priority: 33)이 Lock B 요청, priority Donation 발생 (L priority = 33)
우선순위 기부가 중첩된 상황
한 쓰레드가 다른 쓰레드에게 우선순위 기부 -> 기부받은 쓰레드가 다시 다른 쓰레드에게 우선순위 기부하는 상황
이해를 위해 적어본 nested priority donation 과정
H가 lock B(쓰레드 M이 점유 하는 상황) 요청
-> 따라서 쓰레드 H는 M에게 priority donation.M가 lock A(쓰레드 L이 점유) 요청
-> 쓰레드 M은 lock A가 해제할 때까지 대기L이 lock A 해제
: 쓰레드 L의 priority boost, 쓰레드 L은 더 높은 우선순위가 되어 빠르게 lock A 해제할 수 있게 된다. => Lock A가 해제되면 쓰레드 M은 lock A 획득 가능M이 lock B 해제
: 쓰레드 M은 이제 lock A를 사용해서 작업 후 lock B 해제 => 쓰레드 H가 lock B 획득 가능우선순위 원래대로 복구
먼저 thread 구조체에
Donation 받기 전의 원래의 priority를 저장할 init_priority
필드, 현재 쓰레드가 기다리고 있는 Lock을 저장할 wait_on_lock
필드, donation 기부받은 list를 관리할 donations
필드, donations 리스트의 각각의 엘리먼트를 관리할 d_elem
필드를 추가해준다.
=> 각 쓰레드가 priority donation을 어떻게 받는 상황인지, 어떤 Lock을 기다리고 있는 상황인지, priority donations 리스트를 어떻게 관리하고 있는지를 알 수 있게 된다.
donations
: 각 쓰레드가 받은 우선순위 기부를 추적하기 위한 필드 -> 해당 쓰레드에게 우선순위를 기부한 쓰레드의 list
wait_on_lock
: 각 쓰레드가 기다리고 있는 lock을 추적하기 위한 필드.
현재 쓰레드가 어떤 lock을 기다리고 있는지 알 수 있게 된다.
새로 추가된 필드도 초기화해주는 코드를 입력해준다.
lock_acquire()
쓰레드가 lock을 획득할 때 priority donation을 처리해주는 코드를 추가해준다.
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
//Lock을 획득하는 동작은 인터럽트 컨텍스트에서 수행되면 안됨. 일반적으로 사용자 레벨의 코드에서만 수행되어야 한다.
ASSERT (!lock_held_by_current_thread (lock)); //현재 쓰레드가 이미 해당 락을 보유하고 있지 않는지 확인
//락을 이미 보유한 쓰레드가 다시 시도할 경우 데드락 발생시킬 수 있음.
//해당 Lock의 holder가 이미 존재한다면(다른 쓰레드가 Lock을 보유하고 있다면)
if (lock->holder != NULL) {
thread_current()->wait_on_lock = lock;
// list_push_back(&lock->holder->donations, &thread_current()->d_elem);
//현재 쓰레드를 락을 보유한 쓰레드의 donations 리스트에 우선순위에 따라 삽입
list_insert_ordered(&lock->holder->donations, &(thread_current()->d_elem),compare_donation_priority, NULL);
donate_priority(); // priority donation: lock을 보유한 쓰레드의 우선순위를 현재 쓰레드의 우선순위로 설정
}
sema_down (&lock->semaphore);
//lock에 연결된 세마포어의 값이 0보다 크면 1감소, 그렇지 않으면 대기 상태로 전환
//lock을 획득하기 위해 대기하거나 즉시 획득하는 역할 -> Lock 획득시 -1(공유 자원에 대한 접근 권한 획득했음을 의미)
//현재 쓰레드가 lock을 획득하게 되면,
thread_current()->wait_on_lock = NULL; //현재 쓰레드가 더 이상 이 lock을 기다리고 있지 않음 표시
lock->holder = thread_current(); //lock의 소유자는 현재 쓰레드로 설정
}
if (lock->holder== NULL)
만약 해당 락의 Holder 가 없다면, sema_down
(세마포어 값이 0보다 크면 1 감소, 그렇지 않으면 대기 상태)
=> 이후 lock을 획득하게 되면 wait_on_lock = NULL
로 해주어서 현재 쓰레드가 더 이상 이 lock을 기다리고 있지 않다고 저장하고 lock의 Holder를 thread_current()
로 설정한다.
if (lock->holder != NULL)
반면에 이미 해당 Lock의 Holder가 있다면, priority donation이 일어난다.
donate_priority()
Priority Donation을 수행하는 함수
-> 현재 쓰레드가 기다리고 있는 Lock과 연결된 모든 쓰레드들을 순회하면서
현재 쓰레드의 우선순위를 lock을 보유하고 있는 쓰레드에게 기부한다.
void donate_priority(void) {
struct thread *cur = thread_current();
int cnt = 0;
for (cnt; cnt < 9; cnt++){
//현재 쓰레드를 기다리고 있는 lock이 없으면 반복문 종료
if (cur->wait_on_lock == NULL) {
break;
}
else
{
//holder = 현재 lock을 보유하고 있는 쓰레드
struct thread *holder = cur->wait_on_lock->holder;
//lock을 보유하고 있는 쓰레드의 우선순위를 현재 쓰레드의 우선순위로 설정(priority donation)
holder->priority = cur->priority;
cur= holder;
}
}
}
현재 쓰레드가 기다리고 있는 lock의 holder에게 현재 쓰레드의 우선순위를 기부한다.
nested Priority donation의 limit도 설정해주었다. 우선순위 기부가 너무 많이 발생하게 되면 너무 많은 자원을 우선순위 기부관련 작업을 하는데 사용해야 할 수도 있기 때문이다.
현재 실행 중인 쓰레드는 lock->holder의 우선순위보다 높아서, 우선순위비교 없이 바로 우선순위 기부를 해줄 수 있다.
이미 스케줄링할때 ready_list에서 가장 우선순위가 높은 순으로 스케줄하도록 구현했기 때문에
void
lock_release (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock)); //lock을 해제하기 전에 현재 쓰레드가 Lock의 소유자인지 확인
lock->holder = NULL; //lock의 소유자를 NULL로
remove_with_lock(lock);
revoke_priority();
sema_up (&lock->semaphore); /*세마포어의 값 1증가. ->
만약 세마포어의 값이 0이하였다면, 하나 이상의 쓰레드가 lock을 얻기 위해 대기 중이었음.
-> 하나의 쓰레드가 깨어나서 lock을 얻을 수 있게 됨 */
}
remove_with_lock(lock)
: 현재 쓰레드가 특정 lock을 기다리며 기부받은 priority를 관리하는 함수
-> 현재 쓰레드의 donations 리스트를 순회하면서, 기부해준 쓰레드가 wait_on_lock이release된 Lock
을 기다렸던 경우, 해당 쓰레드를 donations 리스트에서 지워준다.
해당 Lock을 기다렸기 때문에 우선순위를 기부를 했는데 이제 Release됐으니까 기부받은 쓰레드는 원래의 우선순위로 돌아가야 한다.
또한 우선순위 기부는 높은 우선순위의 쓰레드가 낮은 우선순위의 쓰레드가 보유한 자원을 기다릴 때 우선순위 역전을 방지하기 위해 존재한다. lock이 해제되면 더 이상 자원을 기다릴 필요가 없으니 기부된 우선순위도 의미 없어진다.
void remove_with_lock(struct lock *lock){
struct thread *cur = thread_current();
struct list_elem *elem = list_begin(&cur->donations);
//lock이 여러개일 때 -> 순회가 필요
//현재 쓰레드의 Donations(다른 쓰레드로 부터 기부받은 우선순위 리스트 순회)
for (elem; elem!= list_end(&cur -> donations);){
struct thread *t = list_entry(elem, struct thread, d_elem);
//쓰레드가 lock을 기다리고 있다면 donation list에서 제거
if (t->wait_on_lock == lock){
elem = list_remove(&t->d_elem);
}
else {
elem = list_next(elem);
}
}
}
revoke_priority()
현재 쓰레드의 우선순위를 원래대로(처음의
init_priority
로 되돌리거나, 기부를 받은 우선순위가 있다면 기부 받은 우선순위 중 가장 높은 우선순위와 현재 쓰레드의 우선순위를 비교해서 우선순위를 업데이트 한다.
void revoke_priority(void){
struct thread *cur = thread_current();
//현재 쓰레드의 우선순위를 원래 초기 우선순위 값으로 되돌림!
cur->priority = cur->init_priority;
//기부 받은 우선순위가 있다면
if (!list_empty(&cur->donations)){
//donations list에서 가장 큰 우선순위 값
struct thread *donation_max_priority = list_entry(list_begin(&cur->donations), struct thread, d_elem);
//기부 받은 우선순위와 현재 쓰레드의 우선순위를 비교해서,
//기부 받은 우선순위 값이 더 크다면 우선순위 업데이트
if (donation_max_priority->priority > cur->priority){
cur->priority = donation_max_priority->priority;
}
}
}
참고)
여기서 if (donation_max_priority->priority > cur->priority)
조건문은 주석처리 해주어도 테스트 통과된다.
왜냐하면 lock_acquire
할 때 이미 donations 리스트에 정렬되어 insert되기 때문에 donations리스트의 첫 번째 요소는 항상 가장 높은 우선순위를 가진 쓰레드다.
또한 빈리스트가 아닐 때라는 조건을 이미 걸어주었으니 list_front를 사용해도 테스트는 Pass될 것이다!
따라서
lock_release()
를 해줄 때 현재 쓰레드의 Donation list를 순회하면서 해당 Lock을 기다리는 도네이션 항목을 제거해주고, 쓰레드의 우선순위도 재조정해주어야 한다.
Project1에서 가장 어려웠던 Priority scheduling.
특히 donation의 개념이 너무 어려웠고 이를 어떻게 구현해야 할지 너무 막막했다. 정답을 참고하면서 구현했는데도 개념이랑 구현 코드 둘 다 잘 이해가 안가 시간이 더 오래 걸렸다.
wait_on_lock, Donations 리스트로 donation을 관리하는 것을 직접 구현하면서 우선순위 스케줄링에서 우리가 우선순위 역전 문제를 해결해주기 위해서 고려해줘야 하는 것이 얼마나 많은지 깨달았다.