💡 Donation 예시
- priority : H > M > L
- 목표: L이 빨리 쓰고 돌려주도록 H의 priority를 상속한다.
- lock holder(L)에게 H의 priority를 상속한다.
- H가 lock을 요청하면서 L의 priority를 H와 동일하게 상승시키고,
- L이 이어서 실행되고 나서 H가 lock을 얻는다.
- L보다 우선순위가 낮아진 M은 L과 H가 종료되고 나서야 lock을 얻는다.
struct thread
, init_thread
/* thread.c */
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. */
int64_t wakeup_ticks; // 깨어날 tick
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
//👇🏻 추가한 내용
int init_priority;
struct lock *wait_on_lock;
struct list donations;
struct list_elem donation_elem;
...
};
/* thread.c */
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;
//👇🏻 추가한 내용
t->init_priority = priority;
t->wait_on_lock = NULL;
list_init(&(t->donations));
}
lock_acquire
/* synch.c */
void lock_acquire(struct lock *lock)
{
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(!lock_held_by_current_thread(lock));
struct thread *curr = thread_current();
if (lock->holder != NULL) // 이미 점유중인 락이라면
{
curr->wait_on_lock = lock; // 현재 스레드의 wait_on_lock으로 지정
// lock holder의 donors list에 현재 스레드 추가
list_insert_ordered(&lock->holder->donations, &curr->donation_elem, cmp_donation_priority, NULL);
donate_priority(); // 현재 스레드의 priority를 lock holder에게 상속해줌
}
sema_down(&lock->semaphore); // lock 점유
curr->wait_on_lock = NULL; // lock을 점유했으니 wait_on_lock에서 제거
lock->holder = thread_current();
}
cmp_donation_priority
/* thread.h */
bool cmp_donation_priority(const struct list_elem *a, const struct list_elem *b, void *aux)
/* synch.c */
// donation_elem의 priority를 기준으로 정렬하는 함수
bool cmp_donation_priority(const struct list_elem *a,
const struct list_elem *b, void *aux UNUSED)
{
struct thread *st_a = list_entry(a, struct thread, donation_elem);
struct thread *st_b = list_entry(b, struct thread, donation_elem);
return st_a->priority > st_b->priority;
}
donate_priority
/* thread.h */
void donate_priority(void);
/* synch.c */
// 현재 스레드가 원하는 락을 가진 holder에게 현재 스레드의 priority 상속
void donate_priority(void)
{
struct thread *curr = thread_current(); // 검사중인 스레드
struct thread *holder; // curr이 원하는 락을 가진드스레드
int priority = curr->priority;
for (int i = 0; i < 8; i++)
{
if (curr->wait_on_lock == NULL) // 더이상 중첩되지 않았으면 종료
return;
holder = curr->wait_on_lock->holder;
holder->priority = priority;
curr = holder;
}
}
lock_release
/* synch.c */
void lock_release(struct lock *lock)
{
ASSERT(lock != NULL);
ASSERT(lock_held_by_current_thread(lock));
remove_donor(lock);
update_priority_for_donations();
lock->holder = NULL;
sema_up(&lock->semaphore);
}
remove_donor
/* thread.h */
void remove_donor(struct lock *lock);
/* synch.c */
void remove_donor(struct lock *lock)
{
struct list *donations = &(thread_current()->donations); // 현재 스레드의 donations
struct list_elem *donor_elem; // 현재 스레드의 donations의 요소
struct thread *donor_thread;
if (list_empty(donations))
return;
donor_elem = list_front(donations);
while (1)
{
donor_thread = list_entry(donor_elem, struct thread, donation_elem);
if (donor_thread->wait_on_lock == lock) // 현재 release될 lock을 기다리던 스레드라면
list_remove(&donor_thread->donation_elem); // 목록에서 제거
donor_elem = list_next(donor_elem);
if (donor_elem == list_end(donations))
return;
}
}
update_priority_before_donations
/* thread.h */
void update_priority_before_donations(void);
/* synch.c */
void update_priority_for_donations(void)
{
struct thread *curr = thread_current();
struct list *donations = &(thread_current()->donations);
struct thread *donations_root;
if (list_empty(donations)) // donors가 없으면 (donor가 하나였던 경우)
{
curr->priority = curr->init_priority; // 최초의 priority로 변경
return;
}
donations_root = list_entry(list_front(donations), struct thread, donation_elem);
curr->priority = donations_root->priority;
}
thread_set_priority
void thread_set_priority(int new_priority)
{
thread_current()->init_priority = new_priority;
update_priority_for_donations();
preempt_priority();
}
/* Test: /threads에서 입력 */
make check
👇🏻 구현 전
👇🏻 구현 후
mlfqs를 제외한 모든 테스트를 통과했다!