[PintOS] Project1: Part2 Priority Scheduling

김상호·2022년 5월 26일

jungle pintos 개발일지 정글

Development Log

목록 보기

28/45

Priority Scheduling

과제 목표

과제의 목표는 현재 라운드 로빈(Round Robin)으로 구현되어 있는 스케줄링을 우선순위 스케줄링으로 수정하는 것이다.

새로운 thread가 실행되는 thread보다 우선순위가 높다면 새로운 thread가 CPU를 차지해야 한다.

스레드 구조체에 들어가는 PRI_MIN와 PRI_MAX가 있다. 그리고 thread의 우선순위를 바꾸어 주는 함수가 들어간다.

thread_create( ) : 스레드를 생성할 때, 실행 중인 스레드와 비교하여 새로 생성한 스레드가 우선순위가 높다면 스케줄링을 해준다.
unblock과 yield를 수정한다는 것은 ready_list의 변화가 생겼을 때, 우선순위 순으로 정렬하라는 것이다. 정렬은 pintos에 구현되어 있는 list_inster_ordered( )를 사용해서 정렬하면 된다.

구현

위의 그림의 위치에 해당 함수들을 선언해준다.

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

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

위의 주석에서 설명하는 내용의 역할을 하는 것은 test_max_priority( )함수이다. create에 함수를 추가해준다.

tid_t thread_create(const char *name, int priority,
					thread_func *function, void *aux)
{
	    …
	thread_unblock(t);

	/* 생성된 스레드의 우선순위가 현재 실행중인 스레드의 우선순위보다 높다면, CPU를 양보한다. */
	test_max_priority();
	return tid;
}

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

void test_max_priority(void) {
	/* ready_list에서 우선순위가 가장 높은 스레드와
	   현재 스레드의 우선순위를 비교하여 스케줄링 */
	if (!list_empty(&ready_list)) {
		struct thread *top_pri = list_begin(&ready_list);
		if (cmp_priority(top_pri, &thread_current()->elem, NULL))
		{
			thread_yield();
		}
	}
}

thread_current()는 현재 running_thread를 가리킨다. cmp_priority()함수는 밑에서 자세히 설명하겠지만 간단히 두 인자를 비교해 매개변수에서 첫번째 인자가 크다면 TRUE를 반환 아니라면 FALSE를 반환해주는 함수이다. 즉, 실행중인 스레드보다 ready_list에 스레드가 priority가 더 크다면 스케줄링을 해준다.

두 인자 즉, ready_list에서 priority가 가장 큰 스레드와 현재 실행중인 스레드를 비교해 첫번째 인자(ready_list에서 priority가 가장 큰 스레드)가 크다면 TRUE를 반환, 아니라면 FALSE를 반환한다.

bool cmp_priority(const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED) {
	struct thread *a = list_entry(a_, struct thread, elem)->priority;
	struct thread *b = list_entry(b_, struct thread, elem)->priority;
	return a > b;
}

list_entry()함수는 처음에 이해하기 힘들었지만 위에 사진을 보면 이해하기 훨씬 쉬워질것이다. ready_list에 줄 서있는 애들은 엄밀히 말하면 스레드가 아닌 스레드 내 멤버인 list_elem이다. 따라서 list_elem만 가져온다고 해당 스레드 전체를 비교할 수는 없다.(우리가 알아야 할 건 스레드 내에 속한 다른 멤버인 priority인데 이거랑 list_elem과는 연관이 없음) 하지만 우리는 list_entry를 통해서 ready_list에 줄 서있는 해당 스레드 전체를 들고 올 수 있고 그러면 그 안에 속한 priority까지 함께 들고 올 수 있게 되는 것이다.

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

void thread_unblock(struct thread *t)
{
	    …
        
	/* 스레드가 unblock될 때, 우선순위 순으로 정렬되어 ready_list에 삽입 */
	list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
    
        …
}

list_insert_ordered할 때, 정렬 방법은 위에서 작성한 cmp_prioirty를 사용한다. list_insert_ordered는 다음과 같다. 삽입할 스레드를 리스트의 맨 앞에 넣고, 원래 맨 앞에 있던 스레드와 비교한다. 만약 삽입한 스레드가 그 스레드보다 작다면 뒤로 옮긴다.

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

void thread_yield(void)
{
		…
         
		/* 현재 thread가 CPU를 양보하여 ready_list에 삽입될 때, 우선순위 순서로 정렬하여 삽입 */
		list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);  
        
        …
}

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

void thread_set_priority(int new_priority)
{

	thread_current()->priority = new_priority;
	/* 스레드의 우선순위가 변경되었을때 우선순위에 따라
    선점이 발생하도록 한다. */
	test_max_priority();
}