PintOS Project 1 Thread - Priority Schedule의 마자막
priority donnation을 구현해보자
구현 전 테스트 결과
앞으로 어디를 구현하면 어떤 결과가 나오는지 알기 위해서
지난 구현까지의 테스트 결과를 확인해보자.
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
thread.h
priority donation을 구현하기 위해 구조체 부분을 일부 수정했다.
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
int64_t wakeup_tick; // thread가 깨어날 시간
int init_priority; // thread의 초기 priority
struct lock *wait_on_lock; // thread가 기다리는 lock
struct list donations; // priority donation list
struct list_elem d_elem; // donation list element
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf; /* Information for switching */
unsigned magic; /* Detects stack overflow. */
};
sync.c 파일에서 #include "threads/thread.h"해서
thread.c에 작성된 아래 4가지 함수를 사용하기위해 원형을 헤더파일에 적어주었다.
이 함수들은 우선순위를 다루는데 사용되는 함수들이다.
bool donations_higher_priority(const struct list_elem *a_,
const struct list_elem *b_, void *aux UNUSED);
void donate_priority(void);
void remove_with_lock(struct lock *lock);
void refresh_priority(void);thread.c
static void init_thread (...)
위에서 struct thread에 선언했던 멤버변수들을
thread를 초기화할 때 같이 초기화하는 코드를 추가해주자.
int init_priority; // thread의 초기 priority
struct lock *wait_on_lock; // thread가 기다리는 lock
struct list donations; // priority donation list
struct list_elem d_elem; // donation list element
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;
strlcpy (t->name, name, sizeof t->name);
t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
t->priority = priority;
t->magic = THREAD_MAGIC;
// priority donation 관련 초기화
t->init_priority = priority;
t->wait_on_lock = NULL;
list_init(&t->donations);
}priority 관련 함수 원형 선언
앞으로 사용할 priority 관련 함수를 미리 사용하기 위해
원형을 선언해주자.
static void idle (void *aux UNUSED);
static struct thread *next_thread_to_run (void);
static void init_thread (struct thread *, const char *name, int priority);
static void do_schedule(int status);
static void schedule (void);
static tid_t allocate_tid (void);
bool donations_higher_priority(const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED);
static bool get_higher_priority(const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED);
void check_preemption(void);
void check_thread_sleep_list(int64_t os_ticks);
void thread_sleep(int64_t ticks);
void donate_priority(void);
void remove_with_lock(struct lock *lock);
void refresh_priority(void);void donate_priority(void)
현재 스레드가 획득하려는 lock에 이미 holder가 있는 경우
holder의 우선순위가 현재 스레드보다 낮은 경우
현재 스레드가 우선순위를 donate해준다.
// lock holder보다 현재 스레드의 우선순위가 높다면 우선순위를 기부한다.
void donate_priority(void){
struct thread *holder = thread_current()->wait_on_lock->holder;
for(int depth=0;depth<=8;depth++){
if(holder == NULL){
break;
}
holder->priority = thread_current()->priority;
if(holder->wait_on_lock == NULL){
break;
}
holder = holder->wait_on_lock->holder;
}
}void remove_with_lock(struct lock *lock)
donations 리스트를 확인해서 지우는 lock을 찾아서 삭제한다.
// donations 리스트에서 지울 lock을 찾아서 삭제한다.
void remove_with_lock(struct lock *lock)
{
/* donations 리스트에서 지울 lock을 찾아서 삭제한다. */
struct thread *curr = thread_current();
struct list_elem *e;
for(e = list_begin(&curr->donations);
e != list_end(&curr->donations); e = list_next(e)){
struct thread *t = list_entry(e, struct thread, d_elem);
if(t->wait_on_lock == lock){
list_remove(e);
}
}
}void refresh_priority(void)
nested priority에서 현재 스레드는 lock을 release해주고
donate받은 현재 스레드의 우선순위를 donate받기 전에 우선순위로 되돌려준 다음에
현재 스레드의 donations 리스트에 요소가 있는 경우 확인하여
현재 스레드보다 더 높은 우선순위가 있다면 그 우선순위를 현재 스레드에 할당해준다.
// donations 리스트를 확인하고 우선순위를 갱신한다.
void refresh_priority(void)
{
/* 기부받기 전의 우선순위로 초기화 */
thread_current()->priority = thread_current()->init_priority;
/* donations 리스트가 비어있지 않으면서
더 높은 우선순위의 스레드가 있다면 현재 스레드에 donate해준다.*/
if (!list_empty(&thread_current()->donations))
{
struct thread *front_thread
= list_entry(list_begin(&thread_current()->donations),
struct thread,
d_elem);
if (thread_current()->priority < front_thread->priority)
{
thread_current()->priority = front_thread->priority;
}
}
}bool donations_higher_priority(...)
struct thread속에 donations리스트의 d_elem이 가리키는 스레드의 우선순위를
내림차순으로 정렬하기 위한 비교함수를 만들었다.
list_insert_ordered(...)
list_sort(...)에 사용할 수 있다.
bool
donations_higher_priority(const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED){
const struct thread *a = list_entry(a_, struct thread, d_elem);
const struct thread *b = list_entry(b_, struct thread, d_elem);
return a->priority > b->priority;
}void thread_set_priority (int new_priority)
스레드의 우선순위를 바꾸는 경우 우선순위 priority와 donate받지 전에
우선순위 init_priority 둘 다 변경해줘야한다.
그리고 스레드의 바꾼 우선순위와 donations 리스트에 원소가 존재하는 경우
우선순위를 비교해서 donations에 가장 높은 우선순위보다 현재 스레드가 낮은 경우
현재 스레드에게 우선순위를 donate해준다.
void
thread_set_priority (int new_priority) {
thread_current ()->priority = new_priority;
thread_current ()->init_priority = new_priority;
refresh_priority();
check_preemption(); // 바뀐 우선순위가 ready_list의 최고 우선순위보다 낮으면 양도
}구현 후 테스트 결과
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain