1# LK Threading and Scheduler System
2
3## Overview
4
5The LK kernel provides a comprehensive preemptive multithreading system with a priority-based scheduler. The threading system is designed to support both single-core and multi-core (SMP) systems with features including real-time scheduling, thread synchronization primitives, and comprehensive debugging capabilities.
6
7## Core Components
8
9### Thread Structure
10
11Each thread in the system is represented by a `thread_t` structure containing:
12
13- **Identification**: Magic number, name, and list membership
14- **Scheduling State**: Priority, state, remaining quantum, and CPU affinity
15- **Stack Management**: Stack pointer, size, and bounds checking
16- **Synchronization**: Wait queue blocking and return codes
17- **Architecture-specific**: CPU registers and context
18- **Statistics**: Runtime statistics and performance counters (debug builds)
19
20### Thread States
21
22Threads can exist in one of the following states:
23
24- **THREAD_SUSPENDED**: Newly created thread not yet running
25- **THREAD_READY**: Thread ready to run, in the run queue
26- **THREAD_RUNNING**: Currently executing thread
27- **THREAD_BLOCKED**: Waiting on a synchronization primitive
28- **THREAD_SLEEPING**: Sleeping for a specified time period
29- **THREAD_DEATH**: Thread has exited and awaits cleanup
30
31## Priority System
32
33### Priority Levels
34
35The scheduler uses a 32-level priority system (0-31):
36
37- **LOWEST_PRIORITY (0)**: Minimum priority level
38- **IDLE_PRIORITY (0)**: Reserved for idle threads
39- **LOW_PRIORITY (8)**: Low priority tasks
40- **DEFAULT_PRIORITY (16)**: Standard thread priority
41- **HIGH_PRIORITY (24)**: High priority tasks
42- **DPC_PRIORITY (30)**: Deferred Procedure Call priority
43- **HIGHEST_PRIORITY (31)**: Maximum priority level
44
45### Real-time Threads
46
47Threads can be marked as real-time using `thread_set_real_time()`. Real-time threads:
48
49- Bypass preemption timers when priority > DEFAULT_PRIORITY
50- Receive preferential scheduling treatment
51- Are tracked separately for CPU load balancing
52
53## Scheduler Algorithm
54
55### Run Queue Management
56
57The scheduler maintains:
58
59- **Per-priority run queues**: Array of linked lists, one per priority level
60- **Run queue bitmap**: Bit field indicating which priority levels have ready threads
61- **Round-robin within priority**: Threads of equal priority are time-sliced
62
63### Thread Selection
64
65The scheduler uses the following algorithm:
66
671. Find the highest priority level with ready threads (using `__builtin_clz`)
682. Select the first thread from that priority's run queue
693. For SMP systems, consider CPU affinity and pinning
704. Fall back to idle thread if no threads are ready
71
72### Preemption and Time Slicing
73
74- **Quantum-based preemption**: Non-real-time threads receive time slices
75- **Timer-driven preemption**: Periodic timer interrupts check quantum expiration
76- **Voluntary yielding**: Threads can yield CPU with `thread_yield()`
77- **Priority preemption**: Higher priority threads immediately preempt lower priority ones
78
79## SMP (Symmetric Multiprocessing) Support
80
81### CPU Affinity
82
83- **Pinned threads**: Can be restricted to specific CPUs
84- **Load balancing**: Unpinned threads distribute across available CPUs
85- **CPU state tracking**: Idle, busy, and real-time CPU states
86
87### Inter-CPU Communication
88
89- **Reschedule IPIs**: Wake up remote CPUs for newly ready threads
90- **CPU-specific idle threads**: Each CPU has its own idle thread
91- **Per-CPU preemption timers**: Independent timer management per CPU
92
93## Thread Management API
94
95### Thread Creation
96
97```c
98thread_t *thread_create(const char *name,
99                       thread_start_routine entry,
100                       void *arg,
101                       int priority,
102                       size_t stack_size);
103
104thread_t *thread_create_etc(thread_t *t,
105                           const char *name,
106                           thread_start_routine entry,
107                           void *arg,
108                           int priority,
109                           void *stack,
110                           size_t stack_size);
111```
112
113### Thread Control
114
115```c
116status_t thread_resume(thread_t *t);          // Start suspended thread
117void thread_exit(int retcode);               // Terminate current thread
118void thread_sleep(lk_time_t delay);          // Sleep for specified time
119status_t thread_join(thread_t *t, int *retcode, lk_time_t timeout);
120status_t thread_detach(thread_t *t);         // Detach thread for auto-cleanup
121```
122
123### Thread Properties
124
125```c
126void thread_set_name(const char *name);      // Change thread name
127void thread_set_priority(int priority);      // Change thread priority
128status_t thread_set_real_time(thread_t *t);  // Mark as real-time
129```
130
131### Scheduler Control
132
133```c
134void thread_yield(void);      // Voluntary CPU yield
135void thread_preempt(void);    // Handle preemption
136void thread_block(void);      // Block current thread
137void thread_unblock(thread_t *t, bool resched); // Unblock thread
138```
139
140## Wait Queues
141
142### Purpose
143
144Wait queues provide the foundation for thread synchronization primitives:
145
146- Mutexes and semaphores
147- Condition variables
148- Event notifications
149- Resource waiting
150
151### API
152
153```c
154void wait_queue_init(wait_queue_t *wait);
155status_t wait_queue_block(wait_queue_t *wait, lk_time_t timeout);
156int wait_queue_wake_one(wait_queue_t *wait, bool reschedule, status_t error);
157int wait_queue_wake_all(wait_queue_t *wait, bool reschedule, status_t error);
158void wait_queue_destroy(wait_queue_t *wait, bool reschedule);
159```
160
161### Timeout Support
162
163- **INFINITE_TIME**: Block indefinitely
164- **0**: Return immediately with ERR_TIMED_OUT
165- **Positive values**: Block for specified milliseconds
166- **Timer-based wakeup**: Automatic unblocking on timeout
167
168## Memory Management
169
170### Stack Management
171
172- **Automatic allocation**: Default stack allocation during thread creation
173- **Custom stacks**: Support for user-provided stack memory
174- **Stack bounds checking**: Debug-mode overflow detection (THREAD_STACK_BOUNDS_CHECK)
175- **Stack usage tracking**: High-water mark monitoring (THREAD_STACK_HIGHWATER)
176- **Delayed cleanup**: Safe stack deallocation after context switch
177
178### Thread Structure Cleanup
179
180- **Reference counting**: Automatic cleanup for detached threads
181- **Join semantics**: Manual cleanup for joined threads
182- **Delayed free**: Safe memory reclamation using heap_delayed_free()
183
184## Thread Local Storage (TLS)
185
186### Predefined TLS Slots
187
188- **TLS_ENTRY_CONSOLE**: Current console context
189- **TLS_ENTRY_UTHREAD**: User-mode thread context
190- **TLS_ENTRY_LKUSER**: LK user library context
191
192### TLS API
193
194```c
195uintptr_t tls_get(uint entry);
196uintptr_t tls_set(uint entry, uintptr_t val);
197```
198
199## Debugging and Statistics
200
201### Thread Statistics (THREAD_STATS)
202
203Per-thread statistics:
204
205- Total runtime
206- Schedule count
207- Last run timestamp
208
209Per-CPU statistics:
210
211- Idle time
212- Context switches
213- Preemptions and yields
214- Reschedule IPIs
215
216### Debug Features
217
218- **Magic number validation**: Corruption detection
219- **Stack overflow detection**: Bounds checking with guard pages
220- **Thread state validation**: Assertion checking
221- **Thread dumping**: Complete thread state inspection
222
223### Debug API
224
225```c
226void dump_thread(thread_t *t);        // Dump single thread
227void dump_all_threads(void);          // Dump all threads
228void dump_threads_stats(void);        // Dump statistics
229```
230
231## Initialization
232
233### Early Initialization
234
235```c
236void thread_init_early(void);
237```
238
239- Initialize global data structures
240- Create bootstrap thread
241- Set up run queues and thread list
242
243### Full Initialization
244
245```c
246void thread_init(void);
247```
248
249- Initialize preemption timers
250- Complete threading system setup
251
252### SMP Initialization
253
254```c
255void thread_secondary_cpu_init_early(void);  // Per-CPU early init
256void thread_secondary_cpu_entry(void);       // Secondary CPU entry point
257void thread_become_idle(void);               // Become idle thread
258```
259
260## Performance Considerations
261
262### Scheduler Overhead
263
264- **O(1) thread selection**: Bitmap-based priority queue
265- **Minimal context switch overhead**: Architecture-optimized switching
266- **Lockless fast paths**: Reduced lock contention where possible
267
268### SMP Scalability
269
270- **CPU-local data structures**: Reduced cache line bouncing
271- **Intelligent load balancing**: CPU affinity and pinning support
272- **Efficient IPI usage**: Targeted CPU wakeups
273
274### Real-time Responsiveness
275
276- **Priority inheritance**: Through wait queue mechanisms
277- **Bounded latency**: Real-time thread preemption guarantees
278- **Timer precision**: High-resolution timer support
279
280## Integration Points
281
282### Architecture Layer
283
284- **arch_thread_initialize()**: Architecture-specific thread setup
285- **arch_context_switch()**: Low-level context switching
286- **arch_get/set_current_thread()**: Current thread management
287
288### Platform Layer
289
290- **Timer integration**: Preemption timer management
291- **Power management**: CPU idle state handling
292- **Debug LED control**: Visual debugging support
293
294### Virtual Memory
295
296- **Address space switching**: VMM integration for process isolation
297- **Stack allocation**: Virtual memory for thread stacks
298
299## Error Handling
300
301### Common Error Codes
302
303- **ERR_TIMED_OUT**: Wait operation timeout
304- **ERR_NOT_BLOCKED**: Thread not in blocked state
305- **ERR_THREAD_DETACHED**: Operation on detached thread
306- **ERR_OBJECT_DESTROYED**: Wait queue destroyed
307- **ERR_INVALID_ARGS**: Invalid function arguments
308
309### Panic Conditions
310
311- Stack overflow detection
312- Invalid thread magic numbers
313- Inconsistent thread state
314- Failed assertions in debug builds
315
316## Best Practices
317
318### Thread Creation
319
320- Use appropriate priority levels
321- Specify reasonable stack sizes
322- Choose meaningful thread names
323- Consider CPU affinity for performance-critical threads
324
325### Synchronization
326
327- Always use proper locking with wait queues
328- Handle timeout conditions appropriately
329- Avoid priority inversion through careful design
330- Use real-time threads sparingly
331
332### Resource Management
333
334- Detach threads that don't need join semantics
335- Handle thread cleanup properly
336- Monitor stack usage in debug builds
337- Use TLS appropriately for per-thread data
338
339This threading and scheduler system provides a robust foundation for kernel and application development in the LK operating system, with careful attention to performance, scalability, and debugging capabilities.
340