目录
3. Linux kernel 2.6 内核调度队列与调度原理
前言
进程是资源分配的基本单位, 在OS中存在这很多的进程, 那么就必然存在着资源竞争的问题, 操作系统是如何进行资源分配的? 对于多个进程同时运行, 操作系统又是如何调度达到并发呢? 本文将以Linux kernel 2.6为例 , 向大家介绍进程在操作系统中 (OS) 的调度原理;
1. 进程优先级
进程优先级是操作系统中用来确定进程获取 CPU 资源的先后顺序的一种机制;
为什么要排队? 本质是资源不足; 在一台电脑中可能只有一个CPU, 但是可能会同时启动多个进程, 那么进程在分配CPU资源时就需要排队(等待CPU资源);
对于较为重要的进程, 可以设置高优先级, 高优先级进程有优先执行权利。配置进程优先权对多任务环境的linux很有用，可以改善系统性能。还可以把进程运行到指定的CPU上，这样一来，把不重要的进程安排到某个CPU，可以大大改善系统整体性能。
使用ps -l查看系统进程:
其中较为重要的信息:
- UID : 代表执行者的身份
- PID : 代表这个进程的代号
- PPID ：代表这个进程是由哪个进程发展衍生而来的，亦即父进程的代号
- PRI ：代表这个进程可被执行的优先级，其值越小越早被执行
- NI ：代表这个进程的nice值(在进程PCB中)
Linux中进程优先级范围: 60 ~ 99;
Linux中创建进程,默认进程优先级是 80
在Linux中支持优先级的动态调整, 动态调整的规则:
nice值最小是-20, 超过 -20就统一成 -20;
nice值最大为19, 超过19 统一成19;
优先级(PRI) 的计算 : PRI (new) = PRI (old) + nice ;
PRI+ nice值是基于默认值80计算的(不会累计)，比如: 先把nice值设为10，那么PRI就会变成90，使用root账户将nice值设为-10，PRI就变成了70 ;
用top命令更改已存在进程的nice：
- top
- 进入top后按“r”–>输入进程PID–>输入nice值
注意: OS只允许普通用户把优先级调低, 不允许把优先级调高, root账户无限制;
为什么设置限制?
OS在调度时，为了让每一个进程较为均衡得到调度; 如果nice值可以随意乱改, 就会存在用户恶意的将自己的进程优先级调高，导致优先级低的进程长时间得不到CPU资源 ;
需要注意的点是，进程的nice值不是进程的优先级，PR I和 NI 他们不是一个概念，但是进程nice值会影响到进程的优先级变化。可以理解nice值是进程优先级的修正修正数据
几个较为重要的概念:
- 竞争性: 系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为了高效完成任务，更合理竞争相关资源，便具有了优先级
- 独立性: 多进程运行，需要独享各种资源，多进程运行期间互不干扰
- 并行: 多个进程在多个CPU下分别，同时进行运行，这称之为并行
- 并发: 多个进程在一个CPU下采用进程切换的方式，在一段时间之内，让多个进程都得以推进，称之为并发
2. 并发
本文的重点是并发 , 先来介绍一下什么是并发?
一个进程在被CPU调度时, 并不是一直占用CPU直至运行结束 , 而是每隔一段时间(这个时间段也叫做时间片) ，它就会被从CPU上被剥离下来 , 然后会重新放进运行队列等待被调度，如此反复，直到进程运行完毕; CPU每次调度进程时, 都会到运行队列中去取;
Linux内核支持进程之间CPU资源的抢占，它是一种基于时间片轮转式抢占式内核，时间片非常的短，轮转速度非常快(一秒内进程可能被调度了100次)，所以我们很难察觉;
新的问题: 进程在运行时会被从CPU上剥离下来, 那下次调度时, CPU是如何知道进程执行到哪里的呢?
小方框表示寄存器;
在CPU当中有很多各种各样的寄存器:eax、ebx、ecx、edx、ss、ds、cs、gs、fs、ebp、esp、eip..
寄存器的功能有很多，比如记录程序/进程的运行状态(走到那一步);
比如: cpu内:eip:程序计数器;
进程在运行时会使用这些寄存器，进程会产生各种各样的数据，在寄存器中临时保存 !
如果有多个进程，各个进程在CPU内形成的临时数据，都是不一样的每个进程运行到哪里，产生的临时数据，叫做进程硬件上下文;
在进行轮转切换时会暂时将这个数据存储到进程PCB里;
注意:
在以前老的Linux中是这样，现在的不是直接保存到PCB，原因是PCB内容太多，太大，但都与PCB有联系，这里只是可以理解为放在PCB当中;本质就是将CPU寄存器当中的数据保存到内存当中;
CPU寄存器硬件只有一套，进程上下文数据有很多套，比如10个进程有10套上下文数据;
寄存器 != 寄存器内容
3. Linux kernel 2.6 内核调度队列与调度原理
有了前边的基础知识补充, 接下来我们介绍一下Linux kernel 2.6 内核调度队列以及基本调度原理;
一个CPU拥有一个runqueue(如果有多个CPU就要考虑进程个数的负载均衡问题)
下图就是Linux2.6内核中进程队列的数据结构:
优先级:
- 普通优先级： 100～ 139
- 实时优先级： 0～ 99（不关心）
100~139就是我们使用指令看到的40个优先级; 从第100号开始(PRI: 60), 优先级依次向下递减;
如下图:
CUP调度队列中的进程是如果直接遍历一遍队列, 然后依次调度进程, 遍历的过程也会造成资源的浪费; 所以在设计时加入了nr_active 和 bitmap[5];
int整形占4个字节，32个bit位 5 x 32 也就是 160个 bit位 (足够表示140个优先级) ; 利用位图映射可以极大的提高效率;
nr_active判断队列是否有进程，bitmap位图映射快速找到进程位置，这样下来轮转一次的效率就会非常高，时间复杂度接近O(1) ;
在操作系统中会维护两个这样的队列 (活动对列 和 过期队列);
进程在活动队列并不一定就运行完了，可能是时间片结束了，被调度完之后就会加入到了过期队列;
同时还会维护两个指针:
- void *active 活动队列
- void *expired 过期队列
CPU只会执行active指针指向的队列
当进程优先级为99的进程正在被执行时，新插入一些优先级较高的进程，这些进程会被插入
到过期队列当中; (如果直接插入到活动队列，那就会导致优先级较低的队列一直等待，进而引发进程饥饿问题)
这样一来, 过期队列的进程不断增多, 由于不会插入新的进程，所以它的进程数量一定会越来越少;当active指针指向的活动队列执行完毕，就将两个指针指向的队列进行交换即可
原本的活动队列执行空了，再来新的进程就插入到这个队列，这个队列会继续作为过期队列
如此循环，最终就完成了进程的调度;
这样的设计方式不仅提高了效率，并且也解决了进程饥饿问题;
总结
进程是资源分配的基本单位, 在OS中存在这很多的进程, 那么就必然存在着资源竞争的问题, 于是便有了进程优先级来确认进程调度的先后顺序; 但这也可能会伴随着进程饥饿的问题, 而在Linux2.6版本中的进程调度设计很好的解决这些问题; 具有很高的参考学习的价值; 好了以上便是本文的全部内容, 希望对你有所帮助 , 感谢阅读 !
