4、调度算法
点击阅读更多查看文章内容

进程调度算法
进程调度算法也称 CPU 调度算法,毕竟进程是由 CPU 调度的。 当 CPU 空闲时,操作系统就选择内存中的某个「就绪状态」的进程,并给其分配 CPU。 什么时候会发生 CPU 调度呢?通常有以下情况:
- 当进程从运行状态转到等待状态;
- 当进程从运行状态转到就绪状态;
- 当进程从等待状态转到就绪状态;
- 当进程从运行状态转到终止状态;
其中发生在 1 和 4 两种情况下的调度称为「非抢占式调度」,2 和 3 两种情况下发生的调度称为「抢占式调度」。
- 非抢占式的意思就是,当进程正在运行时,它就会一直运行,直到该进程完成或发生某个事件而被阻塞时,才会把 CPU 让给其他进程。
- 而抢占式调度,顾名思义就是进程正在运行时,可以被打断,使其把 CPU 让给其他进程。
那抢占的原则一般有三种,分别是时间片原则、优先权原则、短作业优先原则。 你可能会好奇为什么第 3 种情况也会发生 CPU 调度呢?假设有一个进程是处于等待状态的,但是它的优先级比较高,如果该进程等待的事件发生了,它就会转到就绪状态,一旦它转到就绪状态,如果我们的调度算法是以优先级来进行调度的,那么它就会立马抢占正在运行的进程,所以这个时候就会发生 CPU 调度。 那第 2 种状态通常是时间片到的情况,因为时间片到了就会发生中断,于是就会抢占正在运行的进程,从而占用 CPU。 调度算法影响的是等待时间(进程在就绪队列中等待调度的时间总和),而不能影响进程真在使用 CPU 的时间和 I/O 时间。
- 先来先服务调度算法
- 最短作业优先调度算法
- 高响应比优先调度算法
- 时间片轮转调度算法
- 最高优先级调度算法
- 多级反馈队列调度算法
内存页面置换算法
在了解内存页面置换算法前,我们得先谈一下缺页异常(缺页中断)。 当 CPU 访问的页面不在物理内存时,便会产生一个缺页中断,请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于:
- 缺页中断在指令执行「期间」产生和处理中断信号,而一般中断在一条指令执行「完成」后检查和处理中断信号。
- 缺页中断返回到该指令的开始重新执行「该指令」,而一般中断返回回到该指令的「下一个指令」执行。
我们来看一下缺页中断的处理流程,如下图:

页面置换算法的功能是,当出现缺页异常,需调入新页面而内存已满时,选择被置换的物理页面,也就是说选择一个物理页面换出到磁盘,然后把需要访问的页面换入到物理页。
那其算法目标则是,尽可能减少页面的换入换出的次数,常见的页面置换算法有如下几种:
最佳页面置换算法(OPT) :置换在「未来」最长时间不访问的页面。实际系统中无法实现,因为程序访问页面时是动态的,我们是无法预知每个页面在「下一次」访问前的等待时间。 所以,最佳页面置换算法作用是为了衡量你的算法的效率,你的算法效率越接近该算法的效率,那么说明你的算法是高效的
先进先出置换算法(FIFO) :选择在内存驻留时间很长的页面进行中置换
最近最久未使用的置换算法(LRU) :选择最长时间没有被访问的页面进行置换,虽然 LRU 在理论上是可以实现的,但代价很高。为了完全实现 LRU,需要在内存中维护一个所有页面的链表,最近最多使用的页面在表头,最近最少使用的页面在表尾。 困难的是,在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常费时的操作。
时钟页面置换算法(Lock) :把所有的页面都保存在一个类似钟面的「环形链表」中,一个表针指向最老的页面。 当发生缺页中断时,算法首先检查表针指向的页面: 如果它的访问位位是 0 就淘汰该页面,并把新的页面插入这个位置,然后把表针前移一个位置; 如果访问位是 1 就清除访问位,并把表针前移一个位置,重复这个过程直到找到了一个访问位为 0 的页面为止;
最不常用置换算法(LFU):当发生缺页中断时,选择「访问次数」最少的那个页面,并将其淘汰。它的实现方式是,对每个页面设置一个「访问计数器」,每当一个页面被访问时,该页面的访问计数器就累加 1。在发生缺页中断时,淘汰计数器值最小的那个页面。
磁盘调度算法

常见的机械磁盘是上图左边的样子,中间圆的部分是磁盘的盘片,一般会有多个盘片,每个盘面都有自己的磁头。右边的图就是一个盘片的结构,盘片中的每一层分为多个磁道,每个磁道分多个扇区,每个扇区是 512 字节。那么,多个具有相同编号的磁道形成一个圆柱,称之为磁盘的柱面,如上图里中间的样子。
磁盘调度算法的目的很简单,就是为了提高磁盘的访问性能,一般是通过优化磁盘的访问请求顺序来做到的。 寻道的时间是磁盘访问最耗时的部分,如果请求顺序优化的得当,必然可以节省一些不必要的寻道时间,从而提高磁盘的访问性能。 假设有下面一个请求序列,每个数字代表磁道的位置: 98,183,37,122,14,124,65,67 初始磁头当前的位置是在第 53 磁道。 接下来,分别对以上的序列,作为每个调度算法的例子,那常见的磁盘调度算法有:
先来先服务算法
最短寻道时间优先算法:优先选择从当前磁头位置所需寻道时间最短的请求

扫描算法 :磁头在一个方向上移动,访问所有未完成的请求,直到磁头到达该方向上的最后的磁道,才调换方向,这就是扫描(Scan)算法。中间部分的磁道会比较占便宜,中间部分相比其他部分响应的频率会比较多,也就是说每个磁道的响应频率存在差异。
循环扫描算法:循环扫描(Circular Scan, CSCAN )规定:只有磁头朝某个特定方向移动时,才处理磁道访问请求,而返回时直接快速移动至最靠边缘的磁道,也就是复位磁头,这个过程是很快的,并且返回中途不处理任何请求,该算法的特点,就是磁道只响应一个方向上的请求。
LOOK 与 C-LOOK 算法:我们前面说到的扫描算法和循环扫描算法,都是磁头移动到磁盘「最始端或最末端」才开始调换方向。 那这其实是可以优化的,优化的思路就是磁头在移动到「最远的请求」位置,然后立即反向移动。
LOOK:针对 SCAN 算法的优化,磁头在移动到「最远的请求」位置,然后立即反向移动
C-LOOK:针 C-SCAN 算法的优化则叫 C-LOOK,它的工作方式,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中不会响应请求。