操作系统实验首次适应算法与循环首次适应算法

1、学号P71514032 专业计算机科学与技术 姓名 实验日期 教师签字 成绩实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】学会主存空间分配与回收的基本方法首次适应算法和循环首次适应算法。【实验原理】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。数据结构：1、bool ROMN; /定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcb num20;/定义作业数组，最大支持20个作业3、typedef s

2、truct Pcb /定义作业结构体，包括名称，开始时间，大小，是否执行状态 char name10; 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_rom100;/设置空闲区数组为100个主要函数void init()；/初始化信息，包括初始化内存信息，和初始化作业队列void insert_pcb1(pcb &a)；插入作业函数，首次适应算法，如果有适合的就插入，无合适输

3、出插入失败void insert_pcb1(pcb &a)；插入作业函数，循环首次适应算法，如果有适合的就插入，无合适输出插入失败void Delete(pcb &a)/删除作业信息，包括修改内存状态修改作业状态并对作业进行初始化void show();/显示信息void find_free_rom() /寻找空闲区算法流程图首次适应算法循环首次适应算法程序代码及截图：#include#include#define N 1024bool ROMN;/设置内存块int p=0;/循环首次使用需要标记当前的空闲区块typedef struct Pcb/作业数据结构 char name10; int

4、 start; int size; int state=0; pcb;int free_rom_counter=0;pcb num20; /作业队列typedef struct Free_rom /空闲区结构体 int num; int start; int end; int space; Free_room;Free_rom free_rom100;/设置空闲区数组为100个void find_free_rom() /寻找空闲区 free_rom_counter=0; int i,j,p; for(i=0; iN; i+) if(ROMi=0) p=i; for(j=i; jN; j+) i

5、f(ROMj=0) i=j; continue; if(ROMj=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&ROMj-1=0)/对最后一个内存进行特殊操作 free_rom_counter+; free_rom free_rom_c

6、ounter.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; iN; i+) ROMi=0;void show() printf(空闲区名t开始地址tt大小tt结束地址ttn); for (int i=1; i= free_rom_counter; i+) printf(%dtt%dttt%dtt%dttn,f

7、ree_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; iN; i+) if(ROMi=0) for(j=i; j=(i+a.size)&jN; j+)/查询第一个空闲区，并判断是否适合插入作业 if(ROMj=1) i=j+1; break; if(j=i+a.size+1) a.start=i;/设置作业的开始内存 a.state=1;/标记作业在内存中 for(k=i; ki+a.size&jN;

8、k+) ROMk=1; printf(插入成功，进程%s 的初始地址为%d,结束地址为%dn,,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; iN; i+)/从所标记的当前区域开始查询，查询到末内存 if(ROMi=0) for(j=i; j=(i+a.size)&jN; j+) if(ROMj=1) i=j+1; break; if(j=i+a.size+1)/

9、找到合适的空闲区 a.start=i; a.state=1; for(k=i; ki+a.size&jN; k+) ROMk=1; printf(插入成功，进程%s 的初始地址为%d,结束地址为%dn,,a.start,a.start+a.size-1); p=i+a.size; return; for(i=0; ip; i+)/当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的P if(ROMi=0) for(j=i; j=(i+a.size)&jp; j+) if(ROMj=1) i=j+1; break; if(j=i+a.size+1)/成功找到结束，并标记当前P为

10、现在的作业的尾部 a.start=i; a.state=1; for(k=i; ki+a.size&jp; k+) ROMk=1; printf(插入成功，进程%s 的初始地址为%dn,,a.start); p=i+a.size; break; if(i=p)/查询两部分都未找到合适的区域，输出插入失败语句 printf(插入失败，无可用空间n);void Delete(pcb &a)/删除作业，修改内存信息和初始化该作业信息 int i; for(i=a.start; ia.start+a.size; i+) ROMi=0; a.state=0;/状态标记为未使用 printf(

11、删除成功n);int main() init(); int count=0; int choose1,choose; char name10; pcb a; printf(1、首次适应算法n); printf(2、循环首次适应算法n); scanf(%d,&choose1); do printf(nn1、插入进程n); printf(2、删除进程n); printf(3、显示进程的信息n); printf(4、显示空闲区n); scanf(%d,&choose); if(choose=1) printf(输入进程名n); scanf(%s,&); printf(输入进程大小n);

12、scanf(%d,&a.size); if(choose1=1) insert_pcb1(a); else insert_pcb2(a); numcount+=a; else if(choose=2) printf(输入删除进程的名字n); scanf(%s,&name); for(int i=0; icount; i+) if( !strcmp(,name) Delete(numi); else if(choose=3) printf(进程名tt开始地址tt大小tt结束地址ttn);/输出内存信息 for(int i=0; icount-1; i+) for(int j=i

13、; jnumj+1.start) a=numj; numj=numj+1; numj+1=a; for(int i=0; icount; i+) if(numi.state!=0) printf(%stt%dttt%dtt%dttn,,numi.start,numi.size,numi.size+numi.start-1); else if(choose=4) find_free_rom(); show(); else break; while(1); return 0;首次适应算法：本实验共采用1024个内存进行模拟，首先对内存初始化，得到一个大的空闲区：相继插入3个进程：

14、分别插入进程A B C,大小分别为100,200,300此时查询进程信息和查询空闲区信息有一块大小为424 起始地址为600的空闲区在进行插入D删除B此时有两块空闲区插入一个150大小的进程，他的起始地址应为100此时空闲区只有2块，一块大小为50，删除C进程，构造一块大空闲区再插入一个进程为100大小,此时两块空闲区都满足，此时应从第一块插入再插入一个大于两块空闲区大小的进程，此时无可用空间首次适应算法完成。循环首次适应算法此时有三块空闲区，由于先前插入的是E进程，此时空闲区指针指向3，插入一个小于15的内存，会插入到3空间，再插入一个5的内存，由于采用循环首次适应，此时插入的也是3再插入一个小于200的进程，此时扫描到最后，没找到，转而从低地址开始查找循环首次适应算法正确【小结或讨论】1、 首次适应算法倾向于利用内存中低地址部分的空闲区域，从而保留了高地址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低地址部分不断被划分，会留下许多难以利用的、很小的空闲分区碎片。每次查找都是从低地址部分开始的，这样会增加查找可用空闲分区的开销。2、 为了避免低地址部分留下的许多很小的空闲分区以及减少查找可用空间区的开销，循环首次适应算法在为作业分配时，从上次找到的空闲区的下一个空闲区开始查找，找不到再从头