[정글 Week09_PintOS] 스케쥴러 개념

 

스케쥴러는 다음에 실행할 스레드를 선택하는 역할을 하며, 아래와 같이 행동한다. 

 1️⃣ 준비된 스레드 중에서 가장 우선순위가 높은 스레드 하나를 고른다
 2️⃣ 현재 실행중인 스레드를 종료시킨다 
 3️⃣ 고른 스레드를 실행시킨다
( 2️⃣, 3️⃣은 컨텍스트 스위칭 과정! )

 

스레드 스케쥴링의 핵심: 우선순위 기반 스케쥴링(Priority Scheduling)과 선점 스케쥴링(Preemptive Scheuduling)이다!

 

---

 

1. 스케쥴링 개요

PintOS 기본 구현은 선점형 스케쥴러이다. 

스케쥴러는 Ready List에서 실행 가능한 스레드를 선택하고, 우선순위가 높은 스레드를 먼저 실행시킨다. 

현재 실행 중인 스레드보다 더 높은 우선순위를 가진 스레드가 도착하면, 현재 스레드를 중단시키고 새로운 스레드를 실행시킨다. 

static void schedule(void) 
{
    struct thread *curr = running_thread(); // 현재 스레드
    struct thread *next = next_thread_to_run(); // 다음 스레드
    struct thread *prev = NULL; // 이전 스레드
  	
    ASSERT (intr_get_level() == INTR_OFF); // ???
    ASSERT (curr->status != THREAD_RUNNING); // 현재 스레드는 실행중이지 않아야 함??? 
    ASSERT (is_thread(next)); // 다음 스레드는 스레드이다???
    
    if (curr != next) { // 현재 스레드와 다음 스레드가 다르면
    	prev = switch_threads (curr, next); // 현재 스레드와 다음 스레드를 컨텍스트 스위칭
    }
    schedule_tail(prev); // 이전 스케쥴 
}

 

 

2. 다음에 실행할 스레드 선택

ready_list가 비어있으면 idle_thread(더미 스레드)를 반환하고, 

ready_list에 스레드가 있으면 ready_list에서 가장 높은 우선순위를 가진 스레드를 선택한다.

/*
스케쥴링될 다음 스레드를 골라서 반환한다. 
단, 반드시 run queue에 있는 스레드를 반환해야 한다.
만약 run queue가 비어있으면 더미 스레드를 반환한다.
*/
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_entry()는.. 

ready_list에서 개별 노드를 추적하고 해당 노드의 부모 구조체 시작 주소를 반환하는 매크로다. 

부모 구조체 시작주소는 (LIST_ELEM)->next 주소에서 offsetof(STRUCT, MEMBER.next)을 빼서 구한다.

• offsetof(TYPE, MEMBER): MEMBER가 구조체 내에서 시작되는 바이트 오프셋을 구하는 매크로

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *) 0)->MEMBER)
#define list_entry(LIST_ELEM, STRUCT, MEMBER) ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next - offsetof (STRUCT, MEMBER.next)))

 

 

3. 우선순위 스케쥴링

스레드가 생성될 때 해당 스레드의 우선순위가 현재 실행 중인 스레드보다 높으면 현재 스레드를 강제로 중단시키고 새로 생성된 스레드를 실행시킨다. 

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_push_back(&ready_list, &curr->elem);
    curr->status = THREAD_READY;
    schedule();
    intr_set_level(old_level);
}