北邮操作系统第二次实验

《北邮操作系统第二次实验》由会员分享，可在线阅读，更多相关《北邮操作系统第二次实验（21页珍藏版）》请在金锄头文库上搜索。

1、北京邮电大学 操作系统实验 实验报告班号：2011211314姓名：oneseven学号： 实验日期： 实验名称：操作系统实验一、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解 存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实 现过程，并比较它们的效率。二、实验内容1. 实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。实验准备用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统 计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。2. 设计一个虚拟存储区和内存工作区，并使用

2、下述算法计算访问命中率。1) 最佳置换算法(Optimal)2) 先进先出法( Fisrt In First Out)3) 最近最久未使用( Least Recently Used)4) 最不经常使用法( Least Frequently Used)其中，命中率=1 页面失效次数/页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。实验准备本实验中主要的流程：首先用srand()和rand()函数定义和产生指令序列，然后将指令 序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验可先从一个具体的例子出发。(1) 通过随机数产生一个指令序列，

3、共2048 条指令。指令的地址按下述原则生成：A： 50%的指令是顺序执行的B： 25%的指令是均匀分布在前地址部分C： 25%的指令是均匀分布在后地址部分具体的实施方法是：A：在0, 1023的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为mD：顺序执行一条指令，其地址为m+1E：在后地址m+2, 2047中随机选取一条指令并执行F：重复步骤A-E，直到2048次指令(2) 将指令序列变换为页地址流设：页面大小为 4K； 用户内存容量4页到32页； 用户虚存容量为32K。在用户虚存中，按每K存放64条指

4、令排列虚存地址，即2048条指令在虚存中的存放 方式为：第0条-第63条指令为第0页(对应虚存地址为0， 63) 第64条-第127条指令为第1页(对应虚存地址为64， 127)第 1984 条 -第 2047 条指令为第 31 页（对应虚存地址为1984， 2047） 按以上方式，用户指令可组成32 页。以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时的情形3. 实现内存的 slab 分配器：其基本思想是：一次向内核获取整数页，slab根据数据结构的大小进行划分为一个个小 的数据结构，当需要时直接从该链表上摘取一个返回应用程序，当应用程序释放时，而非真 正释放，只需要该空间放

5、回到链表中，当分散的一页多块又聚集一页时，又会拼成一页，同 时判断 slab 空闲的页数，如果空闲页超过一定的页数，就会向系统释放一定的页数。一个 slab 分配器只能管理一个指定大小的数据结构分配。三、项目要求及分析3.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为2m个字（地址从0到2m-l）,则在开始运行时，整个内 存区是一个大小为2m的空闲块，在运行了一段时间之后，被分隔成若干占用块和空闲块。 为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一 个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用

6、向量结构组织成一个表， 这就是伙伴系统中的可利用空间表，如图所示：分配算法：当用户提出大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子 表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大 的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插 入相应的子表中。若2k-i n 2 k-1，又第k+1个子表不空，则只要删除此链表中第一个结点并分配给用 户即可；若2k-2 n 2k-1-1，此时由于结点大小为2k-1的子表为空，则需从结点大小为2k的 子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为

7、 2k-1的子表中，若2k-i-1 n 2 k-i-1（i为小于是的整数），并且所有结点小于2k的子表均为空, 则同样需从结点大小为2k的子表中取出一块，将其中2k-i的一小部分分配给用户，剩余部分 分割成若干个结点分别插入在结点大小为2k-1、2k-2、2k-i的子表中。回收算法：在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中去。这 里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴” 的两个空闲块的归并。何谓“伙伴”?如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存 储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”

8、。例如：假设p为大小为pow(2,k) 的空闲块的初始地址，且p MOD pow(2,k+l)=0，则初始地址为p和p+pow(2,k)的两个空闲 块互为伙伴。在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说， 若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一 起。由此，在回收空闲块时，应首先判别其伙伴是否为空闲块，若否，则只要将释放的空闲 块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别 合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时， 再插入到相应的子表中去。3. 2.设计

9、一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 页式虚拟存储器实现的一个难点是设计页面调度(置换)算法，即将新页面调入内存时， 如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的 物理页释放出来，供新页面使用。页面替换算法主要用于如下几个地方：(1) 虚拟存储器中，主存页面(或程序段)的替换。(2) Cache 中的块替换。(3) 虚拟存储器的快慢表中，快表的替换。(4) 虚拟存储器中，用户基地址寄存器的替换。在虚拟存储器中常用的页面替换算法有如下几种：(1)最优替换算法，即OPT算法(OPTimal replacement algorithm)。上面

10、介绍的几种页 面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中 的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不 总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换 算法的命中率一定是最高的，它就是最优替换算法。要实现 OPT 算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根 据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此， OPT 算 法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来 作为评价其它页面替换算法好坏的标准。在其它条

11、件相同的情况下，哪一种页面替换算法的 命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。(2) 先进先出算法，即 FIFO 算法( First-In First-Out algorithm )。这种算法选择最先调入 主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调 度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是 经常要使用的页面。(3) 最久没有使用算法，即LRU算法(Least Recently Used algorithm)o这种算法把近期 最久没有被访问过的页面作为被替换的页面。它把 LFU 算法中要记录数量

12、上的多与少 简化成判断有与无，因此，实现起来比较容易。(4) 近期最少使用算法，即LFU算法(Least Frequently Used algorithm )。这种算法选择 近期最少访问的页面作为被替换的页面 显然，这是一种非常合理的算法，因为到目前为止 最少使用的页面，很可能也是将来最少访问的页面 该算法既充分利用了主存中页面调度情 况的历史信息，又正确反映了程序的局部性 但是，这种算法实现起来非常困难，它要为每 个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数 在选择 被替换页面时，要从所有计数器中找出一个计数值最大的计数器 因此，通常采用如下一种相对比较简单的方

13、法。3.3实现内存的slab分配器slab 描述符和空闲对象管理 部分成为 slab 的管理部分，也可以称为 slab 头slab 的头可以放在 slab 自身，也可以放在 slab 之外。如果 slab 头放在了 slab 之外，那么用户申请obj时，需要首先访问slab头，slab头提供未使用free obj的指针然后再访问这个free obj的地址。完成这项工作需要访问2个页块。会带来效率上的损失。 slab头始终位于slab也存在问题，比如一个页面只有4K, objsize = 2K,那么slab头在slab 上，就意味着，这个4K的页面只能够 分配一个obj。造成了内存的浪费。如果

14、页数太少，存放的 obj 个数少，那么 增加管理开销，同时 内存使用率低，如果页数 太多对伙伴内存系统不好，所以需要一定的策略妥协。这个妥协过程是有 calculate_slab_order 这个函数来实现的。从 0 阶（即一页）到kmalloc 的最高阶 KMALLOC_MAX_ORDER，挨个尝试，由 cache_estimate 这个函数计算 如果选用order阶，那么能分配 多少个obj （num），剩余空间是多少（remainder）。所谓剩余空间，就是除去slab头（如果有的话），除去obj*num，剩下的边 角料空间是多少。 需要分成两种情况去计算，分成两种情况的原因，很快就能看

15、到A）slab 头不在 slab 上，即 flag & CFLGS_OFF_SLAB = 1 的时候 这种情况比较简单，由于管理数据完全不在slab 上,size_t slab_size = PAGE_SIZE gfporder;nr_objs = slab_size / buffer_size;B）slab头在slab上，这种情况稍复杂,原因是slab头里面有个除了固定大小的slab描 述符，还有个空闲对象管理数组，这个数组的大小取决于obj的个数。但obj的个数又取 决于 slab 头大小。换句话，slab头的大小取决于obj的个数，obj的个数取决于slab头的大小，四、具体实现4.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。 程序：#include #include #include #define MIN_MOMORY_SIZE 536870912#define WORKTIME 1500#define MAX_REQ_SIZE 268435456#define MIN_DUE 30#define MAX_DUE 90#define OCCUPY_INTERVAL 60#define USED 1#define UNUSED 0/随机产