进程调度算法磁盘调度算法银行家算法操作系统课程设计大全bxaj.docx

操作系统课程设计说明书学院名称： 专业班级： 姓 名： 学 号： 2010年7月16日评分标准优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确；及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，抄袭或雷同。成绩评定为： 。 指导教师： 年 月 日目 录 一进程调度算法 4-23 页二银行家算法 24-34 页三磁盘调度算法 35-46页进程调度算法1设计目的 在多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略决定哪个进程优先占有处理机，因而必须解决进程调度的问题，进程调度算法就是要解决进程调度的问题。2. 任务及要求2.1 设计任务 设计程序来模拟进程的四种调度算法，模拟实现调度的基本功能。2.2 设计要求 产生的各种随机数要加以限制，如alltime限制在40以内的整数。进程的数量n不能取值过大。3. 算法及数据结构3.1算法的总体思想（流程） 每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，优先数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0：就绪态；1：运行态；2：阻塞态。 利用链表将数据连接起来，实现数据的存储。3.2 链表模块3.2.1 功能 实现链表的存储功能，以及实现存储的查找功能。3.2.2 数据结构 构造链表这个数据结构，以及链表的初始化，链表的插入，链表的长度。3.2.3 算法 typedef struct ElemType *elem; int length; int listsize; SqList;Status InitList(SqList &l)l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!l.elem) exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;return OK;int ListLength(SqList l)return(l.length);Status ListInsert_Sq(SqList &L,int i, ElemType e)/在顺序表L的第i个位置前插入元素e,i的合法值为1.L.length+1 if(i<1|i>L.length+1) return ERROR; if(L.length>=L.listsize) ElemType*newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; ElemType *q=&L.elemi-1, *p=&L.elemL.length-1; while(p>=q) *(p+1)=*p; -p; /插入位置后的元素右移 *q=e; +L.length; return OK;Status GetElem(SqList L,int i,ElemType &e)if(i<=0|i>L.length)return ERROR;elsee=*(L.elem+i-1);return OK;void Outputlist(SqList &L)if(0=L.length)printf("空集!");else for(int i=0;i<L.length;+i) printf("%c",*(L.elem+i);3.3 主函数模块3.3.1功能 实现进程调度的四种算法，以及人机交互的菜单。3.3.2 数据结构 主要包括五个部分，分别是四种算法，和进程的输入和菜单部分，功能分别实现。3.3.3算法void main()for(1;)int number; PCB pcb100 ;srand(time(0);int max;int ppp100;int time=0;int time1;int m;int a100;a0=0;printf("n*进程调度算法的模拟*n");printf("* 1.先到先服务调度 2.最短作业优先调度 *n");printf("* 3.优先权调度 4.轮转发调度 *n");printf("*");printf("n请选择调度的方法: ");scanf("%d",&m);if(m!=1&&m!=2&&m!=3&&m!=4) printf("输入错误! 重新输入: "); scanf("%d",&m); if(m!=1&&m!=2&&m!=3&&m!=4) printf("输入错误! 重新输入: "); scanf("%d",&m); if(m!=1&&m!=2&&m!=3&&m!=4) printf("输入错误! 重新输入: "); scanf("%d",&m); if(m!=1&&m!=2&&m!=3&&m!=4) printf("输入错误! 重新输入: "); scanf("%d",&m); printf("请输入进程的个数: ");scanf("%d",&number);printf("n开始时用户进程均为就绪状态,运行时间随机产生nn");SqList sq;InitList(sq);for(int r=0;r<number;r+)pcbr.CPUtime=0;for(int i=0;i<number;i+) pcbi.Priority=rand()%50;while(1) if(pcbi.Priority<20) pcbi.Priority=rand()%50; else break; pcbi.Alltime=rand()%40;while(1) if(pcbi.Alltime<10) pcbi.Alltime=rand()%40;else break;for(int j=0;j<number;j+)ListLength(sq);ListInsert_Sq(sq,ListLength(sq),pcbi ); if(m=1) printf("n*程序演示开始*n"); int coun=0; /计数变量 int wait100; /等待时间数组 wait0=0; int Allwait=0; for(int i1=0;i1<number;i1+)printf("下面开始调用第%d个进程； n",i1); printf("开始时间为%d 执行时间为%dn",coun,pcbi1.Alltime); coun+=pcbi1.Alltime; if(i1!=0)waiti1=pcbi1-1.Alltime+waiti1-1; for(int i2=0;i2<number;i2+)Allwait=waiti2+Allwait; printf("平均等待时间为:%dn",Allwait/number); if(m=2) int min=pcb0.Alltime; int wait1100; wait10=0; int in=0; int coun1=0; printf("*最短作业优先调度!*n"); cout<<"进程所需时间分别是:"<<endl; for(i=0;i<number;i+) cout<<pcbi.Alltime<<endl; printf("进程调度的顺序为: "); for(i=0;i<number;i+) min=50; for(j=0;j<number;j+) if(pcbj.Alltime<min) min=pcbj.Alltime; in=j; printf("%d ",in+1); pcbin.Alltime+=50; if(m=3) printf("ID 优先级 运行总时间 进程状态n"); for(int k=0; k<number; k+) printf("%d %d %d 就绪n",k+1, pcbk.Priority, pcbk.Alltime); printf("n*程序调度演示开始*n"); for(int f=1;f<1000;f+) int count=0,count1=0; for(int i=0;i<number;i+) pppi=pcbi.Priority; if(pcbi.Alltime!=0) count1+; count1-; time=time+count1*4; max=Max(ppp,number); if(pcbmax.Alltime=0) pppmax=-1; pcbmax.Priority=-1; max=Max(ppp,number); pcbmax.Priority-=4; pcbmax.Alltime-=4; pcbmax.CPUtime+=4; if(pcbmax.Alltime<=0) pcbmax.Alltime=0; for(int w=0;w<number;w+) if(pcbw.Alltime=0) pppw=-1; pcbw.Priority=-1; for(int e=0; e<number;e+) pcbe.Priority+; printf("n#第%d个进程正在执行!#n",max+1); printf("n第%d次调度结束，运行结果为:nn",f); printf("ID 优先级 需要总时间 执行时间n"); for(int k=0; k<number; k+) printf("%d %d %d %d n",k+1, pcbk.Priority, pcbk.Alltime,pcbk.CPUtime); for(int l=0;l<number;l+) if(pcbl.Alltime=0) count+; if(count=number) break; time1=time/number; printf("n*用户进程全部执行完毕!*"); printf("nn平均等待时间是: "); printf("%dnn",time1); if(m=4) printf("ID 运行总时间 进程状态n"); for(int k=0; k<number; k+)printf("%d %d 就绪n",k+1, pcbk.Alltime); printf("n*程序调度演示开始*n"); for(int f=1;f<1000;f+)int count=0; for(i=0;i<number;i+)if(pcbi.Alltime=0)continue;if(pcbi.Alltime>0)pcbi.Alltime-=4; pcbi.CPUtime+=4; if(pcbi.Alltime<0)pcbi.Alltime=0; / printf("n#第%d个进程正在执行!#n",i+1); printf("n第%d次调度结束，运行结果为:nn",f); printf("ID 需要时间 执行时间n"); for(int k=0; k<number; k+) printf("%d %d %d n",k+1, pcbk.Alltime,pcbk.CPUtime);/for(int l=0;l<number;l+)if(pcbl.Alltime=0)count+; if(count=number)break;printf("n*用户进程全部执行完毕!*"); 4. 实验结果及分析4.1 实验结果 先到先服务算法的实验结果如下：最短作业优先调度的实验结果如下：优先权调度算法的实验结果如下：轮转法调度的实验结果如下：4.2 结果分析 本次试验基本实现了进程调度的四种算法，每一种算法都能模拟出算法的具体过程。相应的结果也完全符合预想的结果。同时，对于算法的实践编写进一步增加了编程的技巧，以及编程的熟练程度。银行家算法1设计目的 银行家算法是避免死锁的一种十分重要的方法，通过编写一个模拟的动态的银行家算法的程序，能够进一步加深对死锁的理解，以及产生死锁的必要条件。并掌握通过银行家算法来避免死锁。2. 任务及要求2.1 设计任务 根据银行家算法的基本思想来设计程序，模拟银行家算法的过程。用程序来实现银行家算法的具体动态过程。2.2 设计要求 根据银行家算法的基本思想，编写和调试一个能实现动态的分配资源的模拟程序。并能够有效的防止死锁的发生。3. 算法及数据结构3.1算法的总体思想（流程） 银行家算法的基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后会试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源作对比，找出剩余资源能满足的进程，从而保证进程运行完并释放资源继续满足剩下进程对资源的需要。最后检查集合为空集时表明本次申请可行，系统继续处于安全状态，可以实施本次分配。否则不能实施本次分配。3.2 显示资源矩阵 showdata() 模块3.2.1 功能 主要是显示资源的矩阵，包括输入的已分配的的资源矩阵，以及输出的资源矩阵。3.2.2 数据结构 最大需求矩阵max以及已分配矩阵allocation，分别定义为m*n阶的矩阵，利用二维数组来存储。3.2.3 算法void showdata() /显示资源矩阵 int i,j; cout<<"系统目前可用的资源Avaliable:"<<endl; for(i=0;i<N;i+) cout<<namei<<" " cout<<endl; for (j=0;j<N;j+) cout<<Avaliablej<<" " /输出分配资源 cout<<endl; cout<<" Max Allocation Need"<<endl; cout<<endl; cout<<"进程名 " for(j=0;j<3;j+) for(i=0;i<N;i+) cout<<namei<<" " cout<<" " cout<<endl; for(i=0;i<M;i+) cout<<" "<<i<<" " for(j=0;j<N;j+) cout<<Maxij<<" " cout<<" " for(j=0;j<N;j+) cout<<Allocationij<<" " cout<<" " for(j=0;j<N;j+) cout<<Needij<<" " cout<<endl; 3.3 申请资源判定模块3.3.1功能 利用银行家实现对申请的资源进行判定。3.3.2 数据结构 对已经存储的矩阵进行比较。3.3.3算法void share() /利用银行家算法对申请资源对进行判定 char ch; int i=0,j=0; ch='y' cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):" cin>>i; /输入须申请的资源号 cout<<"请输入进程 "<<i<<" 申请的资源:"<<endl; for(j=0;j<N;j+) cout<<namej<<":" cin>>Requestj; /输入需要申请的资源 for (j=0;j<N;j+) if(Requestj>Needij) /判断申请是否大于需求，若大于则出错 cout<<"进程 "<<i<<"申请的资源大于它需要的资源" cout<<" 分配不合理，不予分配！"<<endl; ch='n' break; else if(Requestj>Avaliablej) /判断申请是否大于当前资源，若大于则 cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源" cout<<" 分配出错，不予分配!"<<endl; ch='n' break; if(ch='y') changdata(i); /根据进程需求量变换资源 showdata(); /根据进程需求量显示变换后的资源 safe(); /根据进程需求量进行银行家算法判断 3.4 主函数模块3.4.1功能 实现银行家算法对资源的增加、删除、修改。3.4.2 数据结构 对已经完成的模块进行功能集成。3.4.3算法int main() int i,j,number,choice,m,n,flag; char ming; cout<<endl; cout<<"* 银*行*家*算*法 *"<<endl;cout<<endl; cout<<"请输入资源的种类: " cin>>n;cout<<endl; N=n; for(i=0;i<n;i+) cout<<"资源"<<i+1<<"的名称,只限单个字符: " cin>>ming; namei=ming; cout<<"资源的数量:" cin>>number; Avaliablei=number; cout<<endl; cout<<"请输入进程的数量:" cin>>m; M=m; cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵):"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>Maxij; doflag=0; cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵):"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>Allocationij; if(Allocationij>Maxij) flag=1; Needij=Maxij-Allocationij; if(flag) cout<<"申请的资源大于最大需求量，请重新输入!n"<<endl;while(flag); showdata(); /显示各种资源 safe(); /用银行家算法判定系统是否安全 while(choice)cout<<"*银行家算法演示*"<<endl; cout<<" 1:增加资源 " cout<<" 2:删除资源 " <<endl; cout<<" 3:修改资源 " cout<<" 4:分配资源 " <<endl; cout<<" 5:增加进程 " cout<<" 0:离开 " <<endl; cout<<"*"<<endl; cout<<"请选择功能号：" cin>>choice; switch(choice) case 1: addresources();break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break; case 5: addprocess();break; case 0: choice=0;break; default: cout<<"请正确选择功能号(0-5)!"<<endl;break; return 1;4. 实验结果及分析4.1 实验结果4.2 结果分析 银行家算法就是在系统分配资源时，找到一个安全序列，使得进程间不会发生死锁。若发生死锁则让进程等待。 4.3实验总结 通过本次试验，加深了我对银行家算法的理解，掌握了如何利用银行家算法来避免死锁。通过对代码的编写也加深了我对数据结构的进一步理解。磁盘调度算法1设计目的 加深对操作系统的磁盘调度的进一步理解以及进一步的认识。加强实践能力和动手动脑能力，同时加深对磁盘调度概念的理解，同时也再一次提高了自己编程的能力。2. 任务及要求2.1 设计任务 分析设计模拟磁盘管理系统的方法，加深对磁盘调度算法的了解以及个算法的特点。2.2 设计要求 分别设计出先来先服务算法，最短寻道时间优先算法，扫描算法。并分别求出它们的平均寻道时间。3. 算法及数据结构3.1算法的总体思想（流程） 1.先来先服务的算法，即先来的请求先被响应。FCFS算法看起来是比较合理的算法，但是当请求频率过高的时候FCFS算法的响应时间就会大大的延长，这也是最基本的算法，直接实现的是由输入的顺序来顺序的执行。2.最短寻道时间优先算法，要求访问的磁道，与当前磁头所在的磁道的距离最近，从而以使每次的寻道时间最短。3.扫描磁盘调度，该算法不考虑与访问磁道与当前磁道的距离，更优先考虑的磁头当前的移动方向，例如，当磁头正在有向外移动时，SCAN算法所考虑的下一个访问对象，应是其与访问的磁道，即在当前磁道之外，又是最近的。这样磁头逐渐的从外向里移动，直至再无更里面的磁道要访问，从而避免了出饥饿的情况。3.2先来先服务模块3.2.1 功能 实现磁盘调度的先来先服务调度。3.2.2 数据结构 用链表来存储输入的数据，即各待访问的磁道。然后遍历这个链表，依次对这个链表进行访问，从而实现先来先服务调度。3.2.3 算法 void fcfs(Node *head,int c,int f) /先来先服务算法void print(Node *); Node *l; /,*m,*n; float num=0; l=head->next; for(int i=0;i<c;i+)num+=abs(l->data-f); f=l->data; l=l->next; num=num/c; cout<<"先来先服务的寻道顺序是:"<<endl; print(head); cout<<"平均寻道长度:"<<num<<end