[Project 1-2] Priority Scheduling(mywnajsldkf)

[mywnajsldkf]

7. Priority Scheduling 📅

✍ 과제 미션

• Priority Scheduling: pintos의 스케줄러를 라운드로빈이 아닌, 우선순위를 고려하여 스케쥴링한다.
• 우선순위가 가장 높은 thread가 CPU를 점유한다.

👾 작업

Priority Scheduling

• [x] void test_max_priority (void) 현재 수행중인 스레드와 가장 높은 우선 순위의 스레드의 우선순위를 비교하여 스케쥴링한다.
• [x] bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED 인자로 주어진 스레드들의 우선순위를 비교한다.
• [x] thread_create 생성된 스레드의 우선순위가 현재 실행중인 스레드의 우선순위보다 높으면 CPU를 양보한다.
• [x] void thread_unblock (struct thread *t) 스레드가 unblock될 때 우선순위 순으로 정렬되어 ready_list에 삽입된다.
• [x] void thread_yield(void) thread가 CPU를 양보하여 ready_list에 삽입될 때 우선순위 순서로 정렬되어 삽입되도록 수정한다.
• [x] void thread_set_priority (int new_priority) 스레드의 우선순위가 변경되었을 때 우선순위에 따라 선점이 발생한다.
• [x] bool cmp_priority (construct struct list_elem* a_, const struct list_elem* b_, void* aux UNUSED) 첫번째 인자와 두번째 인자를 비교하여 정렬하기 위한 기준을 작성한다.

⭐️ 생각할 점

• [ ] list_begin과 list_front 함수가 구분되어 있는 이유는 무엇일까?

---

8. Priority Scheduling and Synchronization

✍ 과제 미션

• 여러 스레드가 lock, semaphore, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유하도록 구현한다.

👾 작업

Priority Scheduling-Synchronization

• [x] void sema_down (struct semaphore *sema) 세마포를 획득하고 waiters 리스트에 우선순위대로 삽입한다.
• [x] void sema_up (struct semaphore *sema) 스레드가 waiters list에 있는 동안 우선순위가 변경되었을 경우를 고려하여, waiters list를 우선순위로 정렬한다.
• [x] void cond_wait (struct condition *cont, struct lock *lock) condition variable의 waiters list에 우선순위 순서로 삽입한다.
• [x] void cond_signal(struct condition *cond, struct lock *lock UNUSED) condition variable의 waiters list를 우선순위로 재정렬한다. (대기중에 우선순위가 변경되었을 경우 고려!)
• [x] bool cmp_sem_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) 세마포어 리스트를 높은 우선순위를 가지는 스레드의 우선순위 순으로 정렬한다.

⭐️ 생각할 점

[mywnajsldkf]

7. Priority Scheduling 실행 결과

pintos/threads에서 make check를 실행한다.

부분만 테스트하고 싶다면, pintos/threads/build에서 다음과 같이 실행한다.

pintos -v -k -T 60 -m 20 -- -q run priority-fifo < /dev/null 2> tests/threads/priority-fifo.errors > tests/threads/priority-fifo.output
perl -I../.. ../../tests/threads/priority-fifo.ck tests/threads/priority-fifo tests/threads/priority-fifo.result

[mywnajsldkf]

8. Priority Scheduling and Synchronization 실행 결과

첫번째 시도에서 priority-codvar 테스트 통과를 하지 못했는데, 확인해보니 직접 구현한 cmp_sem_priority 문제였다. list_front 함수를 사용하여 세마포어 wait list의 첫번째 스레드를 확인했는데, 만약 wait list에 아무것도 없다면 list_front에서 list가 빈어있는지 확인하는 assert에 걸릴 것이다! 만약 list_begin 함수를 사용하면 이 부분을 걸리지 않을텐데... 흠,,, 왜 두 함수를 구분해두었는지 잘 모르겠다. 🧐 일단 list_empty 함수를 이용해 비었는지 확인하는 식으로 수정하니 통과되었다.

struct list_elem *
list_front (struct list *list) {
    ASSERT (!list_empty (list));
    return list->head.next;
}

[mywnajsldkf]

cmp_sem_priority 진행 중 발생한 참조 문제

bool
cmp_sem_priority (const struct list_elem *a, const struct list_elem *b, void *aux) {
    struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

    if (!list_empty(&(sa->semaphore.waiters)) && !list_empty(&(sb->semaphore.waiters)))
    {
        struct thread *a_thread = list_entry(list_front(&(sa->semaphore.waiters)), struct thread, elem);
        struct thread *b_thread = list_entry(list_front(&(sb->semaphore.waiters)), struct thread, elem);
        return a_thread->priority > b_thread->priority;
    }
}

이 코드에 문제가 있을까요? 답은 없습니다...

근데 왜 안돌아가고, 계속 list_elem(semaphore_elem)을 찾을 수 없다고 에러코드는 던지고 있는 것일까요??

일단,,, 다른 조원이 작성한 것처럼 해당 함수를 소스 코드 가장 밑으로 이동시켰습니다.

음 일단 되지만 찝찝합니다...

문제가 무엇일까요??

그것은 바로....

// 약 160줄
bool
cmp_sem_priority (const struct list_elem *a, const struct list_elem *b, void *aux) {
    struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

    if (!list_empty(&(sa->semaphore.waiters)) && !list_empty(&(sb->semaphore.waiters)))
    {
        struct thread *a_thread = list_entry(list_front(&(sa->semaphore.waiters)), struct thread, elem);
        struct thread *b_thread = list_entry(list_front(&(sb->semaphore.waiters)), struct thread, elem);
        return a_thread->priority > b_thread->priority;
    }
}

... 

// 대략 250줄에서 semaphore_elem을 만날 수 있었습니다...
/* One semaphore in a list. */
struct semaphore_elem {
    struct list_elem elem;              /* List element. */
    struct semaphore semaphore;         /* This semaphore. */
};

알고보니! semaphore_elem 구조체 선언 전에 semaphore_elem을 찾고 있었네요... 흠,,, 왜 이렇게 코드를 작성했을까요? header 파일로 이동해도 좋을 것 같은데 말이죠... 의도가 있을까요?

암튼 이것을 해결하는데 1시간 30분이 걸렸습니다...

feat. 같이 머리를 함께 모아준,,, 99즈 프렌즈 Thanks a lot!👍 @KimCookieYa @chwangmin