进程调度算法
进程调度也被称为CPU调度算法，毕竟进程是由CPU调度的。当CPU空闲的时候，操作系统就选择内存中某个“就绪状态”的进程，并给其他分配CPU，
什么时候会发生CPU调度呢？通常有以下情况：
- 当进程从运行状态转到等待状态
- 当进程从运行状态转到就绪状态
- 当进程从等待状态转到就绪状态
- 当进程从运行状态转到终止状态
其中发生1和4两种情况下的调度称为“非抢占式调度”，2，3两种情况下发生的调度称为“抢占式调度”。
非抢占式的意思就是，当进程正在运行时，它就会一直运行，直到该进程完成或发生某个事件而被阻塞，才会把CPU让给其他进程。
而抢占式的调度，顾名思义就是进程正在运行时，可以被打断，使其把CPU让给其他进程。那抢占的原则一般有三种，分别是:
- 时间片原则
- 优先权原则
- 短作业优先原则
调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），而不能影响进程真正使用CPU的时间和I/O时间。
先来先服务调度算法
最简单的一个调度算法，就是非抢占式的先来先服务（First Come First Serverd, FCFS）算法
顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或者阻塞，才会继续从队列队列中选择第一个进程接着运行。
这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待时间就会很长，不利于短作业。
FCFS对长作业有利，适用于CPU繁忙型作业的系统，而不使用于I/O繁忙型的系统。
最短作业优先调度算法
最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会选择运行时间最短的进程来运行，这样有助于提高系统的吞吐量。
<br />这显然对长作业不利，而且很容易造成一种极端现象：一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断地往后推，周转时间变长，致使长作业长期不会被运行。
高响应比优先调度算法
前面的先来先服务的算法和最短作业优先调度算法，都没有很好地权衡短作业和长作业。
那么，高响应比优先（Highest Response Ratio Next, HRRN）调度算法每次进程调度时，先计算HRRN, 然后把响应比优先级最高的进程投入运行。响应比优先级的计算公式为：
- 如果两个进程的等待时间是相同的，要求的服务时间越短，响应比就越高，这样短作业进程容易被选中运行
如果两个进程“要求的服务时间”是相同的，等待时间越长，响应比就越高，这就兼顾来长作业进程，因为进程的响应比可以随时间等待的增加而提高。当其等待时间足够长，其响应比便可以升到很高，从而获得运行的机会
时间片轮转调度算法
最古老，最简单，最公平而且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法：
每个进程被分配一个时间段，称为时间片（Quantam），即是允许该进程在该时间段内运行：如果时间片用完，进程还在运行，那么将会把进程从CPU释放出来，并把CPU分配另外一个进程
- 如果该进程在时间片结束前阻塞或者结束，则CPU立即进行切换。
另外，时间片的长度就是一个很关键的点， 如果时间片设得太短会导致过多的进程上下文切换，降低来CPU的效率。通常时间片设为20ms-50ms，这是一个较为合适折中值。
最高优先级调度算法
前面的时间片轮转算法，做了个假设，即让所有的进程同等重要，也不是偏袒谁，大家的运行时间都是一样的。
但有时候我们希望调度是有优先级的，希望调度程序可以从就绪队列中选择最高优先级的进程运行，这称为最高优先级（Highest Priority First, HPF）调度算法。
进程的优先级可以分为，静态优先级或者动态优先级：
- 静态优先级：创建进程的时候，就已经确定了优先级了，然后整个运行时间优先级都不会改变
- 动态优先级：根据进程的动态变化调整优先级，如果进程运行的时间增加，则降低其优先级。如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级别，也就是随着时间的推移增加等待进程的优先级
该算法也有两种处理高优先级的方法，非抢占式和抢占式：
- 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程
- 抢占式：当就绪队列中出现优先级别高的进程，当前进程挂起，调度优先级高的进程运行
内存页面置换算法
在了解内存页面置换算法之前，我们得先谈一下缺页异常（缺页中断）。当CPU访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入物理内存。它与一般的中断的主要区别在于：
- 缺页中断在指令执行期间，产生和处理中断信号，而一般的中断在一条指令执行完成后检查和处理中断信息
- 缺页中断返回到该指令的开始重新执行该指令，而一般中断返回回到该指令的下一个指令执行
我们来看一下缺页中断的处理流程，如下图：
缺页中断的处理流程：
- 在CPU里面访问一条Load M指令，然后CPU会去找到M所对应的页表项
- 如果该页表项的状态位是有效的，那CPU就可以直接去访问物理内存来。如果状态位是无效的，则CPU则会发送缺页中断请求
- 操作系统收到了缺页中断，则会执行缺页中断处理函数，先会查找该页面在磁盘中的页面的位置
- 找到磁盘中对应的页面后，需要把页面换入物理内存中，但是在换入前，需要在物理内存中找到空闲页，如果找到空闲页，就把页面换入物理内存中
- 页面从磁盘换入到物理内存完成后，则把页表中的状态位置修改为有效的
- 最后，CPU重新执行导致缺页异常的指令
那假如说，第4步的时候，找不到空闲页呢？这时候，就需要“页面置换算法”，选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，然后把该被置换出去到页表项的状态改为“无效的”，最后把正在访问的页面装入到这个物理页中。
这里提一下，页表项通常有如下的字段：
- 状态位：用于表示该页表是否还有效，也就是说是否在物理内存中
- 用于记录该页在一段时间被访问的次数，供页面置换算法选择出页面时参考
- 修改位：表示该页在调入内存后是否被修改过，由于内存中的每一个页都在磁盘上保留一份副本。因此，如果没有修改，在置换该页时就不需要将该页写回磁盘上，以减少系统的开销。如果已经被修改，则将该页重新写回磁盘上，以保证磁盘中所保留的始终是最新的副本。
- 硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用
页面置换算法的目标是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种。
最佳页面置换算法
最佳页面访问算法的基本思路是，置换在未来最长时间不访问的页面。
该算法实现需要计算内存中每个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面。
这很理想，但是实际上系统中无法实现，因为程序访问页面时是动态的，我们是无法预知每个页面在下一次访问前的等待时间。
先进先出置换算法
既然我们无法预知页面在下一次访问前所需的等待时间，那我们可以选择在内存驻留时间很长的页面进行置换。
在这个请求的页面序列中，缺页共发生了10次，页面置换共发生了7次，跟最佳页面置换算法比较起来，性能明显差了很多。
最久未使用的置换算法
最近最久未使用(LRU)的置换算法的基本思路是，发生缺页时，选择最长时间没有被访问的页面进行置换。也就是说，该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
虽然LRU在理论上是可以实现的，但是代价很高。为了完全实现LRU, 需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。
困难的是，在每次访问内存时都必须要更新整个链表，在链表中找到一个页面，删除它，然后把它移动到表头是一个费时的操作。所以，LRU虽然看上去不错，但是由于开销太大，实际应用中较少使用。
最不常用算法
最不常用算法（LFU）, 这个名字听起来很调皮，但是它的意思不是指这个算法不常用，而是当发生缺页中断时，选择访问次数最少的那个页面，并将其淘汰。
它的实现方式是，对每个页面设置一个访问计数器，每当页面被访问时，该页面的访问计数器就累加1，在发生缺页中断时，淘汰计数器值最小的那个页面。
缺点：
- 要增加一个计数器，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高
- LFU算法只考虑了频率的问题，但是没有考虑时间的问题，比如有些页面在过去的时间里访问频率很高，但是已经没有访问了。解决方法就是，可以定期减少访问的次数，比如当发生时间中断时，把过去时间的访问页面的访问次数除以2。也就是说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大被置换的概率。
磁盘调度算法
暂时不做梳理
参考
若有收获，就点个赞吧
0 人点赞
