操作系统实验-最佳适应算法最坏适应算法

学号P 专业计算机科学与技术 姓名实验日期 2017/11/23 教师签字 成绩 实验报告【实验名称】 基于顺序搜索的动态分区分配算法(二)【实验目的】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。【实验原理】C+语言程序设计数据结构最佳适应算法最坏适应算法数据结构和符号说明1、bool ROMN; /定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcb num20;/定义作业数组，最大支持20个作业3、typedef struct Pcb /定义作业结构体，包括名称，开始时间，大小，是否执行状态 char name10; int start; int size; int state=0; pcb;主要函数：void find_free_rom()；/寻找空闲区void sort1()；/对空闲区进行排序从小到大void sort1()；/对空闲区进行排序从大到小void show()；/显示函数void insert_pcb1(pcb &a)；/最佳适应算法void insert_pcb2(pcb &a)；/最坏适应算法void init();/初始化函数算法流程图：最佳适应算法：最坏适应算法：#include#include#define N 1024bool ROMN;int p=0;int count=0;int free_rom_counter=0;/空闲区数目typedef struct Pcb /进程结构体 char name10; int start; int size;/大小 int state=0; /状态 pcb;pcb num20;/进程数组typedef struct Free_rom/空闲区结构体 int num; int start; int end; int space;/空闲区大小 Free_room;Free_rom free_rom100;/空闲区数组void show()/显示空闲区信息 printf(*nn); printf(空闲区名t开始地址tt大小tt结束地址ttn); for (int i=1; i= free_rom_counter; i+) printf(%dtt%dttt%dtt%dttn,free_rom i.num,free_rom i.start, free_rom i.space,free_rom i.end); printf(n); printf(*nn);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+) 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 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 sort1()/最佳适应算法对空闲区从小到大排序 find_free_rom(); Free_rom a; for(int i=1; ifree_rom_counter; i+) for(int j=1; j free_romj+1.space) a=free_romj; free_romj=free_romj+1; free_romj+1=a; void sort2()/最坏适应算法对空闲区从大到小排序 find_free_rom(); Free_rom a; for(int i=1; ifree_rom_counter; i+) for(int j=1; jfree_rom_counter; j+) if( free_romj.space free_romj+1.space) a=free_romj; free_romj=free_romj+1; free_romj+1=a; void init()/初始化 for(int i=0; iN; i+) ROMi=0;void input(pcb &a)/输入 char name10; printf(输入进程名n); scanf(%s,&); printf(输入进程大小n); scanf(%d,&a.size);void insert_pcb1(pcb &a)/最佳适应算法插入进程 find_free_rom(); sort1(); int i,j,k; for(i=1; i=free_rom_counter; i+)/判断插入 if(a.size= free_romi.space) for(j= free_romi.start; jfree_romi.start+a.size; j+) ROMj=1; a.state=1; a.start=free_romi.start; numcount+=a; break; if(i=free_rom_counter+1)/插入失败 printf(可用空间不足!n);void insert_pcb2(pcb &a)/最坏适应算法插入find_free_rom();sort2();int i,j,k;for(i=1; i=free_rom_counter; i+) if(a.size= free_romi.space) for(j= free_romi.start; jfree_romi.start+a.size; j+)/寻找 ROMj=1; a.state=1; a.start=free_romi.start; numcount+=a; break; if(i=free_rom_counter+1)/插入失败 printf(可用空间不足!n);void Delete(pcb &a)/内存中释放进程 int i; for(i=a.start; ia.start+a.size; i+) ROMi=0;/更新内存信息，更新进程状态数组 a.state=0; printf(删除成功n); find_free_rom();int main()/主函数 init(); find_free_rom(); int choose1; int choose; char name10; printf(1、最佳适应算法n);/主界面 printf(2、最坏首次适应算法n); scanf(%d,&choose1); pcb a; do printf(nn1、插入进程n); printf(2、删除进程n); printf(3、显示进程信息n); printf(4、显示空余内存信息n); scanf(%d,&choose); if(choose=1)/选择 input(a); if(choose1=1) insert_pcb1(a); else insert_pcb2(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(*nn); printf(进程名tt开始地址tt大小tt结束地址ttn);/输出内存信息 for(int i=0; icount; i+) if(numi.state!=0) printf(%stt%dttt%dtt%dttn,,numi.start,numi.size,numi.size+numi.start-1); printf(n*nn); else if(choose=4) find_free_rom(); show(); else break; while(1); return 0;截图：构造如下空闲区： 此时插入一个进程 G，大小为80H，应插入到第二块空闲区再插入一个大小为30的进程H，应插入到第三块中再插入一个小进程，大小为5，插入到第二块空闲区，查看进程信息和空闲区信息：最佳适应算法成立。最坏适应算法：构造如下空闲区：插入一个大小为80的进程G，插入到第一块空闲区。在插入一个大小为20的进程H，插入到第三块空闲区。再插入一个大小为20的进程，插入到第三块空闲区。最坏适应算法成立。【小结或讨论】1、 本次实验涉及到两个表，空闲区登记表和进程分配表，分配空间需要进程所需空间的大小，给出过分配后进程的起始地址；回收空间除了需要进程所需空间的大小以外，还需要知道进程的起始地址，再进行一系列判断然后回收。2、 本次实验的两个算法是在首次适应算法的基础上进行的改进，最佳适应算法是将所有区按照区的大小进行升序排列，再从第一个区即最小的区开始检索分配内存；最坏适应算法是将所有区按照