티스토리 뷰

운영체제

[pintos] 2. Priority Scheduling

bowbowbow 2016. 4. 23. 11:13
[pintos] 2. Priority Scheduling

과제 목표

현재 핀토스에서는 스레드를 우선순위상관없이 실행하고 있습니다. 이 과제의 목표는 우선순위 순서대로 스레드가 실행되도록 하는 것입니다.

그럼 먼저 CPU가 어떤 순서로 스레드를 실행하는지 알아야합니다. CPU는 ready_list에 있는 스레드를 순서대로 실행합니다. 현재 핀토스에서는 ready_list에 스레드를 추가할 때 리스트에서 우선순위에 맞게 중간에 삽입하는 것이 아니라 단순히 제일 뒤에 추가하고 있습니다.


Solution


아이디어

이 문제는 ready_list에 thread를 삽입할 때 우선순위가 정렬되도록 삽입하도록 수정해서 해결할 수 있습니다. 또한 현재 CPU를 점유하고 있는 스레드의 우선순위가 ready_list에서 우선순위가 가장 높은 스레드보다 우선순위보다 낮으면 이 스레드가 CPU를 선점할 수 있도록 해야합니다.


구현

먼저 ready_list를스레드의 우선순위가 정렬되도록 하기 위해 스레드를 추가할 때 핀토스에 내장된 함수인 list_insert_ordered함수를 사용합니다. 이때 사용할 비교함수 thread_compare_priority를 를 만들어합니다.

/* pintos/src/threads/thread.c */
bool thread_compare_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;
}

이제 thread가 unblock 될 때 우선순위가 정렬되로록 ready_list에 스레드를 추가할 수 있도록 thread_unblock함수 내부에서 list_push_back을 list_insert_orderd로 교체해줍니다.

/* pintos/src/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);
//list_push_back (&ready_list, &t->elem); 이 부분 지움
list_insert_ordered (&ready_list, &t->elem, thread_compare_priority, 0); //이 부분 추가
t->status = THREAD_READY;
intr_set_level (old_level);
}

마찬가지로 현재 CPU점유 중인 스레드가 CPU 점유를 양보하고 ready_list에 스레드를 추가할 때 사용하는 함수인 thread_yield() 내부에서 ready_list에 삽입되는 부분을 list_push_back을 list_insert_orderd로 교체해줍니다.

/* pintos/src/threads/thread.c */
void thread_yield (void)
{
struct thread *cur = thread_current ();
enum intr_level old_level;

ASSERT (!intr_context ());

old_level = intr_disable ();
if (cur != idle_thread)
list_insert_ordered (&ready_list, &cur->elem, thread_compare_priority, 0); //이 부분 추가
//list_push_back (&ready_list, &cur->elem); //이 부분 삭제
cur->status = THREAD_READY;
schedule ();
intr_set_level (old_level);
}

이제 ready_list에 리스트서 가장 높은 우선순위를 가진 스레드, 즉 첫번째 스레드가 현재 CPU 점유 중인 스레드 보다 우선순위가 높으면 첫번째 스레드가 CPU를 점유해야되겠죠? 그래서 ready_list의 첫번째 스레드가 CPU 점유 중인 스레드 보다 우선순위가 높으면 CPU점유를 양보하는 함수 test_max_priority함수를 만듭니다.

/* pintos/src/threads/thread.c */
void
test_max_priority (void)
{
if (!list_empty (&ready_list) &&
thread_current ()->priority <
list_entry (list_front (&ready_list), struct thread, elem)->priority){
thread_yield ();
}
}

test_max_priority 함수는 언제 호출되야할까요? 스레드가 새로 생성되서 ready_list에 추가되거나, 현재 실행중인 스레드의 우선순위가 재 조정되는 순간에 ready_list의 첫번째 스레드가 CPU 점유 중인 스레드 보다 우선순위가 높은 상황이 발생할 수 있습니다. 따라서 스레드를 새로 생성하는 함수인 thread_create 함수와 현재 스레드의 우선순위를 재조정하는 thread_set_priority함수 의 내부에 test_max_priority()를 추가합니다. (함수의 마지막 부분에 추가하면 됩니다.)


결과

pintos/src/threads 폴더로 이동합니다.

umask 000
make clean
make
cd build
make check

위 명령어 5개를 순서대로 터미널에 입력하면 아래 스크린 샷과 같이 3개의 테스트가 추가로 통과함을 확인할 수 있습니다.

make check 결과make check 결과

umask 000을 하는 이유는 새로 생성되는 파일의 퍼미션을 777로 설정하기 위해서 입니다. make check를 할때 pintos/tests/thread에 있는 테스트 코드를 실행하며 정답과 비교하기 위해 출력 파일을 생성합니다. 이 때 출력파일을 쓸 권한이 있어야하고 기본 퍼미션으로 쓰기 권한을 할당하기 위해서 umask 000명령을 입력합니다. 777권한 까지는 줄 필요가 없지만 상용서비스를 만드는게 아니기 때문에 이렇게 했습니다.



댓글
댓글쓰기 폼