小林图解系统调度算法

进程调度算法：

CPU空闲时，操作系统选择内存中的某个就绪状态的进程，并给其分配CPU;

调度算法影响等待时间(进程在就绪队列中等待调度的时间和)，并不影响进程真正使用CPU的时间和I/O时间。

调度算法

• 先来先服务，FCFS，可能有一个长作业，后面短作业都得等着
• 短作业优先(SJF)：也就是运行时间越短(占CPU的时间)的任务先完成，长作业可能一直等待
• 高相应比优先(HRRN)：优先权 = (等待时间 + 要求服务时间) / 要求服务时间。要求服务时间小，有利于短作业；等待时间长，兼顾到了长作业的运行；
• 时间片轮转(RR)：每个线程分配一定时间，没执行完也会切换下一个，时间片过长，退回到FCFS
• 高优先级(HPF)：业务按照优先级处理，运行时间越长，降低其优先级。等待时间越长，提高其优先级
• 多级反馈队列(MFQ)：优先级越高时间片越短，如果长作业到了高优先级没有轮到，会将其放到此优先级的队列末尾，这样虽然等待时间增长，但是轮到自己可以运行的时间也变长了，算是一种平衡。

内存页面置换算法：

当CPU访问的页面不在物理内存时，就需要去磁盘中找，

如果第4步内存没有空闲页可用了，就说明内存已经满了，这时候就需要页面置换算法选择一个物理页，如果物理页是脏页，就需要把它换出到磁盘，然后把置换出去的页表项的状态改成无效的，最后把正在访问的磁盘中的页面装入到物理内存中。

页表项通常有如下字段：

• 状态位：用于表示该页是否有效，也就是说是否在物理内存中，供程序访问时参考。
• 访问字段：用于记录该页在一段时间被访问的次数，供页面置换算法选择出页面时参考。
• 修改位：表示该页在调入内存后是否有被修改过，由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，在置换该页时就不需要将该页写回到磁盘上，以减少系统的开销；如果已经被修改，则将该页重写到磁盘上，以保证磁盘中所保留的始终是最新的副本。
• 硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用。

页面置换算法的功能是：出现缺页情况，需要在硬盘调入新页面，但是内存已满了，这时候选择被置换的物理页面。常见的页面置换算法如下：

• 最佳页面置换算法(OPT)：置换未来最长时间不访问的内存，但是实际很难实现
• 先入先出置换算法(FIFO):内存中驻留时间最长的置换
• 最近最久未使用置换算法(LRU)：最长时间没被访问的页面置换，开销比较大
• 时钟页面置换算法(Lock)：和LRU类似，把所有页面保存在一个类似钟面的环形链表中，表针指向最老的页面。
• 最不常用置换算法(LFU)：选择访问次数最少的页面淘汰

磁盘调度算法：

主要目的是提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序实现的；常见的磁盘调度算法有：

• 先来先服务算法：寻道距离过远
• 最短寻道时间优先算法：有限选择从当前位置所需寻道时间最短的请求，可能存在磁头一直在一小块区域移动，产生饥饿；
• 扫描算法：磁头在一个方向扫描到头，直到到达该方向最大的磁道，才调转方向，但是这样每个磁道相应的频率存在差异，中间的磁道更易被访问，存在公平性问题。
• 循环扫描算法：先向磁道增加的方向移动，到了最右端的磁道后复位。解决了扫描算法的公平性问题。
• LOOK和C-LOOK算法：扫描算法和循环扫描算法的优化，不用扫描到所有的磁道，而是最远的请求位置。