아직 alarm 기능을 구현하지 못했다면 우선 이전 포스트를 확인해보세요.
🎨 우리는 지금까지 Pintos 의 스케쥴링이 Round-Robin + Busy-waiting 으로 구현되어있는걸 확인했고 Busy-waiting 을 sleep 기반으로 바꿔주었어요.
모든 상황에서 sleep 이 busy-waiting 보다 좋은 건 아니지만 두 가지 방법을 모두 알았으니, 상황에 맞게 적절하게 사용하면 돼요.
Round-Robin 방식의 문제점
Round-robin은 분명 좋은 스케쥴링 방식이지만 문제점이 존재해요.
어떤 쓰레드든 모두 일정한 간격으로 실행되기 때문에 빨리 처리되어야 할 쓰레드가 있어도 다른 쓰레드를 기다릴수가 있어요.
thread A는 아주 빨리 처리되어야 할 작업이예요. 예를 들면 사용자 UI 인터럽트나, 비행기, 의료기기 등에서 사용되는 아주 빨리 처리되어야 할 작업이요.
하지만 Round-Robin 방식만으로는 그런 문제를 해결할 수가 없었어요.
그래서 여기에 Priority 방식이 추가돼요.
thread 별로 우선순위를 부여해서 우선순위가 높은 thread 먼저 처리하는 거예요.
thread마다 우선순위를 부여해서 가장 우선순위가 높은 쓰레드를 ready_list 에서 꺼내면 돼요.
그리고 ready_list 에 thread가 하나 추가 될 때 마다 ready_list 를 정렬해줘요. 왜냐하면
/* thread.c 파일 */
static struct thread *
next_thread_to_run (void) {
if (list_empty (&ready_list))
return idle_thread;
else
return list_entry (list_pop_front (&ready_list), struct thread, elem);
}다음 스케쥴될 thread를 선택하는 next_thread_to_run 함수가 ready_list 의 가장 앞에 있는 쓰레드를 선택하니까요.
priority 스케쥴링으로도 해결할 수 없는 문제
이렇게 우선순위가 높은 thread를 먼저 처리하면 너무 좋지만, 처리될 수 없는 문제도 있어요.
바로 동기화문제로 발생하는 우선순위 역전 현상이예요.
🤔 동기화란?
동기화는 OS가 공유자원에 대해서 여러 쓰레드가 동시에 접근하는 것을 막는거예요.
대표적으로 인터럽트를 끄거나, 세마포어, 락 등으로 관리해요.
lock 에는 wait_list가 있어서 쓰레드가 그곳에서 대기하게 됩니다.
위 그림은 대표적인 우선순위 역전 현상이예요.
우선순위가 thread C > thread B > thread A 순으로 높아서
C > B > A 순으로 실행돼야 해요.
하지만 A가 lock을 들고 있어서 C가 어쩔 수 없이 ROCK의 wait_list에서 대기하게 되었습니다.
근데 B는 lock이 필요가 없고 A보다 우선순위가 높아서 더 빨리 실행됐어요.
그래서 실제로 실행되는 순서는
B > A > C 가 됐습니다. 아이러니 하네요.
이 문제를 해결하기위해 Priority-donation 이 등장했습니다.
Priority-donation
지금 문제는 B가 우선순위가 더 낮은데도 가장 우선해서 실행된다는 거예요.
그렇다면 일단 C의 우선순위를 A한테 기부해주면 어떨까요?
다행히도 ROCK 에는 그 LOCK 을 들고있는 holder의 정보가 있어서 우선순위를 전달해 줄 수 있었어요.
A의 우선순위가 c보다 낮기 때문에 기부를 통해서 정상적인 우선순위로 실행될 수 있었습니다. 락은 기다려야겠지만요
A > C > B 순서로 thread가 실행되게 됩니다.
이 개념이 "우선순위 기부"입니다.
이 부분을 완성하고 나면 priority-donation 까지의 테스트가 통과하게 돼요.
각각의 테스트에서는 단순히 하나의 락에 기부하는 경우 말고 다른 여러가지 경우가 있어요.
- wait_list에 있는 lock 중에서 가장 높은 우선순위가 기부되었는지?
- wait_list에서 기다리고 있는 thread 의 우선순위가 변경된다면?
- lock 의 holder가 다른 lock 을 기다리고 있다면?
이런 모든 예외사항을 한번 고려하며 직접 작성해보고 도저히 구현이 안된다면 밑의 코드를 보세요.
/* thread.h 파일 */
struct thread {
/* thread.c가 소유 */
tid_t tid; /* 스레드 식별자 */
enum thread_status status; /* 스레드 상태 */
char name[16]; /* 이름 (디버깅 목적) */
int priority; /* 실제 비교에 사용되는 priority */
/* thread.c와 synch.c가 공유 */
struct list_elem elem; /* 리스트 요소 */
/* project 1.1 alarm wakeup 을 위한 구조체 */
int64_t ticks; /* wake up time */
/* project 1.3 priority_donation 을 위한 구조체 */
int origin_priority; /* 쓰레드 생성 시 받은 priority */
struct list donation_list; /* 나한테 기부한 쓰레드 목록 ( 내 우선순위 보다 큰 값만 )*/
struct list_elem donation_elem; /* 여러 donation list 와 연결될 수 있는 */
struct lock *waiting_lock; /* 내가 기다리고 있는 락 */
}
/* project 1.3 priority 를 위한 커스텀 함수 */
bool cmp_prioirty(const struct list_elem * a, const struct list_elem * b, void * aux);
int thread_max_priority(struct thread *t);/* thread.c 파일 */
tid_t
thread_create (const char *name, int priority,
thread_func *function, void *aux) {
/* ... 이전 코드 */
/* 현재 쓰레드와 방금 입력된 쓰레드를 비교해서 실행 쓰레드를 갱신합니다. */
if ( parent->priority < t->priority ) {
intr_set_level(old_level);
thread_yield();
} else {
intr_set_level(old_level);
}
return tid;
}
/*
project 1.3 priority 를 위한 함수
리스트를 prioirty 로 오름차순 정렬 insert 할 때 사용합니다.
a는 새로 입력된 쓰레드 b는 기존에 리스트에 있던 쓰레드 입니다.
*/
bool
cmp_prioirty(
const struct list_elem * a,
const struct list_elem * b,
void * aux
) {
int new_prioirity = list_entry(a, struct thread, elem)->priority;
int list_priority = list_entry(b, struct thread, elem)->priority;
return new_prioirity > list_priority;
}
/* CPU를 양보합니다. 현재 스레드는 잠들지 않으며
스케줄러의 판단에 따라 즉시 다시 스케줄될 수 있습니다. */
void
thread_yield (void) {
/* .. 이전 코드 */
// 현재 스레드가 유휴 스레드가 아니면 ready_list 에 넣습니다.
if (curr != idle_thread)
/* 특히 이부분을 바꿔줘야 합니다. 지금은 list_push_back으로 되어있을 겁니다. */
list_insert_ordered(&ready_list, &curr->elem, cmp_prioirty, NULL);
/* .. 이후 코드 */
}
/*
project 1.3 priority_donation 에서 필요한 쓰레드에서 가장 높은 우선순위를 반환하는 함수
*/
int
thread_max_priority (struct thread *t) {
if ( list_empty( &t->donation_list ) ) {
return t->origin_priority;
} else {
return max (
t->origin_priority,
list_entry(list_begin(&t->donation_list), struct thread, donation_elem)->priority
);
}
}
/* 현재 스레드의 우선순위를 NEW_PRIORITY로 설정합니다. */
/* 현재 스레드의 우선순위를 새 우선순위로 설정합니다. */
/* 만약 현재 스레드의 우선순위가 더 이상 높지 않으면 우선순위를 양보합니다. */
void
thread_set_priority (int new_priority) {
enum intr_level old_level = intr_disable();
struct thread *t = thread_current();
t->origin_priority = new_priority;
t->priority = thread_max_priority(t);
/* TODO : priority 가 변경된 후 , donation_list 를 살펴보고 가장 높은 걸로 갱신? */
if ( t->priority < list_entry(list_begin(&ready_list), struct thread, elem)->priority ) {
intr_set_level(old_level);
thread_yield();
} else {
intr_set_level(old_level);
}
}
/* 현재 스레드의 우선순위를 반환합니다. */
/* 우선 순위 기부가 있는 경우 더 높은 (기부된) 우선순위를 반환합니다. */
int
thread_get_priority (void) {
return thread_current ()->priority;
}/* synch.c 파일 */
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) {
/* project 1.3 priority 를 위해 변경된 함수 */
list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_prioirty, NULL);
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)) {
list_sort(&sema->waiters , cmp_prioirty, NULL );
struct thread *t = list_entry ( list_pop_front (&sema->waiters), struct thread, elem);
thread_unblock(t);
}
sema->value++;
intr_set_level (old_level);
thread_try_yield();
// thread_yield();
}
/*
project 1.3 priority_donate 를 위해 추가된 함수
이 함수는 내가 필요한 lock을 가지고 있으면서, 나보다 낮은 우선순위를 가진 쓰레드에게
자신이 가진 우선순위를 재귀적으로 기부합니다.
*/
void
priority_donate( struct thread *curr, struct thread* holder ) {
/* 우선순위를 기부받았는데 기다리는 락이 있을 경우 */
if (
holder->waiting_lock != NULL &&
holder->waiting_lock->holder->priority < curr->priority
) {
holder->waiting_lock->holder->priority = curr->priority;
priority_donate(curr , holder->waiting_lock->holder );
}
}
/* LOCK을 획득합니다. 필요한 경우 사용 가능해질 때까지 슬립합니다.
락은 현재 스레드가 이미 보유하고 있어서는 안 됩니다.
이 함수는 슬립할 수 있으므로 인터럽트 핸들러 내에서 호출되어서는 안 됩니다.
이 함수는 인터럽트가 비활성화된 상태에서 호출될 수 있지만, 슬립해야 하는
경우 인터럽트가 다시 켜집니다. */
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
/* project 1.3 priority_donation 을 위해 추가된 코드 */
enum intr_level old_level = intr_disable();
struct thread *curr = thread_current();
/*
누가 락을 들고 있으면 내가 어떤 락을 기다리는지 체크
추후 thread_set_priority 가 일어났을 때, 변경해주기 위해서
*/
if ( lock->holder != NULL ) {
curr->waiting_lock = lock;
/* 내 priority 가 더 높은 경우만 기부를 한다. */
if ( lock->holder->priority < curr->priority ) {
lock->holder->priority = curr->priority;
list_push_front(&lock->holder->donation_list , &curr->donation_elem);
/* TODO: holder의 donate_list에 넣어줄 함수 */
priority_donate(curr , lock->holder);
}
}
intr_set_level(old_level);
sema_down (&lock->semaphore);
lock->holder = thread_current ();
}
/* 현재 스레드가 소유해야 하는 LOCK을 해제합니다.
이것은 lock_release 함수입니다.
인터럽트 핸들러는 락을 획득할 수 없으므로, 인터럽트 핸들러 내에서
락을 해제하려고 시도하는 것은 의미가 없습니다. */
void
lock_release (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
/* proect 1.3 priority_donation 을 위해 추가된 코드 */
enum intr_level old_level = intr_disable();
/* 1. lock을 해제하면서 donation_list에서 해당 lock 을 기다리는 쓰레드 제거 */
struct list_elem *e = list_begin( &lock->holder->donation_list );
while ( e != list_end( &lock->holder->donation_list) ) {
struct list_elem *next = list_next(e);
struct thread * curr = list_entry(e , struct thread, donation_elem);
if ( lock == curr->waiting_lock ) {
curr->waiting_lock = NULL;
list_remove(e);
}
e = next;
}
/* 2. 아직 donation_list 에 무언가 남아있으면 가장 큰 값을 priority 로 설정*/
lock->holder->priority = thread_max_priority(lock->holder);
lock->holder = NULL;
intr_set_level(old_level);
sema_up (&lock->semaphore);
}
/*
condition 구조체의 waiter list를 우선순위로 정렬하기 위한 less 함수입니다.
*/
bool
cmp_cond_priority (
const struct list_elem * a,
const struct list_elem * b,
void *aux
) {
int new_priority = list_entry(a, struct semaphore_elem , elem)->priority;
int list_priority = list_entry(b, struct semaphore_elem , elem)->priority;
return new_priority > list_priority;
}
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);
waiter.priority = thread_current()->priority;
// list_push_back (&cond->waiters, &waiter.elem);
/* priority 1.3 을 구현하기 위해 변경된 함수 */
list_insert_ordered(&cond->waiters, &waiter.elem, cmp_cond_priority, NULL);
lock_release (lock);
sema_down (&waiter.semaphore);
lock_acquire (lock);
}
여기까지가 제가 작성한 priority-donation 입니다.
2주전 코드를 가져오는거라 혹시 일부 누락한 부분이 있어서 테스트 통과가 안될수도 있습니다.
MLFQS 는 통과못했습니다.
