操作系统-小林coding-调度算法
Contents
本系列笔记为作者在跟随小林coding学习的时候做的笔记。感谢小林大大。
进程调度算法
按是否抢占
分为抢占式和非抢占式
按具体策略
先来先服务调度算法（First Come First Severd, FCFS）
从就绪队列选择队列头的进程运行，当前进程退出或被阻塞再从队列中选择队列头的下一个进程运行
最短作业优先调度算法（Shortest Job First, SJF）
优先选择运行时间最短的进程来运行
高响应比优先调度算法（Highest Response Ratio Next, HRRN）
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行
响应比=（等待时间+要求服务时间）/要求服务时间
时间片轮转调度算法（Round Robin, RR）
运行进程被分配一个时间段，称为时间片（Quantum），允许该进程在该时间段中运行
最高优先级调度算法（Highest Priority First，HPF）
从就绪队列中选择最高优先级的进程运行
静态优先级：不变化
动态优先级：按时间增加优先级
多级反馈队列调度算法（Multilevel Feedback Queue）
队列优先级从高到低，优先级越高时间片越短
内存页面置换算法
当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面
最佳页面置换算法
置换在「未来」最长时间不访问的页面，不现实
先进先出置换算法
选择在内存驻留时间很长的页面进行中置换
最近最久未使用的置换算法（LRU）
选择最长时间没有被访问的页面进行置换
实现使用双向链表和哈希表即可
时钟页面置换算法（Clock）
页面保存在一个类似钟面的「环形链表」，表指针指向最老的页面
访问页面时将访问位设为1
淘汰页面时，表指针遇到访问位为0则选择，遇到访问位为1则设置为0，并转到下一个
最不常用算法（LFU）
选择「访问次数」最少的那个页面，并将其淘汰
实现在LRU的基础上（双向链表和哈希表）给哈希表的值添加一个访问次数和时间的字段（访问计数器）
磁盘调度算法
先来先服务（First-Come，First-Served，FCFS）
先到来的请求，先被服务
最短寻道时间优先Shortest Seek First，SSF）
优先选择从当前磁头位置所需寻道时间最短的请求
可能产生饥饿，磁头在一小块区域来回移动
扫描算法（Scan）
磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向
循环扫描算法（Circular Scan, CSCAN ）
返回中途不处理任何请求，磁道只响应一个方向上的请求
LOOK 与 C-LOOK算法
LOOK：扫描算法基础上，磁头在移动到「最远的请求」位置，然后立即反向移动
C-LOOK：循环扫描算法基础上做相同的优化