210206 개발일지(61일차) - 운영체제(OS) 프로젝트 #1-6 : Priority Inversion Problem 해결 (feat. lock & priority donation)

lock 구조체가 필요한 이유

lock 구조체를 살펴보면 아래와 같다. holder(thread 구조체를 가리키는 포인터)와 semaphore 구조체를 갖고 있다.
즉, lock 구조체 안에 semaphore가 있는 것인데 그로 인해 얻을 수 있는 내용을 알아보자.

struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

Critical section에 접근할 필요가 없는 중간 우선순위의 스레드가 발생할 때

앞의 포스팅에서 semaphore로 우선순위 역전현상을 해결하는 내용을 살펴봤다. 그 때의 가정은 모든 스레드(프로세스)가 Critical section에 접근이 필요하다는 것이었다. 그러나 실제 상황에서 모든 스레드(프로세스) 그럴 일은 없을 거다. 그렇기 때문에 아래 그림에서 파란색 스레드(M)처럼 Critical thread에 접근할 필요 없는 스레드가 들어오면 주황색 스레드보다 먼저 실행이 되버리고 만다. 이런 현상을 해결하기 위해 lock 개념이 필요하다.

Priority donation(우선순위 기부)

위의 말한 문제점을 해결하기 위해, 아래 그림처럼 lock이 필요한(Critical section에 접근이 필요한) 상황이라면 주황색 스레드(H)의 우선순위를 초록색 스레드(L)에 그대로 주고 실행이 될 수 있도록 해준다.
혹여라도 파란색 스레드(M)가 생겨서, 파란색이 먼저 실행되는 것을 막기 위해 초록색 스레드를 강제로 우선순위를 높여주는 것이다.
자연스레 초록색 스레드가 lock이 필요 없어지면(=Critical section의 접근이 필요 없어지면) 다시 본인의 우선순위로 돌아가게 된다.

종합적으로 보면 아래 그림과 같이 나타낼 수 있다.

구현하기

필요한 함수들을 아래와 같이 구현했다.

void donate_priority(void){
    struct thread *t = thread_current();
    struct lock *lock = t->wait_on_lock;
    int depth = 0;
    while (lock && depth < NESTED_DEPTH_LIMIT){ // 체인 맨 끝까지 
        if (t->priority > lock->holder->priority){
            lock->holder->priority = t->priority;
            t = lock->holder;
            lock = t->wait_on_lock;
        }
    }
    
}

// donation list 중 해당 lock 기다리는 애들 다 날려준다
void remove_with_lock(struct lock *lock){ 
    struct list_elem *e = list_begin(&thread_current()->donations);

    // donation list 순회하며 찾는다 
    for (e; e != list_end(&thread_current()->donations); e = list_next(e)){
        if (list_entry(e, struct thread, donation_elem)->wait_on_lock == lock){
            list_remove(e);
        }
    }
}

// 스레드의 우선순위가 변경 되었을때 donation 을 고려하여 우선순위를 다시 결정 하는 함수
void refresh_priority(void){
    struct thread *t = thread_current();
    struct lock *lock = t->wait_on_lock;
    
    t->priority = t->init_priority; // 이전 priority로 되돌리기 
    if(!list_empty(&(thread_current()->donations))){ // 근데 dl에 남아있으면서, 얘가 나보다 크면 바꿔줘야지 
        struct thread *dona_front = list_entry(list_front(&thread_current()->donations), struct thread, donation_elem);
        if (t->priority < dona_front->priority){ // 복구한 priority보다 dona_list 맨앞의 pri가 더 크다면 그 우선순위로 ㄱ 
            t->priority = dona_front->priority;
        }
    }   
}

void lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL); // lock의 helder가 존재한다면 
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));
    if (lock->holder){
        thread_current()->wait_on_lock = lock;  
        list_insert_ordered(&(lock->holder->donations), &(thread_current()->donation_elem), cmp_priority, NULL);
        donate_priority(); 
    }
    
	sema_down (&lock->semaphore);
    thread_current()->wait_on_lock = NULL;
	lock->holder = thread_current ();
}

void lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	lock->holder = NULL;
    remove_with_lock(lock); // 이제 lock을 갖게 될 애를 dl에서 제거
    refresh_priority(); // 이전 우선순위로 돌려줌
	sema_up (&lock->semaphore); // 다음 애 실행되도록 
}