【Linux进程篇】Linux学习第十七弹——Linux 进程调度怎么选任务？从内核链表到 O(1) 调度器

本文以 Linux 2.6.22 中的 O(1) 调度器为例，讲解任务如何组织、调度器如何找到可运行任务，以及active/expired优先级数组如何处理任务周转。它是理解 Linux 调度演进的历史模型，不代表现代 Linux 内核仍使用这套调度算法。

一、进程组织

有了进程的优先级和进程切换的概念，那我们就来看看进程是怎么跑起来的—一进程组织！

• 之前在进程状态那谈过进程的调度队列，这个调度队列是怎么把各个进程给组织起来的呢？这就要来谈谈task_struct的结构了。

• 整个调度队列的结构就是一个双链表。
• 每个进程的task_struct都有两个指针prev和next分别指向的是上一个进程和下一个进程第一个结点就是队列的头结点，后面一个一个的进程就组成了一个运行队列。

讲上面的链表转换为代码：

• 有几个细节：每个进程的next指针指向的都是task_struct里的那个struct link node结构体！而不是指向进程的task_struct结构体的起始位置！！！

既然指向的是task_struct中的其中一个结构体，那么怎么得到task_struct的其他属性呢？它们又是如何被组织起来的呢？下面就来看看进程如何组织？

二、进程如何组织？—— 内核链表与 C 语言地址

之前几篇文章中研究的一直是 “一个PCB”。现在要回答：进程到底怎么被组织起来的？为什么说用链表组织？下面就来看看：

2.1 传统单链表（回顾）

• 传统写法：结构体node { data; struct node *next; }，next指向下一个整个节点。
• 需要一个数据就new一个节点，然后再用next串起来。

2.2 Linux 内核链表的特殊之处（铺垫）

• Linux 内核的单链表思想没变，但实现非常特殊——它把next指针嵌在数据结构(task_struct)内部，而不是把数据嵌在链表节点里。（具体内容后面会展开。）
• 为了理解它，必须先搞清 C 语言的地址排布规律。

2.3 三个基础问题（C 语言地址规律）

问题 1：结构体里，先定义的成员地址大还是小？

• 假设结构体struct A { A; B; C; D; }，成员是依次开辟的。
• 结论：先定义的成员地址越低（离结构体起始位置越近）。
  • 即：&obj.A的数值 =&obj（结构体变量地址）的数值；
  • 顺序上 A < B < C < D（地址依次增大）。
• 不用考虑大小端（大小端主要针对内置类型的字节/位序，不影响自定义类型的成员排布规律）。

问题 2：一个int a（4 字节），取&a只得到一个地址，是哪一个字节的地址？

• 4 个字节各有地址，但取&a只给一个地址。
• 结论：取的是这 4 个字节里地址最低的那个字节（整块内存的最低字节）。
• 那怎么访问整个 4 字节？→靠类型(类型即偏移量)：类型决定大小，拿最低地址 + 偏移量（连续取 4 字节），即"基地址 + 偏移量"方式拿到整个变量。

问题 3：数组地址 / 元素地址谁大谁小？

• int arr[10]，取&arr（数组地址），数值上等于第一个元素的地址。
• 元素地址：&arr[0] < &arr[1] < ... < &arr[9]，第一个元素地址最小，依次增大（每次增大一个元素类型的大小）。
• 这解释了为什么"指针++ 往后走"能依次访问数组元素（地址增大）。

所以我们得出一个结论：在C语言中，任何变量/对象取地址，拿到的都是开辟众多字节中，“地址最小” 的那个字节的地址。

2.4 已知内部成员地址，如何反求整个结构体地址？

• 如果我们只知道结构体内部成员 C 的地址，想求整个结构体变量的起始地址怎么办？。
• 做法（"零地址强转"技巧）：

  // 逻辑上：认为从 0 号地址处存在一个 struct A 变量// 访问其成员 C，取地址 → 得到的数值就是 C 相对结构体起始的偏移量size_toffset=(size_t)&((structA*)0)->C;

  • 因为起始地址为 0，所以&C的数值 =C 相对结构体开头的偏移量（如 8）。
• 反过来：已知真实 C 的地址（如 0x123344）减去偏移量（8）→ 得到整个结构体变量的起始地址（因为起始地址比 C 小，所以是"减"）。
• 这是 C 语言提供的offsetof宏的原理（<stddef.h>）。

补充：

• offsetof(type, member)的原理：把 0 强转成该类型指针，取成员地址，即得偏移量。
• “容器宏container_of”：Linux 内核经典宏——已知某个成员指针和结构体类型，反求出整个结构体的指针，正是"成员地址 - 偏移量"。内核链表就是靠它从next指针反推到整个 PCB。
• 意义：只要知道结构体类型 + 内部任意一个成员的地址，就能访问该结构体的任意成员。

3.3 应用：大小端判断的原理

**你往整数里写一个 1，然后把这个整数当成char类型再取——因为你首先卡住的是这个变量本身的地址，它是 4 个字节中地址最小的那一个字节。

原理：

• 整数变量名标识的是地址最小的那个字节；
• 往整数写1，再把该地址强转成char*取第一个字节；
• 看这个字节里是1（低字节）还是0（高字节）→ 判断大小端。

易错点：(char*)&a取到的一定是最低地址那一字节；小端机上是数据的最低有效字节。

总结：

• 结论一：结构体变量的地址 = 其首成员（地址最小字节）的地址
• 结论二：结构体成员在内存中，从起始地址"由低向高"依次排布
  

三、重新设计链表：内嵌式（嵌入式）双链表

3.1 传统写法（把数据和指针放在同一个结点里）：

// 传统双链表结点structnode{structdatadata;// 数据structnode*next;// 前后指针structnode*prev;};

问题在于：指针字段指向的永远是"下一个完整的结点"，指针类型与业务结构体强绑定。若把指针类型写成struct task_struct *，那么这套增删查改只能给进程用。

3.2 内嵌式链表的设计思路

新设计：只定义两个指针的独立类型（先叫struct link）：

structlink{structlink*next;structlink*prev;};

再把这个小结构体"嵌"进业务结构体：

structtask_struct{// PCB// ... 一堆进程属性：PID、状态、优先级、上下文 ...structlinknode;// ← 只把"连接字段"嵌进来};

连接关系：

它的 next 指针并不是指向下一个进程，也就是并不指向下一个结构体——next 指向的是一个struct link（即下一个进程 PCB 内部的node）。

核心点：

1、这种双链表跟进程外部的属性无关。它的next直接指向下一个 PCB 结构体内部的node。
2、next指向的是"结构体内部的node"，不是下一个结构体本身。所以遍历时拿到的是成员地址，必须再用container_of换算回结构体地址。

3.3 如何从链表节点取回整个进程属性

问题：遍历链表时，只知道当前node的地址，怎么拿到这个进程的状态、优先级、上下文等其他属性呢？

“已经知道一个结构体内的一个成员变量的起始地址，就一定能通过这种做法，获得整个结构体本身的起始地址。结构体变量的地址一旦获取，结构体里的其他属性随意获取。”

答案：正是上面所学的container_of——容器宏！(上面的内容其实就是在为这里铺垫！)

遍历链表拿到 node 地址 │ ▼ container_of(node, struct task_struct, node) ← 成员地址 − 偏移量 │ ▼ 得到 task_struct 的起始地址 → 所有属性随意访问

“把零强转成task_struct，直接访问node得到偏移量，再拿next的值减去偏移量，结构体就得到了，那么进程所有属性我当然就全都知道了。”

3.4 为什么要这么干（本质：代码复用 / 扩展性）

引申：将来要管理所有打开的文件、所有硬件设备、所有内存块……我只需要在对应的描述结构体里添加一个struct link，那么一瞬间，管理进程的双链表算法就可以直接平移到对设备 / 文件 / 内存的管理上。

3.5 内核中的真实实现：list_head

内核真实结构：

//注意这是【类型】：描述一种数据结构长什么样，放在头文件里（list.h）structlist_head{structlist_head*next,*prev;};structtask_struct{// ...structlist_headtasks;// 所有进程的"全局双链表" （注意是全局的）// ...};

• list_head等价于上面我们手写的struct link；
• 内核用tasks字段把所有进程连接在一张全局双链表上。

上面是为了讲清楚原理才手搓struct link，真实内核叫list_head。

3.6 一个对象可同时属于多个数据结构

一个问题：一个进程既要被全局管理（在一张双链表里），又要被调度（又要进运行队列），那一个对象怎么可能既在链表里、又在队列里？

谁规定这一个进程的描述结构体里，只有一张链式结构？在 PCB 里嵌多个list_head节点，每个节点连接一张不同的数据结构！

structtask_struct{// ==========【描述信息：进程自身属性】==========pid_tpid;longstate;intprio;structmm_struct*mm;// ... 一大堆进程相关数据，这才是描述进程的信息// ==========【组织节点：只用来挂载，本身无业务含义】==========structlist_headtasks;// 挂在"全局进程双链表"上structlist_headrun_list;// 挂在"运行队列"上structlist_headchildren;// 挂在"子进程链"上structlist_headsibling;// 挂在"兄弟进程链"上// 甚至还有：挂在哈希表、红黑树上的节点……};#这些节点 不增加对象的业务属性。增加的只是 挂载能力:同一个进程对象，可以同时加入多个独立的数据结构。

“一个task_struct里包含了很多这种数据结构。一个节点既属于链表、又属于某个队列、甚至还属于某个哈希表或二叉树=。”

由此得到的结论：

• 进程可以自由迁移：需要调度时把它的run_list节点放进运行队列run_queue；阻塞时把它放进阻塞队列wait_queue；

• 迁移过程不影响它依旧留在全局双链表中；

• 因为节点类型统一（都是struct list_head），甚至不同类型（进程 / 文件）的结构体也能连在一起（虽无实际意义，但结构允许）。

• “这个结构它的耦合关系可以变得非常复杂。这就是内核当中设计数据结构的思路——节点内通过多个指针实现不同的数据结构。”

• 所以Linux 内核一个对象“身兼多职”（链表 / 队列 / 树 / 哈希），靠的就是在描述结构体内嵌多个list_head/rb_node/hlist_node。（有很多属性信息）

3.7 通用链表 / 树算法的伪代码

头插（示范）：往指定链表头插一个节点，只需传入"另一个对象的link地址"，与业务结构体无关：

// 伪代码：把某个对象的链表节点插入到链表头部voidinsert_after(structlist_head*head,structlist_head*new_node);

• 头插、尾插、增删查……全部只操作list_head类型；
• 创建进程时先malloc出一个task_struct，再把它内部的节点插入到全局链表：

structtask_struct*t=malloc(sizeof(structtask_struct));// 只传节点，不传整个 PCBlist_add(&t->tasks,&global_task_list);

四、Linux 进程调度：O(1) 调度算法

4.1 运行队列runqueue/rq

“Linux 内核当中，每一个 CPU 都包含一个叫做’运行队列’的东西。”

• 每个 CPU 都有一个独立的运行队列：2 个 CPU 就有 2 个，4 个 CPU 就有 4 个；
• 不同版本名字不同：2.6 内核里叫struct rq，也有版本改过名；
• 来看一看真实内核源码：

//老内核 runqueue，2.6.0 ~ 2.6.22structrunqueue{spinlock_tlock;// runqueue自旋锁，保护本CPU运行队列并发访问unsignedlongnr_running;// 本rq就绪可运行任务总数（TASK_RUNNING）#ifdefCONFIG_SMPunsignedlongcpu_load;// SMP下本CPU负载值，用于多核负载均衡#endifunsignedlonglongnr_switches;// 本CPU上下文切换总次数unsignedlongexpired_timestamp;// 上一次active/expired指针交换的时间戳unsignedlongnr_uninterruptible;// D状态（不可中断睡眠）任务计数unsignedlonglongtimestamp_last_tick;// 上一次调度tick时间task_t*curr;// 当前CPU正在运行的任务task_t*idle;// 本CPU的idle空闲进程，无任务时运行idlestructmm_struct*prev_mm;// 进程切换时保存旧进程的mm，优化地址空间切换// ========== active / expired + 双优先级数组（O(1)核心） ==========prio_array_t*active;// 活动数组指针：时间片未耗尽的就绪任务prio_array_t*expired;// 过期数组指针：时间片用完的就绪任务prio_array_tarrays[2];// 底层两个prio_array实例，active/expired来回切换指向intbest_expired_prio;// expired数组里最高优先级，用于调度优化atomic_tnr_iowait;// 等待IO的任务数量，负载均衡参考#ifdefCONFIG_SMPstructsched_domain*sd;// SMP调度域intactive_balance;intpush_cpu;task_t*migration_thread;// 任务迁移线程，跨CPU迁移任务structlist_headmigration_queue;// 待迁移任务链表#endif};

4.2 prio_array：140 个优先级队列

“在运行队列内部，它会包含一个具有 140 个元素的数组。”

structprio_array{unsignedintnr_active;// 队列内进程总数unsignedlongbitmap[BITMAP_SIZE];// 位图，BITMAP_SIZE = 5structlist_headqueue[MAX_PRIO];// MAX_PRIO = 140};

• queue[140]：140 个list_head，每个下标是一个先进先出（FIFO）队列；
• 数组下标0 ~ 139。

4.3先钻进 “一个队列” 内部，看怎么选进程

① 先看队列本体：queue [140]

runqueue里有一个struct list_head queue[140]：140 个下标对应 140 个优先级，每个下标挂一条 FIFO 双向链表，同优先级的进程链在同一条链上。

“数组当中 0 到 99 叫做实时优先级，我们今天是不关心的。”

一个铁律：优先级数值越低，越先被执行。

② 灵魂第一问：140 个队列，凭什么判断谁先执行？

答案是看优先级。而我们只关心 100~139，这 40 个梯度正好和 nice 对应。

映射公式（关键）：

普通优先级[60,99]+40→ 队列下标[100,139]60→10080→12099→139

由此得到三个结论：

1. 优先级数字，本质是数组下标。
2. 拿优先级选队列，本质是一个hash(哈希)过程；
3. 一旦确定是哪个队列，剩下的就是FIFO。

注意：真实内核static_prio = nice + 120（nice=0 → 120）。“80+nice 再 +40” 是教学简化，本质一致：普通进程只有 40 档(-20到20)，下标(140队列的下标！)即优先级。

③ 提前埋雷：如果只按优先级选会出 “饥饿”(不断有高优先级的进程插队)

“如果调度算法过度优先优先级高的进程，那么优先级低的进程将一直被插队，始终得不到 CPU 资源，导致进程饥饿。”

• 典型场景：所有进程都是 61，但不断有 60 的新进程来，61 永远跑不到。怎么解决后面会提出方案。

④ 先解决 “怎么选队列”：从 0 开始遍历

如果"从 100 下标开始到 139，局部性地遍历，只要第一个位置不为空，就找到了系统中优先级最高的一批进程(注意是一批进程，每个下标就是一个队列，队列里面可能有很多进程它们优先级一样所以都在同一个队列中)，然后从这一批里直接拿第一个。"

• 插入：优先级 61 → 映射到 101，直接索引到 101 号位，链入队尾；
• 选择：从低下标往高找，第一个非空队列就是全局最高优先级，队头取人。

查队列是 hash（O (1)）即查找该进程是哪个优先级要被分配到哪个下标(这个很快)，但是要找到那个下标还得遍历！！！！队列内取人是 FIFO（O (1)）。

⑤ 遍历O(n)还是很慢！→ 优化方案——位图 bitmap

“当大部分队列都为空时，还这样遍历效率就有点低了。如果转化成位图的形式，不用遍历，可以直接跳过空队列。”

unsignedlongbitmap[5];// 32位下：1个long = 32 bit

• 5 × 32 =160 ≥ 140，每个比特位代表一个队列：1 = 非空，0 = 空，多余 20 位不用；
• 一次可同时检测 32 位，“哪个队列非空” 的问题变成 “位图里哪个比特位为 1”，遍历从最多 40 次降到常数次。
• 顺带一个C语言的位运算技巧：x &= (x-1)消掉最低位的 1，循环计数即二进制中 1 的个数。

注意：64 位下 long 是 8 字节，bitmap[5]逻辑不变，覆盖更多位而已。

⑥ 再加一道保险：nr_active

如果整个队列一个进程都没有，遍历完一圈才发现没有，那不就是浪费时间吗？所以增加了一个nr_active表示的是 140 个优先级队列中进程的总数。

• nr_active：140 个队列里的进程总数，新增 +1、移除 −1；
• 调度顺序变为：先看nr_active > 0→ 再查位图定位非空队列 → 队头取进程。

4.4两个队列 + 指针交换，正面解决饥饿

上面解决的是进程如何选择与之匹配的优先级所在的队列问题(优化线性遍历低效的问题)，那么下面的两个队列+指针交换则是解决进程饥饿问题，其实在上面也提高了如果进程只按照优先级选队列(不断有高优先级的进程插入)就会导致进程饥饿问题，下面来看看如何解决：

① 先立公平目标

分时系统的特点是较为公平的方式，选择一个进程跑一段时间，让所有进程都能够得到 CPU 资源。Linux系统就是典型的分时操作系统。它如何保证公平呢？先来看下面这个问题：

问题再次摆上桌：所有进程都是 61，但不断有 60 的新进程来，61 怎么办？

② 结构升级：runqueue里有两个指针

它不仅仅包括一个 140 队列，而是包括两套完全一样的结构。

structrunqueue{structprio_arrayarrays[2];// 两套底层数组structprio_array*active;// 活跃队列指针structprio_array*expired;// 过期队列指针};

• active→ 活跃的 140 队列：本轮可以被调度的进程；
• expired→ 过期的 140 队列：本轮时间片用完、等待下一轮的进程。

注意：CPU 只查 active 指针指向的对象，不管 expired。

③ 活跃队列的执行逻辑：越调度越少

1. 按优先级高低顺序正常调度；
2. 一个进程时间片到了，不放回活跃队列，而是按优先级插入过期队列；
3. 活跃队列里的进程于是越调度越少。

注意：进过期队列 ≠ 进程结束，只是本轮不再参与调度；直接放回活跃队列，它会永远霸占 CPU。

④ 第二个灵魂拷问：当正执行80优先级级别的进程时，不断插进来79优先级的进程怎么办？

这时候必然不能再去执行 79 的进程，否则会导致饥饿，所以新进程应该插入到过期队列中！

• 新进程哪怕优先级再高，也一律进过期队列，必须等下一轮—— 这就保证老进程不会被无限插队。

⑤ 追问：那新插入的79优先级的进程什么时候才轮得到？

• 它在过期队列里 → 要执行它，就得执行过期队列 → 怎么执行过期队列？
• 答案是交换指针。底层只有两个数组、两个指针：

intarray[2];int*active=&a[0];int*expired=&a[1];// 等价于structprio_array_tarray[2];

• 活跃队列全部调度完，swap(active, expired)：过期队列变活跃队列，原活跃队列变过期队列；
• 新一轮开始，原来排队的 79 自然被调度到。

把active指针与expired指针交换，过期队列变成活跃队列，活跃队列变成过期队列 ——所以执行进程永远看到的是活跃进程！

宏观上每轮都必须把有限的一批进程全部跑完，新进程再高优先级也等下一轮 →局部按优先级，宏观不饥饿。

⑥nice值：改优先级的低成本办法

一个进程要改优先级，比如 80→81，不能直接改数字，还要把 PCB 从原队列摘除再插入新队列，成本很高。

方案：PCB 里单独放一个nice值，做延迟重算：

用户只改 nice 值（不摘链、不挪队列） ↓ 本轮仍按老优先级80调度 ↓ 时间片用完，放入过期队列时顺手重算： 新优先级=老优先级+nice ↓ 指针交换后，新优先级的进程被执行到

• nice为正 → 数字变大、优先级降低；nice为负 → 数字变小、优先级升高；
• 这也同时解释了三个伏笔：nice 为什么是−20 ~ 19、普通优先级为什么是40 档、为什么要有nice—— 都跟调度算法绑定；
• nice不是立即生效，下次进过期队列重算时才体现。

补充：

抢占（Preemption）

• 抢占：来了更高优先级进程，立即把当前进程剥下、换上新进程；
• 正常轮转：新进程进过期队列等下一轮；
• 立即抢占：新进程直接进运行队列，并让 CPU 立刻停下重新选择（机制与软中断有关，后面会说）。

实时进程 0~99

• 0~99 直接对应下标 0~99，不用 +40；
• 实时进程一旦选中必须执行完毕，不进过期队列、不做指针交换；
• 可以理解为分时调度的子集：分时逻辑去掉指针交换，就是实时逻辑。

注意：对于进程饥饿问题上面只是简化的讲法，并不是Linux内核真实的做法，有些出入，下面来看看Linux内核中是怎么做的：

140 个优先级队列、active/expired双队列、指针交换 —— 这些骨架没问题；真正兜住公平性的，是一个 10 秒量级的超时强制交换(超时机制)。新进程该进active还是进active，响应速度和不饿死，靠这个超时机制两头兜底。只要把进程调度的核心数据结构及其关系理清楚，调度的思路就清楚了——结构决定算法。

两个模型对照

Linux 内核源码应按版本阅读。本文以 Linux 2.6.22 的kernel/sched.c为参考；当前内核的调度器结构已经不同。想了解现代实现，可以另写一篇文章专门对照 CFS 与更新的调度实现，避免把历史算法和当前行为混在一起。

真实内核里发生了什么

时间线大概是这样：

1. 低优先级任务 L 时间片用完，下 expired，expired_timestamp从这一刻开始计时；
2. active 里高优先级的交互任务 I 用完时间片，默认可以重插回 active—— 只要没超阈值，允许它反复插队，这是为了交互跟手；
3. 等到 expired 里的等待时间摸到STARVATION_LIMIT × nr_running（约 10 秒量级）这条红线，I 再想重插 active 会被拒绝，直接被拽下 expired；
4. active 空了，交换指针，L 终于跑上 CPU。交换后 expired 清空，时间戳重置，下一轮重新开始。

三个容易被误解的点

1. 新进程不是被关进过期队列的。
新来的高优先级交互任务直接进 active，立刻就能跑 —— 不然桌面点一下卡三秒，没人受得了。

2. 防饥饿的开关不是 “排队”，是 “超时”。
内核给 expired 里的等待设了一个硬时间上限，到点强制交换，跟 active 里还剩多少任务无关。低优先级进程最坏等 “十几秒 × 进程数”，有界，不会无限饿死。

3. 被拽下来的不是新人，是赖着不走的。
超时后强制下放的，是那些时间片用完还反复重插 active 的任务，不是刚进门的。

五、总结：

本文通过 Linux 2.6.22 的 O(1) 调度器，串起了三个知识点：

1. task_struct可以嵌入不同链表节点，表示不同的内核关系；
2. container_of可以从成员节点地址找回外层对象；
3. O(1) 调度器通过每 CPU 运行队列、优先级数组和位图选择可运行任务，并用active/expired管理普通任务的调度轮转。

需要记住的是：这是理解 Linux 调度设计演进的历史案例。分析实际系统时，应先确定内核版本，再对照该版本源码确认字段和行为。