请求分页式存储管理

课程名称 操作系统实践 实验名称 请求分页式存储管理 实验日期 2011-5-13 班级_计科0802 姓名_刘伟 _ 学号_0304080230 仪器编号_________ 实验报告要求 1实验目的 2实验要求 3实验步骤 4程序清单 5运行情况 6流程图 7实验体会 1． 实验目的 理解内存页面调度的机理，掌握几种理论调度算法实现，并通过实验比较各种调度算法的优劣。 2． 实验要求 采用请求分页式存储管理方式对作业及内存进行管理 3． 编程环境 编程工具：VC++6.0 平台：windows XP 4． 实验原理 本程序提供两种分区管理法供用户使用，这两种算法是最佳适应算法和首次适应算法。 最佳适应算法要求将所有的空闲区，按其大小以递增的顺序形成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。但该算法会留下许多这样难以利用的小空闲区。 首次适应算法要求空闲分区链以地址递增的次序链接。在进行内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止。然后，再按照作业的大小，从该分区中划出一快内存空间分配该请求者，余下的空闲分区仍留在空闲链中。 不足之处： 该程序可以用文件形式输入作业的信息，但是该文件没有绑定在程序中。不过，用户用键盘输入的作业的信息会自动保存到该文件中，下次当以文件形式输入作业信息时，文件中的内容是上一次用户用键盘输入的内容。 5． 程序清单 #include #include #include int memoryStartAddress = -1; int memorySize = -1; struct jobList //作业后备队列的链结点 { int id; //作业的ID号 int size; //作业的大小 int status; //作业状态 struct jobList *next; }; struct freeList //空闲链的链结点 { int startAddress; //空闲分区的首地址 int size; //空闲分区的大小 struct freeList *next; }; struct usedList //已分配内存的作业链 { int startAddress; //以分配内存的首地址 int jobID;

1

struct usedList *next; }; void errorMessage(void) //出错信息 { printf(\"\\n\错误!\\a\"); printf(\"\\n按任意键继续!\"); getch(); exit(1); } void openFile(FILE **fp,char *filename,char *mode) //打开文件函数 { if((*fp = fopen(filename,mode)) == NULL) { printf(\"\\n不能打开 %s.\ errorMessage(); } } void makeFreeNode(struct freeList **empty,int startAddress,int size)//申请内存空间 { if((*empty = malloc(sizeof(struct freeList))) == NULL) { printf(\"\\n没有足够空间.\"); errorMessage(); } (*empty)->startAddress = startAddress; //当有足够空间时，则分配 (*empty)->size = size; (*empty)->next = NULL; } void iniMemory(void) //输入要求分配内存的首地址，大小 { char MSA[10],MS[10]; printf(\"\\n请输入要分配内存的首地址 !\"); scanf(\"%s\ memoryStartAddress = atoi(MSA); printf(\"\\n请输入要分配内存的大小!\"); scanf(\"%s\ memorySize = atoi(MS); } char selectFitMethod(void) //选择分区管理算法 { FILE *fp; char fitMethod; do{ printf(\"\\n\\n请选择分区管理的算法!\\ \\n 1 最佳适应算法 \\ \\n 2 首次适应算法\\n\");

2

fitMethod = getche(); }while(fitMethod < '1' || fitMethod > '3'); //选择出错时 openFile(&fp,\"d:\\\\result.cl\ switch(fitMethod) { case '1': fprintf(fp,\"\\n\\n\\n\\n\ 最佳适应算法\"); fprintf(fp,\"\\n**********************************************\"); break; case '2': fprintf(fp,\"\\n\\n\\n\\n\首次适应算法\"); fprintf(fp,\"\\n**********************************************\"); break; } fclose(fp); return fitMethod; } void inputJob(void) //输入作业的信息 { int /*id,size, */status = 0,jobnum = 0; FILE *fp; char id[10],size[10]; openFile(&fp,\"d:\\\\job.cl\ fprintf(fp,\"作业名\大小\状态\"); printf(\"\\n\\n\\n\\n请输入作业名和大小! \\n输入0 0退出 ，job_ID由数字组成\\n\\n\\njob_ID\size\\n\"); do{ /* scanf(\"%d%d\ scanf(\"%s\%s\保存作业ID，大小 if(atoi(id) > 0 && atoi(size) > 0) { fprintf(fp,\"\\n%s\%s\%d\ /* fprintf(fp,\"\\n%d\%d\%d\ jobnum++; } else break; }while(1); if(jobnum) printf(\"\\n完成输入!\"); else { printf(\"\\n没有请求分配内存.\"); errorMessage(); } fclose(fp); } int makeJobList(struct jobList **jobs) //把作业插入分区

3

{ char jobID[10],size[10],status[10]; struct jobList *rear; FILE *fp; openFile(&fp,\"d:\\\\job.cl\ fscanf(fp,\"%s%s%s\ if((*jobs = malloc(sizeof(struct jobList))) == NULL) //当没有空闲分区时 { printf(\"\\n没有足够空间 .\"); fclose(fp); errorMessage(); } rear = *jobs; (*jobs) -> next = NULL; while(!feof(fp)) { struct jobList *p; fscanf(fp,\"%s%s%s\ if((p = malloc(sizeof(struct jobList))) == NULL) { printf(\"\\n没有足够空间.\"); fclose(fp); errorMessage(); } p -> next = rear -> next; //插入已在分区的作业队列中 rear -> next = p; rear = rear -> next; rear -> id = atoi(jobID); rear -> size = atoi(size); rear -> status = atoi(status); } fclose(fp); return 0; } int updateJobFile(struct jobList *jobs) { FILE *fp; struct jobList *p; openFile(&fp,\"d:\\\\job.cl\ fprintf(fp,\"job_ID\size\status\"); for(p = jobs -> next;p;p = p -> next) fprintf(fp,\"\\n%d\%d\%d\ fclose(fp); return 0; } int showFreeList(struct freeList *empty) //在屏幕上显示空闲分区 {

4

FILE *fp; struct freeList *p = empty -> next; int count = 0; openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n显示空闲内存\"); printf(\"\\n\\n显示空闲内存\"); if(p) { fprintf(fp,\"\\nnumber\size\startAddress\"); printf(\"\\n序号\大小\开始地址\"); //显示空闲分区的大小和首地址 for(;p;p = p -> next) { fprintf(fp,\"\\n%d\%d\%d\ printf(\"\\n%d\%d\%d\ } fclose(fp); return 1; } Else //没有空闲分区 { fprintf(fp,\"\\n内存已分配完 !\"); printf(\"\\n内存已分配完!\"); fclose(fp); return 0; } } void getJobInfo(struct jobList *jobs,int id,int *size,int *status) //查找作业是否在分区中 { struct jobList *p = jobs->next; while(p && p->id != id) //删除作业 p = p->next; if(p == NULL) { printf(\"\\n不能找到作业 : %d .\ errorMessage(); } else { *size = p -> size; *status = p -> status; } } void updateJobStatus(struct jobList **jobs,int id,int status) //改变作业的状态 { struct jobList *p = (*jobs)->next; while(p && p->id != id) p = p->next;

5

if(p == NULL) { printf(\"\\n不能找到作业 : %d .\ errorMessage(); } else p -> status = status; //作业状态 } int showUsedList(struct jobList *jobs,struct usedList *used) //显示以分配的分区 { FILE *fp; struct usedList *p = used -> next; int count = 0,size,status; openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n显示已分配的内存\"); printf(\"\\n\\n显示已分配的内存\"); if(p) { fprintf(fp,\"\\nnumber\作业名\大小\开始地址\"); printf(\"\\nnumber\作业名\大小\开始地址\"); //显示分区中的作业信息 for(;p;p = p -> next) { getJobInfo(jobs,p -> jobID,&size,&status); fprintf(fp,\"\\n%d\%d\%d\%d\ printf(\"\\n%d\%d\%d\%d\ } fclose(fp); return 1; } Else //分区中没有作业 { fprintf(fp,\"\\n内存中没有作业.\"); printf(\"\\n内存中没有作业.\"); fclose(fp); return 0; } } int showJobList(struct jobList *jobs) //分区上的作业 { struct jobList *p; p = jobs->next; if(p == NULL) { printf(\"\\n列表上没有作业.\"); return 0; } printf(\"\\n\\nT列表上的作业如下 :\\n作业名\大小\状态\"); //显示作业信息

6

while(p) { printf(\"\\n%d\%d\%d\ p = p->next; } return 1; } void moveFragment(struct jobList *jobs,struct freeList **empty,struct usedList **used) //当回收一部分分区后，进行碎片紧凑 { int size,status; struct usedList *p; int address = memoryStartAddress; if((*empty)->next == NULL) //当没有空闲分区分配时，可以回收已分配内存 { printf(\"\\n内存已用完.\\ \\n你可以先回收一些内存或者 \\ \\n按任意键再试一次 !\"); getch(); return; } for(p = (*used) -> next;p;p = p-> next) //插入作业 { p -> startAddress = address; getJobInfo(jobs,p -> jobID,&size,&status); address += size; } (*empty) -> next -> startAddress = address; //删除作业，回收内存 (*empty) -> next -> size = memorySize - (address - memoryStartAddress); (*empty) -> next -> next = NULL; } void order(struct freeList **empty,int bySize,int inc) //按顺序排列分区的作业 { struct freeList *p,*q,*temp; int startAddress,size; for(p = (*empty) -> next;p;p = p -> next) { for(temp = q = p;q;q = q -> next) { switch(bySize) { case 0 : switch(inc) { case 0:if(q->size < temp->size) //交换作业位置 temp = q;break; default:if(q->size > temp->size) //交换作业位置

7

temp = q;break; } break; default: switch(inc) { case 0:if(q->startAddress < temp->startAddress) temp = q;break; //交换作业位置 default:if(q->startAddress > temp->startAddress) temp = q;break; //交换作业位置 } break; } } if(temp != p) { startAddress = p->startAddress; size = p->size; p->startAddress = temp->startAddress; p->size = temp->size; temp->startAddress = startAddress; temp->size = size; } } } int allocate(struct freeList **empty,int size) //按要求把分区分该作业 { struct freeList *p,*prep; int startAddress = -1; p = (*empty) -> next; while(p && p->size < size) //没有足够分区，删除作业 p = p -> next; if(p != NULL) { if(p -> size > size) //当有足够分区，直接分配 { startAddress = p -> startAddress; p -> startAddress += size; p -> size -= size; } else //将整个分区分给一个作业 { startAddress = p -> startAddress; prep = *empty; while(prep -> next != p) prep = prep -> next; prep -> next = p -> next; free(p); }

8

} else printf(\"\\n你可以拼接碎片.\"); /* Unsuccessful ! */ return startAddress; } void insertUsedNode(struct usedList **used,int id,int startAddress) //在分区中插入作业 { struct usedList *q,*r,*prer; if((q = malloc(sizeof(struct usedList))) == NULL) //没有足够空间时 { printf(\"\\nNot enough to allocate for the used node .\"); errorMessage(); } q -> startAddress = startAddress; //插入作业 q -> jobID = id; prer = *used; r = (*used) -> next; while(r && r->startAddress < startAddress) { prer = r; r = r -> next; } q -> next = prer -> next; prer -> next = q; } int finishJob(struct usedList **used,int id,int *startAddress) //删除作业，回收分区 { struct usedList *p,*prep; prep = *used; p = prep -> next; while(p && p -> jobID != id) //删除作业 { prep = p; p = p -> next; } if(p == NULL) { printf(\"\\n作业: %d 不在内存 !\找不到要删除的作业 return 0; } else { *startAddress = p->startAddress; prep -> next = p -> next; free(p); return 1; }

9

} void insertFreeNode(struct freeList **empty,int startAddress,int size)//插入空闲分区 { struct freeList *p,*q,*r; for(p = *empty;p -> next;p = p -> next) ; if(p == *empty || p -> startAddress + p -> size < startAddress) //对空闲分区进行排列 { makeFreeNode(&r,startAddress,size); r -> next = p -> next; p -> next = r; return ; } if(p -> startAddress + p -> size == startAddress) //插入空闲分区 { p -> size += size; return ; } q = (*empty) -> next; if(startAddress + size == q -> startAddress) //插入空闲分区 { q -> startAddress = startAddress; q -> size += size; } else if(startAddress + size < q -> startAddress) //插入空闲分区 { makeFreeNode(&r,startAddress,size); r -> next = (*empty) -> next; (*empty) -> next = r; } else { while(q -> next && q -> startAddress < startAddress) //插入空闲分区 { p = q; q = q -> next; } if(p -> startAddress + p -> size == startAddress &&\\ q -> startAddress == startAddress + size) //插入空闲分区 { p -> size += size + q -> size; p -> next = q -> next; free(q); } else if(p -> startAddress + p -> size == startAddress &&\\ q -> startAddress != startAddress + size) //插入空闲分区 {

10

p -> size += size; } else if(p -> startAddress + p -> size != startAddress &&\\ q -> startAddress == startAddress + size) //插入空闲分区 { q -> startAddress = startAddress; q -> size += size; } else { makeFreeNode(&r,startAddress,size); //申请作业空间 r -> next = p -> next; p -> next = r; } } } void main(void) { char fitMethod; //定义变量 FILE *fp; //定义变量 struct jobList *jobs; //定义一个队列 struct freeList *empty; //定义一个队列 struct usedList *used; //定义一个队列 if((used = malloc(sizeof(struct usedList))) == NULL) { printf(\"\\n没有足够空间.\"); errorMessage(); } used -> next = NULL; remove(\"d:\\\\result.cl\"); makeFreeNode(&empty,0,0); while(1) //界面设计 { char ch,step; //定义变量 int id,size,startAddress,status; //定义变量 struct jobList *q; printf(\"\\n 1 输入作业的信息.\\ \\n 2 作业放到内存.\\ \\n 3 完成作业,并回收内存.\\ \\n 4 当前空闲的内存.\\ \\n 5 当前已分配的内存.\\ \\n 6 拼接碎片.\\ \\n 7 退出.\"); printf(\"\\n请选择.\\n\"); step = getche(); printf(\"\\n\"); switch(step)

11

{ case '1': //当选择1时 openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n\输入作业的信息 :)\"); used -> next = NULL; //初始化队列 empty->next = NULL; //初始化队列 iniMemory(); makeFreeNode(&(empty->next),memoryStartAddress,memorySize); fprintf(fp,\"\\n\\n\\n你用文件形式输入吗?(Y/N) : \"); //是否用文件形式输出 printf(\"\\n\\n\\n你用文件形式输入吗 ?(Y/N ): \\n\"); ch = getche(); fprintf(fp,\"\\n%c\ fclose(fp); if(ch != 'Y'&& ch != 'y') //当选择用文件形式输出时 { inputJob(); } makeJobList(&jobs); if(ch == 'Y'|| ch == 'y') //读入文件的作业信息 { for(q = jobs->next;q;q = q->next) { if(q->status == 1) { startAddress = allocate(&empty,q->size); if(startAddress != -1) { insertUsedNode(&used,q->id,startAddress); } } } } fitMethod = selectFitMethod(); break; case '2': //当选择2时 if(memoryStartAddress < 0 || memorySize < 1) { printf(\"\\n\\nBad memory allocated !\\a\"); break; } openFile(&fp,\"d:\\\\result.cl\打开文件 fprintf(fp,\"\\n\\n\把作业放到内存\"); fprintf(fp,\"\\n\\n\\n你用键盘输入作业信息吗?(Y/N): \"); printf(\"\\n\\n\\n你用键盘输入作业信息吗?(Y/N): \\n\"); ch = getche(); fprintf(fp,\"\\n%c\

12

fclose(fp); if(ch != 'Y' && ch != 'y') //把作业放到分区中 { for(q = jobs->next;q;q = q->next) { if(q->status == 0) { switch(fitMethod) //用不同分区管理算法 { case '1': order(&empty,0,0);break; case '2': order(&empty,0,1);break; case '3': order(&empty,1,0);break; case '4': order(&empty,1,1);break; } startAddress = allocate(&empty,q->size); if(startAddress != -1) { insertUsedNode(&used,q->id,startAddress); //把作业插入到以分配内存中 updateJobStatus(&jobs,q->id,1); } } } updateJobFile(jobs); } else { showJobList(jobs); //显示可操作的作业 openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n请从上面的作业中选择一个作业，输入作业名.\"); printf(\"\\n请从上面的作业中选择一个作业，输入作业名.\"); scanf(\"%d\ fprintf(fp,\"%d\\n\ getJobInfo(jobs,id,&size,&status); //把作业放入内存 switch(status) //作业的不同状态 { case 0: printf(\"\\nOk !作业的状态是运行状态!\"); fprintf(fp,\"\\nOk!作业的状态是运行状态 !\");fclose(fp);break; case 1: printf(\"\\n作业在内存中 !\"); fprintf(fp,\"\\n作业在内存中 !\");fclose(fp);goto label; case 2: printf(\"\\n作业已完成!\"); fprintf(fp,\"\\n作业已完成!\");fclose(fp);goto label; default:printf(\"\\nUnexpected job status .Please check you job file.\"); fprintf(fp,\"\\nUnexpected job status .Please check you job file.\"); fclose(fp);errorMessage(); } switch(fitMethod) //不同分区管理方法的实现

13

{ case '1': order(&empty,0,0);break; case '2': order(&empty,0,1);break; case '3': order(&empty,1,0);break; case '4': order(&empty,1,1);break; } startAddress = allocate(&empty,size); if(startAddress != -1) { insertUsedNode(&used,id,startAddress); //插入作业 updateJobStatus(&jobs,id,1); //改变作业状态 updateJobFile(jobs); } } label : ; break; case '3': //当选择3时 if(memoryStartAddress < 0 || memorySize < 1) { printf(\"\\n\\nBad memory allocated !\\a\"); break; } do{ int i; openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n\作业完成(回收内存)\"); fclose(fp); if(showUsedList(jobs,used) == 0) break; openFile(&fp,\"d:\\\\result.cl\打开文件 fprintf(fp,\"\\n请从上面的作业中选择一个作业，输入作业名.\\n输入-1来结束测试 .\"); printf(\"\\n请从上面的作业中选择一个作业，输入作业名 .\\n输入-1来结束测试 .\"); scanf(\"%d\ fprintf(fp,\"%d\\n\ fclose(fp); if(id == -1) break; getJobInfo(jobs,id,&size,&status); //把作业放入内存 if(status == 1) //作业状态为运行时 { i = finishJob(&used,id,&startAddress); if(i) { insertFreeNode(&empty,startAddress,size); //插入空闲分区 updateJobStatus(&jobs,id,2); //改变作业状态 updateJobFile(jobs);

14

} } else { if(status == 0 || status == 2) { if(status == 0) printf(\"\\n作业不在内存中 !\"); else printf(\"\\n作业已完成!\"); } else { printf(\"\\nUnexpected job status .\\ Please check you job file.\"); errorMessage(); } } }while(1); break; case '4': //当选择4时 openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n\显示空闲内存\"); fclose(fp); showFreeList(empty); break; case '5': //当选择5时 openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n\显示已分配内存\"); fclose(fp); showUsedList(jobs,used); break; case '6': //当选择6时 openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n\拼接碎片\"); fclose(fp); moveFragment(jobs,&empty,&used); break; case '7': //当选择7时 openFile(&fp,\"d:\\\\result.cl\ fprintf(fp,\"\\n\\n\Exit :(\"); fclose(fp); exit(0); default: printf(\"\\n错误输入!\"); } } getch(); 15

} 6． 运行情况 1．运行EXE文件： 2．首先要选择1，输入要分配内存的首地址，分区大小，输入作业的信息：

16

3．按ENTER键后，选择分区管理算法： 4．然后选择2,把作业放到内存：

17

5．到此，用户就可以选择自己想要的操作功能，这里3为例： 教师评价

及优 良 中 格 不及格 教师签名 日期 18