PintOS Project 1.2(1) - Priority Scheduling(정글사관학교 57일차 TIL)
이어서 바로 과제 2 진행. 과제 1 겨우 끝내고 2를 보니 만만해보였는데 양이 엄청 산더미였더라..하지만 쫄지 않고 몰입 간드아
1. 과제 목표: RR(라운드 로빈) 방식의 스케쥴링을 Priority Scheduling 방식으로 수정
위 과제를 이해하기 위해서는 간단하게 RR과 Priority Scheduling 방식에 대한 이해가 필요하다. (추후 다시 정리 예정) 여기서는 FCFS, SJF는 다루지 않겠다.
CPU 스케쥴링이란, 비싼 자원인 CPU를 어떻게든 효율적으로 사용해 최대한의 퍼포먼스를 내기 위해 고안된 방식이다. 쉽게 말해 "얼마나 CPU한테 단위 시간 당 많은 일을 시킬 것인가?"인데, 단순히 많이 일하는 것만이 능사는 아니다. 1) CPU 이용률, 그리고 주어진 시간 동안 몇개의 일을 완료했는지를 나타내는 2) 처리량도 중요하지만 이는 운영체제 입장에서의 성능 척도이다.
고객(=프로그램)입장에서는 무엇이 중요할까? CPU를 빨리 얻어서 빨리 일을 끝내는 게 좋기에 시간 관련 척도(소요시간, 대기시간, 응답시간)를 중요하게 생각한다.
이 중, Round Robin 방식은 현대 컴퓨터가 쓰는 방식으로 각 프로세스에 동일한 양의 할당 시간(time quantum)을 배정한다. 할당 시간이 끝나면 CPU는 다른 프로세스에게 선점당하고(=뺏기고) 방금까지 작업 중이던 프로세스는 ready queue의 맨 뒤로 가서 줄을 선다. 이러면 모든 프로세스가 조금씩 일을 할 수 있어 위의 척도 중 응답시간이 줄어든다는 장점이 있다.
이를 Priority Scheduling으로 바꾸라는 것인데, Priority Scheduling은 각 프로세스마다 우선순위를 배정해 가장 높은 우선순위를 갖는 프로세스한테 CPU를 먼저 배정하는 방식이다. 여기서 선점형(Preemptive) / 비선점형(Non-Preemptive)로 나뉘며 선점형은 "우선순위가 더 높은 프로세스가 들어오면 CPU를 뺏어서 주는" 방식, 비선점형은 아무리 높은 우선순위를 갖는 CPU가 들어와도 해당 프로세스를 완료하기 전까지는 CPU를 넘겨주지 않는 방식이다. 일단 과제 관련 배경 지식은 요정도로 정리.
설명을 보면, 기존 라운드 로빈 방식에서는 비선점형으로 더 높은 우선순위를 갖는 스레드가 들어와도 cpu를 빼앗기지 않는다. 여기에 priority scheduling을 적용해 더 높은 우선순위를 갖는 스레드가 들어오면 기존에 작업하던 thread를 ready_list에 넣고 새 thread한테 스케쥴링을 진행하면 되겠네. 스케쥴링 함수는 이미 갖고 있는 게 있으니 우선순위를 비교하고 배치만 변경해주는 애들만 추가하면 되겠다.
2. 과제 훑기: 함수 skimming
추가 함수
추가로 구현해야 하는 함수는 위 두 가지이다. 기존에는 우선순위를 비교하지 않으니 비교하는 함수, 그리고 비교 후 실제로 스케쥴링을 변경해주는 함수가 추가된다.
수정 함수
과제 솔루션
thread_create(): 새로 추가된 스레드가 실행 중인 스레드보다 우선순위가 높을 경우 CPU를 선점하도록 하기 위해 thread_create()를 수정한다. 이따 라인 바이 라인으로 보겠지만, thread_create()에는 priority가 인자로 들어가긴 하나 create 함수 내에서 우선순위를 가지고 재배치하는 내용은 들어있지 않다. 하지만 스레드 생성시 초기화할 때, 인자로 받은 스레드의 priority 값을 구조체 내 멤버로 정의되어 있던 priority에 배치하는 내용이 들어있다. 이를 기반으로 코드를 작성하면 되겠다.
thread 구조체 정의
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */init_thread() (t->priority = priority;)
/* Does basic initialization of T as a blocked thread named
NAME. */
static void
init_thread (struct thread *t, const char *name, int priority) {
ASSERT (t != NULL);
ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
ASSERT (name != NULL);
memset (t, 0, sizeof *t);
t->status = THREAD_BLOCKED;
strlcpy (t->name, name, sizeof t->name);
t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
t->priority = priority;
t->magic = THREAD_MAGIC;
}thread_unblock(), thread_yield(): ready_list를 들어온 순서가 아닌 우선순위로 정렬하기 위해 해당 함수를 수정한다. 현재 코드를 보면 thread_unblock()은 list_push_back()으로 해당 스레드를 리스트 맨 뒤로 넣는 것을 볼 수 있다. (아직 수정 전임!)
thread_unblock, thread_yield(수정전)
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable (); // interreput disable
ASSERT (t->status == THREAD_BLOCKED);
list_push_back (&ready_list, &t->elem);
t->status = THREAD_READY;
intr_set_level (old_level);
}
void
thread_yield (void) {
struct thread *curr = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable (); // 인터럽트를 비활성하고 이전 인터럽트 상태(old_level)를 받아온다. 조교님 설명 체크
if (curr != idle_thread) // 현재 스레드가 idle 스레드와 같지 않다면
list_push_back (&ready_list, &curr->elem); // ready리스트 맨 마지막에 curr을 줄세워.
do_schedule (THREAD_READY); // context switch 작업 수행 - running인 스레드를 ready로 전환.
intr_set_level (old_level); // 인자로 전달된 인터럽트 상태로 인터럽트 설정하고 이전 인터럽트 상태 반환
}
그럼 본격적으로 과제를 진행해보자.
3. Priority Scheduling 구현
구현할 함수 선언
새로 구현해야 하는 우선순위 비교 및 스케쥴링 함수를 선언한다.
@/include/threads/thread.h
/* ----Project 1.2: Priority Scheduling---- */
void test_max_priority (void);
bool cmp_priority (const struct list_elem *a,
const struct list_elem *b,
void *aux UNUSED);
구현 함수 추가
bool cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
이어서 곧바로 작성한다. 먼저 cmp_priority. 두 스레드 a, b를 비교해 우선순위가 더 높다면 1을 반환하고 그렇지 않으면 0을 반환하게 한다. list_entry()는 재밌는 애인데, list_elem(리스트 내 element)를 가리키는 구조체에 대해 해당 구조체를 가리키는 포인터를 가지고서 그 구조체가 속한 스레드 전체를 가져오는 함수이다. 우리는 ready_list 내에 줄 서있는 스레드를 비교해야 하는데, 리스트 내에 있는 스레드를 가리키고 있는 건 list_elem이다. 이에 대해 불냥이님 블로그에 자세한 설명이 있으니 참고. 아래에 이미지를 들고 왔으니 저것만 봐도 대략 감이 온다.
쉽게 말해 ready_list에 줄 서있는 애들은 엄밀히 말하면 스레드가 아닌 스레드 내 멤버인 list_elem이다. 따라서 list_elem만 가져온다고 해당 스레드 전체를 비교할 수는 없다.(우리가 알아야 할 건 스레드 내에 속한 다른 멤버인 priority인데 이거랑 list_elem과는 연관이 없음) 하지만 우리는 list_entry를 통해서 ready_list에 줄 서있는 해당 스레드 전체를 들고 올 수 있고 그러면 그 안에 속한 priority까지 함께 들고 올 수 있게 되는 것.
/* --- Project 1-2. Priority Scheduling --- */
/* t_a와 t_b의 우선순위를 비교해 더 높은 애면 1을 반환*/
bool cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
struct thread* t_a;
struct thread* t_b;
t_a = list_entry(a, struct thread, elem);
t_b = list_entry(b, struct thread, elem);
return ((t_a->priority) > (t_b->priority)) ? true : false;
}
수정 함수
thread_unblock(): thread가 unblock되어서 새로 ready_llist에 들어올 때, 원래는 ready_list의 맨 뒤로 들어왔다면 이제는 list내에서 순서를 체크한 다음, 우선순위를 기준으로 적정한 위치에 자리한다. 이때, 기존에 정의된 함수인 list_insert_ordered()를 이용한다. (직접 짜야하는 줄 알고 식겁했네..)
void
thread_unblock (struct thread *t) {
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable (); // interreput disable -> 인터럽트 끈다.
ASSERT (t->status == THREAD_BLOCKED);
/* --- Project 1.2 --- */
// list_push_back (&ready_list, &t->elem); 맨 뒤로 넣을 필요 없으니 삭제
list_insert_ordered(&ready_list, &t->elem, &cmp_priority, NULL);
t->status = THREAD_READY;
intr_set_level (old_level);
}list_insert_ordered() 함수는 아래와 같다.(반복문 돌기 싫어서 어떻게든 짱구 굴렸는데 여기서도 그냥 for문 ^_^...)
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))
break;
return list_insert (e, elem);
}
thread_create(): thread_create()에서는 스레드에 페이지(메모리)를 할당하고 스레드를 초기화한다. 이어서 unblock을 진행하는데, (엥 근데 지금 막 생성된 갓난애기 스레드인데 왜 block도 안했는데 unblock을 하죳!?) unblock 기능 자체가 ready queue에 줄세우는 기능을 포함하기에 그런 것으로 보인다. 주석에도 "Add to run queue."라고 써있는 걸 보면 이게 맞는듯.
먼저, 정의 부분에서 현재 실행중인 스레드(thread_current())와 비교해야 하니 curr을 하나 선언한다. 그 다음, 아래와 같이 새로 생성한 thread t를 unblock시켜서 ready queue에 줄세운다. 이후 priority를 비교한다. 현재 실행중인 thread의 경우 바로 직전에 ready queue에 있었을 당시 가장 높은 우선순위를 지녔을 것이다. 여기서 지금 생성한 스레드의 우선순위가 thread_current보다 높다면 list_insert_ordered()로 ready queue의 맨 앞에 와있을 것이다. 거기서도 모잘라서 현재 실행중인 curr보다 우선순위가 높으니 thread_yield()를 실행하면 다음 차례로 기다리고 있는 건 막 생성한 스레드가 될 것이다.
tid_t
thread_create (const char *name, int priority,
thread_func *function, void *aux) {
struct thread *t;
struct thread *curr = thread_current();
tid_t tid;
/* Add to run queue. */
thread_unblock (t);
/* --- pjt 1.2 --- */
if (cmp_priority(&t->elem, &curr->elem, NULL)) {
thread_yield();
}
/*
thread unblock 후 현재 실행중인 thread와 우선순위 비교해서
새로 생성된 thread 우선순위 높으면 thread_yield() 통해 cpu 양보
*/
return tid;
}
thread_yield()
얘는 간단하다. 원래는 현재 돌고 있는 Thread를 리스트 맨 뒤에 삽입했다면 이번에는 우선순위를 반영해 리스트 내 적당한 위치에 자리하게 하면 된다. 이전에 썼던 list_insert_ordered()를 이용한다.
/* 현재 running 중인 스레드를 비활성화 시키고 ready_list에 삽입.*/
void
thread_yield (void) {
struct thread *curr = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable (); // 인터럽트를 비활성하고 이전 인터럽트 상태(old_level)를 받아온다. 조교님 설명 체크
if (curr != idle_thread) // 현재 스레드가 노는 스레드가 아니면
list_insert_ordered(&ready_list, &curr->elem, &cmp_priority, NULL); // 우선순위대로 ready queue에 배정
//list_push_back (&ready_list, &curr->elem); ready리스트 맨 마지막에 curr을 줄세워.
do_schedule (THREAD_READY); // context switch 작업 수행 - running인 스레드를 ready로 전환.
intr_set_level (old_level); // 인자로 전달된 인터럽트 상태로 인터럽트 설정하고 이전 인터럽트 상태 반환
}
thread_set_priority()
기존에 있는 함수인 thread_set_priority()는 아래처럼 새로 짤 함수 text_max_priority()를 추가해준다.
/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
thread_current ()->priority = new_priority;
/* --- Pjt 1.2 --- */
test_max_priority();
}
test_max_priority()
위에 thread_create()에서 짠 내용이 사실 여기에 그대로 담긴다. (이걸 보니 thread_create()를 수정하지 않아도 되는듯...? 다시 체크)
현재 돌고 있는 thread의 priority를 받고 ready_list 맨 앞에 있는 가장 우선순위가 높은 thread의 값과 비교해 thread_yield를 실행한다. thread_current의 다음 타자는 ready_list 맨앞에 있는 t일테니 이놈의 우선순위가 더 높다면 그대로 이어받을 것이다.
void test_max_priority (void){
if (list_empty(&ready_list)) {
return;
}
int run_priority = thread_current()->priority;
struct list_elem *e = list_begin(&ready_list);
struct thread *t = list_entry(e, struct thread, elem);
if (t->priority > run_priority) {
thread_yield();
}
}결과는 패스. thread_create()에도 만들어주는 게 맞는듯.
