每天十五分钟，熟读一个技能点，水滴石穿，统统只为渴望更精良的你！
————零声学院
在多进程的操作系统中，进程调度是一个全局性、关键性的问题，它对系统的总体设计、
系统的的实现、功能设置以及各个方面的性能都有着决定性的影响。根据调度的结果所作的
进程切换的速率，也是衡量一个操作系统性能的主要指标。进程调度算法的设计，还对系统
的繁芜性有着极大的影响，常常会由于实现的繁芜程度而在功能与性能方面作出必要的权衡
和让步。
进程调度与韶光的关系非常密切，因此，本章首先谈论与韶光干系的主题，然后才谈论
进程的调度，末了先容了 Linux 中进程是如何进行切换的。
5.1 Linux 韶光系统打算机因此严格精确的韶光进行数值运算和和数据处理的，最基本的韶光单元是时钟周
期，例如取指令、实行指令、存取内存等，但是我们不谈论这些纯硬件的东西，这里要谈论
的是操作系统建立的韶光系统，这个韶光系统是全体操作系统活动的动力。
韶光系统是打算机系统非常主要的组成部分，特殊是对付 UNIX 类分时系统尤为主要。
韶光系统常日又被简称为时钟，它的紧张任务是坚持系统韶光并且防止某个进程独占 CPU 及
其他资源，也便是驱动进程的调度。本节将详细讲述时钟的来源、在 Linux 中的实现及其重
要浸染，使读者肃清对时钟的神秘感。
5.1.1 时钟硬件
大部分 PC 机中有两个时钟源，他们分别叫做 RTC 和 OS（操作系统）时钟。RTC（Real Time
Clock，实时时钟）也叫做 CMOS 时钟，它是 PC 主机板上的一块芯片（或者叫做时钟电路），
它靠电池供电，纵然系统断电，也可以坚持日期和韶光。由于它独立于操作系统，以是也被
称为硬件时钟，它为全体打算机供应一个计时标准，是最原始最底层的时钟数据。
Linux 只用 RTC 来得到韶光和日期，同时，通过浸染于/dev/rtc 设备文件，大概可进程
对 RTC 编程。内核通过 0x70 和 0x71 I/O 端口存取 RTC。通过实行/sbin/clock 系统程序（它
直接浸染于这两个 I/O 端口），系统管理员可以配置时钟。
OS 时钟产生于 PC 主板上的定时/计数芯片，由操作系统掌握这个芯片的事情，OS 时钟
的基本单位便是该芯片的计数周期。在开机时操作系统取得 RTC 中的韶光数据来初始化 OS
时钟，然后通过计数芯片的向下计数形成了 OS 时钟，以是 OS 时钟并不是实质意义上的时钟，
它更该当被称为一个计数器。OS 时钟只在开机时才有效，而且完备由操作系统掌握，以是也
被称为软时钟或系统时钟。下面我们重点描述 OS 时钟的产生。
OS 时钟所用的定时/计数芯片最范例的是 8253/8254 可编程定时/计数芯片，其硬件构造
及事情事理在这里不详细讲述，只大略地描述它是若何坚持 OS 时钟的。OS 时钟的物剃头生
示意图如图 5.1 所示。
可编程定时/计数器总体上由两部分组成：计数硬件和通信寄存器。通信寄存器包含有
掌握寄存器、状态寄存器、计数初始值寄存器（16 位）、计数输出寄存器等。通信寄存器在
计数硬件和操作系统之间建立联系，用于二者之间的通信，操作系统通过这些寄存器掌握计
数硬件的事情办法、读取计数硬件确当前状态和计数值等信息。在 Linux 内核初始化时，内
核写入掌握字和计数初值，这样计数硬件就会按照一定的计数办法对晶振产生的输入脉冲信
号（5MHz~100MHz 的频率）进行计数操作：计数器从计数初值开始，每收到一次脉冲旗子暗记，
计数器减 1，当计数器减至 0 时，就会输出高电平或低电平，然后，如果计数为循环办法（通
常为循环计数办法），则重新从计数初值进行计数，从而产生如图 5.1 所示的输出脉冲旗子暗记
（当然不一定是很规则的方波）。这个输出脉冲是 OS 时钟的硬件根本，之以是这么说，是因
为这个输出脉冲将接到中断掌握器上 ，产生中断旗子暗记，触发后面要讲的时钟中断，由时钟中
断做事程序坚持 OS 时钟的正常事情，所谓坚持，实在便是大略的加 1 及细微的改动操作。这
便是 OS 时钟产生的来源。
5.12 时钟运作机制
不同的操作系统，RTC 和 OS 时钟的关系是不同的。RTC 和 OS 时钟之间的关系常日也被
称作操作系统的时钟运作机制。
一样平常来说，RTC 是 OS 时钟的韶光基准，操作系统通过读取 RTC 来初始化 OS 时钟，此后
二者保持同步运行，共同坚持着系统韶光。保持同步运行是什么意思呢？便是指操作系统运
行过程中，每隔一个固定时间会刷新或校正 RTC 中的信息。
Linux 中的时钟运作机制如图 5.2 所示。OS 时钟和 RTC 之间要通过 BIOS 的连接，是因
为传统 PC 机的 BIOS 中固化有对 RTC 进行有关操作的函数，例如 INT 1AH 等中断做事程序，
常日操作系统也直策应用这些函数对 RTC 进行操作，例如从 RTC 中读出有关数据对 OS 时钟初
始化、对 RTC 进行更新等。实际上，不通过 BIOS 而直接对 RTC 的有关端口进行操作也是可以
的。Linux 中在内核初始化完成后就完备抛弃了 BIOS 中的程序。
我们可以看到，RTC 处于最底层，供应最原始的时钟数据。OS 时钟建立在 RTC 之上，初
始化完成后将完备由操作系统掌握，和 RTC 分开关系。操作系统通过 OS 时钟供应给运用程序
所有和韶光有关的做事。由于 OS 时钟完备是一个软件问题，其所能表达的韶光由操作系统的
设计者决定，将 OS 时钟定义为整型还是长整型或者大的超乎想像都是设计者的事。
5.1.3 Linux 韶光基准
以上我们理解了 RTC（实时时钟、硬件时钟）和 OS 时钟（系统时钟、软时钟）。下面我
们详细描述 OS 时钟。
我们知道，OS 时钟是由可编程定时/计数器产生的输出脉冲触发中断而产生的。输出脉
冲的周期叫做一个“时钟滴答”，有些书上也把它叫做“时标”。打算机中的韶光因此时钟
滴答为单位的，每一次时钟滴答，系统韶光就会加 1。操作系统根据当前时钟滴答的数目就
可以得到以秒或毫秒等为单位的其他韶光格式。
不同的操作系统采取不同的“韶光基准”。定义“韶光基准”的目的是为了简化打算，
这样打算机中的韶光只要表示为从这个韶光基准开始的时钟滴答数就可以了。“韶光基准”
是由操作系统的设计者规定的。例如 DOS 的韶光基准是 1980 年 1 月 1 日，UNIX 和 Minux 的
韶光基准是 1970 年 1 月 1 日上午 12 点，Linux 的韶光基准是 1970 年 1 月 1 日凌晨 0 点。
5.1.4 Linux 的韶光系统
通过上面的时钟运作机制，我们知道了 OS 时钟在 Linux 中的主要地位。OS 时钟记录的
韶光也便是常日所说的系统韶光。系统韶光因此“时钟滴答”为单位的，而时钟中断的频率
决定了一个时钟滴答的是非，例如每秒有 100 次时钟中断，那么一个时钟滴答的便是 10 毫秒
（记为 10ms），相应地，系统韶光就会每 10ms 增 1。不同的操作系统对时钟滴答的定义是不
同的，例如 DOS 的时钟滴答为 1/18.2s，Minix 的时钟滴答为 1/60s 等。
Linux 中用全局变量 jiffies 表示系统自启动以来的时钟滴答数目。jiffy 是“瞬间、
一下子”的意思，和“时钟滴答”表达的是同一个意思。jiffies 是 jiffy 的复数形式，在
/kernel/time.c 中定义如下：
unsigned long volatile jiffies
在 jiffies 基 础 上 ， Linux 提 供 了 如 下 适 合 人 们 习 惯 的 时 间 格 式 , 在
/include/linux/time.h 中定义如下：
struct timespec { ／ 这是精度很高的表示／ long tv_sec; ／ 秒 （second） ／ long tv_nsec; / 纳秒：十亿分之一秒（ nanosecond）／}；struct timeval { ／ 普通精度 ／ int tv_sec; / 秒 ／ int tv_usec; / 微秒：百万分之一秒（microsecond）／};struct timezone { / 时区 ／ int tz_minuteswest; ／ 格林尼治韶光往西方的时差 ／ int tz_dsttime; / 韶光改动办法 ／};tv_sec 表示秒（second），tv_usec 表示微秒（microsecond，百万分之一秒即 10-6秒），
tv_nsec 表示纳秒（nanosecond，十亿分之一秒即 10-9秒）。定义 tb_usec 和 tv_nsec 的目
的是为了适用不同的利用哀求，不同的场合根据对韶光精度的哀求选用这两种表示。
其余，Linux 还定义了用于表示更加符合大众习气的韶光表示：年、月、日。但是万变
不离其宗，所有的韶光运用都是建立在 jiffies 根本之上的，我们将详细谈论 jiffies 的产
生和其浸染。简而言之，jiffies 产生于时钟中断！
5.2 时钟中断
5.2.1 时钟中断的产生
前面我们看到，Linux 的 OS 时钟的物剃头生缘故原由是可编程定时/计数器产生的输出脉冲，
这个脉冲送入 CPU，就可以引发一个中断要求旗子暗记，我们就把它叫做时钟中断。
“时钟中断”是特殊主要的一个中断，由于全体操作系统的活动都受到它的勉励。系统
利用时钟中断坚持系统韶光、匆匆使环境的切换，以担保所有进程共享 CPU；利用时钟中断进
行记帐、监督系统事情以及确定未来的调度优先级等事情。可以说，“时钟中断”是全体操
作系统的脉搏。
时钟中断的物剃头生如图 5.3 所示。
操作系统对可编程定时/计数器进行有关初始化，然后定时/计数器就对输入脉冲进行计
数（分频），产生的 3 个输出脉冲：Out0、Out1、Out2，它们各有用途，很多有关接口的书
都先容了这个问题，我们只先容 Out0 上的输出脉冲，这个脉冲旗子暗记接到中断掌握器 8259A_1
的 0 号管脚，触发一个周期性的中断，我们就把这个中断叫做时钟中断，时钟中断的周期，
也便是脉冲旗子暗记的周期，我们叫做“滴答”或“时标”（tick）。从实质上说，时钟中断只
是一个周期性的旗子暗记，完备是硬件行为，该旗子暗记触发 CPU 去实行一个中断做事程序，但是为
了方便，我们就把这个做事程序叫做时钟中断，读者可能早就习气这种叫法了，我们也不必
把一些观点区分得那么详细。
5.2.2 Linux 实现时钟中断的全过程
1．可编程定时/计数器的初始化
IBM PC 中利用的是 8253 或 8254 芯片。有关该芯片的详细知识我们不再详述，只大体介
绍以下它的组成和浸染，如表 5.1 所示。
计数器 0 的输出便是图 5.3 中的 Out0，它的频率由操作系统的设计者确定，Linux 对 8253
的初始化程序段如下（在/arch/i386/kernel/i8259.c 的 init_IRQ()函数中）：
set_intr_gate（ox20, interrupt[0]）;
／在 IDT 的第 0x20 个表项中插入一个中断门。这个门中的段选择符设置成内核代码段
的选择符，偏移域设置成 0 号中断处理程序的入口地址。/
outb_p（0x34,0x43）; / 写计数器 0 的掌握字：事情办法 2/
outb_p（LATCH & 0xff , 0x40）; / 写计数初值 LSB 计数初值低位字节/
outb（LATCH >> 8 , 0x40）; / 写计数初值 MSB 计数初值高位字节/
LATCH（英文意思为：锁存器，即个中锁存了计数器 0 的初值）为计数器 0 的计数初值，
在/include/linux/timex.h 中定义如下：
#define CLOCK_TICK_RATE 1193180 / 图 5.3 中的输入脉冲 /
#define LATCH （（CLOCK_TICK_RATE + HZ/2） / HZ） / 计数器 0 的计数初值 /
CLOCK_TICK_RATE 是全体 8253 的输入脉冲，如图 5.3 中所示为 1.193180MHz，是近似为
1MHz 的方波旗子暗记，8253 内部的 3 个计数器都对这个时钟进行计数，进而产生不同的输出旗子暗记，
用于不同的用场。
HZ 表示计数器 0 的频率，也便是时钟中断或系统时钟的频率，在/include/asm/param.h
中定义如下:
#define HZ 100
2．与时钟中断干系的函数
下面我们接着先容时钟中断触发的做事程序，该程序代码比较繁芜，分布在不同的源文
件中，紧张包括如下函数：
• 时钟中断程序：timer_interrupt（ ）；
• 中断做事通用例程：do_timer_interrupt();
• 时钟函数：do_timer（ ）；
• 中断安装程序：setup_irq（ ）;
• 中断返回函数：ret_from_intr（ ）;
前 3 个函数的调用关系如下：
timer_interrupt（ ）
do_timer_interrupt()
do_timer（ ）
（1）timer_interrupt（ ）
这个函数大约每 10ms 被调用一次，实际上，timer_interrupt（ ）函数是一个封装例
程，它真正做的事情并不多，但是，作为一个中断程序,它必须在关中断的情形下实行。如果
只考虑单处理机的情形，该函数紧张语句便是调用 do_timer_interrupt()函数。
（2）do_timer_interrupt()
do_timer_interrupt()函数有两个紧张任务，一个是调用 do_timer（ ），另一个是维
持实时时钟（RTC，每隔一定韶光段要回写），实在当代码在/arch/i386/kernel/time.c 中，
为了突出主题，笔者对以下函数作了改写，以便于读者理解：
static inline void do_timer_interrupt（int irq, void dev_id, struct pt_regs regs）
{
do_timer（regs）; / 调用时钟函数，将时钟函数等同于时钟中断未尝不可/
if（xtime.tv_sec > last_rtc_update + 660）
update_RTC();
/每隔 11 分钟就更新 RTC 中的韶光信息，以使 OS 时钟和 RTC 时钟保持同步，11 分钟即
660 秒，xtime.tv_sec 的单位是秒，last_rtc_update 记录的是上次 RTC 更新时的值 /
}
个中，xtime 是前面所提到的 timeval 类型，这是一个全局变量。
（3）时钟函数 do_timer() （在/kernel/sched.c 中）
void do_timer（struct pt_regs regs）
{
（（unsigned long ）&jiffies）++; /更新系统韶光，这种写法担保对 jiffies
操作的原子性/
update_process_times();
++lost_ticks;
if（ ! user_mode （ regs ） ）
++lost_ticks_system;
mark_bh（TIMER_BH）;
if （tq_timer）
mark_bh（TQUEUE_BH）;
}
个中，update_process_times()函数与进程调度有关，从函数的名子可以看出，它处理
的是与当提高程与韶光有关的变量，例如，要更新当提高程的韶光片计数器 counter，如果
counter<=0，则要调用调度程序，要处理进程的所有定时器：实时、虚拟、概况，其余还要
做一些统计事情。
与韶光有关的事情很多，不能全都让这个函数去完成，这是由于这个函数是在关中断的
情形下实行，必须处理完最主要的韶光信息退却撤退出，以处理其他事情。那么，与韶光干系的
其他信息谁去处理，何时处理？这便是由第三章谈论的后半部分去去处理。上面
timer_interrupt()（包括它所调用的函数）所做的事情便是上半部分。
在该函数中还有两个变量 lost_ticks 和 lost_ticks_system，这是用来记录 timer_bh()
实行前时钟中断发生的次数。由于时钟中断发生的频率很高（每 10ms 一次），以是在 timer_bh()
实行之前，可能已经有时钟中断发生了，而 timer_bh()要供应定时、计费等主要操作，以是
为了担保韶光计量的准确性，利用了这两个变量。lost_ticks 用来记录 timer_bh()实行前时
钟中断发生的次数，如果时钟中断发生时当提高程运行于内核态，则 lost_ticks_system 用
来记录 timer_bh()实行前在内核态发生时钟中断的次数，这样可以对当提高程精确计费。
（4）中断安装程序
从上面的先容可以看出，时钟中断与进程调度密不可分，因此，一旦开始有时钟中断就
可能要进行调度，在系统进行初始化时，所做的大量事情之一便是对时钟进行初始化，其函
数 time_init ()的代码在/arch/i386/kernel/time.c 中，对其简写如下：
void __init time_init（void）
{
xtime.tv_sec=get_cmos_time();
xtime.tv_usec=0;
setup_irq（0，＆irq0）;
}
个中的 get_cmos_time()函数便是把当时的实际韶光从 CMOS 时钟芯片读入变量 xtime
中，韶光精度为秒。而 setup_irq（0，＆irq0）便是时钟中断安装函数，那么 irq0 指的是
什么呢，它是一个构造类型 irqaction，其定义及初值如下：
static struct irqaction irq0 = { timer_interrupt, SA_INTERRUPT, 0, "timer", NULL, NULL};
setup_irq（0, &irq0）的代码在/arch/i386/kernel/irq.c 中，其紧张功能便是将中断
程序连入相应的中断要求行列步队，以等待中断到来时相应的中断程序被实行。
到现在为止，我们仅仅是把时钟中断程序挂入中断要求行列步队，什么时候实行，若何实行，
这是一个繁芜的过程（拜会第三章），为了让读者对时钟中断有一个完全的认识，我们忽略
中间过程，而给出一个整体描述。我们将有关函数改写如下，表示时钟中断的大意：
do_timer_interrupt（ ） ／＊这是一个伪函数 ＊／
{
SAVE_ALL ／＊保存处理机现场 ＊／
intr_count += 1; ／＊ 这段操作不许可被中断 ＊／
timer_interrupt() ／＊ 调用时钟中断程序 ＊／
intr_count -= 1;
jmp ret_from_intr / 中断返回函数 ＊／
}
个中，jmp ret_from_intr 是一段汇编代码，也是一个较为繁芜的过程，它终极要调用
jmp ret_from_sys_call，即系统调用返回函数，而这个函数与进程的调度又密切干系，因此，
我们重点剖析 jmp ret_from_sys_call。
3．系统调用返回函数
系统调用返回函数的源代码在/arch/i386/kernel/entry.S 中
ENTRY（ret_from_sys_call）
cli # need_resched and signals atomic test
cmpl $0,need_resched（%ebx）
jne reschedule
cmpl $0,sigpending（%ebx）
jne signal_return
restore_all:
RESTORE_ALL
ALIGN
signal_return:
sti # we can get here from an interrupt handler
testl $（VM_MASK）,EFLAGS（%esp）
movl %esp,%eax
jne v86_signal_return
xorl %edx,%edx
call SYMBOL_NAME（do_signal）
jmp restore_all
ALIGN
v86_signal_return:
call SYMBOL_NAME（save_v86_state）
movl %eax,%esp
xorl %edx,%edx
call SYMBOL_NAME（do_signal）
jmp restore_all
….
reschedule:
call SYMBOL_NAME（schedule） # test
jmp ret_from_sys_call
这一段汇编代码便是前面我们所说的“从系统调用返回函数”ret_from_sys_call，它
是从中断、非常及系统调用返回时的通用接口。这段代码主体便是 ret_from_sys_call 函数，
其实行过程中要调用其他一些函数（实际上是一段代码，不是真正的函数），在此我们列出
干系的几个函数。
（1）ret_from_sys_call：主体。
（2）reschedule：检测是否须要重新调度。
（3）signal_return：处理当提高程吸收到的旗子暗记。
（4）v86_signal_return：处理虚拟 86 模式下当提高程吸收到的旗子暗记。
（5）RESTORE_ALL：我们把这个函数叫做彻底返回函数，由于实行该函数之后，就返回
到当提高程的地址空间中去了。
可以看到 ret_from_sys_call 的紧张浸染有：检测调度标志 need_resched，决定是否要
实行调度程序；处理当提高程的旗子暗记；规复当提高程的环境使之连续实行。
末了我们再次从总体上浏览一下时钟中断：
每个时钟滴答，时钟中断得到实行。时钟中断实行的频率很高：100 次/秒，时钟中断的
紧张事情是处理和韶光有关的所有信息、决定是否实行调度程序以及处理下半部分。和韶光
有关的所有信息包括系统韶光、进程的韶光片、延时、利用 CPU 的韶光、各种定时器，进程
更新后的韶光片为进程调度供应依据，然后在时钟中断返回时决定是否要实行调度程序。下
半部分处理程序是 Linux 供应的一种机制，它使一部分事情推迟实行。时钟中断要绝对担保
坚持系统韶光的准确性，而下半部分这种机制的供应不但担保了这种准确性，还大幅提高了
系统性能。
逐日分享15分钟技能择要选读，关注一波，一起保持学习动力！
