ZEPHYR-内核服务-调度
Zephyr系列文章，翻译自 https://developer.nordicsemi.com/nRF_Connect_SDK/doc/latest/zephyr
人肉翻译，英文水平有限，仅供参考。
本文目录：Zephyr API reference->kernel services ->Scheduling
Scheduling 调度
内核的基于优先级的调度器允许应用程序的线程们共享CPU。
Concepts 概念
调度器会及时的在任意时刻决定哪个线程应该被执行；这个线程被称为当前线程（current thread）。
在不同的时间点，可以让调度去有机会去修改当前线程的身份（identity）。这些点称为重新调度点（reschedule point）。一些潜在的重新调度点是：
- 转换线程到就绪状态，例如使用 k_sem_give()或k_thread_start()。
- 将线程从运行状态转换到阻塞或等待状态，例如使用k_sem_take()或k_sleep()。
- 中断处理后里返回线程上下文。
- 当运行的线程调用k_yield()
当调度器改变当前线程的ID，或当当前线程的执行被ISR取代，内核首先会保存当前线程的CPU的寄存器值，这些寄存器将会在稍后线程恢复执行的时候重载。
Scheduling Algorithm 调度算法
内核的调度器选择最高优先级的就绪线程成为当前线程。当存在多个就绪线程优先级相同时，调度去选择一个等待事件最长的。
ISR的执行获取比线程的执行更高的优先级，所以当前线程的执行，可能会被ISR在任意时间取代，除非ISR被屏蔽了。这应用于合作线程与抢占线程。
内核可以使用就绪队列实现的几种选择之一来构建，当添加多个线程时，可在代码大小，恒定因子运行时的开销和性能伸缩性之间提供不同选择。
- 简单的链表就绪队列（CONFIG_SCHED_DUMB）
调度器就绪队列将被实现为一个简单的无序列表，具有非常快的单线程恒定时间慈宁宫能和非常小的代码空间。这个实现应该被选择在空间受限的代码中，任何时候都不应该在线程队列中看到多于某个数值（比如3）的可运行线程。在大多数平台上（否则不使用红黑树）这可以节省将近2K的代码空间。
- 红黑树就绪队列（CONFIG_SCHED_SCALABLE）
调度器的就绪队列将执行红黑树。这具有相当慢的固定时间插入和删除开销，在大多数平台上（否则某处不使用红黑树）需要额外的将近2K的代码空间。所产生的行为将迅速干净的到成千上万的线程中。
这将用于应用程序需要并发很多线程时（大于等于20个）。大多数的应用并不需要这种就绪队列的实现。
- 传统的多队列就绪队列（CONFIG_SCHED_MULTIQ）
当选中后，调度器就绪队列会被实现为经典的/教科书式的列表数组，每个优先级一个（最多32个优先级）。
这对应于1.12之前的zephyr版本中使用的调度器算法。
与“dumb”（愚蠢）的调度器相比，它只带来很小的代码开销，并且大多数情况下都以很低的常熟系数运行在O（1）时间运行。但是它需要相当大的RAM预算来存储这些表头，并且有限的功能让它不兼容更多的特性，例如更精致的线程排布的截止调度，并且需要遍历线程列表的SMP也是类似的。
小数额可运行线程的典型应用可能想要DUMB调度器。
IPC原语（IPC primitives）（IPC=Inter processor Communication）中用于等待线程挂起以便稍后唤醒的wait_q 抽象，与调度器共享同样的后端数据选择，并且可以使用相同的选项。
- 可扩展的wait_q 实现（CONFIG_WAITQ_SCALABLE）
当选择之后，wait_q将使用平衡树实现。如果你希望有很多线程在等待各个原语，就选它。如果红黑树没有在应用程序中的其他地方使用，则CONFIG_WAITQ_DUMB（可能与CONFIG_WAITQ_SCALABLE共享）的配置有一个将近2kb的代码大小提升，并且挂起/未挂起操作在“小”队列上将会稍微慢一点（尽管这不是通常的性能路径）。
- 简单链表wait_q（CONFIG_WAITQ_DUMB）
当选择之后，wait_q将被使用双向链表实现。如果你希望在任何单个IPC原语上仅阻塞几个线程，就选择它。
Cooperative Time Slicing 合作时间切片
当一个合作线程成为当前线程，它将保持当前线程直到它执行了一个让他进入非就绪状态的操作。所以，如果一个合作线程执行了很长时间的计算，它会引起调用其他线程无法接受的延时，包括那些更高优先级或同样优先级的线程。
为了克服这个问题，合作线程可以不时的自动放弃CPU让其他线程执行。一个线程可以放弃CPU有两种方式：
- 调用k_yield() 把线程放到调度器的就绪线程列表的后面，然后启动调度器。所有优先级高于或等于这个停止线程的就绪线程都会在这个停止线程再次调度之前被执行。如果这些线程不存在，调度器会立刻重新调度停止线程并不做上下文切换。
- 调用k_sleep()让线程为一个特殊的时间段进入非就绪态。所有优先级的就绪态线程都允许执行。然后，并没有保证优先级低于休眠线程的那些线程在休眠线程再次就绪之前被调用。
Preemptive Time Slicing 抢占线程
当一个抢占线程成为当前线程，它保持当前线程直到更高优先级的线程就绪，或者直到线程执行一个动作让它非就绪。所以，一个抢占线程执行很长时间的计算，它就引起调用其他线程无法接受的延时，包括那些优先级相同的线程。
为了克服这个问题，一个抢占线程可以执行合作时间片（前文述所），或者调度器的时间片能力可以用于允许其他同优先级的线程执行。
调度器把时间分为一系列的时间片，时间片使用系统时钟滴答测量。时间片的大小是可配置的，这个大小可以在应用程序运行时修改。
每个时间片结束时，调度器会检查当前的线程是否可以抢占，如果可以就代表线程隐式的调用k_yield()。这给予了其他相同优先级的线程机会在当前线程被再次调度之前执行。如果没有相同优先级的就绪线程，当前线程将保持。
内核的时间片算法不能保证很多相同优先级的线程获得相等的CPU时间，因为它没有测量一个线程真正执行的时间。例如，一个线程刚刚在时间片结束的时候成为当前线程，然后又需要立刻让出CPU。然而，算法保证了一个线程在不需要让出时永远不会执行长于1个单独的时间片。
Scheduler Locking 调度锁
一个抢占线程并不希望在执行关键操作时被抢占，可以调用k_sched_lock()来通知调度器暂时把它当作是合作线程。这可以防止来自其它线程在关键操作被执行时的打扰。
一旦关键操作执行完毕，抢占线程必须立刻调用k_sched_unlock()来恢复正常的、可抢占的状态。
如果一个线程调用k_sched_lock()，然后又执行了一个操作成为非就绪状态，调度器将把上锁的线程切换出来，并让其他线程运行。当上锁的线程又成为当前线程，它的非抢占状态将会保持。
可抢占线程为了防止被抢占，相比更改它的优先级为负数，锁定调度器是一种更高效的方式。
Meta-IRQ Priorities Meta-IRQ优先级
当使能之后（CONFIG_NUM_METAIRQ_PRIORITIES），在合作式优先级空间的最高端（数字最小），有一个特殊的合作优先级的子类：meta-IRQ线程。
它们是根据正常优先级进行调度的，但也具有在低优先级抢占其他线程（其他meta-irq线程）的特殊能力，即使这些线程是合作线程或已经使用调度锁的。
当被低优先级线程调用时，或类似ARM的“挂起IRQ” 从真正的中断上下文里完成时，这个行为让非阻塞模式meta-IRQ线程（通过任何方式，例如创建它，调用k_sem_give()，等等）的动作变成等价的同步系统调用。目的是使用这个功能在驱动程序子系统中实现中断“下文”（bottom half）”处理和“微线程（tasklet）”功能。这个线程，一旦被唤醒，将会保证在当前CPU返回应用代码之前运行。
与其他的操作系统中的类似功能不同，meta-IRQ线程是真线程，并在它们自己的栈（必须正常分配）里运行，而不是在每个CPU的中断栈里。在支持的架构中启用IRQ栈的设计工作正在进行中。
注意因为这违背了zephyr API对合作线程的承诺（通常的，系统不会调度其他线程直到当前线程故意阻塞），它将仅在应用程序中非常小心的被使用。这些线程不是简单的高优先级线程，也不该当成高优先级线程来使用。
Thread Sleeping 线程休眠
线程可以调用k_sleep()将其处理延时指定的时间段。在这期间线程休眠，CPU被让出允许其他就绪此线程执行。一旦这个指定的延时过去，这个线程就绪并可以在此进行调度。
休眠修成可以被提前由其他线程使用k_wakeup()唤醒。这项技术可以用来允许辅助线程发信号给休眠线程告知其发生了一些事情，但不需要线程定义内核同步对象（例如信号量）。可以唤醒未休眠的线程，但没有效果。
Busy Waiting 繁忙等待
线程可以调用k_busy_wait()来执行繁忙等待，这将会延时指定的时间段，并且不需要将CPU让给其它的就绪线程。
当需要的延时比从当前线程切换到另一个线程再切换回来的正常调度上下文还短时，繁忙等待典型的用于替代线程休眠。
Suggested Uses 建议用法
合作线程用于设备驱动和其他性能关键的工作。
合作线程可以实现互斥，而无需内核对象（如互斥信号量）。
抢占线程给高时间敏感处理优先权，而不是给低时间敏感处理。
本节完。
