摘要：本文围绕操作系统中的进程切换与 Linux 进程调度展开讲解。第一部分从 CPU 寄存器与上下文数据入手，说明进程切换的本质是保存并恢复寄存器中的临时数据，并介绍了时间片、分时系统与并发运行等核心概念。第二部分深入剖析 Linux 的进程调度机制，重点讲解 O(1) 调度算法中 queue[140] 优先级队列、bitmap 位图、活跃队列与过期队列的配合原理，并进一步说明调度器从 O(1) 演进到 CFS（完全公平调度器）后的核心变化，最后解释了 Linux 为何没有就绪状态以及预留 100 个优先级位置的原因。

目录

1.什么是进程切换

2.Linux的进程调度

---

1.什么是进程切换

当进程在CPU上进行运行的时候，CPU内会有大量的寄存器。如：我们可以问AI大模型：罗列一下，x86场景的寄存器清单。

一般我们学过计算机组成原理的时候学过，如：EA、EX等。在CPU内包含很多的寄存器，基本上是有几十个寄存器的。

在我们之前学习进程的属性的时候，我们曾经提到过：进程属性里面，一个进程在进行调度运行的时候，每一个进程在执行时，它都会在CPU寄存器放一个临时数据，当进程切换时，它一定要把临时数据带走，而这个临时数据，我们称之为：上下文数据。

CPU内，寄存器，就是一套存储空间，而在CPU内寄存器只有一套，寄存器的硬件属于CPU本身，但是寄存器内部的数据可以有很多！

就相当于当前我们正在调度时，寄存器本身的硬件只有一份，但是一个进程在运行时，它会在CPU内就会形成很多的上下文数据，包括现在执行到的哪行代码，返回值，传参等。所以说进程所对应的数据都会放在CPU所对应的寄存器里，这样的话就可以加速CPU的运行了，它访问数据时不需要访存，而直接找CPU要即可。

如：函数的返回值问题：函数的返回值，本质就是函数内部的变量，而函数内的变量，不是具有临时性吗？不是只在函数内部有效吗？不是有作用域吗？返回值怎么会被外部的函数获得？

我们都知道：函数返回的是一份拷贝，但是拷贝是什么呢？

数字是返回到寄存器中的！函数调用完了后会把返回值放到寄存器里，然后我们用一个变量接收它，就会把这个返回值写回到内存里，此时你的临时变量就拿到这个值了。也就是说在CPU的寄存器里会保存很多临时数据，函数返回值是一种代表！

当前（操作）系统，都是分时系统。每一个进程都有自己的“时间片”。

当前的进程，操作系统为了保证这个进程要运行，便把这个进程放到CPU去执行，但是进程执行一段时间后，如：1ms，如果这个进程执行完成需要1000ms，但当前进程放在CPU跑1ms不能让它再跑了，就把这个进程切换到其他地方，不让这个进程运行，让其他的进程继续运行。让这个进程执行1ms指的是：当前进程的“时间片”！也就是说进程A要跑完需要1000ms，它的时间片是1ms，因此如果进程A要跑完要进行1000次切换调度，因此，我们把基于“时间片”的操作系统称为：分时系统。

因此，因为有“时间片”，因为有分时操作系统，所以它能做到以较为公平的方式来进行进程调度。这种让进程调度的系统，在单CPU下，我们称该进程并发运行。每个进程都要有时间片，时间片是操作系统给每个进程分配的实际是一个计数器。操作系统每次调度某个进程时，会检测它的时间片，其实它的时间片就是一个整数，比如：int count=10;它每调度一次，count--，当count减到0的时候这个时间就到了，然后把进程从CPU剥离下来，当下次调度时给这个进程重新赋予时间片去运行。

时间片这个东西需要放到后面再讲，我们现阶段只要理解它是一个计数器就行！时间⽚：当代计算机都是分时操作系统，没有进程都有它合适的时间⽚(其实就是⼀个计数 器)。时间⽚到达，进程就被操作系统从CPU中剥离下来。

我们只需要知道：一个进程在CPU下运行，它的代码不会一次就跑完，而是跑一段时间就切换走，按照我们之前的理解，进程切换本质就是把这个进程PCB放到调度队列的尾部。但CPU内部的寄存器只有一份，但上下文数据可以有多份，即每个进程都有各自的上下文，当进程A暂时被切换下来的时候，我们需要操作系统把进程A顺便把自己的上下文数据带走，带走之后就是为了下次再调度进程A的时候能够恢复，下次调度的时候按照之前的逻辑继续运行，这种我们叫做：进程切换。

所以，寄存器里保存的临时数据存放的就是进程的上下文数据。而这个上下文数据是在tss_struct（任务状态段）里面。

Linux内核0.11代码：

tss_struct包含的就是当前进程的上下文数据，一旦把进程切换走了，就把进程PCB放到调度队列尾部，从队列头部再拿一个，把另一个进程的TSS字段再拿回来，拿回来之后再继续运行。

这个0.11是老内核，而新内核是把当前进程的上下文数据，它没把上下文数据放到tss_struct内部保存了。

2.Linux的进程调度

那么问题来了，Linux系统是如何进行进程调度的呢？

Linux的进程调度是：状态+优先级。

Linux2.6内核当中的进程的运行队列：

一个CPU，一个运行队列：

它的运行队列我们叫做runqueue，在整个runqueue中存在一个queue[140]：

这个queue[140]它的类型实际上是：struct list_head（链表头结点）即struct task_struct *。所以说queue是一个指针数组，而这个指针数组会指向一个具有140个元素所对应的数组：

为什么是140呢？

我们知道140的下标范围为[0,139]，其中[0,99]下标在上面，[100,139]在下面：

[0,99]：我们不用管，我们当前只管[100,139]，我们发现[100,139]一共有40个，之前进程优先级里我们讲过优先级有40个级别，即一共可以调整40个nice值，对应Linux的优先级有40个。

优先级范围为[60,99]，因为nice为[-20,19]本质就是为了让优先级范围为[60,99]，最终[60,99]加上40就转化成[100,139]即转化成下标了！

因此即每个元素可以对应一个链表，相同优先级的进程PCB可以链入到该位置：

也就是说，如果优先级为60的进程，它的PCB会链入到下标为100的位置。

所以未来选择一个进程调度，只需要在运行队列里找到对应的数组下标，也就是说CPU在调度时，它不关注对应的优先级了，它直接从queue[140]里的[100,139]从100找到139下标，如果对应下标有进程，就执行该进程，这个时候拿到的优先级就是最高的，就是按优先级去调度的！

但是有一个问题，如果所有进程优先级都是99（PRI=99），那么如果从100这个下标找到最后一个下标，这样做效率太慢了，因此，runqueue还提供了一个bitmap[5]：

bitmap是一个int类型的数组，含有5个元素。

为什么是5呢？

因为int占32个比特位，如果乘以5即：32*5 = 160个比特位，但是如果小于5，比如4，就为128个比特位，<140个，因此 不够。因为160个比特位我们称为：位图！

位图就是一堆一堆的0和1，假设为char类型，那么就有8个比特位，假设为0000 0000，其中比特位的位置表示：数组中第几个队列！（不考虑[0,99]）也就是说我们把queue中的[100,139]看做bitmap中40个比特位，每个比特位（除了溢出的部分）对应queue中的一个优先级，如果所有的进程优先级都一样，也就是说这40个比特位只有一个队列为1，这就是我们之前所说的FIFO调度算法（先进先出）。

因此，比特位的内容：表明该队列是否为空！如果某个比特位为1，代表这个队列（优先级）有进程，因此要调度这个队列的进程。将来CPU想要调度进程，只要查这个位图，根据位图当中的位置，找到queue的数组下标，得到进程，因此用位图的操作来替换遍历数组的操作，一定程度上提高了效率。（从右向左遍历，因为最右侧比特位最低）

因此，我们把这种调度算法叫做Linux O（1）调度算法，因为在当前CPU里，找到一个进程的时间复杂度是常数。

nr_active存储的是当前有多少个进程，即存储当前含有的进程总数。

我们仔细观察一下该图：

为啥会有两套nr_active,bitmap[5],queue[140]呢？

我们可以把一个nr_active,一个bitmap[5],一个queue[140]统一包装成struct q，其中struct q包含这三个东西，也就是说蓝色框内实际上是一个结构体。而在runqueue里，这两个统一会被包装成struct q array[2]，也就是说一个struct q对应一个array里面的元素，然后再在runqueue定义两个指针：active，expired：

active指针称为活跃队列指针，expired称为过期队列指针，这两个指针类型为struct q *，也就是说active指针指向struct q结构体(array[0])，expired指向的是过期下标(array[1])。

原则：

①CPU调度的时候，不是看队列，而是直接从active指针，找到对应的queue[140]。

②新增进程或者时间片到了的进程，被从CPU剥离下来，被剥离下来的进程，只能重新入队列，只能够入过期队列。

也就是说：一个进程被调度之后，先把进程从活跃队列里拿下来，等时间片用完（进程被调度一定时间后）时，会把这个进程放到过期队列当中。

这样带来的结果是CPU会把当前调度队列里的所有进程全部调度完，所有进程都会跑到过期队列当中。此时活跃队列就为空了。当操作系统检测到nr_active为0了，即活跃队列没有进程了，那么：swap(&active,&expired);交换两个指针的内容，也就是说active指向了之前的过期队列（array[1]），expired指向了之前的活跃队列(array[0])。CPU就会继续调度active，周而复始！

如果我们在已经运行的进程里调整优先级，那么我们不仅需要修改进程PCB，还需要把进程从调度队列里迁移到合适的优先级队列里面。但是实际上，如果当时该进程还在活跃队列里，其优先级并不会改变，等到进程被调度完后，迁移到过期队列时，重新计算优先级，插入到过期队列对应位置。这就是为什么要有nice值的原因，如果我们直接改优先级，那么必须得在队列中重新调整位置（活跃队列），这样操作就会多了两次操作（先拿出进程PCB，再找到新位置插入），有nice就能提高效率！

这种调度算法会存在进程饥饿问题吗？

不会！如果一直频繁的进行改变进程优先级，它会在把所有进程（包含优先级最低）都全部运行完再切换为下一个，即便过期队列里的优先级最高，也要等到活跃队列里最低优先级的进程执行完它才能执行！局部上，有调度的先后问题（根据优先级调度），但是整体上，并不会造成进程饥饿的问题。

因此用两个队列的好处就在于这！

因此，进程有新建状态，新建状态在过期队列里新建的进程，只要没调度到这个新建的进程，此时就处于新建状态，但是在Linux里不用区分新建状态，因为全部都叫做r状态（运行状态）。

实际上的Linux内核真的是这样吗？

如果我们搜索struct runqueue大概率是这样的结果：

因为在Linux内核里，runqueue的实际名称为rq，因此我们需要搜索：

struct rq {

才能找到：

struct rq {
	/* runqueue lock: */
	spinlock_t lock;
/*
 * nr_running and cpu_load should be in the same cacheline because
 * remote CPUs use both these fields when doing load calculation.
 */
unsigned long nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
#ifdef CONFIG_NO_HZ
unsigned long last_tick_seen;
unsigned char in_nohz_recently;
#endif
/* capture load from all tasks on this cpu: */
struct load_weight load;
unsigned long nr_load_updates;
u64 nr_switches;
u64 nr_migrations_in;
struct cfs_rq cfs;
struct rt_rq rt;
#ifdef CONFIG_FAIR_GROUP_SCHED
/* list of leaf cfs_rq on this cpu: */
struct list_head leaf_cfs_rq_list;
#endif
#ifdef CONFIG_RT_GROUP_SCHED
struct list_head leaf_rt_rq_list;
#endif
/*
 * This is part of a global counter where only the total sum
 * over all CPUs matters. A task can increase this counter on
 * one CPU and if it got migrated afterwards it may decrease
 * it on another CPU. Always updated under the runqueue lock:
 */
unsigned long nr_uninterruptible;

struct task_struct *curr, *idle;
unsigned long next_balance;
struct mm_struct *prev_mm;

u64 clock;

atomic_t nr_iowait;
#ifdef CONFIG_SMP
struct root_domain *rd;
struct sched_domain *sd;
unsigned char idle_at_tick;
/* For active balancing */
int post_schedule;
int active_balance;
int push_cpu;
/* cpu of this runqueue: */
int cpu;
int online;

unsigned long avg_load_per_task;

struct task_struct *migration_thread;
struct list_head migration_queue;

u64 rt_avg;
u64 age_stamp;
u64 idle_stamp;
u64 avg_idle;
#endif
/* calc_load related fields */
unsigned long calc_load_update;
long calc_load_active;
#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
int hrtick_csd_pending;
struct call_single_data hrtick_csd;
#endif
struct hrtimer hrtick_timer;
#endif
#ifdef CONFIG_SCHEDSTATS
/* latency stats /
struct sched_info rq_sched_info;
unsigned long long rq_cpu_time;
/ could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
/* sys_sched_yield() stats */
unsigned int yld_count;

/* schedule() stats */
unsigned int sched_switch;
unsigned int sched_count;
unsigned int sched_goidle;

/* try_to_wake_up() stats */
unsigned int ttwu_count;
unsigned int ttwu_local;

/* BKL stats */
unsigned int bkl_count;
#endif
};

其中在查到调度队列之前有一句这样的话：

翻译过来是：

这是主要的、每个 CPU 核心独立拥有的运行队列（runqueue）数据结构。
加锁规则：那些需要同时锁定多个运行队列的地方（例如负载均衡或线程迁移代码），必须按照 &runqueue 地址的升序顺序来获取锁（以避免死锁）。

也就是说：一个CPU一个运行队列。

nr_switches：记录上下文切换计数（该CPU发生调度切换的总次数）。

但是我们并不会看到类似之前的queue[140]和nr_active这种，这是因为这是Linux 调度器从 O(1) 演进到 CFS (完全公平调度器) 后的核心变化。

你提到的 queue[140] 和 nr_active，其实是 O(1) 调度器的设计。在 CFS 中，它们并没有消失，而是以更精细的方式，被重新组织到了不同的子结构中。

为什么 CFS 不再需要 queue[140]？

O(1) 调度器依赖固定的 140 个优先级队列，每次调度需要遍历这些队列以找到最高优先级的任务。而 CFS 的核心思想是完全公平，它不再依赖固定的时间片和优先级数组，而是引入 vruntime（虚拟运行时间） 的概念。

• 调度依据变了：CFS 不再关心任务的优先级队列位置，而是选择 vruntime 最小的任务来运行，以确保公平。

• 数据结构变了：为了高效地找到 vruntime 最小的任务，CFS 使用了红黑树（rbtree） 来组织任务。红黑树是一种自平衡二叉搜索树，能确保在 O(log N) 时间内完成查找、插入和删除操作，非常适合管理大量动态变化的进程。

queue[140] 和 nr_active 去哪了？

它们没有消失，而是被“拆分”并“下放”到了 CFS 和 RT 两个调度器类各自的运行队列中。

• queue[140] (优先级队列):

  • RT (实时) 任务: struct rt_rq 内部依然使用类似 queue[140] 的优先级数组来管理实时任务。

  • CFS (普通) 任务: 其运行队列 struct cfs_rq 则使用我们上面提到的红黑树来管理所有普通任务。

• nr_active (活跃进程总数):

  • 这个统计信息也被分散到了不同层级。struct rq 中的 nr_running 字段，就记录了该 CPU 上所有调度类的进程总数。

如果各位能获取到Linux-2.6.18这些内核源码，能看到这个东西。以下是Linux-2.6.18部分源码：

不过我们主要不是看这些代码是否存在，我们真正要看的是理解这个代码对应的思想即可。

struct q就对应了struct prio_array，我们转到定义有：

其中的nr_active就是我们刚刚讲到的nr_active表示我们有多少个进程在运行队列里面，而DECLARE_BITMAP这个是个宏bitmap也是宏，相当于我们之前的bitmap，是宏替换出来的；struct list_head queue就算刚刚的queue[140]，也就是说140个元素的数组里都是双链表，双链表存储了每个优先级（除了[0,99]）对应的进程。

因此一个进程的PCB可以既属于全局双链表，又属于运行队列，因为无非就算让PCB多定义一个struct list_head即可。对应的宏：

回到最后一个问题，为什么为140个元素的数组呢？即[0,99]是给谁的？

因为操作系统不止在互联网公司被采纳，操作系统本身也可能在工业领域使用，如：操作系统被汽车的车载系统做为系统，因为Linux是开源的，一旦有内存调度、文件管理这类的需求时，人们首先想到的是拿免费的，开源的操作系统来直接纳入自己对应的生态当中。

所以结论：

①操作系统，尤其是Linux操作系统不仅仅在互联网使用，在工业场景中也会被使用，Linux发展了很久，基本上都会使用Linux操作系统，所以预留100个位置能更加适应后面的环境！

操作系统分为：分时操作系统（Windows，Linux），实时操作系统。

分时操作系统强调：系统调用调用任务时要公平公正，实时操作系统更加强调实时性；分时操作系统是基于时间片轮转调度的，而实时操作系统是来一个进程，必须先确定优先级，执行优先级最高的任务，而且必须把优先级最高的任务执行完才能执行下一个任务。

②而Linux操作系统支持实时操作系统的功能！但是只是因为在编译内核时已经把Linux操作系统选择成了分时操作系统，因为它适合互联网领域应用。但在工业领域，如：汽车辅助驾驶系统，它可能采用实时操作系统，而实时操作系统的优先级范围为[0,99]！！！

进程有基于时间片的公平调度的分时进程，也有基于优先级的实时运行，但是操作系统在诞生的时候大部分是实时操作系统，分时操作系统反而更难，因为它要有复杂的调度！

回到最开始的图：

为什么Linux没有就绪状态？

是因为Linux有过期队列和运行队列，新建的进程在过期队列里，也要被运行的，因此，没必要多弄一个就绪状态，只要处于被调度/随时准备好的状态叫做R状态，不是已经在CPU上跑的状态才算R状态，因为在单CPU里，R有多个！

进程的大部分已经讲得差不多了，但是进程的部分还没讲完，后面会讲到进程的控制，在这中间还需要讲一下其他的东西，下讲再见！