QUESTION
누가 current를 되돌리고, 누가 next를 고르는가?
thread_resched()는 current가 이미 RUNNING 이외의 상태이고, interrupt가 막혀 있으며 thread_lock이 잡혀 있다는 전제를 검사한다. 재삽입은 이 함수의 일이 아니다. yield·preempt·block·wait queue 등의 호출자가 먼저 상태와 queue를 정한 뒤 들어온다 (kernel/thread.c:459).
고정 commit에는 priority별 전역 run queue 배열과 bitmap이 있다. get_top_thread(cpu)가 높은 우선순위부터 현재 CPU에서 실행 가능한 READY 후보를 제거해 반환하고, 없으면 해당 CPU의 idle thread를 고른다 (kernel/thread.c:53, kernel/thread.c:431).
STRUCTURE
전역 priority queue와 CPU별 선택
이 버전은 CPU별 run queue가 아니라 전역 배열이다. SMP 후보 필터는 CPU pinning을 확인한다 (kernel/thread.c:439).
CALL PATH
호출자별 재삽입과 조건부 선점
thread_resched()는 newthread == oldthread면 실제 context switch 없이 돌아온다. 타이머 요청·IPI 요청도 그 자체로 즉시 다른 thread 실행을 보장하지 않는다 (kernel/thread.c:490, arch/arm64/exceptions.S:110).
STATE LEDGER
호출 경로별 current 처리
| 진입 경로 | current의 사전 처리 | next 선택 조건 | 근거 |
|---|---|---|---|
| thread_yield | READY; quantum=0; non-idle tail | get_top_thread; 없으면 idle | kernel/thread.c:611 |
| thread_preempt | READY; non-idle, quantum>0 head / ≤0 tail | get_top_thread; 없으면 idle | kernel/thread.c:647 |
| thread_block | caller가 BLOCKED 및 대기 queue 설정 | 현재는 run queue에 넣지 않음 | kernel/thread.c:675 |
| thread_sleep | SLEEPING; timer callback이 READY head 삽입 | 깨우기 전에는 다른 후보 | kernel/thread.c:725 |
| thread_resume | 대상 SUSPENDED→READY head | 로컬 yield는 진입 interrupt 상태에 따라 | kernel/thread.c:275 |
THREAD_LOCK은 spin_lock_irqsave이고 unlock은 irqrestore다. 별도 scheduler disable count가 이 코드에 있는 것처럼 해석하지 않는다 (kernel/include/kernel/thread.h:206).
VISUAL WALKTHROUGH
선택 상태와 요청 경로를 나란히 보기
두 그림은 전역 우선순위 queue 선택과 여러 reschedule 계기를 분리한다. 상태 전이와 CPU mask를 별도로 관찰한다.
current의 상태와 queue는 호출자가 준비하며, thread_resched는 다음 실행 대상을 선택한다.
READY 후보를 만드는 경로와 선점 요청을 전달하는 경로는 서로 다르다.
thread_resume→SUSPENDED→READY, head→선택 후보tick→quantum≤0 때 INT_RESCHEDULE→IRQ의 preemptwait wake→BLOCKED→READY, head→선택 후보get_top_thread→priority + CPU pin 검사→후보 / idlemp_reschedule→SMP 대상 CPU 필터 후 IPI→조건부 IRQUPSTREAM SOURCE
원본 코드
아래 코드는 LK upstream 1eb9917의 kernel/thread.c에서 46-134줄을 그대로 가져온 것이다.
46
47/* global thread list */
48static struct list_node thread_list;
49
50/* master thread spinlock */
51spin_lock_t thread_lock = SPIN_LOCK_INITIAL_VALUE;
52
53/* the run queue */
54static struct list_node run_queue[NUM_PRIORITIES];
55static uint32_t run_queue_bitmap;
56
57/* make sure the bitmap is large enough to cover our number of priorities */
58STATIC_ASSERT(NUM_PRIORITIES <= sizeof(run_queue_bitmap) * 8);
59
60/* the idle thread(s) (statically allocated) */
61#if WITH_SMP
62static thread_t _idle_threads[SMP_MAX_CPUS];
63#define idle_thread(cpu) (&_idle_threads[cpu])
64#else
65static thread_t _idle_thread;
66#define idle_thread(cpu) (&_idle_thread)
67#endif
68
69/* local routines */
70static void thread_resched(void);
71static void idle_thread_routine(void) __NO_RETURN;
72
73#if PLATFORM_HAS_DYNAMIC_TIMER
74/* preemption timer */
75static timer_t preempt_timer[SMP_MAX_CPUS];
76#endif
77
78/* run queue manipulation */
79static void insert_in_run_queue_head(thread_t *t) {
80 DEBUG_ASSERT(t->magic == THREAD_MAGIC);
81 DEBUG_ASSERT(t->state == THREAD_READY);
82 DEBUG_ASSERT(!list_in_list(&t->queue_node));
83 DEBUG_ASSERT(arch_ints_disabled());
84 DEBUG_ASSERT(spin_lock_held(&thread_lock));
85
86 list_add_head(&run_queue[t->priority], &t->queue_node);
87 run_queue_bitmap |= (1<<t->priority);
88}
89
90static void insert_in_run_queue_tail(thread_t *t) {
91 DEBUG_ASSERT(t->magic == THREAD_MAGIC);
92 DEBUG_ASSERT(t->state == THREAD_READY);
93 DEBUG_ASSERT(!list_in_list(&t->queue_node));
94 DEBUG_ASSERT(arch_ints_disabled());
95 DEBUG_ASSERT(spin_lock_held(&thread_lock));
96
97 list_add_tail(&run_queue[t->priority], &t->queue_node);
98 run_queue_bitmap |= (1<<t->priority);
99}
100
101static void wakeup_cpu_for_thread(thread_t *t)
102{
103 /* Wake up the core to which this thread is pinned
104 * or wake up all if thread is unpinned */
105 int pinned_cpu = thread_pinned_cpu(t);
106 if (pinned_cpu < 0)
107 mp_reschedule(MP_CPU_ALL_BUT_LOCAL, 0);
108 else
109 mp_reschedule(1U << pinned_cpu, 0);
110}
111
112static void init_thread_struct(thread_t *t, const char *name) {
113 memset(t, 0, sizeof(thread_t));
114 t->magic = THREAD_MAGIC;
115 thread_set_pinned_cpu(t, -1);
116 strlcpy(t->name, name, sizeof(t->name));
117}
118
119/**
120 * @brief Create a new thread
121 *
122 * This function creates a new thread. The thread is initially suspended, so you
123 * need to call thread_resume() to execute it.
124 *
125 * @param name Name of thread
126 * @param entry Entry point of thread
127 * @param arg Arbitrary argument passed to entry()
128 * @param priority Execution priority for the thread.
129 * @param stack_size Stack size for the thread.
130 *
131 * Thread priority is an integer from 0 (lowest) to 31 (highest). Some standard
132 * prioritys are defined in <kernel/thread.h>:
133 *
134 * HIGHEST_PRIORITY
READING CONTRACT
원본 발췌와 구현 위치
기존 주 원본 kernel/thread.c 46–134행과 보충 421–479행은 고정 원문과 일치해 그대로 보존했다. L70은 thread_resched 선언이고 실제 구현은 L469에서 시작한다. 기존 보충은 구현의 앞부분만 포함하므로 아래 경계를 이어 읽는다.
선택·동일 thread 반환·CPU 소유권
480 THREAD_STATS_INC(reschedules);
481
482 newthread = get_top_thread(cpu);
483
484 DEBUG_ASSERT(newthread);
485
486 newthread->state = THREAD_RUNNING;
487
488 oldthread = current_thread;
489
490 if (newthread == oldthread)
491 return;
492
493 /* set up quantum for the new thread if it was consumed */
494 if (newthread->remaining_quantum <= 0) {
495 newthread->remaining_quantum = 5; // XXX make this smarter
496 }
497
498 /* mark the cpu ownership of the threads */
499 thread_set_curr_cpu(oldthread, -1);
500 thread_set_curr_cpu(newthread, cpu);yield가 재삽입을 수행
611 void thread_yield(void) {
612 thread_t *current_thread = get_current_thread();
613
614 DEBUG_ASSERT(current_thread->magic == THREAD_MAGIC);
615 DEBUG_ASSERT(current_thread->state == THREAD_RUNNING);
616
617 THREAD_LOCK(state);
618
619 THREAD_STATS_INC(yields);
620
621 /* we are yielding the cpu, so stick ourselves into the tail of the run queue and reschedule */
622 current_thread->state = THREAD_READY;
623 current_thread->remaining_quantum = 0;
624 if (likely(!thread_is_idle(current_thread))) { /* idle thread doesn't go in the run queue */
625 insert_in_run_queue_tail(current_thread);
626 }
627 thread_resched();
628
629 THREAD_UNLOCK(state);preempt의 quantum별 head/tail 분기
647 void thread_preempt(void) {
648 thread_t *current_thread = get_current_thread();
649
650 DEBUG_ASSERT(current_thread->magic == THREAD_MAGIC);
651 DEBUG_ASSERT(current_thread->state == THREAD_RUNNING);
652
653 #if THREAD_STATS
654 if (!thread_is_idle(current_thread))
655 THREAD_STATS_INC(preempts); /* only track when a meaningful preempt happens */
656 #endif
657
658 KEVLOG_THREAD_PREEMPT(current_thread);
659
660 THREAD_LOCK(state);
661
662 /* we are being preempted, so we get to go back into the front of the run queue if we have quantum left */
663 current_thread->state = THREAD_READY;
664 if (likely(!thread_is_idle(current_thread))) { /* idle thread doesn't go in the run queue */
665 if (current_thread->remaining_quantum > 0)
666 insert_in_run_queue_head(current_thread);
667 else
668 insert_in_run_queue_tail(current_thread); /* if we're out of quantum, go to the tail of the queue */
669 }
670 thread_resched();
671
672 THREAD_UNLOCK(state);
673 }tick은 재선점 요청만 반환
711 enum handler_return thread_timer_tick(struct timer *t, lk_time_t now, void *arg) {
712 thread_t *current_thread = get_current_thread();
713
714 if (thread_is_real_time_or_idle(current_thread))
715 return INT_NO_RESCHEDULE;
716
717 current_thread->remaining_quantum--;
718 if (current_thread->remaining_quantum <= 0) {
719 return INT_RESCHEDULE;
720 } else {
721 return INT_NO_RESCHEDULE;
722 }
723 }비동적 timer 플랫폼은 timer.c가 10ms periodic timer를 등록하고 tick에서 callback 반환을 모은다. 동적 timer 플랫폼은 thread_resched()가 일반 thread에 필요한 preemption timer를 켠다 (kernel/timer.c:271, kernel/timer.c:283, kernel/thread.c:535). ARM64 IRQ 예시에서는 platform_irq 반환이 0이 아닐 때에만 thread_preempt()를 부른다 (arch/arm64/exceptions.S:110).
RELATED SOURCE
함께 읽어야 하는 원본 코드
첫 코드 조각만으로 동작이 완성되지 않는 경우 호출 매크로, 객체 정의와 실제 실행 목록을 같은 페이지에 묶었다. 각 조각은 같은 기준 commit에서 가져왔다.
01. 현재 CPU에서 우선순위가 가장 높은 thread 선택
kernel/thread.c 421-479줄이다.
421 thread_resched();
422
423 panic("somehow fell through thread_exit()\n");
424}
425
426static void idle_thread_routine(void) {
427 for (;;)
428 arch_idle();
429}
430
431static thread_t *get_top_thread(int cpu) {
432 thread_t *newthread;
433 uint32_t local_run_queue_bitmap = run_queue_bitmap;
434
435 while (local_run_queue_bitmap) {
436 /* find the first (remaining) queue with a thread in it */
437 uint next_queue = sizeof(run_queue_bitmap) * 8 - 1 - __builtin_clz(local_run_queue_bitmap);
438
439 list_for_every_entry(&run_queue[next_queue], newthread, thread_t, queue_node) {
440#if WITH_SMP
441 if (newthread->pinned_cpu < 0 || newthread->pinned_cpu == cpu)
442#endif
443 {
444 list_delete(&newthread->queue_node);
445
446 if (list_is_empty(&run_queue[next_queue]))
447 run_queue_bitmap &= ~(1<<next_queue);
448
449 return newthread;
450 }
451 }
452
453 local_run_queue_bitmap &= ~(1<<next_queue);
454 }
455 /* no threads to run, select the idle thread for this cpu */
456 return idle_thread(cpu);
457}
458
459/**
460 * @brief Cause another thread to be executed.
461 *
462 * Internal reschedule routine. The current thread needs to already be in whatever
463 * state and queues it needs to be in. This routine simply picks the next thread and
464 * switches to it.
465 *
466 * This is probably not the function you're looking for. See
467 * thread_yield() instead.
468 */
469void thread_resched(void) {
470 thread_t *oldthread;
471 thread_t *newthread;
472
473 thread_t *current_thread = get_current_thread();
474 uint cpu = arch_curr_cpu_num();
475
476 DEBUG_ASSERT(arch_ints_disabled());
477 DEBUG_ASSERT(spin_lock_held(&thread_lock));
478 DEBUG_ASSERT(current_thread->state != THREAD_RUNNING);
479
DETAILS
선택·전환을 구성하는 실제 검사
호출자가 current 상태를 결정한다
thread_resched()는 current_thread->state != THREAD_RUNNING을 assert한다. yield는 tail, preempt는 남은 quantum에 따라 head/tail, block은 대기 queue 상태를 만든다 (kernel/thread.c:476, kernel/thread.c:611, kernel/thread.c:647).
bitmap은 후보 priority, list는 실제 후보
get_top_thread()는 높은 priority bit부터 탐색하고, SMP에서는 pinning이 맞는 thread만 고른다. 제거 후 해당 list가 비면 bitmap bit를 지운다. 적합한 READY 후보가 없으면 idle thread를 반환한다 (kernel/thread.c:431).
같은 thread 선택은 switch가 아니다
선택한 next를 RUNNING으로 표시한 뒤 old와 같으면 반환한다. 다를 때만 quantum 재설정, CPU 소유권·통계·동적 timer 갱신, 최종 arch_context_switch()로 진행한다 (kernel/thread.c:486, kernel/thread.c:598).
timer는 요청 값을 전달한다
thread_timer_tick()은 real-time 또는 idle이면 재선점을 요구하지 않고, 일반 thread의 quantum을 줄여 0 이하일 때 INT_RESCHEDULE을 반환한다. IRQ glue가 이 값을 처리하는 방식은 architecture 경로로 확인한다 (kernel/thread.c:711, arch/arm64/exceptions.S:110).
원격 CPU는 대상 필터 뒤 깨운다
wakeup_cpu_for_thread()는 pinning에 따라 대상 mask를 넘긴다. 이 호출은 flags=0이므로 SMP의 mp_reschedule()가 비활성·실시간 실행 중 CPU와 로컬 CPU를 제외한다. 다른 호출에서 MP_RESCHEDULE_FLAG_REALTIME을 지정하면 실시간 CPU 제외를 생략한다. 여기서 실시간 CPU 표시는 REAL_TIME flag와 DEFAULT_PRIORITY 초과 조건을 함께 사용하며, tick의 flag 검사와 다르다. non-SMP 구현은 빈 stub이다 (kernel/thread.c:101, kernel/mp.c:26, kernel/include/kernel/mp.h:86).
IMPLEMENTATION NOTES
세 가지 경계 조건
전역 queue와 idle fallback
run queue는 CPU별 배열이 아니라 전역 priority list다. CPU pinning 때문에 최고 priority list에 항목이 있어도 현재 CPU에 맞는 항목이 없을 수 있다. 이때 탐색을 계속하거나 idle로 간다 (kernel/thread.c:53, kernel/thread.c:439).
tick 빈도는 platform timer 방식에 달려 있다
비동적 timer는 timer_init()에서 10ms periodic tick을 등록한다. 동적 timer는 일반 thread로 전환할 때 preemption timer를 주기 설정하고 real-time/idle로 전환할 때 취소할 수 있다 (kernel/timer.c:283, kernel/thread.c:535).
IRQ 반환과 실제 선택 시점 분리
ARM64 IRQ 예시는 platform_irq 반환이 0이면 preempt를 건너뛴다. 0이 아니면 thread_preempt()로 들어가지만, thread_resched()의 old==next 경로에서는 switch가 없다 (arch/arm64/exceptions.S:110, kernel/thread.c:490).
OBJECT LIFETIME
scheduler가 읽는 상태
| 대상 | 갱신 지점 | 소비 지점 | 불변 조건 |
|---|---|---|---|
| run_queue[p] | READY head/tail 삽입 | get_top_thread가 후보 제거 | RUNNING은 queue에 없음 |
| run_queue_bitmap | 삽입 때 bit 설정; 마지막 항목 제거 때 해제 | 높은 priority부터 탐색 | bit와 list 비어 있음 상태 일치 |
| current_thread | thread_resched의 next 선택 뒤 갱신 | 선택한 CPU의 실행 문맥 | 한 thread가 두 CPU에서 RUNNING 금지 |
| idle_thread(cpu) | 초기화 때 CPU별 정적 객체 | 적합한 READY 후보가 없을 때 | run queue에 삽입하지 않음 |
FAILURE PATH
진단에 유용한 어긋남
| 관찰 | 가능한 상태 어긋남 | 확인 원본 |
|---|---|---|
| READY인데 선택되지 않음 | CPU pinning 또는 더 높은 priority 후보 | kernel/thread.c:431 |
| tick 후 switch 없음 | real-time/idle, quantum 잔여, IRQ 반환 0, old==next | kernel/thread.c:711 |
| 한 thread가 두 번 보임 | queue_node 중복 삽입 또는 상태/lock 위반 | kernel/thread.c:79 |
| block 뒤에도 실행 후보 | BLOCKED 상태와 wait queue link, 기존 READY link 유무 확인 | kernel/thread.c:1090 |
| 원격 CPU 반응 없음 | active/realtime/local CPU mask·pinning·IPI 경로 확인 | kernel/mp.c:26 |
실제 lock·queue·CPU mask를 함께 확인한다. 이 코드에는 별도 scheduler disable count가 없다.
EVIDENCE
빌드와 runtime을 함께 대조
선택한 LK project의 symbol이 남아 있는 ELF를 사용한다. nm에는 C 선언문이 아니라 symbol 이름이 나온다.
| 목적 | 명령 또는 계측 | 판정 기준 |
|---|---|---|
| scheduler symbol | nm -an <ELF> | grep -E '[[:space:]](thread_resched|thread_preempt|thread_timer_tick)$' | 빌드에 존재하는 symbol 이름·주소 |
| queue 일관성 | run_queue_bitmap과 각 priority list 길이 기록 | bit set ⇔ 해당 list nonempty |
| 선택과 전환 | old/new thread·priority·CPU·time 기록 | old==next와 실제 arch switch 구분 |
| timer·IRQ | remaining_quantum와 IRQ 반환·preempt 기록 | 요청, preempt 진입, switch를 각각 분리 |
| 원격 요청 | pinning·active/realtime CPU mask·IPI 기록 | 대상 mask에 로컬 CPU가 포함되지 않음 |
LAB
세 가지 상태 실험
- 01yield와 preempt의 위치 비교
같은 priority 후보 둘을 두고 yield 후 tail, quantum이 남은 preempt 후 head, 소진된 preempt 후 tail을 기록한다.
- 02bitmap과 idle fallback 확인
현재 CPU에 맞는 READY 후보를 없애고 idle 선택을 관찰한다. SMP pinning이 있으면 다른 CPU용 후보는 분리해 기록한다.
- 03tick 요청과 실제 switch 분리
tick의 INT_RESCHEDULE, IRQ의 thread_preempt 진입, old/new thread가 다른지를 서로 다른 timestamp로 기록한다.
PRIMARY REFERENCES