Linux--进程的调度

1.进程切换

CPU上下⽂切换：其实际含义是任务切换, 或者CPU寄存器切换。当多任务内核决定运⾏另外的任务时, 它保存正在运⾏任务的当前状态, 也就是CPU寄存器中的全部内容。这些内容被保存在任务⾃⼰的堆栈中, ⼊栈⼯作完成后就把下⼀个将要运⾏的任务的当前状况从该任务的栈中重新装⼊CPU寄存器,并开始下⼀个任务的运⾏, 这⼀过程就是context switch。

时间⽚：当代计算机都是分时操作系统，没有进程都有它合适的时间⽚(其实就是⼀个计数

器)。时间⽚到达，进程就被操作系统从CPU中剥离下来。

2.Linux内核进程O(1)调度队列

 在前面我们说过进程的状态，在运行状态的进行，是CPU当前要运行的队列，那么CPU要管理它们，总要有个先后顺序吧，因为CPU只有一套寄存器，不能同时运行多个进程，于是就有了运行队列（runqueue），这是一个结构体，专门用于管理运行队列的进程。

⼀个CPU拥有⼀个runqueue，如果有多个CPU就要考虑进程个数的负载均衡问题。

2.1task_struct与runqueue的关系

在 Linux 内核里，task_struct和runqueue是进程调度机制中的两个关键数据结构，它们关系紧密，下面为你详细介绍。

2.1.1 核心概念

• task_struct：这是内核用来表示进程的核心数据结构，也被叫做 "进程描述符"。它把进程的所有信息都整合在一起，像进程状态、优先级、资源分配情况、打开的文件等，都包含其中。
• runqueue：也就是运行队列，其作用是管理系统中处于可运行状态（TASK_RUNNING）的进程。每个 CPU 核心都有属于自己的runqueue，这样可以实现并行调度。

2.1.2 二者的关联

• 进程状态的纽带：当进程处于可运行状态时，它会被加入到runqueue中；而当进程处于阻塞状态（比如等待 I/O）时，就会从runqueue中移除。
• 调度的实现：调度器会从runqueue里挑选出一个进程，让它在对应的 CPU 上运行。挑选进程时依据的是调度算法，像 CFS（完全公平调度）算法，此时task_struct中的se（调度实体）字段就会发挥作用。
• 负载均衡：内核会在不同 CPU 的runqueue之间进行进程迁移，以此来实现负载均衡，task_struct中的相关指针能帮助定位进程所在的队列。

2.1.3 数据结构层面的联系

下面是用伪代码呈现的它们之间的关键联系：

struct task_struct {// 进程状态volatile long state;        // 例如 TASK_RUNNING// 调度相关struct sched_entity se;     // 调度实体，用于CFS调度器struct list_head run_list;  // 连接到runqueue的链表struct rq *rq;              // 指向所在runqueue的指针int on_rq;                  // 标记进程是否在runqueue中
};struct rq {// 运行队列中的进程struct cfs_rq cfs;          // CFS调度器的运行队列struct list_head run_list;  // 可运行进程的链表unsigned int nr_running;    // 可运行进程的数量// 当前运行的进程struct task_struct *curr;   // 当前正在运行的进程
};

2.1.4 工作流程示例

下面以进程调度为例，说明二者的协作流程：

 

1. 当进程被创建或者从阻塞状态变为可运行状态时，内核会调用enqueue_task函数，把该进程添加到runqueue中。
2. 调度器通过pick_next_task函数从runqueue里选择一个最优的进程。
3. 进程执行过程中，如果时间片用完或者主动放弃 CPU，就会调用dequeue_task函数，将进程从runqueue中移除。
4. 整个过程中，进程的task_struct会一直维护自身在runqueue中的状态和位置。

2.1.5 总结

task_struct代表着单个进程，而runqueue则负责管理多个可运行的进程，它们共同构成了 Linux 内核调度系统的基础。通过这种进程状态管理和队列操作机制，Linux 内核能够高效地实现多任务处理。

2.2runqueue的运行原理

这里我们可以简单看看runqueue结构体里的变量。

2.2.1活动队列

时间⽚还没有结束的所有进程都按照优先级放在该队列

nr_active: 总共有多少个运⾏状态的进程

queue[140]: ⼀个元素就是⼀个进程队列，相同优先级的进程按照FIFO规则进⾏排队调度,所以 数组下标就是优先级 ！

从该结构中，选择⼀个最合适的进程，过程是怎么的呢？

1. 从0下表开始遍历queue[140]

2. 找到第⼀个⾮空队列，该队列必定为优先级最⾼的队列

3. 拿到选中队列的第⼀个进程，开始运⾏，调度完成！

4. 遍历queue[140]时间复杂度是常数！但还是太低效了！

于是Linux用了一个非常巧妙的方法：

bitmap[5]:⼀共140个优先级，⼀共140个进程队列，为了提⾼查找⾮空队列的效率，就可以⽤5*32个⽐特位表⽰队列是否为空，这样，便可以大大提⾼查找效率！

2.2.2过期队列

过期队列和活动队列结构⼀模⼀样

过期队列上放置的进程，都是时间⽚耗尽的进程

当活动队列上的进程都被处理完毕之后，对过期队列的进程进⾏时间⽚重新计算

2.2.3活跃进程和过期进程的关系

在上图中我们可以看到两块被圈出来的空间，同样的几个变量为什么要有两套呢？

原因就是，当我们CPU调度的时候是在活跃进程表中一一调度，那么当调度完了进程的task_struct要去哪呢？答案是进入过期进程表，这样当我们活跃进场调度完了之后，进程的顺序还是没有乱，我们再把活跃进程列表和过期进程列表swap一下。

2.2.4 active指针和expired指针

active指针永远指向活动队列

expired指针永远指向过期队列

可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间⽚到期时⼀直

都存在的。

没关系，在合适的时候，只要能够交换active指针和expired指针的内容，就相当于有具有了⼀批

新的活动进程！

3.总结

在系统当中查找⼀个最合适调度的进程的时间复杂度是⼀个常数，不随着进程增多⽽导致时间成

本增加，我们称之为进程调度O(1)算法！