【架构分析】Zircon Scheduler 分析原创

Scheduler 工作方式

物理 CPU 组成逻辑 CPU
逻辑 CPU 上运行scheduler (scheduler之间通过 IPI (Inter-Processor Interrupts)通信)
每个逻辑 CPU 有 32 个 run queue ， queue[31] 为最高优先级 queue ，每个 queue 的 head 为最高优先级 thread
每个逻辑 CPU 有 32bit 的 run_queue_bitmap 标记 run queue 是否有等待调度的 thread, 可以在 O(1) 时间内计算出最高优先级的 run queue#
// using the per cpu run queue bitmap, find the highest populated queue
static uint highest_run_queue(const struct percpu* c) TA_REQ(thread_lock) {
    return HIGHEST_PRIORITY - __builtin_clz(c->run_queue_bitmap) -
           (sizeof(c->run_queue_bitmap) * CHAR_BIT - NUM_PRIORITIES);
thread effective priority 决定thread会被加入哪个run queue : 
// compute the effective priority of a thread
static void compute_effec_priority(thread_t* t) {
    int ep = t->base_priority + t->priority_boost;
    if (t->inherited_priority > ep) {
        ep = t->inherited_priority;
    DEBUG_ASSERT(ep >= LOWEST_PRIORITY && ep <= HIGHEST_PRIORITY);
    t->effec_priority = ep;
Thread Effective Priority = inherited priority/base priority + boost
base priority ∈∈ [0, 31]
inherited priority inherited from its parent thread
Boost ∈∈ [-MAX_PRIORITY_ADJ, MAX_PRIORITY_ADJ],  取值由以下因素确定
  When a thread is unblocked, after waiting on a shared resource or sleeping, it is given a one point boost. 
  When a thread yields (volunteers to give up control), or volunteers to reschedule, its boost is decremented by one but is capped at 0 (won’t go negative). 
  When a thread is preempted and has used up its entire timeslice, its boost is decremented by one but is able to go negative. 
  If the thread is in control of a shared resource and it is blocking another thread of a higher priority then it is given a temporary boost up to that thread’s priority to allow it to finish quickly and allow the higher priority thread to resume 
CPU Assignment and Migration 
Threads are able to request which CPUs on which they wish to run using a 32 bit  CPU affinity mask
        Ex: (001)2 is CPU 1, (100)2  is CPU 3, and (101)2 is either CPU 1 or CPU 3. 
When selecting a CPU for a thread the scheduler will choose, in order:
The CPU doing the selection, if it is idle and in the affinity mask.
The CPU the thread last ran on, if it is idle and in the affinity mask.
Any idle CPU in the affinity mask.
The CPU the thread last ran on, if it is active and in the affinity mask.
The CPU doing the selection, if it is the only one in the affinity mask or all cpus in the mask are not active.
Any active CPU in the affinity mask.
				fifo是一种进程间通信机制，是一种先进先出的queue。其设计目的是作为共享内存传输的控制面，
其读写性能比socket或者channel都更加有效率，但是其在elements和buffers的大小上有严格的限制！
//TODO：限制的本质原因
系统调用banjo文件位置：zircon\system\public\zircon\syscalls.banjo
fifo的创建：zx_fifo_c...
			内核消息是一些不同类型的对象。这些对象可以直接通过syscall调用，并且这些对象是C++的类，由调度接口实现，位于kernel/object目录。许多是自包含的高阶对象，一些是包含低阶的lk原语。
			syscall
			用户空间代码与内核对象的交互通过syscall，大多数仅通过Handle。在用户空间，一个Handle是32位整型(zx_handle_t)。进...
前面已经介绍了 Zircon 内核启动的汇编代码部分，主要是一些 CPU 的初始化。
现在 prime CPU 已经来到了 C 世界的 lk_main() 函数
其他 CPU 也来到了 arm64_secondary_entry() 函数
lk_main
lk_main() 是打开 Zircon 内核世界的大门，由 prime cpu 敲开，一眼望去你就会发现 lk_main 一行行代码目的...
＃＃ 介绍
在Zircon中，设备驱动程序实现为ELF共享库（DSO）,加载到设备主机（devhost）进程中。设备管理器（devmgr）进程，包含设备协调器（Coordinator），用于跟踪驱动程序和设备，进行管理发现驱动程序，设备主机进程的创建和方向，以及维护设备文件系统（devfs），这是用户空间的服务和应用程序（受其命名空间约束）获得设备访问权限的机制。
thread - 可运行的 / 运算实体
线程对象是一种表示时间共享的CPU执行上下文的结构。线程对象存在于关联的特定进程对象中，为其它对象提供I/O和计算所必须的内存和句柄。
线程是通过调用[zx_thread_create()]创建的，但只有在调用了[zx_thread_start()]或[zx_process_start()]时才开始执行。这两个系统调用将要执行的初始例程...
				zircon 实现两种调度机制，一种就是fair 其实现在fair_scheduler.cpp中，一种是基于时间片的其实现在sched.cpp 中，调度器的入口都在sche_reschedule()这个函数中。
例如fair的实现如下：
void sched_reschedule() {
    FairScheduler::Reschedule();
fair的实现是一个cpp的类。
另一...
Zircon 是 Google 新操作系统 Fuchsia 的内核，基于 LK - Little Kernel 演变而来。而 Little Kernel 前面一直作为 Android 系统的 Bootloader 的核心而存在。Zircon 在此基础上增加了 MMU，System Call 等功能。
Zircon 目前支持 X86/X64 和 ARM 两种 CPU 平台，下面我将以 ARM6...
任何调度器首要的责任都是在所有请求的线程之间分配处理器的有限时间资源。在通用操作系统中，尽可能实现公平的分配，确保所有的线程都能够取得一定的进展。
Zircon的调度器由Little Kernel的调度器进化而来。所以是以一个最小化的调度器实现开始，并且随着工程的成长，可依据需求进行扩展。
本质上，机器中的每个逻辑处理器上运行着一个调度器。这些调度器独立运行，...