适合虚存环境的快速排序算法的性能研究（Performance of Quicksort adapted for virtual memory use）
作者：A. I.Verkamo Univ. of Helsinki, Helsinki, Finland
1.导论
在虚存环境中进行排序，内排序是一个可行的方法，即使是大型的排序问题。当进行排序时只有一部分数据村在主存中，这样，主存的大小就不受数据量大小的限制了。实验证明内排序在虚存中可以有效的对大型数据进行排序[1]。
快速排序被广泛的认为是一种有效的内排序算法。实验证明，快速排序在虚存环境中比其他的内排序更加快速[1,2,7]。并且它也被证明比其他算法占用主存更少。下面我们就来比较一下虚存中的内排序算法和外排序算法的性能。在虚存环境下的内排序和外排序的比较中发现，快速排序直接在虚存中工作并不比外排序要更好[11],虽然快速排序比归并排序要快，但是页交换却影响了整体的性能。如果通过延长页在主存中停留的时间来减少页面交换的次数，那么同归并排序相比，快速需要的内存就会变的太大而无法接受。
本论文解决的问题就是回答快速排序是否可以在虚存环境中可以更好的工作。这里将会用到几种方法来减少虚存中的页交换。还会考虑一些变数(variant)，比如待排序数据的大小的影响，虚存中的页大小的影响和内存管理参数。为了在虚存环境中获得比较好的性能，实现算法的程序应该具备局部性，例如，算法应该满足在很长一段时间内只需要它的地址空间中的一小部分，本文的目的就在于验证各种版本快速排序的局部性。
比较基于观察算法数次的模拟运行下的性能。使用模拟的环境是为了排除其他因素的干扰而客观的评价这些算法的性能。
2.虚存中的快速排序
我们来纵观虚存中的快速排序以期能够找到它的瓶颈。在这里我们使用工作集[见注1]来作为内存管理策略，它能比其他内存管理策略更好的适应算法的局部性特点的要求。这种替换策略可以使得很快将被用到的页保留在内存中。如果程序的局部性特点很明显，那么这种基于最近的过去的知识的预测将会很好的工作。工作集替换策略会假设进程所需要的页属于目前的工作集，例如，这些页在最后的i次引用中已经被引用了，i为窗口大小。在虚存环境下使用工作集替换策略的快速排序，算法的内存使用率为图1所示。
___________________________________________________________________________________________________________________
注1： 工作集策略(working set strategy，1968年由Denning提出)
引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整常驻集大小。常驻集指虚拟页式管理中给进程分配的物理页面数目。
1) 工作集的定义：工作集是一个进程执行过程中所访问页面的集合，可用一个二元函数W(t, D)表示，其中：t是执行时刻；D是一个虚拟时间段，称为窗口大小(window size)，它采用“虚拟时间”单位(即阻塞时不计时)，大致可以用执行的指令数目，或处理器执行时间来计算；工作集是在[t - D, t]时间段内所访问的页面的集合，| W(t, D) | 指工作集大小即页面数目。
2) 工作集的性质：
随D单调递增：W(t, D) Í W(t, D + a)，其中a>0；
工作集大小范围：1 £ | W(t, D) | £ min(D, n)，其中n是进程的总页面数。
3) 工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。
工作集大小的变化
4) 利用工作集进行常驻集调整的策略：
记录一个进程的工作集变化；
定期从常驻集中删除不在工作集中的页面；
总是让常驻集包含工作集。
5) 困难：
工作集的过去变化未必能够预示工作集的将来大小或组成页面的变化；
记录工作集变化要求开销太大；
对工作集窗口大小D的取值难以优化，而且通常该值是不断变化的。
_________________________________________________________________________________________________________________________________