调度算法

链接

分区分配算法

给出每个进程的大小，分区编号、起始地址、分区大小

找到分区编号的起始地址就是进程的分配的地址，然后操作（起始地址加上进程大小，分区大小减去进程大小）

首次适应（first）

根据分区编号从小到大进行匹配，找到第一个分区大小大于等于进程大小的分区编号

最佳适应

根据分区大小从小到大进行排序，依次从小到大匹配，找到第一个分区大小大于等于进程大小的分区，注意此排序是动态排序的

循环首次适应（next）

在首次适应的基础上，根据分区编号从小到大进行匹配，下次就从当前分区的下一个进行匹配

最坏适应（worst）

根据分区大小从大到小进行排序，依次从大到小进行匹配，找到第一个分区大小大于等于进程大小的分区，注意此排序是动态排序的，如果第一个不匹配了就不找了，所以他的效率很高

页面置换算法

先进先出置换（FIFO）

选择在内存驻留时间很长的页面进行中置换

一般来说直接把第一个换掉就可以了

最佳页面置换（OPT）

置换未来最长时间不访问的页面

从当前点开始，从左往右找，最后出现的值替换掉，如果有多个没找到就替换第一个

最近最久未使用（LRU）

置换最近最久未使用的页面

从当前点开始，从右往左找，最后出现的值替换掉

磁盘调度算法

参考

给你一个磁盘和磁盘磁道的范围，然后再给你一个请求队列，里面是要访问的磁道，要你求磁头的移动顺序。

平均寻道长度就是磁头在访问两个磁道之间需要移动的插值和，再除以请求次数

先来先服务（FCFS）

按照请求队列的顺序服务，磁头的根据磁道进行移动

最短寻道时间有限（SSTF）

磁头移动时是根据当前访问的磁道，寻找离队列中还未访问的最近的磁道，所谓最近就是两个磁道差值最小

扫描算法（Scan）

磁头在一个方向上移动，访问所有未完成的所有请求，直到磁头到达该方向上的最后磁道（也就是磁道范围的左边界和右边界），才调换方向

比如从当前访问的磁道（A）一直从左访问，访问到磁盘范围的左边界，然后从A的右边一直访问直到右边界，这里前提是给请求队列中要访问的磁道排好顺序了

循环扫描算法（Sscan）

这种算法和上面的scan相比，磁头有没有调换方向

scan磁头先是往左再往右；sscan磁头是一直往某个方向，比如往右

scan反向移动响应请求，sscan不会响应任何请求

磁头往某一个方向（右）移动，返回时直接快速移动至最靠边缘（左边界）的位置，然后继续移动，该算法的特点，就是磁道只响应一个方向上的请求

LOOK算法

对scan算法的优化，优化的思路就是磁头在移动到最远请求的位置，然后立即反向移动

CLOOK算法

对sscan算法的优化，优化的思路就是磁头在移动到最远请求的位置，然后立即反向移动,而不需要移动到磁盘的最始端或最末端

进程调度算法

平均周转时间、平均带权周转时间

平均周转时间 = 完成时间 - 到达时间

平均带权周转时间 = 平均周转时间 / 服务时间