[Project_1_THREADS]_Priority Scheduling_1

 

1-2 과제

Priority scheduling과 Priority donation을 Pintos에서 실행하라

 

하나의 스레드가 레디리스트에 추가되었을 때 이것이 높은 우선순위를 가지면 현재 running중인 스레드는 즉시 이 녀석에게 양보를 해주어야 한다. 

비슷하게 스레드가 lock, 세마포어 또는 Condition 변수를 기다릴때 가장 높은 우선순위를 가진 기다리는 중이던 스레드가 먼저 일어난다.

 

스레드의 우선순위는 높아지거나 낮아질 수있다.

그러나 우선순위가 낮아지게 되면 더 이상 높은 우선순위를 가 아니므로 CPU를 양보한다.

 

스레드의 우선순위 범위는 PRI_MIN(0)부터 PRI_MAX(63)까지이다.

초기 스레드의 우선순위는 thread_create()의 인수로 전달된다. 

우선순위의 변동이 필요 없는 스레드라면 PRI_DEFAULT(31)을 사용하면 된다.

 

우선순위 스케줄링?

우선순위 스케줄링을 만들 때 우선순위 반전 문제를 고려해야 한다 

우선순위 반전이란 H, M, L 각 우선순위를 가진 스레드가 있다고 했을 때 

 

 L가 A라는 자원을 쓰면서 running 하는 와중 H가 들어오면 L은 CPU를 H에게 양보한다 그런데 H도 A자원을 요구하는 상황! A를 반납받으려면 L이 돌아야 하는데 현재 ready list 에는 M이 있다.

이런 경우 H는 절대 CPU를 얻을 수 없다. 

 

이 방법을 해결하는 한 가지 방법으로는 필요자원이 lock 되어있다면 H가 자신의 우선순위를 L에게 기부해 L이 실행되도록 해주어 A를 반납하면 다시 우선순위를 회복해 H로 높여 실행하는 방법이 있다.

 

 

스레드가 자신의 우선순위를 점검 수정하는 함수를 구현하자.

 

뼈대는 treads/tread.c에 있다.

void thread_set_priority (int new_priority);

thread_set_priority( new_priority ) 현재 스레드의 우선순위를 새로 설정하는 함수

 

int thread_get_priority (void);

현재 스레드의 우선순위를 반환하고 priority donation이 있는 경우 더 높은 우선순위를 반환한다.

 

서로 다른 스레드끼리 우선순위를 직접 수정할 수 있도록 하는 인터페이스는 제공하지 않는다.

 

우선순위 스케쥴러는 나머지 프로젝트에서는 쓰이지 않는다고 한다...

 

---

최초 부여받은 우선순위만을 고려하여 우선순위 스케줄링 

우선은 현재 기본 핀토스에서 어떤 부분을 수정해야 할지 생각해 보자.

ready_list에 새로운 스레드가 push 될 때는 언제일까?

thread_unblock()

thread_yiethread_yield()

위 두 함수가 호출될 때일 것이다.

그럼 이 함수가 호출도 이 스케줄을 직접 할 때는 어떤 형식으로 이루어지고 있을까?

schedule (void) 함수를 보자

static void
schedule (void) {
	struct thread *curr = running_thread (); 
	struct thread *next = next_thread_to_run ();

	ASSERT (intr_get_level () == INTR_OFF);
	ASSERT (curr->status != THREAD_RUNNING);
	ASSERT (is_thread (next));
	/* Mark us as running. */
	next->status = THREAD_RUNNING;

	/* Start new time slice. */
	thread_ticks = 0;


#ifdef USERPROG
	/* Activate the new address space. */
	process_activate (next);
#endif

	if (curr != next) {
		/* If the thread we switched from is dying, destroy its struct
		   thread. This must happen late so that thread_exit() doesn't
		   pull out the rug under itself.
		   We just queuing the page free reqeust here because the page is
		   currently used bye the stack.
		   The real destruction logic will be called at the beginning of the
		   schedule(). */
		if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
			ASSERT (curr != next);
			list_push_back (&destruction_req, &curr->elem); //뒤로 가져다 놓는다
		}

		/* Before switching the thread, we first save the information
		 * of current running. */
		thread_launch (next);
	}
}

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);
} //ready_list 의 맨 앞의 항목을 반환 ->현재 pintos 는 ready_list 에 push 는 맨 뒤에, pop 은 맨 앞에서 하는 round-robin 방식

 

넣을 때는 list_push_back으로 뒤에서부터 넣고 뺼떄는 list_pop_front부터 하는 Round_robin 방식을 채택하고 있다.

<round_robin> 방식이 궁금하면 아래 글을 참조하길 바란다.

 

5. 프로세스 스케쥴링

 

즉 현재는 우선순위 상관없이 먼저 들어온 대로 실행 FIFO를 따른다. 우선은 정렬을 통해 현재 자신들이 가지고 있는 우선순위로만이라도 정렬을 해보도록 하자.

 

구현 

ready_list에 들어 보낼 때부터 우선순위를 맞추어서 push 하도록 해보자.

이를 위해 앞서 언급한

thread_unblock()

thread_yiethread_yield()

의 수정이 필요하다.

 

핀토스 lib/kernel/list.c를 들어가 보면 리스트 삽입시 정렬을 하는 list_insert_ordered 함수가 있다.

/* lib/kernel/list.c */
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))
		// elem<e 이면 True , elem>=e 면 False
			break;
	return list_insert (e, elem); //e의 앞에 elem이 삽입된다.
}//정렬하여 리스트에 insert하는 함수

void
list_insert (struct list_elem *before, struct list_elem *elem)
{
  ASSERT (is_interior (before) || is_tail (before));
  ASSERT (elem != NULL);
  elem->prev = before->prev;
  elem->next = before;
  before->prev->next = elem;
  before->prev = elem;
}

내용을 보면 for문으로 list의 첫 요소들 e 와 입력받은 요소 elem를 비교 less함수를 통과하면 e의 앞에 새로운 요소 elem을 삽입함을 확인할 수 있다.

현재는 새로운 요소 element 가 기존 요소보다 작다면 기존 요소의 앞에 elem이 삽입되도록 되어있다. 

우리는 elem > e 일 때 true를 반환하는 함수를 적용시켜야 한다.

 

따라서 우선순위를 비교해줄 함수 ((thread_compare_priority를 새로 만들고

thread_unblock(), thread_yiethread_yield() 함수에서 push back대신 list_insert_ordered를 넣어 이를 해결해 보자.

/* thread/thread.c */
bool 
thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED)
{
    return list_entry (l, struct thread, elem)->priority
         > list_entry (s, struct thread, elem)->priority;
}

//기존에 있던함수 
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);
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0);
	/*------------------------------------------------------------------------*/
	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 ();
	if (curr != idle_thread)
//		list_push_back (&ready_list, &curr->elem);
/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, 0);
/*------------------------------------------------------------------------*/

	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

 

 

끝이 아니다 실행 중인 running 스테드의 priority가 대기 중인 ready_list안 스레드보다 우선순위가 낮다면 현재 진행 중인 스레드는 CPU를 양보해야 한다.

이 두 가지가 일어나는경우는 아래 두가지 경우 발생한다. 

• thread_create()
• thread_set_priority()

현재 실행 중인 스레드와 레디 리스트의 가장 처음에 있는 스레드(들어오면서 정렬되었으니 맨 앞만 확인하면 된다.)를 비교하는 코드(thread_test_preemption (void))를 만들어 넣어준다.

 

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

thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;

	ASSERT (function != NULL);

	/* Allocate thread. */
	t = palloc_get_page (PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;

	/* Initialize thread. */
	init_thread (t, name, priority);
	tid = t->tid = allocate_tid ();

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t) kernel_thread;
	t->tf.R.rdi = (uint64_t) function;
	t->tf.R.rsi = (uint64_t) aux;
	t->tf.ds = SEL_KDSEG;
	t->tf.es = SEL_KDSEG;
	t->tf.ss = SEL_KDSEG;
	t->tf.cs = SEL_KCSEG;
	t->tf.eflags = FLAG_IF;

	/* Add to run queue. */
	thread_unblock (t);
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	thread_test_preemption();
	/*------------------------------------------------------------------------*/

	return tid;
}

thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	thread_test_preemption();
	/*------------------------------------------------------------------------*/
}

실행결과

이렇게 우선은 주어지는 우선순위를 가지고 간단한 우선순위 스케쥴링을 해보았다. 하지만 아직 우선순위 inversion 같은 문제가 남아있으니 다음 포스팅에서 해결해 보자

 

 

 

도움을 받은 블로그

[PintOS, Project1] Priority_Scheduling

[Pintos] Project 1 : Thread(스레드) - Priority Scheduling(1)