5.调度算法

5.1说说进程调度算法有哪些？

进程是由CPU调度的，当CPU空闲时，操作系统就选择内存中某个就绪状态的进程，并给其分配CPU。
（1）先来先服务调度算法

每次从就绪队列中选择最先进入队列的进程，然后一直运行，直到进程退出或者被阻塞，才会继续从队列中选择第一个进程接着运行；FCFS对长作业有利，使用于CPU繁忙型作业的系统，不适用于IO繁忙型的系统；
（2）最短作业优先调度算法

优先选择运行时间最短的进程来运行，提高系统的吞吐量。但是这对长作业不利，很容易造成这种极端现象：一个长作业在就绪队列中等待运行，但这个就绪队列中很非常多的短作业，导致长作业一直得不到运行，周期时间变长；
（3）高响应比优先调度算法

主要是权衡了短作业和长作业。
如果两个进程的等待时间相同，要求服务的时间越短，响应比越高，这样短作业的进程容易被选中；
如果两个进程的要求服务时间相同，等待时间越长，响应比越高，这样也能兼顾到长作业进程，因此进程的响应比可以随着等待时间的增加而提高，当它等待了足够长的时间后，它的响应比会达到很高的值，从而得到CPU调度的机会。
（4）时间片轮流调度算法

每个进程被分配一个时间片，允许该进程在该时间范围内运行，时间片的时间通常为20ms-50ms。
如果时间片用完，进程还在运行，此时就会把该进程从CPU释放出来，并把CPU分配给另外一个进程运行；
如果该进程在时间片结束前阻塞或结束，则CPU立刻进行切换；
（5）最高优先级调度算法
前面的时间片轮转算法，让所有进程的地位相等，不偏袒谁，而且大家的运行时间都是一样的。但是在多用户计算机系统中，它希望调度是有优先级的，希望系统能从就绪队列中优先选择最高优先级的进程运行；
静态优先级：创建进程的时候，就已经确定优先级了，优先级不会改变；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果等待时间增加，就升高其优先级。
非抢占式：当就绪队列中出现了优先级高的进程，运行完当前进程，再选择优先级高的进程运行；
抢占式：当就绪队列中出现了优先级高的进程，当前进程挂起，调度优先级高的进程运行；
（6）多级反馈队列调度算法
多级表示有多个队列，每个队列的优先级从高到低，同时优先级越高，分配的时间片越短；反馈表示如果有新的进程加入到优先级高的队列时，立刻停止当前运行的进程，转而去运行优先级高的队列中的进程；

5.2说说内存页面置换算法有哪些？

当CPU访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页面调入到物理内存。

（1）CPU执行一条Load M的指令，然后CPU会去找M所对应的页表项；
（2）如果该页表项是有效地，那CPU就可以直接访问物理内存了；如果状态是无效的，则CPU会发送缺页中断请求；
（3）操作系统收到缺页中断请求后，执行缺页中断处理函数，查找该页面在磁盘中的位置；
（4）找到磁盘中对应的页面后，将该页面置换到物理内存，但是在置换之前需要先找到空闲页，如果找到空闲页，就把页面置换到物理内存中；
（5）页面从磁盘换入到物理内存后，对应的页表项改成有效的；
（6）CPU重新执行指令。

当执行(4)时，如果没有找到空闲页，就需要选择一个物理页面换出到磁盘，然后把新访问的页面换入到物理内存；
（1）最佳页面置换算法
基本思路是置换未来最长时间不访问的页面，这个是理想状态的算法，在实际的操作系统是不可能实现的，因为操作系统也不知道下一时刻会访问哪个页面。
（2）先进先出置换算法
基本思路就是选择在内存中驻留了最久的页面进行置换；
（3）LRU(最近最少使用置换算法)
LRU在理论上是可以实现的，但是代价比较高。为了完全实现LRU，需要在内存维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾；
（4）时钟页面置换算法
基本思路是，把所有的页面都保存在一个环形链表中，一个表针指向最老的页面。当发生缺页异常时，首先检查表针指向的页面，如果访问位是0就淘汰该页面，并把新的页面插入到这个位置，然后把表针往前移一个位置；如果访问位是1就将访问位置为0，然后把表针顺时针移动一个位置，直到这个过程找到了一个访问位为0的页面为止；

（5）LFU算法(最少频次置换算法)
基本思路是，对每个页面设置一个访问计数器，当一个页面被访问时，访问计数器就+1。在发生缺页中断时，淘汰计数器就小的那个页面。但是这个代价其实也是挺高的，每个页面都需要维护一个访问计数器，需要考虑硬件成本。