우선순위 스케줄링

이게 스케줄러 구현하면서도 헷갈렸는데

• 우선순위에 따른 스케줄링 규칙
  • A의 우선순위 > B의 우선순위이면, A가 실행되고 B는 실행되지 않음
  • A의 우선순위 = B의 우선순위이면, A와 B는 RR 방식으로 실행됨

스케줄러가 실행되는 경우

thread_yield 호출 시

(1) 타이머 인터럽트 시, 현재 쓰레드 실행 후 틱 수(thread_ticks)가 TIME_SLICE=4 이상일 때

• 아래 있는 intr_yield_on_return는 인터럽터핸들러 반환 후 thread_yield 호출

#define TIME_SLICE 4

/* Called by the timer interrupt handler at each timer tick.
   Thus, this function runs in an external interrupt context. */
void
thread_tick (void) {
	struct thread *t = thread_current ();
	// 생략.
	/* Enforce preemption. */
	if (++thread_ticks >= TIME_SLICE)
		intr_yield_on_return ();
}

(2). 수동으로 thread_yield를 호출

• 이후 thread_yield 함수에선, 현재 실행 중인 쓰레드를 ready_list에 삽입 (이때 priority의 내림차순을 따르도록 삽입하게 구현해야 함)
  • 동일한 priority의 쓰레드가 ready_list에 있는 경우, 해당 쓰레드들 이후 위치에 현재 쓰레드를 삽입.
  • 17 삽입해야하는데 연결리스트가 17-17-17-13이면 17이랑 13 사이에 삽입해야한단 소리임.

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)
		// [구현 2-1A] Priority 내림차순을 지킬 수 있게, 올바른 위치에 삽입할 것.
		list_insert_ordered(&ready_list, &curr->elem, dsc_priority, NULL);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

• 이후 do_schedule 내 schedule에선 ready_list 중 맨 앞 쓰레드, 즉 priority가 제일 높은 노드로 문맥 전환(thread_launch) 수행
  • 단 현재쓰레드와 레디리스트 맨 앞 쓰레드가 동일할 시, 문맥전환이 이루어지지 않음.
• 이때 레디리스트엔 아까 yield하면서 삽입된 쓰레드가 포함되어 있음에 유의할 것.
  • 레디리스트 맨 앞 쓰레드가thread_yield에서 삽입된 현재 쓰레드인 경우, 다른 쓰레드로 전환 없이 현재 쓰레드가 유지됨. 그래서 만약 priority 높은 쓰레드가 계속 CPU를 차지하면 더 낮은 쓰레드들은 절대로 실행되지 못함.
  • 레디리스트 맨 앞 쓰레드가 현재 쓰레드와 동일한 priority의 다른 쓰레드인 경우, 해당 쓰레드로 문맥 전환. 이런 방식 덕분에 Priority가 동일한 쓰레드끼린 round robin으로 스케줄링이 이루어짐.
  • 다른 쓰레드의 priority가 현재 쓰레드보다 더 높은 경우, 해당 쓰레드로 문맥 전환됨.

static void
schedule (void) {
	struct thread *curr = running_thread (); // 현재 돌아가는 쓰레드
	struct thread *next = next_thread_to_run (); // 연결리스트 맨앞쓰레드

	/* Mark status as running. */
	// 다음 쓰레드를 실행한단 소리지
	next->status = THREAD_RUNNING;

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

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

	// 당연히 똑같은 노드면 문맥전환해 줄 필요가 없겠지
	if (curr != next) {
		thread_launch (next);
	}
}

쓰레드 종료 시

• 현재 실행중인 쓰레드의 종료 (thread_exit)
• do_schedule->schedule 호출하고, 이후에는 앞서 설명한 대로 레디리스트 통해 스케줄링됨.

/* Deschedules the current thread and destroys it.  Never
   returns to the caller. */
void
thread_exit (void) {
	ASSERT (!intr_context ());
	intr_disable ();
	do_schedule (THREAD_DYING);
}