操作系统里的算法

处理机管理

调度算法

先来先服务调度算法(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算法

简介：当磁头移动到最外面立刻回到最里面要访的磁头。

优点：更加公平

缺点：时间较长