[PintOS, Project1] Priority_Scheduling

과제 목표는 우선순위 스케줄링을 사용하는 것이다. 

 

 만약 CPU에 있는 스레드보다 높은 우선순위의 스레드가 들어오면 새로운 스레드가 CPU를 차지한다.

 

 

 

 스레드 구조체에 PRI가 들어갈 것 같다. 그리고 스레드의 우선순위를 바꾸는 함수와 우선순위를 반환하는 함수가 들어간다. 

 

 

 

 thread_create() : 스레드를 생성할 때, 우선순위도 지정하도록 바꾼다. 

 

 unblock과 yield할 때 수정한다는 것은, ready_list에 변화가 있을 때 우선순위별로 정렬하라는 것이다. 이는 list_insert_ordered() 로 정렬한다.

 

 

 

우선 구현할 함수를 선언한다. 

@/include/threads/thread.h

/*-------------------------- project.1-Alarm_Clock -----------------------------*/
 void thread_sleep(int64_t);
 void thread_awake(int64_t);
 void update_next_tick_to_awake(int64_t);
 int64_t get_next_tick_to_awake(void);
/*-------------------------- project.1-Alarm_Clock -----------------------------*/

/*-------------------------- project.1-Priority Scheduling -----------------------------*/
// 현재 수행중인 스레드와 가장 높은 우선순위의 스레드의 우선순위를 비교하여 스케줄링
void test_max_priority(void);

// 인자로 주어진 스레드들의 우선순위를 비교
bool cmp_priority (const struct list_elem *a, const struct list_elem *a, void *aux UNUSED);
/*-------------------------- project.1-Priority Scheduling -----------------------------*/

@/threads/thread.c

/*-------------------------- project.1-Alarm_Clock -----------------------------*/
void thread_sleep(int64_t);
void thread_awake(int64_t);
int64_t get_next_tick_to_awake(void);
void update_next_tick_to_awake(int64_t);
bool find_less(struct list_elem *, struct list_elem *, void *);
void list_check_for_awake(struct list *, int64_t);
/*-------------------------- project.1-Alarm_Clock -----------------------------*/

/*-------------------------- project.1-Priority Scheduling -----------------------------*/
// 현재 수행중인 스레드와 가장 높은 우선순위의 스레드의 우선순위를 비교하여 스케줄링
void test_max_priority(void);

// 인자로 주어진 스레드들의 우선순위를 비교
bool cmp_priority (const struct list_elem *a, const struct list_elem *a, void *aux UNUSED);
/*-------------------------- project.1-Priority Scheduling -----------------------------*/

 

 

 

 생각해보니 이미 thread 구조체에 priority가 있고, thread_create()에도 priority의 인자가 있다. 그러면 priority 자체는 추가하지 않아도 될 것 같다. 

 

  일단 cmp_priority()부터 구현해보자. 이는 두 elem이 주어지면 해당 elem의 스레드가 가진 priority를 비교하여 a가 b보다 높다면 1을 반환하도록 한다. 

@/threads/thread.c

/*-------------------------- project.1-Priority Scheduling -----------------------------*/
bool cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
	t_a = list_entry(a, struct thread, elem);
	t_b = list_entry(b, struct thread, elem);
	if ((t_a->priority) > (t_b->priority)) ? true : false
}

 

 그리고 running 중인 스레드를 a로 주고, 새로운 스레드를 b로 주자. 그리고 list_entry로 각 elem에 대한 스레드를 받아오고 priority를 비교한다. a가 크면 1을 반환하고, b가 크면 0을 반환한다.

 

 

 

 원래는 ready_list에 넣을 때는 선입선출방식으로 정렬하기 위해 list_push_back을 사용했으나 이번에는 priority 순으로 넣을 수 있도록 list_insert_ordered()로 ready_list에 삽입한다.

@/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);
	/*-------------------------- project.1-Priority Scheduling -----------------------------*/
	list_insert_ordered(&ready_list, &t->elem, &cmp_priority, NULL);
	/*-------------------------- project.1-Priority Scheduling -----------------------------*/

	t->status = THREAD_READY;
	intr_set_level(old_level);
}

 

list_insert_ordered할 때, 정렬 방법은 위에서 작성한 cmp_prioirty를 사용한다. list_insert_ordered는 다음과 같다. 

@/libs/kernal/list.c

/* 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))
			break;
	return list_insert(e, elem);
}

 삽입할 스레드를 리스트의 맨 앞에 넣고, 원래 맨 앞에 있던 스레드와 비교한다. 만약 삽입한 스레드가 그 스레드보다 작다면 뒤로 옮긴다. 

 

 

 

 

  thread_yield()는 running_thread를 ready_list로 옮기는 작업이다. 이 때, 위와 똑같이 FIFO순이 아닌 priority순으로 정렬될 수 있도록 삽입한다. 

 

@/threads/thread.c

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
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);
		/*-------------------------- project.1-Priority Scheduling -----------------------------*/
		list_insert_ordered(&ready_list, &curr->elem, &cmp_priority, NULL);
		/*-------------------------- project.1-Priority Scheduling -----------------------------*/
		}
	do_schedule(THREAD_READY);
	intr_set_level(old_level);
}

 

 

 

 

 

 만약 running_thread의 priority가 변경되었을 때, ready_list에 running_thread보다 priority가 더 큰 thread가 있으면, 더 큰 thread가 running_thread가 될 수 있도록한다. 

 

@threads/thread.c


/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
    /*-------------------------- project.1-Priority Scheduling -----------------------------*/
    test_max_priority();
    /*-------------------------- project.1-Priority Scheduling -----------------------------*/
}

 test_max_priority()는 다음과 같다. 

 

 

 

 ready_list의 가장 priority가 높은 thread와 running_thread를 비교한다. 만약, ready_list의 thread의 priority가 더 높다면 교체한다. 이 때, 우리는 thread를 ready_list에 삽입할 때, priority 순으로 정렬되도록 삽입했기떄문에, ready_list의 가장 앞에 있는 thread가 ready_list 중 priority가 가장 높은 thread가 된다. 

 

 

@threads/thread.c

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 (run_priority < t->priority)
	{
		thread_yield();
	}
}

 thread_current()는 현재 running_thread를 가리킨다. 만약 ready_list의 thread의 priority가 더 높다면 thread_yield()로 running_thread를 ready_list로 보낸다. 그 다음 running_thread는 자동으로 ready_list 중 priority가 가장 높은 thread가 된다.