LK · source analysis

run queue와 thread_resched

호출자의 current 재삽입과 thread_resched의 next 선택·조건부 문맥 전환을 구분합니다.

이 글은 LK upstream 고정 commit 1eb9917의 thread 구현을 설명한다. 실제 timer·CPU 동작은 선택한 platform 구성에서 확인한다.

Series
06 / 20
Baseline
upstream 1eb9917
Commit
1eb99171efae
Source
kernel/thread.c:46-134 (발췌 범위)

누가 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).

전역 priority queue와 CPU별 선택

그림 1. bitmap·list·idle fallback의 관계
run_queue[0..31]priority마다 list; READY thread만 link. head/tail은 호출 경로가 정한다.
run_queue_bitmap비어 있지 않은 priority bit. 삽입 때 설정, 선택 후 list가 비면 해제.
현재 CPUget_top_thread(cpu)
높은 priority부터 검사WITH_SMP이면 pinned_cpu가 이 CPU에 맞는 후보만
후보 제거 또는 idleREADY 후보가 없으면 idle_thread(cpu)
RUNNING current는 run queue에 동시에 있지 않는다. idle thread도 run queue에 넣지 않는다.

이 버전은 CPU별 run queue가 아니라 전역 배열이다. SMP 후보 필터는 CPU pinning을 확인한다 (kernel/thread.c:439).

호출자별 재삽입과 조건부 선점

그림 2. yield·preempt·block이 갈라졌다가 선택 단계에서 만남
thread_yield()RUNNING→READY, quantum=0, non-idle은 tail 삽입
thread_preempt()RUNNING→READY; quantum 남으면 head, 소진이면 tail; idle 제외
thread_block()·sleep·waitcaller가 BLOCKED/SLEEPING과 대기 queue를 준비; run queue 재삽입 없음
caller가 상태·queue 준비interrupt disabled + thread_lock
thread_resched()get_top_thread(cpu) 또는 idle
동일 thread면 반환다르면 CPU 소유권·timer 갱신 후 arch_context_switch
timer/IRQtick이 INT_RESCHEDULE을 반환한 경우 architecture IRQ 경로가 preempt를 호출
다른 CPU · SMP만wakeup_cpu_for_thread → mp_reschedule → 대상 필터·IPI; 대상 IRQ가 재선점 판단

thread_resched()는 newthread == oldthread면 실제 context switch 없이 돌아온다. 타이머 요청·IPI 요청도 그 자체로 즉시 다른 thread 실행을 보장하지 않는다 (kernel/thread.c:490, arch/arm64/exceptions.S:110).

호출 경로별 current 처리

진입 경로current의 사전 처리next 선택 조건근거
thread_yieldREADY; quantum=0; non-idle tailget_top_thread; 없으면 idlekernel/thread.c:611
thread_preemptREADY; non-idle, quantum>0 head / ≤0 tailget_top_thread; 없으면 idlekernel/thread.c:647
thread_blockcaller가 BLOCKED 및 대기 queue 설정현재는 run queue에 넣지 않음kernel/thread.c:675
thread_sleepSLEEPING; 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).

선택 상태와 요청 경로를 나란히 보기

두 그림은 전역 우선순위 queue 선택과 여러 reschedule 계기를 분리한다. 상태 전이와 CPU mask를 별도로 관찰한다.

그림 3. thread_resched 안에서만 일어나는 선택·전환

current의 상태와 queue는 호출자가 준비하며, thread_resched는 다음 실행 대상을 선택한다.

01interrupt off · thread_lock 보유 확인
02get_top_thread(cpu)
03READY 후보 제거 또는 idle
04next = RUNNING
05old == next ? 반환 : CPU/timer 갱신
06arch_context_switch
그림 4. READY 생산과 선점 요청은 서로 다른 경로

READY 후보를 만드는 경로와 선점 요청을 전달하는 경로는 서로 다르다.

01thread_resumeSUSPENDED→READY, head선택 후보
02tickquantum≤0 때 INT_RESCHEDULEIRQ의 preempt
03wait wakeBLOCKED→READY, head선택 후보
04get_top_threadpriority + CPU pin 검사후보 / idle
05mp_rescheduleSMP 대상 CPU 필터 후 IPI조건부 IRQ

원본 코드

아래 코드는 LK upstream 1eb9917의 kernel/thread.c에서 46-134줄을 그대로 가져온 것이다.

commit1eb99171efae98867d4be4a5bd6479ea03f43ac9anchor · L70void thread_resched(void)
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

원본 발췌와 구현 위치

기존 주 원본 kernel/thread.c 46–134행과 보충 421–479행은 고정 원문과 일치해 그대로 보존했다. L70은 thread_resched 선언이고 실제 구현은 L469에서 시작한다. 기존 보충은 구현의 앞부분만 포함하므로 아래 경계를 이어 읽는다.

선택·동일 thread 반환·CPU 소유권

kernel/thread.c L480–500

 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가 재삽입을 수행

kernel/thread.c L611–629

 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 분기

kernel/thread.c L647–673

 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은 재선점 요청만 반환

kernel/thread.c L711–723

 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).

함께 읽어야 하는 원본 코드

첫 코드 조각만으로 동작이 완성되지 않는 경우 호출 매크로, 객체 정의와 실제 실행 목록을 같은 페이지에 묶었다. 각 조각은 같은 기준 commit에서 가져왔다.

01. 현재 CPU에서 우선순위가 가장 높은 thread 선택

kernel/thread.c 421-479줄이다.

filekernel/thread.canchor · L431static thread_t *get_top_thread(int cpu)
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

선택·전환을 구성하는 실제 검사

01

호출자가 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).

02

bitmap은 후보 priority, list는 실제 후보

get_top_thread()는 높은 priority bit부터 탐색하고, SMP에서는 pinning이 맞는 thread만 고른다. 제거 후 해당 list가 비면 bitmap bit를 지운다. 적합한 READY 후보가 없으면 idle thread를 반환한다 (kernel/thread.c:431).

03

같은 thread 선택은 switch가 아니다

선택한 next를 RUNNING으로 표시한 뒤 old와 같으면 반환한다. 다를 때만 quantum 재설정, CPU 소유권·통계·동적 timer 갱신, 최종 arch_context_switch()로 진행한다 (kernel/thread.c:486, kernel/thread.c:598).

04

timer는 요청 값을 전달한다

thread_timer_tick()은 real-time 또는 idle이면 재선점을 요구하지 않고, 일반 thread의 quantum을 줄여 0 이하일 때 INT_RESCHEDULE을 반환한다. IRQ glue가 이 값을 처리하는 방식은 architecture 경로로 확인한다 (kernel/thread.c:711, arch/arm64/exceptions.S:110).

05

원격 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).

세 가지 경계 조건

01

전역 queue와 idle fallback

run queue는 CPU별 배열이 아니라 전역 priority list다. CPU pinning 때문에 최고 priority list에 항목이 있어도 현재 CPU에 맞는 항목이 없을 수 있다. 이때 탐색을 계속하거나 idle로 간다 (kernel/thread.c:53, kernel/thread.c:439).

02

tick 빈도는 platform timer 방식에 달려 있다

비동적 timer는 timer_init()에서 10ms periodic tick을 등록한다. 동적 timer는 일반 thread로 전환할 때 preemption timer를 주기 설정하고 real-time/idle로 전환할 때 취소할 수 있다 (kernel/timer.c:283, kernel/thread.c:535).

03

IRQ 반환과 실제 선택 시점 분리

ARM64 IRQ 예시는 platform_irq 반환이 0이면 preempt를 건너뛴다. 0이 아니면 thread_preempt()로 들어가지만, thread_resched()의 old==next 경로에서는 switch가 없다 (arch/arm64/exceptions.S:110, kernel/thread.c:490).

scheduler가 읽는 상태

대상갱신 지점소비 지점불변 조건
run_queue[p]READY head/tail 삽입get_top_thread가 후보 제거RUNNING은 queue에 없음
run_queue_bitmap삽입 때 bit 설정; 마지막 항목 제거 때 해제높은 priority부터 탐색bit와 list 비어 있음 상태 일치
current_threadthread_resched의 next 선택 뒤 갱신선택한 CPU의 실행 문맥한 thread가 두 CPU에서 RUNNING 금지
idle_thread(cpu)초기화 때 CPU별 정적 객체적합한 READY 후보가 없을 때run queue에 삽입하지 않음

진단에 유용한 어긋남

관찰가능한 상태 어긋남확인 원본
READY인데 선택되지 않음CPU pinning 또는 더 높은 priority 후보kernel/thread.c:431
tick 후 switch 없음real-time/idle, quantum 잔여, IRQ 반환 0, old==nextkernel/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가 없다.

빌드와 runtime을 함께 대조

선택한 LK project의 symbol이 남아 있는 ELF를 사용한다. nm에는 C 선언문이 아니라 symbol 이름이 나온다.

목적명령 또는 계측판정 기준
scheduler symbolnm -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·IRQremaining_quantum와 IRQ 반환·preempt 기록요청, preempt 진입, switch를 각각 분리
원격 요청pinning·active/realtime CPU mask·IPI 기록대상 mask에 로컬 CPU가 포함되지 않음

세 가지 상태 실험

  1. 01
    yield와 preempt의 위치 비교

    같은 priority 후보 둘을 두고 yield 후 tail, quantum이 남은 preempt 후 head, 소진된 preempt 후 tail을 기록한다.

  2. 02
    bitmap과 idle fallback 확인

    현재 CPU에 맞는 READY 후보를 없애고 idle 선택을 관찰한다. SMP pinning이 있으면 다른 CPU용 후보는 분리해 기록한다.

  3. 03
    tick 요청과 실제 switch 분리

    tick의 INT_RESCHEDULE, IRQ의 thread_preempt 진입, old/new thread가 다른지를 서로 다른 timestamp로 기록한다.

원문과 다음 글