C算法
深入理解 Linux 进程状态与内核 O(1) 调度算法
本文深入解析 Linux 进程概念、管理方式（PCB/task_struct）、进程状态（运行、睡眠、磁盘休眠、停止、死亡、僵尸、孤儿）、优先级机制及切换原理，并详细阐述了 Linux 2.6 内核中的 O(1) 调度算法实现细节，包括活动队列、过期队列及位图优化查找过程。
本文深入解析 Linux 进程概念、管理方式（PCB/task_struct）、进程状态（运行、睡眠、磁盘休眠、停止、死亡、僵尸、孤儿）、优先级机制及切换原理，并详细阐述了 Linux 2.6 内核中的 O(1) 调度算法实现细节，包括活动队列、过期队列及位图优化查找过程。
课本概念：正在执行的程序就是一个进程。
内核概念：分配系统资源（CPU，内存）的实体。
进程 = PCB 进程控制块 + 代码和数据。
操作系统为了方便管理进程，也采用了先描述，再组织的方式。
而描述一个进程，无非就是创建一个结构体，然后在这个结构体中记录与进程相关的信息。
在Linux 系统中 PCB 就是一个叫 task_struct 的结构体，即进程 = task_struct + 代码和数据。
那进程的信息有什么呢？换句话说就是，task_struct 中有什么数据。
• 标识符：描述本进程的唯一标识符，用来区别其他进程。
**• 状态：**任务状态，退出代码，退出信号等。
• 优先级：相对于其他进程的优先级。
**• 程序计数器：**程序中即将被执行的下一条指令的地址。
• 内存指针：包括程序代码和进程相关数据的指针，还有和其他进程共享的内存块的指针
• 上下文数据: 进程执行时处理器的寄存器中的数据。
• 其他信息...
下面我们会进行讲解。
/* 内核 0.11 版本的 task_struct 定义如下：*/
struct task_struct {
long state; // 任务的运行状态 (-1 不可运行，0 可运行 (就绪), >0 已停止)
long counter; // 任务运行时间计数 (递减)(滴答数), 运行时间片
long priority; // 运行优先数，任务开始运行时 counter=priority, 越大运行越长
long signal; // 信号，是位图，每个比特位代表一种信号，信号值=位偏移值 +1
struct sigaction sigaction[32]; // 信号执行属性结构，对应信号将要执行的操作和标志信息
long blocked; // 进程信号屏蔽码 (对应信号位图)
int exit_code; // 任务执行停止的退出码，其父进程会取
unsigned long start_code; // 代码段地址
unsigned long end_code; // 代码长度 (字节数)
unsigned long end_data; // 代码长度 + 数据长度 (字节数)
unsigned long brk; // 总长度 (字节数)
unsigned long start_stack; // 堆栈段地址
long pid; // 进程标识号 (进程号)
long father; // 父进程号
long pgrp; // 父进程组号
long session; // 会话号
long leader; // 会话首领
unsigned short uid; // 用户标识号 (用户 id)
unsigned short euid; // 有效用户 id
unsigned short suid; // 保存的用户 id
unsigned short gid; // 组标识号 (组 id)
unsigned short egid; // 有效组 id
unsigned short sgid; // 保存的组 id
long alarm; // 报警定时值 (滴答数)
long utime; // 用户态运行时间 (滴答数)
long stime; // 系统态运行时间 (滴答数)
long cutime; // 子进程用户态运行时间
long cstime; // 子进程系统态运行时间
long start_time; // 进程开始运行时刻
unsigned short used_math; // 标志：是否使用了协处理器
int tty; // 进程使用 tty 的子设备号，-1 表示没有使用
unsigned short umask; // 文件创建属性屏蔽位
struct m_inode *pwd; // 当前工作目录 i 节点结构
struct m_inode *root; // 根目录 i 节点结构
struct m_inode *executable; // 执行文件 i 节点结构
unsigned long close_on_exec; // 执行时关闭文件句柄位图标志
struct file *filp[NR_OPEN]; // 文件结构指针表，最多 32 项，表项号即是文件描述符的值
struct desc_struct ldt[3]; // 任务局部描述符表，0-空，1-代码段 cs, 2-数据和堆栈段 ds&ss
struct tss_struct tss; // 进程的任务状态段信息结构
};
Linux 底层用创建了一个结构体（假设为 List_Node），且这个结构体中的有两个 struct list_head* 类型的指针 next 和 prev。List_Node 结构体对象也是 task_struct 中的成员，然后通过 next 和 prev 将进程链接为双向链表。
然后对进程的管理就转化为了对链表的增删改查了。
这里其实有一个问题：不同于前面我们所学过的 链表，链接链表节点的指针的类型就是节点结构体类型的，而通过 List_Node 结构体中的指针将进程链接起来，由于 next 和 prev 是 List_Node 类型的，所以我们应该怎样访问 task_struct 中的数据呢？
解决这个问题用到了一个非常巧妙的方法：通过计算task_struct 中 List_Node* 对象 node 相对于结构体 task_struct 起始位置的偏移量，然后通过当前进程的 List_Node* 对象地址减去偏移量就是 task_struct 对象的起始位置的地址。然后我们就可以通过其他成员变量相对于 task_struct 起始位置的偏移量找到并访问数据了。
计算偏移量可以将 0 强转为 task_struct* 类型，然后找到 task 对象的 node 成员，由于 task 对象起始地址为 0，则 node 的地址即为偏移量（node 的地址：&((task_struct*) -> node)）。
在 Linux 源代码中，对于进程的管理和组织方式其实非常巧妙：相当于是由我们上述的结构推广而来的：
struct list_head{
struct list_head *next, *prev;
};
1、进程的信息可以在系统文件/proc 中查看
// 指令：ls /proc // 查看 PID 为 1 的进程
sudo ls /proc/1
2、进程 id
对于每个进程都有自己唯一的标识，子进程的标识符——PID，父进程标识符——PPID。
每个进程都有自己的父进程，子进程是父进程创建的，怎么创建？下面会讲
我们还可以通过系统调用的方式来获取进程 id：
调用 getpid() 函数可以得到进程自己的 PID，getppid() 可以得到父进程 PID。
使用这两个函数需要包含头文件：#include<unistd.h>
#include<stdio.h>
#include<unistd.h>
int main() {
printf("当前进程的 pid: %d\n",getpid());
printf("当前进程的父进程的 ppid: %d\n",getppid());
return 0;
}
通过 man fork 查手册可知，fork 头文件为#include<unistd.h>，最重要的是：fork 有两个返回值。
这是为什么？
fork() 执行时，内核会复制父进程的资源（如 PCB、内存空间）生成子进程，之后父、子进程会并发执行 fork() 后的代码 —— 因此
fork()的返回操作会在两个进程中分别执行，产生两个不同的返回值。
对于父进程返回子进程的 pid，子进程返回 0，表示是新创建的进程；如果错误就返回 -1。
所以，fork() 创建进程后一般用 if 进行分流：
int main() {
pid_t ret = fork();
if(ret == 0) printf("我是子进程，我的 pid:%d，我的父进程的 ppid: %d\n",getpid(),getppid());
if(ret == -1) printf("fork 出错\n");
else printf("我是父进程，我的 pid:%d，ret = %d\n",getpid(),ret);
return 0;
}
父子进程代码共享，数据各自开辟空间，私有一份（采用写时拷贝）
创建子进程时，不实际复制父进程的地址空间，而是让父子进程共享同一块物理内存，仅将这些共享的内存页标记为'只读'。只有当父子进程中任意一个尝试修改某块内存时，内核才会为该内存页创建一个副本，让修改操作在副本上进行 —— 即'需要写的时候才拷贝'
我们先通过下面一张图来大概了解一下进程状态，主要是有哪些名词。
我们常用的查看进程详细信息的指令：
ps axj | head -1 && ps axj | grep 关键字
只用 ps axj 会打印出所有的进程，不方便观察。ps axj | head -1 可以保留表头：
我们想要观察我们自己的进程，就可以再加上ps axj | grep 关键字 ，中间用 && 相连接，就可以打印出进程信息。
同时由于 grep myprocess 本来就是一个进程，大家还可以考虑加上 | grep -v grep 反向过滤 不打印出 grep 相关的进程。
一个 CPU 有一个运行队列（runqueue），当我们创建好的进程处于运行队列时，就说该进程是在运行状态，此时该进程就会等着被调度到 CPU 上执行。
现在的系统其实并不区分就绪状态，即就绪状态即为处于运行状态。
当进程 1（task1）到 CPU 上执行，代码运行到 cin 时，程序就需要等待用户从键盘上输入数据（等待用户输入数据就是等待事件），此时该进程就处于阻塞状态，操作系统就会把该进程从运行队列先拿下来，放到键盘的等待队列，当用户输入数据之后才会再次把该进程放到运行队列。
阻塞的本质就是等待某种设备或者资源就绪。
对于键盘，显示器，网卡...这些硬件，操作系统的管理方式依旧是先描述，再组织。
那什么是挂起呢？
对于操作系统的运行态部分是在内存中的，当操作系统在运行过程中内存不够用时，就会把阻塞队列（键盘等待队列）中进程的代码和数据等核心资源换出到外存的 swap 交换分区（Linux），甚至包括运行队列中进程的代码和数据。此时，进程就处于挂起状态。
注意：进程的PCB（进程控制块）会保留在内存（用于记录进程状态）。
接下来我们再看看 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 */
};
实际上在 Linux 系统中这些状态就一个整数。
R 运行状态（running）: 并不意味着进程一定在运行中，它表明进程要么是在 CPU 上运行中要么在运行 队列里。
可以同时打开两个 Xshell 窗口观察，当运行上面的程序同时，输入指令：
while : do; ps axj|head -1 && ps axj|grep ./process|grep -v grep; done
可以看到由于 while(1) 死循环，所以程序一直处于运行状态。
R+ 表示当前进程是终端的前台进程，R 表示后台进程。
**注意：**于前台进程我们可以通过 Ctrl C 结束（杀掉）进程；而 Ctrl C 并不会影响后台进程。
S 睡眠状态（sleeping): 意味着进程在等待某个事件完成（这里的睡眠有时候也叫做可中断睡眠 ），阻塞的一种。
由于我们一直在用 printf() 函数（向显示器输出内容），进程会进入显示器的等待队列，等待 IO 资源就绪。这个操作会让进程处于'等待 IO 资源'的阻塞状态。
而 CPU 处理速度极快，进程实际占用 CPU 的时间极短，所以大多数时间都处于阻塞状态，呈现出持续阻塞的状态。
S+（有'+'）表示当前进程是终端的前台进程；S（没有'+'）表示是后台进程。
bash 是Linux 系统中最常用的命令行解释器，即用户通过终端输入命令（如**
ls、cd、mkdir），bash**会解析命令并调用内核执行，返回结果。 当用户通过终端（本地终端、SSH 远程连接等）登录系统时，内核会自动创建一个 bash 进程作为'登录 shell 进程'。
可以看到全是 S 状态，因为它在等待用户输入命令，此时处于 IO 阻塞的休眠状态。
D 磁盘休眠状态（Disk sleep）：有时候也叫不可中断睡眠状态，是 Linux 进程的一种阻塞状态，指进程因等待磁盘 IO 操作完成而进入的休眠状态。
进程在等待磁盘 IO 期间，不会响应普通的信号（比如 Ctrl C），只能等磁盘操作完成后才会被内核唤醒。
很明显它和 S 状态的区别就是：一个可终断，一个不可中断。
那有什么具体应用场景呢？
比如在银行存储数据时，来了一个进程（让磁盘存储 1000MB 数据），此时该进程就会等待磁盘存储数据的结果（是否存储成功）同时进入阻塞队列（S）。
如果恰好此时内存紧张，操作系统就可能将该进程直接杀掉，当磁盘存储了 900MB 数据后发现空间不足后，要向该进程报告存储失败的结果时。
进程已经被操作系统清掉了，导致这 1000MB 的数据最后丢失，而这 1000MB 数据是当天银行的转账记录，就会造成严重的事故。
所以，又规定了一种 D 状态。当内存爆满时，操作系统就不会将 D 状态的进程清理，保证了数据不会丢失。
T 停止状态（stopped）：可以通过发送 SIGSTOP 信号给进程来停止（T）进程。这个被暂停的进程可以通过发送 SIGCONT 信号让进程继续运行。
通过 kill -19 进程 PID（发送 SIGSTOP 信号）就可以暂时中断程序，发送kill -18 进程 PID（发送 SIGCONT 信号）可以让程序继续运行。
但是需要注意：此时进程变为后台进程，Ctrl C 无法杀掉进程，需要用指令：kill -9 进程 PID，强制终止进程。
核心定义: 进程因为被调试器（如 gdb）跟踪而暂停执行的状态。
常见触发方式:
1）程序运行到断点处（break 命令）。 2）使用单步执行命令（n, s）后。 3）在程序运行时按下 Ctrl + C 主动中断。 如何恢复:
在调试器中使用 continue, next, step 等命令让程序继续执行。
X 死亡状态（dead）：这个状态只是一个返回状态，你不会在任务列表里看到这个状态。
第一次听到这个概念，确实有点抽象。下面我来举个例子：
假设：当我们在路上遇到一个人跑步（进程执行），但突然那个人倒在路上，当你过去的时候发现人已经走了（进程中断），你的第一反应肯定是报警，当警察来了之后，不是直接将这个人抬走，而是法医先采集这个人的相关信息，然后才会联系家属处理，抬走这个人。
而这个人倒下（进程终止）到法医采集完信息的过程就是僵尸状态。
【僵尸状态（Z）】：即当进程退出并且父进程（使用 wait() 系统调用，后面讲）没有读取到子进程退出的返回代码时就会产生僵死 (尸) 进程。
所以，进程结束退出后，父进程只要不来获取子进程的退出信息，就会出现僵尸状态，而且会一直持续到父进程读取到子进程退出信息。
***注意：***父进程不读取子进程的退出信息，子进程就会一直处于僵尸状态。即子进程 PCB（task_struct）就一直存在，并且需要操作系统维护，而一个父进程可以创建多个子进程，如果这些子进程退出后父进程都不去读取退出信息，子进程就无法被回收，就会造成内存泄漏（浪费内存资源）。
如何避免？我们后面讲
上面我们介绍了僵尸进程，即子进程退出，但父进程仍在执行。
那有没有一种可能：子进程还没退出，父进程先退出了。
有，就是'孤儿进程'，当父进程结束，其子进程就变成孤儿进程了。
当父进程结束后，子进程由 S+ 状态变为 S 状态，即由前台进程变为后台进程。同时，该进程（孤儿进程）的 PPID 变为 1，说明此时子进程被 PID 为 1 的进程管理（领养）。
PID = 1 的进程：是系统启动后创建的第一个用户态进程，属于系统初始化进程，负责启动系统服务、管理进程生命周期、收养孤儿进程等核心系统管理工作，是整个进程树的根。
由于 CPU 和内存资源是有限的，且一个 CPU 上一次只能跑一个进程，但进程的数量却有很多，所以进程想要在 CPU 上运行就必须排队。而进程优先级就是进程获得 CPU 资源的先后顺序，排在前面的进程优先级高，反之。
进程优先级实际上就是一个数字，数字小的优先级高，数字达到优先级低。
// 指令：ps -l
上面我们已经了解了 PID 和 PPID（ps axj），下面再补充几个关于进程 的信息：
（1）UID（user id）：进程的创建者的 id。
💡问题 1：前面访问文件时系统怎么知道我们是拥有者，所属组还是 other？
创建文件（指令）就是进程，该进程的创建者决定了该文件的拥有者，当访问文件（指令）就是进程，同样的输入指令访问文件即创建进程时，进程也会记录当前的 UID，然后将该 UID 与文件创建者的 id 进行比较，就确定了你是什么角色。
（2）PRI（priority）：进程优先级，值越小优先级越高。
💦对于 Linux 系统而言，PRI 的值默认为 80（基准值），且 PRI 的值在 [60，90] 这个区间。
（3）NI（nice 值）：进程优先级的修正数据。
💦当 PRI 为 60 时，NI 为 -20；当 PRI 为 99 时，NI 为 19。NI 的值在 [-20，19] 这个区间范围。
PRI（new） = PRI（默认） + NI。
💡问题 2：为什么修改进程优先级每次在 PRI(默认) 的基础上加 NI？
当修改进程优先级时在 PRI(默认) 的基础上加 NI（进程优先级 = 80 + NI），保证了我们即使在不知道进程原来优先级的情况下，也能将进程优先级修改为我们想要的值，避免了我们不断去查看进程优先级的不必要过程。
先输入：top -> 然后输入你要修改的进程的 PID -> 最后输入进程优先级的修正值。
***注意：***Linux 系统不支持频繁地修改进程的优先级，这会导致进程调度的不平衡。
所以，一般情况下我们都不会去修改进程优先级。
其他调整优先级的命令：nice，renice。
💡问题 3：为什么进程优先级 PRI 是在 [60，99] 这个区间范围？
在调度队列里面会讲到。
**• 竞争性：**系统进程数目众多，而 CPU 资源只有少量，甚至 1 个，所以进程之间是具有竞争属性的。为 了高效完成任务，更合理竞争相关资源，便具有了优先级。
• **独立性：**多进程运行，需要独享各种资源，多进程运行期间互不干扰
• **并行：**多个进程在多个 CPU 下分别，同时进行运行，这称之为并行
• **并发：**多个进程在一个 CPU 下采用进程切换的方式，在一段时间之内，让多个进程都得以推进，称 之为并发
上面的并发，就是通过进程切换完成的，由于 CPU 数量的限制，进程切换就成了操作系统极为重要的一个功能，下面我就来带大家了解操作系统是怎么完成进程切换的。
进程切换的原因很简单，因为多个进程都在等着到 CPU 上去运行，虽然有优先级的顺序，但还是不能保证所有的进程都能被执行到。
假设出现一个死循环，如果操作系统不对进程进行切换，这个死循环的进程就会一直占着 CPU，其他进程就永远不能被执行到了；或者有的进程执行时间可能比较长，那对于优先级较低的进程也是不公平的，所以，操作系统就需要进行进程切换。
基于时间片的分时操作系统：对于每个进程都给一个时间片（计数器），不管你优先级如何，只要在时间片在 CPU 上运行耗尽，就会把你这个进程从 CPU 上剥离下来，这样即使出现死循环操作系统也不会挂掉，同时，也保证了对于每个进程的在 CPU 上运行的公平性。
但也不能说剥离下来就剥离下来，如果进程在时间片耗尽之前运行完了，那没说的；但要是我还没到结束的时候呢？
CPU 上其实有很多寄存器，当进程在 CPU 运行时，就会将自己的数据存储在 CPU 的寄存器里面，当该进程时间片耗尽，但进程还不能结束时，肯定不能直接让操作系统把该进程剥离下来放到运行队列最后，在操作系统将进程剥离下来之前，会将该进程在寄存器上的数据记录一份在一个专门记录寄存器上数据的结构体中（struct tss_struct），而该进程的 task_struct 中就有一个 tss_struct* 的指针，操作系统会让该指针指向这份数据，当下一次轮到该进程运行时，就会根据 task_struct 中记录进程状态的参数判断：该进程是第一次占有 CPU 还是被切换下来的进程，如果是被切换过的，就会将 tss_struct 结构体中的数据拷贝（恢复）到 CPU 的寄存器里，继续接着运行。
所以说进程切换的核心就是：保存和恢复进程在 CPU 上寄存器中的上下文数据。
对于一个 CPU 而言只有一个运行队列（runqueue），上面我们已经讲了进程的切换，也就是进程的调度。那么操作系统如何完成进程的高效调度呢？
如果有多个 CPU 就要考虑进程个数的负载均衡问题
在 CPU 的运行队列中，有几个核心的组成部分：
queue[140]：这是一个指针数组，管理根据优先级组织进程（结构为哈希桶）。
为什么有 140 个位置？
queue[0 ~ 99]：为实时优先级的进程（不考虑）。
queue[100 ~ 139]：普通优先级进程（我们目前见到的进程都是普通进程，完全根据进程优先级执行），上面我们提到 NI 的值在 [-20，19] 区间，即对应 40 个优先级，刚好和这里的 100 ~ 139（40 个）不同优先级的指针数组元素对应。
那操作系统怎样完成 O(1) 调度算法？
首先我们看到上面 active 和 expired 两个指针指向两个一模一样的部分：
active 指向的 queue[140] 是活动队列，expired 指向的 queue[140] 是过期队列。
对于时间片没有消耗完的进程都按照进程优先级放在活动队列，即将要运行和正在运行的进程都在活动队列。
当进程的时间片消耗完，但进程还没到结束的时候时，就会把进程放在与活动队列相同位置处的过期队列中。当活动队列中所有 的进程在各自时间片运行完后，此时，操作系统就会让 active 指向原来的过期队列，让 expired 指向原来的活动队列，至此，活动队列中的进程又开始在 CPU 上运行了。
CPU 要执行进程，就得选一个合适的进程，从该结构中，选择一个最合适的进程，过程是怎么的呢？
从 0 下表开始遍历 queue[140]
找到第一个非空队列，该队列必定为优先级最高的队列
拿到选中队列的第一个进程，开始运行，调度完成！
遍历 queue[140] 时间复杂度是常数！但还是太低效了！
所以用一个叫**位图（bitmap[5]）**的东西实现进程的 O(1) 查找。
bitmap[5]：一共 140 个优先级，一共 140 个进程队列，为了提高查找非空队列的效率，就可以用 5*32 个比特位表示队列是否为空（若比特位为 1 则非空，为 0 则为空），这样，便可以实现对进程的 O(1) 查找，极大的 提高查找效率！
补充：**nr_active：**总共有多少个运行状态的进程。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online