[pintos] 1주차 - Priority Scheduling 문서 해석 / 코드 해석

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

Priority Scheduling · GitBook

 

Priority Scheduling

레디큐에 현재 실행 중인 스레드보다 우선순위가 높은 스레드가 추가되면 즉시 우선순위가 높은 스레드에게 프로세서를 양보해야 한다.

스레드가 lock, semaphore, condition variable을 기다리고 있다면 가장 높은 우선순위를 가진 waiting 스레드가 첫 번째로 wake되어야 한다.

스레드는 언제나 우선순위가 올라가거나 내려가지만, 우선순위가 내려가서 더 이상 가장 높은 우선 순위를 가지지 못하게 되면 무조건 cpu를 양보해야 한다.

 

스레드 우선순위는 PRI_MIN(0)부터 PRI_MAX(63)까지 존재한다.

숫자가 작으면 낮은 우선순위, 숫자가 크면 높은 우선순위를 뜻한다.

스레드의 처음 초기화되는 우선순위는 thread_create()의 인자로 전달된다.

만약 다른 우선 순위를 선택할 필요가 없으면 PRI_DEFAULT(31)을 사용한다.

PRI_매크로는 thread/thread.h에 선언되어 있으며, 값을 바꿀 수 없다.

 

우선순위 스케줄링의 한 가지 이슈는 ‘우선순위 역전’이다.

high, medium, low 우선순위 스레드를 생각해보라.

h가 l을 기다려야 하고, m은 레디 리스트에 있다면, h는 cpu를 절대 얻을 수 없다. 왜냐하면 우선순위가 낮은 스레드는 cpu를 점유할 수 없기 때문이다.

이 문제를 해결하기 위한 방법은 l이 Lock을 가지고 있는 동안 h에게 우선순위를 ‘donate’하고, l이 Lock을 해제하면 donation을 recall하는 것이다.

 

우선순위 donation을 구현하라.

우선순위 donation이 필요한 모든 상황을 계산해야 할 것이다.

multiple donation을 다루기 위해서, single thread에게 multiple priority가 donate되게 해라.

nested(중첩된) donation도 다뤄야 한다. m과 l 모두 h의 우선순위를 가져야 한다.

필요하다면, nested priority donation의 depth에 8 level과 같은 합리적인 제한을 부과할 수도 있다.

 

lock을 위해 priority donation을 구현해야 한다.

아래 두 가지 함수를 구현하라. 두 함수는 스레드가 본인의 우선순위를 수정하고 검사할 수 있는 함수이다.

두 함수의 skeleton은 threads/thread.c에 있다. void thread_set_priority (int new_priority); → 현재 스레드의 우선순위를 새로 설정한다. 현재 스레드가 더 이상 가장 높은 우선순위가 아니라면 yield한다. int thread_get_priority (void);

→ 현재 스레드의 우선순위를 반환한다. priority donation이 존재한다면, 더 높은(donate된) 우선순위를 반환한다.

 

 

 

next_thread_to_run()

pintos-kaist/threads/thread.c

• run queue가 비어있지 않다면 ****다음 스케줄될 스레드를 선정하여 반환하는 함수
• running thread가 계속 실행될 수 있다면 run queue에 있을 것이다.
• run queue가 비어있다면 idle_thread를 반환한다.

/* Chooses and returns the next thread to be scheduled.  Should
   return a thread from the run queue, unless the run queue is
   empty.  (If the running thread can continue running, then it
   will be in the run queue.)  If the run queue is empty, return
   idle_thread. */
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);
}

 

thread_set_priority()

pintos-kaist/threads/thread.c

• 현재 스레드의 우선순위를 인자로 받은 new_priority로 설정함

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
}

 

pintos-kaist/threads/thread.c

ready_list 구조체

• 스레드 상태가 THREAD_READY인 스레드들이 저장된 리스트
• 언제든 cpu를 점유하여 실행될 준비가 된 스레드들

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;

 

pintos-kaist/threads/thread.c

thread_unblock()

• 인자로 받은 blocked 상태인 스레드를 ready 상태로 바꾼다.
• 스레드가 blocked 상태가 아니면 에러로 판단한다.
• 이 함수는 실행 중인 스레드를 선점하지 않는다.
• 호출부가 인터럽트를 비활성화했다면 자동으로 스레드를 unblock하고 다른 데이터를 update할 수 있다는 것을 예상할 수 있다.???

/* Transitions a blocked thread T to the ready-to-run state.
   This is an error if T is not blocked.  (Use thread_yield() to
   make the running thread ready.)

   This function does not preempt the running thread.  This can
   be important: if the caller had disabled interrupts itself,
   it may expect that it can atomically unblock a thread and
   update other data. */
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);
}

👉🏼 스레드를 unblock하면서 ready_list에 스레드를 list_push_back()으로 넣고 있다.

이 부분을 list_insert_ordered()를 사용하여 ready_list가 pritority가 높은 순서대로 정렬되도록 만들어야 한다.

 

pintos-kaist/threads/thread.c

do_schedule()

• 새로운 프로세스를 스케줄한다.
• 스케줄 시작 시점에는 interrupt가 비활성화되어야 한다.
• 이 함수는 현재 스레드의 상태를 변경하고 다음에 실행될 스레드로 문맥교환을 한다.
• 스케줄 중 printf()를 실행하는 것은 안전하지 않다.

/* Schedules a new process. At entry, interrupts must be off.
 * This function modify current thread's status to status and then
 * finds another thread to run and switches to it.
 * It's not safe to call printf() in the schedule(). */
static void
do_schedule(int status) {
	ASSERT (intr_get_level () == INTR_OFF);
	ASSERT (thread_current()->status == THREAD_RUNNING);
	while (!list_empty (&destruction_req)) {
		struct thread *victim =
			list_entry (list_pop_front (&destruction_req), struct thread, elem);
		palloc_free_page(victim);
	}
	thread_current ()->status = status;
	schedule ();
}

 

thread_yield()

pintos-kaist/threads/thread.c

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
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_insert_ordered(&ready_list, &curr->elem, list_high_priority, NULL);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

👉🏼

thread_yield 함수는 현재 스레드를 ready 상태로 바꾸고 ready_list에 넣는다.

원래는 push_back으로 ready_list의 맨 뒤에 스레드를 넣었는데 list_insert_ordered로 우선 순위에 따라 정렬되도록 만들어야 한다.

/* 인자로 들어온 a, b 스레드 중 priority가 a가 더 높으면 true, b가 더 높으면 false를 리턴 */
bool
list_high_priority(const struct list_elem *a, const struct list_elem *b, void *aux){
	
	struct thread* t_a = list_entry(a, struct thread, elem);
	struct thread* t_b = list_entry(b, struct thread, elem);
	
	//a의 우선순위가 더 작으면 true 리턴
	return t_a->priority > t_b->priority;
}

 

list_insert_ordered()를 사용해서 priority를 기준으로 리스트를 정렬해야 하는데 list_less_func()가 리턴하는 값에 따라서 어떻게 정렬되는지를 모르겠어서… 그걸 봐야겠다.

/* Inserts ELEM in the proper position in LIST, which must be
   sorted according to LESS given auxiliary data AUX.
   Runs in O(n) average case in the number of elements in LIST. */
void
list_insert_ordered (struct list *list, struct list_elem *elem,
		list_less_func *less, void *aux) {
	struct list_elem *e;

	ASSERT (list != NULL);
	ASSERT (elem != NULL);
	ASSERT (less != NULL);

	for (e = list_begin (list); e != list_end (list); e = list_next (e))
		if (less (elem, e, aux))
			break;
	return list_insert (e, elem);
}

👉🏼 리스트를 순회하면서 리스트에 삽입할 elem값과 리스트 요소값(e)을 비교한다.

list_less_func(elem, e) == true 즉 elem이 e보다 작으면 true가 반환되므로 리스트 순회를 멈추고 list_insert(e, elem) 즉 요소값(e) 뒤에 elem을 삽입한다.

less(a, b)가 true이면 a가 b보다 앞에 온다.

/* Inserts ELEM just before BEFORE, which may be either an
   interior element or a tail.  The latter case is equivalent to
   list_push_back(). */
void
list_insert (struct list_elem *before, struct list_elem *elem) {
	ASSERT (is_interior (before) || is_tail (before));
	ASSERT (elem != NULL);

	elem->prev = before->prev;
	elem->next = before;
	before->prev->next = elem;
	before->prev = elem;
}

🔥 list_insert_ordered() 작동 방법 정리 :

• less(a, b)는 a<b이면 true를 반환한다.
• list_insert(x, y)는 x 뒤에 y를 삽입한다.
• 즉 less(a, b)가 a<b일 때 true를 반환하면 list_insert(b, a)가 실행되므로 b 뒤에 a가 삽입됨

 

thread_launch()

pintos-kaist/threads/thread.c

• 새로운 스레드 페이지 테이블을 활성화하여 스레드를 스위치한다.
• 만약 이전 스레드가 죽으면 그 스레드를 종료시킨다.
• 이 함수 호출 시, 방금 스레드 'PREV'에서 전환했고, 새 스레드는 이미 실행 중이며 인터럽트는 여전히 비활성화되어 있다.

/* Switching the thread by activating the new thread's page
   tables, and, if the previous thread is dying, destroying it.

   At this function's invocation, we just switched from thread
   PREV, the new thread is already running, and interrupts are
   still disabled.

   It's not safe to call printf() until the thread switch is
   complete.  In practice that means that printf()s should be
   added at the end of the function. */
static void
thread_launch (struct thread *th) {
	uint64_t tf_cur = (uint64_t) &running_thread ()->tf;
	uint64_t tf = (uint64_t) &th->tf;
	ASSERT (intr_get_level () == INTR_OFF);

	/* The main switching logic.
	 * We first restore the whole execution context into the intr_frame
	 * and then switching to the next thread by calling do_iret.
	 * Note that, we SHOULD NOT use any stack from here
	 * until switching is done. */
	__asm __volatile (
			/* Store registers that will be used. */
			"push %%rax\n"
			"push %%rbx\n"
			"push %%rcx\n"
			/* Fetch input once */
			"movq %0, %%rax\n"
			"movq %1, %%rcx\n"
			"movq %%r15, 0(%%rax)\n"
			"movq %%r14, 8(%%rax)\n"
			"movq %%r13, 16(%%rax)\n"
			"movq %%r12, 24(%%rax)\n"
			"movq %%r11, 32(%%rax)\n"
			"movq %%r10, 40(%%rax)\n"
			"movq %%r9, 48(%%rax)\n"
			"movq %%r8, 56(%%rax)\n"
			"movq %%rsi, 64(%%rax)\n"
			"movq %%rdi, 72(%%rax)\n"
			"movq %%rbp, 80(%%rax)\n"
			"movq %%rdx, 88(%%rax)\n"
			"pop %%rbx\n"              // Saved rcx
			"movq %%rbx, 96(%%rax)\n"
			"pop %%rbx\n"              // Saved rbx
			"movq %%rbx, 104(%%rax)\n"
			"pop %%rbx\n"              // Saved rax
			"movq %%rbx, 112(%%rax)\n"
			"addq $120, %%rax\n"
			"movw %%es, (%%rax)\n"
			"movw %%ds, 8(%%rax)\n"
			"addq $32, %%rax\n"
			"call __next\n"         // read the current rip.
			"__next:\n"
			"pop %%rbx\n"
			"addq $(out_iret -  __next), %%rbx\n"
			"movq %%rbx, 0(%%rax)\n" // rip
			"movw %%cs, 8(%%rax)\n"  // cs
			"pushfq\n"
			"popq %%rbx\n"
			"mov %%rbx, 16(%%rax)\n" // eflags
			"mov %%rsp, 24(%%rax)\n" // rsp
			"movw %%ss, 32(%%rax)\n"
			"mov %%rcx, %%rdi\n"
			"call do_iret\n"
			"out_iret:\n"
			: : "g"(tf_cur), "g" (tf) : "memory"
			);
}

 

next_thread_to_run()

pintos-kaist/threads/thread.c

/* Chooses and returns the next thread to be scheduled.  Should
   return a thread from the run queue, unless the run queue is
   empty.  (If the running thread can continue running, then it
   will be in the run queue.)  If the run queue is empty, return
   idle_thread. */
static struct thread *
next_thread_to_run (void) {
	if (list_empty (&ready_list))													//ready_list가 비어있다면
		return idle_thread;															//idle_thread를 반환
	else																			//레디큐가 비어있지 않다면
		return list_entry (list_pop_front (&ready_list), struct thread, elem);		//ready_list의 가장 앞에 위치하는 스레드를 반환
}

👉🏼

• 아아아ㅏ드디어 schedule()할 때 레디큐에서 어떤 스레드를 가장 먼저 꺼내서 cpu를 할당하는지 정하는 함수 찾음! 이 부분이다.
• ready_list의 가장 앞 부분에 있는 스레드를 반환한다.
• next_thread_to_run()의 호출부를 보면 schedule() 안에서 next thread를 꺼낼 때 사용하고 있다.

static void
schedule (void) {
	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;

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

	if (curr != next) {
		/* If the thread we switched from is dying, destroy its struct
		   thread. This must happen late so that thread_exit() doesn't
		   pull out the rug under itself.
		   We just queuing the page free reqeust here because the page is
		   currently used by the stack.
		   The real destruction logic will be called at the beginning of the
		   schedule(). */
		if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
			ASSERT (curr != next);
			list_push_back (&destruction_req, &curr->elem);
		}

		/* Before switching the thread, we first save the information
		 * of current running. */
		thread_launch (next);
	}
}

 

---

 

sema_init()

pintos-kaist/threads/synch.c

• 세마포어 변수값을 value로 설정하는 함수

/* Initializes semaphore SEMA to VALUE.  A semaphore is a
   nonnegative integer along with two atomic operators for
   manipulating it:

   - down or "P": wait for the value to become positive, then
   decrement it.

   - up or "V": increment the value (and wake up one waiting
   thread, if any). */
void
sema_init (struct semaphore *sema, unsigned value) {
	ASSERT (sema != NULL);

	sema->value = value;
	list_init (&sema->waiters);
}

 

sema_down()

pintos-kaist/threads/synch.c

• 세마포어 변수값을 down시킴 (P연산)
• 세파포어 변수값이 양수가 되기를 기다리다가 양수가 되면 자동으로 감소시킨다.
• 이 함수는 sleep상태일 것이므로, 인터럽트 핸들러 내에서 호출하면 안 된다.
• 이 함수는 인터럽트가 비활성화 상태인 경우에만 호출될 것이다. 하지만 함수가 sleep 상태이면, 다음에 스케줄될 스레드는 인터럽트를 다시 활성화시킬 것이다.

/* Down or "P" operation on a semaphore.  Waits for SEMA's value
   to become positive and then atomically decrements it.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but if it sleeps then the next scheduled
   thread will probably turn interrupts back on. This is
   sema_down function. */
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);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

💡

intr_disable()과 intr_set_level() 사이에 로직을 넣으면 그 로직들이 임계 영역 내에 있게 되는 거야....? 그냥 인터럽트의 영향을 받지 않게 되는 것 뿐인 거 아니야? 임계영역을 지정한다는 건 뮤텍스나 세마포어를 사용해서 이 영역에 접근하는 스레드 개수를 제한하는거잖아. 다른 개념 아닌가? 인터럽트를 disable처리했다가 다시 허용하는 것도 임계영역으로 지정했다고 할 수 있을까?

—-

답변 :

이 질문 정말 훌륭해요! 👏

지금 딱 운영체제에서의 "임계 영역"이라는 개념이 여러 방식으로 구현될 수 있음을 고민하신 거예요.

맞아요, intr_disable()은 뮤텍스나 세마포어처럼 “스레드 개수를 제한”하지는 않지만, 그래도 임계 영역을 보호하는 방법 중 하나입니다.

아래에 차근차근 정리해드릴게요 😊

---

🧩 먼저, "임계 영역(critical section)"이란?

공유 자원을 접근/변경하는 일련의 연산 구간에서,

두 개 이상의 실행 흐름(스레드, 인터럽트 등)이 동시에 접근하면 안 되는 영역

즉, 임계 영역은 개념이에요.

• "한 번에 하나의 실행 흐름만 접근해야 하는 코드 블록"이 바로 임계 영역입니다.
• 이걸 어떻게 보호하느냐는 여러 방식이 있을 수 있어요.

---

🔐 임계 영역을 보호하는 방법: 두 가지 주요 방식

보호 방식 설명 예시

동기화 도구 사용	여러 스레드 사이의 동시 접근을 제한	lock_acquire(), sema_down()
인터럽트 비활성화	단일 CPU에서 인터럽트로 인한 문맥 전환을 방지	intr_disable(), intr_set_level()

---

✅ intr_disable()도 임계 영역 보호 방법이다

Pintos는 단일 CPU 환경(single core) 기반이에요.

따라서 한 순간에 오직 하나의 스레드만 실행될 수 있고,

스레드 전환은 인터럽트 (특히 timer interrupt) 에 의해 발생합니다.

그렇기 때문에:

intr_disable()을 호출하면, 현재 실행 흐름이 인터럽트에 의해 중단되지 않고 임계 영역을 안전하게 통과할 수 있어요.

그래서 intr_disable() ~ intr_set_level() 사이의 코드는 "인터럽트에 의한 경쟁 상태"로부터 보호된 임계 영역이라고 볼 수 있습니다.

---

💡 그럼 동기화 도구와는 어떻게 다르냐?

맞아요! 질문하신 대로 중요한 차이점이 있어요.

항목 intr_disable() 방식 lock, semaphore 방식

보호 대상	인터럽트 핸들러와의 경쟁	다른 스레드와의 경쟁
다중 CPU 지원	❌ 단일 CPU에서만 안정적	✅ 멀티코어까지 대응 가능
스레드 개수 제한	❌ 없음 (전역 동기화 X)	✅ 있음 (한 스레드만 접근 허용)
주 사용 예	커널 내부 / 빠른 보호 필요	사용자 코드 / 다중 스레드 보호

---

✨ 요약하면

• intr_disable() ~ intr_set_level() 사이의 코드는 "임계 영역"이 맞습니다.
• 다만 이는 스레드 간 동기화 도구가 아니라, 인터럽트 차단을 통해 구현된 임계 영역입니다.
• Pintos처럼 단일 CPU 커널 코드에서는 간단하고 빠른 보호 방법으로 많이 사용돼요.

---

🚀 즉, “임계 영역”은 무엇을 보호해야 하느냐에 따라 구현 방법이 달라지는 개념이에요.

지금처럼 정확하게 “보호 수단과 개념의 차이”를 고민하신 건 정말 깊이 있는 이해로 가는 길이에요!

더 궁금하신 포인트가 있다면 계속 이어서 도와드릴게요 🙂

 

💡

(위와 이어지는 질문) 그러니까 임계 영역이란 개념이 범용적인 거지? intr_disable ~ intr_set_level은 인터럽트로부터의 보호를 받을 수 있다는 관점에서 임계영역일 수 있는데, 여러 스레드가 여전히 동시에 접근할 수 있다는 관점에서는 임계 영역이 여전히 아닌거고..? 그리고 여러 스레드가 동시에 접근 불가능하게까지 만들려면 intr_disable ~ intr_set_level과 세마포어/뮤텍스를 함께 쓰면 되는거고? —-

답변 :

네!!! 완벽하게 이해하셨어요! 🎯

지금 말씀하신 내용을 요약하자면

임계 영역은 "개념"이고 intr_disable()과 세마포어/락은 그 개념을 구현하는 "방법"들인데, 각각 보호 범위와 목적이 다르다 라는 걸 정확히 짚으셨어요 👏

 

💡

(또 이어지는 질문)

그럼 timer_sleep() 내에서 임계영역을 intr_disable(), intr_set_level로 사용하는 이유는 현재 스레드를 sleep_list에 넣고 blocked 상태로 만드는 중간에 timer_interrupt가 발생해서 cpu 점유 스레드가 바뀌는 상황을 방지하기 위한 목적인거네?

 

 

 

sema_try_down()

pintos-kaist/threads/synch.c

• semaphore 변수가 양수이면 1 감소시키고 true를 반환, 양수가 아니면 감소시키지 못하고 false를 반환하는 함수
• 인터럽트 핸들러에 의해 호출되는 함수

/* Down or "P" operation on a semaphore, but only if the
   semaphore is not already 0.  Returns true if the semaphore is
   decremented, false otherwise.

   This function may be called from an interrupt handler. */
bool
sema_try_down (struct semaphore *sema) {
	enum intr_level old_level;
	bool success;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (sema->value > 0) //semaphore 변수가 양수이면
	{
		sema->value--; //semaphore 변수값을 1 감소시킴
		success = true; //semaphore 변수 감소 성공했으면 true 리턴
	}
	else
		success = false; //감소 실패했으면 false 리턴
	intr_set_level (old_level);

	return success;
}

 

sema_up()

pintos-kaist/threads/synch.c

• semaphore변수를 1 증가시키고, sema를 기다리는 스레드가 있다면 그 중 하나를 깨워서(현재는 우선순위 스케줄링을 구현하면서 깨우기 전에 우선순위가 큰 순서로 정렬하는 로직을 추가하였음!) ready_list에 넣는 함수
• 인터럽트 핸들러에 의해 호출되는 함수

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;
	intr_set_level (old_level);
}