OS课程设计报告书.doc

南通大学计算机学院操作系统教程课程设计报 告 书设计题目 1优先级调度算法 2首次适应算法 专业班级 软外122 学生姓名 宋俞璋 学 号 指导教师 周建美 日 期 2014年7月3日 目 录一级目录1页码一级目录2页码1课程设计题目：（1） 设计一个按优先级调度的算法实现处理机调度（2） 采用首次适应算法管理内存2课程设计目的：（1）进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先级算法的具体实施办法。 （2）一个好的计算机系统不仅要有足够的存储容量，较高的存取速度和稳定可靠的存储器，而且能够合理的分配和使用这些主存空间。当用户提出申请主存空间的要求时，存储管理能够按照一定的策略分析主存的使用情况，找出足够的空间分配给申请者；当作业运行完毕，存储管理要回收作业占用的主存空间。本实验实现在可变分区存储管理方式下，采用最先适应算法对主存空间进行分配和回收，以加深了解操作系统的存储管理功能。 3. 课程设计要求：实验一：（1）假设系统中有35个进程，每个进程由一个进程控制块（PCB）来代表。进程的优先数、要求运行时间和估计运行 时间由用户程序任意设计，且优先数越低，优先级越高。调度时，总是选择优先级最高的进程运行。（2）为了调度方便，设计一个指针指向就绪队列的第一个进程。另外再设一个当前运行进程指针，指向当前正运行的进程。 （3）处理机调度时，总是选择已经到达队列的优先级最高的进程运行。为了采用 动态优先级调度，进程每运行一次，其优先级就减1。由于本实验是模拟实验，所以对被选中进程并不实际启动运行，而只是执行： 优先数加1和估计运行时间减1用这个操作来模拟进程的一次运行。（4）进程运行一次后，若剩余的运行时间不为0，且其优先级低于就绪队列的其他进程的优先级，则选择一个高优先级进程抢占CPU；若剩余运行时间为0，则把它 的状态改为完成状态“C”，并撤出就绪队列。 （5）若就绪队列不空，则重复上述的步骤（3）和（4）直到所有进程都运行完为止。（6）在所设计的程序中应有显示或打印语句，以显示或打印每次被选中进程的进程名字、运行一次后进程的变化以及就绪队列中的各进程排队情况等。实验二：一个好的计算机系统不仅要有足够的存储容量，较高的存取速度和稳定可靠的存储器，而且能够合理的分配和使用这些主存空间。当用户提出申请主存空间的要求时，存储管理能够按照一定的策略分析主存的使用情况，找出足够的空间分配给申请者；当作业运行完毕，存储管理要回收作业占用的主存空间。本实验实现在可变分区存储管理方式下，采用最先适应算法对主存空间进行分配和回收，以加深了解操作系统的存储管理功能。4. 课程设计报告内容实验一：（1）数据结构设计如下： struct pcb /* 定义进程控制块PCB */ char name10; /进程名 char state; /进程状态int super; /优先级数 int ntime; /需要运行时间 int rtime; /已运行时间（2）流程图实验二：（1）基本思想空闲分区链以地址递增的次序连接。在分配内存时，从链首开始顺序查找，直至找到一个大小能够满足要求的空闲分区为止；然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败。（2）主要数据结构typedef struct FreeLink /空闲链 struct FreeLink *prior; char name; int start; int size; bool flag; struct FreeLink *next;* ptr,*head;head top;ptr p;（3）内存分配算法 当有进程要求分配主存时，依据首次适应算法从链头开始，延链查找一个足以容纳该进程的空闲区。若这个分区比较大，则一分为二，一部分分配给进程，另一部分作为空闲区仍留在链中的当前位置，修改它的上一个空闲区的前向指针值为再加上分配给进程的分区大小，下一个空闲区的后向指针值为再加上分配给进程的分区大小，使链保持完整。若这个分区的大小正好等于进程的大小，该分区全部分配给进程，并将该空闲区从链中摘除（即修改下一个空闲区的后向指针=该空闲区后向指针，上一个空闲区的前向指针=该空闲区的前向指针）。再在已分配区表中找一个空表目，登记刚刚分配的内存始址、长度和进程号。（4）内存的回收当进程运行完成，释放内存时，通过输入进程号，来回收进程占用的分区。在回收时，释放区与空闲区相邻接的情况要考虑4种情况：释放区下邻空闲区释放区上邻空闲区释放区与上下空闲区均相邻释放区与上下空闲区均不相邻（5）程序流程图空闲链的首次适应算法分配流程图开始申请xkb内存由链头找到第一个空闲区分区大小xkb？大于分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针等于小于延链查找下一个空闲区到链尾了？作业等待返回是否登记已分配表返回分配给进程的内存首地址空闲链的首次适应算法回收流程图 开始输入完成进程的标号在分配区表中查找释放区p下邻分区空闲区前一个空闲区的后向指针指向p的后一个分区，p的后一个分区的前向指针指向p的前一个分区，且p的前一个分区大小更改为加上p的大小，释放p释放区p上邻分区空前一个分区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个分区，且p的后一个分区大小更改为加上p的大小释放区p上下均邻空闲区前一个空闲区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个空闲分区，且p的前一个空闲分区大小更改为加上p的大小再加上p的后一个空闲分区的大小，合并后的这个空闲区的后向指针指向p的下下个分区，如果p的下下个分区不为空，则其前向指针指向合并后的这个空闲区，释放p和p的下一个分区释放区p上下均不邻空闲区将p放在链首，并修改其状态位为空闲（6）截图 5设计总结及体会（1）首先这次实验的难度不小，它必须在熟悉掌握数据结构的链表和队列的前提下才能完成，这次实验中用了三个队列，就绪队列，执行队列和完成队列，就绪队列中的优先级数是有序插入的，当进行进程调度的时候，需要先把就绪队列的队首节点（优先级数最大的节点）移入执行队列中，当执行进程结束后，判断该进程是否已经完成，如果已经完成则移入完成队列，如果没有完成，重新有序插入就绪队列中，这就是这次实验算法的思想。（2）通过本实验，深刻地理解到了利用可变分区，采用首次适应算法为作业分配内存的过程。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后的作业分配大的内存空间创造了条件。其缺点是地低址部分不断被划分，会留下很多难以利用的，很小的空闲区，而每次查找又都是从低地址部分开始，这无疑会增加查找可用的空闲区时的开销。 参考书目：1 孙钟秀，操作系统教程，北京，高等教育出版社，2008.2 张丽芬，刘昕，刘利雄操作系统实验教程，北京，清华大学出版社，2010附录：（源程序）实验1：#include <stdio.h>#include <stdlib.h>#include <iostream>#define getpch(type) (type*)malloc(sizeof(type)using namespace std;struct pcb char pname10; char state; int super; int ntime; int rtime; struct pcb* link;*ready=NULL,*p;typedef struct pcb PCB;void sort() PCB *first, *second; int insert=0; if(ready=NULL)|(p->super)>(ready->super) p->link=ready; ready=p; else first=ready; second=first->link; while(second!=NULL) if(p->super)>(second->super) /*若插入进程比当前进程优先数大,插入到当前进程前面*/ p->link=second; first->link=p; second=NULL; insert=1; else /* 插入进程优先数最低,则插入到队尾*/ first=first->link; second=second->link; if(insert=0) first->link=p; void input() /* 建立进程控制块函数*/ int i,num; cout<<"请输入进程数：" cin>>num; if(num>=5) cout<<"为了便于演示，请输入一个小于5的数！n" <<"请输入进程号：n" cin>>num; if(num<5) for(i=0;i<num;i+) cout<<"进程号No.n"<<i+1; p=getpch(PCB); cout<<"输入进程名:n" cin>>p->pname; cout<<"输入进程优先数:n" cin>>p->super; cout<<"输入进程运行时间:n" cin>>p->ntime; cout<<endl; p->rtime=0;p->state='w' p->link=NULL; sort(); /* 调用sort函数*/ int space() int l=0; PCB* pr=ready; while(pr!=NULL) l+; pr=pr->link; return(l);void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/ cout<<"qnametstatetsupertndtimetruntimen" cout<<pr->pname; cout<<"t"<<pr->state; cout<<"t"<<pr->super; cout<<"t"<<pr->ntime; cout<<"t"<<pr->rtime; cout<<endl;void check() /* 建立进程查看函数 */ PCB* pr; cout<<"n当前正在运行的进程是: n"<<p->pname; /*显示当前运行进程*/ disp(p); pr=ready; cout<<"n当前就绪队列状态为:n" /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr->link; void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/ cout<<"进程"<<p->pname <<"已完成.n" free(p);void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ (p->rtime)+; if(p->rtime=p->ntime) destroy(); /* 调用destroy函数*/ else (p->super)-; p->state='w' sort(); /*调用sort函数*/ void cpuprio() /*主函数*/ int len,h=0; char ch; input(); len=space(); while(len!=0)&&(ready!=NULL) ch=getchar(); h+; cout<<"优先级最高的进程号是NO."<<h; cout<<"，其优先级是n"<<ready->super<<endl; p=ready; ready=p->link; p->link=NULL; p->state='R' check(); running(); cout<<"按回车键继续n" ch=getchar(); cout<<"进程已经完成n" ch=getchar();实验2:#include <iostream.>#include <malloc.h>#include <stdlib.h>using namespace std;typedef struct FreeLink/定义空闲链struct FreeLink *prior;char name;int start;int size;bool flag;struct FreeLink *next;* ptr,*head;head top;ptr p;void print()/将内存分配情况打印到屏幕上p=top;cout<<"*内存分配情况表*"<<endl;cout<<"区号tt"<<"起始位置t"<<"区间长度t"<<"区间状态t"<<endl;docout<<p->name<<"tt"<<p->start<<"tt"<<p->size<<"tt"if(p->flag=false)/flag为false，表明该分区空闲cout<<"空闲"<<endl;elsecout<<"已占用"<<endl;p=p->next;while(p!=NULL);void clear()/结束操作时清空“内存”以备其他操作dop=top;top=top->next;free(p);while(top!=NULL);cout<<"内存已清空！"void hebing(ptr &p)/若被操作的内存有相邻空闲区则将空闲区拼接合并int x;if(p->prior->flag=false&&p->next->flag=false)x=1; /释放区与上下空闲区均相邻if(p->prior->flag=false&&p->next->flag=true)|(p->prior->flag=false&&p->next=NULL)x=2;/释放区下邻空闲区if(p->prior->flag=true&&p->next->flag=false)|(p->prior=NULL&&p->next->flag=false)x=3;/释放区上邻空闲区if(p->prior->flag=true&&p->next->flag=true)|(p->prior=NULL&&p->next->flag=true)|(p->prior->flag=true&&p->next=NULL)x=4;/释放区与上下空闲区均不相邻 switch(x)case 1:p->next->prior=p->prior; p->prior->next=p->next; p->prior->size=p->prior->size+p->size+p->next->size; p->prior->next=p->next->next; if(p->next->next!=NULL) p->next->next->prior=p->next->prior; free(p->next);/释放 free(p); break; case 2:if(p->next=NULL)/p为最后一个分区 p->prior->next=p->next; else p->next->prior=p->prior; p->prior->next=p->next; p->prior->size=p->prior->size+p->size; free(p); break;case 3:if(p->prior=NULL)/p为第一个分区 top=p->next; p->next->prior=NULL; p->next->start=p->start; p->next->size=p->next->size+p->size; else p->next->prior=p->prior; p->prior->next=p->next;p->next->start=p->start; p->next->size=p->next->size+p->size; free(p); break;case 4:p->name='*'/将释放区移至链首并标记为未被占用 p->flag=false; break;void allocate(ptr &p)/最先适应法的内存分配函数FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink);cout<<"请输入要分配内存的进程号："cin>>fl->name;cout<<"请输入要分配内存的大小："cin>>fl->size;fl->flag=true;doif(p->flag=false&&p->size>fl->size) fl->start=p->start; p->start=fl->start+fl->size; p->size=p->size-fl->size; fl->next=p; fl->prior=p->prior; p->prior->next=fl; p->prior=fl; goto a;if(p->flag=false&&p->size=fl->size) p->flag=fl->flag; p->name=fl->name; free(fl); goto a;p=p->next;while(p!=NULL);cout<<"内存过小，分配失败！"<<endl;goto b;a: cout<<"分配成功！"<<endl;b: ;/啥也不做void huishou(ptr &p)/内存回收函数char n = ' 'cout<<"请输入要回收的内存对应的进程号："cin>>n;do if(p->flag=true&&p->name=n)hebing(p); goto c; p=p->next;while(p!=NULL);cout<<"内存未能分配给该进程，回收失败！"<<endl;goto d;c: cout<<"内存回收成功！"<<endl;d: ;int firstfit()/最先适应法char choice=' 'print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink);pcb->next=top;pcb->prior=top->prior; top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块号："cin>>pcb->name;cout<<"请输入要分配内存的大小："goto f;e:cout<<"超过内存最大容量，请重新输入要分配内存的大小："f:cin>>pcb->size;if(pcb->size>256)goto e;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true)dop=top->next;cout<<"请从下列选项中进行选择："<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择："cin>>choice;while(choice!='1'&&choice!='2'&&choice!='3');switch(choice)case '1':allocate(p);print();break;case '2':huishou(p);print();break;case '3':clear();return 0;break;int main()/主函数 ptr free=(FreeLink *)malloc(sizeof(FreeLink); top=free; top->name='*' top->start=0; top->size=256;top->flag=false; top->prior=NULL; top->next=NULL;cout<<endl;cout<<"* 首次适应算法 *"<<endl;cout<<endl;firstfit();