1、操作系统内存buddy算法和页置换算法实验报告一、 实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、 实验内容1. 实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。2. 设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1) 最佳置换算法（Optimal）2) 先进先出法（Fisrt In First Out）3) 最近最久未使用（Least Recently Used）4) 最不经常使用法（Least Frequent
2、ly Used）其中，命中率页面失效次数页地址流长度试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。三、 项目要求及分析1、 要求：用随机函数仿真程序进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。分析：总的内存大小固定（默认为2048），申请内存的时候用到随机函数，为了使分配效果更加突出，每次申请内存大小为1600。每次申请完并成功分配后，得到剩余内存大小availMemory和碎片大小fragment，来得到分配失败的原因。分配成功的内存集记录为haveAllo，在haveAllo中随机抽
3、取内存进行释放。2、 要求：首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。分析：可以直接忽略指令的内容，按照地址来进行分析，这样是执行更加方便。各个算法总体相同，主要区别就是置换的条件不同，掌握好条件是本实验的关键。四、 具体实现4.1 流程图：1、 分配内存：释放内存：2、（1）最佳置换算法（Optimal） （2）先进先出法（Fisrt In First Out） （3）最近最久未使用（Least Recently Used） 4) 最不经常使用法（Least Frequently Used） 4.2数
4、据结构定义：1、typedef struct MemoryTreestruct MemoryTree *left;struct MemoryTree *right;struct MemoryTree *father;int tab;int thisMemory;int used;TreeNode, *Mtree;内存节点定义：tab为可用标记，1为可用，0为已用thisMemory表示此节点共有内存量used表示已用内存量int AlloMemory(int toBeAllo, Mtree root)分配内存void ReleaseMemory(int toBeRele, Mtree root
5、)释放内存void Delete(int a, int num)从数组a中删除元素num，该函数用于内存释放。void ScanMemory(Mtree root)浏览分配树，以得到可用内存和碎片2、void init_addr(void)初始化指令序列，并按照一定规则执行void init_page(void)初始化页表int isIn(int a)判断地址为a的指令是否在页中int find_max(int num, int data)找出data序列中第一个最大值的序号int find_min(int num, int data)找出data序列中第一个最小值的序号float optim
6、al(void)optimal算法，返回命中率float FIFO(void)FIFO算法，返回命中率float LRU(void)LRU算法，返回命中率float LFU(void)LFU算法，返回命中率五、 调试运行结果1、 假设有3次分配，然后释放。结果如下：若分配次数增加，假设变为7次，结果如下：我们发现，出现两次碎片过多引起的分配失败。释放过程只释放5次就结束了，不会释放非配失败的内存：2、 我们进行对页表大小为1、5、10、15、20、25、32来进行模拟，结果如下：（1）页表大小为1 （2）页表大小为5 （3）页表大小为10 （4）页表大小为15 （5）页表大小为20 （6）页表
7、大小为25 （7）页表大小为32六、 所遇问题及解决办法1、 P：在数组传递参数时出错A：发现很多需要传递的数组时贯穿全局的，所以设置为全局变量，不再进行参数的传递2、 P：在合并可用伙伴内存的时候不知道如何去进行未知次数的合并A：调用递归，进行树的后续遍历，先合并再判断，使问题迎刃而解。3、 P：在分配指令序列的时候，没有考虑到极端情况：如有320条指令，第一次随机的m为320，第m+1条指令不存在。A：把此时的第m条指令作为地址流中的一个，此处理不影响全局的概率。附：程序代码：1、内存分配与释放：#include #include #include #define MEMORY 2048i
8、nt available100, avaiNum = 0, avaiMemory = MEMORY;int fragment100, fragNum = 0;typedef struct MemoryTreestruct MemoryTree *left;struct MemoryTree *right;struct MemoryTree *father;int tab;int thisMemory;int used;TreeNode, *Mtree;int AlloMemory(int toBeAllo, Mtree root)if(toBeAllo avaiMemory)return 0;
9、else if(toBeAllo root-thisMemory)return -1;else if(toBeAllo root-thisMemory/2)if(root-left = NULL) & (root-tab = 0)root-tab = 1;root-used = toBeAllo;return 1;elsereturn -1;else if(root-tab = 1)return -1;elseif(root-left = NULL)root-left = (Mtree)malloc(sizeof(TreeNode);root-left-tab = 0;root-left-th
10、isMemory = root-thisMemory/2;root-left-used = 0;root-left-left = NULL;root-left-right = NULL;root-left-father = root;root-right = (Mtree)malloc(sizeof(TreeNode);root-right-tab = 0;root-right-thisMemory = root-thisMemory/2;root-right-used = 0;root-right-left = NULL;root-right-right = NULL;root-right-
11、father = root;if(AlloMemory(toBeAllo, root-left) != 1)return AlloMemory(toBeAllo, root-right);elsereturn 1;void ReleaseMemory(int toBeRele, Mtree root)Mtree temp;if(root != NULL)ReleaseMemory(toBeRele, root-left);ReleaseMemory(toBeRele, root-right);if(root-left = NULL)if(root-tab = 0) & (root-father
12、 != NULL)if(root-father-left-tab = 0) & (root-father-right-tab = 0) & (root-father-left-left = NULL) & (root-father-right-left = NULL)temp = root-father;temp-left = NULL;temp-right = NULL;else if(root-tab = 1) & (root-used = toBeRele)root-used = 0;root-tab = 0;if(root-father-left-tab = 0) & (root-fa
13、ther-right-tab = 0) & (root-father-left-left = NULL) & (root-father-right-left = NULL)temp = root-father;temp-left = NULL;temp-right = NULL;void Delete(int a, int num)int i = num;while(ai != 0)ai = ai+1;i+;void ScanMemory(Mtree root)if(root-left = NULL)if(root-tab = 0)availableavaiNum+ = root-thisMe
14、mory;elsefragmentfragNum+ = root-thisMemory - root-used;elseScanMemory(root-left);ScanMemory(root-right);int main()int times, i, j, n, releNum;int allocated, released;int label; /表明分配后的结果int haveAllo256;Mtree init = NULL;printf(The size of memory is:%d.nPlease input the times you will allocate the m
15、emory:, MEMORY);scanf(%d, ×);n = times;releNum = 0;init = (Mtree)malloc(sizeof(TreeNode);init-tab = 0;init-thisMemory = MEMORY;init-used = 0;init-left = NULL;init-right = NULL;init-father = NULL;srand(time(NULL);for(i = 0; i times; i+)allocated = rand() % 600;printf(The size of memory to be all
16、ocated : %dn, allocated);label = AlloMemory(allocated, init); ScanMemory(init);avaiMemory = avaiMemory - allocated;fragmentfragNum = 0;availableavaiNum = 0;if(label = 1)haveAlloreleNum+ = allocated;printf(Allocation succeed!n);j = 0;if(available0 = 0)printf(There is no available memory.);elseprintf(
17、Now,the memory available are:n);while(availablej != 0)printf(%d ,availablej+);avaiNum = 0;printf(n);j = 0;if(fragment0 = 0)printf(There is no fragment);elseprintf(The framgment are:n);while(fragmentj != 0)printf(%d ,fragmentj+);printf(n);fragNum = 0;else if(label = 0)n-;printf(Allocation failed!Shor
18、t of memory!n);elsen-;printf(Allocation failed!Too many fragment!n);haveAlloi = 0;printf(nnnNow,release!n);times = n;for(i = 0; i times; i+)releNum = rand() % n;n-;released = haveAlloreleNum;Delete(haveAllo, releNum);ReleaseMemory(released, init);ScanMemory(init);avaiMemory = avaiMemory + released;f
19、ragmentfragNum = 0;availableavaiNum = 0;printf(The memory to be released is: %dnReleasion succeed!n, released);j = 0;if(available0 = 0)printf(There is no available memory.);elseprintf(Now,the memory available are:n);while(availablej != 0)printf(%d ,availablej+);avaiNum = 0;printf(n);j = 0;if(fragmen
20、t0 = 0)printf(There is no fragment);elseprintf(The framgment are:n);while(fragmentj != 0)printf(%d ,fragmentj+);printf(n);fragNum = 0;system(pause);2、页面置换算法：#include #include #include #define ADDRESS 320#define PAGENUM 32#define FRAMENUM 10#define MAX ADDRESS * 2int addrADDRESS, pagePAGENUM;void ini
21、t_addr(void)int i = 0, x, m1, m2;srand(time(NULL);while(i ADDRESS)x = rand() % ADDRESS;if( x = ADDRESS - 1)addri+ = x;elseaddri+ = x + 1;m1 = rand() % (x + 1);addri+ = m1;addri+ = m1 + 1;m2 = (rand() % (ADDRESS - (m1 + 2) - 1) + (m1 + 2);if( m2 = ADDRESS - 1)addri+ = m2;elseaddri+ = m2 + 1;void init
22、_page(void)int i;for(i = 0; i PAGENUM; i+)pagei = -1;int isIn(int a) /判断地址为a的指令是否在页中int i;for(i = 0; i PAGENUM; i+)if(pagei = a / FRAMENUM)return i;return -1;int find_max(int num, int data) /找出data序列中第一个最大值的序号int i, temp, max = -1;for(i = 0; i num; i+)if(max datai)max = datai;temp = i;return temp;in
23、t find_min(int num, int data) /找出data序列中第一个最小值的序号int i, temp, min = MAX;for(i = 0; i datai)min = datai;temp = i;return temp;float optimal(void)int page_fault = 0;int i, t, j, bad;int tempPAGENUM;for(i = 0; i PAGENUM; i+)tempi = MAX; /初始化距离所有页面最大for(i = 0; i ADDRESS; i+)t = isIn(addri);if(t = -1)bad
24、= find_max(PAGENUM, temp);pagebad = addri / FRAMENUM;for(j = 0; j PAGENUM; j+)if(tempj MAX)tempj-;for(j = i + 1; j ADDRESS; j+)if(addrj / FRAMENUM) = pagebad)tempbad = j - i;break;tempbad = MAX;page_fault+;elsefor(j = 0; j PAGENUM; j+)if(tempj MAX)tempj-;for(j = i + 1; j ADDRESS; j+)if(addrj / FRAME
25、NUM) = paget)tempt = j - i;break;tempt = MAX;return 1 - (float)(page_fault) / ADDRESS;float FIFO(void)int i, count = 0, page_fault = 0;for(i = 0; i ADDRESS; i+)if(isIn(addri) = -1)pagecount = addri / FRAMENUM;count = (count + 1) % PAGENUM;page_fault+;return 1 - (float)(page_fault) / ADDRESS;float LRU(void)int too_long = 0, i, page_fault = 0, t, j;int tempPAGENUM;for(i = 0; i PAGENUM; i+)tempi = 0;for(i = 0; i ADDRESS; i+)t = isIn(addri)
