操作系统第5次实验报告：内存管理

2023-07-22 23:54| 来源: 网络整理| 查看: 265

0. 个人信息姓名罗廷杨学号 201821121013 班级计算1811 1. 记录内存空间使用情况

建立一个链表来记录内存空间的使用情况。首先定义一个结构体allocated_block来存放加载到内存中的进程，然后定义一个全局指针变量allocated_block_head来指向链表的头结点，当调用alloc_process函数来为进程分配内存空间时，就将成功分配到内存空间的进程块节点添加到链表中。当调用kill_process函数来对进程内存进行释放时，就将成功释放的进程块节点从链表中删除。

/*每个进程分配到的内存块描述*/ typedef struct allocated_block{ int pid; int size; int start_addr; char process_name[NAME_LEN]; struct allocated_block *next; }AB;

/*进程分配内存块链表的首指针*/ AB *allocated_block_head = NULL; 2. 记录空闲分区

建立一个链表来记录空闲分区。首先定义一个结构体free_block_type来存放空闲内存块，然后定义一个全局指针变量free_block来指向链表的头结点，当调用init_free_block函数时对整个内存空间进行初始化，此时的内存空间都为空闲分区。当调用alloc_process函数来为进程分配内存空间时，就会使用首次适配算法来从空闲分区中选出一块空闲内存分配给进程，这样就有可能将连续的空闲分区划分成几块不连续的空闲分区，这时候就将这几块不连续的空闲分区添加到记录空闲分区的链表中，并按照分区大小从小到大排序。当调用kill_process函数来对进程内存进行释放时，就会将分配给该进程的内存空闲出来，此时需要将该空闲分区插入到空闲分区链表中，注意空闲分区块的排列顺序是从小到大。

/*描述每一个空闲块的数据结构*/ typedef struct free_block_type{ int size; int start_addr; struct free_block_type *next; }FBT;

/*指向内存中空闲块链表的首指针*/ FBT *free_block; 3. 内存分配算法

首次适配算法的原理是把空闲表中最先能够满足要求的空闲区分配给进程，为适应这种算法要使得空闲区的大小按起始地址升序排列。根据首次适配算法在空闲分区链表中搜索合适空闲分区进行分配，分配时如果找到可满足空闲分区且分配后剩余空间足够大，则分割；如果找不可满足需要的空闲分区但空闲分区之和能满足需要，则采用内存紧缩技术，进行空闲分区的合并，然后再分配。在成功分配内存后，应保持空闲分区按照首次适配算法有序。

int allocate_mem(AB *ab){ /*分配内存模块*/ FBT *fbt,*pre; int request_size=ab->size; fbt = pre = free_block; //尝试寻找可分配空闲，具体结果在函数中有解释 int f = find_free_mem(request_size); if(f == -1){ //不够分配 printf("空闲内存不足,内存分配失败!\n"); return -1; }else{ if(f == 0){ //需要内存紧缩才能分配 memory_compact(); } //执行分配 do_allocate_mem(ab); } //重新排布空闲分区 rearrange(ma_algorithm); return 1; } //执行分配内存 void do_allocate_mem(AB *ab){ int request = ab->size; FBT *tmp = free_block; while(tmp != NULL){ if(tmp->size >= request){ //分配 ab->start_addr = tmp->start_addr; int shengyu = tmp->size - request; tmp->size = shengyu; tmp->start_addr = tmp->start_addr + request; return ; } tmp = tmp->next; } } void rearrange_FF(){ /*首次适应算法，空闲区大小按起始地址升序排序*/ //这里使用冒泡排序方法 if(free_block == NULL || free_block->next == NULL) return; FBT *t1,*t2,*head; head = free_block; for(t1 = head->next;t1;t1 = t1->next){ for(t2 = head;t2 != t1;t2=t2->next){ if(t2->start_addr > t2->next->start_addr){ int tmp = t2->start_addr; t2->start_addr = t2->next->start_addr; t2->next->start_addr = tmp; tmp = t2->size; t2->size = t2->next->size; t2->next->size = tmp; } } } } 4. 内存释放算法

释放进程内存包括更新分区表和进程节点两个部分。更新分区表的步骤可以分为以下几点：第一：将新释放的结点插入到空闲分区队列末尾；第二：对空闲链表按照地址有序排列；第三：检查并合并相邻的空闲分区；第四：将空闲链表重新按照首次适配算法排序。释放进程节点比较简单，只要处理好节点的前后关联就比较容易实现。

//释放链表节点 int dispose(AB *free_ab){ /*释放ab数据结构节点*/ AB *pre,*ab; if(free_ab == allocated_block_head){ //如果要是释放第一个节点 allocated_block_head = allocated_block_head->next; free(free_ab); return 1; } pre = allocated_block_head; ab = allocated_block_head->next; while(ab!=free_ab){ pre = ab; ab = ab->next; } pre->next = ab->next; free(ab); return 2; } //更新分区表 int free_mem(AB *ab){ /* 将ab所表示的已分配区归还，并进行可能的合并 */ int algorithm = ma_algorithm; FBT *fbt,*pre,*work; fbt = (FBT*)malloc(sizeof(FBT)); if(!fbt) return -1; /* 进行可能的合并，基本策略如下? 1. 将新释放的结点插入到空闲分区队列末尾? 2. 对空闲链表按照地址有序排列? 3. 检查并合并相邻的空闲分区? 4. 将空闲链表重新按照当前算法排序 */ fbt->size = ab->size; fbt->start_addr = ab->start_addr; //插至末尾 work = free_block; if(work == NULL){ free_block = fbt; fbt->next == NULL; }else{ while(work ->next != NULL){ work = work->next; } fbt->next = work->next; work->next = fbt; } //按地址重新排布 rearrange_FF(); //合并可能分区;即若两空闲分区相连则合并 pre = free_block; while(pre->next){ work = pre->next; if(pre->start_addr + pre->size == work->start_addr ){ pre->size = pre->size + work->size; pre->next = work->next; free(work); continue; }else{ pre = pre->next; } } //按照当前算法排序 rearrange(ma_algorithm); return 1; } int kill_process(int pid){ AB *ab; ab = find_process(pid); if(ab!=NULL){ free_mem(ab); //释放ab所表示的分配表 dispose(ab); //释放ab数据结构节点 return 0; }else{ return -1; } } 5. 运行结果

（1）产生测试数据

随机为3个进程分配、释放内存10次以上，即随机产生10组以上数据：(进程Pi分配内存大小)或者(进程Pi结束)

int main(int argc, char const *argv[]){ /* code */ int sel1,sel2; int total=0; //记录分配内存的次数 free_block = init_free_block(mem_size); //初始化空闲区 Prc prc[PROCESS_NUM];//存放要加载的进程 init_program(prc,PROCESS_NUM);//对这几个程进程进行初始化 srand( (unsigned)time( NULL ) ); for(int i=0;isize = mem_size; fb->start_addr = DEFAULT_MEM_START; fb->next = NULL; return fb; } int display_mem_usage(){ //显示当前内存的使用情况，包括空闲分区的情况和已经分配的情况 FBT *fbt = free_block; AB *ab = allocated_block_head; // if(fbt == NULL) return -1; printf("\e[0;31;1m------------------------------------------------------------------\e[0m\n"); //显示空闲区 printf("\e[0;32;1m空闲的内存:\e[0m\n"); printf("\e[0;33;1m%20s %20s\e[0m\n"," start_addr"," size"); while(fbt!=NULL){ if(fbt->size!=0) printf("%20d %20d\n",fbt->start_addr,fbt->size); fbt = fbt->next; } //显示已分配区 printf("\n"); printf("\e[0;35;1m使用的内存:\e[0m\n"); printf("\e[0;33;1m%10s %20s %20s %10s\e[0m\n","PID","ProcessName","start_addr","size"); while(ab != NULL){ printf("%10d %20s %20d %10d\n",ab->pid,ab->process_name,ab->start_addr,ab->size); ab = ab->next; } printf("\e[0;31;1m------------------------------------------------------------------\e[0m\n"); return 0; } //释放链表节点 int dispose(AB *free_ab){ /*释放ab数据结构节点*/ AB *pre,*ab; if(free_ab == allocated_block_head){ //如果要是释放第一个节点 allocated_block_head = allocated_block_head->next; free(free_ab); return 1; } pre = allocated_block_head; ab = allocated_block_head->next; while(ab!=free_ab){ pre = ab; ab = ab->next; } pre->next = ab->next; free(ab); return 2; } //更新分区表 int free_mem(AB *ab){ /* 将ab所表示的已分配区归还，并进行可能的合并 */ int algorithm = ma_algorithm; FBT *fbt,*pre,*work; fbt = (FBT*)malloc(sizeof(FBT)); if(!fbt) return -1; /* 进行可能的合并，基本策略如下? 1. 将新释放的结点插入到空闲分区队列末尾? 2. 对空闲链表按照地址有序排列? 3. 检查并合并相邻的空闲分区? 4. 将空闲链表重新按照当前算法排序 */ fbt->size = ab->size; fbt->start_addr = ab->start_addr; //插至末尾 work = free_block; if(work == NULL){ free_block = fbt; fbt->next == NULL; }else{ while(work ->next != NULL){ work = work->next; } fbt->next = work->next; work->next = fbt; } //按地址重新排布 rearrange_FF(); //合并可能分区;即若两空闲分区相连则合并 pre = free_block; while(pre->next){ work = pre->next; if(pre->start_addr + pre->size == work->start_addr ){ pre->size = pre->size + work->size; pre->next = work->next; free(work); continue; }else{ pre = pre->next; } } //按照当前算法排序 rearrange(ma_algorithm); return 1; } //找到pid对应的链表节点 AB *find_process(int pid){ AB *tmp = allocated_block_head; while(tmp != NULL){ if(tmp->pid == pid){ return tmp; } tmp = tmp->next; } printf("\e[0;31;1m 没有找到进程id为%d的进程！ \e[0m\n",pid); return NULL; } int kill_process(int pid){ AB *ab; ab = find_process(pid); if(ab!=NULL){ free_mem(ab); //释放ab所表示的分配表 dispose(ab); //释放ab数据结构节点 return 0; }else{ return -1; } } //寻找是否有分区可以非进程分配 int find_free_mem(int request){ FBT *tmp = free_block; int mem_sum = 0; while(tmp){ if(tmp->size >= request){ //可以直接分配 return 1; } mem_sum += tmp->size; tmp = tmp->next; } if(mem_sum >= request){ //合并后分配 return 0; }else{ //没有足够的空间可供分配 return -1; } } //将已分配表按起始地址从大到小排序 void sort_AB(){ if(allocated_block_head == NULL || allocated_block_head->next == NULL) return; AB *t1,*t2,*head; head = allocated_block_head; for(t1 = head->next;t1;t1 = t1->next){ for(t2 = head;t2 != t1;t2=t2->next){ if(t2->start_addr > t2->next->start_addr){ int tmp = t2->start_addr; t2->start_addr = t2->next->start_addr; t2->next->start_addr = tmp; tmp = t2->size; t2->size = t2->next->size; t2->next->size = tmp; } } } } //重新给所有进程分配内存地址 void reset_AB(int start){ /*在真实操作系统中这个操作非常不容易，故内存紧缩并不能频繁使用*/ AB *tmp = allocated_block_head; while(tmp != NULL){ tmp->start_addr = start; start += tmp->size; tmp = tmp->next; } } void memory_compact(){ //进行内存紧缩 FBT *fbttmp = free_block; AB *abtmp = allocated_block_head; //检测剩余内存 int sum = 0; while(fbttmp!=NULL){ sum += fbttmp->size; fbttmp = fbttmp->next; } //合并区块为一个 fbttmp = free_block; fbttmp->size = sum; fbttmp->start_addr = 0; fbttmp->next=NULL; //释放多余分区 FBT *pr = free_block->next; while(pr != NULL){ fbttmp = pr->next; free(pr); pr = fbttmp; } //重新排序已分配空间 sort_AB(); reset_AB(sum); } //执行分配内存 void do_allocate_mem(AB *ab){ int request = ab->size; FBT *tmp = free_block; while(tmp != NULL){ if(tmp->size >= request){ //分配 ab->start_addr = tmp->start_addr; int shengyu = tmp->size - request; tmp->size = shengyu; tmp->start_addr = tmp->start_addr + request; return ; } tmp = tmp->next; } } int allocate_mem(AB *ab){ /*分配内存模块*/ FBT *fbt,*pre; int request_size=ab->size; fbt = pre = free_block; /* 根据当前算法在空闲分区链表中搜索合适空闲分区进行分配，分配时注意以下情况： 1. 找到可满足空闲分区且分配后剩余空间足够大，则分割 2. 找到可满足空闲分区且但分配后剩余空间比较小，则一起分配 3. 找不可满足需要的空闲分区但空闲分区之和能满足需要，则采用内存紧缩技术，进行空闲分区的合并，然后再分配 4. 在成功分配内存后，应保持空闲分区按照相应算法有序 5. 分配成功则返回1，否则返回-1 */ //尝试寻找可分配空闲，具体结果在函数中有解释 int f = find_free_mem(request_size); if(f == -1){ //不够分配 printf("空闲内存不足,内存分配失败!\n"); return -1; }else{ if(f == 0){ //需要内存紧缩才能分配 memory_compact(); } //执行分配 do_allocate_mem(ab); } //重新排布空闲分区 rearrange(ma_algorithm); return 1; } //为进程分配内存 int alloc_process(Prc prc){ AB *ab; int ret; ab = (AB*)malloc(sizeof(AB)); if(!ab) exit(-5); /*为ab赋值 */ ab->next=NULL; pid++;//记录id strcpy(ab->process_name,prc.process_name); ab->pid = pid; ab->size=prc.size+rand()%ALLOC_SIZE;//随机分配内存 ret = allocate_mem(ab); //从空闲分区分配内存，ret==1表示分配成功 if((ret == 1) && (allocated_block_head == NULL)){ /*如果此时allocated_block_head尚未赋值，则赋值*/ allocated_block_head = ab; return 1; }else if(ret == 1){ /*分配成功，将该分配块的描述插入已分配链表*/ ab->next = allocated_block_head; allocated_block_head = ab; return 2; }else if(ret == -1){ //分配不成功 printf("\e[0;31;1m 内存分配失败！ \e[0m\n"); free(ab); return -1; } return 3; } void rearrange_FF(){ /*首次适应算法，空闲区大小按起始地址升序排序*/ //这里使用冒泡排序方法 if(free_block == NULL || free_block->next == NULL) return; FBT *t1,*t2,*head; head = free_block; for(t1 = head->next;t1;t1 = t1->next){ for(t2 = head;t2 != t1;t2=t2->next){ if(t2->start_addr > t2->next->start_addr){ int tmp = t2->start_addr; t2->start_addr = t2->next->start_addr; t2->next->start_addr = tmp; tmp = t2->size; t2->size = t2->next->size; t2->next->size = tmp; } } } } /*按指定的算法整理内存空闲块链表*/ void rearrange(int algorithm){ rearrange_FF(); } //初始化进程 void init_program(Prc prc[],int n) { for(int i=0;i

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章