内核进程调度队列(linux的真实调度算法) ─── linux第13课
目录
内核进程调度队列的过程
一个CPU拥有一个runqueue(运行队列在内存)
活动队列(active)
过期队列(expired)
active指针和expired指针
重绘runqueue
linux内核O(1)调度算法
总结
补充知识:
封装链式结构的目的是:
仅使用封装链式结构可以得到全部的task_struct的信息的原理:
内核进程调度队列的过程

上图是Linux2.6内核中进程队列的数据结构,之间关系也已经给大家画出来,方便大家理解
一个CPU拥有一个runqueue(运行队列在内存)
如果有多个CPU就要考虑进程个数的负载均衡问题
在上图我们可以看到,runqueue中含有两个struct queue数据结构 array[0]是活跃队列和array[1]是过期队列
struct queue队列数据结构包含了nr_activce bitmap[5] queue[140]三个结构
queue队列中的
- nr_active是哈希桶中task_struct的数量 功能:控制是否swap(下面讲了)
- bitmap[5]充当位图 功能:更快找到下一个要调度的进程在哈希桶的哪个位置
- queue[140]是一个哈希桶, 在100到139下标中分别存储链式的进程PCB(task_struct) ,正好对应了40种进程优先级.
活动队列(active)
- 时间片还没有结束的所有进程都按照优先级放在该队列
- nr_active: 总共有多少个运行状态的进程
- queue[140]: 一个元素就是一个进程队列,相同优先级的进程按照FIFO规则进行排队调度,所以,数组下标就是优先级!
从该结构中,选择下一个最合适的进程,过程是怎么的呢?
1. 从0下表开始遍历queue[140]
2. 找到第一个非空队列,该队列必定为优先级最高的队列
3. 拿到选中队列的第一个进程,开始运行,调度完成!
4. 遍历queue[140]时间复杂度是常数!但还是太低效了!因此设计了bitmap[5r]
- bitmap[5]:一共140个优先级,一共140个进程队列,为了提高查找非空队列的效率,就可以用5*32个比特位表示队列是否为空,这样,便可以大大提高查找效率
过期队列(expired)
- 过期队列和活动队列结构一模一样
- 过期队列上放置的进程,都是时间片耗尽的进程
- 当活动队列上的进程都被处理完毕之后,对过期队列的进程进行时间片重新计算
active指针和expired指针
active指针永远指向活动队列
expired指针永远指向过期队列
可是活动队列上的进程会越来越少,过期队列上的进程会越来越多,因为进程时间片到期时一直都存在的。
没关系,在合适的时候,只要能够交换active指针和expired指针的内容,就相当于有具有了一批新的活动进程!
重绘runqueue
下图重新描绘了runqueue
此时active是array[0]的首地址 ,expired 是array[1]的首地址
为什么runqueue需要两个array呢?
- runqueue只有一个array , 如果一直有优先级高的进程插入进来,会导致优先级低的进程一直无法运行,导致饥饿问题
- 而两个array可以解决问题: 一个array结构叫做actice队列 ,另一个叫做expired队列,归定cpu只能从active队列中,选取task_struct运行其对应的程序 , 新进程和时间片到了的进程的task_struct 按照优先级加在expired队列中,等到active队列中pcb的数量为0时 ,交换两个队列指针(swap(&active,&expried)) 省去了将pcb重新插入的步骤.
linux内核O(1)调度算法
如何进行快速算法调度(快速找到下一个task_struct),linux设计了一种O(1)算法
4*8*5 =140
而bitmap[5]正好是5个int值
可以利用类似这种算法
for(int i=0; i<5 ;i++) {if(bitmap[i] == 0) continue;//一次可检测32个位置else(bitmap[i]!= 0){算法2查找bit位为1的精确位置}}而算法2可以 利用
n & (n - 1)可以清除最低位的 1 的特性,减少循环次数。找到哪个比特位为1, 就是哪个优先级中有pcb#include <stdio.h>int countBits(int num) {int count = 0;while (num) {num &= (num - 1);count++;}return count; }int main() {int num = 29; // 二进制表示为 11101printf("Number of 1 bits in %d is %d\n", num, countBits(num));return 0; }
总结
在系统当中查找一个最合适调度的进程的时间复杂度是一个常数,不随着进程增多而导致时间成本增加,我们称之为进程调度O(1)算法!
补充知识:
进程的task_struct都用链表链接
task_struct可在运行队列 , 阻塞队列中
linux的链式结构是双链结构
task_struct中将双链结构进行了封装如下图struct node

封装链式结构的目的是:
如果进程处于某个链式结构中, 只需将task_struct中的链式结构的next和prev填充就行, 而且使得task_struct还可以同时处于多个链表中.
仅使用封装链式结构可以得到全部的task_struct的信息的原理:

下图讲解了仅使用封装链式结构可以得到全部的task_struct的信息
先得到链式结构的偏移量,再找到task_struct的首地址即可
类似使用offset(type ,x)
假设structA从0地址存储, 其实大概率不可能存储到这 , 只是为了得到C的偏移量,再用真实C的地址来找structA 的起始地址.

相关文章:
内核进程调度队列(linux的真实调度算法) ─── linux第13课
目录 内核进程调度队列的过程 一个CPU拥有一个runqueue(运行队列在内存) 活动队列(active) 过期队列(expired) active指针和expired指针 重绘runqueue linux内核O(1)调度算法 总结 补充知识: 封装链式结构的目的是: 仅使用封装链式结构可以得到全部的task_struct的信…...
16.7 LangChain LCEL 极简入门:Prompt + LLM 的黄金组合
LangChain LCEL 极简入门:Prompt + LLM 的黄金组合 关键词:LCEL 基础示例、Prompt 模板设计、LLM 集成、链式调用、LangChain 快速上手 1. 基础架构解析:Prompt → LLM → Output 1.1 核心组件交互流程 #mermaid-svg-pv3fH3mEKyE4TNaF {font-family:"trebuchet ms&qu…...
Spring线程池学习笔记
Spring提供了多种方式来配置和使用线程池,最常见的是通过TaskExecutor和ThreadPoolTaskExecutor。 Spring线程池 TaskExecutor 接口 TaskExecutor 是Spring框架中的一个接口,它是对Java的Executor接口的简单封装。它的主要目的是为了提供一个统一的接口…...
ArcGIS操作:08 计算shp面积并添加到属性表
1、打开属性表 注意:计算面积前,需要把shp的坐标系转化为投影坐标系(地理坐标系用于定位、投影坐标系用于测量) 2、创建字段 3、编辑字段名、类型 4、选择字段,计算几何 5、选择属性、坐标系、单位...
安卓音频框架混音器
在 Android 音频框架中,混音器(Mixer) 是 AudioFlinger 服务的核心组件之一,负责将多个音频流(来自不同应用或系统组件)混合为统一的输出流,再传输到音频硬件设备(如扬声器、耳机等&…...
左值引用与指针的区别
很多朋友遇到过这个问题:左值引用与指针有哪些区别?脑子里闪过很多答案,但大部分都是各自的定义,真要说他们两个有什么区别,有的时候还这是说不上来。本文针对这个问题进行归纳总结,希望对大家有所帮助。 …...
Linux基础使用和程序部署
目录 1.Linux 1.2 Linux的环境搭配 1.2.1 使用云服务器 1.2.2使用终端软件连接到Linux 1.3. Linux 常用命令 1. ls:列出当前目录中的文件和子目 2.pwd:显示当前工作目录的路径 3.cd:改变工作目录,将当前的工作目录改变到指定目…...
Linux驱动开发之串口驱动移植
原理图 从上图可以看到RS232的串口接的是UART3,接下来我们需要使能UART3的收发功能。一般串口的驱动程序在内核中都有包含,我们配置使能适配即可。 设备树 复用功能配置 查看6ull如何进行uart3的串口复用配置: 设备树下添加uart3的串口复用…...
计算机毕业设计SpringBoot+Vue.js美食推荐系统商城(源码+文档+PPT+讲解)
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
指针小节.
....指针的第四个作用:函数的结果和计算状态分开 高级指针。。 指针中的数据类型:获取字节数据的个数。步长:指针移动一次的字节个数(int,long。。。各自字节都不同) 加减都可以...
[Qt5] QJson数据之间的转换以及QByteArray图像数据压缩
📢博客主页:https://loewen.blog.csdn.net📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正!📢本文由 丶布布原创,首发于 CSDN,转载注明出处🙉📢现…...
2025年能源工作指导意见
2025年是“十四五”规划收官之年,做好全年能源工作意义重大。为深入贯彻落实党中央、国务院决策部署,以能源高质量发展和高水平安全助力我国经济持续回升向好,满足人民群众日益增长的美好生活用能需求,制定本意见。 一、总体要求…...
Android 获取jks的SHA1值:java.io.IOException: Invalid keystore format
命令生成 keytool -list -v -keystore 全路径.jks -alias 别名 -storepass 密码 -keypass 密码 1、遇到 的问题: 通过快捷键 ‘win r’ 启动的小黑框运行上面的命令会出现下面这个错误keytool 错误: java.io.IOException: Invalid keystore format 2、解决问题 …...
深入探索像ChatGPT这样的大语言模型-02-POST training supervised finetuning
参考 【必看珍藏】2月6日,安德烈卡帕西最新AI普及课:深入探索像ChatGPT这样的大语言模型|Andrej Karpathy fineweb知乎翻译介绍 fineweb-v1原始连接 fineweb中文翻译版本 Chinese Fineweb Edu数据集 查看网络的内部结果,可以参…...
广义线性模型下的数据分析(R语言)
一、实验目的: 通过上机试验,掌握利用R实现线性回归分析、逻辑回归、列联分析及方差分析,并能对分析结果进行解读。 数据: 链接: https://pan.baidu.com/s/1JqZ_KbZJEk-pqSUWKwOFEw 提取码: hxts 二、实验内容: 1、2…...
AutoMQ:无需 Cruise Control 实现 Kafka 的自动分区再平衡
导读:AutoMQ是一款贯彻云优先理念来设计的 Kafka 替代产品。AutoMQ 创新地对 Apache Kafka 的存储层进行了基于云的重新设计,在 100% 兼容 Kafka 的基础上通过将持久性分离至 EBS 和 S3 带来了 10x 的成本降低以及 100x 的弹性能力提升,并且相…...
在剪映中给英文学习视频添加中文字幕
文章目录 一、剪映是什么?二、使用步骤1.下载2.操作 一、剪映是什么? 剪映是由字节跳动公司开发的一款功能强大且易于使用的视频编辑软件,在移动端和电脑端均有应用。 二、使用步骤 1.下载 2.操作...
Opencv之sift特征检测和FLANN 匹配器进行指纹特征匹配
sift特征检测和FLANN 匹配器进行指纹匹配 目录 sift特征检测和FLANN 匹配器进行指纹匹配1 sift特征检测1.1 概念1.2 优缺点 2 FLANN 匹配器2.1 概念2.2 工作原理与匹配方式2.3 FLANN 匹配器的使用步骤2.4 优缺点 3 函数3.1 特征检测匹配3.2 匹配符合条件点并绘制 3 代码测试3.1…...
rust学习~tokio的io
await Suspend execution until the result of a Future is ready. 暂停执行,直到一个 Future 的结果就绪。 .awaiting a future will suspend the current function’s execution until the executor has run the future to completion. 对一个 Future 使用 .awa…...
FPGA开发,使用Deepseek V3还是R1(2):V3和R1的区别
以下都是Deepseek生成的答案 FPGA开发,使用Deepseek V3还是R1(1):应用场景 FPGA开发,使用Deepseek V3还是R1(2):V3和R1的区别 FPGA开发,使用Deepseek V3还是R1&#x…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...





