归并排序：

归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：

1）划分子表

2）合并半子表

首先我们来讨论归并算法，归并算法将一系列数据放到一个向量中，索引范围为[first,last],这个序列由两个排好序的子表构成，以索引终点（mid）为分界线，

算法函数为：

public void Merger(int[] v, int first, int mid, int last)
       {
           Queue<int> tempV = new Queue<int>();
           int indexA, indexB;
           indexA = first;
           indexB = mid;
           while (indexA < mid && indexB < last)
           {
               if (v[indexA] < v[indexB])
               {
                   tempV.Enqueue(v[indexA]);
                   indexA++;
               }
               else
               {
                   tempV.Enqueue(v[indexB]);
                   indexB++;
               }
           }

           while (indexA < mid)
           {
               tempV.Enqueue(v[indexA]);
               indexA++;
           }
           while (indexB < last)
           {
               tempV.Enqueue(v[indexB]);
               indexB++;
           }
           int index = 0;
           while (tempV.Count > 0)
           {
               v[first+index] = tempV.Dequeue();
               index++;
           }
       }

实现归并排序；归并排序算法分为两步，第一步：先将原来的数据表分成排好序的子表，然后调用 Merger 对子表进行归并，使之成为有序表，

一、最佳置换算法和先进先出置换算法

　　1. 最佳置换算法

　　最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。

　　假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

　　7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

　　进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。

　　2. 先进先出页面置换算法

该算法总是淘汰最先进入主存的页面，即选择在主存中驻留时间最长的页面予以淘汰。

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

　　1. LRU置换算法的硬件支持

　　1) 寄存器

　　为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3 … R2R1R0

　　2) 栈

简单来说：最近久未使用。调用页面最长时间，被淘汰出去。

某请求页式存储系统采用最近最久未使用（LRU）页面置换算法.一个作业的页面走向是0,1,2,3,1,4,3,1,0,3,4,5，012314310345 0 01 012,接下来要调入3,由最近久未使的是0,故为312(3换0),调入1,因为1在其中,所以不发生置换仍为312,整个过程：0 01 012 312（3换0） 312 314（4换2） 314 314 310(0换4) 310 340（4换1） 345（5换0）

三、两级页表

对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号。下面我们仍以前面的32位逻辑地址空间为例来说明。当页面大小为 4 KB时(12位)，若采用一级页表结构，应具有20位的页号，即页表项应有1兆个；在采用两级页表结构时，再对页表进行分页，使每页中包含210 (即1024)个页表项，最多允许有210个页表分页；或者说，外层页表中的外层页内地址P2为10位，外层页号P1也为10位。

为了地址变换实现上的方便起见，在地址变换机构中同样需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用P2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址

主要的两级页表的图由于格式问题没有办法上传所以主要实现理解其理论。