【作者：张佩】【原始链接：www.yiiyee.cn/blog】
任务管理
LK支持多任务，并且也支持多核。多任务和调度，是LK内核最复杂的功能。一般的嵌入是系统，为了实现简单和便利部署的考虑，会把多任务实现得比较简单，比如uos这样的rtos系统便是了。但LK其实有比较丰富而全面的多任务支持的基础。这使得一些功能更全面的微内核系统比如Zircon，会选择基于它进行开发。
线程结构体
每个内核实现都会为线程创建一个结构体，用来管理任务的执行和维护线程状态。由于无受限的多任务支持能力，所以系统中的线程数量和功能，是不受限的。所以要有一种管理设施，能够对所有的任务进行无区别的管理（某些时候是有区别的，比如idle线程、init线程等，但很少）。这个模块就是内核的任务管理器。而它管理这些任务的抓手，就是线程结构体。
下面是LK定义的线程结构体：
typedef struct thread {
int magic;
struct list_node thread_list_node;
/* active bits */
struct list_node queue_node;
int priority;
enum thread_state state;
int remaining_quantum;
unsigned int flags;
#if WITH_SMP
int curr_cpu;
int pinned_cpu; /* only run on pinned_cpu if >= 0 */
#endif
#if WITH_KERNEL_VM
vmm_aspace_t *aspace;
#endif
/* if blocked, a pointer to the wait queue */
struct wait_queue *blocking_wait_queue;
status_t wait_queue_block_ret;
/* architecture stuff */
struct arch_thread arch;
/* stack stuff */
void *stack;
size_t stack_size;
/* entry point */
thread_start_routine entry;
void *arg;
/* return code */
int retcode;
struct wait_queue retcode_wait_queue;
/* thread local storage */
uintptr_t tls[MAX_TLS_ENTRY];
char name[32];
} thread_t;
成员变量magic：
LK内核实现的一个特点是把内核的基本能力，通过一系列的内核对象进行暴露。或者也可以说LK内核是以内核对象为实现方式的。线程对象是这类基本对象之一。LK内核在实现内核对象的时候，有一个有趣的特点，是它：用奇异数作为对象类型的识别标识，同时也用来进行类型验证。
线程对象的奇异数是：#define THREAD_MAGIC (0x74687264) // 'thrd'
成员变量thread_list_node:
内核的任务管理器需要管理一系列的任务，所以需要这些任务能够自动地组织在一起，让内核管理器找到他们。所以线程结构体中包含了一个链表节点，而任务管理器处，也有一个全局节点名为thread_list。它通过这个全局节点，可以索引到系统中的所有线程结构体。
成员变量queue_node：
此变量也是一个链表节点，任务管理器用它组成不同状态的执行队列。
成员变量priority/remaining_quantum：
线程的优先级priority。这说明LK内核支持内核抢占，有实时调度的能力。
预定义的优先级如下：
/ * HIGHEST_PRIORITY
* DPC_PRIORITY
* HIGH_PRIORITY
* DEFAULT_PRIORITY
* LOW_PRIORITY
* IDLE_PRIORITY
* LOWEST_PRIORITY */
线程的执行时间片remainging_quantum。这个变量和具体的调度策略有关。一般的调度策略会包含轮训机制，会在同等优先级的任务之间进行轮流调度，这样会有一个轮询时间片，当前任务把自己的预定时间片用完后，就把执行机会让给同等优先级的其他任务。
成员变量 state/flags：
线程状态state。线程的实现符合传统的任务状态机。可能的状态包括：suspend、ready、running、blocked、sleeping、death。
线程标志flags。这是和实现有关的线程标志，用来标注一些特征或者特殊的状态（不在由state表示的状态机之内的状态）。现在支持的标志有：detached、free_stack、free_struct、real_time、idle、debug_stack_bounds_check。
curr_cpu/pinned_cpu：
在支持SMP多核配置的平台上，此两个变量才有意义。否则它们都是0。者两个变量表示任务当前执行的cpu号，和cpu亲和性。
blocking_wait_queue/wait_queue_ret：
线程的等待事件，以及等待结果。
stack/stack_size：
线程的执行栈和大小。这里注意一点，栈的大小不是固定的，而是可以根据需求来自己设定的。和Linux内核创建内核线程时候的4K或8K的内核栈，以及1M用户栈的固定大小不同。
entry/arg：
线程的入口函数和参数。
retcode/retcode_wait_queue：
线程函数的返回值retcode，调用者将可以获取到这个值。
如果有外部执行者在等待本线程返回，则retcode_wait_queue是所有这些等待者的休息室，它们在这里侯着。在线程要退出（exit或detach）的时候，会一一地通知到休息室里的等待者。换句话说，线程对象本身是可等待的对象（通过函数thread_join），这两个变量就是LK内核实现线程等待的方法。
tls：
和Linux类似，每个任务有一个线程相关的本地存储空间，可以存取若干个任务相关的本地数值。
name：
线程是可命名的。
线程创建
线程创建是一件相对简单的操作，在LK中创建一个线程，要传入的参数包括：线程名（可为NULL，则无名），线程函数和参数，优先级，以及栈大小。需要特别注意的是栈大小，它是一个可指定的值，而非固定。但可以通过函数封装，来使用默认的栈大小。LK其实定义了一个默认的栈大小的。
/* stack size */
#ifdef CUSTOM_DEFAULT_STACK_SIZE
#define DEFAULT_STACK_SIZE CUSTOM_DEFAULT_STACK_SIZE
#else
#define DEFAULT_STACK_SIZE ARCH_DEFAULT_STACK_SIZE
#endif
thread_t *thread_create(const char *name, thread_start_routine entry, void *arg, int priority, size_t stack_size)
默认的栈size既可以用户在编译的时候通过编译选项来自定义，也可以使用系统默认的和架构相关的一个默认值，这个值是一个经验值，不同的架构对应的值有所不同，x86是8k，arm的普通版本是4k，arm-m版本（m代表embeded）是1k。
LK定义了一种简单的获取栈空间使用大小的方法，它在为线程创建栈空间的时候，往栈中填充了特征字符0x99。由于栈是从栈顶（高地址）开始使用的，所以在判断栈的使用size的时候，只需从栈低（低地址）开始，逐字节地比对是否等于0x99，如果不是，就表示此处已经用到了，就得到了栈的已使用的大小。
这个方法其实并不正确，因为线程的栈的使用是随时存在伸缩的。子函数返回后，栈空间将向栈顶回缩，但这一点通过特征字符0x99是不能体现出来的。所以thread_stack_used得到的其实是线程执行到目前位置，最多使用到的栈size，而不是当前实际使用的size。
size_t thread_stack_used(thread_t *t)
执行中的线程可以给自己改名字。由于只提供了修改“自己”名字的接口，而其它线程可能修改或设置线程名字的地方，只有创建的时候，其时线程函数是肯定没有执行的，这使得修改名字这个操作天然地不可能存在竞争。所以thread_set_name(const char *name)的实现就非常简单，直接把输入参数name以字符串拷贝的方式设置到线程结构体中去。
实时线程
LK实现的线程是有实时性支持的。实时线程通过flag位THREAD_FLAG_REAL_TIME 来标识。函数thread_is_realtime就通过判断这个标志位来实现的：
static bool thread_is_realtime(thread_t *t)
{
return (t->flags & THREAD_FLAG_REAL_TIME) && t->priority > DEFAULT_PRIORITY;
}
这个函数除了判断实时标志位，还要求线程的优先级必须大于DEFAULT_PRIORITY。LK一共定义了32个优先级，并将这32个优先级大概地将其分成了4组。其中DEFAULT_PRIORITY恰好地位于最中间值为16。
0 --------------8 -------------- 16 --------------- 24 -------------- 32
Lowest Low Default High Highest
此外，IDLE_PRIORITY等于0，DPC_PRIORITY等于30。所以，如果要称为实时线程，需要其线程的优先级大于16才行。这一点需要创建线程时，创建者自己设置。因为在将线程设置为实时的时候，LK不会调整线程的优先级的。
status thread_set_real_time(thread_t *t)
这个函数只会修改标志位，不会判断线程的当前优先级而作调整。如果在线程创建的时候没有配置恰到的优先级，还可以由线程自己在运行时进行动态调整，这个函数是thread_set_priority：
void thread_set_priority(int priority)
这个函数只能为自己调整优先级，不能调整其他的线程，即便父线程也做不到。所以父进程如果确实向把子线程配置为实时任务，就务必在创建的时候，配置正确的参数。
抢占
抢占有三个点会发生。
一个是周期的调度点，由任务调度器主动操作。但LK当前并没有在周期操作中进行优先级判断，表明LK目前的实时支持是不够的。
一个是当前线程的善意，让出执行权并让调度器重调度，这时候调度器会让高优先级的任务抢占当前任务的。这里有两个函数：thread_yield和thread_preempt。
一个是当前线程的事件阻塞或满足，则将导致thread_block或thread_unblock被调用，也会导致重新调度。
调度
LK的实时线程实现方式属于FIFO（先到先出）的方式，先者通吃，直到主动放弃为止。这一点在实际使用的时候，需要注意，千万不要陷入到死循环中。后面我们会讲到，当前的lk调度策略起始是没有抢占的。唯有在重调度的时候，优先级才起到作用。
另外，如果一个实时线程在执行，它所在的cpu将被设置为realtime_cpu，这个状态被保存在全局结构体mp中。如果一个cpu属于realtime_cpu，在进行多核（mp）调度的时候会被剔除掉的。
如果处理器1是realtime_cpu，运行的线程为a；这时候我在处理器0上创建一个实时线程b并绑定到处理器1上，此时，如果配置它的优先级高于处理器1上的当前线程会怎么样呢？实时线程b是不能抢占实时线程a的，而要一直等到实时线程a主动放弃执行才有机会。并且b一旦执行，就将一直执行下去，直到主动放弃时线程a才有机会继续。
线程休眠
LK提供了一个典型的休眠函数，它的功能是让当前线程主动放弃执行权，线程状态被设置为SLEEPING；同时，创建一个新的延时计时器，设置其延时时间为休眠时间，让线程在指定的时间后重新被调度。
计时器的执行函数是一个固定的函数名为thread_sleep_handler(timer* timer, lk_time_t now, void* arg)。这个args就是之前进入休眠的线程结构体。
在这个handler函数中，进入休眠的线程将重新被设置为READY状态，并将其插入到调度队列的头部。
thread_t *t = (thread_t *)arg;
THREAD_LOCK(state); // 保护运行队列用
t->state = THREAD_READY;
insert_in_run_queue_head(t);
THREAD_UNLOCK(state);
这里面用到一个全局锁，这是一个大锁，保护全部的每个线程的状态操作，运行队列的操作，以及所有的任务管理的操作。这个锁的粒度比较大，所以一定存在优化的空间。
空闲线程
空闲线程的实现本质上是类似的，进行一些不紧急但不可少的工作，保持相关系统状态一定程度的持续性。比如系统平台的性能参数的收集，内核调度策略的调整，系统资源的管理策略调整等。
如果这些空闲工作都不需要的话，那么至少系统还有一件事情要做：等待中断到来，并且如果可以的话，让自己处于节能状态。对于x86系统而言，它调用hlt指令，让cpu进入节电状态，在中断到来是醒来；对于arm系统而言，它调用wfi指令，在低电状态下等待中断事件。
static void idle_thread_routine(void)
{
for (;;)
arch_idle();
}
boot strap线程
在系统启动的时候有一个特殊的boot strap线程，它是从cpu启动开始几代单传下来的执行流，典型的流程是：bios -> kernel loader -> kernel entry。LK也是类似的。它的kernel entry函数叫做lk_main，它是第一个被执行的c函数，此前还都是汇编的天下。
对于boot strap线程，它成立和生长在解放前，户口本都是民国或清朝时候办理的。线程管理的这套设施，确实解放后才有的设施。为了解决好管理这个问题，LK内核的办法是两点：
- 在boot strap线程完成了它的必要的系统初始化之工作后，创建了另外一个有新中国户口本的boot strap2线程（线程函数为
bootstrap2），继续其工作 - boot strap线程本身随后就调用become_idle_thread方法执行idle_thread_routine，让自己闲下来。等到中断来临的时候，就顺理成章地把执行权移交给内核的任务管理器了。因为boot strap线程没有正式的线程身份，它将从此隐没在线程调度的星辰大海之中了，它所代表的boot strap执行绪，再不会出现。
线程等待
前面我们在讲thread结构体时，提到了retcode和retcode_wait_queue这两个变量。它们是用来实现线程等待的。和Linux下面的实现类似，LK实现了一个名为thread_join的线程等待接口。
status_t thread_join(thread_t *t, int *retcode, lk_time_t timeout)
它的三个参数，分别是等待对象t，期望得到的线程返回值retcode，以及超时时间，这个时间可以被设置成无限等待（即：INFINITE_TIME）。
对于被等待，LK实现了和pthread类似的处理方式，即支持“可合（joinable）”与“非合（detached）”两种方式。
第一种是可合线程，就是普通的线程等待方式，当线程结束后，会得到相关的线程返回值。这里要千万注意一点的是，如果线程是可合（joinable）的，则一定要有一个线程调用thread_join()这个合函数去等待它，否则此线程退出后，其相关的线程资源如stack、线程结构体等，就不会被释放，从而变成一个僵尸线程，很是恐怖。
第二种是非合线程，这种线程被认为不必被任何其他线程所等待或依赖，应该是独立存在的，并且要自己在结束的时候释放资源。所以，可通过调用线程方法thread_detach设置其线程状态THREAD_FLAG_DETACHED。如此，当其他线程试图调用thread_join等待此线程时，会立即返回并得到一个错误码ERR_THREAD_DETACHED，即线程不可等待。
每个线程在退出时，要主动地调用函数thread_exit来结束线程。对于非合线程，其资源被此函数释放掉；而可合线程则不会的，必须有一个外部线程通过调用thread_join方可也。
调度管理
我们前面讲过了空闲线程、boot strap线程还有实时线程了。这里再讲讲调度的事情。调度要有一个触发时机，一个天然的触发时机是时钟中断或者所谓的滴答周期。这使得调度管理器的逻辑，可以被周期性地执行。LK定义了一个名为thread_timer_tick的基于时钟的调度函数。LK的内核调度既可以是基于滴答周期的，也可以是动态周期的，即根据当前的调度需求，决定下一次调度的事件并通过一个timer来规划它。下面是这个函数的定义：
enum handler_return thread_timer_tick(struct timer *t, lk_time_t now, void *arg)
这个调度管理函数实现得比较简单。它的策略如下：
- 如果当前线程是实时或者idle线程，它是没有时间片限制的，会继续执行下去；除非有外部事件或者中断发生，并触发了重调度，否则当前线程会一直保持执行状态。lk在这里缺少了一些看上去必要的抢占逻辑。
- 如果当前线程是普通线程，它的时间片减少1个单位。如果时间片降低到0，就返回
INT_RESCHEDULE，这会导致重调度操作。
这里面有一件颇值玩味的地方是，如果当前线程是idle线程，调度函数会持续地为他延长时间片，那么如果空闲线程永远执行的话，这个系统就不可能做任何“有效”的工作了。这看上去好像一个bug，但事实上，系统中只要还有一个线程存在，就不可能出现idle线程一直执行下去的情况。
我们便考虑系统中仅一个普通线程的情况。系统启动时，lk内核创建此普通线程，并主动调用一次重调度，则普通线程将获得执行权。此后，此普通线程如果被block，则执行权将被idle夺去。但block普通线程的时间一旦获得满足，会在时钟中断中处理unblock行为，并激发一次重调度。这样，执行权又将回到普通线程手中。
优先级
在一次重调度发生的时候，会选择一个新的线程执行。它这时候会根据优先级进行判断的。高者先得，低者晚得。实时线程的优先级是高的，且一旦其获得执行权，就没有时间片的概念，会一直执行下去，直到其主动放弃为止。
每个优先级有一个执行队列（run queue）。前者说过一共有32个优先级，这样就有32个执行队列。在实际执行的时候，未必每个执行队列都有有效的任务，这样就可以通过一个bitmap位图来识别之。
在寻找最高优先级的任务时，其过程就是挨个地检查执行队列的位图。如其是有效的运行队列，就检索其队列，看是否有一个运行在当前cpu上的线程（pinned_cpu）。如存在，则找到并返回；否则继续检索。如果最终都没有找到一个有效任务，则最后将返回空闲线程。
static thread_t *get_top_thread(int cpu)
{
thread_t *newthread;
uint32_t local_run_queue_bitmap = run_queue_bitmap;
while (local_run_queue_bitmap) {
/* find the first (remaining) queue with a thread in it */
uint next_queue = sizeof(run_queue_bitmap) * 8 - 1 - __builtin_clz(local_run_queue_bitmap);
list_for_every_entry(&run_queue[next_queue], newthread, thread_t, queue_node) {
#if WITH_SMP
if (newthread->pinned_cpu < 0 || newthread->pinned_cpu == cpu)
#endif
{
list_delete(&newthread->queue_node);
if (list_is_empty(&run_queue[next_queue]))
run_queue_bitmap &= ~(1<<next_queue);
return newthread;
}
}
local_run_queue_bitmap &= ~(1<<next_queue);
}
/* no threads to run, select the idle thread for this cpu */
return idle_thread(cpu);
}
多核MP
LK是支持多核的。其实现的主干内容包含两方面：
- 启动时候，主处理器（BSP）将其它处理器（AP）作为secondary cpu进行硬件初始化，并在线程管理器就绪后，于各secondary cpu上执行一个idle线程；
- 运行时候的多核调度支持。线程可以通过设置pinned_cpu来决定让自己执行在哪个cpu上。注意，LK并不支持负载均衡，他的调度策略是简单的。所以开发者在线程创建的时候，要自己考虑负载的问题。为了支持运行时多核调度，lk提供了一个
mp_reschedule内核函数。它通过IPI（inter processor interrupt）中断的方式，向目标处理器发送一个MP_IPI_RESCHEDULE消息。目标处理器收到这个中断后，就立刻在本地执行任务调度。
如此而已。
void mp_reschedule(mp_cpu_mask_t target, uint flags)
{
/* mask out cpus that are not active and the local cpu */
target &= mp.active_cpus;
/* mask out cpus that are currently running realtime code */
if ((flags & MP_RESCHEDULE_FLAG_REALTIME) == 0)
target &= ~mp.realtime_cpus;
target &= ~(1U << arch_curr_cpu_num());
arch_mp_send_ipi(target, MP_IPI_RESCHEDULE);
}
IPI是处理器之间通信的通用方式，也就是a处理器发送一个中断给b处理器，并传递一个简单的消息。
待续…
7,689 total views, 5 views today