Linux是一个多用户多任务的操作系统，其中多用户，是指多个用户可以在同一时间使用计算机系统；多任务，是指Linux可以在同一时间内运行多个应用程序，每个正在执行的应用程序被称为一个任务。
但我们知道单核CPU在某一时刻只能执行一个任务，所以Linux将CPU的时间分片，时间片很短大概几十到上百毫秒，调度器轮流分配给各个任务使用，因此形成多任务"同时运行"的错觉。当任务执行时，即占用CPU，其时间片会递减，OS会在当前任务的时间片用完时，切换任务，让CPU去执行其他任务(Linux是任务抢占调度机制)。
所以怎么去衡量和维护这些CPU的时间片？Linux是事先定义的节拍率，来处理时间中断，并使用全局变量Jiffies记录了开机以来的节拍数，即每发生一次时间中断，Jiffies的值就加1。
进程调度
timer_interrupt
还记得我们在任务调度初始化sched_init中费了很大功夫来初始化8253定时器，经过设置，它会每10毫秒，产生一次时间中断信号，通知CPU来调用对应的中断服务程序timer_interrupt，其中断号0x20。
在Linux0.12中，进程调度的核心驱动动力，来源于时间中断，定时器每10毫秒，就产生1次时间中断信号，来驱动系统进程调度。
下图为主要流程：
图片
我们先来看一下timer_interrupt的源码：
复制
// /kernel/sched.c
void sched_init(void)
{
...
outb_p(0x36,0x43); /* binary, mode 3, LSB/MSB, ch 0 */
outb_p(LATCH & 0xff , 0x40); /* LSB */
outb(LATCH >> 8 , 0x40); /* MSB */
set_intr_gate(0x20,&timer_interrupt); !
...
}
// /kernel/sys_call.s
....
.align 2
_timer_interrupt: //时钟中断处理程序
push %ds # save ds,es and put kernel data space
push %es # into them. %fs is used by _system_call
push %fs # # 保存ds、es并让其指向内核数据段。fs将用于system_call
pushl $-1 # 这里填-1，表明不是系统调用
//下面我们保存寄存器eax、ecx和edx。这是因为gcc编译器在调用函数时不会保存它们。
//这里也保存了ebx寄存器，会后面ret_from_sys_call中会用到它。
pushl %edx # we save %eax,%ecx,%edx as gcc doesnt
pushl %ecx # save those across function calls. %ebx
pushl %ebx # is saved as we use that in ret_sys_call
pushl %eax
movl $0x10,%eax # ds,es置为指向内核数据段
mov %ax,%ds
mov %ax,%es
movl $0x17,%eax # fs置为指向局部数据段（程序的数据段）
mov %ax,%fs
incl _jiffies #系统启动后的时钟滴答值+1
// 由于初始化中断控制芯片时没有采用自动EOI，所以这里需要发指令结束该硬件中断
movb $0x20,%al # EOI to interrupt controller #1
outb %al,$0x20
// 下面从堆栈中取出执行系统调用代码的选择符（CS段寄存器值）中的当前特权级别(0或3)并压入
// 堆栈，作为do_timer的参数
movl CS(%esp),%eax
andl $3,%eax # %eax is CPL (0 or 3, 0=supervisor) 获取当前特权级别
pushl %eax
//do_timer()函数执行任务切换、计时等
call _do_timer # do_timer(long CPL) does everything from
addl $4,%esp # task switching to accounting ...
jmp ret_from_sys_call1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.
注意这里pushl $-1，这里把-1压入栈中，表明不是系统调用。其中incl _jiffies表示jiffies值加1，jiffies则记录着，系统开机之后的时钟滴答值；另一个核心函数_do_timer，用来执行任务切换、计时等功能。
do_timer
我们接着看下do_timer的源码：
复制
// /kernel/sched.c
//参数cpl是当前特权级0或3，它是时钟中断发生时正被执行的代码选择符中的特权级。
// cpl=0时表示中断发生时正在执行内核代码；cpl=3时表示中断发生时正在执行用户代码。
void do_timer(long cpl)
{
static int blanked = 0;
//首先判断是否需要执行黑屏（blankout）操作
if (blankcount || !blankinterval) {
if (blanked)
unblank_screen();// 屏幕恢复
if (blankcount)
blankcount--;
blanked = 0;
} else if (!blanked) {
blank_screen();// 屏幕黑屏
blanked = 1;
}
// 接着处理硬盘操作超时问题。如果硬盘超时计数递减之后为0，则进行硬盘访问超时处理
if (hd_timeout)
if (!--hd_timeout)
hd_times_out();
//如果发声计数次数到，则关闭发声。(向0x61口发送命令，复位位0和1。位0控制8253计数器2的工作，位1控制扬声器)
if (beepcount)
if (!--beepcount)
sysbeepstop();
// 如果当前特权级(cpl)为0（最高，表示是内核程序在工作），则将内核代码运行时间stime递增
if (cpl)
current->utime++;
else
current->stime++;
//如果有定时器存在，则将链表第1个定时器的值减1。如果已等于0，则调用相应的处理程序，
// 并将该处理程序指针置为空。然后去掉该项定时器-和软盘有关
if (next_timer) { // 定时器链表的头指针
next_timer->jiffies--;
while (next_timer && next_timer->jiffies <= 0){
void (*fn)(void);//插入了一个函数指针定义,利用函数指针临时保存当前定时器的处理函数
fn = next_timer->fn;
next_timer->fn = NULL;
next_timer = next_timer->next;
(fn)(); //调用定时处理函数
}
}
//如果当前软盘控制器FDC的数字输出寄存器DOR中马达启动位有置位的，则执行软盘定时程序
if (current_DOR & 0xf0)
do_floppy_timer();
//如果当前进程时间片不为0，则退出继续执行当前进程。否则置当前任务运行计数值为0。
if ((--current->counter)>0) return;
current->counter=0;
// 如果当前特权级表示发生中断时正在内核态运行，则返回(内核任务不可被抢占)
if (!cpl) return;
schedule();//执行调度函数
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.
do_timer中与屏幕、硬盘处理、发生器处理、软盘处理，我们暂时忽略。其中current全局变量，表示当前任务指针，永远指向当前的任务。当初始化的时候struct task_struct *current = &(init_task.task);，current是指向0号进程的。
current->counter表示当前进程的运行时间片，用来计时的，在Linux0.12中每经过一次时钟中断(10ms)， counter就会减去1。
如果当前进程的运行时间片大于0，时间片没用完，就直接退出该函数，继续执行当前进程；如果时间片用完了，就重置为0，且当前程序运行在用户态，去执行任务调度函数(任务切换)，这就是典型的时间片轮转策略。
其中在执行任务调度之前，还会判断当前任务的特权级，如果当前特权级如果表示发生中断时正在内核态运行，哪怕其时间片用完了，也直接返回不进行任务切换，来表示内核态任务不可被抢占。
schedule
我们接着看schedule函数的源码：
复制
//kernel/sched.c
void schedule(void) //调度程序
{
int i,next,c;
struct task_struct ** p; // 任务结构指针的指针
/* check alarm, wake up any interruptible tasks that have got a signal */
//检测alarm（进程的报警定时值），唤醒任何已得到信号的可中断任务
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) // 从任务数组中最后一个任务开始循环检测alarm
if (*p) { //在循环时跳过空指针项, 即如果任务数组中有任务
//当前任务超时，则重置当前任务超时时间
if ((*p)->timeout && (*p)->timeout < jiffies) {
(*p)->timeout = 0;
//如果任务处于可中断睡眠状态TASK_INTERRUPTIBLE下
if ((*p)->state == TASK_INTERRUPTIBLE)
(*p)->state = TASK_RUNNING;//将其置为就绪状态（TASK_RUNNING）
}
//如果任务的alarm值超时则向任务发送SIGALARM信号
if ((*p)->alarm && (*p)->alarm < jiffies) {
(*p)->signal |= (1<<(SIGALRM-1));
(*p)->alarm = 0; //重置任务alarm
}
// 如果当前任务中除了阻塞信号还有其他信号，并且该任务处于可中断状态
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING; //则置任务为就绪状态
}
/* this is the scheduler proper: */
//下面是是调度程序的核心部分，简短高效
while (1) {
c = -1;
next = 0;
i = NR_TASKS;//当前任务数组长度
p = &task[NR_TASKS];
while (--i) {//从任务数组的最后一个任务开始循环处理，并跳过不含任务的数组槽
if (!*--p)
continue;
// 如果任务为运行态，就循环找出剩余时间片最大的那个任务
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
// 如果比较得出的结果不为0，则结束循环，执行switch_to
if (c) break;
// 如果比较结果为0,则重新循环任务数组
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) // 判断任务数组值不为空
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;//counter 值的计算方式为 counter = counter/2 + priority
//回到while(1)
}
//任务切换
switch_to(next);
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.
schedule任务调度函数，非常简短但很优雅， Linux0.12这里采用了基于优先级排队的调度策略 ，主要是在循环中找到系统中处于就绪态的且时间片最大的任务，进行调度。
退出循环并执行任务切换，主要有2种情况：
一种是找到处于就绪态的且时间片最大的任务。另一种就是系统中没有一个可运行的任务存在(c=-1,next=0)；其他情况则重新循环任务数组，更新任务的运行时间值counter = counter/2 + priority，继续进行循环。
父子进程的调度的顺序是由调度器决定的，与所谓进程的创建顺序无关。另外我们可以发现随着循环往后，哪些任务的优先级越高，分配到的时间片就会越大，即优先级高的任务优先运行。
switch_to
我们再来看下switch_to源码，又是内联汇编写法：
复制
// /include/linux/sched.h
#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,_current\n\t" \ // 比较n是否是当前任务
"je 1f\n\t" \ // 如果是就什么都不作
"movw %%dx,%1\n\t" \ // 将新任务的16位选择符存入__tmp.b中
"xchgl %%ecx,_current\n\t" \ // current = task[n]；ecx = 被切换出的任务
"ljmp %0\n\t" \ // 长跳转到__tmp处，此时会自动发生任务切换！！！！
"cmpl %%ecx,_last_task_used_math\n\t" \ // 判断是否使用了协处理器
"jne 1f\n\t" \ // 没有就退出
"clts\n" \ // 原任务使用过则清理cr0中的任务
"1:" \
::"m" (*&__tmp.a),"m" (*&__tmp.b), \
"d" (_TSS(n)),"c" ((long) task[n])); \ //_TSS(n)传入给dx，任务号n对应的任务传入给ecx
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.
switch_to主要功能是，切换当前任务到任务n，也就是schedule函数中的next，这个函数还是比较复杂的，我们来讲解一下其实现任务切换的流程：
定义8字节结构体__tmp，只用到了其中的六个字节，来作为后面ljmp的操作数。je 1f首先比较n是否是当前任务current，如果是就什么都不做，直接跳转到标号1处。movw %%dx,%1新任务TSS选择符(16位)赋值给第一个参数__tmp.b，也就是__tmp.b存放的是进程n的tss段选择符。xchgl %%ecx,_current交换两个操作数的值，等同于current = task[n] ，ecx = 被切换出去的任务(即原任务)。ljmp %0，这步非常重要，ljmp跳转指令表示跳转到进程n的TSS描述符处(__tmp.b存放的是进程n的tss段选择符，_tmp.a存放的是偏移地址0)。当ljmp识别描述符为TSS时，会告诉CPU进行任务切换，CPU会自动将当前任务的现场信息保存到当前任务私有的TSS中，然后将进程n的TSS中信息保存到对应的寄存器中，CPU会根据这些寄存器的值来跳转到新的进程的代码段执行任务。cmpl %%ecx,_last_task_used_math判断是否使用了协处理器，需要注意的是，只有当任务切换回来后才会继续执行该行，因为在切换前，EIP指向引起任务切换指令ljmp的下一条指令，当保存进程现场信息时，EIP的值夜会保存到原任务的TSS中；直到当任务切换回来后，原任务的TSS中进程现场信息，重新恢复到对应的寄存器中，CPU继续从EIP指向的指令开始执行任务。jne 1f、clts，如果使用了协处理器，就复位控制寄存器cr0中的TS标志，不然就跳转到标号1处直接退出。
图片
当此时完成任务切换后，会返回到时间处理函数_timer_interrupt中，继续执行ret_from_sys_call，主要是参与信号处理，我们本文就不再细讲了，后面有机会再详细聊聊。
休眠与唤醒
我们接着趁热打铁，了解一下进程的休眠与唤醒。在linux0.12中进程的休眠，主要是通过sleep_on函数来实现的，它是一个关键的调度函数，用于将当前进程置于等待状态，直到某个资源可用。
复制
//不可中断等待状态 // /kernel/sched.c
static inline void __sleep_on(struct task_struct **p, int state)
{
struct task_struct *tmp;
if (!p) // 若指针无效，则退出
return;
if (current == &(init_task.task))//如果当前任务是任务 0，则恐慌
panic("task[0] trying to sleep");
//让 tmp 指向已经在等待队列上的任务(如果有的话)，例如 inode->i_wait，并且将睡眠队列头
// 的指针指向当前任务。这样就把当前任务插入到 *p 的等待队列中。然后将当前任务置为指定
// 的等待状态，并执行重新调度
tmp = *p;
*p = current;
current->state = state;
repeat: schedule();
//只有当这个等待任务被唤醒时，程序才又会从这里继续执行。表示进程已被明确地唤醒并执行
//如果队列中还有等待的任务，并且队列头指针 *p 所指向的任务不是当前任务，则说明在本任务
// 插入队列后还有任务进入队列，于是我们应该也要唤醒这些后续进入队列的任务，因此这里将队
// 列头所指任务先置为就绪状态，而自己则置为不可中断等待状态，即要等待这些后续进入队列的
// 任务被唤醒后才用 wake_up()唤醒本任务。然后跳转至 repeat 标号处重新执行调度函数
if (*p && *p != current) {
(**p).state = 0;//0是运行态
current->state = TASK_UNINTERRUPTIBLE;//TASK_UNINTERRUPTIBLE,2,不可中断等待状态
goto repeat;
}
// 执行到这里，说明任务被真正被唤醒执行。此时等待队列头指针应该指向本任务。若它为空，
// 则表明调度有问题，
if (!*p)
printk("Warning: *P = NULL\n\r");
if (*p = tmp) //最后我们让头指针指向在我们的前面进入队列的任务//（*p = tmp）
tmp->state=0;
}
//把当前任务置为不可中断的等待状态（TASK_UNINTERRUPTIBLE）;需要利用wake_up()函数来明确唤醒，即使有信号也无法唤醒
void sleep_on(struct task_struct **p)
{
__sleep_on(p,TASK_UNINTERRUPTIBLE);//同时传入了当前任务指针p
}
// 将当前任务置为可中断的等待状态（TASK_INTERRUPTIBLE）;可以通过信号、任务超时等手段唤醒
void interruptible_sleep_on(struct task_struct **p)
{
__sleep_on(p,TASK_INTERRUPTIBLE);
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.
当多个进程在调用sleep_on函数时，会隐式构建一个等待队列，通过每个进程在内核栈中的临时变量tmp，形成了"链表"结构，它并不是一个真正的链表。每个调用sleep_on的进程会被插入到等待队列的头部。随着sleep_on函数的执行，使得tmp指针指向队列中队列头指针指向的原等待任务，而队列头指针p则指向本次新加入的等待任务。
这里还是比较特殊的，大家可以参考下面笔者吐血画的一张等待队列示意图：
图片
sleep_on函数将指定的进程进行休眠，其实就是将进程的状态设置为可中断等待状态(TASK_INTERRUPTIBLE 1)或不可中断等待状态(TASK_UNINTERRUPTIBLE 2)，那么反过来唤醒的话，就直接将进程的状态重新设置为TASK_RUNNING 0 运行态
复制
// sched.h
#define TASK_RUNNING 0 // 运行态
#define TASK_INTERRUPTIBLE 1 // 可中断等待状态
#define TASK_UNINTERRUPTIBLE 2 // 不可中断等待状态
#define TASK_ZOMBIE 3 // 僵死
#define TASK_STOPPED 4 // 停止状态1.2.3.4.5.6.
sleep_on函数在将当前进程置于等待状态后，它还会调用schedule()函数，让CPU切换到其他可运行的进程去执行。
另外我们还需知道这里可中断等待状态和不可中断等待状态的区别，可中断的等待状态的进程可以被信号或其他中断方式手段唤醒；而不可中断的等待状态，必须通过wake_up函数来显式唤醒，即使有信号也无法唤醒！
如果是操作系统的0号进程的话，当其尝试调用sleep_on函数时，会进行特殊处理，0号进程不允许进入睡眠状态，系统会触发一个恐慌panic。
接着再来看看wake_up唤醒函数：
复制
void wake_up(struct task_struct **p)
{
if (p && *p) {
if ((**p).state == TASK_STOPPED)// 处于停止状态
printk("wake_up: TASK_STOPPED");
if ((**p).state == TASK_ZOMBIE) // 处于僵死状态
printk("wake_up: TASK_ZOMBIE");
(**p).state=0;//设置为就绪状态 TASK_RUNNING
}
}1.2.3.4.5.6.7.8.9.10.
这个函数还是非常简单的，核心就是将进程的状态再设置为就绪状态(0)。需要注意的是， 调用该函数唤醒的是最后进入等待队列的任务，即等待队列中的队头任务。被唤醒的进程会重新进入调度队列task[NR_TASKS]，等待再次被调度执行。
参考资料：
https://elixir.bootlin.com/linux/0.12/source/kernel/sched.c
《Linux内核完全注释5.0》
《Understanding Linux Kernel and its Impact on System Efficiency》
