210205 개발일지(60일차) - 운영체제(OS) 프로젝트 #1-5 : Priority Inversion Problem 해결(feat. semaphore)

우선순위 역전현상 (Priority Inversion Problem)

앞에서 semaphore를 통해 Critical section에 여러 개의 스레드(프로세스)의 접근을 막는 것을 배웠다. 그러나 아래와 같은 문제가 있다.
위의 사진의 문제는 파란색, 보라색, 주황색 스레드가 우선순위 순으로 waiters에 대기하지 않고 Lock요청 순으로 waiters에 대기한다는 것이다. 그래서 초록색 막대의 semaphore가 1이 되는 시점(=Lock이 반환되는 시점)을 보면, 우선순위가 높은 스레드(프로세스)인 보라색이 먼저 진행되지 않고 파란색이 먼저 진행된다.
그래서 아래와 같이 waiters의 순서를 바꿔줘야 한다.

이에 해당하는 함수 sema_down()과 sema_up()를 바꿔주면 아래와 같다.
list_insert_ordered()함수 안에 인자로 들어갈 cmp_priority() 함수도 만들어야 한다.

void sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (list_empty (&sema->waiters) == false){
        // waiter list를 우선순위로 정렬 
        list_sort(&sema->waiters, cmp_priority, NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
        sema->value++;
        intr_set_level (old_level);
        thread_yield();
    }
    else
    {
        sema->value++;
        intr_set_level (old_level);
    }
}

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) { // sema 0이면 sema 1될때까지 while문에서 기다림 
		// list_push_back (&sema->waiters, &thread_current ()->elem);
        // project1-3
        // 먼저 넣고 블락함 
        list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

bool cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
    return list_entry(a, struct thread, elem)->priority > list_entry(b, struct thread, elem)->priority;
}

lock 기능 (lock 구조체 사용)

semaphore 구조체를 통해, 동시에 Critical section에 접근하지 못하도록 구현이 가능했다.
그러나 pintOS 과제에서는 semaphore보다 발전된 lock 기능까지 구현해서 donation을 진행해야 한다. 그 이유는 다음 포스팅에서 알아보자.