yangjava

Linux调度系统

2021/01/13 Linux

Linux调度系统

调度可以说是操作系统的灵魂，为了让CPU资源利用最大化，Linux设计了一套非常精细的调度系统，对大多数场景都进行了很多优化，系统扩展性强，我们可以根据业务模型和业务场景的特点，有针对性的去进行性能优化，在保证客户网络带宽前提下，隔离客户互相之间的干扰影响，提高CPU利用率，降低单位运算成本，提高市场竞争力。

CPU

CPU作为计算资源，一直是云计算厂商比拼的核心竞争力，我们的目标是合理安排好计算任务，充分提高CPU的利用率，预留更多空间容错，增强系统稳定性，让任务更快执行，降低无效功耗，节约成本，从而提高市场竞争力。

  1. 首先，我们有一个自动计数器。这个自动计数器会随着时钟主频不断地自增，来作为我们的 PC 寄存器；

  2. 在这个自动计数器的后面，我们连上一个译码器。译码器还要同时连着我们通过大量的 D 触发器组成的内存。

  3. 自动计数器会随着时钟主频不断自增，从译码器当中，找到对应的计数器所表示的内存地址，然后读取出里面的 CPU 指令。

  4. 读取出来的 CPU 指令会通过CPU 时钟的控制，写入到一个由 D 触发器组成的寄存器，也就是指令寄存器当中。

  5. 在指令寄存器后面，我们可以再跟一个译码器。这个译码器的作用不再是用于寻址，而是把拿到的指令解析成opcode 和对应的操作数。

  6. 当我们拿到对应的 opcode 和操作数，对应的输出线路就要连接 ALU，开始进行各种算术和逻辑运算。对应的计算结果，则会再写回到 D 触发器组成的寄存器或者内存当中。

这里整个过程就大概是CPU的一条指令的执行过程。为了加快CPU指令的执行速度，CPU在发展过程中做了很多优化，例如流水线，分支预测，超标量，Hyper-threading，SIMD，多级cache，NUMA架构等, 这里主要关注Linux的调度系统。

CPU上下文

Linux 是一个多任务操作系统，它支持远大于 CPU 数量的任务同时运行。当然，这些任务实际上并不是真的在同时运行，而是因为系统在很短的时间内，将 CPU 轮流分配给它们，造成多任务同时运行的错觉。

而在每个任务运行前，CPU 都需要知道任务从哪里加载、又从哪里开始运行，也就是说，需要系统事先帮它设置好 CPU 寄存器和程序计数器(Program Counter，PC)。

CPU 寄存器，是 CPU 内置的容量小、但速度极快的内存。而程序计数器，则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。它们都是 CPU 在运行任何任务前，必须的依赖环境，因此也被叫做 CPU 上下文（执行环境）

而这些保存下来的上下文，会存储在系统内核中（堆栈），并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

在Linux中，内核空间和用户空间是两种工作模式，操作系统运行在内核空间，而用户态应用程序运行在用户空间，它们代表不同的级别，而对系统资源具有不同的访问权限。

这样代码（指令）执行存在不同的CPU上下文，而进行调度的时候，要进行相应的CPU上下文切换，Linux系统存在不同堆栈来保存CPU上下文，系统中每个进程都会拥有属于自己的内核栈，而系统中每个CPU都将为中断处理准备了两个独立的中断栈，分别是hardirq栈和softirq栈：

中断上下文：中断代码运行于内核空间，中断上下文即运行中断代码所需要的CPU上下文环境，需要硬件传递过来的这些参数，内核需要保存的一些其他环境（主要是当前被打断执行的进程或其他中断环境），这些一般都保存在中断栈中（x86是独立的，其他可能和内核栈共享，这和具体处理架构密切相关），在中断结束后，进程仍然可以从原来的状态恢复运行。

进程上下文：进程是由内核来管理和调度的，进程的切换发生在内核态，进程的上下文不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。

系统调用上下文：进程可以在内核空间和用户空间运行，分别称为进程的用户态和进程的内核态, 从用户态到内核态的转变需要通过系统调用来完成，需要进行CPU上下文切换，在执行系统调用时候，需要保存用户态的CPU上下文（用户态堆栈）到内核堆栈，然后加载内核态的CPU上下文。

CPU处理器总处于以下状态中的一种： １、内核态，运行于进程上下文，内核代表进程运行于内核空间； ２、内核态，运行于中断上下文，内核代表硬件运行于内核空间； ３、用户态，运行于用户空间。

中断

中断是由硬件设备产生的，而它们从物理上说就是电信号，之后，它们通过中断控制器发送给CPU，接着CPU判断收到的中断来自于哪个硬件设备（这定义在内核中），最后，由CPU发送给内核，内核来处理中断。

X86计算机的 CPU 为中断只提供了两条外接引脚：NMI 和 INTR。其中 NMI 是不可屏蔽中断，它通常用于电源掉电和物理存储器奇偶校验；INTR是可屏蔽中断，可以通过设置中断屏蔽位来进行中断屏蔽，它主要用于接受外部硬件的中断信号，这些信号由中断控制器传递给 CPU。当前x86 SMP架构主流都是采用多级I/O APIC（高级可编程中断控制器）中断系统。

Local APIC：主要负责传递中断信号到指定的处理器；

I/O APIC：主要是收集来自 I/O 装置的 Interrupt 信号且在当那些装置需要中断时发送信号到本地 APIC；

中断分类：

中断可分为同步（synchronous）中断和异步（asynchronous）中断：

同步中断是当指令执行时由 CPU 控制单元主动产生，之所以称为同步，是因为只有在一条指令执行完毕后 CPU 才会发出中断，而不是发生在代码指令执行期间，比如系统调用，根据 Intel 官方资料，同步中断称为异常（exception），异常可分为故障（fault）、陷阱（trap）、终止（abort）三类。

异步中断是指由其他硬件设备依照 CPU 时钟信号随机产生，即意味着中断能够在指令之间发生，例如键盘中断，异步中断被称为中断（interrupt），中断可分为可屏蔽中断（Maskable interrupt）和非屏蔽中断（Nomaskable interrupt）。

非屏蔽中断(Non-maskable interrupts,即NMI）：就像这种中断类型的字面意思一样，这种中断是不可能被CPU忽略或取消的。NMI是在单独的中断线路上进行发送的，它通常被用于关键性硬件发生的错误，如内存错误，风扇故障，温度传感器故障等。

可屏蔽中断（Maskable interrupts）：这些中断是可以被CPU忽略或延迟处理的。当缓存控制器的外部针脚被触发的时候就会产生这种类型的中断，而中断屏蔽寄存器就会将这样的中断屏蔽掉。我们可以将一个比特位设置为0，来禁用在此针脚触发的中断。

相同点：

1.最后都是由CPU发送给内核，由内核去处理；

2.处理程序的流程设计上是相似的。

不同点：

1.产生源不相同，陷阱、异常是由CPU产生的，而中断是由硬件设备产生的；

2.内核需要根据是异常，陷阱，还是中断调用不同的处理程序；

3.中断不是时钟同步的，这意味着中断可能随时到来；陷阱、异常是CPU产生的，所以，它是时钟同步的；

4.当处理中断时，处于中断上下文中；处理陷阱、异常时，处于进程上下文中。

中断亲和：

在 SMP 体系结构中，我们可以通过系统调用和一组相关的宏来设置 CPU 亲和力（CPU affinity），将一个或多个进程绑定到一个或多个处理器上运行。中断在这方面也毫不示弱，也具有相同的特性。中断亲和力是指将一个或多个中断源绑定到特定的 CPU 上运行；

在 /proc/irq 目录中，对于已经注册中断处理程序的硬件设备，都会在该目录下存在一个以该中断号命名的目录 IRQ# ，IRQ# 目录下有一个 smp_affinity 文件（SMP 体系结构才有该文件），它是一个 CPU 的位掩码，可以用来设置该中断的亲和力， 默认值为 0xffffffff，表明把中断发送到所有的 CPU 上去处理。如果中断控制器不支持 IRQ affinity，不能改变此默认值，同时也不能关闭所有的 CPU 位掩码，即不能设置成 0x0；

中断亲和好处是，在大量硬件中断场景，对于文件服务器、高流量 Web 服务器这样的应用来说，把不同的网卡 IRQ 均衡绑定到不同的 CPU 上将会减轻某个 CPU 的负担，提高多个 CPU 整体处理中断的能力；对于数据库服务器这样的应用来说，把磁盘控制器绑到一个 CPU、把网卡绑定到另一个 CPU 将会提高数据库的响应时间，优化性能。合理的根据自己的生产环境和应用的特点来平衡 IRQ 中断有助于提高系统的整体吞吐能力和性能；

Linux系统常见中断分类

时钟中断：

时钟芯片产生，主要工作是处理和时间有关的所有信息，决定是否执行调度程序以及处理下半部分。和时间有关的所有信息包括系统时间、进程的时间片、延时、使用CPU的时间、各种定时器，进程更新后的时间片为进程调度提供依据，然后在时钟中断返回时决定是否要执行调度程序。下半部分处理程序是Linux提供的一种机制，它使一部分工作推迟执行。时钟中断要绝对保证维持系统时间的准确性，“时钟中断”是整个操作系统的脉搏。

NMI中断：

外部硬件通过CPU的 NMI Pin 去触发（硬件触发），或者软件向CPU系统总线上投递一个NMI类型中断（软件触发），NMI中断的主要用途有两个：

用来告知操作系统有硬件错误（Hardware Failure），如内存错误，风扇故障，温度传感器故障等；

用来做看门狗定时器，检测CPU死锁等；

硬件IO中断：

大多数硬件外设IO中断，比如网卡，键盘，硬盘，鼠标，USB，串口等；

虚拟中断：

KVM里面一些中断退出和中断注入等，软件模拟中断；

查看方式：cat /proc/interrupts

由于中断会打断内核中进程的正常调度运行，所以要求中断服务程序尽可能的短小精悍；但是在实际系统中，当中断到来时，要完成工作往往需要进行大量的耗时处理。因此期望让中断处理程序运行得快，并想让它完成的工作量多，这两个目标相互制约，诞生顶/底半部机制。

中断上半部分：

中断处理程序是顶半部——接受中断，它就立即开始执行，但只有做严格时限的工作。能够被允许稍后完成的工作会推迟到底半部去，此后，在合适的时机，底半部会被开终端执行。顶半部简单快速，执行时禁止部分或者全部中断。

中断下半部分：

底半部稍后执行，而且执行期间可以响应所有的中断。这种设计可以使系统处于中断屏蔽状态的时间尽可能的短，以此来提高系统的响应能力。顶半部只有中断处理程序机制，而底半部的实现有软中断，tasklet和工作队列等实现方式；

软中断

软中断作为下半部机制的代表，是随着SMP（share memory processor）的出现应运而生的，它也是tasklet实现的基础（tasklet实际上只是在软中断的基础上添加了一定的机制）。软中断一般是“可延迟函数”的总称，有时候也包括了tasklet（请读者在遇到的时候根据上下文推断是否包含tasklet）。它的出现就是因为要满足上面所提出的上半部和下半部的区别，使得对时间不敏感的任务延后执行，而且可以在多个CPU上并行执行，使得总的系统效率可以更高。它的特性包括：产生后并不是马上可以执行，必须要等待内核的调度才能执行。软中断不能被自己打断(即单个cpu上软中断不能嵌套执行)，只能被硬件中断打断（上半部）， 可以并发运行在多个CPU上（即使同一类型的也可以）。所以软中断必须设计为可重入的函数（允许多个CPU同时操作），因此也需要使用自旋锁来保护其数据结构。

软中断的调度时机:

do_irq完成I/O中断时调用irq_exit。

系统使用I/O APIC，在处理完本地时钟中断时。

local_bh_enable，即开启本地软中断时。

SMP系统中，cpu处理完被CALL_FUNCTION_VECTOR处理器间中断所触发的函数时。

ksoftirqd/n线程被唤醒时。

软中断内核线程

在 Linux 中，中断具有最高的优先级。不论在任何时刻，只要产生中断事件，内核将立即执行相应的中断处理程序，等到所有挂起的中断和软中断处理完毕后才能执行正常的任务，因此有可能造成实时任务得不到及时的处理。中断线程化之后，中断将作为内核线程运行而且被赋予不同的实时优先级，实时任务可以有比中断线程更高的优先级。这样，具有最高优先级的实时任务就能得到优先处理，即使在严重负载下仍有实时性保证。但是，并不是所有的中断都可以被线程化，比如时钟中断，主要用来维护系统时间以及定时器等，其中定时器是操作系统的脉搏，一旦被线程化，就有可能被挂起，后果将不堪设想，所以不应当被线程化。

软中断优先在 irq_exit() 中执行，如果超过时间等条件转为 softirqd 线程中执行。满足以下任一条件软中断在 softirqd 线程中执行：

在 irq_exit()->__do_softirq() 中运行，时间超过 2ms。

在 irq_exit()->__do_softirq() 中运行，轮询软中断超过 10 次。

在 irq_exit()->__do_softirq() 中运行，本线程需要被调度。

注：调用 raise_softirq() 唤醒软中断时，不在中断环境中。

TASKLET

由于软中断必须使用可重入函数，这就导致设计上的复杂度变高，作为设备驱动程序的开发者来说，增加了负担。而如果某种应用并不需要在多个CPU上并行执行，那么软中断其实是没有必要的。因此诞生了弥补以上两个要求的tasklet。它具有以下特性：

a）一种特定类型的tasklet只能运行在一个CPU上，不能并行，只能串行执行。

b）多个不同类型的tasklet可以并行在多个CPU上。

c）软中断是静态分配的，在内核编译好之后，就不能改变。但tasklet就灵活许多，可以在运行时改变（比如添加模块时）。

tasklet是在两种软中断类型的基础上实现的，因此如果不需要软中断的并行特性，tasklet就是最好的选择。也就是说tasklet是软中断的一种特殊用法，即延迟情况下的串行执行。

tasklet有两种，tasklet 和 hi-tasklet：

前者对应softirq_vec［TASKLET_SOFTIRQ］；

后者对应softirq_vec[HI_SOFTIRQ]。只是后者排在softirq_vec[]的第一个，所以更早被执行;

工作队列

工作队列(work queue)是Linux kernel中将工作推后执行的一种机制。软中断运行在中断上下文中，因此不能阻塞和睡眠，而tasklet使用软中断实现，当然也不能阻塞和睡眠，工作队列可以把工作推后，交由一个内核线程去执行—这个下半部分总是会在进程上下文执行，因此工作队列的优势就在于它允许重新调度甚至睡眠。

workqueue 中几个角色关系：

work ：工作/任务。

workqueue ：工作的集合。workqueue 和 work 是一对多的关系。

worker ：工人。在代码中 worker 对应一个work_thread() 内核线程。

worker_pool：工人的集合。worker_pool 和 worker 是一对多的关系。

pwq(pool_workqueue)：中间人 / 中介，负责建立起 workqueue 和 worker_pool 之间的关系。workqueue 和 pwq 是一对多的关系，pwq 和 worker_pool 是一对一的关系。

通常，在工作队列和软中断/tasklet中作出选择，可使用以下规则：

如果推后执行的任务需要睡眠，那么只能选择工作队列。

如果推后执行的任务需要延时指定的时间再触发，那么使用工作队列，因为其可以利用timer延时(内核定时器实现)。

如果推后执行的任务需要在一个tick之内处理，则使用软中断或tasklet，因为其可以抢占普通进程和内核线程，同时不可睡眠。

如果推后执行的任务对延迟的时间没有任何要求，则使用工作队列，此时通常为无关紧要的任务。

实际上，工作队列的本质就是将工作交给内核线程处理，因此其可以用内核线程替换。但是内核线程的创建和销毁对编程者的要求较高，而工作队列实现了内核线程的封装，不易出错，推荐使用工作队列。

中断上下文

中断代码运行于内核空间，中断上下文即运行中断代码所需要CPU上下文环境，需要硬件传递过来的这些参数，内核需要保存的一些其他环境（主要是当前被打断执行的进程或其他中断环境），这些一般都保存在中断栈中（x86是独立的，其他可能和内核栈共享，这和具体处理架构密切相关），在中断结束后，进程仍然可以从原来的状态恢复运行。

总结和注意的点：

1.Linux kernel的设计者制定了规则：

中断上下文不是调度实体，task才是【进程（主线程）或者线程】;

优先级顺序：硬中断上下文 > 软中断上下文 > 进程上下文 ;

中断上下文（hardirq和softirq context）并不参与调度（暂不考虑中断线程化），它们是异步事件的处理机制，目标就是尽快完成处理，返回现场。因此，所有中断上下文的优先级都是高于进程上下文的。也就是说，对于用户进程（无论内核态还是用户态）或者内核线程，除非disable了CPU的本地中断，否则一旦中断发生，它们是没有任何能力阻挡中断上下文抢占当前进程上下文的执行的。

2.Linux 将中断处理过程分成了两个阶段，也就是上半部和下半部：

上半部用来快速处理中断，它在中断禁止模式下运行，主要处理跟硬件紧密相关的或时间敏感的工作，需要快速执行；

下半部用来延迟处理上半部未完成的工作，通常以软中断方式运行，可以延迟执行。

  1. 硬中断和软中断（只要是中断上下文）执行的时候都不允许内核抢占（本文后续章节会讲内核抢占）。因为在中断上下文中,唯一能打断当前中断handler的只有更高优先级的中断，它不会被进程打断(这点对于softirq,tasklet也一样,因此这些bottom half也不能睡眠)；如果在中断上下文中睡眠，则没有办法唤醒它，因为所有的wake_up_xxx都是针对某个进程而言的，而在中断上下文中，没有进程的概念，没有相应task_struct(这点对于softirq和tasklet一样)，因此真的睡眠了，比如调用了会导致阻塞的例程，内核几乎会挂。

4.硬中断可以被另一个优先级比自己高的硬中断“中断”，不能被同级（同一种硬中断）或低级的硬中断“中断”，更不能被软中断“中断”。软中断可以被硬中断“中断”，但是不会被另一个软中断“中断”。在一个CPU上，软中断总是串行执行。所以在单处理器上，对软中断的数据结构进行访问不需要加任何同步原语。

5.关中断不会丢失中断，但是对于期间到来的多个相同的中断会合并成一个，即只处理一次；时钟中断中需要更新jieffis计数值，如果多个中断合成一个，为了减少影响jieffis值准确性，需要其他硬件时钟来矫正。

抢占

早期的Linux核心是不可抢占的。它的调度方法是：一个进程可以通过schedule()函数自愿地启动一次调度。非自愿的强制性调度只能发生在每次从系统调用返回的前夕，以及每次从中断或异常处理返回到用户空间的前夕。但是，如果在系统空间发生中断或异常是不会引起调度的。这种方式使内核实现得以简化。但常存在下面两个问题：

  1. 如果这样的中断发生在内核中，本次中断返回是不会引起调度的，而要到最初使CPU从用户空间进入内核空间的那次系统调用或中断(异常)返回时才会发生调度。

  2. 另外一个问题是优先级反转。在Linux中，在核心态运行的任何操作都要优先于用户态进程，这就有可能导致优先级反转问题的出现。例如，一个低优先级的用户进程由于执行软/硬中断等原因而导致一个高优先级的任务得不到及时响应。

当前的Linux内核加入了内核抢占(preempt)机制。内核抢占指用户程序在执行系统调用期间可以被抢占，该进程暂时挂起，使新唤醒的高优先级进程能够运行。这种抢占并非可以在内核中任意位置都能安全进行，比如在临界区中的代码就不能发生抢占。临界区是指同一时间内不可以有超过一个进程在其中执行的指令序列。在Linux内核中这些部分需要用自旋锁保护。

内核抢占要求内核中所有可能为一个以上进程共享的变量和数据结构就都要通过互斥机制加以保护，或者说都要放在临界区中。在抢占式内核中，认为如果内核不是在一个中断处理程序中，并且不在被 spinlock等互斥机制保护的临界代码中，就认为可以”安全”地进行进程切换。

Linux内核将临界代码都加了互斥机制进行保护，同时，还在运行时间过长的代码路径上插入调度检查点，打断过长的执行路径，这样，任务可快速切换进程状态，也为内核抢占做好了准备，抢占分为用户抢占和内核抢占，linux抢占发生的时机：

用户抢占在以下情况下产生：

从系统调用返回用户空间 从中断处理程序返回用户空间

内核抢占会发生在：

当从中断处理程序返回内核空间的时候，且当时内核具有可抢占性； 当内核代码再一次具有可抢占性的时候（如:spin_unlock时）； 如果内核中的任务显式的调用schedule()； 如果内核中的任务阻塞。

时钟

计算机最基本的时间单元是时钟周期，例如取指令、执行指令、存取内存等, CPU执行指令需求时钟来同步和推进。时间系统是计算机系统非常重要的组成部分，所有信息包括系统时间、进程的时间片、延时、使用CPU的时间、各种定时器，进程更新后的时间片为进程调度提供依据，也就是驱动进程的调度，任务调度与时钟的关系非常密切。

时钟芯片 时钟芯片主要是提供时间源， 一般在一个计算机系统中存在三个时间发生器，一个用于记录日期时间的，它就是利用电池进行供电的一个单独芯片——RTC，第二个是PIT(可编程间隔定时器），第三个是TSC时间戳计数器，而PIT就是产生IRQ0的定时器芯片。而进行校正的就是利用TSC计数器，它在每个clock-cycle就会自动加一，不需要CPU操作，所以每个时钟中断产生时都可以利用一个全局变量记录下TSC的值，在下次时钟中断时再用这个全局变量校正jieffis的值，这样就可以记录精准的时间（TSC计数器是纳秒级的）。

操作系统对可编程定时/计数器进行有关初始化，然后定时/计数器就对输入脉冲进行计数（分频），产生的三个输出脉冲Out0、Out1、Out2各有用途，很多书都介绍了这个问题，我们只看Out0上的输出脉冲，这个脉冲信号接到中断控制器8259A_1的0号管脚，触发一个周期性的中断，我们就把这个中断叫做时钟中断，时钟中断的周期，也就是脉冲信号的周期，我们叫做“滴答”或“时标”（tick）。时钟与 CPU 和系统总线相关的每一个操作都是由一个恒定速率的内部时钟脉冲来进行同步的。机器指令的基本时间单位是机器周期 (machine cycle) 或时钟周期 (clock cycle) 。

时钟中断 “时钟中断”是特别重要的一个中断，因为整个操作系统的活动都受到它的激励。系统利用时钟中断维持系统时间、促使环境的切换，以保证所有进程共享CPU；利用时钟中断进行记帐、监督系统工作以及确定未来的调度优先级等工作。可以说，“时钟中断”是整个操作系统的脉搏。

从本质上来说，时钟中断只是一个周期性的信号，完全是硬件行为，该信号触发CPU去执行一个中断服务程序，在Linux的0号中断是一个时钟中断。在固定的时间间隔都发生一次中断，也就是说，每秒发生该中断的频率都是固定的。该频率是常量HZ，该值一般是在100 ~ 1000之间。该中断的作用是为了定时更新系统日期和时间，使系统时间不断地得到跳转。另外该中断的中断处理函数除了更新系统时间外，还需要更新本地CPU统计数。比如更新任务的调度时间片，若递减到0，则被调度出去而放弃CPU使用权。

时钟框架 时钟芯片提供节拍（tick），Linux系统设计一套时钟软件系统，满足应用对时间的各种需求：比如时间片调度，系统时间，日期，定时器，睡眠等：

内核对相关的时间硬件设备进行了统一的封装，定义了主要有下面两个结构：

时钟源设备(closk source device)：抽象那些能够提供计时功能的系统硬件，比如 RTC(Real Time Clock)、TSC(Time Stamp Counter)，HPET，ACPI PM-Timer，PIT等。不同时钟源提供的精度不一样，现在pc大都支持高精度模式(high-resolution mode)，也支持低精度模式(low-resolution mode)。

时钟事件设备(clock event device)：系统中可以触发 one-shot（单次）或者周期性中断的设备都可以作为时钟事件设备。

定时Timer

这类timer每个cpu都有一个独立的，称为local timer。这类timer的中断一般都是PPI（Private Peripheral Interrupt）类型，即每个cpu都有独立一份中断。与PPI对应的是SPI（Shared Peripheral Interrupt，即多个cpu共享同一个中断。

这类timer一般是32bit宽度count，最重要的它会频繁的溢出并产生timer到期中断。

这类timer服务于tick timer(低精度)或者hrtimer(高精度)。

低精度模式，local timer工作在PERIODIC模式。即timer以tick时间(1/HZ)周期性的产生中断。在tick timer中处理任务调度tick、低精度timer、其他时间更新和统计profile。在这种模式下，所有利用时间的进行的运算，精度都是以tick(1/HZ)为单位的，精度较低。比如HZ=1000，那么tick=1ms。

高精度模式，local timer工作在ONESHOT模式。即系统可以支持hrtimer(high resolution)高精度timer，精度为local timer的计数clk达到ns级别。这种情况下把tick timer也转换成一种hrtimer。

时间戳Timer

这类timer一个系统多个cpu共享一个，称为global timer。

这类timer一般是32bit/64bit宽度count，一般不会溢出产生中断，系统实时的去读取count的值来计算当前的时间戳。

这类timer服务于clocksource/timekeeper。

timerwheel实现依赖基于系统tick周期性中断，高精度时钟定时器不在依赖系统的tick中断，而是基于事件触发，内核启动后会进行从低精度模式到高精度时钟模式的切换，hrtimer模拟的tick中断将驱动传统的低精度定时器系统（基于时间轮）和内核进程调度。

时间轮算法

Linux定时器时间轮分为5个级别的轮子(tv1 ~ tv5)，如图3所示。每个级别的轮子的刻度值(slot)不同，规律是次级轮子的slot等于上级轮子的slot之和。Linux定时器slot单位为1jiffy，tv1轮子分256个刻度，每个刻度大小为1jiffy。tv2轮子分64个刻度，每个刻度大小为256个jiffy，即tv1整个轮子所能表达的范围。相邻轮子也只有满足这个规律，才能达到“低刻度轮子转一圈，高刻度轮子走一格”的效果。tv3，tv4，tv5也都是分为64个刻度，因此容易算出，最高一级轮子tv5所能表达的slot范围达到了25664646464 = 2^32 jiffies。

基于时间轮 (Timing-Wheel) 方式实现的定时器， timer wheel只能支持ms级别的精度， 虽然大部分时间里，时间轮可以实现O(1)时间复杂度，但是当有进位发生时，不可预测的O(N)定时器级联迁移时间，这对于低分辨率定时器来说问题不大，可是它大大地影响了定时器的精度。低分辨率定时器几乎是为“超时”而设计的，并为此对它进行了大量的优化，对于这些以“超时”未目的而使用定时器，它们大多数期望在超时到来之前获得正确的结果，然后删除定时器，精确时间并不是它们主要的目的，例如网络通信、设备IO等等。

高精度定时器Hrtimer

hrtimer采用红黑树进行高精度定时器的管理， 通过将高精度时钟硬件的下次中断触发时间设置为红黑树中最早到期的 Timer 的时间，时钟到期后从红黑树中得到下一个 Timer 的到期时间，并设置硬件，如此循环反复。

在高精度时钟模式下，操作系统内核仍然需要周期性的tick中断，以便刷新内核的一些任务。前面可以知道， hrtimer是基于事件的，不会周期性出发tick中断，所以为了实现周期性的tick中断(dynamic tick)：系统创建了一个模拟 tick 时钟的特殊 hrtimer，将其超时时间设置为一个tick时长，在超时回来后，完成对应的工作，然后再次设置下一个tick的超时时间，以此达到周期性tick中断的需求。引入了dynamic tick，是为了能够在使用高精度时钟的同时节约能源,，这样在产生tickless 情况下，会跳过一些 tick。

Search

    微信好友

    博士的沙漏

    Table of Contents