Pintos_project1 - Priority

핀토스 프로젝트1 - 우선순위 구현

---

1. Priority 구현

가이드라인

1. struct thread에 우선순위 관련 멤버 추가
2. thread_create() - 새 스레드가 현재 스레드보다 높은 우선순위면 즉시 양보
3. thread_unblock() - unblock된 스레드가 현재 스레드보다 높은 우선순위면 즉시 양보
4. thread_set_priority() - 우선순위 변경 시 필요하면 양보
5. thread_get_priority() - 현재 우선순위 반환

---

Priority의 의미

[!NOTE] 우선순위로직
ready_list를 우선순위순으로 정렬
현재스레드보다 높은 스레드에게 cpu양보

위 가이드라인에서 보면 thread 구조체에는 priority 멤버만 추가해주면 된다.

그리고 create, unblock 에서 우선순위 처리를 해주면 되는데
먼저 왜 저 두개 함수에서만 해야하는지 이해해보자.

우선순위를 체크한다는 것은

1. ready_list 에 삽입될때
2. Running중인 스레드의 우선순위가 다시 설정됐을 때

그림을보면 스레드를 Ready상태로 만드는
thread_create()
thread_unblock()
함수에서 스레드를 ready_list 에 삽입하고,
만약 첫번째가 높다면(현재스레드) 양보함수를 사용하여
스레드를 가동시키면 된다.

---

구현

// 스레드 생성함수
tid_t thread_create(const char *name, int priority, thread_func *function, void *aux)
{
    struct thread *t;
    tid_t tid;

    ...

    thread_unblock(t); // 내림차순 삽입됨
    thread_preemption(); // 맨 앞이 제일 높다면 양보
    return tid;
}

void thread_unblock(struct thread *t) // Block -> Ready
{
    ...
    old_level = intr_disable(); // 인터럽트중단

    t->status = THREAD_READY; // 스레드를 Ready상태로
    list_insert_ordered(&ready_list, &t->elem, priority_insert_helper, NULL); 
    // 내림차순 삽입

    intr_set_level(old_level); // 인터럽트 복구
}

void thread_preemption(void)
{
    if (!list_empty(&ready_list) &&
        thread_current()->cur_priority < 
        list_entry(list_front(&ready_list), struct thread, elem)->cur_priority)
        thread_yield();
} // 리스트가 비어있지 않고, 첫번째 스레드가 더 높으면 양보

void thread_set_priority(int new_priority) 
// 현재프로세스가 낮아지면 바로 다음스레드 선점
{
    thread_current()->init_priority = new_priority;
    set_priority_self(); // donation 관련 함수
    thread_preemption();
}

---

요약

• 준비리스트 삽입(unblock, create..)에서 모두 우선순위 내림차순 삽입
• 삽입한 후에 선점
• 별개로 스레드의 우선순위 변경시에도 이 작업이 필요

---

2. 동기화 함수에서 Priority 구현

가이드라인

1. Ready list를 우선순위 순으로 정렬
2. next_thread_to_run() 수정
3. sema_up() - 가장 높은 우선순위 스레드 깨우기
4. cond_signal() - 가장 높은 우선순위 스레드 깨우기

---

동기화 함수의 의미

pintos에서 사용하는 동기화방식은 총 3개로

1. 뮤텍스
   1. 뮤텍스는 상호배제 개념으로 하나의 스레드만 접근할 수 있도록
      lock 개념을 사용한다.
2. 세마포어
   1. 여러 스레드가 접근하는 것을 허용. 동시접근의 양을 제어
3. 조건변수
   1. 자원 보다는 조건을 확인하여 동기화하는 고수준추상화
      lock과 semaphore를 활용해 안정적으로 동기화

즉, 공유자원 점유로 멈춰있던 스레드를 다시 실행하는 과정에서
우선순위를 고려해야한다.

---

구현

struct semaphore
{
    unsigned value;      /* Current value. */
    struct list waiters; /* elem */
};
struct lock
{
    struct thread *holder;      /* 점유스레드 */
    struct semaphore semaphore; 
};
struct condition
{
    struct list waiters; /* semaphore_elem */
};
struct semaphore_elem
{
    struct list_elem elem;      /* 리스트용 */
    struct semaphore semaphore; /* 본체 */
};

구조체를 보면 세마포어를 내부적으로 사용하는 것을 알 수 있다.
즉 sema_down, sema_up 함수에서 ready_list 우선순위
동기화를 구현하고, lock을 따로 처리해주면 깨어나는 스레드들은
이전처럼 우선순위로 ready_list 에 들어갈 수 있다.

// 이 자원 점유하고싶어! 함수
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_insert_ordered(&sema->waiters, &thread_current()->elem, priority_insert_helper, NULL); // 대기리스트 우선순위로 삽입
        thread_block(); // 스레드 대기
    }
    sema->value--;
    intr_set_level(old_level);
}

// 반납할래! 함수
void sema_up(struct semaphore *sema) // 깨우기함수
{
    enum intr_level old_level;
    bool should_yield = false;
    ASSERT(sema != NULL);

    sema->value++; // 자원은 반납
    if (!list_empty(&sema->waiters)) // 기다리고 있는 자원
    {
        old_level = intr_disable();
        list_sort(&sema->waiters, priority_insert_helper, 0); 
        // 중간에 바뀌었을지도 모르니
        struct list_elem *e = list_pop_front(&sema->waiters);
        intr_set_level(old_level);

        struct thread *semaup_th = list_entry(e, struct thread, elem); 
        // 기다린 스레드 중 가장 우선순위가 높은 스레드
        thread_unblock(semaup_th); // 대기리스트로
        thread_preemption(); // 선점
    }
}

// 깨울때까지 기다려! 함수
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);
    // list_insert_ordered(&cond->waiters, &waiter.elem, sema_priority, NULL);
    lock_release(lock); // 자원반납하고
    sema_down(&waiter.semaphore); // 기다려
    lock_acquire(lock); // lock 획득
}

• 여기서 특이한 점은 list에 push_back했다는 점인데,
  깨울때 sort를 한다.
  그 이유는 현재 이 코드는 각 세마포어의 대기리스트(어차피1개)에서
  스레드를 확인하고 정렬하는데
  아직 sema_down을 하지 않았으니 대기리스트는 의미가 없다
• 따라서 로직이 조금 더 간단한 push_back사용

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_priority, 0);
        // semaphore_elem을 참고하여 정렬
        sema_up(&list_entry(list_pop_front(&cond->waiters), struct semaphore_elem, elem)->semaphore);
        // 첫번째 스레드의 세마포어를 up (이때깨어남)
    }
}

---

요약

각 자원마다 대기리스트에 우선순위로 저장한뒤에
스레드가 다시 자원을 소유할 수 있을 때 레디리스트에
unblock + preemption

주의해야할 점은 구조체끼리의 연관성을 잘 이해하는 것!

---

3. 기부메커니즘 구현

가이드라인

1. struct thread에 donation 관련 멤버 추가
2. lock_acquire() - 우선순위 기부 구현
3. lock_release() - 기부 해제 구현
4. 중첩 donation 처리
5. 다중 donation 처리

Donation이란?

동기화 기법을 사용할 때 만약
공유자원A 를 우선순위5 스레드가 점유하고 있다고 보자.
그다음 우선순위20 스레드가 공유자원A에 대해서 대기하는 상황에서

ready_list에 우선순위10 스레드가 추가된다면
우선순위10 -> 우선순위5 -> 우선순위20 으로 스레드가 실행된다.

이것을 우선순위역전 이라고 하는데 우선순위기부 메커니즘으로
이를 해결할 수 있다.

기본 개념은 lock을 대기하는 스레드 중에서 가장 우선순위를
lock의 소유스레드 에게 기부하는 것이다.

그럼 방금과 같은 상황에서
공유자원A 를 소유한 우선순위5 스레드가 일시적으로 우선순위20 스레드
가 되어서 먼저 처리후 실제 대기하고있던 우선순위20 스레드가
ready_list에 삽입되어 의도한 동작이 이루어진다.

구현

1. 구조체에 멤버추가
   1. struct list donations;
      1. 기부받은 스레드리스트
   2. struct list_elem donation_elem;
      1. 스레드리스트에 소속될 elem
   3. struct lock *wait_lock;
      1. 대기중인lock (nested할때 필요)
   4. int cur_priority;
      1. 기본우선순위와 기부받은우선순위 분리

- thread 구조체 수정

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 cur_priority;          /* 현재 우선순위 */
int init_priority;         /* 원래 우선순위 */

int64_t wakeup_tick; /* 기다리는 tick. /
struct list_elem elem; / 소속 elem */

/* donation */
struct list donations;
struct list_elem donation_elem;
struct lock *wait_lock;

 

lock을 요청했을 때 비어있다면 바로 해당 자원을 잡으면 되고,
점유되어있다면 잡고있는 스레드의 기부리스트로 들어가면 된다.

release를 수행할 때는 해당 lock을 기다리는 스레드들을 제거하고,
남은 donation중 가장 높은 우선순위으로 갱신한다.

- lock_acquire 수정

void donate_nested(void)
// 연쇄적으로 스레드의 priority를 전달(가장 높음)
{
    // 이게 실행된 자체가 현재스레드가 높다는 것
    int depth;
    struct thread *cur = thread_current();

    for (depth = 0; depth < 8; depth++)
    {
        if (!cur->wait_lock)
            break;
        struct thread *holder = cur->wait_lock->holder;
        holder->cur_priority = cur->cur_priority;
        cur = holder;
    }
}

// 나 이거 쓸래! 함수
void lock_acquire(struct lock *lock) // 현재스레드가 lock을 잡는다
{
    ASSERT(lock != NULL);
    ASSERT(!intr_context());
    ASSERT(!lock_held_by_current_thread(lock));

    enum intr_level old_level;

    if (lock->holder) // lock이 소유가 있으면
    {
        thread_current()->wait_lock = lock; // lock을 기다리고 있다.

        old_level = intr_disable();
        list_insert_ordered(&lock->holder->donations, &thread_current()->donation_elem, priority_insert_helper_donation, 0);
        // holder 기부리스트에 나의 donation_elem을 소속시킴

        donate_nested(); // lock->holder의 priority를 바꿈. 연쇄적으로
        intr_set_level(old_level);
    }
    sema_down(&lock->semaphore); // 양도해준 스레드는 sema_down

    thread_current()->wait_lock = NULL;
    lock->holder = thread_current();
}

- lock_release 수정

static void remove_donation_lock(struct lock *lock)
{
    // 순회하면서 wait_lock == lock 이면 아웃!
    ASSERT(lock != NULL);
    ASSERT(lock->holder != NULL);

    struct list_elem *e;
    struct list_elem *next;
    struct list *donations = &lock->holder->donations;

    enum intr_level old_level = intr_disable();
    for (e = list_begin(donations); e != list_end(donations); e = next)
    {
        next = list_next(e); 
        // 미리 저장해두는 이유는 포인터 손실때문
        if (list_entry(e, struct thread, donation_elem)->wait_lock == lock)
        {
            list_remove(e);
        }
    }
    intr_set_level(old_level);
}

// 다중기부 (자신의 기부리스트중 최고를 받음)
void set_priority_self(void)
{
    // ASSERT(lock != NULL);
    // ASSERT(lock->holder != NULL);

    struct thread *cur_th = thread_current();
    cur_th->cur_priority = cur_th->init_priority;
    // 기부리스트가 없다면 나의 우선순위로

    if (!list_empty(&cur_th->donations))
    {
        list_sort(&cur_th->donations, priority_insert_helper_donation, 0);
        struct thread *front = list_entry(list_front(&cur_th->donations), struct thread, donation_elem);
        // 첫번째 스레드가 가장 우선순위가 높음

        if (front->cur_priority > cur_th->cur_priority)
            cur_th->cur_priority = front->cur_priority;
        // 내 우선순위랑 비교 후 갱신
    }
}

void lock_release(struct lock *lock) // lock 해제
{
    ASSERT(lock != NULL);
    ASSERT(lock_held_by_current_thread(lock));

    remove_donation_lock(lock); 
    // 홀더가 가진 기부리스트에서 해당 lock을 기다리는 스레드를 삭제
    set_priority_self();        
    // 홀더가 가진 기부리스트중에서 다시 높은 우선순위를 현재우선순위로 변경

    lock->holder = NULL;
    sema_up(&lock->semaphore);
}

요약

1. lock 획득시 nested donation 으로 확산
2. lock 해제시 관련donatoin을 삭제하고,
   자신의 donation을 탐색해 가장 높은 우선순위로 갱신

---

https://github.com/SJ-Leeee/pintos_project_1_team4/tree/main/seungjun

 

Reference

https://poalim.tistory.com/34

https://casys-kaist.github.io/pintos-kaist/project1/priority_scheduling.html