[CS] Kaist PintOS THREAD, Priority Scheduling #2

이 문서는 카이스트 핀토스 원유집 교수님의 강의를 참고하여 작성하였습니다.

이 문서는 카이스트 핀토스 프로젝트 가이드라인을 정리한 글입니다.

 

Part 1 : Threads

 

다음 세 가지를 구현한다.

1. Alarm clock

2. Priority scheduling

3. Advanced scheduler

 

#2 Priority scheduling

이번 과제에서는 다음 3가지는 구현해야 한다.

1. 스레드 우선순위에 다른 ready_list 정렬

2. 동기화 요소에 따른 wait_list 정렬(semaphore, condition variable)

3. preemption 구현

 

PintOS의 우선순위 수준은 0(PRI_MIN)에서 63(PRI_MAX)으로 64 계층으로 이루어져 있다.

숫자가 높을수록 우선순위가 높다.

스레드가 처음 생길 때의 default 값은 31(PRI_DEFAULT)이다.

 

PintOS는 다음 두 함수를 제공한다.

thread_set_priority

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

현재 스레드의 우선순위를 인자 값으로 바꾸는 함수

 

thread_get_priority

/* Returns the current thread's priority. */
int
thread_get_priority (void) {
	return thread_current ()->priority;
}

현재 스레드의 우선순위를 반환하는 함수

 

 

 

구현해야 하는 것

 

1. 스레드 우선순위에 다른 ready_list 정렬

01. thread_create

thread.c

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

	/* 중략 */

	/* Add to run queue. */
	thread_unblock (t);

	/* compare the priorities of the currently running 
	thread and the newly inserted one. Yield the CPU if the 
	newly arriving thread has higher priority*/


	return tid;
}

기존의 thread_create 함수에서 수정사항이 있다.

thread_unblock(t); 구문 이후에 우선순위와 관련된 코드를 작성해야 한다.

1. 현재 running상태의 스레드와 새로 삽입하는 스레드의 우선순위 비교

2. 만약 새로 삽입하는 스레드의 우선순위가 높다면 현재 running 상태의 스레드의 CPU 할당을 반환시킨다.

 

02. thread_unblock

thread.c

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); /* delete */
	void list_insert_ordered (&ready_list, &t->elem, cmp_priotity, NULL); /* add */
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

thread가 unblock 될 때, 우선순위에 맞게 ready_list에 삽입한다.

list_push_back 함수를 삭제하고 list_insert_ordered를 추가한다.

 

03. thread_yield

thread.c

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
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);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

현재 thread의 CPU 할당을 반환받고, 해당 thread를 우선순위에 맞게 ready_list에 삽입한다.

 

04. thread_set_priority

thread.c

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

해당 우선순위 값으로 변경하는 것뿐만 아니라, ready_list를 우선순위에 맞게 정렬(혹은 삽입)한다.

 

 

 

2. 동기화 요소에 따른 wait_list 정렬(semaphore, condition variable)

thread가 wait_list에 가게 되면, running 하는 시점에 lock에 걸려 우선순위 역전(Priority Inversion)이 발생할 수 있다.

 

struct semaphore

include/threads/synch.h

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

 

sema_init

include/threads/synch.h

/* Initializes semaphore SEMA to VALUE.  A semaphore is a
   nonnegative integer along with two atomic operators for
   manipulating it:

   - down or "P": wait for the value to become positive, then
   decrement it.

   - up or "V": increment the value (and wake up one waiting
   thread, if any). */
void
sema_init (struct semaphore *sema, unsigned value) {
	ASSERT (sema != NULL);

	sema->value = value;
	list_init (&sema->waiters);
}

Semaphore는 공유자원의 개수를 뜻하는 단순한 변수!

semaphore를 설정한다. 해당 공유자원의 개수를 value로 설정한다.

 

sema_down

include/threads/synch.h

/* Down or "P" operation on a semaphore.  Waits for SEMA's value
   to become positive and then atomically decrements it.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but if it sleeps then the next scheduled
   thread will probably turn interrupts back on. This is
   sema_down function. */
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);
}

semaphore를 요청한다. 만약 semaphore를 획득하면 value를 1 줄인다.

 

sema_up

include/threads/synch.h

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
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);
}

할당받은 semaphore를 반환한다. semaphore의 value를 1 늘린다.

 

struct lock

include/threads/synch.h

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

lock은 semaphore에 의해 구현되어있다.

lock_init, lock_acquire, lock_release 또한 semaphore에 의해 구현되어있다.

 

struct condition

include/threads/synch.h

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

initialize the condition variable data structure.

 

cond_wait

include/threads/synch.h

void cond_wait (struct condition *cond, struct lock *lock);

Wait for signal by the condition variable

 

cond_signal

include/threads/synch.h

void cond_signal (struct condition *cond, struct lock *lock UNUSED);

Send a signal to thread of the highest priority waiting in the condition variable

 

cond_broadcast

include/threads/synch.h

void cond_broadcast (struct condition *cond, struct lock *lock);

Send a signal to all threads waiting in the condition variable

 

 

05. sema_down

include/threads/synch.h

 

06. cond_wait

include/threads/synch.h

 

07. sema_up

include/threads/synch.h

 

08. cond_signal

include/threads/synch.h

 

05~08번 함수는 코드 내부에 priority 값에 맞게 정렬시키는 코드를 추가(수정)해야 한다.

05,06 insert 시점에 우선순위에 따른 정렬(삽입) 해야 한다.

07,08 waiters list 정렬해야 한다.

 

09. init_thread

thread.c

해당 함수에서 lock acquire, lock release, set priority에 대해 수정해야 한다.

>>> priority donation을 위한 자료구조를 초기화해야 한다

 

10. lock_acquire

include/threads/synch.h

만약 lock이 사용 불가능하면, 락의 주소를 저장한다.

현재 우선순위 값과 리스트(multiple donation)의 기부받은 스레드를 유지한다.

우선순위 값을 기부한다.

 

11. lock_release

include/threads/synch.h

해당 스레드를 donation list에서 remove 한다.

우선순위를 업데이트한다.

 

12. thread_set_priority

thread.c

donation을 고려하여 우선순위를 세팅해야 한다.

 

03. preemption 구현은 매 함수에서 고려해야하는 사항이다.

 

13. struct thread

thread.h

thread_set_priority에서 세팅해야할 멤버는 다음과 같다.

thread 구조체에 다음 멤버를 추가하자.

wait_on_lock : lock이 사용불가능 할 때 락의 주소를 저장하는 멤버

donations : list of Donors, 기부자들 리스트를 생성한다.

d_elem : list of Donors의 다음 기부자를 가르킨다.