[TIL] pintos 프로젝트 - 쓰레드 우선순위 문맥 전환

오늘까지 donate priority 구현을 마쳤다.

 

스케줄링에 대해 이해하는 것은 어렵지 않지만 실제로 운영체제에 어떤 요소들을 삽입하여 구현하는 것이 쉽지 않았다.

 

확실히 핀토스가 실제 운영체제보다 엄청 작은 코드량을 가지지만, 그래도 몇만줄 되는 방대한 양의 코드가 동작하는 방식을 이해하고

 

생각한 뒤 원하는 방식으로 동작하도록 코드를 짠다는 것이 굉장이 어려운 부분인 것 같다.

 

 

 

아무튼 포스팅 순서는 우리가 원하는 동작이 무엇인지 생각한 뒤

 

실제로 그것을 어떻게 구현했는지 확인해보겠다.

 

---

 

시작 전에..

 

지금까지는 FIFO 로 4틱마다 context_switching이 진행되고 있었다.

 

하지만 지금부터 priority를 도입하면 다음과 같은 상황으로 전환된다.

 

 

1. 4ticks 후 yield interrupt switch 가 true로 켜진다.

 

2. 다음 틱에 context_switching을 위해 현재 쓰레드는 yield가 실행된다.

 

3. yield()에서 현재 쓰레드를 ready_list에 집어넣고 do_schedule() 이후 schedule() 함수를 실행한다.

 

4. schedule() 함수에서 ready_list의 맨 앞 쓰레드로 context_switching한다.

 

 

 

이 상황에서 3번과 4번을 유심히 생각해보자.

 

3번 상황에서 현재 쓰레드가 ready_list에 들어가기 때문에

 

4번 상황에서 ready_list에서 지금 쓰레드가 가장 우선순위가 높다면 ready_list의 맨 앞으로 와있을 것이기 때문에

 

다시 현재 쓰레드가 실행된다.

 

 

따라서 더이상 시분할 시스템처럼 context switching 되지 않고 우선순위가 바뀌지 않는 이상

 

우선순위 순으로 thread가 일을 끝낼때 까지 쭉 진행하도록 바뀐다.

 

이 상황으로 전환했다는 것은 이후 구현을 진행하면서 점차 깨닫게 되었지만

 

처음부터 깨닫고 있었다면 조금 더 수월했을 것 같아서 기록해둔다.

 

---

 

 

 - alarm-priority

 

우리가 alarm-clock을 통해 sleep한 쓰레드를 재우고 깨우는 과정까지 진행했다면

 

이후에 alarm-priority를 반영하기 위해 해야 할 과제는 일단 다음과 같다.

 

0. ready_list에 특정 쓰레드가 삽입되는 순간마다 현재 스레드와 비교하여 context_switching 하기

-> check_running_priority() 를 통해 구현

 

1. ready_list 를 priority 가 높은 순으로 정렬

-> bool thread_more_priority() 로 정렬 기준 함수를 구현 + 해당 함수를 통해 insert_ordered()로 정렬 삽입

 

2. thread_set_priority() 에 의해 현재 스레드의 우선순위가 변경되면 즉시 전환

 

---

 

+ check_running_priority()

 

0번을 위한 함수로 다음과 같이 구현했다.

 

void check_running_priority(void){
	enum intr_level old_level;
	
	if (list_empty(&ready_list) == true)
		return;

	old_level = intr_disable ();
	struct thread *curr = running_thread();
	struct thread *ready_head = list_entry(list_begin(&ready_list),struct thread,elem);
	if(curr->priority < ready_head->priority) {
		list_insert_ordered(&ready_list,&curr->elem,thread_more_priority,NULL);
		curr->status = THREAD_READY;
		schedule();
	}
	intr_set_level (old_level);
}

 

해당 함수는 현재 쓰레드가 ready_list에 있는 쓰레드보다 우선순위가 낮다면 즉시 schedule()을 통해 context switching 하는 역할을 한다.

 

이 함수는 set priority로 우선순위가 변경되었을 때,

 

그리고 메인함수가 쓰레드를 만들어서 ready_list로 삽입했을 때 실행되도록 배치했다.

 

 

*** 유의할 점 ***

 

tid_t
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);
	check_running_priority();

	return tid;
}

 

해당 함수는 thread를 생성하는 thread_create()이다.

 

맨 마지막을 보면 thread_unblock() 이후 check_running_priority() 함수를 사용하여

 

방금 ready_list로 들어간 쓰레드가 우선순위가 현재 쓰레드보다 높은지 확인하고 필요하다면 switching을 수행하게 했다.

 

근데 문제는 thread_unblock 안에 넣었더니 error가 발생한 것이다.

 

 

그 이유는 thread_unblock()에서 인터럽트를 꺼주어서 발생한 것이 아닌가 해서 인터럽트가 켜진 하단에서 진행했는데 똑같았다.

 

왜 thread_unblock()에서 check_running_priority()를 하면 안되는지 아시는 분이 계시다면 댓글 부탁드립니다.

 

 

---

 

 

+ thread_set_priority()

 

이 코드는 현재 진행중인 쓰레드의 우선순위를 강제로 변경시키는 함수이다.

 

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
	struct thread *curr = thread_current();
	curr->priority = new_priority;
	check_running_priority();
}

 

원래 current_thread의 priority 를 new_priority로 변경하는 줄만 있었는데

 

해당 함수 맨 마지막에 check_running_priority()를 추가했다.

 

현재 쓰레드가 갑자기 우선순위가 낮아져 ready_list 안에 있는 쓰레드보다 후순위라면 즉시 context_switching을 해주기 위해서였다.

 

 

 

---

 

++ bool thread_more_priority()

이 함수는 ready_list를 priority 순으로 내림차순으로 정렬해주기 위해 구현했다.

 

/* ready_list를 높은 우선순위 순으로 정렬하는 bool 함수 */
bool
thread_more_priority (const struct list_elem *a_, const struct list_elem *b_,
            void *aux UNUSED) 
{
  const struct thread *a = list_entry (a_, struct thread, elem);
  const struct thread *b = list_entry (b_, struct thread, elem);
  
  return a->priority > b->priority;
}

 

이전 포스팅에서 wake_time을 오름차순으로 정렬해준 것 처럼

 

return의 비교연산자를 수정하여 내림차순으로 정렬할 수 있는 함수를 만들었다.

 

결과적으로 list_insert_ordered() 함수에 이 bool 함수를 인자로 사용하여 list에 priority 내림차순 정렬이 가능했다.

 

 

 

---

 

 

최종적으로 수정된 alarm-sleep&wake 의 관련 함수들

 

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_insert_ordered(&ready_list,&t->elem,thread_more_priority,NULL);
	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_insert_ordered (&ready_list, &curr->elem,thread_more_priority,NULL);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}


/* 쓰레드를 sleep_list에 넣어주자 */
void thread_sleep_and_yield(void) {
	struct thread *curr = thread_current();
	
	if (curr != idle_thread)
		list_insert_ordered(&sleep_list,&curr->elem,thread_less,NULL);
		if (list_begin(&sleep_list) == &curr->elem){
			min_wake_ticks = curr->wake_time;
		}
		curr->status = THREAD_SLEEPING;
		schedule ();
}


/* 일어나야 하는 쓰레드를 전부 깨워보자.*/
void time_to_wake (void){
	int64_t now_time = timer_ticks();
	if (min_wake_ticks > timer_ticks){
		return;
	}
	struct thread *t;
	struct list_elem *telem;

	for(telem=list_begin(&sleep_list); telem!=list_end(&sleep_list);) {
		t = list_entry (telem, struct thread, elem);
		if(t->wake_time <= now_time){
			telem = list_remove(telem);
			list_insert_ordered(&ready_list,&t->elem,thread_more_priority,NULL);
			t->status = THREAD_READY;
			t->wake_time = 0;
		}
		else {
			struct list_elem *min_wake_elem = list_begin(&sleep_list);
			struct thread *min_wake_thread = list_entry(min_wake_elem, struct thread, elem);
			min_wake_ticks = min_wake_thread->wake_time;
			break;
		}
	}
}

 

해당 함수들의 공통점은 모두 ready_list에 쓰레드를 삽입하는 작업이 있다는 것이고

 

모두 push_back에서 insert_ordered로 변경하여 우선순위 내림차순으로 모두 정렬되도록 하였다.