可变分区存储管理方式的内存分配回收

可变分区存储管理方式的内存分配回收 文档状态 发布版 Document status XXXXXXXXXX 发布日期 2017-3-30 Release date 实验报告 操作系统 可变分区存储管理方式的内存分配回收 班级:XXXXXXXXXXXX 学号:XXXXXXXXXXXX 姓名:XXXXXX 日期:XXXX.XX.XX 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number DZ-2013-5 A0 1 (12) 版本历史 Revisions History 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 2 (12) 目录 1 引言 ...................................................................................................................................................4 1.1 实验目的......................................................................................................................................4 1.2 参考文档......................................................................................................................................4 2 可变分区存储管理 ...............................................................................................................................5 2.1 实验原理分析 ...............................................................................................................................5 2.2 思路......................................................................................................................................5 2.3 源程序 .........................................................................................................................................6 2.4 重要结构体说明..........................................................................................................................10 2.5 重要变量说明 .............................................................................................................................10 2.6 结果 ..........................................................................................................................................11 2.7 测试方法对结果的分析................................................................................................................11 2.8 接口 ..........................................................................................................................................12 2.8.1 接口设计说明 ........................................................................................................................12 2.9 任务设计....................................................................................................................................12 2.9.1 图 ..................................................................................................................................12 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 3 (12) 1 引言 1.1 实验目的 通过首次适应算法、最佳适应算法和最坏适应算法实现主存空间的分配， 可以使开发人 员更好地理解存储分配算法。 1.2 参考文档 1. 操作系统2.3.1节 空闲存储区 2. 操作系统2.3.2节 首次适应法(1.分配算法，2.回收算法) 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 4 (12) 2 可变分区存储管理 2.1 实验原理分析 在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是 一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被 占用，而有的分区时空闲的。为了方便主存空间的分配和去配，用于管理的数据结 构可由两张表组成:“已分配区表”和“未分配区表”。在“未分配表中”将空闲 区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进 程要求的最小分区进行分配。这时从已分配表中找出一个空栏目登记新作业的起始 地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。当作业撤离时 已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有 相邻空闲区再将其连接后登记。 2.2 设计思路 1、 分配算法: 采用首次适应法为作来分配大小为size的内存空间时，总是从表的起始端的低地址 部分开始查找，当第一次找到大于或等于申请大小的空闲区时，就按所需大小分配 给作业。如果分配后原空闲区还有剩余空间，就修改原存储区表项的m_size和 m_addr，使它记录余下的“零头”。如果作业所需空间正好等于该空闲区大小，那 么该空闲区表项的m_size就成为0，接下来要删除表中这个“空洞”，即将随后的 各非零表项依次上移一个位置。 2、 回收算法: 当某一作业回收以前所分配到的内存时，就要将该内存区归还给系统，使其成为空 闲区而可被其它作来使用。回收时如释放区与邻近的空闲区相衔接，要将它们合并 成较大的空闲区，否则空闲区将被分割得超来越小，最终导致不能利用;另外，空 闲区个数越来越多，也会使空闲区登记表溢出。 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 5 (12) 2.3 源程序 /* | 如不会使用文件输入/输出，也不会使用I/O转向做输入和输出结果文件， | 可以手再抄输出结果后后再输到文件中，实验报告的文字内容由自己掌握，能多能少。 */ #include #include /*表的定义*/ #define N 5 #define MEMSIZE 1000 typedef struct map { unsigned m_size; char *m_addr; }; struct map coremap[N]; /* coremap表的初始化程序*/ void initcoremap(char *addr, unsigned size) { unsigned i; printf("init coremap, first addr: %d\n", addr); coremap[0].m_size = size; coremap[0].m_addr = addr; for(i = 1; i < N; i++) { coremap[i].m_size = 0; coremap[i].m_addr = 0; } } /* 输出表的内容*/ void printcoremap(void) { unsigned i; 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 6 (12) /* 打印coremap表中各项的m_size和m_addr */ for(i = 0; i < N; i++) { printf("coremap[%d].m_addr=%d ", i, coremap[i].m_addr); printf("coremap[%d].m_size=%d\n", i, coremap[i].m_size); } } /* 首次适应的分配函数*/ char *fmalloc(unsigned size) { register char *a; register struct map *bp; for (bp = coremap; bp->m_size; bp++) { if(bp->m_size >= size) { a = bp->m_addr; bp->m_addr += size; /* 修改表项的首地址*/ if((bp->m_size -= size) == 0) /* 有正好大小的空闲区*/ do { bp++; (bp - 1)->m_addr = bp->m_addr; /* 修改表项的首地址*/ } while((bp - 1)->m_size = bp->m_size); /* 打印分配内存空间的m_size和m_addr*/ printf("fmalloc size: %d, addr:%d\n", size, a); return(a); } } return(0); } /* 首次适应的回收函数*/ void ffree(unsigned size, char *addr) { struct map *bp; char *a, *t; 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 7 (12) unsigned tt; printf("ffree mem size=%u, addr=%u\n", size, addr); a = addr; for (bp = coremap; bp->m_addr <= a && bp->m_size != 0; bp++); if (bp > coremap && (bp - 1)->m_addr + (bp - 1)->m_size == a) /* 情况 1、2 */ { (bp - 1)->m_size += size; /* 情况 1 */ if (a + size == bp->m_addr) /* 情况 2 */ { (bp - 1)->m_size += bp->m_size; while (bp->m_size) { bp++; (bp - 1)->m_addr = bp->m_addr; (bp - 1)->m_size = bp->m_size; } } } else { if (a + size == bp->m_addr && bp->m_size) /* 情况 3 */ { bp->m_addr -= size; bp->m_size += size; } else if (0 != size) /* 情况 4 */ { do { t = bp->m_addr; bp->m_addr = a; a = t; tt = bp->m_size; bp->m_size = size; bp++; } while (size = tt); } } 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 8 (12) } /* 主程序的框架*/ int main(void) { char *mymem; int size; int addr; char cmdchar; char c=""; if ((mymem = malloc(MEMSIZE)) == NULL) { printf("Not enough memory to allocate buffer\n"); exit(1); } initcoremap(mymem, MEMSIZE); while(c != 'q') { do { c = getchar(); } while(c == '\n' || c == '\t' || c == ' '); cmdchar = c; switch (cmdchar) { case 'm': /* 分配空间*/ scanf("%u", &size); fmalloc(size); break; case 'f': /* 释放空间*/ scanf("%u %u", &size, &addr); ffree(size, mymem + addr); break; case 'p': printcoremap(); 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 9 (12) break; default: /* 其它字母退出*/ break; } } free(mymem); return 0; } 2.4 重要结构体说明 空闲存储区表可采用结构数组的形式，采用的数据结构形式为: typedef struct map { unsigned m_size; char *m_addr; }; m_size:是空闲分区的长度 m_addr:是空闲分区的起始地址 2.5 重要变量说明 coremap[N]:是空闲存储区表 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 10 (12) 2.6 结果 2.7 测试方法对结果的分析 1、连续分配3个100长度的分区，剩下700长度的分区 2、从头释放掉一个100长度的分区，里面有两个可用的分区，一个是100长度的分区，一个是700长度的分区 3、程序运行的结果，与设计思路一致。 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 11 (12) 2.8 接口 2.8.1 接口设计说明 myTest 名称 函数名 char *fmalloc(unsigned size) 函数说明 首次适应的分配功能 fmalloc 输入 size 类型 unsigned 输出 未实际使用 类型 char 函数名 void ffree(unsigned size, char *addr) 函数说明 首次适应的回收功能 ffree Size unsigned 输入 类型 addr char 输出 / 类型 / 2.9 任务设计 2.9.1 流程图 开始 malloc( ) 系统、表格初始化 命令处理 结束处理 fmalloc( ) ffree( ) 打印表格 实验报告 文 档 编 号 版 本 页 码 上海交通大学 Document number Version Page number A0 12 (12)