页面置换算法

IV 页面置换算法 1 项目概述 2 全局页面置换算法 3 局部页面置换算法 4 产生引用串 5 性能评价 6 具体任务 5 附加任务的建议 1 项目概述 在本项目中，我们将实现不同的全局和局部页面置换算法，并利用随机产生的引用串一比较它们的相对性能。 2 全局页面置换算法 全局页面置换算法采用固定数目的页框。我们考虑一个单进程系统并做如下假设： · 进程的虚拟内存由P个页面组成，编号从0~P-1。 · 引用串RS是范围从0~P-1的的连续的整数。RS的每一个元素p示对页面p的一次引用。 · 内存由F个页框组成，编号从0~F-1。使用数组M[F]表示。数组的每一项M[f]包含当前驻留在页框f中的页面的页面号。 原理教材中讨论了几种不同的全局页面置换算法。每一个算法顺序读取RS的元素。对于RS中的每一个元素p，置换算法会搜索内存数组以便找到匹配的项，也就是要找到 一个f满足 2.1 内存 内存管理器要管理线性的物理内存。在开发管理器时，我们不必访问系统中实际的物理内存。相反，可以通过分配连续的字节序列来模拟物理内存，并开发用于模拟内存所需要的所有函数。这些函数使用指针而不是物理地址。 可以通过下面两种方法中的一种来创建大小为mem_size的内存： (1) 利用操作系统中的动态内存管理函数，如UNIX中，mm= malloc(mm_size)。 (2) 声明一个字符数组来表示物理内存，如mm[mm_size]。 在上面的两种情况中，我们可以得到大小为mm_size的连续字节序列——即被模拟的内存。指针mm对应于实际物理内存的物理地址0。在该内存数组中的所有空闲块和已分配的内存块都由内存管理器维护。（注意，只要诸如标志、大小和指针等不同类型的字段被写入内存或从内存读出，都必须用到类型转换。） 2.2 用户接口 内存管理器必须提供能够被其它进程调用的下列函数： (1) void *mm_request(int n) 此函数请求一个有n个连续字节的内存块。如果该请求得到满足，它返回指向被分配的内存块的第一个可用字节的指针。如果由于没有足够大的内存空闲块或参数非法（如为负数），该请求不能得到满足，它返回NULL。（注意，该函数同UNIX中的malloc函数相似。） (2) void mm_release(void *p) 此函数会释放先前分配的、由指针p所指向的内存块。为了防止内存碎片增多而形成更小的空闲块，如果释放的内存块同其它空闲块相连，该函数必须合并这些空闲块。如果释放的内存块被已分配的内存块围绕着，就简单地将它添加到空闲块列表中。（注意，该函数同UNIX中的free函数相似。） (3) void *mm_init(init mem_size 这个函数通过创建适当的标志、大小和指针域来将内存初始化为一个单一的空闲块。它会返回在2.1节中介绍的mm指针。 3 模拟试验 使用不同的分配策略实现两个或者更多版本的内存管理器。可能的选择有最先匹配、下一块匹配、最佳匹配或者最差匹配。然后设计并完成试验，该试验会根据以下原则比较所选择的分配策略的性能： (1) 内存的平均利用率； (2) 找到一个合适的空闲块所需要的平均步数。 为了建立模拟试验，我们有下面的假设。请求和释放调用在两个单独的队列中到达管理器。总是先处理释放调用力为任何释放都将马上得到满足，所以释放队列总是空的。一个请求调用是否能够得到满足依赖于是否有足够大的空闲块提供给此请求。如果没有，请求一直保留在队列上直到后面的释放操作释放了足够大的空间。请求队列以先进先出的次序处理；否则，就可能发生饥饿。 在这些假设下，我们可以模拟内存管理器的动作。开始状态是内存由已占用的内存和空闲块组成；没有释放请求，并且不足在队列最前面的请求。此时，管理器不能做任何动作，只能等待下一次释放请求。这一段时间内，内存分配情况不会发生变化。当处理下一次释放请求时，管理器试图满足在队列最前面的请求。如果失败，管理器会再一次等待下一次释放请求。如果请求成功，管理器马上试图满足队列中的下一个请求，等等。因此，在每一次释放请求后就会有零个或多个等待的请求得到满足，这依赖于被释放内存块的大小和挂起请求的大小。 为了评价不同分配策略的效率，我们必须假设内存一直被填充到最大容量。这就是说，我们假设请求流(request stream)是没有限制的，队列永远不会为空。 基于上面的假设，模拟试验的基本框架如下。它收集 了被选择的分配策略的性能统计信息。 (1) for (i=0;i<=sim_steps;i++) { (2) do { (3) Get_size n of next request; /*见3.1节*/ (4) Mm_request(n); } (5) while (request successful) (6) record memory utilization; /*见3.2节*/ (7) Select block p to be released; /*见3.3节*/ (8) mm_release(p) (9) } 程序由一个重复了许多次模拟步骤(sim_steps)的主循环(第1 行)所组成。外循每次迭代时，程序都会执行如下任务。内循环(第2 行~第5 行)试图尽量满足等待的请求。通过得到一个表示请求大小的随机数n(第3 行)来产生每次请求。 一旦请求失败，内存管理器必须等待，直到有下一个内存块被释放。直到那时，当前的内存分配情况不会再发生变化，这样我们就可以记录当前的内存使用情况了。（注意，我们做了隐含的假设，即内存块驻留在内存中的时间与内存块的大小是毫不相干的，因此，外循环的每上次迭代表示了一个固定的时间间隔，在此期间内存的使用情况不会发生变化。） 然后，迁中一个已经分配的内存块p并将其释放掉(第7 行~(第8 行)。这便释放了一些空间，允许模拟程序在下一次迭代时处理。 3.1 产生请求的大小 假设可以用高斯(Gaussian)分布得到请求的近似大小。因此，我们可以使用以下函数产生每次请求的大小n： n = gauss(a,d) 其中，aj是请求的平均大小，d是标准误差。（大多数的库都提供了一系列的这种分布函数。）选择a趋近0，就说明平均请求只会请求内存的很少字节；a比较大的时候说明进程一般请求内存中较大的内存块。标准误差决定了高斯曲线的形状。d比较小时将会产生陡峭的曲线，说明大部分请求都位于平均值附近；d比较大时，说明大小分布更加均匀。 如果不考虑a和d的值，那么n的数目范围就是从最小到正无穷。因此，我们必须截取一部分范围以反映实际的物理内存大小。这就是说，因为不可能满足超过整个内存大小的请求，所以只要n超过了mm_size，就将其丢弃。因为所有的内存块都一直比0大，所于我们也要丢弃n的所有负值（或者用其绝对值）。（理论上，大小为0的内存块是有可能，但是实际上是没有用的。） 3.2 收集有关性能的数据 我们必须收集两种类型的性能数据。内存利用率表示为已分配的空间同整个内存大小的比率。在模拟循环的每一次迭代中就可以得到这个值。这些值可以放在一个文件中，最后再平均之。另一种方法是在模拟程序每次运行时的平均值。 第二个性能值 是平均搜索时间，即满足请求所需要的步数。可以通过为每一种内存分配策略调用mm_request函数得到该值。必须记录每次请求时一定要检查的空闲块的数目，并计算在模拟程序运行期间的平均值。 3.3 选择要释放的内存块 如果假设给定内存块驻留在内存中的时间同其大小豪无关系，那么我们就可以在每次迭代中随机地选择要释放的内存块。模拟程序必须记录氖已分配的内存块。为了达到这个目的，链表是最合适的数据结构。如果在已分配的内存块队列中有k个元素，我们选择一个在1~k之间随机数p，并释放在队列位置p的内存块。 4 具体任务总结 （1） 设计并实现内存管理器的3个函数。至少实现两种不同的分配策略（最先匹配、下一块匹配、最佳匹配或者最差匹配）。 （2） 设计并实现一个驱动程序，以便测试和说明内存管理器的功能。 （3） 使用模拟试验评价所选择的分配策略的性能。生成一系列曲线，以说明内存平均利用率和平均搜索时间（满足请求的步骤）是如何随着平均请求大小的变化而变化的。对高斯函数中的参数a和d选择不同的值重复试验。 7 附加任务的建议 （1） 使用其他的分配策略进行试验，如将分配后剩下的空闲块的大小考虑在内的多种优化匹配策略。 （2） 使用请求大小的不同分布。例如，采用请求大小基本相同的分布，或者采用请求大小聚集在两个峰值（每个都用一个高斯函数表示）的周围的双峰分布。