Project_1 : Threads - Priority Scheduling(3)

다음으로 동기화 기본 연산들의 스케줄링 방식을 수정하고자 한다.

Pintos에서 제공하고 있는 동기화 기본 연산은 Semaphore, Lock, Condition Variable 세 가지이다.

Semaphore

우선, semaphore 구조체를 살펴보면 value와 waiters라는 변수로 구성되어 있다.

value는 공유 자원의 수, waiters는 공유 자원을 사용하기 위해 대기하고 있는 스레드들의 리스트를 의미한다.

Priority Scheduling을 적용하기 위해서는 공유 자원을 사용하기 위해 대기하고 있는 스레드 가운데

우선순위가 가장 높은 스레드가 공유 자원을 차지할 수 있도록 만들어야 한다.

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

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

이를 위해 semaphore를 조작하는 함수 sema_down( ), sema_up( )을 수정해야 한다.

현재 sema_down( ), sema_up( ) 함수는 아래와 같이 FIFO 방식으로 구현되어 있다.

/* threads/synch.c */

/* PROJECT1: THREADS - Priority Scheduling */

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) {
		list_push_back (&sema->waiters, &thread_current ()->elem);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

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

ready_list 때와 마찬가지로 waiters에 스레드를 넣어줄 때, 우선순위를 고려하여 넣어줄 수 있도록 sema_down( ) 함수를 수정하자.

/* threads/synch.c */

/* PROJECT1: THREADS - Priority Scheduling */

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) {
		list_insert_ordered (&sema->waiters, &thread_current ()->elem, thread_compare_priority, 0);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

sema_up( ) 함수의 경우, waiters 리스트에 있는 동안 우선순위의 변동이 있을 수 있다.

따라서, thread_unblock( ) 함수를 호출하기 전에 해당 리스트를 내림차순으로 정렬할 수 있도록 한다.

그런데 unblock 된 스레드가 현재 CPU를 점유하고 있는 스레드보다 우선순위가 높을 수 있다.

thread_test_preemption( ) 함수를 실행하여 CPU를 점유할 수 있도록 한다.

/* threads/synch.c */

/* PROJECT1: THREADS - Priority Scheduling */

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

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters)){
		list_sort (&sema->waiters, thread_compare_priority, 0);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	  	
	sema->value++;
	thread_test_preemption ();
	intr_set_level (old_level);
}

Lock

lock 구조체는 holder와 semaphore 변수로 구성되어 있다. 

holder는 현재 lock을 가지고 있는 스레드를 의미한다.

lock 에서의 semaphore는 0과 1의 value를 갖는 binary semaphore를 의미한다. 

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

lock과 관련한 함수 lock_acquire( ), lock_release( )를 살펴보면 아래와 같다.

내부에서 sema_down( ), sema_up( ) 함수를 호출하는 것을 알 수 있다. 

앞서 해당 함수들을 수정하였기에 여기서 따로 수정할 필요는 없다.

/* threads/synch.c */

/* PROJECT1: THREADS - Priority Scheduling */

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

	sema_down (&lock->semaphore);
	lock->holder = thread_current ();
}

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

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

Condition Variables

마지막으로, condition 구조체는 waiters를 변수로 가진다.

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

struct condition {
	struct list waiters;        /* List of waiting threads. */
};

condition과 관련한 함수로는 cond_wait( ), cond_signal( )이 있다.

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

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

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))
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

우선, cond_wait( ) 내부를 살펴보면, list_push_back( ) 함수가 있다. 이를 list_insert_ordered( ) 함수로 바꾸어주어야 한다.

다만, 기존에는 스레드와 스레드 사이의 우선순위를 비교하는 함수를 list_insert_ordered( )의 인자로 넣어주었다.

여기서는 세마포어 waiters 리스트의 맨 앞 스레드 끼리 우선순위를 비교하는 함수가 필요하다.

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

bool sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux);


/* threads/synch.c */

/* PROJECT1: THREADS - Priority Scheduling */

bool sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED){
	struct semaphore_elem *l_sema = list_entry (l, struct semaphore_elem, elem);
	struct semaphore_elem *s_sema = list_entry (s, struct semaphore_elem, elem);

	struct list *waiter_l_sema = &(l_sema->semaphore.waiters);
	struct list *waiter_s_sema = &(s_sema->semaphore.waiters);

	return list_entry (list_begin (waiter_l_sema), struct thread, elem)->priority
		 > list_entry (list_begin (waiter_s_sema), struct thread, elem)->priority;
}

이제 이 sema_compare_priority( )함수를 list_insert_ordered( )함수의 인자로 넣어주면된다.

또한, waiters 리스트에 있는 동안 우선순위의 변동이 있을 수 있기 때문에 cond_signal( ) 함수에 list_sort( ) 함수를 추가한다.

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

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);
	list_insert_ordered (&cond->waiters, &waiter.elem, sema_compare_priority, 0);

	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

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, sema_compare_priority, 0);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}
}

지금까지 동기화 기본 연산들의 스케줄링 방식을 수정하였다.

터미널의 다음과 같이 입력하면 결과를 확인할 수 있다.