《操作系统实验-首次适应算法与循环首次适应算法.docx》由会员分享，可在线阅读，更多相关《操作系统实验-首次适应算法与循环首次适应算法.docx（17页珍藏版）》请在三一文库上搜索。
1、学号P71514032 专业计算机科学与技术 姓名 实验日期2017.11.16 教师签字 成绩实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】学会主存空间分配与回收的基本方法首次适应算法和循环首次适应算法。【实验原理】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。数据结构：1、bool ROMN; /定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcb num20;/定义作业数组，最大支持20个作业3
2、、typedef struct 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 n
4、ame10; int 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;
5、 jN; j+) if(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
6、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; iN; i+) ROMi=0;void show() printf(空闲区名t开始地址tt大小tt结束地址ttn); for (int i=1; i= free_rom_counter; i+) printf(%dtt%dttt%
7、dtt%dttn,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; 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
8、.size&jN; k+) ROMk=1; printf(插入成功，进程%s 的初始地址为%d,结束地址为%dn,a.name,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+
9、a.size+1)/找到合适的空闲区 a.start=i; a.state=1; for(k=i; ki+a.size&jN; k+) ROMk=1; printf(插入成功，进程%s 的初始地址为%d,结束地址为%dn,a.name,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)/成功找到
10、结束，并标记当前P为现在的作业的尾部 a.start=i; a.state=1; for(k=i; ki+a.size&jp; k+) ROMk=1; printf(插入成功，进程%s 的初始地址为%dn,a.name,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;/状态标记为未
11、使用 printf(删除成功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,&a.name); printf(
12、输入进程大小n); 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(numi.name,name) Delete(numi); else if(choose=3) printf(进程名tt开始地址tt大小tt结束地址ttn);/输出内存信息 for(int i=0; icount-1; i+) f
13、or(int j=i; 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.name,numi.start,numi.size,numi.size+numi.start-1); else if(choose=4) find_free_rom(); show(); else break; while(1); return 0;首次适应算法：本实验共采用1024个内存进行模拟，首先对内存初始化，得到一个大的空闲区
14、：相继插入3个进程：分别插入进程A B C,大小分别为100,200,300此时查询进程信息和查询空闲区信息有一块大小为424 起始地址为600的空闲区在进行插入D删除B此时有两块空闲区插入一个150大小的进程，他的起始地址应为100此时空闲区只有2块，一块大小为50，删除C进程，构造一块大空闲区再插入一个进程为100大小,此时两块空闲区都满足，此时应从第一块插入再插入一个大于两块空闲区大小的进程，此时无可用空间首次适应算法完成。循环首次适应算法此时有三块空闲区，由于先前插入的是E进程，此时空闲区指针指向3，插入一个小于15的内存，会插入到3空间，再插入一个5的内存，由于采用循环首次适应，此时
15、插入的也是3再插入一个小于200的进程，此时扫描到最后，没找到，转而从低地址开始查找循环首次适应算法正确【小结或讨论】1、 首次适应算法倾向于利用内存中低地址部分的空闲区域，从而保留了高地址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低地址部分不断被划分，会留下许多难以利用的、很小的空闲分区碎片。每次查找都是从低地址部分开始的，这样会增加查找可用空闲分区的开销。2、 为了避免低地址部分留下的许多很小的空闲分区以及减少查找可用空间区的开销，循环首次适应算法在为作业分配时，从上次找到的空闲区的下一个空闲区开始查找，找不到再从头开始查找，实现该算法，在程序中设置了一个指针P，用于指示下一个起始查询的空闲分区。该算法能够使内存中分配的分布区域更均匀，从而减少了查找空闲区的开销，但这样也会导致缺乏大的空闲区。3、 根据经验，如果作业的大小较为均为，使用循环首次适应算法实现较好。4、 本实验对两种算法进行模拟时，并未采用链表的方式，而是采用数组的方式，内存是连续的，判断是否内存是否被占用，仅仅用一个布尔型的量进行状态记录，且在查询过程中，当循环计数器达到最大内存号时，便认为到达了尾部，较为简便。