Nested donation 관련 test case는 통과하였으나 잡아야하는 오류
OS project PintOS 과정에서 조교님들께 질문하고 답변 받는 채널이 생겼고 질문이 올라왔다.
조교님들 안녕하세요,
스레드가 두개 이상의 lock을 보유하고 있어서 각 lock에 의해 donation이 발생하는 상황 (multiple donation)에서, 이전 상태의 우선순위로 적절하게 돌아가도록 하기 위해 thread 구조체 내에 “donations”라는 리스트를 선언하여 관리하였습니다.
질문: 우선순위가 높은 스레드가 낮은 스레드에게 lock을 요청하는 경우에 donation이 필요하므로, donation list에는 정렬을 하지 않아도 항상 우선순위 순으로 스레드가 들어온다고 생각했습니다. donations에 list_push_back 함수를 호출하여 스레드를 추가하였을 때 테스트 케이스를 잘 통과하는 것을 확인하였는데, 이와 관련한 예외적인 케이스가 있을 수 있을까요? list_insert_ordered를 사용하여야만 적절하게 동작하는 케이스가 (테케가 아닌 실제 OS 구동 상황에서 )있는지 궁금합니다.
답변해주셨다.
말씀해주신 아이디어는 괜찮은 아이디어라고 생각됩니다. 구체적으로 어떻게 구현하셨는지 소스코드를 보지 않으면 제대로 구현하셨는지 정확히 대답할 수는 없지만, 몇몇 고려 사항만 생각하셨다면 충분히 가능한 아이디어 입니다.
이 아이디어에서 고려해야 할 점은
donation list를 별도로 정렬하지 않아도 lock_acquire에서 새로 thread를 추가할 때 그 thread는 가장 높은 priority를 가지고 있는 것은 맞습니다.
다만 nested priority donation의 경우에 donations에 들어 있는 thread의 priority가 변동될 수 있고, 이 경우에 donations안에 thread가 정렬되어 있다는 사실은 보장할 수 없습니다.
그러므로 2번과 같이 donations안에 있는 thread가 항상 정렬되어 있다는 가정을 쓰려면 별도의 신경을 써야겠지만, 1번과 같이 단순히 새로 donations에 추가되는 thread는 항상 가장 높은 priority를 가진다는 사실만 쓴다면 별 문제 없는 것 같습니다.
우리 조의 구현은 lock을 요청하고 얻지 못했을 때, donation list에 넣어야하니 정렬을 해서 넣고
lock을 반환하며 현재 쓰레드의 우선순위가 바뀌었을 때 refresh_priority()를 하며 현재 쓰레드의 donation list 중 가장 높은 우선순위와 비교해서 현재 쓰레드의 우선순위를 갱신하는 방법으로 구현하였다.
/* lock을 요청 */
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
struct thread *cur = thread_current();
/* 해당 lock 의 holder가 존재 한다면 아래 작업을 수행 */
/* 현재 스레드의 wait_on_lock 변수에 획득 하기를 기다리는 lock의 주소를 저장 */
if(lock->holder != NULL){
cur->wait_on_lock = lock;
/* donation 을 받은 스레드의 thread 구조체를 list로 관리 */
list_insert_ordered(&lock->holder->donations, &cur->donation_elem, cmp_don_priority ,NULL);
/* priority donation 수행하기 위해 donate_priority() 함수 호출 */
donate_priority();
}
sema_down (&lock->semaphore);
cur->wait_on_lock = NULL;
/* lock을 획득 한 후 lock holder 를 갱신한다. */
lock->holder = thread_current();
}
/* lock을 반환 */
void
lock_release (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
/* lock 을 해지 했을때 donations 리스트에서 해당 엔트리를 삭제 하기 위한 함수 */
remove_with_lock(lock);
/* 스레드의 우선순위가 변경 되었을때 donation 을 고려하여 우선순위를 다시 결정 하는 함수 */
refresh_priority();
lock->holder = NULL;
sema_up (&lock->semaphore);
}
/* 스레드의 우선순위가 변경 되었을때 donation 을 고려하여 우선순위를 다시 결정 하는 함수 */
void refresh_priority(void){
/* 현재 스레드의 우선순위를 기부받기 전의 우선순위로 변경 */
struct thread *cur = thread_current();
cur->priority = cur->init_priority;
/* 가장 우선순위가 높은 donations 리스트의 스레드와
현재 스레드의 우선순위를 비교하여 높은 값을 현재 스레드의 우선순위로 설정 */
if(list_empty(&cur->donations)== false){
// list_sort(&cur->donations, cmp_don_priority, NULL);
struct thread *t = list_entry(list_front(&cur->donations), struct thread, donation_elem);
/* 가장 우선순위가 높은 donations 리스트의 스레드가 현재 스레드의 우선순위보다 높으면*/
if(t->priority > cur->priority){
cur->priority = t->priority;
}
}
}위 질문을 통해 우리 코드에서 놓친 점은 nested_donation으로 인해 donation list 안에 있는 쓰레드의 우선순위가 바뀌는 상황에서 재정렬을 하지 못한다는 것을 다시 생각해보게 되었다.
list_sort(&cur->donations, cmp_don_priority, NULL);이미 test는 통과하겠지만 donation list 안에 쓰레드를 바뀐 우선순위에 따라 재정렬해주는 해당 코드를 추가하며 떠오른 반례에 대해 해결해줄 수 있다.
위 질문으로 돌아가면
lock_acquire()의 우선순위 정렬하며 넣는 list_insert_ordered 대신에 들어오는 순서대로 넣는 list_push_back 함수를 사용하면 단순히 새로 donations에 추가되는 thread는 항상 가장 높은 priority를 가진다는 사실만 쓴다면 괜찮은듯 보인다는 것이다.
결론은 donation list에 넣을 때 list_push_back함수만 쓰거나 넣고 뺄 때 정렬해주는 함수를 써야한다.
피드백은 언제나 환영입니다!
