[pintos] Week1: Priority Scheduling - Part.1

이전 포스팅인 Alarm Clock의 경우 pintos를 어떻게 접근해야 하는가? 그런 느낌이 들었다면 Priority Scheduling의 경우 복잡하고 어려웠다. 그리고 다시 한번 느끼게 된 건 문서를 잘 읽고 개념을 잘 잡고 진행하자였다.

---

구현 요구사항 설명

• pintos는 FIFO(First In First Out)으로 스케줄링을 진행한다.
• pintos를 우선순위에 따라 스케줄링을 진행하도록 수정하라
  • ready list를 스레드 우선순위에 따라 정렬하라
  • 동기화 기본 요소(세마포어, 조건 변수)에 대한 대기 목록을 정렬한다.
  • 선점기능을 구현하라
  • 선점 지점: 스레드가 준비 목록에 추가될 때(타이머 인터럽트가 호출될 때마다가 아님).

---

구현 목표

• ready list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유 중인 thread의 우선순위보다 높으면 기존 thread 대신 CPU를 점유하도록 만든다.
• 스레드를 우선순위 순으로 Ready_list에 삽입한다. (확장 가능하지 않음에 유의하라.)
• 스레드가 Ready_list에 추가되면 새 스레드의 우선순위와 현재 스레드의 우선순위를 비교한다.
• 새 스레드의 우선순위가 더 높으면, schedule()을 호출한다(현재 스레드가 CPU를 양보한다).

---

구현 진행

1. 구현 함수 헤더에 추가

include/threads/thread.h

/* 기존 코드 */
.
.
/* 우선순위 스케줄링 */
void cmp_nowNfirst (void);
bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);

#endif /* threads/thread.h */

---

2. thread_creat() 함수 수정

• threads/thread.c

PintOS는 thread_create()로 스레드가 생성될 때 초기 우선순위를 설정합니다.

• thread_create()
  • Ready_list에 스레드를 삽입할 때, 현재 실행 중인 스레드와 우선순위를 비교한다.
  • 새로 도착한 스레드의 우선순위가 더 높으면 현재 실행 중인 스레드를 선점하고 새 스레드를 실행한다.

• 현재 실행 중인 스레드와 새로 삽입된 스레드의 우선순위를 비교한다. 새로 삽입된 스레드의 우선순위가 더 높으면 CPU를 양보한다.

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);

	/* 현재와 가장 높은 우선순위 비교후 현재보다 우선순위가 높다면 양보 */
	if(t->priority > thread_current()->priority)
	thread_yield();

	return tid;
}

---

3. thread_unblock() 함수 수정

• threads/thread.c

• 스레드가 차단 해제되면 우선순위에 따라 ready_list에 삽입된다.
• 스레드 차단을 해제할 때 list_push_back 대신 list_inert_ordered를 사용한다.

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

	ASSERT (is_thread (t));

	old_level = intr_disable ();
	ASSERT (t->status == THREAD_BLOCKED);
	//FIFO-> priority로 변경
	list_insert_ordered (&ready_list, &t->elem, cmp_priority, NULL);
	t->status = THREAD_READY;
	intr_set_level(old_level);
}

---

4. thread_yeild() 함수 수정

• threads/thread.c

• 현재 스레드가 CPU를 양보하고, 우선순위 순서대로 ready_listin에 삽입된다.

//FIFO-> 우선순위
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)
        list_insert_ordered (&ready_list, &curr->elem, cmp_priority, NULL);
    do_schedule (THREAD_READY);
    intr_set_level (old_level);
}

---

5. thread_set_priority() 함수 수정

• threads/thread.c

• 현재 스레드의 우선순위를 설정한다.
• 준비 목록 재정렬

// 우선 순위 변경 -> 우선순위에 따라 선점 
void thread_set_priority (int new_priority) {
    thread_current ()->priority = new_priority;
	/* 우선순위에 따른 스케줄링 진행 */
	cmp_nowNfirst();
}

---

6. 함수 추가 구현

cmp_nowNfirst() 함수 추가

• threads/thread.c

헤더에 추가했던 추가 함수를 구현한다.

ready_list에서 우선순위가 가장 높은 스레드와 현재 스레드의 우선순위를 비교해서 현재 스레드의 우선순위가 더 작으면 thread_yeild()를 수행한다.

// 현재와 가장 높은 우선 순위 비교
void cmp_nowNfirst (void){
    if (list_empty(&ready_list))
        return;

    struct thread *th = list_entry(list_front(&ready_list), struct thread, elem);

    if (thread_get_priority() < th->priority)
        thread_yield();
}

cmp_priority() 함수 추가

• threads/thread.c

첫 번째 인자의 우선순위가 높으면 1, 두 번째 인자의 우선순위가 높으면 0을 반환한다.

// 우선순위 비교
bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *thread_a = list_entry(a, struct thread, elem);
	struct thread *thread_b = list_entry(b, struct thread, elem);
	
	if (thread_a == NULL || thread_b == NULL)
		return false;

	// 우선순위가 높은 스레드가 앞에 오도록 (내림차순)
	return thread_a->priority > thread_b->priority;
  }

---

테스트 실행

통과해야 하는 테스트 목록

• alarm-priority
• priority-change
• priority-fifo
• priority-preempt

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
FAIL tests/threads/priority-sema
FAIL tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/threads/mlfqs/mlfqs-load-1
FAIL tests/threads/mlfqs/mlfqs-load-60
FAIL tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-block
17 of 27 tests failed.
../../tests/Make.tests:28: recipe for target 'check' failed
make: *** [check] Error 1

---

참고

[Pintos-KAIST] Project 1 : Priority Scheduling