먼저 Ready queue에 들어온 스레드가 먼저 실행되는 FCFS(First Come First Served) 방식에, 일정 time slice가 지나면 CPU의 주도권을 다음 스레드에 넘기는 Round Robin 방식이다. Preemptive 방식의 스케줄링이 아니며, 우선 순위는 고려되지 않고 있다.
thread.c/thread_unblock()
block 상태의 스레드를 깨우고 난 뒤 ready list의 맨 뒤에 삽입한다.
void thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
list_push_back (&ready_list, &t->elem); // 깨우고 난 뒤 ready list의 맨 뒤에 삽입.
t->status = THREAD_READY;
intr_set_level (old_level);
}
thread.c/schedule()
next_thread_to_run() 함수에 의해 다음 실행 스레드가 정의된다.
static void
schedule (void) {
struct thread *curr = running_thread ();
struct thread *next = next_thread_to_run (); // CPU 주도권을 넘겨줄 다음 스레드
ASSERT (intr_get_level () == INTR_OFF);
ASSERT (curr->status != THREAD_RUNNING);
ASSERT (is_thread (next));
/* Mark us as running. */
next->status = THREAD_RUNNING; // 다음 스레드 상태 변경
/* Start new time slice. */
thread_ticks = 0; // 현재 time slice는 4 ticks
....
thread_launch (next); // 다음 스레드 실행
}
}
thread.c/next_thread_to_run()
ready list에서 맨 앞 스레드를 pop해 CPU 주도권을 넘겨줄 다음 스레드로 설정한다. 만약 ready list가 비어 있다면 idle 스레드가 다음 CPU 주도권을 잡도록 설정해준다.
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); // list에서 맨 앞
}
thread_create()와 thread_set_priority() 함수에서 스레드들의 우선순위에 따른 CPU 선점이 일어난다.
우선 순위를 정렬하여 리스트에 삽입시켜주는 list_insert_ordered() 함수를 이용한다.
list.c/list_insert_ordered()
자신보다 더 큰 원소가 나오면 멈춘다. 그 사이에 삽입한다.
만약 인자를 cmp_priority() 함수로 주었다면, 우선 순위가 가장 큰 스레드가 맨 앞에 올 것이다.
/* Inserts ELEM in the proper position in LIST, which must be
sorted according to LESS given auxiliary data AUX.
Runs in O(n) average case in the number of elements in LIST. */
void
list_insert_ordered (struct list *list, struct list_elem *elem,
list_less_func *less, void *aux) {
struct list_elem *e;
ASSERT (list != NULL);
ASSERT (elem != NULL);
ASSERT (less != NULL);
for (e = list_begin (list); e != list_end (list); e = list_next (e))
if (less (elem, e, aux)) // less function의 인자로 elem, e, aux를 넣어준다.
break; // 멈춘다.
return list_insert (e, elem);
}
list.h/list_less_func()
리스트 원소 a와 b를 비교하는 함수의 타입을 정의한다. a의 값이 b보다 더 작다면 true를, 더 크다면 false를 리턴한다.
뒤에서 볼 cmp_priority()도 이와 같은 타입이므로, 다른 함수의 인자로 넣어줄 때 타입을 list_less_func으로 정할 수 있다(thread_unblock() 참고).
/* Compares the value of two list elements A and B, given
auxiliary data AUX. Returns true if A is less than B, or
false if A is greater than or equal to B. */
typedef bool list_less_func (const struct list_elem *a,
const struct list_elem *b,
void *aux);