每天十五分钟，熟读一个技术点，水滴石穿，一切只为渴望更优秀的你！
————零声学院
在多进程的操作系统中，进程调度是一个全局性、关键性的问题，它对系统的总体设计、
系统的的实现、功能设置以及各个方面的性能都有着决定性的影响。根据调度的结果所作的
进程切换的速度，也是衡量一个操作系统性能的重要指标。进程调度算法的设计，还对系统
的复杂性有着极大的影响，常常会由于实现的复杂程度而在功能与性能方面作出必要的权衡 和让步。
进程调度与时间的关系非常密切，因此，本章首先讨论与时间相关的主题，然后才讨论 进程的调度，最后介绍了 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）;
outb_p（LATCH & 0xff , 0x40）;
outb（LATCH >> 8 , 0x40）;
LATCH（英文意思为：锁存器，即其中锁存了计数器 0 的初值）为计数器 0 的计数初值，
在/include/linux/timex.h 中定义如下：
#define CLOCK_TICK_RATE 1193180
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分钟技术摘要选读，关注一波，一起保持学习动力！