学号P7*******专业计算机科学与技术姓名实验日期2017.11.16教师签字成绩实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】学会主存空间分配与回收的基本方法首次适应算法和循环首次适应算法。

【实验原理】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。

采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。

采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。

数据结构：1、bool ROM[N]; //定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcb num[20];//定义作业数组，最大支持20个作业3、typedef struct Pcb //定义作业结构体，包括名称，开始时间，大小，是否执行状态{char name[10];int start;int size;int state=0;} pcb;typedef struct Free_rom //空闲区结构体{int num;int start;int end;int space;} Free_room;Free_rom free_rom[100];//设置空闲区数组为100个主要函数void init()；//初始化信息，包括初始化内存信息，和初始化作业队列void insert_pcb1(pcb &a)；插入作业函数，首次适应算法，如果有适合的就插入，无合适输出‘插入失败’void insert_pcb1(pcb &a)；插入作业函数，循环首次适应算法，如果有适合的就插入，无合适输出‘插入失败’void Delete(pcb &a)//删除作业信息，包括修改内存状态修改作业状态并对作业进行初始化void show();//显示信息void find_free_rom() //寻找空闲区算法流程图首次适应算法循环首次适应算法程序代码及截图：#include<stdio.h>#include<string.h>#define N 1024bool ROM[N];//设置内存块int p=0;//循环首次使用需要标记当前的空闲区块typedef struct Pcb//作业数据结构{char name[10];int start;int size;int state=0;} pcb;int free_rom_counter=0;pcb num[20]; //作业队列typedef struct Free_rom //空闲区结构体{int num;int start;int end;int space;} Free_room;Free_rom free_rom[100];//设置空闲区数组为100个void find_free_rom() //寻找空闲区{free_rom_counter=0;int i,j,p;for(i=0; i<N; i++)if(ROM[i]==0){p=i;for(j=i; j<N; j++){if(ROM[j]==0){i=j;continue;}if(ROM[j]==1)//找到空闲区{free_rom_counter++;free_rom[ free_rom_counter].num= free_rom_counter;free_rom[ free_rom_counter].start=p;free_rom[ free_rom_counter].end=j-1;free_rom[ free_rom_counter].space=j-p;i=j+1;break;}}if(j==N&&ROM[j-1]==0)//对最后一个内存进行特殊操作{free_rom_counter++;free_rom[ free_rom_counter].num= free_rom_counter;//对空闲区进行处理free_rom[ free_rom_counter].start=p;free_rom[ free_rom_counter].end=j-1;free_rom[ free_rom_counter].space=j-p;}}}void init()//初始化{for(int i=0; i<N; i++)ROM[i]=0;}void show(){printf("空闲区名\t开始地址\t\t大小\t\t结束地址\t\t\n");for (int i=1; i<= free_rom_counter; i++)printf("%d\t\t%d\t\t\t%d\t\t%d\t\t\n",free_rom[ i].num,free_rom[ i].start, free_rom[ i].space,free_rom[ i].end);}void insert_pcb1(pcb &a)//首次适应算法来实现作业调度{int i,j,k;for(i=0; i<N; i++)if(ROM[i]==0){for(j=i; j<=(i+a.size)&&j<N; j++)//查询第一个空闲区，并判断是否适合插入作业if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1){a.start=i;//设置作业的开始内存a.state=1;//标记作业在内存中for(k=i; k<i+a.size&&j<N; k++)ROM[k]=1;printf("插入成功，进程%s 的初始地址为%d,结束地址为%d\n",,a.start,a.start+a.size-1);return;}}if(i==N)//未查询到合适的区域printf("插入失败，无可用空间\n");}void insert_pcb2(pcb &a)//循环首次适应算法来实现作业调度{int i,j,k;for(i=p; i<N; i++)//从所标记的当前区域开始查询，查询到末内存{if(ROM[i]==0){for(j=i; j<=(i+a.size)&&j<N; j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1)//找到合适的空闲区{a.start=i;a.state=1;for(k=i; k<i+a.size&&j<N; k++)ROM[k]=1;printf("插入成功，进程%s 的初始地址为%d,结束地址为%d\n",,a.start,a.start+a.size-1);p=i+a.size;return;}}for(i=0; i<p; i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的Pif(ROM[i]==0){for(j=i; j<=(i+a.size)&&j<p; j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1)//成功找到结束，并标记当前P为现在的作业的尾部{a.start=i;a.state=1;for(k=i; k<i+a.size&&j<p; k++)ROM[k]=1;printf("插入成功，进程%s 的初始地址为%d\n",,a.start);p=i+a.size;break;}}if(i==p)//查询两部分都未找到合适的区域，输出插入失败语句printf("插入失败，无可用空间\n");}void Delete(pcb &a)//删除作业，修改内存信息和初始化该作业信息{int i;for(i=a.start; i<a.start+a.size; i++)ROM[i]=0;a.state=0;//状态标记为未使用printf("删除成功\n");}int main(){init();int count=0;int choose1,choose;char name[10];printf("1、首次适应算法\n");printf("2、循环首次适应算法\n");scanf("%d",&choose1);do{printf("\n\n1、插入进程\n");printf("2、删除进程\n");printf("3、显示进程的信息\n");printf("4、显示空闲区\n");scanf("%d",&choose);if(choose==1){printf("输入进程名\n");scanf("%s",&);printf("输入进程大小\n");scanf("%d",&a.size);if(choose1==1)insert_pcb1(a);else insert_pcb2(a);num[count++]=a;}else if(choose==2){printf("输入删除进程的名字\n");scanf("%s",&name);for(int i=0; i<count; i++)if( !strcmp(num[i].name,name))Delete(num[i]);}else if(choose==3){printf("进程名\t\t开始地址\t\t大小\t\t结束地址\t\t\n");//输出内存信息for(int i=0; i<count-1; i++)for(int j=i; j<count-1; j++)if(num[j].start>num[j+1].start){a=num[j];num[j]=num[j+1];num[j+1]=a;}for(int i=0; i<count; i++)if(num[i].state!=0)printf("%s\t\t%d\t\t\t%d\t\t%d\t\t\n",num[i].name,num[i].start,num[i].size,num[i].s ize+num[i].start-1);}else if(choose==4){find_free_rom();show();}else break;}while(1);return 0;}首次适应算法：本实验共采用1024个内存进行模拟，首先对内存初始化，得到一个大的空闲区：相继插入3个进程：分别插入进程A B C,大小分别为100,200,300此时查询进程信息和查询空闲区信息有一块大小为424 起始地址为600的空闲区在进行插入D删除B此时有两块空闲区插入一个150大小的进程，他的起始地址应为100此时空闲区只有2块，一块大小为50，删除C进程，构造一块大空闲区再插入一个进程为100大小,此时两块空闲区都满足，此时应从第一块插入再插入一个大于两块空闲区大小的进程，此时无可用空间首次适应算法完成。