[Pintos-KAIST] Project 1 :: Priority Donation

2023. 4. 26. 01:46ㆍComputer Science

728x90
반응형

Donation

Donation 구현사항

  • lock을 보유하고 있는 스레드가 낮은 우선순위를 가진 스레드일 경우, 대기하고 있는 스레드의 우선순위를 보유한 스레드에게 기부한다.
  • 이 때, 재귀적으로 기부가 이루어질 수 있다.

 

🤔 Donation을 하는 이유 :: Priority Inversion

  • 높은 우선순위 스레드가 낮은 우선순위 스레드가 가진 공유 자원(lock)을 사용하기 위해 대기할 때 Priority Inversion이 발생한다.
    • 높은 우선순위 스레드는 블록되어 CPU 시간을 할당받지 못하고, 대기 상태에서 머물러 있게 된다.
    • 이럴 경우 중간 우선순위의 스레드가 ready_list에 존재한다면, 높은 우선순위 스레드는 우선순위가 더 높음에도 불구하고 CPU 시간을 할당받지 못하고 대기 상태에 머물러 있는 상황이 발생한다.
  • 이러한 문제를 해결하기 위해, 높은 우선순위 스레드가 낮은 우선순위 스레드가 자원을 보유하고 있는 동안 우선순위를 기부하는 것이다.
    • 낮은 우선순위 스레드가 보유한 자원을 사용하고 있는 동안에는 높은 우선순위를 갖게 되어 스레드가 CPU 시간을 할당받게 되고, 이후 자원을 반납하면, 높은 우선순위 스레드는 우선순위를 되돌려받아 CPU 시간을 할당받을 수 있다.

 

💡 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을 얻는다.
donation을 구현할 때는 아래의 두 가지를 고려해야 한다.

(1) Nested Donation

  • Donation은 재귀적으로 이어진다.
    • T1이 점유한 lockA를 T2가 요청하면 (T2가 더 높을 경우) T2의 priority로 갱신한다.
    • 위 상황에서, T2가 점유한 lockB를 T3이 요청하면 (T3이 더 높을 경우) T1과 T2를 T3의 priority로 갱신한다.

 

(2) Multiple Donation

  • lock을 여러 개 점유한 스레드는 lock을 요청한 스레드의 priority 중 가장 높은 priority로 갱신한다.
  • lock을 반환할 경우에는, 반환한 lock을 획득한 스레드를 제외한 lock을 요청한 스레드들의 priority 중에서 가장 높은 priority로 갱신한다.

 

구현하기

(1) struct thread에 필드 추가 & 초기화

struct thread , init_thread

  • 스레드 구조체에 donation에 필요한 필드를 추가하고, 스레드가 생성될 때 초기화한다.
  • int init_priority;
    • 스레드가 생성될 때, 혹은 thread_set_priority로 갖게 된 스레드의 priority를 저장한다.
    • donation이 종료될 때 기존의 priority로 돌아오기 위한 필드이다.
  • struct lock *wait_on_lock;
    • 스레드가 요청했지만 다른 스레드가 점유하고 있어서 획득하지 못하고 기다리고 있는 lock을 저장한다.
    • 스레드가 lock을 요청하고 대기하게 될 경우 block되므로 lock을 얻기 전까지는 다른 요청을 할 수 없다. 따라서 각 스레드는 lock을 단 한 개만 보유할 수 있다.
  • struct list donations;
    • 스레드가 점유하고 있는 lock을 요청하면서 priority를 기부해준 스레드들을 연결 리스트 형태로 저장한다.
    • 스레드가 lock을 반환하면서 priority를 기부받기 전으로 되돌리기 위해 사용한다.
  • struct list_elem donation_elem;
    • 스레드가 다른 스레드가 점유하고 있는 lock을 요청했을 때, 다른 스레드에게 priority를 기부하면서 해당 스레드의 donations에 들어갈 때 사용되는 elem이다.
    • 기존에 스레드 구조체가 가지고 있는 elem은 ready_list와 sleep_list에서 사용되고 있으므로, donations에서는 사용될 수 없다.
      (elem은 한 리스트에서만 사용되어야 하며, 스레드는 ready_list와 sleep_list 두 리스트에 공존할 수 없기 때문에 기존에는 한 elem만으로도 가능했다.)
    • lock과 마찬가지로, lock 요청은 한 스레드 당 하나만 가능하므로, elem도 하나만 있으면 된다.
/* 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));
}

 

(2) lock 요청 시 donation

lock_acquire

  • lock을 요청했을 때, 이미 holder(lock을 점유하고 있는 스레드)가 있다면 holder에게 priority를 기부한다.
  • wait_on_lock(내가 기다리고 있는 lock)으로 설정한다.
  • holder의 donations에 현재 스레드를 추가한다.
    • elem이 아닌 donation_elem을 추가해야 하는 것에 유의한다.
    • priority를 기준으로 내림차순 정렬되도록 삽입한다.
    • 정렬을 위한 함수 cmp_donation_priority는 아래에서 새로 선언한다.
  • holder도 lock을 요청해둔 상태라면, holder가 요청한 lock의 holder에게도 priority 기부가 이어져야 한다. (depth 8까지 재귀적으로 기부한다.)
    • 재귀적으로 기부하는 함수인 donate_priority는 아래에서 새로 선언한다.
  • lock을 얻고 나면 (sema_down 실행 이후) wait_on_lock을 삭제한다.
/* 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

  • donation_elem을 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

  • 현재 스레드가 원하는 lock을 가진 holder에게 현재 스레드의 priority를 기부하는 함수
    • 현재 스레드가 원하는 락을 가진 holder1 → holder1가 원하는 락을 가진 holder2 → holder2가 원하는 락을 가진 holder3 … 에게 이어가면서 depth가 8이 될 때까지 모두 현재 스레드를 갖게 한다.
    • holder가 있는 lock에 요청을 한다는 것은, 현재 스레드가 holder보다 높은 우선순위를 가지고 있어서 현재 실행되고 있다는 것을 의미하므로, priority를 비교할 필요 없이 holder가 존재한다면 바로 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;
    }
}

 

(3) lock 반환 시 donation 이전 priority로 복귀

lock_release

  • 현재 스레드가 lock을 반환할 때, 이 lock을 요청한 스레드가 있어서 donation을 받았다면, 해당 스레드에게 받은 donation은 철회해야 한다.
  • 기부를 해준 스레드 목록인 donations 목록에서 현재 반환될 lock을 요청했던 스레드를 찾아서 제거한다.
    • remove_donor 함수는 아래에서 새로 선언한다.
    • (remove_donor 함수는 lock_release 함수 이외에는 호출되지 않으므로 함수로 만들지 않아도 괜찮지만, 가독성을 위해 분리한다.)
    • lock 정보를 remove_donor 함수에서 사용해야 하므로, remove_donor 함수를 호출하고 나서 lock의 holder를 제거한다.
  • 제거하고 나서 남은 donations 목록 중에서 가장 높은 priority를 가진 스레드의 priority로 현재 스레드의 priority를 재지정해준다.
    • update_priority_before_donations 함수는 아래에서 새로 선언한다.
/* 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

  • 기부를 해준 스레드 목록인 donations 목록에서 현재 반환될 lock을 요청했던 스레드를 찾아서 제거한다.
/* 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

  • 현재 반환한 lock으로 인해 받은 donation을 철회하는 함수
    • 원래 donations가 비어있었거나, 현재 함수가 호출되기 전에 remove_donor 함수에서 donor를 제거하면서 donations가 비어있을 수 있다. 그럴 경우, 최초의 priority인 init_priority로 변경한다.
    • donations가 비어있지 않다면, donations가 priority를 기준으로 내림차순 정렬되어있으므로 가장 앞에 있는 스레드의 priority로 지정한다.
/* 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

  • thread의 priority가 변경되면, donations 정보를 갱신해야 한다.
    • 해당 thread가 기부를 해줬던 스레드가 있다면 기부를 받은 스레드의 priority가 변경되어야 한다.
void thread_set_priority(int new_priority)
{
    thread_current()->init_priority = new_priority;
    update_priority_for_donations();
    preempt_priority();
}

 

Test - Priority 3

/* Test: /threads에서 입력 */

make check

👇🏻 구현 전

👇🏻 구현 후

mlfqs를 제외한 모든 테스트를 통과했다!

728x90
반응형
저작자표시

'Computer Science' 카테고리의 다른 글

[Pintos-KAIST] Project 2 :: System Calls - 2 (exec, wait, fork), Deny Write on Executables  (1) 2023.05.05
[Pintos-KAIST] Project 1 :: Priority Scheduling  (0) 2023.04.25
[Pintos-KAIST] Project 1 :: Alarm Clock (Sleep-Awake 방식의 Alarm Clock 구현하기)  (0) 2023.04.25

관련글

댓글 0

티스토리툴바