15.Linux进程调度与优先级机制解析

一.孤儿进程

僵尸进程是父进程在，子进程退出了，且子进程退出父进程什么都不做，但如果父进程提前退出了会怎样呢？

子进程不退出，父进程执行5s后退出

然后编译运行后再去查看进程，等父进程退出后可以看到

这时我们发现，子进程的PPID变成了1，即如果父子关系中，父进程先退出，子进程要被1号进程领养，这个被领养的进程（子进程）叫做孤儿进程

top后可以看到1号进程的名字为systemd

（1）1号进程是谁

现在我们就先理解它是操作系统

（2）为什么要被领养？

如果不被领养的话，就没有父进程，那么等子进程退出变为僵尸进程后，就没有父进程去回收它，会造成内存泄漏问题

（3）变成在后台运行

变成孤儿进程后该进程就变成在后台运行了，此时再ctrl+c发现它还在运行，后台运行不会阻塞命令行，可以用kill杀掉

二.进程优先级

1.是什么

是进程得到cpu资源的先后顺序

2.为什么要有优先级

目标资源稀缺，导致要通过优先级确认谁先谁后的问题，合理分配优先级可以优化系统性能，尤其是在多任务环境中。

3.怎么实现

在一般的操作系统内，优先级也是一种数字，是pcb（task_struct)内的一种属性。值越小优先级越高。我们大部分操作系统都是基于时间片（规定一个任务完成的时间）的分时操作系统，其特点会考虑公平性的问题，保证优先级之间差别不会太大，优先级的变化不会太大，尽可能保持公平。

UID：

UID标识用户的唯一数字ID。每个用户账户都有一个对应的UID，系统通过UID来区分不同用户的权限和资源访问。

（n表示以数字显示）

小知识：系统怎么知道一个用户访问文件的时候，是拥有者，所属组，还是other？

进程启动的时候，会记录是谁启动的即记录下对应的UID，然后进程就会以这个UID依次和文件拥有者用户的UID，所属组的UID作对比，哪一个先匹配就是对应的身份。如果都不相等就是other。

PRI和NI

PRI：进程的优先级，默认是80

NI：进程优先级的修正值，默认是nice值（0）

PRI(new)=PRI(old默认就是80)+nice

eg：

PRI(new）=PRI(old)+nice=80+10=90;(都是80去运算）

怎么改优先级？

1.top

命令行输入top后按下r键，输入目标进程的PID（进程ID），随后输入新的nice值。

2.nice

使用nice命令启动新进程

nice -n [优先级值] [命令]

例如，以优先级10启动一个进程：

nice -n 10 ./script.sh

2.renice

renice -n [新nice值] -p [PID]

优先级的极值问题

在Linux中nice[-20,19]，则优先级的范围[60,99]---只针对普通进程（只有普通进程收nice值影响，一共40个）

这对资源系统稳定性和资源分配有重要作用，优先级极值限制了用户进程对系统资源的过度占用。若允许无限调整优先级，低优先级进程可能因资源匮乏而完全无法运行，高优先级进程可能垄断CPU导致系统不稳定。极值设定在-20（最高）和19（最低）之间，确保资源分配相对公平。

三.概念-竞争、独立、并行、并发

竞争性:

系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级

独立性:

多进程运行，需要独享各种资源，多进程运行期间互不干扰

并行:

多个进程在多个CPU下分别，同时进行运行，这称之为并行

并发:

多个进程在⼀个CPU下采用进程切换的方式，在⼀段时间之内，让多个进程都得以推进，称之为并发

四.进程切换

1.死循环进程怎么运行

一旦一个进程占用cpu，不会把其代码跑完，待它的时间片结束后，就会切换进程，不会让cpu一直执行某个进程，进入死循环

2.cpu和寄存器

CPU（中央处理器）是计算机的核心部件，负责执行指令和处理数据。

寄存器是CPU内部的高速存储单元，用于临时存放指令、数据或地址，其访问速度远高于内存。

cpu执行某个进程的代码时不会一股脑全部加载到cpu，而是CPU从内存读取指令到寄存器，解码后执行运算，结果可能写回寄存器或内存。寄存器会保存正在运行的进程的临时数据，根据寄存器功能不同，其里面保存的数据也不相同，例如其中EIP/pc就是存储下一条待执行指令的地址，这样cpu就知道要执行的下一条语句地址了。所以寄存器减少了CPU直接访问内存的次数，显著提升性能。

寄存器是cpu内部的临时空间，即寄存器！=寄存器的里面内容

一个是空间一个是内容，空间只有一份，而内容可以有多份

3.怎么切换进程

具体步骤：

保存当前进程上下文
将当前进程的寄存器状态（如PC、SP、通用寄存器）、程序计数器和其他运行时数据保存到其进程控制块（PCB）中。

选择下一个进程
调度器从就绪队列中选择一个优先级最高的进程，将其PCB加载到内存中。

恢复新进程上下文
从新进程的PCB中恢复寄存器状态、程序计数器等，并更新内存管理单元（MMU）的页表或段表。

更新内核数据结构
修改进程状态（如将原进程设为就绪或阻塞）、更新调度队列，并可能处理进程统计信息（如运行时间）。

eg：当进程A切换到进程B时，会先通过把进程A的寄存器状态、程序计数器和其他运行时数据保存到其进程控制块（PCB）中的方式来保存进程A的上下文数据。然后再从调度队列中选择一个优先级最高的进程（例如B），将其PCB加载到内存中，cpu再运行进程B，这时就会从B进程的PCB中恢复寄存器状态、程序计数器等即恢复进程B的上下文数据，等到B进程的时间片结束后，再到A进程的时候就会一样的从A的PCB恢复寄存器状态、程序计数器等即恢复曾经进程A保存的历史上下文数据。

所以进程切换本质最核心的就是保存和恢复当前进程的硬件上下文数据，即寄存器的内容

补充知识：上下文数据保存到哪里了？

其实在Linux一些比较老的内核版本中，是由在task_struct内部的一个结构体TSS（任务状态段）来保存，但现在新的内核版本通常把其单独分了出来，不在task_struct内部了

五.Linux的真实调度算法（O(1)调度算法）

1.几个小知识

（1）操作系统内部会有一个指针struct task_struct *current永远指向当前进程。

（2）操作系统一般可以分为

分时操作系统：按时间片公平调度

实时操作系统：是一种专门设计用于在严格时间限制内处理任务的系统，即有新进程要想被调度时会立刻响应，不会等时间片结束。主要运用在工业和制造业上。

Linux优先级有140个，前100个称为实时优先级，而后面40个才为分时优先级这也和优先级范围[60,99]对应

（3）调度器=调度+切换

2.Linux2.6内核中进程队列的数据结构

// 每个CPU独有一个 runqueue struct runqueue { // 锁、统计、当前运行进程、负载、时间戳...一堆全局字段 spinlock_t lock; task_struct *curr; // 当前正在跑的进程 task_struct *idle; // CPU空闲进程 // 关键：两个 prio_array 实体，存就绪任务 struct prio_array arrays[2]; // 两个指针，分别指向上面两块数组 struct prio_array *active; struct prio_array *expired; }; // prio_array 只是runqueue里面的“就绪任务收纳盒” struct prio_array { int nr_active; unsigned long bitmap[5]; struct list_head queue[140]; };//active和expired的类型就是struct prio_array呀

⼀个CPU拥有⼀个runqueue，杜绝多核全局锁争抢， 如果有多个CPU就要考虑进程个数的负载均衡问题

其中一个 runqueue 绑定 2 个 prio_array分别是活跃队列和过期队列

runqueue 管 CPU 全局调度状态，prio_array 只管就绪进程的优先级排队

活跃队列

正在使用的队列叫活跃队列

（1） struct list_head queue[140] 其中每个元素类型：struct list_head（双链表），链表上的每一个元素就是struct task_struct，比如queue[10]就表示所有优先级为10的进程都挂载到queue[10]这条队列上，所以，数组下标就是优先级！而相同优先级的进程（在同一条队列中）按照FIFO规则进行排队调度（下面有图）

（2）nr_active:总共有多少个运行状态的进程

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

1、从0下表开始遍历queue[140]。
2、找到第一个非空队列，该队列必定为优先级最高的队列。
3、拿到选中队列的第一个进程，开始运行，调度完成。
4、遍历queue[140]时间复杂度是常数！但还是太低效了。

（4）bitmap[5]：一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32（160，其中20个没用，对应140个优先级和进程队列）个比特位表示队列是否为空，这样便可以大大提高查找效率！

比特位的位置和queue[140]的下标一一对应

比特位的内容：1/0，表示对应queue[140]相应位置是否存在进程，是否为空。

所以有了bit_map，调度的时候先查看nr_active大于0则再去查找bit_map确认下标，再在队列中找到该下标位置，从队列头部选中第一个进程，把该进程的pcb给current指针，最后cpu就能通过current指针找到并调度对应的进程。即调度器先挑选队列再到对应队列上挑选进程

但一个队列没办法做到公平调度——进程饥饿问题

只有一个活跃队列（实时操作系统）是没办法做到公平调度，例如有优先级为60的进程不断死循环，一直被调度，那优先级为99的进程就不能被调度，会造成进程饥饿问题。所以还得有一个结构和活跃队列相同的队列

过期队列

• 过期队列和活动队列结构⼀模⼀样（queue，bitmap这些就不再重复说了）

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

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

实现双队列轮转

active指针永远指向活跃队列

expired指针永远指向过期队列

运行方法：

• 调度器只从runqueue->active指向的 prio_array 取进程运行；
• 进程时间片耗尽 → 从 active 对应的 prio_array 摘下，重算优先级后放入runqueue->expired对应的 prio_array；
• 当 active 的 prio_array 内没有就绪进程时： 直接交换 runqueue 里active和expired两个指针，不用移动 prio_array 里任何进程；
• 下次调度继续从新的 active（原 expired）prio_array 中挑选任务。

综上所述

• prio_array 的 bitmap：O (1) 找最高优先级进程
• runqueue 内 active/expired 指针交换：O (1) 切换调度周期

整个过程，时间复杂度是O(1)，所以这就是Linux内核之O(1)调度算法

总结一下实时和普通进程的区别（都适用O（1）调度算法）