run queue와 thread_resched | LK

QUESTION

run queue와 thread_resched 단계에서 실제로 바뀌는 상태는 무엇인가?

호출 이유가 yield인지 block인지 preemption인지에 따라 현재 thread를 다시 enqueue하는 조건이 달라진다. interrupt disable 구간도 함께 본다.

같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다. 이 문장을 기준으로 코드를 위에서 아래로 읽으면, 함수 이름을 외우는 대신 어느 시점에 어떤 상태를 신뢰할 수 있는지 판단할 수 있다.

STRUCTURE

객체와 주소가 놓이는 구조

그림 1. run queue와 thread_resched에서 입력, 내부 상태, 출력의 경계

입력과 전제내부 상태외부로 공개되는 결과

01priority queues

02current_thread

03saved registers

04scheduler lock

INVARIANT

같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다.

run_queue / current_thread를 중심에 놓고 왼쪽의 입력이 어떤 검사를 거쳐 오른쪽 결과로 공개되는지 표시했다. 실제 디버깅에서는 각 블록의 주소와 크기를 로그에 대입한다.

CALL PATH

실행 흐름

그림 2. 정상 경로의 주요 호출과 상태 전달

timer/wakeup/yield

scheduler lock

run queue pick

arch context switch

next thread

화살표는 단순 호출 순서만 뜻하지 않는다. 각 단계가 성공을 반환할 때 다음 단계가 읽을 수 있는 상태가 무엇인지 함께 확인한다. 오류 반환이 발생하면 바로 다음 화살표로 진행하지 않고 해당 단계의 정리 경로를 따라간다.

STATE LEDGER

단계별 입력과 출력

호출 순서를 함수 이름으로만 외우지 않고, 각 단계가 무엇을 받아 무엇을 공개하는지 적은 표다. 실제 소스에서 생산 필드가 다르면 표를 고치는 방식으로 사용한다.

#	단계	진입 시 신뢰할 상태	성공 뒤 남아야 할 상태	다음 소비자
01	`timer/wakeup/yield`	interrupt를 막은 scheduler 임계 구역	priority queues	scheduler lock
02	`scheduler lock`	timer/wakeup/yield 완료 상태	current_thread	run queue pick
03	`run queue pick`	scheduler lock 완료 상태	saved registers	arch context switch
04	`arch context switch`	run queue pick 완료 상태	scheduler lock	next thread
05	`next thread`	arch context switch 완료 상태	scheduler lock	최종 최종 부트로더 이미지 또는 다음 stage

공통 불변 조건: 같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다. 한 단계의 출력이 다음 단계의 입력 조건을 만족하지 않으면 오류가 실제로 드러난 위치보다 앞의 생산 단계부터 조사한다.

UPSTREAM SOURCE

원본 코드

아래 코드는 LK upstream 1eb9917의 kernel/thread.c에서 46-134줄을 그대로 가져온 것이다. 설명을 위해 실제 코드를 가짜 의사 코드로 바꾸지 않았다.

commit1eb99171efae98867d4be4a5bd6479ea03f43ac9symbolvoid 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

LINE BY LINE

46-134줄 해설

원본에 보이는 모든 줄을 순서대로 설명한다. 빈 줄도 block 경계로 남겨, 코드와 설명의 위치가 어긋나지 않게 했다.

46(빈 줄)

이전 block 경계까지의 동작과 /* global thread list */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 priority queues 상태가 아래 블록의 입력으로 사용되는 경계다.

47/* global thread list */

원본 주석이 'global thread list'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

48static struct list_node thread_list;

static struct list_node thread_list를 선언한다. 함수 안 선언이면 현재 stack frame, file scope와 static이면 image의 data/BSS에 놓인다. 이 값이 run_queue / current_thread를 직접 소유하는지 pointer만 빌리는지, interrupt를 막은 scheduler 임계 구역를 벗어난 뒤에도 참조되는지 다음 대입과 callback 등록까지 따라간다.

49(빈 줄)

static struct list_node thread_list;까지의 동작과 /* master thread spinlock */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

50/* master thread spinlock */

원본 주석이 'master thread spinlock'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

51spin_lock_t thread_lock = SPIN_LOCK_INITIAL_VALUE;

spin_lock_t thread_lock에 SPIN_LOCK_INITIAL_VALUE를 = 연산으로 반영해 현재 scope의 계산 결과를 저장한다. 이후 next thread 단계가 이 값을 처음 소비하는 지점을 찾는다. 실패 경로가 이 field를 이전 값으로 되돌리거나 객체 전체를 폐기하는지도 확인한다.

52(빈 줄)

spin_lock_t thread_lock = SPIN_LOCK_INITIAL_VALUE;까지의 동작과 /* the run queue */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

53/* the run queue */

원본 주석이 'the run queue'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

54static struct list_node run_queue[NUM_PRIORITIES];

static struct list_node run_queue[NUM_PRIORITIES]를 선언한다. 함수 안 선언이면 현재 stack frame, file scope와 static이면 image의 data/BSS에 놓인다. 이 값이 run_queue / current_thread를 직접 소유하는지 pointer만 빌리는지, interrupt를 막은 scheduler 임계 구역를 벗어난 뒤에도 참조되는지 다음 대입과 callback 등록까지 따라간다.

55static uint32_t run_queue_bitmap;

원본 55번 줄의 static uint32_t run_queue_bitmap;는 앞의 static struct list_node run_queue[NUM_PRIORITIES]; 결과를 받아 다음 다음 block 경계로 넘기는 중간 연산이다. 이 줄이 바꾸는 register·field·list link를 찾고, 변경 뒤에도 '같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다' 조건이 유지되는지 확인한다.

56(빈 줄)

static uint32_t run_queue_bitmap;까지의 동작과 /* make sure the bitmap is large enough to cover our number of priorities */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

57/* make sure the bitmap is large enough to cover our number of priorities */

원본 주석이 'make sure the bitmap is large enough to cover our number of priorities'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

58STATIC_ASSERT(NUM_PRIORITIES <= sizeof(run_queue_bitmap) * 8);

STATIC_ASSERT(NUM_PRIORITIES <에 sizeof(run_queue_bitmap) * 8)를 = 연산으로 반영해 현재 scope의 계산 결과를 저장한다. 이후 next thread 단계가 이 값을 처음 소비하는 지점을 찾는다. 실패 경로가 이 field를 이전 값으로 되돌리거나 객체 전체를 폐기하는지도 확인한다.

59(빈 줄)

STATIC_ASSERT(NUM_PRIORITIES <= sizeof(run_queue_bitmap) * 8);까지의 동작과 /* the idle thread(s) (statically allocated) */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

60/* the idle thread(s) (statically allocated) */

원본 주석이 'the idle thread(s) (statically allocated)'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

61#if WITH_SMP

#if 전처리 지시문으로 이 줄 아래의 code가 binary에 존재할지를 결정한다. architecture 또는 build stage 조건을 여닫는다. 현재 .config와 compiler의 -dD -E 출력에서 실제로 남은 branch를 확인한 뒤 line-by-line 흐름에 포함한다.

62static thread_t _idle_threads[SMP_MAX_CPUS];

원본 62번 줄의 static thread_t _idle_threads[SMP_MAX_CPUS];는 앞의 #if WITH_SMP 결과를 받아 다음 #define idle_thread(cpu) (&_idle_threads[cpu])로 넘기는 중간 연산이다. 이 줄이 바꾸는 register·field·list link를 찾고, 변경 뒤에도 '같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다' 조건이 유지되는지 확인한다.

63#define idle_thread(cpu) (&_idle_threads[cpu])

#define 전처리 지시문으로 이 줄 아래의 code가 binary에 존재할지를 결정한다. architecture 또는 build stage 조건을 여닫는다. 현재 .config와 compiler의 -dD -E 출력에서 실제로 남은 branch를 확인한 뒤 line-by-line 흐름에 포함한다.

64#else

#else 전처리 지시문으로 이 줄 아래의 code가 binary에 존재할지를 결정한다. architecture 또는 build stage 조건을 여닫는다. 현재 .config와 compiler의 -dD -E 출력에서 실제로 남은 branch를 확인한 뒤 line-by-line 흐름에 포함한다.

65static thread_t _idle_thread;

원본 65번 줄의 static thread_t _idle_thread;는 앞의 #else 결과를 받아 다음 #define idle_thread(cpu) (&_idle_thread)로 넘기는 중간 연산이다. 이 줄이 바꾸는 register·field·list link를 찾고, 변경 뒤에도 '같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다' 조건이 유지되는지 확인한다.

66#define idle_thread(cpu) (&_idle_thread)

67#endif

#endif 전처리 지시문으로 이 줄 아래의 code가 binary에 존재할지를 결정한다. architecture 또는 build stage 조건을 여닫는다. 현재 .config와 compiler의 -dD -E 출력에서 실제로 남은 branch를 확인한 뒤 line-by-line 흐름에 포함한다.

68(빈 줄)

#endif까지의 동작과 /* local routines */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

69/* local routines */

원본 주석이 'local routines'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

70static void thread_resched(void);

thread_resched(void)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

71static void idle_thread_routine(void) __NO_RETURN;

idle_thread_routine(void)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

72(빈 줄)

static void idle_thread_routine(void) __NO_RETURN;까지의 동작과 #if PLATFORM_HAS_DYNAMIC_TIMER에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

73#if PLATFORM_HAS_DYNAMIC_TIMER

74/* preemption timer */

원본 주석이 'preemption timer'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

75static timer_t preempt_timer[SMP_MAX_CPUS];

원본 75번 줄의 static timer_t preempt_timer[SMP_MAX_CPUS];는 앞의 /* preemption timer */ 결과를 받아 다음 #endif로 넘기는 중간 연산이다. 이 줄이 바꾸는 register·field·list link를 찾고, 변경 뒤에도 '같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다' 조건이 유지되는지 확인한다.

76#endif

77(빈 줄)

#endif까지의 동작과 /* run queue manipulation */에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

78/* run queue manipulation */

원본 주석이 'run queue manipulation'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

79static void insert_in_run_queue_head(thread_t *t) {

insert_in_run_queue_head 함수 정의가 시작된다. 입력은 thread_t *t이며, interrupt를 막은 scheduler 임계 구역에서 호출된다는 전제로 반환 전까지의 상태 변화를 읽는다.

80DEBUG_ASSERT(t->magic == THREAD_MAGIC);

DEBUG_ASSERT(t->magic에 = THREAD_MAGIC)를 = 연산으로 반영해 run_queue / current_thread와 연결된 field를 갱신한다. 이후 next thread 단계가 이 값을 처음 소비하는 지점을 찾는다. 실패 경로가 이 field를 이전 값으로 되돌리거나 객체 전체를 폐기하는지도 확인한다.

81DEBUG_ASSERT(t->state == THREAD_READY);

DEBUG_ASSERT(t->state에 = THREAD_READY)를 = 연산으로 반영해 run_queue / current_thread와 연결된 field를 갱신한다. 이후 next thread 단계가 이 값을 처음 소비하는 지점을 찾는다. 실패 경로가 이 field를 이전 값으로 되돌리거나 객체 전체를 폐기하는지도 확인한다.

82DEBUG_ASSERT(!list_in_list(&t->queue_node));

list_in_list(&t->queue_node))를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

83DEBUG_ASSERT(arch_ints_disabled());

arch_ints_disabled())를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

84DEBUG_ASSERT(spin_lock_held(&thread_lock));

spin_lock_held(&thread_lock))를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

85(빈 줄)

DEBUG_ASSERT(spin_lock_held(&thread_lock));까지의 동작과 list_add_head(&run_queue[t->priority], &t->queue_node);에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

86list_add_head(&run_queue[t->priority], &t->queue_node);

list_add_head(&run_queue[t->priority], &t->queue_node)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

87run_queue_bitmap |= (1<<t->priority);

run_queue_bitmap에 (1<<t->priority)를 |= 연산으로 반영해 현재 scope의 계산 결과를 저장한다. 이후 next thread 단계가 이 값을 처음 소비하는 지점을 찾는다. 실패 경로가 이 field를 이전 값으로 되돌리거나 객체 전체를 폐기하는지도 확인한다.

88}

현재 block, initializer 또는 호출의 경계를 닫는다. 이 지점까지 획득한 resource가 성공 경로와 실패 경로에서 대칭인지 점검한다.

89(빈 줄)

}까지의 동작과 static void insert_in_run_queue_tail(thread_t *t) {에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

90static void insert_in_run_queue_tail(thread_t *t) {

insert_in_run_queue_tail 함수 정의가 시작된다. 입력은 thread_t *t이며, interrupt를 막은 scheduler 임계 구역에서 호출된다는 전제로 반환 전까지의 상태 변화를 읽는다.

91DEBUG_ASSERT(t->magic == THREAD_MAGIC);

92DEBUG_ASSERT(t->state == THREAD_READY);

93DEBUG_ASSERT(!list_in_list(&t->queue_node));

94DEBUG_ASSERT(arch_ints_disabled());

95DEBUG_ASSERT(spin_lock_held(&thread_lock));

96(빈 줄)

DEBUG_ASSERT(spin_lock_held(&thread_lock));까지의 동작과 list_add_tail(&run_queue[t->priority], &t->queue_node);에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

97list_add_tail(&run_queue[t->priority], &t->queue_node);

list_add_tail(&run_queue[t->priority], &t->queue_node)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

98run_queue_bitmap |= (1<<t->priority);

99}

현재 block, initializer 또는 호출의 경계를 닫는다. 이 지점까지 획득한 resource가 성공 경로와 실패 경로에서 대칭인지 점검한다.

100(빈 줄)

}까지의 동작과 static void wakeup_cpu_for_thread(thread_t *t)에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

101static void wakeup_cpu_for_thread(thread_t *t)

wakeup_cpu_for_thread 함수 정의가 시작된다. 입력은 thread_t *t이며, interrupt를 막은 scheduler 임계 구역에서 호출된다는 전제로 반환 전까지의 상태 변화를 읽는다.

102{

바로 위 함수·조건·초기화의 block이 열린다. 이 scope 안에서 만들어지는 지역 객체와 오류 이동 지점을 run_queue / current_thread의 수명에 맞춰 묶어 읽는다.

103/* Wake up the core to which this thread is pinned

원본 주석이 'Wake up the core to which this thread is pinned'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

104* or wake up all if thread is unpinned */

원본 주석이 'or wake up all if thread is unpinned'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

105int pinned_cpu = thread_pinned_cpu(t);

int pinned_cpu = thread_pinned_cpu(t)를 선언한다. 함수 안 선언이면 현재 stack frame, file scope와 static이면 image의 data/BSS에 놓인다. 이 값이 run_queue / current_thread를 직접 소유하는지 pointer만 빌리는지, interrupt를 막은 scheduler 임계 구역를 벗어난 뒤에도 참조되는지 다음 대입과 callback 등록까지 따라간다.

106if (pinned_cpu < 0)

pinned_cpu < 0를 검사해 진행 여부를 가른다. 거짓 경로와 참 경로 중 어느 쪽이 '같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다' 조건을 보존하는지 다음 return 또는 goto까지 따라간다.

107mp_reschedule(MP_CPU_ALL_BUT_LOCAL, 0);

mp_reschedule(MP_CPU_ALL_BUT_LOCAL, 0)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

108else

원본 108번 줄의 else는 앞의 mp_reschedule(MP_CPU_ALL_BUT_LOCAL, 0); 결과를 받아 다음 mp_reschedule(1U << pinned_cpu, 0);로 넘기는 중간 연산이다. 이 줄이 바꾸는 register·field·list link를 찾고, 변경 뒤에도 '같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다' 조건이 유지되는지 확인한다.

109mp_reschedule(1U << pinned_cpu, 0);

mp_reschedule(1U << pinned_cpu, 0)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

110}

현재 block, initializer 또는 호출의 경계를 닫는다. 이 지점까지 획득한 resource가 성공 경로와 실패 경로에서 대칭인지 점검한다.

111(빈 줄)

}까지의 동작과 static void init_thread_struct(thread_t *t, const char *name) {에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

112static void init_thread_struct(thread_t *t, const char *name) {

init_thread_struct 함수 정의가 시작된다. 입력은 thread_t *t, const char *name이며, interrupt를 막은 scheduler 임계 구역에서 호출된다는 전제로 반환 전까지의 상태 변화를 읽는다.

113memset(t, 0, sizeof(thread_t));

memset(t, 0, sizeof(thread_t))를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

114t->magic = THREAD_MAGIC;

t->magic에 THREAD_MAGIC를 = 연산으로 반영해 run_queue / current_thread와 연결된 field를 갱신한다. 이후 next thread 단계가 이 값을 처음 소비하는 지점을 찾는다. 실패 경로가 이 field를 이전 값으로 되돌리거나 객체 전체를 폐기하는지도 확인한다.

115thread_set_pinned_cpu(t, -1);

thread_set_pinned_cpu(t, -1)를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

116strlcpy(t->name, name, sizeof(t->name));

strlcpy(t->name, name, sizeof(t->name))를 호출한다. 반환값을 직접 사용하지 않으므로 이 함수가 실패를 내부 처리하는지 확인해야 한다. pointer 인자는 run_queue / current_thread의 소유권을 넘기는지 호출 동안만 빌리는지 구분하고, 호출 뒤 공개되는 상태를 scheduler lock 항목과 대조한다.

117}

현재 block, initializer 또는 호출의 경계를 닫는다. 이 지점까지 획득한 resource가 성공 경로와 실패 경로에서 대칭인지 점검한다.

118(빈 줄)

}까지의 동작과 /**에서 시작하는 동작을 나누는 빈 줄이다. 앞 블록이 만든 scheduler lock 상태가 아래 블록의 입력으로 사용되는 경계다.

119/**

원본 주석이 'block boundary'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

120* @brief Create a new thread

원본 주석이 '@brief Create a new thread'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

121*

원본 주석이 'block boundary'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

122* This function creates a new thread. The thread is initially suspended, so you

원본 주석이 'This function creates a new thread. The thread is initially suspended, so you'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

123* need to call thread_resume() to execute it.

원본 주석이 'need to call thread_resume() to execute it.'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

124*

원본 주석이 'block boundary'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

125* @param name Name of thread

원본 주석이 '@param name Name of thread'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

126* @param entry Entry point of thread

원본 주석이 '@param entry Entry point of thread'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

127* @param arg Arbitrary argument passed to entry()

원본 주석이 '@param arg Arbitrary argument passed to entry()'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

128* @param priority Execution priority for the thread.

원본 주석이 '@param priority Execution priority for the thread.'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

129* @param stack_size Stack size for the thread.

원본 주석이 '@param stack_size Stack size for the thread.'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

130*

원본 주석이 'block boundary'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

131* Thread priority is an integer from 0 (lowest) to 31 (highest). Some standard

원본 주석이 'Thread priority is an integer from 0 (lowest) to 31 (highest). Some standard'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

132* prioritys are defined in <kernel/thread.h>:

원본 주석이 'prioritys are defined in <kernel/thread.h>:'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

133*

원본 주석이 'block boundary'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

134* HIGHEST_PRIORITY

원본 주석이 'HIGHEST_PRIORITY'라고 기록한 줄이다. 바로 아래 구현이 이 전제와 같은 순서·단위를 사용하는지 대조한다.

DETAILS

내부 동작을 더 깊게 읽기

진입 조건을 먼저 고정한다

timer/wakeup/yield에서 들어온 실행은 interrupt를 막은 scheduler 임계 구역에 놓여 있다. 이때 interrupt, MMU/cache, stack, heap 중 무엇이 이미 준비되었는지 소스의 호출자까지 올라가 확인한다. 같은 함수라도 SPL, relocation 전후, app thread처럼 호출 문맥이 달라지면 허용되는 API와 지연 시간이 달라진다.

호출 이유가 yield인지 block인지 preemption인지에 따라 현재 thread를 다시 enqueue하는 조건이 달라진다. interrupt disable 구간도 함께 본다.

중심 객체의 생성과 공개를 나눈다

이 글의 중심 객체는 run_queue / current_thread다. 메모리를 확보한 시점, 필드를 채운 시점, 전역 list나 다른 subsystem에 공개한 시점을 구분한다. 공개 뒤 오류가 발생한다면 목록에서 제거하고 child, buffer, reference를 역순으로 정리하는지 확인한다.

빌드 산출물 관점에서는 최종 부트로더 이미지 안에 해당 symbol과 section이 실제로 포함되었는지도 map과 objdump로 검증한다.

주소, 크기와 정렬을 계산한다

부트 코드의 오류는 논리보다 주소 계산에서 먼저 드러나는 경우가 많다. source range, destination range, header가 말하는 payload size, block 또는 page 단위를 표로 적고 각 구간의 끝 주소를 직접 계산한다. 끝 주소는 start + size - 1인지 exclusive end인지 API 계약을 확인한다.

같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다.

성공 flag와 실제 완료 시점을 맞춘다

scheduler lock → run queue pick → arch context switch 구간에서는 부분 초기화 상태가 생길 수 있다. flag, list insertion, callback 등록, storage write 완료 중 무엇이 성공의 기준인지 찾는다. hardware write나 DMA가 포함되면 함수 반환과 장치 완료가 같은 시점인지도 확인한다.

다른 CPU, interrupt handler, USB completion 또는 shell command가 상태를 관찰할 수 있다면 memory ordering과 lock 범위도 함께 읽는다.

마지막 handoff의 계약을 적는다

정상 경로는 next thread에서 끝난다. 이 단계가 함수 반환인지, scheduler 전환인지, 다른 image로의 비복귀 분기인지 구분한다. 비복귀 handoff라면 cache clean/invalidate, interrupt disable, 장치 quiesce, argument register와 FDT 또는 image address가 최종 점검 항목이다.

반환하는 경로라면 caller가 오류와 부분 성공을 구분하고 다음 후보 또는 복구 경로를 선택하는지 확인한다.

IMPLEMENTATION NOTES

구현을 읽을 때 놓치기 쉬운 부분

run queue 조작은 interrupt-disabled lock 범위에서 읽는다

현재 thread를 queue에 다시 넣고 다음 runnable thread를 고르는 동안 timer interrupt나 다른 CPU가 같은 queue를 만질 수 있다. spinlock만 볼 것이 아니라 local interrupt state와 scheduler disable count를 함께 확인한다.

priority별 queue와 bitmap이 있다면 두 표현이 항상 일치해야 한다. dequeue 뒤 bitmap bit를 지우는 조건을 빈 queue 경계에서 검증한다.

reschedule 요청과 실제 context switch는 같은 시점이 아니다

interrupt handler는 reschedule flag만 세우고 exception return에서 switch할 수 있으며 thread 문맥은 즉시 thread_resched()를 호출할 수 있다. latency는 요청 timestamp부터 새 thread가 실행한 첫 instruction까지 측정한다.

preemption disable 구간이 길면 높은 priority thread가 runnable이어도 상한이 깨진다.

SMP에서는 current thread와 CPU affinity를 함께 본다

thread가 다른 CPU run queue로 이동할 수 있으면 per-CPU current pointer, affinity mask와 IPI가 일관되어야 한다. lock 획득 순서가 CPU 번호에 따라 달라지면 migration과 wakeup이 교차할 때 deadlock이 생긴다.

두 CPU에서 같은 thread가 동시에 RUNNING으로 보이지 않는다는 불변 조건을 trace로 검증한다.

OBJECT LIFETIME

객체와 수명

대상	만들어지는 시점	유효 범위	확인할 조건
`run_queue / current_thread`	scheduler lock	next thread 또는 오류 정리 완료까지	같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다.
입력 buffer / metadata	timer/wakeup/yield	parse와 검증이 끝날 때까지	길이, 정렬, 소유권, 변조 가능성
등록된 list / descriptor	run queue pick	subsystem 종료 또는 image handoff까지	이중 등록, dangling pointer, 오류 unwind
hardware 또는 persistent state	실제 write/probe가 완료된 뒤	reset 또는 명시적 해제·갱신까지	flush, timeout, 전원 차단, rollback
`최종 부트로더 이미지`	link/image 생성 시점	다음 stage가 새 image로 교체할 때까지	load address, entry, section과 header 일치

FAILURE PATH

실패 지점과 증상

#	조건	관찰되는 증상	먼저 볼 단계
01	이중 enqueue	같은 thread 두 번 선택	scheduler lock
02	lock count 불일치	영구 preemption disable	run queue pick
03	ISR 반환 flag 누락	높은 우선순위 thread 지연	arch context switch

로그가 끊긴 마지막 함수만 고치지 않는다. 그 함수가 받은 주소, size, flag가 만들어진 앞 단계까지 올라가고, 오류 뒤 등록 객체와 hardware 상태가 남았는지도 확인한다.

EVIDENCE

소스 밖에서 확인할 증거

소스 해석은 실제 빌드 산출물과 target 로그로 닫아야 한다. 아래 명령의 보드 이름과 toolchain prefix는 사용 중인 빌드 환경에 맞게 바꾼다.

#	목적	명령 또는 계측	판정 기준
01	빌드 구성	`make <project> -j1`	platform, target, app 선택과 linker 입력을 로그로 남긴다.
02	symbol과 주소	`nm -n build-*/lk.elf \| grep 'void thread_resched'`	init hook, app descriptor와 함수가 어느 주소에 놓였는지 확인한다.
03	어셈블리 대조	`objdump -drS build-*/lk.elf`	thread 전환과 interrupt disable 구간의 실제 명령을 확인한다.
04	초기화 순서	`init level 전후에 current_time_hires()와 함수 이름 기록`	level 내부 순서와 지연을 serial log로 남긴다.
05	문맥 확인	`current_thread, interrupt state, stack pointer 기록`	함수가 bootstrap thread인지 scheduler 이후 thread인지 구분한다.

LAB

직접 확인할 실험

01
context switch마다 old/new priority 기록
scheduler lock 진입 전후에 priority queues의 주소·크기·반환값과 timestamp를 함께 남긴다. 결과는 정상 부팅 여부로 끝내지 말고 같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다. 조건이 처음 깨지는 줄을 기록한다.
02
run queue bitmap과 list 일관성 검사
run queue pick 진입 전후에 current_thread의 주소·크기·반환값과 timestamp를 함께 남긴다. 결과는 정상 부팅 여부로 끝내지 말고 같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다. 조건이 처음 깨지는 줄을 기록한다.
03
timer tick과 explicit yield의 call stack 비교
arch context switch 진입 전후에 saved registers의 주소·크기·반환값과 timestamp를 함께 남긴다. 결과는 정상 부팅 여부로 끝내지 말고 같은 순간에 하나의 thread만 RUNNING이며 runnable thread는 정확히 하나의 run queue에 존재해야 한다. 조건이 처음 깨지는 줄을 기록한다.

PRIMARY REFERENCES

원문과 다음 글

kernel/thread.cupstream 1eb9917 원본 파일 LK source tree기준 commit 1eb99171efae