[Pint OS] Priority Scheduling(1) - 즉시 양보하기

설현아·2025년 5월 13일

pintos

우선순위 스케줄링 요구사항

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

1️⃣ 현재 실행 중인 스레드보다 우선순위가 높은 스레드가 준비 목록에 추가되면, 현재 스레드는 즉시 새 스레드에게 프로세서를 양보해야 합니다. → OK

2️⃣ 마찬가지로, 스레드가 잠금, 세마포어 또는 조건 변수를 대기하는 경우, 우선순위가 가장 높은 대기 스레드가 먼저 깨어나야 합니다. → OK

3️⃣ 스레드는 언제든지 자신의 우선순위를 높이거나 낮출 수 있지만, 우선순위를 낮춰 더 이상 가장 높은 우선순위를 갖지 않게 되면 즉시 CPU를 양보해야 합니다. → OK

위의 세 가지 경우를 우선순위에 맞게, 그리고 즉시, 양보하도록 수정하는 것이 이번 과제의 요구사항이다.

하나씩 가보자.

▶︎ 우선순위가 높은 스레드가 준비 목록에 추가된 경우

ready_list에 추가될 때, 우선순위 기준으로 내림차순 정렬하여 관리하면 되겠다.
현재 ready_list에 추가하는 부분은 다음과 같다.

ready queue 에 쓰레드를 삽입하는 함수들

/* 1번 thread_unblock() */
void
thread_unblock(struct thread* t) {
  enum intr_level old_level;

  ASSERT(is_thread(t));

  old_level = intr_disable();
  ASSERT(t->status == THREAD_BLOCKED);
  list_push_back(&ready_list, &t->elem); // 여기
  t->status = THREAD_READY;

  intr_set_level(old_level);
}

/* 2번 thread_yield() */
void
thread_yield(void) {
  struct thread* curr = thread_current();
  enum intr_level old_level;

  ASSERT(!intr_context());

  old_level = intr_disable();
  if (curr != idle_thread)
    list_push_back(&ready_list, &curr->elem); // 여기

  do_schedule(THREAD_READY);
  intr_set_level(old_level);
}

/* 3번 schedule() */
static void schedule(void) {
  enum intr_level old_level;
  old_level = intr_disable();

  struct thread* curr = running_thread();
  struct thread* next = next_thread_to_run();

  ASSERT(intr_get_level() == INTR_OFF);
  ASSERT(curr->status != THREAD_RUNNING);
  ASSERT(is_thread(next));
  /* Mark us as running. */
  next->status = THREAD_RUNNING;

  /* Start new time slice. */
  thread_ticks = 0;

  intr_set_level(old_level);
#ifdef USERPROG
  /* Activate the new address space. */
  process_activate(next);
#endif

  if (curr != next) {
    if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
      ASSERT(curr != next);
      list_push_back(&destruction_req, &curr->elem); // 여기
    }

    thread_launch(next);
  }
}

전체 코드에서 list_push_back() 함수를 활용하여 ready queue의 맨 뒤에 삽입하고 있다.

이를 우선순위 값을 기준으로 삽입해주면 된다. 우선순위 큐를 내림차순으로 구현하는 것과 같다!

이렇게 구현하기 위해서는 list 에 이미 구현되어있는 함수를 사용하면 편할 것 같다. list_insert_ordered 라는 함수를 이용하여 구현해보자!

thread_compare_priority()

/* priority 기준의 내림차순 정렬을 위한 서브 함수 */
bool thread_compare_priority(const struct list_elem* a, const struct list_elem* b,
  void* aux UNUSED) {
  struct thread* data_a = list_entry(a, struct thread, elem);
  struct thread* data_b = list_entry(b, struct thread, elem);
  return data_a->priority > data_b->priority;
}

우선순위 내림차순으로 정렬하기 위해 정의한 위의 서브함수를 활용하여, ready_list에 삽입하도록 변경한다.

/* 1번 thread_unblock() */
void
thread_unblock(struct thread* t) {
  enum intr_level old_level;

  ASSERT(is_thread(t));

  old_level = intr_disable();
  ASSERT(t->status == THREAD_BLOCKED);
  // list_push_back(&ready_list, &t->elem);
  list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, NULL);
  t->status = THREAD_READY;

  intr_set_level(old_level);
}

/* 1번 thread_yield() */
void
thread_yield(void) {
  struct thread* curr = thread_current();
  enum intr_level old_level;

  ASSERT(!intr_context());

  old_level = intr_disable();
  if (curr != idle_thread)
    // list_push_back(&ready_list, &curr->elem);
    list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, NULL);

  do_schedule(THREAD_READY);
  intr_set_level(old_level);
}

/* 3번 schedule() */
static void schedule(void) {
  enum intr_level old_level;
  old_level = intr_disable();

  struct thread* curr = running_thread();
  struct thread* next = next_thread_to_run();

  ASSERT(intr_get_level() == INTR_OFF);
  ASSERT(curr->status != THREAD_RUNNING);
  ASSERT(is_thread(next));
  /* Mark us as running. */
  next->status = THREAD_RUNNING;

  /* Start new time slice. */
  thread_ticks = 0;

  intr_set_level(old_level);
#ifdef USERPROG
  /* Activate the new address space. */
  process_activate(next);
#endif

  if (curr != next) {
    if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
      ASSERT(curr != next);
      // list_push_back(&destruction_req, &curr->elem);
      list_insert_ordered(&destruction_req, &curr->elem, thread_compare_priority, NULL);
    }

    thread_launch(next);
  }
}

priority-fifo
alarm-priority

두 개가 성공했다.

다른 것도 해보자.

▶︎ 준비 목록에 추가된 스레드에게 즉시 프로세서를 양보

준비 목록에 추가된 스레드가 현재 실행 중인 스레드 보다 우선순위가 높을 경우에도 즉시 CPU 제어를 넘겨야 한다.

준비 목록에 추가하는 시점이 언제일까?

thread_unblock() 함수와 함께 ready list에 추가된다.
(이는 나중에 변경된다ㅠ priority-preempt 과제에서는 통과되지만 이후의 semaphore 과제로 갔을 때, main thread로의 불필요한 context switching이 발생한다.)

그렇다면 이 함수 안에서 ready list에 추가하고, 현재 실행 중인 스레드의 우선 순위와 비교해야 한다.

추가한 스레드의 우선순위가 높을 경우에는 즉시 재스케줄링을 하도록 해야 한다.

void
thread_unblock(struct thread* t) {
  enum intr_level old_level;

  ASSERT(is_thread(t));

  old_level = intr_disable();
  ASSERT(t->status == THREAD_BLOCKED);
  // list_push_back(&ready_list, &t->elem);
  list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, NULL);
  t->status = THREAD_READY;

  if (thread_current() != idle_thread && t->priority > thread_current()->priority) {
    thread_yield();
  }

  intr_set_level(old_level);
}

thread_current() != idle_thread 이 코드가 굉장히 중요하다. 없으면 무한루프에 빠지기 때문..

왜그럴까?

만약 idle_thread를 ready_list에 넣으면…

ready_list는 절대 비어있지 않은 상태처럼 보인다. 그렇게 되면 스케줄러는 항상 ready_list에 idle_thread가 있으니 다른 thread가 없더라도 비었다고 인식하지 못하여 우선순위에 따라 수행하게 된다.

보통의 thread와 동일하게 취급된다는 말이다.
idle_thread의 역할에 위배된다.(CPU를 최소한의 전력으로 일하게 하는 것)

결국 다른 thread가 있어도 idle_thread가 running 상태 유지하며 priority-preempt 같은 선점 실패하며 starvation을 유발한다.
이 코드를 보면 알 수 있다.

/* thread_yield() */

void
thread_yield(void) {
  struct thread* curr = thread_current();
  enum intr_level old_level;

  ASSERT(!intr_context());

  old_level = intr_disable();
  if (curr != idle_thread)
    // list_push_back(&ready_list, &curr->elem);
    list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, NULL);

  do_schedule(THREAD_READY);
  intr_set_level(old_level);
}

timer tick은 time slice 단위로 인터럽트를 일으킨다.thread_tick()에 정의되어있으며, 특정 스레드가 time slice 이상으로 CPU를 점유한다면 인터럽트가 발생한다.(intr_yield_on_return())
interrupt.c / intr_handler()는
이 인터럽트를 처리한다. yield_on_return 변수가 true 이면 thread_yield() 가 실행된다.
thread_yield() 는 현재 스레드가 idle_thread가 아니라면 대기열(ready list)에 현재 스레드를 추가하며 ready 상태로 내리면서, schedule()을 호출하며 다시 CPU 스케줄링이 되도록 한다.

즉, idle_thread가 running 상태라면, CPU 스케줄링은 일어나지만 선점을 이루어지지 않는다. 새로운 스레드가 생성되지 않고서야, ready_list에 삽입하지 않는다. 그렇기 때문에 계속 idle_thread만 실행된다.
이 idle_thread가 다시 blocked 되는 경우는 최초 뿐이다.

이 흐름대로 running 상태인 idle_thread는 절대 ready 상태로 들어갈 수 없다.
단지, ready list에 다른 thread가 추가되면 그 스레드를 스케줄링한다.(schedule() 에서 next_thread_to_run() 을 호출하며 이루어진다.)

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);
  }
}

그니까,
더 간단하게 idle_thread의 근본적인 역할을 기준으로 정리하자면,
idle_thread는 ready list가 비었는지 존재하는지를 알게 해주는 역할을 한다.

그래서 이 idle thread가 ready list에 들어가게 되면 OS에게 제대로된 신호를 주지 못하게 된다. idle thread의 우선순위에 따라 보다 우선순위가 낮은 다른 스레드를 수행시키지 못할 수도 있다.

그리고 idle thread의 본 역할인 'ready list가 비어있는지 확인하는 용도'로 사용하지 못하게 된다. OS는 당황하게 되겠지?

이렇게 하면 priority-preempt 까지 완료다.

현재 상황의 문제점은 ready_list만 우선순위 순으로 관리하고 있다는 점이다.
그러나, pintos에서는 semaphore, lock, condition을 동기화 도구로 사용하고 있다.

semaphore 또한, waiters 라는 하나의 자원에 대해 대기 중인 대기자 목록을 관리한다.
condition 또한, 여러 semaphore에 대한 waiters 목록을 관리한다.

지금 이 목록들은 전부 FIFO(First In First Out) 방식으로 구현되어 있기 때문에, 이들도 우선순위를 고려하여 재정렬시켜주어야 한다.

▶︎ 스레드가 잠금, 세마포어 또는 조건 변수를 대기하는 경우, 우선순위가 가장 높은 대기 스레드가 먼저 깨어나야 한다.

이 요구사항을 판단하는 테스트는 priority-sema 이다. 이를 통과해야 한다.
기존 코드를 분석하고 변경해야 할 부분을 알아보자.
사실 기존 코드를 다시 옮기기 귀찮아서 일단 완성 코드만 기록한다.. 아직 우선순위 역전도 해야 한다ㅠㅠ

semaphore

semaphore 대기열을 관리하는 방식을 priority 내림차순으로 정렬하여 관리하도록 변경해야 한다.

sema_down(): running 상태의 스레드를 semaphore 대기열에 추가한다.

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_push_back(&sema->waiters, &thread_current()->elem);
		list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_compare_priority, NULL);
		thread_block();
	}

sema_up() : semaphore 대기열에서 하나의 스레드를 깨운다.

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, thread_compare_priority, NULL);
		thread_unblock(list_entry(list_pop_front(&sema->waiters),
			struct thread, elem));

	}
	sema->value++;

	thread_test_preemption();
	intr_set_level(old_level);
}

lock

semaphore를 호출하며 최종 처리를 하고, lock을 지닌 주체만을 변경하기 때문에 변경해줄 사항이 없다.

lock_acquire() : lock을 획득하고 sema_down을 호출한다.

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

	sema_down(&lock->semaphore);
	lock->holder = thread_current();
}

lock_release() : lock을 반환하고 sema_up을 호출한다.

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

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

conditio

여기에서는 아주 중요한 것이 있다.
condition 구조체는 다음과 같이 정의되어있다.

/* synch.c */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};

그러면 waiters는 어떻게 정의할까?

/* cond_wait() */
list_insert_ordered(&cond->waiters, &waiter.elem, sema_compare_priority, NULL);

waiter.elem이라는 매개변수 타입으로 관리한다.

그러면 waiter.elem 타입은 뭘까?

/* cond_wait() */
	struct semaphore_elem waiter;

/* synch.c */
struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
};

waiter.elem은 thead 구조체이지만, 그 상위를 보면 semaphore_elem 구조체로 waiter를 정의하여 사용한다.

따라서 앞선 thread 타입으로만 이루어진 대기열과 달리, semaphore_elem 타입으로 이루어진 대기열인 것이다.

그렇다면 우선순위 내림차순으로 정렬하기 위한 함수를 다시 만들어야겠지?

void sema_compare_priority(const struct list_elem* a, const struct list_elem* b,
	void* aux UNUSED) {
	struct semaphore_elem* sema_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem* sema_b = list_entry(b, struct semaphore_elem, elem);

	struct list* waiters_in_sema_a = &sema_a->semaphore.waiters;
	struct list* waiters_in_sema_b = &sema_b->semaphore.waiters;

	struct thread* max_sema_a = list_entry(list_front(&waiters_in_sema_a), struct thread, elem);
	struct thread* max_sema_b = list_entry(list_front(&waiters_in_sema_b), struct thread, elem);

	return max_sema_a->priority > max_sema_b->priority;
}

자, 이제 시작!!

cond_wait() : 조건 변수에 따른 세마포어의 대기열에 추가한다.

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_compare_priority, NULL);
	lock_release(lock);
	sema_down(&waiter.semaphore);
	lock_acquire(lock);
}

cond_signal() : 조건에 따른 semaphore 대기열에서 하나의 스레드를 꺠운다.

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_compare_priority, NULL);

		sema_up(&list_entry(list_pop_front(&cond->waiters),
			struct semaphore_elem, elem)->semaphore);
	}
}

이렇게 했는데도 아래와 같은 결과가 생기는 거다.
진짜 미치겠다..

FAIL
Test output failed to match any acceptable form.

Acceptable output:
  (priority-sema) begin
  (priority-sema) Thread priority 30 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 29 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 28 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 27 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 26 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 25 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 24 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 23 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 22 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 21 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) end
Differences in `diff -u' format:
  (priority-sema) begin
+ (priority-sema) Back in main thread.
  (priority-sema) Thread priority 30 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 29 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 28 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 27 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 26 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 25 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 24 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 23 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 22 woke up.
- (priority-sema) Back in main thread.
- (priority-sema) Thread priority 21 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) end

도대체 main thread가 뭔데 자꾸 저기로 돌아가서 실패한다는 거냐ㅜㅜ
그래서 main thread에 관한 이야기는 이전 포스팅에 자세히 다루었다.

여기에서 중요한 건, main thread도 ready_list로 들어가고 다른 스레드와 동일하게 스케줄링된다는 점이다.
main thread의 우선순위는 DEFULT인 31 이다.

기억한 채로 다시 시도!

일단 정의해보자.

우선순위를 따져서 ready_list에 더 높은 우선순위가 있다면 선점해야 하는데, 이 선점의 시점이 어떻게 될까?

쓰레드가 생성될 때
우선순위가 조정될 때

즉, thread_create(), thread_set_priority() 에서이다.

ready_list에서 더 높은 우선순위가 있다면, thread_yield()를 실행하는 함수를 별도로 정의하고 두 순간에 실행해주자.

thread_test_preemption()


void
thread_test_preemption(void)
{
  if (!list_empty(&ready_list) &&
    thread_current()->priority <
    list_entry(list_front(&ready_list), struct thread, elem)->priority)
    thread_yield();
}

thread_create()

tid_t
thread_create(const char* name, int priority,
  thread_func* function, void* aux) {
  struct thread* t;
  tid_t tid;

  ASSERT(function != NULL);

  /* Allocate thread. */
  t = palloc_get_page(PAL_ZERO);
  if (t == NULL)
    return TID_ERROR;

  /* Initialize thread. */
  init_thread(t, name, priority);
  tid = t->tid = allocate_tid();

  /* Call the kernel_thread if it scheduled.
   * Note) rdi is 1st argument, and rsi is 2nd argument. */
  t->tf.rip = (uintptr_t)kernel_thread;
  t->tf.R.rdi = (uint64_t)function;
  t->tf.R.rsi = (uint64_t)aux;
  t->tf.ds = SEL_KDSEG;
  t->tf.es = SEL_KDSEG;
  t->tf.ss = SEL_KDSEG;
  t->tf.cs = SEL_KCSEG;
  t->tf.eflags = FLAG_IF;

  /* Add to run queue. */
  thread_unblock(t);
  thread_test_preemption();

  return tid;
}

thread_set_priority()

void
thread_set_priority(int new_priority) {
  // 우선순위가 낮아졌다면 우선순위가 높은 쓰레드에게 넘김
  thread_current()->priority = new_priority;
  thread_test_preemption();
}

다시 한 번 언급하자면,

진짜진짜 실수하면 안 되는 것이 있다.

thread_unblock()에서 thread_yield()를 호출하는 것이다.

이렇게 하면, 기존에 실행되던(running) 스레드를 ready_list로 내리고, 그 ready_list 중 가장 우선순위가 높은 스레드를 수행한다.

	
	#define PRI_DEFAULT 31                  /* Default priority. */

  init_thread(initial_thread, "main", PRI_DEFAULT);

그런데 이 때 main thread는 PRI_DEFAULT 로 우선순위가 설정된다. 아까 에러 로그를 다시 보자.

FAIL
Test output failed to match any acceptable form.

Acceptable output:
  (priority-sema) begin
  (priority-sema) Thread priority 30 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 29 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 28 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 27 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 26 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 25 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 24 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 23 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 22 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 21 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) end
Differences in `diff -u' format:
  (priority-sema) begin
+ (priority-sema) Back in main thread.
  (priority-sema) Thread priority 30 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 29 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 28 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 27 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 26 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 25 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 24 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 23 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) Thread priority 22 woke up.
- (priority-sema) Back in main thread.
- (priority-sema) Thread priority 21 woke up.
  (priority-sema) Back in main thread.
  (priority-sema) end

테스트 스레드들은 전부 31 보다 우선순위가 낮다.

즉, 메인 스레드의 DEFUALT 우선순위 보다 낮다.

메신 스레드는 생성 시점 이후에 우선순위를 변경하지 않기 때문에 round-robin 방식에 따라 우선순위대로 수행하되, 선점하지는 않게 될 것이다.

하지만 지금처럼 thread_unblock() 함수에서도 thread_yield() 를 호출하게 되면 스레드가 만들어지거나, 우선순위가 변경될 때가 아닌, 다른 순간에도 위와 같이 의미없이 main thread를 한 번 더 거치며 로그를 출력하게 된다.

이제 원인을 알았으니, 수정해준다.

void
thread_unblock(struct thread* t) {
  enum intr_level old_level;

  ASSERT(is_thread(t));

  old_level = intr_disable();
  ASSERT(t->status == THREAD_BLOCKED);
  // list_push_back(&ready_list, &t->elem);
  list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, NULL);
  t->status = THREAD_READY;

  intr_set_level(old_level);
}

오예 성공이다.

정리

개선 포인트 1

: ready_list에서 스케줄링 되는 순서는, priority 기준 내림차순이어야 한다.

이 방법에는, 1. 삽입할 때부터 내림차순으로 삽입하는 방법 2. 꺼낼 때 가장 큰 노드를 꺼내는 방법

두 가지가 있다.

나는 시간 복잡도를 고려하여 1번 방법으로 채택하였지만, 어떤 방법이든 스케줄링 되는 순서를 무조건 priority 순서로 지정해야 한다.

개선 포인트 2

: running thread 보다, ready_list의 thread의 priority가 더 높다면 즉시 제어를 넘겨준다.(thread_yield())

다음 두 가지 경우가 존재한다.

① 새로운 thread가 추가되는 경우 → thread_create()
② 기존의 thread의 priority가 변경되는 경우 → thread_set_priority()

이 두 경우에 running thread 보다, 우선순위가 클 경우 제어를 넘겨야 한다.

여기까지 했다면

우선순위 역전 priority-donate-@@@ 얘네만 남았다.

설현아

어서오세요! ☺️ 후회 없는 내일을 위해 오늘을 열심히 살아가는 개발자입니다.