틀린 내용은 댓글 부탁드립니다.
목표
CPU는 고정된 시간 할당(time slice)을 기준으로, ready_list의 앞에서부터 순서대로 스레드를 실행하고, 시간이 만료되면 해당 스레드를 ready_list 뒤로 이동시키는 Round Robin 스케줄링 방식을 사용합니다.
|
1
2
3
4
5
6
7
8
|
/* /threads/thread.c */
static struct thread *
next_thread_to_run (void) {
if (list_empty (&ready_list))
return idle_thread;
else
return list_entry (list_pop_front (&ready_list), struct thread, elem);
}
|
▲ CPU를 점유 시 ready_list의 첫 번째 쓰레드가 점유하는 부분
|
1
2
3
4
5
6
7
|
/* /threads/thread.c */
void
thread_yield (void) {
struct thread *curr = thread_current ();
if (curr != idle_thread)
list_push_back (&ready_list, &curr->elem);
}
|
▲ CPU를 반환할 때, 현재 쓰레드를 ready_list에 우선순위에 맞게 삽입합니다. (Priority Scheduling 적용)
쓰레드의 수가 많거나 작은 시간 간격으로 스위칭하면, 현재 실행 중인 쓰레드를 다른 쓰레드로 전환 시 상태를 저장, 복원, 작업을 수행하는데 이렇게 발생하는 컨텍스트 스위칭 오버헤드가 증가됩니다. (자리는 바꾸는데 비용과 시간이 소모됩니다.)
따라서, 우선순위 스케줄링을 사용해서 시스템 내의 중요한 작업 또는 긴급한 작업을 신속하게 처리하고 특정 작업을 우선적으로 처리하여 전체적인 시간과 자원을 효율적으로 사용할 수 있습니다.
수정 파일
/threads/thread.c
/include/threads/thread.h
구현
ready_list를 가지고 우선순위 스케줄링하는 방법은 2가지로 구현할 수 있습니다.
첫 번째는 ready_list에서 CPU를 선점할 쓰레드 중 가장 높은 우선순위를 찾는 방법입니다.
점유하고 있는 쓰레드들 다시 ready_list에 넣거나 THREAD_BLOCK 상태로 만든 후, 우선순위가 높은 쓰레드를 찾는 과정에서 많은 시간이 소모되기 때문에 해당 방법은 구현하지 않았습니다.
두 번째는 ready_list가 항상 우선순위로 정렬된 상태를 유지하는 방법입니다.
Pint OS는 CPU를 점유할 쓰레드를 ready_list의 첫 번째에서 가져옵니다.
가장 높은 우선 순위의 쓰레드가 점유될 수 있도록 ready_list가 정렬된 상태를 유지하면 과정에서 쓰레드를 찾는데 비용과 시간을 줄입니다.
따라서, ready_list에 쓰레드의 elem을 넣을 때 우선순위가 정렬된 상태를 유지하도록 삽입합니다. (Pint OS에서는 쓰레드를 elem으로 관리합니다.)
추가적으로 ready_list의 특정 쓰레드의 우선순위가 변경하는 경우에 CPU를 점유하고 있는 쓰레드 보다 우선순위가 높은 경우가 있습니다.
현재 쓰레드를 양보하고 높은 쓰레드가 점유하도록 스케줄링을 수정합니다.
1. thread_create 함수 수정
thread_create () 함수로 쓰레드를 생성하는 경우, CPU를 할당하고 있는 쓰레드보다 우선순위가 높을 경우 선점할 수 있도록 변경합니다.
높은 우선 순위일 경우 CPU를 양보하는 스케줄링 로직을 실행하는 helper function을 만듭니다.
|
1
2
|
/* /include/threads/thread.h */
void test_max_priority (void);
|
|
1
2
3
4
5
6
7
8
9
10
|
/* /threads/thread.c */
void
test_max_priority (void) {
struct list_elem *highest_pri_elem = list_begin(&ready_list);
struct thread *highest_pri_thread = list_entry(highest_pri_elem, struct thread, elem);
if (thread_current()->priority < highest_pri_thread->priority) {
thread_yield ();
}
}
|
ready_list가 항상 우선순위로 정렬되어 있기 때문에 첫 번째 쓰레드는 가장 높은 우선순위를 가지고 있습니다.
list_begin ()으로 첫 번째 elem의 포인터를 가져온 다음에 list_entry ()으로 해당 쓰레드를 우선순위를 가져오고, 실행중인 쓰레드의 우선순위가 ready_list의 가장 높은 우선 순위보다 낮은 경우에는 thread_yield() 함수를 호출해서 CPU를 양보합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
/* /threads/thread.c */
tid_t
thread_create (const char *name, int priority,
thread_func *function, void *aux) {
/* Add to run queue. */
thread_unblock (t);
/* Priority Scheduling */
test_max_priority();
return tid;
}
|
thread_unblock() 함수를 호출해 ready_list에 삽입하고, 해당 스레드를 THREAD_READY 상태로 만든 후, test_max_priority()를 호출해 우선순위 스케줄링을 적용합니다. thread_create() 후 test_max_priority()에서 thread_yield()를 호출하면, 현재 스레드는 ready_list에 삽입되고 즉시 스케줄링이 트리거됩니다. thread_yield() 호출 후 즉시 스케줄링이 일어나지만, 인터럽트 컨텍스트 여부에 따라 실제 context switch 시점은 다를 수 있습니다.
2. thread_unblock 함수
Alarm Clock에서 구현 시 사용했던 함수로 sleep_list에서 쓰레드가 깨어날 시간이 되면 ready_list로 이동합니다.
리스트가 정렬된 상태를 유지하기 위해서 쓰레드를 삽입할 때 우선순위로 넣기 위한 helper function을 만듭니다.
|
1
2
|
/* /include/threads/thread.h */
bool cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);
|
|
1
2
3
4
5
6
7
8
|
/* /threads/thread.c */
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);
return thread_a->priority > thread_b->priority;
}
|
list_entry 매크로를 사용해서 elem으로 주어진 쓰레드의 포인터로 변환합니다.
쓰레드의 포인터에서 우선순위의 값을 비교하여 반환합니다.
|
1
2
3
4
5
6
7
8
|
/* /threads/thread.c */
void
thread_unblock (struct thread *t) {
/* Priority Scheduling */
list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
t->status = THREAD_READY;
}
|
쓰레드가 THREAD_READY 상태로 ready_list에 삽입할 때 리스트가 우선순위로 정렬될 수 있도록 함수를 수정합니다. thread_unblock()은 ready_list에 우선순위 순서로 삽입하지만, 현재 running thread를 강제로 preempt하진 않습니다.
3. thread_yield 함수
기존 코드는 thread_yield()를 호출하면 현재 running 중인 스레드를 ready_list에 우선순위에 맞춰 삽입하고, 스케줄링을 트리거합니다.
리스트가 우선순위로 정렬된 상태를 유지할 수 있도록 cmp_priority () 함수를 사용해서 삽입합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/* /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)
list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);
do_schedule (THREAD_READY);
intr_set_level (old_level);
}
|
4. thread_set_priority 함수
ready_list에 있는 특정 쓰레드의 우선 순위를 직접 변경하는 thread_set_priority 함수입니다.
우선순위가 변경되면 CPU를 점유하고 있는 쓰레드보다 높은 경우가 발생하기 때문에 test_max_priority () 함수를 호출해서 스케줄링 해줍니다.
|
1
2
3
4
5
6
|
/* /threads/thread.c */
void
thread_set_priority (int new_priority) {
thread_current ()->priority = new_priority;
test_max_priority ();
}
|
결과
Pintos는 기본적으로 time slice 기반 Round Robin 스케줄링을 사용하며, Priority Scheduling을 통해 ready_list를 항상 우선순위 정렬 상태로 유지하여, 가장 높은 우선순위의 스레드가 CPU를 점유할 수 있도록 합니다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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
pass 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
16 of 27 tests failed.
|
GITHUB
깃허브 Merge pull request입니다.
https://github.com/laphayen/pintos-kaist/commit/060f37e6dd9c363a4dfbfb7251baf7a20ab5a34a
Merge pull request #3 from laphayen/PriorityScheduling · laphayen/pintos-kaist@060f37e
Priority scheduling
github.com
댓글