PintOS Project1 : Threads - Alarm Clock , Priority Scheduling

 

 

PintOS가 시작되었다.. 

3주 동안 같은 조가 Project1과 2를 구현하고, 2주 동안 다른 조로 바뀌면서 Project3을 구현하게 된다.

1.5주 동안 팀원들과 페어프로그래밍하며 완성시킨 Project1 Alarm Clock고 Prioirty Scheduling에 대해 해결방법, 시행착오에 대해 작성하였다. 중요한 함수, 수정된 코드 중심이므로 다른 코드와 함수에 대해서는 코드를 보며 숙지하길 바란다.

---

⏰ Alarm Clock 

Alarm Clock에서 해결해야 할 주 된 문제

 -  First  : busy waits 피해라! 

 -  Second : 우선순위가 높은 스레드를 먼저 깨워서 먼저 실행되도록 해라!

 

busy waits 방식을 피하고 우선순위가 높은 스레드를 먼저 깨워서 먼저 실행되도록해서 테스트를 통과하는 것이 주된 목적이었다. 

test case

1. alarm-single / alarm-multiple
2. alarm-simultaneous
3. alarm-priority
4. alarm-zero
5. alarm-negative

 

 

기본 코드

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();	//현재 시간 기록
	
	//인터럽트가 활성화돼있어야 한다.
  	//에러검출용(디버깅 모드에서 개발자가 오류가 생기면 치명적일 것이라는 곳에 심어놈)
	ASSERT (intr_get_level () == INTR_ON);	
    
	while (timer_elapsed (start) < ticks)	//경과 시간이 틱보다 작은지 시간 확인 
		thread_yield ();	//cpu 양보
}

 

현재 코드는 경과 시간을 확인해서 현재 스레드가 sleep해야 할 tick 시간보다 작을 때까지 while문을 계속 돌면서 cpu를 양보하여 다른 스레드에게 실행 기회를 넘겨주고 있다. -> busy waits

 

그래서 timer_sleep 함수를 수정하여 busy waits 방식이 아닌 sleep_list를 생성해서 주어진 시간(ticks) 동안 현재 스레드를 슬립 상태로 만들어서 해당 시간이 경과하면 다시 스케줄링하는 방식으로 수정하였다.

busy waits -> 개선

 

 

수정해야 할 함수 :  thread_init() , timer_sleep() , timer_interrupt()
추가해야 할 변수 / 함수 : int64_t wakeup_tick,  struct list sleep_list  /  thread_sleep(),  thread_wakeup()

---

timer.c

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();	//현재 시간 기록
	
	ASSERT (intr_get_level () == INTR_ON);	

	// busy waits
	// while (timer_elapsed (start) < ticks) 
	// 	thread_yield ();
	
	/* Alarm Clock */
	if(timer_elapsed(start) < ticks)
		thread_sleep(start + ticks);
}

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	/* Alarm Clock */
	//매 틱마다, 스레드가 sleep_list에서 깨어나야 하는지 확인하고 깨우기 함수 호출
	thread_wakeup(ticks);
}
                                       .
                                       .

 

timer_elasped(start) 함수를 통해 현재까지 경과한 시간을 확인하고, 주어진 시간 'ticks'가 지나지 않았으면 thread_sleep() 함수를 호출해서 스레드를 잠재운다. 이때 thread_sleep 함수를 통해 해당 스레드는 sleep_list로 들어가게 된다.

 

그리고 타이머 인터럽트가 발생하면 therad_wakeup() 함수를 호출하여 슬립 상태에 있는 스레드를 깨운다. 

 

이 부분에서 헷갈렸던 점이 있었는데 그것은 바로 타이머 인터럽트는 언제 어디서 누가 발생시켜??? 였다.

 

결론은 타이머 인터럽트는 하드웨어적으로 매 시스템 클럭 주기마다 발생하고, 타이머 인터럽트가 발생할 때마다 시간이 경과했음을 운영체제에게 알리면서 스레드 스케줄링이나 타이머 기반 작업을 수행할 수 있는 것이다.

그래서 타이머 인터럽트가 발생하면 thread_wakeup() 함수를 호출하면서 매 틱마다, sleep_list에서 슬립 상태에 빠져있는 스레드를 깨워 스케줄링을 수행!

 

thread.c

void
thread_sleep(int64_t ticks){
	struct thread *curr = thread_current();
	enum intr_level old_level;

	ASSERT(!intr_context());

	old_level = intr_disable();	  //인터럽트 비활성화, 유저모드->커널모드
	curr->status = THREAD_BLOCKED;
	curr->wakeup_tick = ticks;
	
	if(curr!= idle_thread)
		list_insert_ordered(&sleep_list, &curr->elem, sleep_less , NULL); //오름차순으로 정렬
	schedule();
	intr_set_level(old_level);	//인터럽트 활성화, 커널모드->유저모드
}

//sleep_list에 들어가는 elem을 tick이 짧은 순서대로 오름차순 정렬
bool
sleep_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *ta = list_entry(a, struct thread, elem);
	struct thread *tb = list_entry(b, struct thread, elem);
	return ta->wakeup_tick < tb->wakeup_tick;
}
                             .
                             .

 

현재 스레드의 상태를 THREAD_BLOCK으로 설정해 주고, 각 스레드는 깨어나는 시간을 유지해야 하므로 wakeup_tick이라는 local tick에 주어진 시간 'ticks'을 저장한다.

그리고 현재 스레드가 idle_thread가 아닐 때까지 주어진 시간 ticks가 짧은 순으로 정렬하여 sleep_list에 삽입해 준다.

 

void
thread_wakeup(int64_t ticks)
{
	if(list_empty(&sleep_list))
		return;

	enum intr_level old_level;
	
	//sleep_list의 시작 지점에 대한 iterator를 반환하여 해당 요소를 struct thread로 캐스팅
	struct thread *sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);
	struct thread *sleep_pop_front_thread;

	//깨워야 하는 스레드 중에서 우선순위가 높은 스레드를 greater_list에 삽입
	while(sleep_front_thread->wakeup_tick <= ticks)
	{
		old_level = intr_disable();
		sleep_front_thread->status = THREAD_READY;
		
		/* alarm clock - priority */
		sleep_pop_front_thread = list_entry(list_pop_front(&sleep_list), struct thread, elem);
		list_insert_ordered(&greater_list, &sleep_pop_front_thread->elem , cmp_priority, NULL);
		
		sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);	
		intr_set_level(old_level);
	}

	while(!list_empty(&greater_list))
	{
		old_level = intr_disable();
		list_push_back(&ready_list, list_pop_front(&greater_list));
		intr_set_level(old_level);
	}
}

 

타이머 인터럽트가 발생하면 주어진 시간(ticks)이 지난 현재 슬립 상태인 스레드를 깨우고 ready_list로 이동시켜야 한다.

Second Problem이었던 우선순위 순으로 깨워서 실행해야 한다!라는 부분을 이곳에서 해결할 수 있다.

 

우리는 greater_list라는 우선순위 리스트를 따로 만들어 현재 주어진 시간이 지난 슬립 상태인 스레드들 중에서 우선순위가 높은 스레드를 greater_list에 넣고 우선순위대로 정렬이 되어있으니 이 순으로 ready_list에 넣어주면서 스케줄링하도록 구현하였다.

 

 

잠깐! 여기서 헷갈렸던 점 1🤦‍♀️

void
list_insert_ordered (struct list *list, struct list_elem *elem,
		list_less_func *less, void *aux)

 

list_insert_ordered의 함수를 보면 매개변수로 list_less_func 함수 포인터를 받고 있는 걸 볼 수 있다.

이게 뭔데 대체..! 해서 찾아보니.. 

typedef bool list_less_func (const struct list_elem *a,
                             const struct list_elem *b,
                             void *aux);

이것은 리스트의 요소들을 비교하는 비교 함수의 형식을 정의하는 typedef 문이다.

각 매개변수는 리스트의 요소를 나타내는 포인터이며, 'a'와 'b'는 비교할 두 요소를 가리키고, 'aux'는 비교에 필요한 추가적인 정보를 제공할 수 있는 매개변수인데 NULL 값을 넣어도 된다.

 

 

잠깐! 여기서 헷갈렸던 점 2🤦‍♀️

enum intr_level old_level;
old_level = intr_disable();
intr_set_level(old_level);

 

이 코드를 자주 보게 될 것이다. 이게 대체 뭐길래 현재 인터럽트를 비활성화하고 , 다시 인터럽트를 활성화하는 거야?라고 생각했었다. 무심하게 넘어갔었는데 매우 중요한 부분이었다.

 

intr_disable() 함수를 통해 현재 실행 중인 코드의 인터럽트가 비활성화된다. 이렇게 되면 현재 실행 중인 코드가 실행을 마치기 전까지 다른 인터럽트가 발생하지 않는다. 따라서 이 코드는 유저 모드에서 커널 모드로 전환되기 전에 실행된다.

intr_set_level() 함수를 통해 이전에 저장한 인터럽트 레벨을 다시 설정하여, 이전에 비활성화된 인터럽트를 활성화한다. 따라서 이 코드는 커널 모드에서 유저 모드로 전환되기 전에 실행된다.

 

 

잠깐! 여기서 알게 된 점 🙆‍♀️

//sleep_list의 시작 지점에 대한 iterator를 반환하여 해당 요소를 struct thread로 캐스팅
struct thread *sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);

 

처음에 sleep_front_thread = list_pop_front(&sleep_list)를 하면서 sleep_list에 있는 요소를 꺼냈었는데 계속 에러가 뜨고 돌아가지 않았다.

그러다 다른 동료분의 코드를 보게 되었는데 저 줄이 추가되어 있어서 물어보니 우리가 했던 방식대로 꺼내면

sleep_list (연결리스트)에 있는 첫 번째 요소에 대한 포인터를 꺼내오는 것이므로 이 요소가 포함된 struct thread 구조체로 변환해서 구조체에 대한 포인터를 반환하도록 해야 스레드를 조작할 수 있다고 한다는 점을 알게 되었다!

이 이후로 list_entry 함수를 적용해서 사용해야 하는 일이 많아진다. (아주 중요한 녀석이었다..)

 

 

테스트는 6개 다 통과하였다!

6개 중 alarm-single 결과

 

busy waits 방식이었을 경우 0개의 idle 스레드 , 288개의 커널 스레드가 실행된 것을 볼 수 있는데 

개선된 방식의 결과 250개의 idle 스레드가 실행되고 커널 스레드는 27개로 줄어든 것을 볼 수 있다.

 

idle 스레드는 시스템이 다른 작업을 수행하지 않을 때 기본적인 운영 체제 동작을 유지하도록 실행되는 특수한 스레드다.

여기서 idle 스레드가 생긴 이유는 현재 시스템이 슬립 상태이므로 아무런 작업을 수행하지 않기 때문에 생겨난 것이다. 이로써 운영 체제의 동작을 유지하면서 CPU의 사용을 최소화할 수 있게 되었다!

 

6개 중 alarm-prioirty 결과

각 스레드들의 우선순위 순으로 깨어나고 실행된 것을 볼 수 있다.

마찬가지로 idle 스레드의 동작으로 CPU 사용 최소화!

 

---

⚖️Prioirty Scheduling 

 

Prioirty Scheduling에서 해결해야 할 주된 문제

 -  First.  우선순위 스케줄링(선점, 세마포어, 잠금, 조건 변수)

 -  Second.  우선순위 기부(Prioity Donataion - Multiple, Nested, Chain)

 

현재 실행 중인 스레드보다 우선순위가 높은 스레드가 준비 목록에 추가되면 현재 스레드는 즉시 프로세서에게 스레드를 양보해야 한다( lock, semaphore, condition variable).

우선순위 역전을 고려하여 잠금에 대한 우선순위 기부를 구현해야 한다. 

 

test case

1. priority-change
2. priority-donate-one
3. priority-donate-multiple / priority-donate-multiple2
4. priority-donate-nest
5. priority-donate-sema
6. priority-donate-lower
7. priority-fifo
8. priority-preempt
9. priority-sema
10. priority-condvar

 

First . 우선순위 스케줄링(선점, 세마포어, 잠금, 조건 변수)

현재 실행 중인 스레드보다 우선순위가 높은 스레드가 준비 목록에 추가되면 현재 스레드는 즉시 프로세서에게 스레드를 양보해야 한다( lock, semaphore, condition variable)

 

thread.c

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);

	//새로 들어온 스레드와 현재 스레드의 우선순위 비교
	//새로 들어온 스레드의 우선순위가 더 높으면 ->schedule 실행 , 기존 스레드 cpu양보
	if(t->priority > thread_get_priority())
		thread_yield();

	return tid;
}

 

스레드를 생성할 때 thread_unblock() 함수를 호출하면서 해당 스레드를 언블록 하고 새로운 스레드와 현재 실행 중인 스레드의 우선순위를 비교하여 현재 실행 중인 스레드가 더 낮으면 CPU를 양보한다.

 

이러한 방식으로 thread_create 함수는 새로운 스레드를 생성하고 준비 리스트에 추가하여 우선순위 스케줄링되도록 한다.

 

void
thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t));

	old_level = intr_disable ();
	ASSERT (t->status == THREAD_BLOCKED);

	//우선순위로 정렬하여 ready_list에 삽입
	list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);

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

//우선순위내림차순 정렬
bool
cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *ta = list_entry(a, struct thread, elem);
	struct thread *tb = list_entry(b, struct thread, elem);
	return ta->priority > tb->priority;
}

 

스레드가 언블록 될 때, 우선순위 순으로 정렬하여 ready_list에 삽입한다. 우선순위 순으로 정렬하기 위해 리스트의 요소들을 비교하는 비교 함수를 만들어주었다. 

우선순위가 큰 순으로 정렬되어야 하기 때문에 내림차순으로 정렬되게끔 구현하였다.

 

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, cmp_priority, NULL);
		//list_push_back (&ready_list, &curr->elem);
	
    do_schedule (THREAD_READY);	//contenxt switching
	intr_set_level (old_level);	// 인터럽트 활성화, 커널 모드-> 유저 모드
}

 

기존의 thread_yield 함수는 현재 스레드가 idle 스레드가 아닐 때까지 ready_list에 넣어주었다면,

수정된 부분은 우선 순위 순으로 정렬해서 넣어주어야 하기 때문에 위에서 만들어놓았던 우선순위 비교 함수를 사용하였다.

 

/* 현재 스레드의 우선순위를 새 우선순위로 설정
   현재 스레드가 더 이상 가장 높은 우선 순위를 갖지 않으면 yield */
void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;

	struct thread *head_thread = list_entry(list_begin(&ready_list), struct thread, elem);
	if(thread_current()->priority < head_thread->priority)	
		thread_yield(); 
}

/* 현재 스레드의 우선순위를 반환 */
int
thread_get_priority (void) {
	return thread_current ()->priority;
}

 

기존 thread_set_priority() 함수를 수정해서 ready_list에 맨 앞에 있는(우선순위가 가장 높은) 스레드와 현재 설정된 스레드의 우선순위를 비교해서 현재 스레드가 더 이상 가장 높은 우선순위를 갖지 않으면 양보하는 코드를 추가하였다.

 

이 함수에도 우선순위를 비교하고 양보하는 코드를 넣은 이유는 현재 스레드의 우선순위가 새 우선순위로 설정되었을 때 다시 우선순위를 비교해서 ready_list에 재정렬해야 하기 때문이다.

 

여기까지 구현하면 prioirty-change, fifo, preempt test는 통과하게 된다!

-> First Problem 우선순위 스케줄링(선점)까지 해결!

 

테스트 결과

---

 

이제 sema, condition variable를 해결하기 위해서는 synh.c 파일을 수정해야 한다.

 

세마포어에서 대기 중인 우선순위가 가장 높은 스레드가 가장 먼저 깨어나야 하고,

cond_signal()이 가장 우선순위가 높은 스레드를 깨우는지 확인해야 한다.

 

synch.h

struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

 

우선 세마포어 구조체를 보면 세마포어의 값과 대기 리스트가 있는 걸 볼 수 있다.

이 대기 리스트에 들어갈 때 우선순위로 삽입되어야 함을 잊지 말고 구현하면 된다. 항상 코드를 분석하고 구현하면서 각 구조체에 무슨 변수가 들어가 있는지 보는 것이 중요한 것 같다.

 

synch.c
semaphore

 

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		//sema->waiters list에 들어갈 때 우선순위로 삽입
		list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 

세마 다운은 P 연산으로 세마 값이 양수가 될 때까지 기다렸다가 세마 값을 감소시킨다. 세마 값이 현재 0이기 때문에 sema의 대기 리스트로 들어가는데 이때 우선순위로 정렬되면서 삽입된다. 

 

왜 why? 세마포어가 양수 값이 되면서 대기리스트에 있는 현재 스레드가 깨어날 때 우선순위가 가장 높은 스레드가 깨어나야 하기 때문! 

 

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();

	if (!list_empty (&sema->waiters))
	{
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
				struct thread, elem));			
	}

	sema->value++;
	intr_set_level (old_level);	
	
	//cpu 양보
	thread_yield();
}

 

세마 업은 V연산으로 세마 값을 증가시키고, sema 대기 리스트 중 sema를 기다리는 스레드가 없을 때까지 스레드를 깨워준다.

현재 sema 대기 리스트에는 우선순위 순으로 정렬되어 있으므로 우선순위가 큰 스레드가 깨어나고, 현재 스레드는 cpu를 양보한다.

 

 

sync.c
condition variable

 

조건 변수는 동기화 기법 중 하나로, 스레드가 특정 조건이 충족될 때까지 대기해야 하는 상황에서 사용된다.

각 스레드가 락을 획득한 후에 'cond_wait()' 함수를 호출하여 조건 변수를 기다리는 상태로 전환하고, 이때 특정 조건은 'cond_signal()' 함수가 호출되는 것을 기다리는 것이다.

따라서 조건 변수는 'cond_signal()' 함수가 호출될 때까지 대기하며, 시그널이 보내지면 대기 중인 스레드 중 우선순위가 가장 높은 스레드가 깨어나게 된다.

void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_push_back(&cond->waiters, &waiter.elem);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

 

cond_wait 함수는 조건 변수를 기다리는 동안 스레드를 대기시킨다. 

 

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
	{	
		list_sort(&cond->waiters, cmp_condvar_priority, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
				struct semaphore_elem, elem)->semaphore);
	}
}

 

cond_signal 함수는 조건 변수에 신호를 보내는 함수이다.

조건 변수의 대기자 목록이 비어있지 않다면, 대기자 목록을 우선순위로 정렬하여 가장 높은 우선순위를 가진 스레드가 먼저 신호를 받을 수 있도록 한다. 그래서 가장 높은 우선순위를 가진 스레드에게 세마포어를 사용하여 신호를 보내고 이를 통해 대기 중인 스레드 중 우선순위가 가장 높은 스레드가 대기를 해제하여 실행 가능한 상태로 만들어준다.

 

//condition variable 우선순위 비교
bool
cmp_condvar_priority(const struct list_elem *a, const struct list_elem  *b, void *aux UNUSED) {
	struct semaphore_elem *sema_elem_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sema_elem_b = list_entry(b, struct semaphore_elem, elem);

	struct semaphore sema_a = sema_elem_a->semaphore;
	struct semaphore sema_b = sema_elem_b->semaphore;

	struct thread *t_a = list_entry(list_begin(&sema_a.waiters), struct thread, elem);
	struct thread *t_b = list_entry(list_begin(&sema_b.waiters), struct thread, elem);
	
	return t_a->priority > t_b->priority;
}

 

조건  변수 대기자의 우선 순위를 비교하는 부분에서 많은 시간을 할애하고 많이 헷갈리기도 했다. 

우선 조건 변수의 대기자 목록을 semaphore_elem 구조체로 캐스팅해서 조건 변수 대기자 목록에 있는 각 스레드의 대기 요소를 나타낸다.

그리고 각 요소에 해당하는 세마포어를 추출하고, 각 세마포어에서 세마포어에서 대기 중인 스레드 목록 중 첫 번째 대기자 스레드를 추출하여 스레드의 우선순위를 비교하게끔 하였다.

이 부분이 정말 헷갈리고 헷갈리고 헷갈렸다....

 

테스트 결과

 

 

---

 Second.  우선순위 기부(Prioity Donataion - Multiple, Nested, Chain)

우선순위 역전을 고려하여 잠금에 대한 우선순위 기부를 구현해야 한다. 

 

우선순위 역전은 높은 우선순위를 가진 스레드가 낮은 우선 순위를 가진 스레드가 소유한 자원을 기다리는 상황에서 낮은 우선순위 스레드가 자원을 계속 가지고 있는 경우에 발생한다.

이때 우선순위 기부를 사용하여 높은 우선순위의 스레드가 낮은 우선 순위를 가진 스레드에게 우선순위를 기부해서 높은 우선순위의 스레드가 빨리 실행될 수 있도록 한다.

 

 

마찬가지로 유튜브에 있는 카이스트 핀토스 강의를 듣고 정리하면서 코드 구현을 시작하였다.

 

One Donation(단일 기부)는 단일 고우선순위 스레드가 여러 개의 저우선순위 스레드에게 우선순위를 기부하는 것

Multiple Donation(다중 기부)는 여러 개의 고우선순위 스레드가 여러 개의 저우선순위 스레드에게 우선순위를 기부하는 것

Nested Donation(중첩 기부)는 스레드가 다른 스레드에게 우선순위를 기부하면서 스스로도 우선순위를 받는 것이다.

 

 

대기자 리스트와 wait_on_lock을 통해 multiple, nest , chain donation을 구현할 수 있다.

함수에 추가해야 할 코드에 대한 주석을 보면서 구현을 하였다. 물론 저 부분만 수정하는 것이 아닌 하다가 필요한 부분에 대해 찾아가면서 수정해야 한다.

 

thread.h

 

struct thread {
	//기존의 우선순위 저장        
	int original_priority;
    
   	//donation
   	struct lock *wait_on_lock;	//특정 스레드가 기다리고 있는 락
	struct list donations;		//donations 리스트
	struct list_elem d_elem;	//donations 리스트 요소

 

우선순위가 기부가 되고 높은 우선순위의 스레드가 실행이 종료가 되면 낮은 우선순위의 스레드는 본래의 우선순위로 돌아가야 된다. 그래서 기존의 우선순위를 저장할 변수를 구조체에 선언해 준다.

 

thread.c

 

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;			//대기상태여야 하기 때문 (아직 실행x)
	strlcpy (t->name, name, sizeof t->name);	//버퍼 오버플로우 방지 , 문자열 복사 함수
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
	t->priority = priority;
	t->magic = THREAD_MAGIC;

	//priotity, donation
	t->original_priority = priority;
	list_init(&t->donations);
}

 

original_prioirty에 현재 우선순위를 저장하고, donations list를 초기화한다.

 

void
thread_set_priority (int new_priority) {
	//donations 리스트가 비었다면 
	if(list_empty(&thread_current()->donations))
	{
		thread_current ()->priority = new_priority;
	}
	thread_current ()->original_priority = new_priority;

	struct thread *head_thread = list_entry(list_begin(&ready_list), struct thread, elem);
	if(thread_current()->priority < head_thread->priority)	
		thread_yield(); 
}

 

기부를 고려하여 우선순위를 설정해 준다.

만일 현재 스레드의 우선순위를 재설정해줬다면 original_prioirty도 재설정해줘야 하는데 이 부분을 추가를 안 해줘서 문제였던 적이 있다.. 

 

sync.c 
lock_acquire

 

이제 lock_release() 함수와 lock_acquire() 함수를 수정하면 된다!

 

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	if(lock->holder != NULL)
	{
		//wait_on_lock에 lock을 저장한다.
        	thread_current()->wait_on_lock = lock;
        
		//lock holder의 priority가 더 작으면 나의 priority를 기부
        	if(lock->holder->priority < thread_current()->priority)
            		//donoation list에 insert
            		list_insert_ordered(&lock->holder->donations, &thread_current()->d_elem,
                    				cmp_donor_priority, NULL);

		struct lock *cur_wait_on_lock = thread_current()->wait_on_lock;
		while(cur_wait_on_lock  != NULL)
		{
			if(cur_wait_on_lock->holder->priority< thread_current()->priority)
			{
				cur_wait_on_lock->holder->priority = thread_current()->priority;
				cur_wait_on_lock = cur_wait_on_lock->holder->wait_on_lock;
			}
			else
				break;
		}
	}

	sema_down (&lock->semaphore);

	//락 획득 -> 현재 쓰레드의 wait_on_lock NULL로 설정
	thread_current()->wait_on_lock = NULL;
	lock->holder = thread_current ();	//현재 스레드에 대한 잠금 획득
}

 

잠금을 사용할 수 없는 경우(락을 소유한 자가 있다) , 현재 스레드의 wait_on_lock에 해당 락을 저장하고,

lock holder의 우선순위와 현재 우선순위를 비교해서 donations 리스트에 삽입한다.

 

 

잠깐! 여기서 고생했던 점.. 🤦‍♀️

 

nest donation은 현재 스레드의 wait_on_lock->holder를 확인해서 현재 우선순위보다 작으면 계속해서 기부를 해주는데

언제까지 기부를 하느냐? wait_on_lock이 없는 스레드까지, 그리고 현재 우선순위보다 클 때 while문을 탈출하도록 구현하려고 했다.

 

초기 작성 코드

struct thread *front_td = thread_current()->wait_on_lock->holder;

while(front_td != NULL)
{
	if(front_td->priority < thread_current()->priority)
	{
		//현재 스레드를 donations 리스트에 삽입(우선순위순으로)
		list_insert_ordered(&lock->holder->donations, &thread_current()->d_elem, &cmp_donor_priority, NULL);
		front_td->priority = thread_current()->priority;
		front_td = front_td->wait_on_lock->holder;
	}
	else

		break;
}

 

이렇게 하다 보니 h -> m -> l까지 기부가 돼야 하는데, l이 조건문에 걸리게 되면서 탈출하게 되니까 l까지 우선순위 기부가 안 되는 문제가 발생했다. 되게 간단한 문제인데 머리는 안 돌아가고 그림을 계속 그려가며 해결하려고 했지만 계속해서 인터럽트 에러가 발생하거나.. 제대로 실행이 안되는 문제가 발생했었다.

 

그러다 산을 타며 점심을 먹으러 가면서 왜 안될까요... ㅠㅠ 하면서 털어놓다가 다른 동료분이 "락만 확인하면 돼요. wait_on_lock을 확인해서 null이면 어차피 holder가 없는 거니까!"라는 말에 전구가 번뜩이게 되면서 점심을 먹고 들어와서 탁탁.. 쳐보니..

 

pass test....................... 어 됐다.. 한마디에 모두들 기립박수를 쳐주는 고마운 정글러분들 🥲🥲

이 문제를 해결하니 일이 술술 잘 풀리게 된! 

 

 

수정 코드

//lock holder의 priority가 더 작으면 나의 priority를 기부
if(lock->holder->priority < thread_current()->priority)
{	
    //donoation list에 insert	
    list_insert_ordered(&lock->holder->donations, &thread_current()->d_elem, cmp_donor_priority, NULL);
}

struct lock *cur_wait_on_lock = thread_current()->wait_on_lock;

while(cur_wait_on_lock  != NULL)
{
	if(cur_wait_on_lock->holder->priority< thread_current()->priority)
	{
		cur_wait_on_lock->holder->priority = thread_current()->priority;
		cur_wait_on_lock = cur_wait_on_lock->holder->wait_on_lock;
	}
	else
		break;
}

 

스레드를 확인하는 것이 아닌 현재 스레드의 wait_on_lock을 확인하면서 현재 wait_on_lock의 holder의 우선순위보다 현재 우선순위가 더 크면 우선순위 기부를 해주고, cur_wait_on_lock을 다음으로 갱신을 해주었다.

그리고 기존에 donation list에 insert 하는 코드도 현재 내 우선순위가 더 큰 경우에 donation 리스트에 삽입해야 하니까 따로 빼주었다!!!

 

sync.c 
lock_release

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	if(!list_empty(&lock->holder->donations))
	{	
		//탐색을 위한 현재 donations 리스트에서 맨 앞 요소 확인
		struct list_elem *front_elem = list_begin(&lock->holder->donations);

		//리스트 탐색
		while(front_elem != list_end(&lock->holder->donations))
		{
			struct thread *front_thread = list_entry(front_elem, struct thread, d_elem);
			
			//해당 락 소유 쓰레드 찾기
			if(front_thread->wait_on_lock == lock)
			{
				list_remove(&front_thread->d_elem);
				front_thread->wait_on_lock = NULL;
			}			
			front_elem = list_next(front_elem);
		}

		//donations list가 비어있지 않다면 list에 있는 가장 큰 우선순위로 락 소유 스레드에게 기부 한다.
		if(!list_empty(&lock->holder->donations))
		{
			struct thread *next_thread = list_entry(list_front(&lock->holder->donations), struct thread, d_elem);
			lock->holder->priority = next_thread->priority;
		}	
		//비어있으면 원래의 우선순위로 복귀
		else
			lock->holder->priority = lock->holder->original_priority;
	}

	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

 

잠금을 해제할 때, donation 리스트를 끝까지 탐색하면서 잠금을 가지고 있는 스레드를 제거하고 donations 리스트가 비어있지 않다면 list에 있는 가장 큰 우선순위로 락 소유 스레드에게 기부를 하고, 비어있으면 원래의 우선순위로 복귀한다.

 

이 부분에서도 해당 스레드의 wait_on_lock을 NULL을 안 해줘서 고생을 했었습니다......🥲🥲

 

---

 

총 테스트 결과

 

 

mlfqs 제외해서 총 18개 통과하였다. 

시간 관계상 mlfqs는 못하였는데 그래도 내 손으로 끝까지 alarm과 priority를 해냈다는 뿌듯함이 너무 커서 아쉽지만 기분은 좋다!

처음에는 너무 막막하고 내가 이걸 할 수 있을까 했는데 조원들과 페어프로그래밍한 덕분인지 잘 끝냈다는 게 뿌듯합니다.

앞으로 남은 프로젝트들도 잘 무사히 끝낼 수 있길 바라며...