Project1 : Thread - Priority Scheduling(2)

Priority Scheduling and Synchronization

동기화 기본 연산 스케쥴링 방식 수정

• 여러 스레드가 semaphore, lock, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 CPU를 점유하도록 구현
  • 현재 Pintos는 semaphore를 대기 하고 있는 스레드들의 List인 waiters가 FIFO로 구현되어있다.
  ready_list : 실행되기를 기다리기위한 thread들
• waiters : sema-down에서 sema →value==0 즉, 사용불가 상태, 다른 사람이 쓰고있는데 waiter에서 blocked된 상태로 자고 있음 다시 sema-up 하면 깬다

Semaphore

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()수정 필요

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

💡  waiters에 thread를 넣어줄 때, 우선순위를 고려하여 넣어줄 수 있도록 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_push_back (&sema->waiters, &thread_current ()->elem);
		list_insert_ordered (&sema->waiters, &thread_current()->elem, thread_compare_priority, 0);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

💡  sema_up()함수의 경수 waiter 리스에 있는 동안, 우선순위의 변동이 있을 수 있음

따라서, thread_unblock()함수를 호출하기 전에 해당 리스트(waiters)를 내림차순으로 정렬할 수 있도록! (Pintos에서는 숫자가 클수록 우선순위가 높은것!)

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); //unblock 호출 하기전, waiter리스트를 내림차순으로 정렬 (우선순위가 바뀌었을까봐!)
		thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
	}

	sema->value++;
	intr_set_level (old_level);
}

Lock

/* include/threads/synch.h */

/* PROJECT1: THREADS - Priority Scheduling */

struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
															// 현재 lock을 가지고 있는 thread 의미함
	struct semaphore semaphore; /* Binary semaphore controlling access. */
															// 0과 1의 value 갖는 binary semaphore의미
};

lock과 관련한 함수 lock_acquire( ), lock_release( )를 확인

/* 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); //sema_down 호출!!!
	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); //sema_up 호출!!!
}

semaphore부분에서, sema_down(), sema_up() 수정하였기에, 수정할 필요 없음.

Condition Variable

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

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

: sema_compare_priority()함수생성 필요

/* 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.c */

/* PROJECT1: THREADS - Priority Scheduling */

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