北邮操作系统第二次实验

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

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

2、存失败时区分实际空间不足和由于碎片而不能满足。2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1) 最佳置换算法（Optimal） 2) 先进先出法（Fisrt In First Out） 3) 最近最久未使用（Least Recently Used） 4) 最不经常使用法（Least Frequently Used） 其中，命中率页面失效次数页地址流长度。 试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比 较。实验准备 本实验中主要的流程：首先用 srand( )和 rand( )函数定义和产生指令序列，然后将指令 序列变换成相应的页地址流，并针

3、对不同的算法计算出相应的命中率。 实验可先从一个具体的例子出发。 (1)通过随机数产生一个指令序列，共 2048 条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在0，1023的指令地址之间随机选取一起点 m B：顺序执行一条指令，即执行地址为 m+1 的指令 C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为 m D：顺序执行一条指令，其地址为 m+1 E：在后地址m+2，2047中随机选取一条指令并执行 F：重复步骤 A-E，直到 2048 次指令 (2)将

4、指令序列变换为页地址流 设：页面大小为 4K； 用户内存容量 4 页到 32 页； 用户虚存容量为 32K。 在用户虚存中，按每 K 存放 64 条指令排列虚存地址，即 2048 条指令在虚存中的存放 方式为： 第 0 条-第 63 条指令为第 0 页（对应虚存地址为0，63） 第 64 条-第 127 条指令为第 1 页（对应虚存地址为64，127）2 第 1984 条-第 2047 条指令为第 31 页（对应虚存地址为1984，2047） 按以上方式，用户指令可组成 32 页。以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时的情形。3. 实现内存的 slab 分配器： 其基

5、本思想是：一次向内核获取整数页，slab 根据数据结构的大小进行划分为一个个 小的数据结构，当需要时直接从该链表上摘取一个返回应用程序，当应用程序释放时，而 非真正释放，只需要该空间放回到链表中，当分散的一页多块又聚集一页时，又会拼成一 页，同时判断 slab 空闲的页数，如果空闲页超过一定的页数，就会向系统释放一定的页数。 一个 slab 分配器只能管理一个指定大小的数据结构分配。三、项目要求及分析三、项目要求及分析3.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为 2m个字

6、(地址从 0 到 2m-1)，则在开始运行时，整个 内存区是一个大小为 2m的空闲块，在运行了一段时间之后，被分隔成若干占用块和空闲块。 为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是 一个双重链表，这样的链表可能有 m+1 个，将这 m+1 个表头指针用向量结构组织成一个 表，这就是伙伴系统中的可利用空间表，如图所示：分配算法： 当用户提出大小为 n 的内存请求时，首先在可利用表上寻找结点大小与 n 相匹配的子 表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更 大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而

7、将剩余部 分插入相应的子表中。若 2k-1 #include #include #define MIN_MOMORY_SIZE 536870912 /随机产生的最小内存空间 #define WORKTIME 1500 /系统工作时间 #define MAX_REQ_SIZE 268435456 /申请空闲内存分配的最大容量：256M #define MIN_DUE 30 /使用内存块的最短时间 #define MAX_DUE 90 /使用内存块的最长时间 #define OCCUPY_INTERVAL 60 /每次分配的最大间隔 #define USED 1 /内存块被使用 #define U

8、NUSED 0 /内存块未被使用5/内存块链表结点结构 typedef struct buddy_node int flag; /标记空间是否被使用 int base; /本块儿内存的基地址 int occupy; /实际使用空间大小 int fragment; /碎片大小 int duetime; /使用时间 struct buddy_node *nextPtr; /指向下一个结点 Buddy, *BuddyPtr;IndexTable tableINDEX_SIZE;/使用哈希表管理伙伴系统 int ready = 0; /需要分配内存的时刻 int availSpace; /可分配空间大

9、小 int totalFragment = 0; /总碎片大小 /函数：添加结点（形参为内存块结点的信息） void insert_node (int i, int inbase, int f, int occ, int frag, int d) BuddyPtr newnodePtr = NULL, prePtr = NULL, curPtr = NULL;newnodePtr = (BuddyPtr) malloc (sizeof (Buddy);/分配结点newnodePtr-base = inbase;newnodePtr-flag = f;newnodePtr-occupy = oc

10、c; newnodePtr-fragment = frag;newnodePtr-duetime = d;newnodePtr-nextPtr = NULL; if (tablei.headPtr = NULL)tablei.headPtr = newnodePtr;else curPtr = tablei.headPtr;prePtr = NULL;/按地址顺序插入内存块 while (curPtr if (prePtr = NULL) /插在最前 newnodePtr-nextPtr = curPtr;tablei.headPtr = newnodePtr;else if (curPtr

11、= NULL) /插在最后 prePtr-nextPtr = newnodePtr;6else /插在中间 prePtr-nextPtr = newnodePtr;newnodePtr-nextPtr = curPtr; /函数：删除结点 int delete_node (int i, BuddyPtr delPtr) BuddyPtr prePtr = NULL, curPtr = NULL;int basehold = delPtr-base;curPtr = tablei.headPtr;while (curPtr != delPtr) /寻找要删除的结点的位置 prePtr = cur

12、Ptr;curPtr = curPtr-nextPtr; if (prePtr = NULL) /要删除的结点在最前 tablei.headPtr = curPtr-nextPtr;else /要删除的结点不在链表的最前 prePtr-nextPtr = curPtr-nextPtr;free (curPtr); /释放结点 return basehold; /返回删除的内存块结点的基地址 /函数：伙伴系统的分配算法 void buddy_allocate (int time_slice) int i, j, size, due;int state = 0; /分配状态：0 为未分配，1 为已

13、分配 int inbase, basehold;BuddyPtr curPtr = NULL;if (ready = time_slice) /到达分配内存的时刻 printf (“Time %d:“, time_slice);size = 1 + rand () % MAX_REQ_SIZE; /申请使用内存的大小 due = MIN_DUE + rand ()%(MAX_DUE - MIN_DUE); /申请使用内存的时间if (availSpace size) /在可分配空间大于申请空间时分配/依次寻找可分配的内存块 for (i = 0; (i = size /遍历相应的循环链表中 w

14、hile (curPtr curPtr-occupy = size;curPtr-fragment = tablei.nodesize - size;curPtr-duetime = due + ready;/修改可系统分配空间和碎片大小 availSpace -= tablei.nodesize;totalFragment += curPtr-fragment;state = 1;/标记已分配 break;/空闲块的大小刚大于申请大小的 2 倍else basehold = delete_node (i, curPtr);/删除较大的空闲 块并保留其基地址 inbase = basehold + tablei.nodesize;j = i;/分割空闲块 do j -;inbase -= tablej.nodesize; /设置要添加内 存块结点的基地址 insert_node (j, inbase, UNUSED, 0, 0, 0);/添加 较小的空闲块 printf (“A block cut takes placen“); while (tablej.nodesize / siz