页面置换算法以及磁盘服务算法

　　在操作系统发生缺页中断的时候，如果操作系统中没有空闲的页面，操作系统就必须在内存中选择一个页面将其移出内存。而操作系统中怎样选择淘汰的页面就要用到页面置换算法。在下文中我们将会讲解页面置换算法以及磁盘服务算法。。。。。。。

　　页面置换算法

　　请求分页系统中一进程P共有10页， 系统为其在内存中分配三个物理块，初始均为空，页面走向为

　　4，3，2，1，4，3，5，4，3，2，1，5。

　　FIFO置换算法(先进先出)

　　FIFO置换算法总是淘汰最先进入内存的页面，换句话说就是淘汰在内存中最久的页面。下面给出例子理解：

　　4,3,2,的时候各占一个内存，到1的时候产生缺页中断。根据FIFO置换算法，4是最先进入内存的，所以把页面4淘汰置换为页面1。在访问下一个页面4的时候内存中的页面3是最先进入内存的，所以淘汰页面3置换成页面4。后面的置换过程都是这样子置换。

　　OPT置换算法(最佳置换算法)

　　最佳置换算法是不能实现的，因为这种方法所选的淘汰页面为在后面最长的时间内不会被访问的页面。但是在一个进程在内存的若干个页面中，我们不能预知哪一个是最长时间不会被使用的，所以此算法无法实现。但是最佳置换算法理论上是最好的页面置换算法。例子：

　　在图中，页面4,3,2先占了三个内存空间，然后访问1页面的时候，判定页面4,3,2中页面2是在未来最长时间不会被使用的，所以把页面2淘汰置换为页面1。

　　在访问过程中总共缺页中断7次。

　　LRU置换算法(最久未使用算法)

　　顾名思义就是选择在内存中最久未被使用的页面予以淘汰。要注意的是：刚刚开始学习置换算法的朋友，遇到最久未使用和先进先出可能会有疑问。先进先出不就相当与最久未使用吗？其实两者是不同的，看例子：

　　在内存第二次访问页面2的时候把页面5给淘汰，因为下面的页面4和页面3虽然在内存中存在时间很久。但是它们在访问页面5之后又重新访问了一次页面4和页面3，所以页面5是最近最久未被使用的。

　　磁盘调度算法

　　磁盘是一种高速、大量旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，负担着繁重的输入输出任务，在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请示等待处理。

　　某盘面磁盘服务请求顺序如下：55,58,39,18,90,160,150,38,184号磁道(当前磁头在100号磁道上且向增加方向移动)。下面根据这个例子来分析按照先来先服务、最短寻道时间优先、扫描算法的执行顺序以及计算平均寻道距离。

　　先来先服务

　　顾名思义就是按请求顺序进行服务。特点：简单快速但是效率不高。

　　满足请求的次序是55，58，39，18，90，160， 150，38，184。

　　总寻道距离是：|55-100|+|58-55|+|39-58|+|18-39|+|90-18|+|160-90|+|150-160|+|38-150|+|184-38|=498

　　平均寻道距离：498/9=55.3

　　最短寻道时间优先

　　最短寻道时间优先算法就是哪个磁道距离磁头最近就优先服务哪个。

　　优点：改善磁盘平均服务时间

　　缺点：造成某些访问请求时间过长

　　满足请求的次序是：90，58，55，39，38，18， 150，160，184。

　　总寻道距离是：|90-100|+|58-90|+|55-58|+|39-55|+|38-39|+|18-38|+|150-18|+|160-150|+|184-160|=248

　　平均寻道距离：248/9=27.55

　　扫描算法(SCAN)

　　也称为电梯算法，就是先判断距离最近的需要的磁道，然后先服务这一边所有的磁道，再去服务另一边。

　　满足请求的次序是150，160，184，90，58，55，39，38，18。

　　总寻道距离：|150-100|+|160-150|+|184-160|+|90-184|+|58-90|+|55-58|+|39- 55|+|38-39|+|18-38|=250

　　平均寻道距离：250/9=27.8

      页面置换算法和磁盘服务算法其实很简单，只要你认真看几次就能明白，我把容易混淆的知识点都写出来了。虽然这些算法很简单，但是对于操作系统来说确是重要的算法。只有弄懂了在写程序或者做题目的时候才能很好的理解。