江苏通信建设交易中心网站,辽宁省建设工程信息网人员解除,wordpress顶部菜单哪里设置,网站开发与建设个人总结#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负 目录
前言
1.进程切换
2.进程调度
2.…
樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》
每一个不曾起舞的日子都是对生命的辜负 目录
前言
1.进程切换
2.进程调度
2.1Linux系统的进程调度算法如何实现兼顾进程优先级的设计
2.2Linux系统的进程调度算法如何实现兼顾效率的设计
2.3nr_active
2.4Linux系统的进程调度算法如何实现兼顾进程饥饿的设计
2.4.1理论上讲解
2.4.2如何实现的 前言
上篇文章我们最后提到了进程的并发多个进程在一个CPU下采用进程切换的方式在一段时间之内让多个进程都得以推进称之为并发。
那么Linux是如何完成进程的调度与切换的呢
本篇文章博主会与大家共同学习Linux下进程的调度与切换。 欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码fanfei_c的仓库 1.进程切换
我们知道一个CPU在同一时间只能运行一个进程而并发实际上就是利用时间片让每个进程在CPU上只能运行一个时间片的时间然后就被切换到另一个进程所以我们计算机虽然看起来似乎是非常流畅的运行每个进程而实际上则是一卡一卡的运行的只不过这个时间非常短我们感觉不到罢了。
那进程首次调度完成被切换走当CPU二次调度该进程时是如何记得上次执行到哪里了呢 CPU中存在有大量的寄存器进程运行产生的临时数据都被保存在这些寄存器中这些临时数据被称为进程的硬件上下文当时间片消耗完的时候进程会保存这些上下文现阶段大家可以理解为保存到PCB中当进程被二次调度时进程会将曾经保存的硬件上下文进行恢复将之前保存的硬件上下文覆盖到CPU的寄存器中。 虽然CPU中的寄存器只有一套但是寄存器内部保存的数据可以有多套。CPU是被所有进程共享的但内部的数据却是进程私有的。
大家可以理解为在任意一个时刻CPU中的数据只属于一个进程。
所以看起来我们用的是同一个设备但实际上进程之间是具有独立性的。 独立性进程运行需要独享各种资源多进程运行期间互不干扰。 2.进程调度
上篇文章我们讲到了优先级的概念那Linux是如何在兼顾进程优先级、饥饿、效率来实现进程调度的算法呢
实际上操作系统想要实现一个进程调度算法并不容易而Linux对于进程调度的算法设计非常优秀我们一起来学习一下吧
之前我们学习进程状态时有关进程排队中CPU运行队列有过这样一张图 今天我们来细化一下运行队列中的成员 这是Linux系统下对运行队列的设计。
不考虑其他成员我们只看圈出来的两个部分
蓝色部分为活动队列红色部分为过期队列他们两个你可以认为是完全相同的两个结构。 2.1Linux系统的进程调度算法如何实现兼顾进程优先级的设计
该数组中一个元素就是一个进程队列相同优先级的进程按照FIFO先进先出规则进行排队调度所以数组下标就是优先级
但我们之前学习优先级时不是说进程优先级范围为[60,99]么一共40个优先级为什么这里有140个优先级呢
首先这里我们只考虑100~139这部分被称为普通优先级100就对应着60139就对应着99而剩下0~99的部分为实时优先级。 什么是实时优先级 分时操作系统必须以时间片为周期调度不同的进程是为了确保公平避免进程饥饿比如现在的互联网在互联网的视角中所有用户都是公平的不能因为谁的优先级高就仅服务谁所有用户的优先级都差不太多不会出现谁的优先级非常高的情况。还有另外一种为实时操作系统则相反在运行某个进程时必须跑完严格按照队列先后顺序进行如果有更高优先级的进程允许插队即实时操作系统必须对用户有高响应这一特性比如车载系统绝对不能使用基于时间片轮转的分时操作系统而必须采用实时操作系统刹车的指令优先级非常高在用户需要刹车时他不会考虑音乐播放器进程会不会饥饿。所以我们必须保证一些进程实时尽快的被处理所以也就有了实时优先级的概念而0~99这些优先级就是为了这一部分而准备的。 所以我们运行队列中queue[140]的构成大概为这样子 之前我们以为运行队列就是一个队列但实际上操作系统要给我们维护40个队列每个队列都代表着不同的优先级。 2.2Linux系统的进程调度算法如何实现兼顾效率的设计
每次CPU运行进程难道都要从开始向上遍历找不为空的队列么那也太麻烦了。
所以就有了bitmap[5]这个成员该成员是int类型的数组int类型占32个bit所以5个int就是160个bit而queue为140多出来的20我们不管那是不是检测哪个优先级队列中有进程就能够转化乘检测对应的比特位是否为1了呢 位操作的速度可比遍历快多了。 比如如果数组中某个元素为0则证明该32个比特位都为0也就证明该32个队列都为空如果某个元素不为0那该问题就转化为了如何从一个整形中提取出最低位的不为0的比特位。 所以该算法在系统中查找一个最合适调度的进程的时间复杂度是一个常数不会随着进程的增多而导致时间成本增加被称为O(1)调度算法。 2.3nr_active
表示该运行队列共有多少个活跃进程。 2.4Linux系统的进程调度算法如何实现兼顾进程饥饿的设计
假设在运行队列里存在有很多优先级为139的进程等待执行但此时不断产生更高优先级的进程也就导致优先级为139的进程进程饥饿的问题了。 2.4.1理论上讲解
那Linux系统是如何处理进程饥饿的呢
Linux系统搞了两个一摸一样的结构就是为了处理进程饥饿。
一个称之为活跃队列一个称之为过期队列。
CPU只会执行活跃队列中的进程而新产生的进程会被操作系统添加到过期队列不论这个新进程的优先级高低等活跃队列中的进程都被执行完成了后此时过期队列摇身一变成为活跃队列而活跃队列变为过期队列周而复始也就解决了进程饥饿的问题。
注意如果某个处在活跃队列中的进程的时间片消耗完该进程就会从活跃队列中剥离然后被添加到过期队列。 2.4.2如何实现的
我们将蓝色框与红色框定义为两个结构体
struct q//这两个结构体相同这里就写一个大家理解就行
{int nr_active;int bitmap[5];task_struct queue[140];
}
再定义一个数组struct q array[2];
该数组用来存放这两个结构体。
再定义两个成员*active与*expired 这两个指针分别指向数组中的内容即
struct q *activearray[0];
struct q *expiredarray[1]; 每当活跃队列为空时就会交换这两个指针变量的内容使之指向对方原来指向的内容这也就完成了活跃队列变为过期队列过期队列变为活跃队列的操作
swap(active,expired);
所以Linux系统对于进程调度的设计是不是非常巧妙呢 如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
