摘要本文围绕操作系统中的进程切换与 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 count10;它每调度一次count--当count减到0的时候这个时间就到了然后把进程从CPU剥离下来当下次调度时给这个进程重新赋予时间片去运行。时间片这个东西需要放到后面再讲我们现阶段只要理解它是一个计数器就行时间⽚当代计算机都是分时操作系统没有进程都有它合适的时间⽚(其实就是⼀个计数 器)。时间⽚到达进程就被操作系统从CPU中剥离下来。我们只需要知道一个进程在CPU下运行它的代码不会一次就跑完而是跑一段时间就切换走按照我们之前的理解进程切换本质就是把这个进程PCB放到调度队列的尾部。但CPU内部的寄存器只有一份但上下文数据可以有多份即每个进程都有各自的上下文当进程A暂时被切换下来的时候我们需要操作系统把进程A顺便把自己的上下文数据带走带走之后就是为了下次再调度进程A的时候能够恢复下次调度的时候按照之前的逻辑继续运行这种我们叫做进程切换。所以寄存器里保存的临时数据存放的就是进程的上下文数据。而这个上下文数据是在tss_struct任务状态段里面。Linux内核0.11代码tss_struct包含的就是当前进程的上下文数据一旦把进程切换走了就把进程PCB放到调度队列尾部从队列头部再拿一个把另一个进程的TSS字段再拿回来拿回来之后再继续运行。这个0.11是老内核而新内核是把当前进程的上下文数据它没把上下文数据放到tss_struct内部保存了。CPU上下⽂切换其实际含义是任务切换, 或者CPU寄存器切换。当多任务内核决定运⾏另外的任务时,它保存正在运⾏任务的当前状态, 也就是CPU寄存器中的全部内容。这些内容被保存在任务⾃⼰的堆栈中, ⼊栈⼯作完成后就把下⼀个将要运⾏的任务的当前状况从该任务的栈中重新装⼊CPU寄存器, 并开始下⼀个任务的运⾏,这⼀过程就是context switch。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下标如果对应下标有进程就执行该进程这个时候拿到的优先级就是最高的就是按优先级去调度的但是有一个问题如果所有进程优先级都是99PRI99那么如果从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 O1调度算法因为在当前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定义两个指针activeexpiredactive指针称为活跃队列指针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个位置能更加适应后面的环境操作系统分为分时操作系统WindowsLinux实时操作系统。分时操作系统强调系统调用调用任务时要公平公正实时操作系统更加强调实时性分时操作系统是基于时间片轮转调度的而实时操作系统是来一个进程必须先确定优先级执行优先级最高的任务而且必须把优先级最高的任务执行完才能执行下一个任务。②而Linux操作系统支持实时操作系统的功能但是只是因为在编译内核时已经把Linux操作系统选择成了分时操作系统因为它适合互联网领域应用。但在工业领域如汽车辅助驾驶系统它可能采用实时操作系统而实时操作系统的优先级范围为[0,99]进程有基于时间片的公平调度的分时进程也有基于优先级的实时运行但是操作系统在诞生的时候大部分是实时操作系统分时操作系统反而更难因为它要有复杂的调度回到最开始的图为什么Linux没有就绪状态是因为Linux有过期队列和运行队列新建的进程在过期队列里也要被运行的因此没必要多弄一个就绪状态只要处于被调度/随时准备好的状态叫做R状态不是已经在CPU上跑的状态才算R状态因为在单CPU里R有多个进程的大部分已经讲得差不多了但是进程的部分还没讲完后面会讲到进程的控制在这中间还需要讲一下其他的东西下讲再见