操作系统实验四主存空间分配与回收首次适应算法和循环首次适应算法

来源:证券从业 发布时间:2020-12-04 点击:

实验报告 【实验名称】 首次适应算法和循环首次适应算法 【实验目的】 理解在连续分区动态的存储管理方式下,如何实现主存空间的分配与回收。

【实验原理】 首次适应(first fit,FF)算法 FF算法要求空闲分区链以地址递增的次序链接。在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区即可。然后再按照作业的大小,从该分区中划出一块内存空间,分配给请求者,余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区,则表明系统中已经没有足够大的内存分配给该进程,内存分配失败,返回。

循环首次适应(next fit,NF)算法 为避免低址部分留下许多很小的空闲分区,以及减少查找可用空闲分区的开销,循环首次适应算法在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块玉请求大小相等的内存空间分配给作业。

【实验内容】 实现主存空间的分配与回收:
1. 采用可变式分区管理,使用首次适应算法实现主存空间的分配与回收;

2. 采用可变式分区管理,使用循环首次适应算法实现主存空间的分配与回收。

数据结构和符号说明:
typedef struct PCB//进程控制块 { char ProgressName[10]; //进程名称 int Startaddress; //进程开始地址 int ProgressSize; //进程大小 int ProgressState = 0; //进程状态 }; typedef struct FREE //空闲区结构体 { int Free_num; //空闲区名称 int Startaddress; //空闲区开始地址 int Endaddress; //空闲区结束地址 int Free_Space; //空闲区大小 }; 算法流程图:
首次适应算法 循环首次适应算法 程序代码及截图:
#include<stdio.h> #include<string.h> #include <stdlib.h> #include <io.h> #define N 1024 typedef struct PCB//进程控制块 { char ProgressName[10]; //进程名称 int Startaddress; //进程开始地址 int ProgressSize; //进程大小 int ProgressState = 0; //进程状态 }; typedef struct FREE //空闲区结构体 { int Free_num; //空闲区名称 int Startaddress; //空闲区开始地址 int Endaddress; //空闲区结束地址 int Free_Space; //空闲区大小 }; int count = 0; //当前内存中进程个数 bool ROM[N];//设置内存块 int p = 0;//循环首次使用需要标记当前的空闲区块 FREE FREE[100];//设置空闲区数组为100个 int FREE_counter = 0;//空闲区的个数 PCB num[20]; //作业队列 void init()//初始化操作 { for(int i=0; i<N; i++) ROM[i] = 0; } void showProgress(PCB &a) { printf(“----------------------------------------------------------------------\n“); printf(“进程名\t\t开始地址\t\t大小\t\t结束地址\n“);//输出内存信息 printf(“----------------------------------------------------------------------\n“); for(int i=0; i<count-1; i++) for(int j=i; j<count-1; j++) if(num[j].Startaddress>num[j+1].Startaddress) { a = num[j]; num[j] = num[j+1]; num[j+1] = a; } for(int i=0; i<count; i++) if(num[i].ProgressState!=0) printf(“%s\t\t%d\t\t\t%d\t\t%d\t\t\n“,num[i].ProgressName,num[i].Startaddress,num[i].ProgressSize,num[i].ProgressSize+num[i].Startaddress-1); printf(“----------------------------------------------------------------------\n“); } void showFree()//打印空闲区的情况 { printf(“----------------------------------------------------------------------\n“); printf(“ 空闲区名\t| 开始地址\t| 大小 \t| 结束地址\n“); printf(“----------------------------------------------------------------------\n“); for (int i=1; i<= FREE_counter; i++) { printf(“\t%1d\t%8d\t%11d\t %d\n“,FREE[i].Free_num,FREE[i].Startaddress, FREE[i].Free_Space,FREE[i].Endaddress); printf(“----------------------------------------------------------------------\n“); } } void find_FREE() //寻找空闲区 { int i,j,p; //计数值 FREE_counter = 0;//预设空闲区数为0 for(i = 0; i < N; i++) if(ROM[i] == 0) { p = i; for(j = i; j < N; j++) { if(ROM[j]==0)//未找到空闲区,则将j赋值给i后继续循环 { i = j; continue; } if(ROM[j]==1)//找到空闲区 { FREE_counter++;//空闲区个数+1;

FREE[FREE_counter].Free_num = FREE_counter;//设置空闲区编号 FREE[FREE_counter].Startaddress = p; FREE[FREE_counter].Endaddress = j-1; FREE[FREE_counter].Free_Space = j-p; i=j+1; break; } } if(j == N && ROM[j-1] == 0)//对最后一个内存进行特殊操作 { FREE_counter++; FREE[ FREE_counter].Free_num = FREE_counter;//对空闲区进行处理 FREE[ FREE_counter].Startaddress = p; FREE[ FREE_counter].Endaddress =j-1; FREE[ FREE_counter].Free_Space = j-p; } } } void First_Fit(PCB &a)//首次适应算法 { int i,j,k; for(i=0; i<N; i++) if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j<N; j++)//查询第一个空闲区,并判断是否适合插入作业 if(ROM[j]==1) { i = j + 1; break; } if(j==i+a.ProgressSize+1) { a.Startaddress = i;//设置作业的开始地址 a.ProgressState = 1;//标记作业在内存中 for(k=i; k<i+a.ProgressSize&&j<N; k++) ROM[k]=1; printf(“进程%s插入成功,进程%s的初始地址为%d,结束地址为%d\n“,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); return; } } if(i==N)//未查询到合适的区域 printf(“插入失败,无可用空间!\n“); } void Next_Fit(PCB &a)//循环首次适应算法来实现作业调度 { int i,j,k; for(i=p; i<N; i++)//从所标记的当前区域开始查询,查询到末内存 { if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j<N; j++) if(ROM[j]==1) { i = j+1; break; } if(j==i+a.ProgressSize+1)//找到合适的空闲区 { a.Startaddress=i; a.ProgressState=1; for(k=i; k<i+a.ProgressSize&&j<N; k++) ROM[k]=1; printf(“插入成功,进程%s 的初始地址为%d,结束地址为%d\n“,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); p=i+a.ProgressSize; return; } } } for(i=0; i<p; i++)//当未找到时,从第一个空闲区开始查询,结束条件为小于所标记的P if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j<p; j++) if(ROM[j]==1) { i=j+1; break; } if(j==i+a.ProgressSize+1)//成功找到结束,并标记当前P为现在的作业的尾部 { a.Startaddress=i; a.ProgressState=1; for(k=i; k<i+a.ProgressSize&&j<p; k++) ROM[k]=1; printf(“插入成功,进程%s 的初始地址为%d\n“,a.ProgressName,a.Startaddress); p=i+a.ProgressSize; break; } } if(i==p)//查询两部分都未找到合适的区域,输出插入失败语句 printf(“插入失败,无可用空间\n“); } void Delete(PCB &a)//删除作业,修改内存信息和初始化该作业信息 { int i; for(i=a.Startaddress; i<a.Startaddress+a.ProgressSize; i++) ROM[i]=0; a.ProgressState=0;//状态标记为未使用 printf(“进程%s删除成功\n“,a.ProgressName); } int main() { int choose1,choose; char ProgressName[10]; PCB a; init(); printf(“\t主存空间的分配与回收\n“); printf(“---------------------------------------\n“); printf(“\t1、首次适应算法\n“); printf(“\t2、循环首次适应算法\n“); printf(“---------------------------------------\n“); printf(“请选择分配算法:“); scanf(“%d“,&choose1); system(“cls“); while(1) { w:system(“cls“); printf(“当前分配算法:“); if(choose1 == 1) printf(“首次适应算法\n“); else printf(“循环首次适应算法\n“); printf(“---------------------------------------\n“); printf(“\t1、插入进程\n“); printf(“\t2、删除进程\n“); printf(“\t3、显示进程的信息\n“); printf(“\t4、显示空闲区\n“); printf(“---------------------------------------\n“); printf(“请输入:“); scanf(“%d“,&choose); system(“cls“); switch(choose) { case 1: printf(“请输入进程名:“); scanf(“%s“,&a.ProgressName); printf(“请输入进程的大小:“); scanf(“%d“,&a.ProgressSize); for(int i = 0; i < count; i++) if(strcmp(num[i].ProgressName,a.ProgressName)==0) { printf(“已存在同名进程,无法插入。\n“); system(“pause“); goto w; } if(choose1==1)//首次适应算法 First_Fit(a); else Next_Fit(a);//循环首次适应算法 num[count++]=a; break; case 2: if(count == 0) { printf(“当前没有进程在内存中,无法删除!\n“); system(“pause“); goto w; } printf(“输入删除的进程名字:“); scanf(“%s“,&ProgressName); for(int i=0; i<count; i++) if(!strcmp(num[i].ProgressName,ProgressName)) Delete(num[i]); else printf(“没有找到对应进程,请重新输入。\n“); break; case 3: showProgress(a); break; case 4: find_FREE(); showFree(); break; default: printf(“\n无效的输入。\n“); } system(“pause“); } return 0; } 主界面:
首次适应算法,初始空闲区:
插入进程:
插入3个进程:
空闲区信息:
删除进程2:
删除后空闲区状况:
再插入一个进程,可以看到其其初始地址为100:
循环首次适应算法,插入3个进程 删除进程2后:
再插入进程A,发现其从上次找到的空闲分区的下一个空闲分区开始查找,其初始地址为750而不是200:

推荐访问:
上一篇:请你谈谈对马克思主义中国化科学内涵理解?(三)
下一篇:冀教版实验小学2019-2020学年六年级上册数学期中试卷

Copyright @ 2013 - 2018 优秀啊教育网 All Rights Reserved

优秀啊教育网 版权所有