北邮操作系统第二次实验.docx

北京邮电大学 操作系统实验 实验报告班号：2011211314 姓名： oneseven 学号： 实验日期： 2013.12.16 实验名称： 操作系统实验 一、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容1.实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。实验准备用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1) 最佳置换算法（Optimal）2) 先进先出法（Fisrt In First Out）3) 最近最久未使用（Least Recently Used）4) 最不经常使用法（Least Frequently Used）其中，命中率页面失效次数页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。实验准备本实验中主要的流程：首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验可先从一个具体的例子出发。(1)通过随机数产生一个指令序列，共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条指令排列虚存地址，即2048条指令在虚存中的存放方式为：第 0 条-第 63 条指令为第0页（对应虚存地址为0，63）第64条-第127条指令为第1页（对应虚存地址为64，127）第1984条-第2047条指令为第31页（对应虚存地址为1984，2047）按以上方式，用户指令可组成32页。以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时的情形。3. 实现内存的slab分配器：其基本思想是：一次向内核获取整数页，slab根据数据结构的大小进行划分为一个个小的数据结构，当需要时直接从该链表上摘取一个返回应用程序，当应用程序释放时，而非真正释放，只需要该空间放回到链表中，当分散的一页多块又聚集一页时，又会拼成一页，同时判断slab空闲的页数，如果空闲页超过一定的页数，就会向系统释放一定的页数。一个slab分配器只能管理一个指定大小的数据结构分配。三、项目要求及分析3.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为2m个字(地址从0到2m-1)，则在开始运行时，整个内存区是一个大小为2m的空闲块，在运行了一段时间之后，被分隔成若干占用块和空闲块。为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表，这就是伙伴系统中的可利用空间表，如图所示：分配算法： 当用户提出大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应的子表中。 若2k-1 n 2k-1，又第k+1个子表不空，则只要删除此链表中第一个结点并分配给用户即可；若 2k-2 n 2k-1-1，此时由于结点大小为2k-1的子表为空，则需从结点大小为2k的子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为2k-1的子表中，若2k-i-1 n 2k-i-1(i为小于是的整数)，并且所有结点小于2k的子表均为空，则同样需从结点大小为2k的子表中取出一块，将其中2k-i的一小部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为2k-1、 2k-2、 2k-i的子表中。回收算法：在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中去。这里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴”的两个空闲块的归并。 何谓“伙伴”?如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。例如：假设p为大小为pow(2,k)的空闲块的初始地址，且p MOD pow(2,k+1)=0，则初始地址为p和p+pow(2,k)的两个空闲块互为伙伴。在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一起。 由此，在回收空闲块时，应首先判别其伙伴是否为空闲块，若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。3. 2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。 页面替换算法主要用于如下几个地方： (1) 虚拟存储器中，主存页面（或程序段）的替换。 (2) Cache中的块替换。 (3) 虚拟存储器的快慢表中，快表的替换。 (4) 虚拟存储器中，用户基地址寄存器的替换。在虚拟存储器中常用的页面替换算法有如下几种：(1) 最优替换算法，即OPT算法（OPTimal replacement algorithm）。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。 (2) 先进先出算法，即FIFO算法（First-In First-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。 (3) 最久没有使用算法，即LRU算法（Least Recently Used algorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的多与少简化成判断有与无，因此，实现起来比较容易。 (4) 近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相对比较简单的方法。 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。造成了内存的浪费。如果 页数太少，存放的 obj个数少，那么 增加管理开销，同时 内存使用率低，如果页数太多对伙伴内存系统不好，所以需要一定的策略妥协。这个妥协过程是有calculate_slab_order 这个函数来实现的。从 0阶（即一页） 到kmalloc的最高阶KMALLOC_MAX_ORDER ，挨个尝试，由cache_estimate这个函数计算 如果选用order 阶，那么能分配 多少个 obj（num），剩余空间是多少（remainder）。所谓剩余空间，就是除去slab头（如果有的话），除去 obj*num，剩下的边角料空间是多少。 需要分成两种情况去计算，分成两种情况的原因，很快就能看到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 /申请空闲内存分配的最大容量：256M #define MIN_DUE 30 /使用内存块的最短时间#define MAX_DUE 90 /使用内存块的最长时间#define OCCUPY_INTERVAL 60 /每次分配的最大间隔 #define USED 1 /内存块被使用 #define UNUSED 0 /内存块未被使用/内存块链表结点结构 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; /可分配空间大小 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 = occ; newnodePtr-fragment = frag; newnodePtr-duetime = d; newnodePtr-nextPtr = NULL; if (tablei.headPtr = NULL) tablei.headPtr = newnodePtr; else curPtr = tablei.headPtr; prePtr = NULL; /按地址顺序插入内存块 while (curPtr & curPtr-base nextPtr; if (prePtr = NULL) /插在最前 newnodePtr-nextPtr = curPtr; tablei.headPtr = newnodePtr; else if (curPtr = NULL) /插在最后 prePtr-nextPtr = newnodePtr; else /插在中间 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 = curPtr; 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为已分配 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 & tablei.headPtr) curPtr = tablei.headPtr; /遍历相应的循环链表中 while (curPtr & (state = 0) /找到空闲块 if (curPtr-flag = UNUSED) /空闲块的大小小于申请大小的2倍，分配 if (tablei.nodesize / size = 1) /在分配的内存块上设置信息 curPtr-flag = USED; 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 / size 1); /分配 insert_node (j, basehold, USED, size, tablej.nodesize - size, due + ready); /修改可系统分配空间和碎片大小 availSpace -= tablej.nodesize; totalFragment += tablej.nodesize - size; state = 1;/标记已分配 /块被占用，查看下一结点 else curPtr = curPtr-nextPtr; printf (Allocated %d,Fragment %d,Due %dn, size, totalFragment, ready+due); else if (availSpace = size) printf (Allocation failed because of fragment!n); else printf (Allocation failed because of no enough unused space!n); ready += (1 + rand() % OCCUPY_INTERVAL); /下次需要分配内存的时刻 /函数：伙伴系统的回收算法void buddy_retrieve (int time_slice) int i, basehold, dif; int f = 0;int Modnext=0; BuddyPtr curPtr = NULL, todelPtr = NULL; /依次查找，并回收需要回收的块 for (i = 0; i flag = USED) & (curPtr-duetime = time_slice) /需要回收 /修改可系统分配空间和碎片大小 availSpace += tablei.nodesize; totalFragment -= curPtr-fragment; /回收为空闲块 curPtr-flag = UNUSED; curPtr-occupy = 0; curPtr-fragment = 0; curPtr-duetime = 0; printf (Time %d:Retrieve %d,Fragment %dn, time_slice, tablei.nodesize, totalFragment); curPtr = curPtr-nextPtr; /合并空闲块 for (i = 0; i nextPtr) /将地址连续且都为空闲的块合并后加入下一级的链表中 if (curPtr-flag = UNUSED & (curPtr-nextPtr)-flag = UNUSED) dif = (curPtr-nextPtr)-base - curPtr-base;Modnext = (int)(curPtr-nextPtr-base)%(2*tablei.nodesize); if (dif = tablei.nodesize)&(Modnext=0) /删除两个结点 todelPtr = curPtr; curPtr = curPtr-nextPtr; basehold = delete_node (i, todelPtr); todelPtr = curPtr; curPtr = curPtr-nextPtr; delete_node (i, todelPtr); insert_node (i+1, basehold, UNUSED, 0, 0, 0);/添加合并后的结点 printf (Two blocks mergen); else curPtr = curPtr-nextPtr; else curPtr = curPtr-nextPtr; /函数：伙伴系统的处理过程 void buddy_system (void) int time_slice = 0; /在每个时间片内使用分配算法和回收算法 for (; time_slice WORKTIME; time_slice +) buddy_allocate (time_slice); /分配算法 buddy_retrieve (time_slice); /回收算法 int main(int argc, char *argv) int memory_size; ini_index (); /初始化哈希索引表 srand (time (NULL); /设置随机数种子 /随机产生需要管理的内存大小：512M 1G memory_size = MIN_MOMORY_SIZE + rand() % MIN_MOMORY_SIZE; printf (The size of memory is:%dn, memory_size); int_system (memory_size); /初始化伙伴系统 buddy_system (); /伙伴系统的处理过程 printf (Time %d:System execution stops and the spaces are all freed.n, WORKTIME); free_system (); /释放所有结点 system(pause); return 0;42.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。程序：#include#include#include#define TRUE 1#define FALSE 0#define INVALID -1#define NUL 0#define total_instruction 320 /指令流长#define total_vp 32 /虚页长#define clear_period 50 /清零周期typedef struct int pn; /页号 int pfn; / 面号 int counter; / 一个周期内访问该页面的次数 int time; / time为访问时间pl_type;pl_type pltotal_vp; /页面结构数组struct pfc_struct /页面控制结构 int pn,pfn; struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;int diseffect,atotal_instruction;int pagetotal_instruction, offsettotal_instruction;/* Name: void Lprintf(void) Achieve: 格式控制 */void Lprintf(void) int i,j; printf(|); for(i = 1;i=6;i+) for(j = 1;j=9;j+) printf(-); if(i!=6) printf(+); printf(|n); /* Name: void initialize(int total_pf) Achieve:初始化相关数据结构*/void initialize(int total_pf) int i; diseffect=0; for(i=0;itotal_vp;i+) pli.pn=i;pli.pfn=INVALID; /置页面控制结构中的页号，页面为空 pli.counter=0;pli.time=-1; /页面控制结构中的访问次数为0，时间为-1 for(i=1;itotal_pf;i+) pfci-1 .next=&pfci;pfci-1.pfn=i-1;/建立pfci-1和pfci之间的连接 pfctotal_pf-1.next=NUL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /页面队列的头指针为pfc0/* Name:void FIFO(int total_pf) Achieve:先进先出法（Fisrt In First Out）*/void FIFO(int total_pf)int i,j;pfc_type *p;/中间变量initialize(total_pf); /初始化相关页面控制用数据结构busypf_head=busypf_tail=NULL; /忙页面队列头，队列尾链接for(i=0;inext; plbusypf_head-pn.pfn=INVALID;freepf_head=busypf_head; /释放忙页面队列的第一个页面freepf_head-next=NULL; /表明还是缺页*/busypf_head=p;p=freepf_head-next; freepf_head-pn=pagei;plpagei.pfn=freepf_head-pfn;freepf_head-next=NULL; /使busy的尾为nullif(busypf_tail=NULL)busypf_tail=busypf_head=freepf_head;elsebusypf_tail-next=freepf_head;busypf_tail=freepf_head;freepf_head=p;printf(%6.3f,1-(float)diseffect/320);/* Name: void LRU (int total_pf) Achieve: 最近最久未使用（Least Recently Used）*/void LRU (int total_pf)int min,minj,i,j,present_time; /minj为最小值下标initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /页面失效diseffect+;if(freepf_head=NULL) /无空闲页面min=32767;/设置最大值for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; /空出一个单元plminj.pfn=INVALID;plminj.time=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空闲页面,改为有效plpagei.time=present_time;freepf_head=freepf_head-next; /减少一个free 页面elseplpagei.time=present_time;/命中则增加该单元的访问次数present_time+;printf(%6.3f,1-(float)diseffect/320);/* Name:void OPT(int total_pf) Achieve:最佳置换算法（Optimal）*/void OPT(int total_pf)int i,j, max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*页面失效*/diseffect+;if(freepf_head=NULL) /*无空闲页面*/for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)distj=3276