PintOS 프로젝트1 Priority Scheduling (priority-sema)

priority-sema

함수 코드에서 수정 사항이 적을 경우 같은 코드 박스에 작성하였습니다. 그러나 수정 사항이 많은 경우 각각 다른 코드 박스에 작성하였습니다. 또한 세마포어 이론을 이해했다는 가정하에 설명하므로 참고하시면 좋겠습니다.

현재 기본으로 제공된 세마포어는 down과 up 등 기본적으로 필요한 로직들은 담겨 있습니다. 그러나 priority(우선순위)에 따라 스레드에게 공유자원 접근 권한을 부여하지 않습니다. 그러므로 세마포어 값을 증가시키며 삽입할 때는 list_insert_ordered 를 통해 정렬을 하며 삽입합니다. 물론 priority_sema_cmp 이라는 비교 함수도 작성해야합니다.

세마포어 값을 올리며 pop을 할 때도 sort를 통해 정렬된 리스트에서 pop을 해오고 thread_check_priority 라는 함수를 통해 우선순위에 따른 lock 획득을 유지합니다.

synch.c 수정사항

경로: threads/synch.c

sema_down

일부분만 바꿨습니다. 위의 push back에서 insert ordered 방식으로 바꿨습니다.

// 원본
list_push_back (&sema->waiters, &thread_current ()->elem);

// 수정본
list_insert_ordered (&sema->waiters, &thread_current ()->elem, priority_sema_cmp, NULL);
// 세마포어가 공유자원을 엑세스할 수 있는 여부를 숫자로 표사하므로 세마포어 값을 올리거나 낮출때, 
// waiters 리스트에서 스레드의 prority 우선순위를 비교하여 정렬하여 삽입하고 빼내야할 것 같다. 

priority_sema_cmp 추가

이에 따라 스레드 구조체에 있는 priority 값을 비교할 필요가 생겼습니다. 그러므로 전에 썻던 스레드 priority 비교 함수를 sema_down 상단에 작성합니다.

// 스레드 스트럭쳐 내부의 인자 가져옴(priority가져와야함)
bool priority_sema_cmp (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct thread *T_A = list_entry(a, struct thread, elem);
    struct thread *T_B = list_entry(b, struct thread, elem);

    return T_A -> priority > T_B -> priority;
}

---

sema_up

sema_down과 마찬가지로 pop을 하되, 정렬된 리스트에서 가져와야되므로 list_sort를 사용하여 정렬하고 priority_sema_cmp에서 나온 값을 토대로 스레드를 언락 시켜줍니다.

사실 세마 다운처럼 정렬만 설정해주면 되는 줄 알았는데, 테스트케이스가 통과되지 않았다. 그래서 다른 동료분께 여쭤보고 방법을 찾은 결과 lock을 해제한 이후에 문제가 생길 수 있음을 알게 되었다. 그래서 다음과 같이 함수를 하나 추가하였다.

언락과 세마포어 값을 up한 이후 (sema->value++)

언락 이후에 current_thread에 waiter 리스트에서 lock을 가진 스레드로 배정되므로 다른 lock을 가지지 않은 waiter 리스트의 스레드와 비교하여 우선순위에 따라 실행할 필요가 있습니다. 그러므로thread_check_priority을 통해 priority가 높은 스레드를 체크하여 우선 실행됩니다.
→ 해당 thread_check_priority 함수는 thread.c에 구현해야합니다.

원본

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

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters))
        thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
    sema->value++;
    intr_set_level (old_level);
}

수정본

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

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters)) {
        **list_sort(&sema->waiters, priority_sema_cmp, NULL);**   //// pop 이전에 정렬 수행
        **struct thread *T1 = list_entry(list_pop_front(&sema->waiters), struct thread, elem);**  
        //// 여기서 pop하지 않고 list_front만 해서 오류가 걸렸다. list 중복이 발생!
        thread_unblock (T1);
    }
    sema->value++;
    **thread_check_priority();**   //// 해당 함수는 thread.c에 구현되어 있습니다. 
    intr_set_level (old_level);
}

thread.c 수정사항

경로: threads/thread.c

위의 과정에서 비교 과정이 추가됨에 따라 thread.c에 다음과 같은 내용을 추가해야합니다.

/* 현재 실행 중인 스레드의 우선순위를 동적으로 변경합니다. */
void
thread_set_priority (int new_priority) {
    thread_current ()->priority = new_priority;
    if (list_empty(&ready_list))  return;   // 리스트가 비었을때 그냥 종료
    struct thread *T1 = list_entry(list_front(&ready_list), struct thread, elem);
    enum intr_level old_level;

    old_level = intr_disable ();   // 인터럽트를 비활성화하고 이전 인터럽트 상태를 반환합니다.
    if ((thread_current() != idle_thread) && (thread_current() -> priority < T1 -> priority))
    thread_yield (); // 우선순위를 바꿨다면, 우선순위에 따라 yield 해줘야한다.
    intr_set_level (old_level);   // 인터럽트 다시 받게 재세팅
}

테스트해보기

make tests/threads/**priority-sema**.result VERBOSE=1

pintos / threads / build 폴더에서 위의 명령어를 통해 priority-sema 테스트 케이스만 실행시킬 수 있습니다. 그러면 결과는 다음과 같이 나옵니다.