目录
1. 冯诺依曼体系结构
2. 操作系统(Operator System)
2.1 操作系统的概念
2.2 设计操作系统(OS)的目的
2.3 系统调用和库函数概念
3. 进程
3.1 进程的基本概念与基本操作
3.1.1 进程的基本概念
3.1.2 PCB -- 描述进程
3.1.3 task_ struct
3.1.4 查看进程
3.1.5 通过系统调用获取进程标识符
3.1.6 通过系统调用创建进程 -- fork初识
3.2 进程状态
3.2.1 运行状态、阻塞状态、挂起状态的理解
3.2.1.1 运行状态
3.2.1.2 阻塞状态
3.2.1.3 挂起状态
3.2.2 Linux内核源代码中对进程状态的描述
3.2.3 僵尸进程
3.2.4 孤儿进程
3.3 进程优先级
3.3.1 基本概念
3.3.2 查看系统进程
3.3.3 PRI 和 NI
3.3.4 进程运行时修改进程优先级的命令
3.3.5 补充概念 -- 竞争、独立、并行、并发
3.4 进程切换
3.5 Linux2.6内核进程O(1)调度算法
3.5.1 Linux2.6内核中进程队列的数据结构
3.5.2 优先级
3.5.3 活动队列
3.5.4 过期队列
3.5.5 active指针和expired指针
3.5.5 总结Linux2.6内核的调度过程
1. 冯诺依曼体系结构
我们常⻅的计算机，如笔记本。我们不常⻅的计算机，如服务器，⼤部分都遵守冯诺依曼体系。
目前，我们所认识的计算机都是由一个个的硬件组成，包括如下：
输⼊单元：包括键盘, ⿏标，扫描仪, 写板，网卡，磁盘(外存)等。
中央处理器(CPU)：含有运算器和控制器等。
存储器：内存。
输出单元：显⽰器，打印机，磁盘，网卡等。
关于冯诺依曼体系结构，需要强调几点：
1.存储器指的就是内存。
2.不考虑缓存的情况，CPU只能对内存进行读写，不能访问外设。
3.外设要输入或者输出数据，也只能写入内存或者从内存中读取。
知识点1：
为什么程序运行必须先加载到内存？
程序的执行是通过CPU执行代码和访问数据的，CPU只能对内存进行读写，所有是冯诺依曼体系结构决定了程序运行前必须先加载到内存中。
知识点2：
数据进行传输或者流动的本质就是从一个设备“拷贝”到另一个设备，体系结构的效率由设备的“拷贝”效率决定。
从硬件的角度上来理解，用户1用qq发送一条消息给用户2。本质上就是两台冯诺依曼体系结构的计算机进行数据的交互，具体过程如下：
(1)首先用户1和用户2都要启动qq，本质是将qq这个可执行程序加载到内存中。
(2)当用户1用键盘输入消息时，本质是从键盘（用户1输入设备）输入数据到内存中，然后cpu从内存中读取数据进行加密等过程，把输入的数据进行处理，再给回内存。
(3)内存把处理后的数据交给网卡（用户1输出设备），网卡 经过网络把数据传给用户2的网卡（用户2的输入设备）。
(4)用户2的内存从网卡（用户2的输入设备）中读取数据并交给cpu处理再写回内存，然后再由内存输出到显示屏（用户2的输出设备）上。
2. 操作系统(Operator System)
2.1 操作系统的概念
任何计算机系统都包含一个基本的程序集合，称为操作系统(OS)。操作系统的本质就是一款进行计算机软硬件管理的软件。
狭义上的操作系统：就是指的内核(Linux内核，windows内核)，主要的任务是进行进程管理，内存管理，文件管理，驱动管理。
广义上的操作系统：包含内核，外壳shell，函数库，预装的系统软件等。我们所说的Linux，Windows一般指的是广义上的操作系统。
2.2 设计操作系统(OS)的目的
设计操作系统的核心目的是为了给用户程序（应用程序）提供一个良好的执行环境，其为了达到这个目的，就设计出操作系统与硬件交互，管理所有的软硬件资源。
操作系统本质上是一款“搞管理”的软件，管理软硬件资源。
以操作系统管理硬件为例，操作系统对硬件进行管理时本质上是对硬件的属性数据进行管理，而且拿到这些属性数据并不需要操作系统去访问硬件，而是由驱动程序去访问硬件，然后再把硬件的属性数据给操作系统。操作系统是C语言写的，在C语言中可以使用struct结构体对象，对一个实体对象（这里指的是硬件设备）进行描述，然后在struct中加入一个指向struct对象的指针使硬件设备连接起来，形成链表的结构。这样一来，操作系统对硬件的管理，就转换为了对链表的增删查改。
所以进行管理就是先描述再组织。先使用struct结构体对被管理对象的属性数据进行描述，然后使用链表，红黑树等数据结构对其每个结构体对象进行组织。
所以在C++中，类就是解决描述的问题，而STL容器就是解决组织的问题。
知识点1：
如上图，是软硬件体系结构，是一种层状结构。
知识点2：
访问操作系统必须使用系统调用接口 -- 其实就是函数，只不过是系统提供的。知识点3：
程序只要访问了硬件，那么它必须贯穿整个软硬件体系结构。
知识点4：
平时使用的库函数可能封装了系统调用接口，如printf。
2.3 系统调用和库函数概念
在开发角度，操作系统对外会表现为一个整体，但是会提供自己的部分接口供上层开发使用，这部分由操作系统提供的接口叫做系统调用。系统调用的本质就是系统提供给上层用户的接口，方便用户和操作系统之间进行数据交互。
系统调用使用上功能比较基础，对用户的要求相对也比较高，所以有的开发者就对部分系统调用进行适度封装，从而形成库，有了库函数，就很有利于更上层用户或者开发者进行二次开发。
3. 进程
3.1 进程的基本概念与基本操作
3.1.1 进程的基本概念
进程的定义：程序的一个执行实例，即正在执行的程序。从内核的角度看，一个进程就是担当分配系统资源（cpu，内存）的实体。在Linux内核里，进程有时也叫做任务。
当一个程序运行起来，要把其对应的代码和数据加载到内存中，但是OS需要对这一段的代码和数据已经其他的程序进行管理，所以要进行先描述再组织！则会在OS内部有一个自定义结构体对象对程序的代码和数据(代码地址，数据地址，id，优先级，状态等属性)进行描述，然后使用双链表等数据结构对其进行连接即组织起来。该结构体在0S中被称为PCB(process control block)。在Linux中PCB则是被叫做task_struct。
所以一个通俗的进程的定义就是：进程 = 内核数据结构对象 + 程序的代码和数据。在Linux操作系统中：进程 = PCB(task_struct) + 程序的代码和数据。
知识点1：
之前执行的所以指令，工具，自己写的程序，运行起来全部都是进程。
3.1.2 PCB -- 描述进程
基本概念：进程信息被放在叫一个进程控制块(PCB)的数据结构中，可以理解为进程属性的集合。Linux操作系统的PCB是task_struct。task_struct是Linux内核的一种数据结构类型，它会被装载到RAM（内存）里，并包含着进程的信息。
3.1.3 task_ struct
task_struct中的内容分类：
（1）标识符(pid)：描述本进程的唯一标识符，用来区分其他进程。
（2）状态： 任务状态，退出代码，退出信号等。
（3）优先级: 相对于其他进程的优先级。
（4）程序计数器: 程序中即将被执⾏的下⼀条指令的地址。
（5）内存指针: 包括程序代码和进程相关数据的指针，还有和其他进程共享的内存块的指针。
（6）上下⽂数据: 进程执⾏时处理器的寄存器中的数据。
（7）I/O状态信息: 包括显⽰的I/O请求,分配给进程的I∕O设备和被进程使⽤的⽂件列表。
（8）记账信息: 可能包括处理器时间总和，使⽤的时钟数总和，时间限制，记账号等。
（9）其他信息。
组织进程：所有运行在系统里的进程的task_struct都要以双链表的形式连接起来存储在内核里。下图中，每一个长条形就代表一个进程的task_struct。
知识点1：
理解内核中存储task_struct的链表：
首先task_struct中存放的是进程的属性，其中还存放了一个list_head的结构体变量links，而list_head中只有struct list_head *next 和 struct list_head *prev指针。task_struct 和 list_head 的结构如下：
struct task_struct { int x; int y; int z; ... list_head links; ... } struct list_head { struct list_head *next, *prev; }所以在内核中task_struct的连接，就是前一个 task_struct 中的 list_head 中的 next指针指向下一个 task_struct 中的 list_head 结构体对象，下一个 task_struct 中的 list_head 的 prev 指针指向上一个 task_struct 中的 list_head 结构体对象。
知识点2：
怎么通过上述链表的连接获取task_struct中的属性呢？
结构体内部属性的地址是依次增加的。&((struct task_struct*)0->links)这行代码首先是将0号地址强转为struct task_struct*类型，然后对这个结构体中的links变量取地址，则得到0到links的偏移量offset。如上图，要获得第一个task_struct的地址，则使用前面一个next - offset，再将获得的地址强转为struct task_struct*，则这样就可以通过->的方式对结构体内部的其他属性进行访问了。
3.1.4 查看进程
（1）进程的信息可以通过 /proc 系统⽂件夹查看。
先启动一个死循环的进程myprocess，pid为21023，然后使用 ls /proc/21023 -l 对该进程里的属性进行查询可以得到如下信息：
知识点1：
Linux中一切皆文件。/proc是一种内存级的文件，里面存储的是每一个进程的信息，所以可以使用查看文件的方式对进程进行查看。
知识点2：
进程在启动的时候就会记录当前可执行程序的路径已经当前的工作目录，如果在代码中要进行新建文件操作等，就会在当前工作目录下进行新建，可以在程序中使用chdir()系统调用对当前工作目录进行修改。
（2）⼤多数进程信息同样可以使⽤top和ps这些⽤⼾级⼯具来获取
这里查看指定的进程已经进程上方显示进行的属性，可以使用grep来进行过滤，在命令行中使用“ ; ”和“ && ”用来连接两条命令。
介绍杀掉进程的两种方式：
（1）Ctrl + c （2）kill -9 进程的pid
3.1.5 通过系统调用获取进程标识符
获取当前进程的pid：getpid()。获取父进程的pid：getppid()。
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
int main()
{
printf("pid: %d\n", getpid());
printf("ppid: %d\n", getppid());
return 0;
}
知识点1：
命令行启动的进程，该进程的父进程是bash(命令行解释器)，上述父进程pid为16354。OS会给每一个登录用户分配一个bash，-bash代表远程登录的意思。
3.1.6 通过系统调用创建进程 -- fork初识
下列代码中用fork()函数创建子进程，创建成功把子进程的PID返回给父进程，把0返回给子进程，创建失败返回-1。创建之后，子进程和父进程都会执行后续的代码。
#include <stdio.h>
#include <unistd.h>
int main()
{
printf("父进程开始运行，pid：%d\n", getpid());
fork();
printf("进程开始运行，pid：%d\n", getpid());
return 0;
}
因为fork创建进程返回给父进程和子进程的PID不同，所以可以根据PID的不同使用if进行分流，使父子进程执行不同的代码块。
#include <stdio.h>
#include <unistd.h>
int main()
{
printf("父进程开始运行，PID：%d\n", getpid());
pid_t id = fork();
if (id < 0)
{
perror("failed!!!\n");
return 1;
}
else if (id == 0)
{
//子进程
while(1)
{
sleep(1);
printf("我是一个子进程！，我的PID：%d，我的父进程PID：%d\n", getpid(), getppid());
}
}
else
{
//父进程
while(1)
{
sleep(1);
printf("我是一个父进程！，我的PID：%d，我的父进程PID：%d\n", getpid(), getppid());
}
}
return 0;
}
知识点1：
为什么一个函数会返回两次?
这里以fork函数为例，一个函数执行到最后的return语句时，核心的功能和任务都已经完成，所以在fork函数的栈帧中，还没有执行到return语句的时候，子进程已经被创建了出来，所以后续的return语句也是父子进程共享的，在fork的栈帧中，return语句就被父进程和子进程各执行了一次，所以fork函数有两个返回值。
知识点2：
为什么一个变量即 == 0，又大于0？导致if elseif同时成立？
默认情况下，子进程和父进程的数据是共享的，但是当一方对数据进行修改时，操作系统会对内存中被修改的数据进行拷贝一份，这样之后，父子进程就各自有一份独立的数据，所以上述fork()返回的值即 == 0又大于0，因为在底层，操作系统对程序的数据进行了写时拷贝。
知识点3：
为什么fork给父进程返回子进程的PID，给子进程返回0？
父进程：子进程 == 1：n 的关系，所以要把子进程的PID给父进程，父进程根据不同的PID来区分不同的子进程，方便对子进程做管理。
知识点4：
进程具有独立性！-- 一个进程结束不会影响另一个进程的运行，父进程挂了也不影响子进程的运行。
3.2 进程状态
进程状态就是进程task_struct中的一个整型变量，该整型变量标识着该进程此时对应的状态。
3.2.1 运行状态、阻塞状态、挂起状态的理解
3.2.1.1 运行状态
定义：一个进程要么正在被CPU运行要么位于运行调度队列中就被称为该进程处于运行状态。
理解：一个CPU就会有一个调度队列（runqueue），该队列中存储的是一个一个指针（task_struct*），这些指针指向处于运行状态的进程的task_struct。
知识点1：
CPU执行程序不是先执行完一个程序再去执行另外一个程序，而是先将准备好被执行的程序按照其优先级排列在调度队列中，规定每次执行10ms(该数值这里是随便给的，具体情况还需要根据具体操作系统进行分析)这么长的一个时间片，给一个程序执行一个时间片之后停止执行该程序，转而去执行调度队列中的下一个程序,执行一个时间片。从优先级高的执行到优先级低的程序。这种执行方式也叫做并发。
3.2.1.2 阻塞状态
定义：一个进程等待某种设备或者资源就绪的状态称为阻塞状态。
理解：首先，操作系统不仅要使用一个task_struct的结构体来对进程进行描述和组织，还有用另外一个结构体（类似于进程的结构体）对硬件进行描述和组织，这里暂时给描述硬件结构体命名为struct device。以一个程序中scanf()为例，当该程序执行到scanf()时，该进程会等待用户从键盘（硬件设备）上输入数据，此时描述键盘的struct device中会有一个指针，指向该设备的等待队列，等待队列中存储的就是等到键盘响应的进程，这些进程被链接到这个等待队列中，则表明该进程处于阻塞状态。
知识点1：
进程状态变化的表现之一就是，在不同的队列中进行流动。比如从运行状态到阻塞状态，就是从调度队列流动到一个资源或设备的等待队列中。本质都是数据结构的增删查改。
知识点2：
有了上面对内核中双链表的理解，我们可以在一个task_struct中放入多个类似于list_head的节点，这样的话，一个task_struct结构体对象就不止属于一个数据结构中了，可以同时属于内核中的双链表和等待队列等多个数据结构中。所以task_struct就可以在内核中不同的队列中流动了。
3.2.1.3 挂起状态
定义：一个进程将它的代码和数据唤出到磁盘中，在内存中只保留对应的PCB（task_struct）时，这种状态称为挂起。
理解：在磁盘上有一块区域名为swap交换分区，当内存不足的时候，操作系统会将在阻塞状态的进程对应的代码和数据唤出到磁盘的swap交换分区中，此时在内存中只有该进程的task_struct，这种状态称为阻塞挂起。假如现在键盘的等待队列中有一个进程为阻塞挂起状态，此时从键盘中输入数据，则操作系统会将swap交换分区中被唤出的该进程的代码和数据重新唤回到内存中，然后把该进程链接到调度队列中，此时该进程则转换为运行状态。当内存严重不足时，操作系统会把调度队列中当前没有被执行的进程的代码和数据唤出到swap交换分区中，这种状态称为运行挂起。
3.2.2 Linux内核源代码中对进程状态的描述
在Linux系统中，有一个静态的字符串数组，里面存储的就是进程所有可能的状态，并且每一个状态都对应着一个整数。下面就是Linux系统中进程的状态。
/*
*The task state array is a strange "bitmap" of
*reasons to sleep. Thus "running" is zero, and
*you can test for combinations of others with
*simple bit tests.
*/
static const char *const task_state_array[] = {
"R (running)", /*0 */
"S (sleeping)", /*1 */
"D (disk sleep)", /*2 */
"T (stopped)", /*4 */
"t (tracing stop)", /*8 */
"X (dead)", /*16 */
"Z (zombie)", /*32 */
};1. R（running）运行状态: 进程要么是正在被CPU运⾏要么在运⾏调度队列中。
#include <stdio.h>
int main()
{
while(1)
{
//printf("hello Linux!\n");
}
return 0;
}
上述代码就是一个空的while循环，该代码一直运行着，通过监视可以看到这个进程的状态一直为R+。R+代表该进程在前台运行。
使用 ./test &，使程序在后台运行，不占用前台的命令行解释器。这样观察到的状态就是R。
2. S（sleeping）睡眠状态: 意味着进程在等待事件完成，这⾥的睡眠有时候也叫做可中断睡眠（interruptible sleep），意思就是进程在等待的时候用户可以杀掉该进程，是阻塞状态中的一种。进程中执行到scanf()等待用户输入时，该进程就是睡眠状态。
3. D（Disk sleep）磁盘休眠状态：有时候也叫不可中断睡眠状态（uninterruptible sleep），进程如果涉及到高IO操作时，就会将该进程设为D状态，一般这个状态下不能通过kill杀掉进程，这个状态的进程通常会等待IO操作的结束。该状态也是阻塞状态的一种。
4. T/t（stopped）停止状态：可以通过发送 SIGSTOP 信号给进程来停⽌（T）进程。这个被暂停的进程可以通过发送 SIGCONT 信号让进程继续运行。
使用gdb调试test时，程序运行到断点停止就是一种停止状态，test则是为t状态。使用Ctrl + z来暂停进程，此时test为T状态。
5. X（dead）死亡状态：这个状态只是⼀个返回状态，不会在任务列表⾥看到这个状态。
6. Z（zombie）僵死状态：一个比较特殊的状态。子进程退出，父进程还在运行，但父进程没有读取子进程状态，子进程进入Z状态。下面介绍僵尸进程时具体进行介绍。
知识点1：
一个进程在系统中运行，就是反复的在不同的状态中进行切换，直到运行到结束，收到结束信号为止。
3.2.3 僵尸进程
一个进程如果处于僵死状态（Z）就是僵尸进程，僵尸进程会以终止状态保持在进程表中，并且会一直等待父进程读取退出状态代码。
下面这段代码中创建一个子进程，当子进程执行完父进程不进行回收，观察子进程的状态，为僵死状态。
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main()
{
pid_t id = fork();
if (id == 0)
{
//child
int count = 5;
while(count)
{
printf("我是子进程，我正在运行：%d\n", count);
sleep(1);
count--;
}
}
else
{
//father
while(1)
{
printf("我是父进程，我正在运行...\n");
sleep(1);
}
}
return 0;
}
如果父进程一直不管子进程，不获取子进程的退出信息，那么子进程会一直处于僵死状态，则子进程的PCB会一直存在，一直占用内存，导致内存泄漏。僵尸进程也是内存泄漏。
知识点1：
进程退出了，内存泄漏问题还存不存在？
进程退出之后，该进程中申请的资源系统都会自动回收，不存在内存泄漏问题。
操作系统也是一款软件，当电脑一打开操作系统就会一直运行，这种一直运行的程序称为常驻程序。而进程的管理是操作系统进行管理的，所以出现僵尸进程时，代表操作系统这个软件出现了内存泄漏，需要用户进行手动的管理回收。
知识点2：
程序运行起来就会变为进程，而OS中会有一个task_struct来维护这个进程，所以程序一运行起来就会向内存申请空间来存储它的task_struct。
但是操作系统中进程的创建和释放是非常高频的事情。所以在这里，当一个进程释放的时候，不释放它的task_struct，而是把它的task_struct存入一个unuse的链表中进行维护，这里可以称为数据结构对象的缓存，而当下一个进程创建的时候，在这个链表中取出一个task_struct对其进行初始化，用于维护新创建的进程。
这样的会就会减少内存的申请和释放，加速创建进程和释放进程的速度，提升效率。
3.2.4 孤儿进程
父进程先退出，子进程还没有退出，此时该子进程就称为孤儿进程。孤儿进程被1号进程(init或者systemd)领养。1号进程可以就看作为操作系统。
用下列这段代码来演示一下孤儿进程：
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main()
{
pid_t id = fork();
if (id == 0)
{
//child
while(1)
{
printf("我是一个子进程， pid：%d，ppid：%d\n", getpid(), getppid());
sleep(1);
}
}
else
{
//father
int cnt = 5;
while(cnt)
{
printf("我是一个父进程， pid：%d，ppid：%d\n", getpid(), getppid());
cnt--;
sleep(1);
}
}
return 0;
}
知识点1：
为什么1号进程要领养孤儿进程？如果孤儿进程没有父进程，则在退出的时候退出信息没有进程获取，会一直处于僵尸状态，则会造成内存泄漏问题。所以1号进程要领养孤儿进程，成为它的父进程，进而回收子进程。
知识点2：
孤儿进程被1号进程领养之后就在后台运行了， Ctrl + c不能直接结束孤儿进程。
3.3 进程优先级
3.3.1 基本概念
cpu资源分配的先后顺序，就是进程的优先级(priority)。优先级高的进程有优先执行权利。配置进程优先权多任务环境的linux很有用，可以改善系统性能。
进程的优先级也是该进程task_struct结构体中的一个属性，一个int类型的变量，一般这个数字值越低，优先级越高。
为什么进程要有优先级？
因为cpu资源稀缺，导致要通过优先级来确认谁先谁后。
3.3.2 查看系统进程
在Linux或者unix系统中，用 ps -al 命名则会输出类似如下的几个内容：
UID：代表执行者的身份。
PID：代表这个进程的代号。
PPID：代表这个进程父进程的代号。
PRI：代表这个进程可被执行的优先级，其值越小优先级越高。
NI：代表这个进程的nice值，即为优先级的修正值。
知识点1：
UID(user id)是用户的代号，运行命令 ls -ln 可以查看文件拥有者和所属组的UID，使用 ps 这类命令时可以看到进程执行者的UID。
知识点2：
系统怎么知道访问文件时，访问者是拥有者，所属组还是other？
Linux系统中，访问任何资源都是进程在进行访问，进程有自己的UID，进程久代表用户。文件的拥有者，所属组也有自己的UID，用进程的UID与依次匹配文件拥有者，所属组的UID，就能知道该进程的执行者是文件的拥有者，所属组还是other了。
3.3.3 PRI 和 NI
PRI：进程的优先级，默认情况下为80.
NI：进程优先级的修正值(nice值)，默认情况下为0.
PRI(new) = PRI(默认) + nice
当nice值为负值时，该进程的优先级会变高，nice值为正值时，该进程的优先级会变低。调整进程优先级，在Linux系统中，就是调整进程的nice值，nice的取值范围是-20到19，一共40个级别。
知识点1：
优先级设置不合理，会导致优先级低的进程长时间得不到CPU资源，进而导致进程饥饿。
3.3.4 进程运行时修改进程优先级的命令
输入 top 命令
进入top后按 " r "
然后输入进程PID，再输入回车
输入nice值
得到如下结果，将进程的优先级调低了。
注：其他调整优先级的命令 -- nice，renice，以及系统调用接口。
3.3.5 补充概念 -- 竞争、独立、并行、并发
竞争性：系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级。
独立性：多进程运行，需要独享各种资源，多进程运行期间互不干扰。比如电脑上的各个启动的程序之间，相互是不受影响的。
并行：多个进程在多个CPU下分别同时运行，称为并行。
并发：多个进程在一个CPU下采用进程切换的方式，在一段时间内，让多个进程都得以推进，称为并发。
下图中第一个图就是并发，第二图就是并行。
知识点1：
理论上，在某一时刻，一个CPU上只能有一个进程在运行，但是在一段时间中，可以通过进程切换的方式，让多个进程同时推进，比如一个进程运行10ms，然后换另一个进程运行。由于时间间隔短，用户层面是察觉不出区别的，就会感觉所以进程是在一起运行的。
3.4 进程切换
CPU上下文切换：实际含义就是任务切换（进程切换），或者CPU寄存器切换。当内核决定运行另外的任务时，它保存正在运行任务的当前状态，就是CPU寄存器中该进程当前的临时数据。这些内容被保存在任务自己的堆栈(TSS：任务状态段)中，然后把下一个要运行的任务的当前状态从该任务的栈中重新装入CPU寄存器中，并开始执行下一个任务的运行，这一过程就是context switch。
知识点1：
时间片：当代计算机都是分是操作系统，每个进程都有它适合的时间片(一个计数器)。时间片到达，进程就被操作系统从CPU中剥离下来，然后调度下一个进程进行运行。
3.5 Linux2.6内核进程O(1)调度算法
3.5.1 Linux2.6内核中进程队列的数据结构
一个CPU只有一个runqueue，runqueue是一个结构体，里面存储的是运行队列的相关属性值。
系统中有一个类似struct task_struct* current的指针，指向当前正在运行的进程的task_struct。
3.5.2 优先级
上述活跃进程和过期进程中的queue，就是优先级队列，里面存储的就是优先级[0, 139]的所有进程。
普通优先级：[100, 139]，刚好40个优先级，对应之前的PRI范围[60, 99]。
实时优先级：[0, 99]，用于支持实时操作系统，一般用于工业领域，这里不考虑。
3.5.3 活动队列
所有运行状态进程都按照优先级放在queue[140]中。
nr_active：表示总共有多少个运行状态的进程。
queue[140]：该数组本质是一个开散列哈希表，数组下标代表进程的优先级，数组元素代表同一个优先级的进程队列，相同优先级的进程按照FIFO规则在队列中进行排列。
bitmap[5]：这是一个位图，数组中一个元素有32个bit位，一共160个bit位。这里只使用其中140，对应的就是140个优先级，为了提高查找非空队列的效率，就可以使用140个bit位表示队列是否为空，大大提高查找队列的效率。
上图中第一个元素的第二位和第六位不为空，则表示queue中下标为2和6的队列不为空队列。
活跃队列的运行过程：
（1）根据位图，从0-139找到第一个非空队列。
（2）找到非空队列之后，再在队列中以FIFO的规则拿出第一个进程的task_struct，这样就找到了即将要运行的进程了，然后把current指针指向该进程的task_struct，在把该进程当前状态下的临时变量从该进程的堆栈中放入CPU中，此时CPU在执行该进程。
3.5.4 过期队列
过期队列和活动队列结构一模一样，过期队列上放置的进程就是上一个时间片运行完但没有运行到结束的进程，当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片的重新计算。
3.5.5 active指针和expired指针
active指针永远指向活动队列，expired指针永远指向过期队列。新建的进程会被插入到活动队列里。
在运行时，活动队列上当前被执行的进程时间片耗尽之后，就会把该进程的task_struct放入过期队列中，这样活动队列上的进程数会越来越少，过期队列上的进程数会越来越多。当活动队列中全部的进程都运行了一个时间片之后，所以进程都在过期队列中，然后把active和expired指针进行交换，这样之前的活动队列就成为了新的过期队列，之前的过期队列就成为了新的活动队列，然后继续执行。
这样的话就会在局部保证所有进程都运行完一个时间片才会运行第二个时间片，有效的防止了进程饥饿的问题。
3.5.5 总结Linux2.6内核的调度过程
(1) 先找到active指向的活动队列。
(2) 再在活动队列中根据位图，从0 - 139找到不为空且优先级最高的进程队列。
(3) 再在进程队列中按照FIFO规则拿出待执行的进程的taks_struct，然后系统中的current指针(指向当前CPU正在运行的进程的PCB)指针该进程的task_struct。
