close
프로필 사진

stddb

github: @denev6
구현하기 · 2025. 5. 16. fullscreen 넓게보기

PintOS #3 : Priority Scheduling

현재 실행중인 쓰레드보다 높은 우선순위를 가진 쓰레드가 ready_list에 추가 되면, 현재 쓰레드는 즉시 해당 쓰레드에게 프로세서를 양보해야한다. 다양한 상황에서도 양보가 원활하게 이루어질 수 있도록 구현하는 과정을 논해보자.

2025.05.16 - [구현하기] - PintOS #2 : Alarm Clock

 

PintOS #2 : Alarm Clock

PintOS의 코드를 구현하는 것은 상당히 난이도 있다. 여러가지 고생했고, 어디서 어떻게 막혔는지 하나하나 논하기엔 여러분들은 나의 고생이 그다지 궁금하지 않다. 그냥 GPT 없이 접근해보길 바

hyeonistic.tistory.com

 

논외로, 코치님은 전부 다 해야하며, 그래야만 다음 주를 이어 할 수 있다고 했다. 근데 사실 fifo 까지만 어찌저찌 가능하다면 다음 꺼 그냥 해도 된다고 언급한게 너무 다행이었다. 난 진짜 툭 치면 나올 수준으로 눈에 거의 각인을 했다고 생각하지만.. 근데? 설명은 잘 할지는 모르겠다.

 

 

여기서 새로운 개념이 등장한다.

우선순위 역전이라는 개념으로, 어떤 말끔한 글을 보고 단번에 이해 후 진도가 확 나갔던 기억이 있다.

 

 

일이 급하게 진행 되어야 하는 순서는 Hah,  Mah,  Lee 순이다.

Hah는 우선순위가 우선되니 한창 일을 하고 있었다. 그러다 중요한 물건이 필요해졌고 이게 없으면 더 진행하지 못한다.

Hah는 Lee가 가진 중요한 물건이 필요한 상황이다. 이게 없으면 일의 진행이 안된다.

근데 Lee도 나름 일을 해야하고, Mah도 해야한다. Mah는 사실 중요한 물건이 없어도 이리저리 진행이 잘 된다.

그럼 이 상황에서, 맥락상 일이 제일 급한 Hah는 중요한 물건의 소유자인 Lee의 영향을 받아 수행이 불가 한 것이다.

 

이 경우에는 Hah가 Lee에게 자신의 우선순위 정도를 잠시 빌려줌으로써 자신의 일을 수행하기 위한 양보를 한다. 이걸 통해서 Mah의 개입을 줄일 수 있게 되었다.

 우선순위가 높은 쓰레드 H, 중간 M 그리고 낮은 L가 있다고 생각해보세요. 만약 L이 락을 갖고있어서 H가 L을 기다려야하고 M이 ready list에 있다면, H는 절대로 CPU를 사용하지 못할 것입니다. 왜냐면 낮은 우선순위의 스레드가 CPU시간을 얻지 못할 것이기 때문입니다. 이 문제에 대한 부분적으로 해결하는 방법은 L이 락을 갖는 동안 H가 L에게 우선순위를 기부(donate)한 다음, L이 잠금을 해제하면 (따라서 H가 획득) 이 기부를 회수하는 것입니다.

그럼 우선순위를 물려주는 형태를 구현해야하는데, 이게 여간 쉬운일이 아니다.

이 중요한 물건에 대한 정의는 생각보다 범위가 넓어서, 한 쓰레드가 여러 개의 주인이 되는 경우도 가능하고, 난리가 난다.

수정 범위는 thread.* 와 synch.* 두 개이다.

synch.*

PintOS에서는 이 중요한 물건의 정의로 Lock, Semaphore, Condition Variable을 사용한다. 좀 더 정리하면 앞에서 이야기한 중요한 물건의 존재 의의를 논한다는 것이다.

Semaphore Up/Down

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_priority_only, NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	sema->value++;
	preempt_priority();
	intr_set_level (old_level);
}

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, cmp_priority_only, NULL);
		thread_block ();
	}
	sema->value--;
   preempt_priority();
	intr_set_level (old_level);
}

Lock Acquire/Release

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;
      //  curr->wait_on_lock->semaphore.waiters
        struct thread *temp = curr;
        struct thread *new_holder;
        //list_insert_ordered(&lock->holder->donations, &temp->d_elem, cmp_priority_donation, NULL);
        list_insert_ordered(&lock->holder->donations, &temp->d_elem, cmp_priority_donation, NULL);

        int cnt = 0;
        while (((temp -> wait_on_lock) != NULL ) && (cnt <= 8)) 
        {
            cnt += 1;
            new_holder = temp->wait_on_lock->holder;
            if (temp->priority > new_holder->priority) 
            {
                new_holder->priority = curr->priority;
            }
            temp = new_holder;
        }
    }
    sema_down (&lock->semaphore);
    lock->holder = curr;
    curr->wait_on_lock = NULL;
    preempt_priority();
}

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

   struct thread *curr = thread_current();
   struct list_elem *e;
   lock->holder = NULL;
   
   for (e = list_begin (&curr->donations); e != list_end (&curr->donations); e = list_next(e))
   {
      struct thread *donaItem = list_entry (list_front (&curr->donations), struct thread, d_elem);
      if(donaItem->wait_on_lock == lock)
         list_remove(e);
   }

   recal_priority(curr);
   sema_up (&lock->semaphore);
   //thread_yield();

}

Condition Wait/Signal

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_insert_ordered(&cond->waiters, &waiter.elem, cmp_sema_priority, NULL);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

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, cmp_sema_priority, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);
	}	
}

 

thread.*

	struct list donations;              /* 우선순위 donations를 추적하기 위한 리스트 */
	struct lock *wait_on_lock;          /* 대기 중인 락 */
	int base_priority;                  /* 기부 이전 우선순위 */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
	struct list_elem d_elem;            /* Donations List element. */

쓰레드 구조체에 이 멤버변수가 추가되었다.

donations

  • 이 쓰레드에게 중요한 물건이 필요하여 우선순위를 넘겨 준, 혹은 넘겨 줄 수 있는 사람들의 목록이다.
  • 내 생각엔 그렇다면 여기엔 그럼 현재 이 쓰레드보다 더 높은 숫자들만 있을 수 있다..고 생각했다. 근데 나중에 donation에 들어가는 상황에서 따로 조건을 보진 않음. 우선 넣어두는건 필요 하다고 생각하고 있다.

 

 

wait_on_lock

  • 나, 이 중요한 물건이 필요합니다!! 라고 딱 찍는 것, lock_acquire() 라는 함수에서 사용된다. 결과적으로 중요한 물건이 필요한 사람에게 쥐어주는 것이 맥락 상 전체적인 규칙을 깨지 않기 때문에, 저장은 그렇게 오랫동안 이루어지지 않고 기다리는 사람에게 중요한 물건이 주어지게 된다.

 

 

base_priority

  • 내가 우선순위를 잠시 빌려받았다가 돌아가는 경우에는 원래 내 숫자가 뭐였는지를 다시 기억하고 있어야한다. 그 내용 때문에 생긴 내용. base_priority는 thread_set_priority() 에서도 변경된다. 이거 하나 없어서 테스트 몇 개를 통과 못한건지..

 

elem, d_elem

  • elem은 기존에 쓰레드 단위의 리스트를 관리하는데 필요한 일종의 손잡이 영역이었다.
  • 나는 손잡이가 하나만 있어도 될 것이라고 생각했으나 이것은 ready_list 또는 sleep_list에 쓰이고, 그리고 ready/sleep은 중복이 되지 않기 때문에 두 리스트에 하나의 손잡이만 사용될 수 있는 것이라고 설명을 들었다.
  • 그래서 d_elem은 donations list에 투입되어야하는데, ready/sleep 중 하나의 state이면서 donate 해줄수있는 상태를 같이 갖추기 위해선 손잡이를 두 개 써야한다는 판단이 들었다.
  • 일리 있는 말이지만 실제로 활용하는데 있어서 Kernel Panic을 이거 때문에 너무 많이 보았다. 아니 대체 무슨 상관인데?

 

thread_create() 에서 앞에서 이야기한 변수들의 초기 값 배정이 필요하다고 판단했다.

	list_init(&t->donations);
	t->wait_on_lock = NULL;
	t->base_priority = t->priority;

리스트에서 삽입을 할 때 우리는 순서가 있는 배치를 하길 원했다. 그 기준점을 위해선 비교 변수를 몇 개 만들었어야 하는데 그 내용들이다.

bool
cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) 
{
	struct thread *ta = list_entry(a, struct thread, elem);		// a 요소를 thread 구조체로 변환
	struct thread *tb = list_entry(b, struct thread, elem);		// b 요소를 thread 구조체로 변환

	if (ta->priority == tb->priority)				 // 우선순위가 같은 경우 (tie-breaker)
        return ta->wakeup_ticks < tb->wakeup_ticks;  // wakeup_thicks가 빠른 스레드를 우선 배치 (FIFO)
	return ta->priority > tb->priority;				 // 우선순위가 높은 (값이 큰) 스레드를 먼저 배치
}

bool
cmp_priority_only(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) 
{
	struct thread *ta = list_entry(a, struct thread, elem);		// a 요소를 thread 구조체로 변환
	struct thread *tb = list_entry(b, struct thread, elem);		// b 요소를 thread 구조체로 변환

	return ta->priority > tb->priority;				 // 우선순위가 높은 (값이 큰) 스레드를 먼저 배치
}

bool
cmp_priority_donation(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) 
{
	struct thread *ta = list_entry(a, struct thread, d_elem);		// a 요소를 thread 구조체로 변환
	struct thread *tb = list_entry(b, struct thread, d_elem);		// b 요소를 thread 구조체로 변환

	return ta->priority > tb->priority;				 // 우선순위가 높은 (값이 큰) 스레드를 먼저 배치
}

 

base_priority의 존재로 set_priority의 수정이 필요했다.

기존 priority를 냅다 수정했다간, 이게 우선순위를 빌린 상태를 아예 뭉개 없애버리는 상황을 초래 할 수 있었다. 

void
thread_set_priority (int new_priority) 
{
	struct thread *thr = thread_current();
	// 주석처리 된 이 줄은 기존에 일어나던 내용인데, 즉시 개시했다간 참사가 발생 할 것이다.
	//thread_current ()->priority = new_priority;
	thr->base_priority = new_priority;
	recal_priority(thr);
	preempt_priority();
}

 

쓰레드가 할 일을 끝내고 제자리로 돌아가기 전에 자신의 소유인 중요한 물건과 이해 관계가 있는 사람을 다시 한번 확인하는 코드가 필요하다. 왜냐하면 단 한 번만 중요한 물건에 대한 우선순위 기부를 수행하고 돌아가면 앞에서 이야기했던 Hah, Mah, Lee의 뭔가 맥락상 이상한 상황을 다시 볼 수 있기 때문이다. 

내 소유의 중요한 물건이 있는 것은 충분히 그럴 수 있다. 근데 중요한 물건을 쓰고 싶다는 요청은 소유자의 donations에 일단 담긴다. 정확하게는 donations는 후보군 으로 생각해야한다. 앞에서 내가 생각했던 것과 달리 내 base_priority가 바뀌는 여지를 생각하면 여기 사람들은 일단 받아두는게 적합한 것이다.

더 쉽게 설명하려고 다시 적어보는데, donations에 입력 할까 하고 조건을 보는 시점에서 내 priority 또는 base_priority랑 비교해서 낮은걸 쳐내버렸는데, 나중에 set_priority로 바닥을 찍은 상태에서 작업을 끝내고 원복하려고 하니 기존에 쳐내버린 쓰레드의 우선순위가 바닥을 찍은 나의 우선순위보다 높다는 것을 알았다. 그럼 걔한테 우선순위를 기부받아야하는데 입력 자체를 받질 못했으니 추적을 할 수 없다. 그래서 donations는 후보군으로 생각해야한다. 

void recal_priority(struct thread *t)
{
    int max_p = t->base_priority; /* base_priority로 초기화 */
    /* 해상 thread의 donations list에 있는 thread들을 순회하며 가장 큰 priority를 탐색 */
    for(struct list_elem *e = list_begin(&t->donations); e != list_end(&t->donations); e = list_next(e))
    {
        struct thread *cmp_t = list_entry(e, struct thread, d_elem);
        max_p = max_p > cmp_t->priority ? max_p : cmp_t->priority;
    }
    // max_p = max_p > t->priority ? max_p : t->priority; /* 현재 thread의 우선 순위와 donations list 중에 큰 priority로 갱신 */
    t->priority = max_p; /* t의 priority 값 갱신 */
    return;
}

 

유의미한 수정점은 이정도인데, 이것만 참고하고 잘 작동이 안된다고 생각한다면 글까지 반영되지 않은 부분을 참고해보면 좋겠다.

https://github.com/Jungle-W9-T8/PintOS

 

GitHub - Jungle-W9-T8/PintOS: KAIST PintOS 구현 프로젝트

KAIST PintOS 구현 프로젝트. Contribute to Jungle-W9-T8/PintOS development by creating an account on GitHub.

github.com

여기서 threads/thread.c를 미리 확인해보라. 내가 이 부분은 덜 바쁠때 차례로 수정할 예정에 있다.

'구현하기' 카테고리의 다른 글

PintOS P2 #2 : Argument Passing을 다루기 전  (0) 2025.05.21
PintOS P2 #1 : User Program 서론  (0) 2025.05.20
PintOS #2 : Alarm Clock  (0) 2025.05.16
PintOS #1 : 진행 흐름도 파악하기  (0) 2025.05.12
PintOS #0 : 서론  (0) 2025.05.10
구현하기 관련 글
더 보기
Copyright © pwerty 모든 권리 보유.
SKIN: Copyright © 쭈미로운 생활 All rights reserved. Designed by JJuum.
and Current skin "dev-roo" is modified by Jin.

티스토리툴바