进程调度算法 & 内存页面置换算法 & 磁盘调度算法

进程调度算法

• 先来先服务
  • 适用于 CPU 繁忙型，不适用于 I/O 繁忙型
• 短作业优先
  • 长作业饿死
• 长作业优先
  • 短作业饿死
• 高响应比优先
  • 理想场景
• 时间片轮转
  • 时间片划分要合理
• 高优先级优先
  • 低优先级饿死
• 多级反馈队列
  • 时间片轮转 + 高优先级

内存页面置换算法

• 最佳页面置换
  • 未来最长时间不访问的页
  • 理想场景
• 先进先出置换
  • 在内存驻留时间最长的页
• 最近最久未使用置换
  • LRU，最长时间未被访问
• 时钟页面置换
  • LRU + FIFO
• 最不常用置换
  • LFU，访问次数最少的页

页表项数据结构：

• 状态位：表示该页是否有效，即是否在物理内存中
• 访问字段：记录访问次数
• 修改位：表示该页在写入内存后是否有被修改过，若没有则置换该页时就无需将该页写回到磁盘，因为磁盘上仍保留其最新的副本数据，若有则还需将该页重写回磁盘，以保证数据的一致性

磁盘调度算法

磁盘的 I/O 操作通常是相对较慢的，其中寻道（即磁盘读取/写入头移动到目标位置的过程）是最耗时的部分之一。因此，磁盘调度算法的核心目标是尽可能减少寻道次数，以提高磁盘 I/O 的效率。

• 先来先服务
  • FCFS，按请求到达的顺序进行服务，简单但可能导致较长的寻道时间
• 最短寻道时间优先
  • SSTF，优先处理距离当前位置最近的请求，可以减少平均寻道时间，但可能导致饥饿现象，因为磁头在一小块区域来回移动
• 扫描算法
  • SCAN，电梯算法，磁头像电梯一样在磁盘上来回移动，服务所遇到的每个请求，减少了寻道时间，但可能会增加等待时间
  • 磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向
  • 中间部分的磁道会比较占便宜，因为中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异
• 循环扫描算法
  • C-SCAN，类似于 SCAN，但每次到达一端后直接返回起始端，而不服务中间请求，保证了服务的一致性
• LOOK & C-LOOK 算法
  • 针对 SCAN 算法的优化则叫 LOOK 算法，它的工作方式是：磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求
  • 针对 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式是：磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求