1、操作系统试验可变分区存储管理实验四可变分区存储管理 学时:4学时 实验内容 主存储器空间分配实验。 实验目的 通过首次适应算法、最佳适应算法和最坏适应算法实现主存空间的分配,可以使读者可好地理解存储分配算法。 实验题目 编写一段程序来模拟可变分区管理方法。要求能通过文件形式定义空闲区表;能随意输入作业及需要分配的空间;能分别使用首次适应算法、最佳适应算法和最坏适应算法对输入的作业进行空间分配;能显示系统空闲表和已分配空间表。 实验提示 可变分区方式是按作业需要的主存空间大小来分区。当装入一个作业时,首先要查看是否有足够的空闲空间来分配,若有则按指定的分配方式进行分配;否则作业不能装入。随着作业
2、的装入和撤离主存空间被分为若干个大大小小的不连续的区间,为了表明各区间的状态可以用一个内存分区表如表1所示来表示。 表1 内存分区表 起始地址 长度 标志 作业1 20k 120k 空闲 50k 200k 这样我们可以定义一个如下的结构表示内存分区信息。 typedef struct node int start; /起始地址 int length; /长度 char tag20; /标志 job; 可变分区的三种算法就是为作业分配主存空间的方法。 首次适应算法:在空闲区间中查询满足作业需要的空间,并将作业装入第一个满足条件的空间中去。 最佳适应算法:在空闲区间中查询满足作业需要的空间,并将作
3、业装入满足条件的空闲空间中最小的一个空间中去。 最坏适应算法:在空闲区间中查询满足作业需要的空间,并将作业装入满足条件的空闲空间中最大的一个空间中去。 从三种算法的说明可以看出,分配空间的过程主要可以分两步:查询所有满足作业需求的空间块。 按照指定的算法将作业装入空间块中。 在操作的最初主存空间实际就是一个大的空闲区,不涉及到如何分配的问题。为直接模拟运行一段时间后主存中出现了多个空闲块的状态,题目要求从一个文件读入空闲区表。在这里我们可以设计一个空闲区表文件的结构为如表2所示: 空闲区表2 表 起始地址 长度 50k 200k 这样也可以方便地将空闲表一次读入程序中,而不必再一个个的输入。
4、主要变量及函数说明如表3所示。 变量与函数说明表3 表typedef struct node内存块结空闲区job frees 已分配区表 job occupys 空闲区数量 free_quantity 已分配区数量occupy_quantity 初始化函数 void initial() 从文件读入空闲表函数 int readData() 排序空闲表void sort() 显示分区信息void view() 最先适应分配算法void earliest() 最优适应分配算法 void excellent() 最坏适应算法void worst() 空闲表文件mem.txt 5.实验案例 /动态分区算
5、法memory.c /运行环境Redhad9.0 gcc 4.0 #include #include #include #define MAXJOB 200 /定义存储数据最大值 内存块结构/ typedef struct node int start; int length; char tag20; job; job freesMAXJOB; /定义空闲区表 int free_quantity; /空闲区块数 job occupysMAXJOB; /定义已分配区表 int occupy_quantity; /已分配区块数 /初始化函数 void initial() int i; for(i=
6、0;iMAXJOB;i+) freesi.start=-1; freesi.length=0; strcpy(freesi.tag,ree); /定义所有块为空闲块 occupysi.start=-1; occupysi.length=0; strcpy(occupysi.tag,); /已分配块为0 free_quantity=0; occupy_quantity=0; /读数据函数,从文件中读入空闲表的设置 int readData() FILE *fp; char fname20; 牰湩晴尨请输入初始空闲表文件名:); /输入空闲表文件的文件名 scanf(%s,&fname); if(
7、fp=fopen(fname,)=NULL) 牰湩晴尨错误,文件打不开,请检查文件名n); else while(!feof(fp) /打开文件读入空闲表信息 fscanf(fp,%d %d,&freesfree_quantity.start,&freesfree_quantity.length); free_quantity+; return 1; return 0; /排序空闲表 void sort() int i,j,p; for(i=0;ifree_quantity-1;i+) p=i; for(j=i+1;jfree_quantity;j+) if(freesj.startfrees
8、p.start) p=j; if(p!=i) freesfree_quantity=freesi; freesi=freesp; freesp=freesfree_quantity; /显示函数 void view() int i; printf(-n); 牰湩晴尨当前空闲表:n); /显示空闲表 牰湩晴尨起始地址t长度t状态n); for(i=0;ifree_quantity;i+) printf(?tMt%sn,freesi.start,freesi.length,freesi.tag); printf(-n); 牰湩晴尨当前已分配表:n); 牰湩晴尨起始地址t长度t占用作业名n); fo
9、r(i=0;ioccupy_quantity;i+) /显示已分配表 printf(?tMt%sn,occupysi.start,occupysi.length,occupysi.tag); getchar(); /最先适应分配算法 void earliest() char job_name10; int job_length; int i,j,flag,t; 牰湩晴尨请输入新申请内存空间的作业名:); scanf(%s,&job_name); 牰湩晴尨请输入新申请内存空间的大小:); scanf(%d,&job_length); flag=0; for(i=0;i=job_length) f
10、lag=1; if(flag=0) /没找到满足的空间 printf(当前没有能满足你申请长度的空闲内存,请稍候再试n); else /找到了满足的空间 t=0; i=0; while(t=0) if(freesi.length=job_length) t=1; i+; i-; occupysoccupy_quantity.start=freesi.start; /分配满足条件的空间 strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length; occupy_quantity+; i
11、f(freesi.lengthjob_length) freesi.start+=job_length; freesi.length-=job_length; else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-; 牰湩晴尨内存空间成功!n); /最优适应分配算法 void excellent() char job_name20; int job_length; int i,j,flag,t; 牰湩晴尨请输入新申请内存空间的作业名:); scanf(%s,&job_name); 牰湩晴尨请输入新申请内存空间的大小:)
12、; scanf(%d,&job_length); flag=0; for(i=0;i=job_length) flag=1; if(flag=0) printf(当前没有能满足你申请长度的空闲内存,请稍候再试n); else t=0; i=0; while(t=0) if(freesi.length=job_length) t=1; i+; i-; for(j=0;j=job_length)&(freesj.lengthjob_length) freesi.start+=job_length; freesi.length-=job_length; else for(j=i;jfree_quan
13、tity-1;j+) freesj=freesj+1; free_quantity-; 牰湩晴尨内存空间成功!n); /最坏适应算法 void worst() char job_name20; int job_length; int i,j,flag,t; 牰湩晴尨请输入新申请内存空间的作业名:); scanf(%s,&job_name); 牰湩晴尨请输入新申请内存空间的大小:); scanf(%d,&job_length); flag=0; for(i=0;i=job_length) flag=1; if(flag=0) printf(当前没有能满足你申请长度的空闲内存,请稍候再试n); e
14、lse t=0; i=0; while(t=0) if(freesi.length=job_length) t=1; i+; i-; for(j=0;j=job_length)&(freesj.lengthfreesi.length) i=j; occupysoccupy_quantity.start=freesi.start; /分配空闲空间 strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length; occupy_quantity+; if(freesi.lengthjob_l
15、ength) freesi.start+=job_length; freesi.length-=job_length; else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-; 牰湩晴尨内存空间成功!n); /主函数 int main() int flag=0; int t=1; int chioce=0; initial(); /初始化 flag=readData(); /读空闲表文件 while(flag=1) sort(); /排序 /显示菜单 printf(=n); 牰湩晴尨动态分区算法); printf(=n
16、); printf(.显示空闲表和分配表n2.最先适应法 n3.最优适应法 n4.最坏适应法 n0.退出n=); 牰湩晴尨请选择:); scanf(%d,&chioce); /输入选择的菜单项 switch(chioce) case 1: /显示空闲表和分配表 view(); break; case 2: /调用最先适应法 earliest(); break; case 3: /最优适应法 excellent(); break; case 4: /最坏适应法 worst(); break; case 0: /退出 flag=0; break; default: printf(选择错误!n);
17、运行结果: rootredlinux ys# gcc memory.c o memory.o rootredlinux ys#./memory.o 请输入初始空闲表文件名:mem.txt = 动态分区算法 = 1.显示空闲表和分配表 2.最先适应法 3.最优适应法 4.最坏适应法 0.退出 =请选择:1 - 当前空闲表: 起始地址 长度 状态 20 32 free 52 8 free 60 120 free 180 331 free - 当前已分配表: 起始地址 长度 占用作业名 选择2后,情况如下:(由于篇幅有限,简化了运行过程) =请选择:2 请输入新申请内存空间的作业名:a 请输入新申请内存空间的大小:32 内存空间成功! 请选择:2=请输入新申请内存空间的作业名:b 请输入新申请内存空间的大小:24 - 当前空闲表: 起始地址 长度 状态 52 8 free 60 96 free 180 331 free - 当前已分配表: 起始地址 长度 占用作业名 20 32 a 60 24 b