操作系统算法汇总

《操作系统算法汇总》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章 ①作业调度和低级调度算法P126：1.先来先服务算法FCFS（非剥夺）调度策略：先来先服务2.最短作业优先算法SJF（非剥夺）调度策略：选择预计使用CPU时间最短的作业3.最短剩余时间优先算法SRTF（剥夺）调度策略：若新到来的进程所需CPU时间较短则选择新进程执行4.响应比最高优先算法HRRF（非剥夺）调度策略：每执行完一个作业计算剩余作业的响应比（1+等待时间/处理时间，此处的处理时间指的是所需CPU总时间而非已经执行的时间），选择响应比最高者执行5.优先级调度算法（剥夺/非剥夺，由系统决定）调度策略：就绪队列中出现优先级更高的进程时：剥夺：直接执行该高优先级进程；非剥夺

2、：等CPU执行完当前进程之后再执行高优先级进程。优先级的确定可采用静态和动态两种方案静态：优先级确定之后不变，会引起饥饿；动态：等待越久优先级越高，防止饥饿。6.轮转调度算法RR（剥夺）调度策略：即时间片轮转法7.多级反馈队列调度MLFQ（非剥夺）调度策略：设置多个优先级队列，优先执行高优先级队列中的进程。高优先级分配较短时间片，低优先级分配较长时间片。会饥饿。8.彩票调度算法（非剥夺）调度策略：给不同进程分配多张彩票，系统每秒钟抽奖N次，抽中了你的彩票你可以获得1/N秒的执行时间。卖萌用，考试应该不考（误。②实时调度算法P133：1.单比率调度算法2.限期调度算法3.最少裕度法第三

3、章银行家算法系统现在有若干资源，有若干进程想要占用这些资源，你知道的是他们分别想要多少资源和各自已经占用的多少资源，要求得出一个不会让系统出BUG的安全队列。然后你就开始找安全队列了，一般安全队列都有几种十几种，正常情况下都能找到。注意若分配完最后一个进程的资源后系统无法再满足任一进程的资源需求（系统现有资源+已分配资源<进程总需求量）则该安全队列不成立。找到一个安全队列之后第二小题会让你判断一个进程的资源申请能否获得批准。首先你先看该进程的请求是否小于等于它的剩余需求量(request<=总需求-已分配)，以及请求是否小于系统可用资源量。满足以上两个条件之后根据请求修改该进程的已分

4、配资源量和当前系统可用资源量，然后再排一次安全队列，存在安全队列的话请求就是合法的。第四章①全局页面替换算法P264：1.最佳页面替换算法OPT替换策略：替换以后不再访问或距现在最长时间不访问的页面2.先进先出页面替换算法FIFO替换策略：先进先出3.最近最少使用页面替换算法LRU替换策略：替换最近一段时间内最久未被使用的页面模拟方法1：最近未使用页面替换算法NRU（引用位）模拟方法2：计数器法4.第二次机会页面替换算法SCR（引用位）替换策略：引用>什么都没做5.时钟页面替换算法Clock（引用位）替换策略：引用>什么都没做6.改进的时钟页面替换算法（引用位+修改位）替换策略：引用

5、>修改>什么都没做②局部页面替换算法P270：1.局部最佳页面替换算法MIN（滑动窗口）替换策略：移出在未来t时间内未被引用的页面2.工作集WS（滑动窗口）替换策略：移出在之前t时间内未被引用的页面3.模拟工作集替换算法模拟WS（引用位+年龄寄存器）替换策略：每隔t时间，寄存器右移1位，引用位放入寄存器最高位，移出那些寄存器内容为0的页面。4.缺页频率替换算法PFF（引用位）替换策略：移出在时间间隔大于t的两次缺页中断之间未被引用的那些页面③可变分区主存管理P239 1.最先适应分配算法firstfit 分配策略：顺序查找未分配区，使用第一个满足长度要求的区域，占用一部分，另一部分给

6、未分配区 2.下次适应分配算法nextfit 分配策略：从上次查找结束的地方开始继续查找，其余同firstfit 3.最优适应分配算法bestfit 分配策略：找能满足要求的最小未分配区 4.最坏适应分配算法worstfit（利于中小型作业） 分配策略：找能满足要求的最大的未分配区 5.快速适应分配算法quickfit 分配策略：系统建立一个常用长度空闲区链表，链表表项分别指向对应长度的空闲区链表表头，查找时取相应长度的空闲区链表的第一项存放。 第五章 ①磁盘的搜查定位算法P327 1.先来先服务算法FCFS 搜查策略：FCFS 2.电梯调度算法（饥饿） 搜查策略：选择当前移动方向上

7、最近的柱面进行搜查，当一个方向上没有请求之后才往另一个方向搜查3.最短查找时间优先算法（饥饿） 搜查策略：选择最靠近磁头的请求进行搜查 4.扫描算法（不饥饿） 搜查策略：每次朝一个方向移动扫过所有柱面，处理遇到的所有请求，之后再折回来，如此循环 5.分布扫描算法（不饥饿） 搜查策略：先将请求分组，再执行扫描算法，每次只处理一个分组的请求。 6.循环扫描算法（不饥饿） 搜查策略：每次都从0号柱面开始扫描到最大柱面，处理又遇到的所有请求，然后直接从最大柱面返回