Project 1. Priority Scheduling 구현 (1)

➡️ 과제 설명(Gitbook)

Priority Scheduling

🎯 Goal
- 우선 순위 스케줄링과 우선 순위 기부를 구현하라
- 'threads/thread.c' 에서 'thread_set_priority' 와 'thread_get_priority' 를 구현하라

• 현재 실행 중인 스레드보다 우선 순위가 높은 스레드가 레디 리스트에 추가되면 현재 스레드는 즉시 프로세서를 새 스레드에게 양보해야한다.
• 스레드가 락, 세마포, 상황 변수를 기다리고 있을 때 우선 순위가 가장 높은 대기 스레드가 먼저 깨어나야한다.
• 스레드는 언제든지 자신의 우선 순위를 높이거나 낮출 수 있지만 해당 스레드가 더 이상 가장 높은 우선 순위를 가진 스레드가 아니라면 바로 CPU를 양보해야한다.

 

---

• 스레드 우선 순위의 범위 : PRI_MIN(0) ~ PRI_MAX(63)
  오름차순
• 다른 우선 순위를 선택할 이유가 없으면 PRI_DEFAULT(31) 을 사용한다.

+) “PRI_…” 매크로는 threads/thread.h 에 정의되어 있다.

 

Priority Scheduling의 한 가지 이슈는 “priority inversion” 이다.

• 우선순위 역전(Priority Inversion)

⭐ Lock 에 대한 우선 순위 기부를 구현하라.

 

• 가정 : 우선 순위 높음(High)를 가진 스레드를 “H” 로, 중간(Medium)을 가진 스레드를 “M”, 낮음(Low)를 가진 스레드를 “L”라고 표시한다.

1. 만약 H가 L에 의한 락이 걸려 있다면, H는 L을 먼저 처리해야하므로 H는 CPU를 점유할 수 없다.
   (우선 순위가 낮은 스레드는 CPU를 점유할 수 없기 때문)
2. 이때의 해결 방법은 H는 자신의 우선 순위를 L에게 기부한 다음 L이 락을 해제하면 H는 자신의 우선 순위를 해제한다.

 

• 중첩된 기부
  • 기부가 필요한 다양한 상황을 모두 고려해야한다.
  • H가 M에 의한 락을 기다리고 있고 M이 L에 의한 락을 기다리고 있을 때, M과 L 모두 H의 우선 순위로 높아져야한다.

 

---

• threads/thread.c

void thread_set_priority (int new_priority);

• 현재 스레드의 우선 순위를 새 우선 순위로 설정한다.
• 현재 스레드가 더 이상 가장 높은 우선 순위를 가지지 않으면 양보한다.

 

int thread_get_priority (void);

• 현재 스레드의 우선 순위를 반환한다.
• 우선 순위 기부가 있는 경우, 더 높은 우선 순위를 기부한다.

 

⚠️ 스레드가 다른 스레드의 우선 순위를 직접 수정할 수 있도록 인터페이스를 제공하지 않아도 된다.

⚠️ 우선 순위 스케줄러는 이후 프로젝트에서 사용되지 않는다.

 

 

---

➡️ 구현 [Section 1] Basic Priority Scheduling

 

📌 코드부분은 한글 주석을 달아놓은 부분이 추가된 부분입니다!

 

🎯 Goal

• Functions to modify
  • thread_create : 새로운 스레드를 생성한다.
  • thread_unblock : blocked 스레드를 unblock 한다.
  • thread_yield : 현재 실행중인 스레드가 사용중인 CPU를 반환한다.
  • thread_set_priority : 현재 실행중인 스레드의 우선순위를 변경한다.

 

• Functions to add
  • cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
    : 인자로 주어진 스레드들의 우선순위를 비교한다.

 

---

• Modified files
  • include/threads/thread.h
  • threads/thread.c

 

 

---

📝 Functions List

1. thread_create
2. thread_unblock
3. thread_yield
4. thread_set_priority
5. cmp_priority

 

 

---

1. thread_create

<구현 사항>

1. unblock : 새로 생성한 스레드를 READY 상태로 만든다.

 

 

• threads/thread.c

tid_t
thread_create (const char *name, int priority,
        thread_func *function, void *aux) {
    struct thread *t;
    tid_t tid;

    ASSERT (function != NULL);

    /* Allocate thread. */
    t = palloc_get_page (PAL_ZERO);
    if (t == NULL)
        return TID_ERROR;

    /* Initialize thread. */
    init_thread (t, name, priority);
    tid = t->tid = allocate_tid ();

    /* Call the kernel_thread if it scheduled.
     * Note) rdi is 1st argument, and rsi is 2nd argument. */
    t->tf.rip = (uintptr_t) kernel_thread;
    t->tf.R.rdi = (uint64_t) function;
    t->tf.R.rsi = (uint64_t) aux;
    t->tf.ds = SEL_KDSEG;
    t->tf.es = SEL_KDSEG;
    t->tf.ss = SEL_KDSEG;
    t->tf.cs = SEL_KCSEG;
    t->tf.eflags = FLAG_IF;

    /* Add to run queue. */
    thread_unblock (t); // ready_list 에 새로 넣은 스레드 

    if (thread_get_priority() < priority) { // 현재 실행중인 스레드와 새로 추가하려는 스레드를 비교한다.
        thread_yield(); // 만약 새로 추가하려는 스레드가 현재 실행중인 스레드보다 우선순위가 높으면 CPU를 선점한다.
    }

    return tid;
}

 

• threads/thread.h

struct thread {
    /* Owned by thread.c. */
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging purposes). */
    int priority;                       /* Priority. */
    int64_t wakeup_tick; // 해당 스레드를 깨워야하는 시간(local ticks)

    /* Shared between thread.c and synch.c. */
    struct list_elem elem;              /* List element. */

#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint64_t *pml4;                     /* Page map level 4 */
#endif
#ifdef VM
    /* Table for whole virtual memory owned by thread. */
    struct supplemental_page_table spt;
#endif

    /* Owned by thread.c. */
    struct intr_frame tf;               /* Information for switching */
    unsigned magic;                     /* Detects stack overflow. */
};

• 새 커널 스레드를 생성해서 준비 큐에 추가한다.

 

 

---

2. thread_unblock

<구현 사항>

1. unblock될 때 우선순위 순으로 정렬되어 ready_list에 삽입되도록 수정한다.

 

• BLOCKED 상태의 스레드를 READY 상태로 전환하고 ready_list에 삽입한다.

 

• threads/thread.c

void
thread_unblock (struct thread *t) {
    enum intr_level old_level;

    ASSERT (is_thread (t));

    old_level = intr_disable ();
    ASSERT (t->status == THREAD_BLOCKED);
    /* origin code
    list_push_back (&ready_list, &t->elem);
    */
    list_insert_ordered(&ready_list, &t -> elem, cmp_priority, NULL); // 정렬된 상태로 스레드가 삽입되도록 한다.
    t->status = THREAD_READY;
    intr_set_level (old_level);
}

• BLOCKED 스레드를 READY 상태로 전환한다.
• 해당 함수는 실행 중인 스레드를 선점하지 않는다. (상태변화만 있고 컨텍스트 스위칭은 이루어지지 않는다.)

⭐ 스레드의 상태를 변경 하기 위해 인터럽트를 비활성화한다.

 

 

---

3. thread_yield

<구현 사항>

1. 우선순위 순으로 정렬되어 ready_list에 삽입되도록 수정한다.
   • ready, schedule 과정 모두 포함되어 있음

 

• threads/thread.c

void
thread_yield (void) {
    struct thread *curr = thread_current (); // 현재 스레드의 포인터
    enum intr_level old_level;

    ASSERT (!intr_context ());

    old_level = intr_disable (); // 인터럽터를 비활성화한다.
    if (curr != idle_thread) { // 현재 스레드가 유휴 스레드가 아니면 리스트의 맨 뒤로 넣는다.
        /* origin code
        list_push_back (&ready_list, &curr->elem); // 현재 스레드를 레디리스트의 맨 뒤로 삽입한다.
        */
        list_insert_ordered(&ready_list, &curr -> elem, cmp_priority, NULL); // 정렬된 상태로 스레드가 삽입되도록 한다.
    }
    do_schedule (THREAD_READY); // ready 상태로 전환하고 컨텍스트 스위칭을 한다.
    intr_set_level (old_level); // 이후 다시 이전 상태로 되돌린다.
}

• CPU 점유를 다른 스레드에게 양보한다.
• 양보를 하더라도 우선 순위에 따라 정렬된 후, 다시 CPU를 점유하게 될 수도 있다.

 

 

---

4. thread_set_priority

<구현 사항>

1. 현재 실행 중인 스레드의 우선 순위를 해당 함수의 인자로 들어온 새 우선 순위로 변경한다.

 

• threads/thread.c

void
thread_set_priority (int new_priority) {
    thread_current ()->priority = new_priority; // 현재 스레드의 우선순위를 new_priority(매개변수)로 바꾼다.

    if (thread_get_priority() <  list_entry(list_begin(&ready_list), struct thread, elem) -> priority){
        thread_yield();
    }
}

 

 

---

5. cmp_priority

<구현 사항>

1. 인자로 주어진 스레드들의 우선 순위를 비교한다.
2. a 스레드의 우선순위가 더 크면 1, b가 같거나 더 크면 0을 리턴한다.
3. ⭐ thread.h에 선언해주는 거 잊지 말기!

 

• threads/thread.c

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 ? \
        1 : 0; 
}

 

 

---

🎉 Test Result

>>> cd ./pintos-kaist/threads
>>> make check