处理机管理
调度算法
先来先服务调度算法(first come first server,FCFS)
简介;先来先服务调度算法是最简单的调度算法,系统按照作业到达的先后次序进行调度。
优点:有利于长作业,适合繁忙的工作
缺点:不利于短作业
短作业优先调度算法(short job first,SJF)
简介:按照作业的长短来计算优先级,作业越短,优先级越高。
优点:有利于短作业
缺点:不利于长作业,长作业可能长时间得不到执行而“饿死”
优先级调度算法
该算法通过优先级决定顺序,优先级一般由外部决定(如用户)
高响应比优先调度算法(highest response ratio next,HRRN)
简介:优先级=(等待时间+要求服务时间)/要求服务时间
特点:如果作业等待时间相同,类似于SJF调度算法;如果作业要求服务时间相同,类似于FCFS调度算法;对于长作业的优先级,其可随等待时间的增加而提高,当作业的等待时间足够长时,也可以获得处理机
优点:实现了较好的折中
缺点:增加系统的开销
轮转调度算法(round robin,RR)
简介:该算法采用了非常公平的处理机分配方式,即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有n个进程,则每个进程每次大约可获得1/n的处理机时间
优点:非常公平
缺点:内存开销大
实时调度
最早截止时间优先算法(earliest deadline first,EDF)
简介:完成截止时间越早越优先,可以拥有抢占式调度方式也可以用于非抢占式调度方式。
最低松弛度优先算法(least laxity first,LLF)
简介:根据松弛度确定优先级,主要用于抢占式调度方式,当松弛度为0时发生抢占。松弛度=必须完成时间-其本身运行时间-当前时间,程序开始运行时松弛度不变。
存储器管理
动态分区分配
首次适应算法(first fit,FF)
简介:在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止
优点:有利于大作业,因为很多小作业在低址部分已经分区,在高址部分留下很多大的空闲空间
缺点:在低址部分留下很多难以利用的碎片,每次查找都从低址开始也增加了开销
循环首次适应算法(next fit,NF)
简介:从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区
优点:使内存中的空闲分区分布更加均匀,减小了查找空闲分区的开销
缺点:使得大的空闲分区比较缺乏
最佳适应算法(best fit,BF)
简介:每次分配时,总是把能满足要求的最小空闲分区分配给作业,为了加速寻找,所有空闲空间从小到大排序,排成一个空闲分区块
缺点:实际效果最差,会形成很多难以利用的碎片
最坏适应算法(worst fit, WF)
简介:在扫描整个空闲分区表或空闲分区链时,总是挑选一个最大的空闲区,从中分割一部分存储空间给作业使用,以至于存储器中会缺乏大的空闲分区。要求所有空闲分区按容量从大到小排成一个空闲分区链
优点:实际效果最佳,让剩下的空间不至于太小,产生碎片概率最最小,查找效率很高
页面置换算法
最佳页面置换算法(optimal,OPT)
简介:选择淘汰的页面,是以后永不使用或在未来很长时间内不会被访问的页面
优点:可以保证最低缺页率
缺点:不可能实现,因为无法预测未来,不过可以作为指标
先进先出页面置换算法(first in first out,FIFO)
简介:总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
优点:适合没有循环的程序
缺点:循环在程序里很常见,但是该算法遇到循环会频繁换页面,缺页率高
最近最久未使用页面置换算法(least recently used,LRU)
简介:将最近最久未使用的页面予以淘汰。
优点:实际效果好,缺页率较低
缺点:需要系统提供较多的硬件支持
最少使用页面置换算法(least frequently used,LFU)
简介:将最少使用的页面调出,在效果上和LRU一样
Clock页面置换算法
简介:LRU需要有较多硬件支持,所以大多时候使用LRU算法的近似算法,Clock就是其中之一。
过程:当使用该算法时,要为每页设置一个访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列即可。当某页被访问时,其访问页被置1。当选择一页进行淘汰时,只要检查页的访问位,如果是0就换出,是1置0暂不换出。
外部设备管理
磁盘调度算法
FCFS调度算法
简介:最简单的磁盘调度算法,根据程序请求访问磁盘的先后顺序进行调度。
优点:公平、简单
缺点:未对寻道进行优化,平均寻道时间可能较长。
SSTF调度算法
简介:最短距离优先
优点:相较于FCFS有更好的性能
缺点:不能保证平均寻道时间最短,容易导致饥饿现象。
SCAN调度算法
简介:SCAN算法不仅考虑距离,还优先考虑当前磁头移动方向。
优点:平均寻道时间短,相比SSTF避免饥饿。
缺点:当磁头恰好在一个区域临近相反方向移动,读取需要很长时间。
CSCAN算法
简介:当磁头移动到最外面立刻回到最里面要访的磁头。
优点:更加公平
缺点:时间较长