操作系统里的算法
处理机管理
调度算法
先来先服务调度算法(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算法
简介：当磁头移动到最外面立刻回到最里面要访的磁头。
优点：更加公平
缺点：时间较长