Mach 调度

Mach 在核心原语的基础上实现了很多重要的功能。几乎所有的功能都和系统资源：硬件设备、虚拟内存以及CPU本身的管理有关。CPU 的管理称之为调度（schedule），因为这种管理操作需要判定众多竞争CPU资源的程序中的哪一个程序在何时可以获得CPU资源。

调度原语

和所有现代的操作系统一样，内核调度的对象是线程，而不是进程。事实上，Mach 并不能识别UNIX 中所说的进程，而是采取了一种稍微不同的方式，使用了比进程更轻量级的概念：任务（task）。经典的UN*X采用了自上而下的方法：最基本的对象是进程，然后进一步划分一个或多个线程。而Mach 采用 自底向上的方式，最基本的单元是线程，一个或多个线程包含在一个任务中。

线程

线程（thread）定义了Mach中最小的执行单元。线程表示的是底层的机器寄存器状态以及各种调度统计数据。线程从设计上提供了所需要的大量信息，同时又尽可能地维持最小开销。
线程的数据结构非常巨大，因此大部分的线程创建时都是从一个通用的模板复制而来的，这个模板使用默认值填充这个数据结构，这个模板名为thread_template，内核引导过程中被调用的thread_bootstrap( )负责填充这个模板。thread_create_internal( )函数分配新的线程数据结构，然后将换这个模板的内容负责到新的线程数据结构中。Mach API thread_create( ) 就是通过thread_create_internal( )实现的。

任务

任务（task）是一种容器（container）对象，虚拟内存空间和其他资源都是通过这个容器对象管理的，这些资源包括设备和其他句柄。资源进一步被抽象为端口。因而资源的共享实际上相当于允许对对应端口的访问。

严格地说，Mach 的任务并不是其他操作系统中所谓的进程，因为Mach 作为一个微内核的操作系统，并没有提供“进程”的逻辑，而只是提供了最基本的实现。不过在BSD的模型中，这两个概念有1：1的简单映射，每一个BSD 进程（也就是OS X 进程）都在底层关联了一个Mach 任务对象。实现这种映射的方法是指定一个透明的指针bsd_info，Mach 对bsd_info 完全无知。Mach 将内核也用任务表示（全局范围内称为kernel_task），尽管这个任务没有对应的PID（从技术上说，可以想象PID 为0）。

就其本身而言，任务是没有生命的。任务存在的目的就是称为一个或多个线程的容器。任务中的线程都在threads成员中维护，这是一个包含thread_count个线程的队列。此外，大部分对任务的操作实际上就是遍历给定任务中的所有线程，并对这些线程进行对应的线程操作。

账本

账本（ledger）是Mach 任务的配额记账（charge quota）和设置限制所需要的机制。这种机制类似于POSIX 的系统调用getrlimit( )/setrlimit( )，但是提供了更为强大的资源节流（throttling）能力：资源（一般之CPU资源管理和内存资源）可以在账本间颛臾；超出限制可能会导致Mach 异常、执行回调函数、或阻塞线程直到账本被“充值（refill）”

任务和线程相关的API

Mach 提供了各式各样对任务和线程操作的API调用，可以用类似面向对象的方式操作这些任务和线程，而具体的实现则保持透明。

• 获得当前的任务和线程
  在任何时刻，内核都必须能够获得当前任务和当前线程的句柄。内核分别通过current_task( ) 和 current_thread( ) 函数完成这两个任务

任务相关的API

Mach 提供了完整的一套用于操作任务的APT。在用户态可以在<mach/task.h> 头文件中找到这些API。下表列出这些函数（用户态），其中除了mach_task_self( ) 之外的所有函数都是通过Mach消息实现的（MIG子系统编号为3400）

Mach 任务API（只有函数名）	用途
mach_task_self	获得任务的端口，带有发送权限的名称
task_create	以target_task为父任务创建一个任务child_task
task_terminate	终止已有的任务
task_threads	将target_task 任务中的所有线程枚举保存在act_list 中
task_info	根据task_flavor_t 指定的类型，查询task_name_t 的信息
task_suspend、task_resume	通过枚举任务中所有的线程并对线程直接调用thread_suspend/resume 来挂起/恢复target_task执行。任务采用挂起计数器
get/set_special_port	获取/设置给定任务的特殊端口
task_get/set/swap_exception_ports	查询/设置/交换任务的异常端口
task_policy_set/get	设置/获取一个任务的调度策略（即针对所有线程的操作）
task_sample	定时采用一个任务的IP（Intel平台）或PC（ARM 平台）。现已移除
task_get/set_state	获得/设置一个任务的状态

上表的API是暴露给用户态的。接下来的API是Mach 内核内部使用的任务API

Mach 任务API	用途
task_priority	将task_t 的优先级设置为priority，并将最高允许的优先值设置为max.这是通过遍历所有线程调用thread_task_priority实现的
taks_importance	用于renice( )的实现，实际上是对task_priority( ) 的包装：调用task_priority( )时提供的优先级为importance + BASEPRI_DEFAULT

线程相关的API

类似于任务相关的API，Mach 还提供了丰富的线程管理API。这些API大部分都和任务API的功能类似。实际上API通常的实现方法是遍历任务中的线程列表，然后对每一个线程执行对应的操作。这些调用（除了mach_thread_sekf( )之外）都是通过Mach消息实现的(MIG子系统编号为3600)。下表是Mach线程常用的API

Mach线程API	用途
mach_thread_self	获得线程内核端口的发送权限
thread_terminate	终止自己
thread/act_get/set_state	获得/设置线程上下文。act_函数不允许获得/设置当前线程的状态。其他情况则调用对应的thread_函数
thread_suspend/resume	挂起/恢复线程，会递增/递减挂起计数器
thread_abort	销毁另一个线程
thread_depress_abort	强迫降低线程的优先级
thread_get/set/special_port	获得或设置线程的某一个特殊端口。XNU中唯一支持的特殊端口是THREAD_KERNEL_PORT
thread_info	查询flavoe指定的thread消息
thread_get/set/swap_exception_ports	查询/设置/交换移除端口，异常端口是Mach 异常消息发送的目标
thread_policy_set/get	设置/获取线程调度策略
thread_assign	将thread分配给某个指定处理器集new_pset或默认处理器集
thread_get_assignment	返回当前线程绑定的处理器集。总是返回默认处理器集pset0的引用

内核私有的线程API

Mach 内核提供了一组线程控制的函数，这些函数只能在内核态中调用。

Mach 线程API	用途
assert_wait	将当前线程加入event 的等待队列。wait_hash( ) 函数可以将事件转换为等待队列
assert_wait_dealine	功能等同于assert_wauit( ) ，但是允许设置一个截止时间
thread_wakeup_prim	唤醒一个或多个正在等待event的线程
thread_block_reason	阻塞当前线程，让出CPU资源，还可以为这个线程设置一个continutatiom和对应的parameter
thread_bind	将这个线程的亲缘性设置为绑定至processor，或通过传入PROCESSOR_NULL取消相关亲缘性
thread_run	执行线程的转交（handoff）：当前线程让出CPU执行资源（参数同thread_block_partmeter），但是将控制权直接转交给new_thread。用于实现handoff，这个函数是对thread_invoke( )的包装，后者是调度器的内部函数
thread_go	解除一个线程的阻塞并分发（dispatch）这个线程。将线程从等待队列中时使用这个调用
thread_setrun	分发一个线程，将线程分发至绑定的出路器或在任何处理器（优先选择闲置处理器）

调度

由于Mach具有处理器集的抽象，所以从某个角度说，Mach 比Linux 和 Windows 更擅长管理多核处理器：Mach 可以将同一个CPU 的多个核心放在同一个pset管理，并且通过不同的pset管理不同的CPU。

概述

上下文切换（content switch）：上下文切换是暂停某个线程的执行，并且将其寄存器状态记录在某个预定义的内存位置中。寄存器状态是和及其相关的。当一个线程被抢占时，CPU 寄存器中会价值另一个线程保存的线程状态，从而恢复到那个线程的执行。
一个线程在CPU上可以执行任意长的时间。执行（execute）指的是这样的一个事实：CPU 寄存器中填满了线程的状态，因此CPU（通过EIP/RIP指令指针或PC程序计数器）执行该线程函数的代码。这个执行过程一直在延续，知道发生下面某种情况：

• 线程终止
• 线程自愿放弃
• 外部中断打断了线程的执行，外部中断要求CPU 保存线程状态并且立即执行中断处理代码

优先级

每一个线程都被分配了有点急，优先级直接影响线程被调度的频率。每一个操作系统都提供了一个这种优先级的范围：Windows 有32个优先级，Linux 有140个优先级，Mach 有128个优先级。
内核线程的最低优先级为80，比用户态线程的优先级要高。可以保证内核以及用户维护管理的线程能够抢占用户态的线程。

优先级偏移

给线程分配优先级只是一个开头，这些优先级在运行时常常需要调整。Mach 会针对每一个线程的CPU 利用率和整体系统负载动态调整每一个线程的优先级。

运行队列

线程是通过运行队列管理的。 运行队列是一个多层列表，即一个列表的数组，针对128个优先级中的每一个优先级都要一个队列。Mach 实际采用的方法是检查位图，这样就可以同时检查32个队列，这样时间复杂度为O(4)。

等待队列

当线程阻塞，就没有必要考虑调度这个线程，因为只有当线程等待的对象或I/O 操作完成或时间发生时才能继续执行。所以可以将线程放在等待队列中。当等待的条件满足之后，一个或多个等待的线程可以被解除阻塞并且再次分发执行。

CPU 亲缘性

在使用多核、SMP 或 超线程的现代架构中，还可以设置某个线程和一个或多个指定CPU 的亲缘性（affinity）。这种亲缘性对于线程和系统来说都是有好处的，因为当线程回到同一个CPU上执行时，线程的数据可能还留在CPU的缓存中，从而提升性能。
用Mach的说法，线程对CPU 的亲缘性的意思就是绑定。thread_bind( )的目的就是绑定线程，这个函数仅仅是更新thread_t的bound_processor字段。如果这个字段被设置为PROCESSOR_NULL之外的任何值，那么未来的调度策略就会将这个线程分发到对应处理器的运行队列。

MACH 调度器的独特特性

Mach 自己特有的重要特性：

• 控制权转交：允许一个线程主动放弃CPU，但不是将CPU放弃给任何其他线程，而是将CPU转交给自己选择的某个特定的线程。由于Mach 是一个基于消息传递的内核，线程之间通过消息传递通讯，所以这项特性在Mach 中特别有用。通过这个特性，消息的处理延迟可以达到最小，而不需要投机地等待消息处理线程（发送者或接收者）下一次得到调度。
• 使用续体：可以使线程不用管理自己的栈，线程可以丢弃自己的栈，系统恢复线程执行时不需要恢复线程的栈。续体是缓解上下文切换开销的简单有效的机制
• 异步软件陷阱（Asynchronous Software Trap，AST）：是软件对底层硬件陷阱机制的补充完善，通过使用AST，内核可以响应需要得到关注的带外（out-off-band）事件，例如调度事件
• 调度算法模块化：调度算法是模块化的，系统引导时可以动态设置调度器（使用sched引导参数）。不过实际中只用了一个调度器（即“传统”调度器）

抢占模式

系统中的线程可能被两种方式抢占：

• 显式抢占：即线程放弃CPU的控制权或进入阻塞的操作，显式抢占是事先可以预知的，所以显式抢占是同步的
• 隐式抢占：这种抢占是由中断引起的，由于中断不可预测的本身，所有隐式抢占是异步的

异步软件陷阱（AST）

AST是人工引发的非硬件触发的陷阱。AST是内核操作的关键部分，而且是调度时间的底层机制，也是BSD信号的实现基础。AST实现为线程控制块中一个包含各种标志位的字段，这些标志位可以通过thread_ast_set（ ）分别设置。

调度算法

Mach 的线程调度算法高度可扩展，而且运行更换用于线程调度的算法。通常情况下，只启用了一个调度器。但是Mach的架构运行定义额外的调度器，并且在编译时根据CONFIG_SCHED_的定义设置调度器。每一个调度器对象都维护一个sched_dispatch_table 数据结构，其中以函数指针的方式保存了各种操作。一个全局表sched_current_dispatch保存了当前活动的调度算法，并且允许运行时切换调度器。所有的调度器都必须实现相同的字段，通用的调度逻辑可以通过SCHED宏访问这些字段。

定时器中断

中断驱动的调度

对于要提供抢占式多任务的系统来说，必须有某种机制允许调度器能够首先得到CPU的控制权，从而抢占当前正在执行的线程，然后才能执行调度算法，并且通过调度算法决定当前的线程可以继续恢复执行还是要抢夺其 CPU 给更重要的线程使用。为了能够从当前运行的线程抢夺CPU，现在的操作系统（包括苹果操作系统）都利用了现有的硬件中断机制。由于中断的特点是强迫CPU在发生中断时“放下手中所有的任务”，并longjmp 跳转到中断处理程序（也称为中断服务例程（interrupt service routinr，ISR））执行，因此可以通过中断机制在发生中断时运行调度器。

XNU 中的定时器中断处理

XNU 定义了每个CPU都有的rtclock_timer_t 类型，这个数据结构的作用是跟踪基于定时器的时间。这个结构体指定了定时器的截止时间线，还包含一个call_entry 结构体的队列。队列中包含的是“调出”信息。

异常

Mach 异常模型

Mach 异常处理设施的设计者考虑到一下的因素：

• 带有一致语义的单一异常处理设施：Mach 只提供了一个异常处理机制用于处理所有类型的异常：包括用户定义的异常、平台无关的异常以及平台特定的异常。根据异常的类型对异常进程分组，具体的平台可以定义具体的子类型
• 清晰和简洁：异常处理和接口依赖于Mach 已有的具有良好定义的消息和端口架构，因此非常优雅（又不会影响效率）。这就允许调试器和外部处理程序的扩展：甚至在理论上还支持扩展基于网络的异常处理
  Mach的异常处理模型和其他的异常处理模型不同，其他模型的异常处理程序运行组出错的线程的上下文中，而Mach 的异常处理程序在不同的上下文中运行异常处理程序，出错的线程向预先指定好的异常端口发送消息，然后等待应答。发生异常时，首先尝试将异常抛给线程的异常端口，然后尝试抛给任务的异常端口，最后在抛给主机的异常端口（即主机注册的默认端口），如果没有一个端口返回KERN_SUCESS，那么整个任务被终止。