【把Linux“聊”明白】进程调度三要素：优先级、切换与O(1)算法

优先级、切换与O(1)调度算法

友情专栏：【把Linux“聊”明白】

前言

当CPU资源有限而进程众多时，操作系统如何决定谁先执行？这就是进程调度的关键。本文将简明解析进程调度的三大核心：优先级决定顺序，进程切换实现并发，O(1)算法保证效率。

一、进程优先级

1-1 基本概念

• cpu资源分配的先后顺序，就是指进程的优先权（priority）。
• 优先权高的进程有优先执行权利。配置进程优先权对多任务环境的linux很有用，可以改善系统性能。
• 还可以把进程运行到指定的CPU上，这样一来，把不重要的进程安排到某个CPU，可以大大改善系统整体性能。

优先级 vs 权限

优先级的前提是，能得到资源，只是时间先后的问题； 权限却是指的能否得到资源！！！

对于优先级的说明：

优先级也是一种数字； 值越低，优先级越高，反正，优先级越低； 由于我们现在的操作系统大多是基于时间片的分时操作系统，考虑公平性，优先级可能改变，但是变化幅度不能太大。

1-2 查看系统进程

在Linux系统中，用ps -l 命令会输出以下几个内容：

在这里插入图片描述

可见：

UID：代表执行者的身份，即（用户id）user id PID：代表这个进程的代号 PPID：代表这个进程是由哪个进程发展衍生而来的，亦即父进程的代号 PRI：代表这个进程可被执行的优先级，其值越小越早被执行 NI：代表这个进程的nice值

看到这里，我们先跳出去一下，那么系统是怎么知道我访问文件的时候，是拥有者、所属组，还是other？？

在Linux中，访问任何资源，都是进程访问，进程就代表用户，上图中的UID就是对应的用户id； 每个进程是由哪个用户执行的，此进程就会有用户的uid，然后访问文件时，进程用自己的UID去匹配文件的权限设置。 我们也可以使用ls -ln来查看文件对应用户的uid。

在这里插入图片描述

1-3 PRI 与 NI

对于进程的优先级，我们关注这两者：

在这里插入图片描述

PRI：进程的优先级，或者通俗点说就是程序被CPU执行的先后顺序，此值越小进程的优先级别越高； NI：nice值，其表示进程可被执行的优先级的修正数值； 即：PRI(真实的优先级)=PRI(默认优先级)+nice 我们知道，PRI值越小越快被执行，那么加入nice值后，当nice值为负值的时候，那么该程序将会优先级值将变小，即其优先级会变高，则其越快被执行。 所以，调整进程优先级，在Linux下，就是调整进程nice值。

注：

大多数 Linux 系统中，默认 PRI 值是 80。 nice其取值范围是-20至19，一共40个级别。

所以可知，Linux进程的优先级范围是：[60,99]。

1-4 调整Nice值命令 及 验证nice值范围

调整Nice值有命令，也有系统调用，我们这里只了解命令，在绝大多数情况下，我们不需要手动调整进程的优先级，万一由于优先级设置不合理，就会导致低优先级进程长时间或永久无法获得所需的 CPU 时间片和其他系统资源，导致进程饥饿 。

启动时设置优先级 - nice 命令 基本语法：

nice -n [NICE值] [命令]

使用示例：

# 此时真实优先级是 90
nice -n 10 ./peocess

修改运行中进程的优先级 - renice命令 基本语法：

renice -n [新NICE值] [选项] [PID|用户|进程组]

使用示例：

# 修改指定PID进程的优先级
renice -n 10 -p 1234

# 修改用户的所有进程优先级
renice -n 5 -u username

用top命令更改已存在进程的nice：

进入top后按“r”‒>输入进程PID‒>输入nice值

验证nice值范围 nice最大值： 先来个死循环程序，可以使用命令pa -al来查看: 此时PRI为80，NI为0；

在这里插入图片描述

即nice最大值为19；

nice最小值：

在这里插入图片描述

即nice最小值为-20； 在这里我们还要注意renice是将NI值设置为XX，而不是在上次的基础上±的。

1-5 竞争、独立、并行、并发

• 竞争性：系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级；
• 独立性：多进程运行，需要独享各种资源，多进程运行期间互不干扰；
• 并行：多个进程在多个CPU或者多核单CPU下分别，同时进行运行，这称之为并行；
• 并发：多个进程在一个CPU下采用进程切换的方式，在一段时间之内，让多个进程都得以推进，称之为并发。

并发与并行理解：

在这里插入图片描述

并发是两个队列交替使用一台咖啡机，并行是两个队列同时使用两台咖啡机

二、进程切换

并发是多个进程在一个CPU下采用进程切换的方式实现的，那什么是进程切换呢？

我们先来说说死循环进程如何运行？

首先，一旦一个进程占有CPU，会把自己的代码跑完吗？？ 答案是不会，因为有时间片的存在。 时间片：当代计算机都是分时操作系统，每个进程都有它合适的时间片(其实就是一个计数器)。时间片到达，进程就被操作系统从CPU中剥离下来。 所以，我们以前的死循环进程，才不是一直占有CPU、一直卡死系统！

我们再来简单的说说CPU、寄存器：

CPU是什么？ CPU（中央处理器）是计算机的"大脑"，负责执行指令和处理数据，控制整个计算机系统的运行。

寄存器是什么？ 寄存器是CPU内部的超小型高速存储单元，就像CPU的"工作台"，用于临时存放正在处理的指令和数据。

两者关系 寄存器是CPU的一部分：寄存器直接集成在CPU芯片上，是CPU的内部组件 CPU包含寄存器：CPU由多个部件组成，其中寄存器是关键组成部分 简单比喻：如果把CPU比作一个工厂，那么寄存器就是工厂里工人手边的工作台，用来临时放置正在加工的零件寄存器的特点 寄存器的特点 速度极快：响应时间约1纳秒，与CPU处理速度匹配 容量很小：通常只有几个到几十个字节 作用关键：暂存指令、数据和地址，让CPU能快速获取处理信息

由此，我们可以说明：

进程运行的临时数据保存在CPU寄存器中, 这些数据构成了进程上下文的重要组成部分，当然，上下文还包括内存状态、文件状态等系统信息，我们现在只考虑CPU寄存器中的内容。

进程切换，我们要先将正在运行的进程的上下文数据 — 寄存器中的临时数据保存起来，使得下次重新调度的时候，可以正常恢复。

保存上下文数据：即CPU内寄存器里面的内容，保存起来； 恢复上下文数据：即保存起来的内容，恢复到CPU内寄存器； 其实进程切换，最核心的，就是保存和恢复进程的硬件上下文数据，即CPU内寄存器的内容 ---- CPU上下文切换。

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

在这里插入图片描述

这里辨析一个概念：

cpu内的寄存器只有一份，但上下文可以有多份，分别对应不同的进程，要理清楚。

所以，当前进程要把自己的进程硬件上下文数据，保存起来，保存到哪里了呢? ? ? task_struct（PCB）中，我们可以来看看早期 Linux 版本中上下文数据保存的地方，早期使用硬件任务切换的版本，后来改为软件上下文切换。 参考一下Linux内核0.11代码，保存在task_struct中的TSS（任务状态段）。

在这里插入图片描述

三、Linux2.6内核进程O(1)调度队列

这里，我们认为一个CPU一个运行队列。

下面是是Linux2.6内核中运行队列的数据结构，可以简单看一下：

// kernel/sched.c
struct rq {
    /* 基本运行队列信息 */
    unsigned long nr_running;
    unsigned long cpu_load;
    unsigned long nr_switches;
    unsigned long nr_uninterruptible;
    
    /* 时间相关 */
    u64 expired_timestamp;
    unsigned long long timestamp_last_tick;
    
    /* 进程指针 */
    struct task_struct *curr, *idle;
    struct mm_struct *prev_mm;
    
    /* 优先级数组 */
    struct prio_array *active, *expired;
    struct prio_array arrays[2];
    int best_expired_prio;
    
    /* SMP 相关 */
#ifdef CONFIG_SMP
    unsigned long nr_iowait;
    int active_balance;
    struct task_struct *migration_thread;
    struct list_head migration_queue;
    struct sched_domain *sd;
#endif
};

我们主要看优先级数组结构

// kernel/sched.c
struct prio_array {
    unsigned int nr_active;
    unsigned long bitmap[5];      //这里本是宏定义，为了方便，就直接写数字了（32位平台）
    struct list_head queue[140];	 //宏定义，为了方便，就直接写数字了
};

解释：

nr_active：活跃进程数。 bitmap[5]：优先级位图，用于快速查找最高优先级进程。 queue[140]：140个优先级的进程队列。

我们详细来看一下：

在这里插入图片描述

由于现在我们的操作系统大多都是分时操作系统，所以我们主要关注分时系统（后40个队列）。 即queue中的100 ~ 139(共40个)，看到40，我们会想到什么呢？nice值的范围-20~19(40个)，这不就与之对应嘛！

所以，对于优先级来说，60~99对应的就是queue下标的100 ~ 139。 然后，相同优先级的进程按照FIFO规则进行排队调度，所以，数组下标就是优先级！

有了前面的说明，我们来看一下，调度的详细细节吧： 我们要从该结构中，选择⼀个最合适的进程，过程是怎么的呢？

1.从0下表开始遍历queue[140]； 2.找到第一个非空队列，该队列必定为优先级最高的队列； 3.拿到选中队列的第一个进程，开始运行，调度完成！

简单，虽然遍历queue[140]时间复杂度是常数！但还是太低效了！ 所以，有了bitmap[5]：一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个比特位表示队列是否为空（位图），这样，便可以大大提高查找效率！此时，才叫O(1)。

在这里插入图片描述

所以，我们调度队列就成了根据位图选队列，再根据队列取进程。

上面说的都没有问题，但是，我们说，进程是有时间片的，当一个正在被调度的进程时间片耗尽的时候，就会调度下一个进程，那此时时间片耗尽的进程它去哪里 — 过期队列。

过期队列

过期队列和活动队列结构一模一样； 过期队列上放置的进程，都是时间片耗尽的进程； 当进程时间片耗尽，重新计算该进程的时间片，然后将进程加入过期队列即可。

active指针和expired指针

active指针永远指向活跃队列； expired指针永远指向过期队列； 不难看出，活动队列上的进程会越来越少，过期队列上的进程会越来越多； 只需要在活跃队列变空时，交换active指针和expired指针的内容，就相当于有具有了一批新的活动进程！

小总结： 在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法！

总结

进程优先级是调度的依据，PRI值越小优先级越高，通过nice值可在-20到19范围内调整。进程切换通过保存/恢复CPU寄存器状态实现时间片轮转。Linux 2.6的O(1)调度算法用两个优先级数组（活动队列和过期队列）配合位图，实现了常数时间的进程选择，调度高效且公平。