计算机存储器的层次结构，磁盘调度算法，内存的页面置换算法
目录
先来先服务算法（FCFS）First Come First Service
最短寻道时间优先算法（SSTF） Shortest Seek Time First
先进先出页面置换算法（First In First Out，FIFO）
最近最久未使用（ Least Recently Used，LRU）置换算法
最不常用算法（LFU，Least Frequently Used）
计算机存储器的层次结构
存储系统是一个具有不同容量，成本和访问时间的存储设备的层次结构。
cpu 寄存器保存着最常用的数据。
靠近cpu的小的，快速的高速缓存存储器作为一部分存储在相对较慢速的主存储器（main memory，主存）中的数据和指令的缓冲区。
主存暂时存放容量较大的，慢速磁盘上的数据。而这些磁盘又常常作为存储在通过网络连接在其他机器或者设备上数据的缓冲区，是一个层次递进的关系。
作为一个程序员，需要理解存储器的层次结构，因为他对应用程序的性能有着巨大的影响。
如果你的程序需要的数据是存储在cpu的寄存器中的，那么在指令的执行期间，在0个周期内就能访问到它们。 如果是存储在高速缓存中，需要 1 - 30 个周期。 如果存储在主存中，需要50 - 200个周期。
而如果存储在磁盘上，需要大约几千万个周期。
这个思想围绕这计算机程序的一个称为 局部性 的思想。具有良好局部性的程序倾向于一次又一次的访问相同的数据项集合，或是倾向于访问临近的数据项集合。
每一层都保存下面一层的数据，相当于下面一层>上面一层，容量比上面一层大，但是速度比上面一层慢，这是成本和访问时间的平衡。
磁盘调度算法
磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：
先来先服务算法（FCFS）
最短寻道时间优先算法（SSTF）
扫描算法（SCAN）
循环扫描算法（CSCAN）
例:假定某磁盘共有200个柱面，编号为0-199，如果在为访问143号柱面的请求者服务后，当前正在为访问125号柱面的请求服务，同时有若干请求者在等待服务，它们每次要访问的柱面号为 86，147，91，177，94，150，102，175，130
先来先服务算法（FCFS）First Come First Service
这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。
此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
先来先服务 （125）86.147.91.177.94.150.102.175.130
最短寻道时间优先算法（SSTF） Shortest Seek Time First
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。
其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。
最短寻道时间优先（125）130.147.150.175.177.102.94.91.86
扫描算法（SCAN）电梯调度
扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。
由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。
电梯调度（125）102.94.91.86.130.147.150.175.177
循环扫描算法（CSCAN）
循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
循环扫描 （125）130.147.150.175.177.86.91.94.102
内存的页面置换算法
请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。
在请求分页系统中，只要求将当前需要的一部分页面装入内存，以便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过置换功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
最佳置换算法（Optimal，OPT）
所选择的被换出的页面将是以后永不使用的，或者是在最长时间内不再被访问，通常可以保证获得最低的缺页率。但是由于人们无法预知一个页面多长时间不再被访问，因此该算法是一种理论上的算法。最佳置换算法可以用来评价其他算法。
举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，根据最佳置换算法，页面 7 在第18次访问才需要调入，再次被访问的时间最长，因此会将页面 7 换出，后面的过程以此类推，具体过程如下图；
先进先出页面置换算法（First In First Out，FIFO）
选择换出的页面是最先进入的页面。该算法实现简单，但会将那些经常被访问的页面也被换出，从而使缺页率升高。
举例：仍使用上面的例子，使用FIFO算法进行页面置换，过程如下：
进行了12次页面置换，比最佳置换算法正好多一倍。
FIFO算法还会产生 当分配的物理块数增大而页故障数不减反增的异常现象，称为Belady异常。FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会。
最近最久未使用（ Least Recently Used，LRU）置换算法
虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出，它认为过去一段时间内未使用的页面，在最近的将来也不会被访问。
实现方式一：
在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面时最近最久未访问的。
实现方式二：
为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
使用和上面同样的实例，采用LRU算法进行页面置换：
LRU性能较好，但需要寄存器和栈的硬件支持，LRU是堆栈类的算法，理论上可以证明，堆栈类算法不可能出现Belady异常，FIFO算法基于队列实现，不是堆栈类算法。
第二次机会算法
FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
时钟算法（clock）
第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面链接起来，再使用一个指针指向最老的页面。
最简单的时钟策略需要给每一页框关联一个附加位，称为使用位。当某一页首次装入内存中时，则将该页页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。
该方法中，用于置换的候选页框集合（当前进程：局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针针与之相关联。当一页被置换时，该指针针被设置成指向缓冲区中的下一页框。当需要置换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一页框。每当遇到一个使用位为1的页框时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有页框的使用位均为0时，则选择遇到的第一个页框置换；如果所有页框的使用位均为1时，则指针针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，置换该页框中的页。当需要使用的页已经存在时，则指针不会受到影响，不会发生转动。
可见该策略类似于FIFO(先进先出)，唯一不同的是，在时钟策略中使用位为1的页框被跳过，该策略之所以称为时钟策略，是因为可以把页框形象地想象成在一个环中。许多操作系统都采用这种简单时钟策略的某种变体。
以下是一个使用实例，其中*号表示相应的使用位为1，红色单元格表示指针指向的位置
改进时钟算法
在页面中增加了修改位，1为修改过，0为未修改过。因为当发生缺页中断时，把未修改过的页面替换进外存就相当于把页面直接从内存中删除，因为内存和外存中所对应的该页面的内容相同，处理时间只有一次缺页中断访问外存的时间。而修改过的页面则还需要向外存中写入一次，再加上缺页中断的时间，相当于访问了两次外存，是上述未修改的两倍。所以避免把修改过的页面替换下去可以提高性能。
由访问位A和修改位M可以组合成下面四种类型的页面：
1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。
2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。
3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。
4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。
可能有人会发现第2类这种情况根本不会出现，如果一个页帧被修改，其修改位会被置1，同时它也被使用了，其使用位也会被置1；即不会出现被修改但是没有被使用的情况。真实情况是，页帧的使用位可能会被清零，这样第3组经过一次清零就会变成第2组。
算法执行如下操作步骤：
从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一类页(A=0，M=0)作为淘汰页。
如果第1)步失败，则开始第二轮扫描，查找(A=0，M=1)的第二类页。选择遇到的第一个这样的页作为淘汰页。在这个扫描过程中，对所有经过的页，把它的访问位A设置成0。
如果第2)步失败，指针将回到它的最初位置，并且集合中所有页的访问位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到被淘汰的页。
改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。
最不常用算法（LFU，Least Frequently Used）
是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
这种算法选择最近时期使用次数最少的页作为淘汰页。为每个页面配置一个计数器，一旦某页被访问，则将其计数器的值加1，在需要选择一页置换时，则将选择其计数器值最小的页面，即内存中访问次数最少的页面进行淘汰。
这种算法可能存在的问题是：有些也在进程开始时被访问的次数很多，但以后这些页可能不再被访问，这样的页不该长时间停留在内存中。解决这个问题的方法之一是定期的将计时器右移，以形成指数衰减的平均使用次数。
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
抖动