在学习Linux进程管理的知识之前，我们来从操作系统的发展说起，在每个阶段的发展历程中，每一个新的技术都是解决当前的技术瓶颈。
- 操作系统的进程管理的发展和解决什么问题
- 早期分时系统的内核实现，以linux0.11源码为主
1. 我从哪里来
人工控制时代
在20世纪50年代中期，出现了人们历史上的第一代计算机，那个时候还需要程序员亲自手工操作穿孔的纸带卡片，当时的计算机一切数据和操作指令都是通过穿孔纸带输入的。 穿孔纸带利用一排孔表示一个字符，用穿孔或不穿孔表示1和0，来将指令和数据导入内存。
当时，所有的程序都挨着排好队，等待管理员将其取出，换上下一个开始执行，久而久之，程序员也开始抱怨，排队十分钟，执行三秒钟，管理员切换也太慢了，时间都用在排队和切换上呢？
单道批处理
能不能让计算机自动完成程序切换，不需要手动切换呢？
人工操作的速度比起计算机实在是慢太多了， 人机矛盾 日益凸显，人类决定对机器重新进行设计，并且开发了一个 控制程序 ，在它的指挥下，可以批量执行程序，自动实现切换，不用再需要人工介入了，效率提高了不少。这就是早期的单道批处理系统诞生了，提高了系统资源利用率和吞吐量。
多道批处理
所有进程一个一个排队执行，等待执行的队伍越来越长，但是突然其中一个A阻塞了，因为在内存中仅有一道程序，所以程序在运行中发出I/O请求后，CPU就在那一直等。
大家就觉得，你看这个程序一直在做输入输出，CPU一直空着，一时半会也用不到，这不是浪费吗？要不换一个程序上去执行一会？
但是A程序执行的数据都在内存中存放着，如果切换到B程序，目前只有一个CPU，如何保证内存现场，待A输入输出回来后也能正常运行呢？
因为计算机资源的增加，此时有了同时将多个程序载入内存的能力，此时操作系统主要解决
- 操作系统需要决定将哪些程序载入内存
- 在多个隔离的程序之间进行切换
- 操作系统中多了“进程”对象和进程管理API
所以 20世纪60年代中期，引入了多道程序的设计技术，形成多道批处理系统，进一步提高资源利用率和系统吞吐量，使程序更好运行系统软件。
分时系统
但是没过多久，随着技术和需求的发展，此时要求支持多任务、多用户、多终端，新的问题有出现了。
有一天，所有的程序都在排队，等待操作系统调度，但是此时操作系统发现此时运行的程序有一个死循环，一直占用CPU，无法切换出去
对于这个问题，就产生了时间片的概念，把计算机的系统资源（尤其是 CPU时间）进行时间上的分割，每个时间段称为一个时间片，每个用户依次轮流使用时间片。
2. 分时系统
主机以很短的时间片为单位，把CPU轮流分配给每个终端使用；直到所有作业被运行完。若某个作业在分配给它的时间片内未完成计算，则该作业暂停运行，把处理器让给其他作业使用，等待下一轮再继续使用。若终端数量不多，每个终端很快就能重新获得CPU,使得每个终端得到及时响应。
2.1 时间中断
说到时间片，那么就必须用到计算机的定时器功能，这个定时器，每当定时时间到了，就会向CPU发送一个中断信号。
在linux0.11中，这个定时间隔被设置为10ms，也就是100Hz，其代码在include\sched.h
#define NR_TASKS 64 // 系统中同时最多任务（进程）数。
#define HZ 100 // 定义系统时钟滴答频率(1 百赫兹，每个滴答10ms)
也就是说每10ms硬件上通过定时器产生一次时钟中断，如果没有操作系统，这个10ms的一次时钟中断就没有任何的意义，CPU收到这个中断也不会做出任何的反映。但是，此时有了操作系统，操作系统提前设置好了中断向量表，在kernel/sched.c中有如下配置
void sched_init (void)
{
int i;
struct desc_struct *p; // 描述符表结构指针。
...
// 设置时钟中断处理程序句柄（设置时钟中断门）。
set_intr_gate (0x20, &timer_interrupt);
// 修改中断控制器屏蔽码，允许时钟中断。
outb (inb_p (0x21) & ~0x01, 0x21);
// 设置系统调用中断门。
set_system_gate (0x80, &system_call);
...
}
这样，当时钟中断，也就是 0x20 号中断来临时，CPU 会查找中断向量表中 0x20 处的函数地址，这个函数地址即中断处理函数，并跳转过去执行。
_timer_interrupt:
push ds ;// save ds,es and put kernel data space
push es ;// into them. %fs is used by _system_call
push fs
push edx ;// we save %eax,%ecx,%edx as gcc doesn't
push ecx ;// save those across function calls. %ebx
push ebx ;// is saved as we use that in ret_sys_call
push eax
mov eax,10h ;// ds,es 置为指向内核数据段。
mov ds,ax
mov es,ax
mov eax,17h ;// fs 置为指向局部数据段（出错程序的数据段）。
mov fs,ax
inc dword ptr _jiffies // 增加系统滴答数
;// 由于初始化中断控制芯片时没有采用自动EOI，所以这里需要发指令结束该硬件中断。
mov al,20h ;// EOI to interrupt controller ;//1
out 20h,al ;// 操作命令字OCW2 送0x20 端口。
;// 下面3 句从选择符中取出当前特权级别(0 或3)并压入堆栈，作为do_timer 的参数。
mov eax,dword ptr [R_CS+esp]
and eax,3 ;// %eax is CPL (0 or 3, 0=supervisor)
push eax
do_timer(CPL) ;//执行任务切换、计时等工作，在kernel/shched.c,305 行实现。
call _do_timer ;// 'do_timer(long CPL)' does everything from
add esp,4 ;// task switching to accounting ...
jmp ret_from_sys_call
这个函数主要做了以下几件事情，我们重点关注任务切换的函数
- 保持中断前的现场，主要包括内核数据段等
- 将系统滴答数这个变量_jiffies加1,
- 调用do_timer，执行任务切换，计时等工作
- ret_from_sys_call控制任务的切换与返回
时钟中断C 函数处理程序，在kernel/system_call.s 中的_timer_interrupt（176 行）被调用。
// 参数cpl 是当前特权级0 或3，0 表示内核代码在执行。
// 对于一个进程由于执行时间片用完时，则进行任务切换。并执行一个计时更新工作。
void do_timer (long cpl)
{
extern int beepcount; // 扬声器发声时间滴答数(kernel/chr_drv/console.c,697)
extern void sysbeepstop (void); // 关闭扬声器(kernel/chr_drv/console.c,691)
// 如果发声计数次数到，则关闭发声。(向0x61 口发送命令，复位位0 和1。位0 控制8253
// 计数器2 的工作，位1 控制扬声器)。
if (beepcount)
if (!--beepcount)
sysbeepstop ();
// 如果当前特权级(cpl)为0（最高，表示是内核程序在工作），则将超级用户运行时间stime 递增；
// 如果cpl > 0，则表示是一般用户程序在工作，增加utime。
if (cpl)
current->utime++;
else
current->stime++;
// 如果有用户的定时器存在，则将链表第1 个定时器的值减1。如果已等于0，则调用相应的处理
// 程序，并将该处理程序指针置为空。然后去掉该项定时器。
if (next_timer)
{ // next_timer 是定时器链表的头指针(见270 行)。
next_timer->jiffies--;
while (next_timer && next_timer->jiffies <= 0)
{
void (*fn) (); // 这里插入了一个函数指针定义！！！??
fn = next_timer->fn;
next_timer->fn = NULL;
next_timer = next_timer->next;
(fn) (); // 调用处理函数。
}
}
// 如果当前软盘控制器FDC 的数字输出寄存器中马达启动位有置位的，则执行软盘定时程序(245 行)。
if (current_DOR & 0xf0)
do_floppy_timer ();
if ((--current->counter) > 0)
return; // 如果进程运行时间还没完，则退出。
current->counter = 0;
if (!cpl)
return; // 对于超级用户程序，不依赖counter 值进行调度。
schedule ();
}
这代码，非常简单，主要是完成以下两个内容
- 如果时间片仍然大于零，则什么都不做直接返回，该程序继续执行
- 如果时间片已经为0，则调用schedule，这就是进行进程调度的主要函数
2.2 进程调度
对于进程调度的函数，主要是通过schedule来完成，而对于linux0.11的进程调度算法也比较简单，其代码实现
void schedule (void)
{
int i, next, c;
struct task_struct **p; // 任务结构指针的指针。
/* 检测alarm（进程的报警定时值），唤醒任何已得到信号的可中断任务 */
// 从任务数组中最后一个任务开始检测alarm。
for (p = &LAST_TASK; p > &FIRST_TASK; --p)
if (*p)
{
// 如果任务的alarm 时间已经过期(alarm<jiffies),则在信号位图中置SIGALRM 信号，然后清alarm。
// jiffies 是系统从开机开始算起的滴答数（10ms/滴答）。定义在sched.h 第139 行。
if ((*p)->alarm && (*p)->alarm < jiffies)
{
(*p)->signal |= (1 << (SIGALRM - 1));
(*p)->alarm = 0;
}
// 如果信号位图中除被阻塞的信号外还有其它信号，并且任务处于可中断状态，则置任务为就绪状态。
// 其中'~(_BLOCKABLE & (*p)->blocked)'用于忽略被阻塞的信号，但SIGKILL 和SIGSTOP 不能被阻塞。
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state == TASK_INTERRUPTIBLE)
(*p)->state = TASK_RUNNING; //置为就绪（可执行）状态。
}
/* 这里是调度程序的主要部分 */
while (1)
{
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
// 这段代码也是从任务数组的最后一个任务开始循环处理，并跳过不含任务的数组槽。比较每个就绪
// 状态任务的counter（任务运行时间的递减滴答计数）值，哪一个值大，运行时间还不长，next 就
// 指向哪个的任务号。
while (--i)
{
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
// 如果比较得出有counter 值大于0 的结果，则退出124 行开始的循环，执行任务切换（141 行）。
if (c)
break;
// 否则就根据每个任务的优先权值，更新每一个任务的counter 值，然后回到125 行重新比较。
// counter 值的计算方式为counter = counter /2 + priority。[右边counter=0??]
for (p = &LAST_TASK; p > &FIRST_TASK; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
}
switch_to (next); // 切换到任务号为next 的任务，并运行之。
}
该接口主要包括两部分，我们重点关注调度的部分
- 检测alarm（进程的报警定时值），唤醒任何已得到信号的可中断任务
- 调度程序部分，其流程如下
2.3 进程切换
进程切换主要是通过switch_to接口来实现的，其主要是干两件事
- 跳转到新切换的进程进行执行
- 保持当前进程的TSS信息，并将新进程的TSS加载到各个寄存器中
简单的说，即保持当前进程上下文，恢复下一个进程的上下文，其主要流程如下图，源于Linux内核完全注释V5.0
至此，我们通过linux0.11完成了进程切换的整个链路的梳理，其过程如下
3. 数据结构
对于内核，进程相关的调度都是通过struct task_struct来实现的，一个容量只有 64 大小的数组，数组中的元素是 task_struct 结构。
struct task_struct *task[NR_TASKS]
struct task_struct
{
/* these are hardcoded - don't touch */
long state; /* -1 unrunnable, 0 runnable, >0 stopped */
long counter;
long priority;
long signal;
struct sigaction sigaction[32];
long blocked; /* bitmap of masked signals */
/* various fields */
int exit_code;
unsigned long start_code, end_code, end_data, brk, start_stack;
long pid, father, pgrp, session, leader;
unsigned short uid, euid, suid;
unsigned short gid, egid, sgid;
long alarm;
long utime, stime, cutime, cstime, start_time;
unsigned short used_math;
/* file system info */
int tty; /* -1 if no tty, so it must be signed */
unsigned short umask;
struct m_inode *pwd;
struct m_inode *root;
struct m_inode *executable;
unsigned long close_on_exec;
struct file *filp[NR_OPEN];
/* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
struct desc_struct ldt[3];
/* tss for this task */
struct tss_struct tss;
};
4. 进程启动流程
我们就从这 main.c 开启我们的旅程，当然，我们只关注进程相关的部分
void main(void) {
...
// 第一步：进程调度初始化
sched_init();
...
// 第二步：创建一个新进程并做些事
if (!fork()) {
init();
}
// 第三步：死循环，操作系统正式启动完毕
for(;;) pause();
}
- 第一步 是 sched_init 进程调度初始化，上面章节已经介绍过
- 主要是最终执行到 shell 程序等待用户输入
- 操作系统就是一个中断驱动的死循环代码
5. 总结
本文主要学习了操作系统进程管理的演变过程，以最早的linux0.11为例，从数据结构，时间片，来讲解了进程调度的一些细节。同时在操作系统的不断演变过程中，进程管理的细节也不断优化和演变，但是整个骨架和流程都是一样的。本章只是从总体的视角，来学习了进程管理的框架。
