08级操作系统课程设计报告书(共39页).doc
精选优质文档-倾情为你奉上课程设计报告书2011 / 2012 学年 第 1 学期课程名称：操作系统实践课程设计 专业班级：学 号：姓 名： 指导教师： 课程设计指导教师评语 成 绩：_ 指导教师签字：_题目1 进程调度算法的模拟11 题目的主要研究内容及预期达到的目标（1）编程序模拟实现进程调度算法中的FCFS、SJF和高响应比优先算法。（2）基本完成了模拟实现FCFS、SJF 和HRN调度算法。12 题目研究的工作基础或实验条件（1）硬件环境：windows系统（2）软件环境：Visual C+ 13 设计思想 （1）FCFS:将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片，就出让CPU（如阻塞）。(2)SJF：对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。（3）HRN：HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。14 流程图15 主要程序代码#include<iostream.h>#include<stdio.h>#include<stdlib.h>#define N 100typedef struct JCBint ID; /*作业标识数*/int requesttime; /*作业运行所需时间*/int runtime; /*作业实际运行所需时间*/int priority; /*作业优先数*/int quick; /*作业紧迫程度*/JCB;JCB jcbN;int jcbnum; /*后备作业数*/void init(); /*赋值函数*/void FCFS(); /*定义FCFS函数*/void SJF();/*定义SJF函数*/void HRN();/*定义HRN函数*/void main() /*main函数*/int i=0;init();cout<<"="<<endl;cout<<"| 1:FCFS 2:SJF |"<<endl;cout<<"| 3:HRN |"<<endl;cout<<"="<<endl;while(i<=0|i>=5) /*while循环选择算法*/cout<<"Please select a number(1,2,3,4):"<<endl;cin>>i;switch(i) /*switch语句选择执行函数*/ case 1:FCFS();break;case 2:SJF();break;case 3:HRN();break;void init() /*对定义的变量进行赋值的函数*/int i=0;while(i<=0|i>=2000)cout<<"Input the JCB number:(1-2000)"<<endl;cin>>i;jcbnum=i;for(i=0;i<jcbnum;i+) /*for循环赋值语句*/jcbi.ID=i+1;jcbi.priority=rand()%100+1;jcbi.quick=rand()%5+1;jcbi.requesttime=rand()%1000+1;void FCFS()/*FCFS函数*/int i;int w=0,t=0; int Waittime=0;/*给waitime赋值*/cout<<"This is frist come fist server:"<<endl;for(i=0;i<jcbnum;i+)/*for循环语句*/cout<<"The NO."<<jcbi.ID<<"JCB enter Memory."<<endl;Waittime+=jcbi.requesttime;w=(Waittime-t)/(jcbi.requesttime);cout<<"带权周转时间为："<<w<<endl; t+;void SJF()/*SJF函数*/int i,j,dest ,Waittime,w,t=0;/*定义的变量*/cout<<"This is shortest job first:"<<endl;while(jcbnum>0)dest=0;for(i=0;i<jcbnum;i+)/*for循环语句*/if(jcbdest.requesttime>jcbi.requesttime)/*条件语句*/dest=i;cout<<"The NO."<<jcbdest.ID<<"JCB enter Mermory"<<endl; Waittime+=jcbdest.requesttime;w=(Waittime-t)/(jcbdest.requesttime);cout<<"带权周转时间为："<<w<<endl;t+;for(j=dest;j<jcbnum-1;j+)/*用for语句进行赋值*/jcbj.ID=jcbj+1.ID;jcbj.requesttime=jcbj+1.requesttime;jcbnum-;void HRN()/*HRN函数*/int i,j,dest;/*定义的变量*/int waittime=0;/*给waitime赋值*/cout<<"This is Highest responseratio first"<<endl;while(jcbnum>0)dest=0;for(i=0;i<jcbnum;i+)/*for循环语句*/if(waittime/(jcbdest.requesttime)>(waittime/(jcbi.requesttime)/*条件语句*/dest=i;cout<<"The NO."<<jcbdest.ID<<"JCB enter Memory."<<endl;waittime+=jcbdest.requesttime;/*给waittime赋新值*/for(j=dest;j<jcbnum-1;j+)/*用for语句进行赋值*/jcbj.ID=jcbj+1.ID;jcbj.requesttime=jcbj+1.requesttime;jcbnum-;16 运行结果及分析（1）FCFS算法运行结果（2）SJF算法运行结果：（3）HRN算法运行结果17 心得体会整个设计中最麻烦的就是程序模块的划分和各模块之间接口设计，编程经常犯想当然的错误，出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.在算法实现上要有一定的思路体现设计的目的。同时上机调试也是十分重要的，在调试的过程中能够不断的发现在编写算法时应该注意的一些细节和算法语句的非法使用，在调试过程中通过对算法的不断测试、更正、扩充功能、修饰细节，使算法程序不断的得到完善。题目2 银行家算法的实现11 题目的主要研究内容及预期达到的目标（1）编程序模拟实现银行家算法。（2）基本完成了模拟实现银行家算法。12 题目研究的工作基础或实验条件（1）硬件环境：windows系统（2）软件环境：C语言 13 设计思想 （1）银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示Requestij=k。系统按下述步骤进行安全检查：1）如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。2）如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。（2）安全性算法1）设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; 4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。结束 否是申请失败。以上分配作废，恢复原来的分配状态：Availablej = Availablej + RequestijAllocationij= AllocationijRequestijNeedij = Needij+RequestijNYNYRequestij> Needij出错返回：return(error)Requestij> Availablej出错返回：(进程阻塞)return(error)Availablej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：输入初始参数（资源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化银行家算法流程图14 流程图15 主要程序代码#include <iostream>using namespace std;#define MAXPROCESS 50 /*最大进程数*/#define MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int m,n; /*m个进程,n个资源*/void Init();bool Safe();void Dijkstra();int main() Init(); Safe(); Dijkstra();void Init() /*初始化算法*/ int i,j; cout<<"请输入进程的数目:" cin>>m; cout<<"请输入资源的种类:" cin>>n; cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>MAXij; cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>ALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij<0) cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl; j-; continue; cout<<"请输入各个资源现有的数目:"<<endl; for(i=0;i<n;i+) cin>>AVAILABLEi; void Dijkstra() /*银行家算法*/ int i,cusneed; char again; while(1) cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl; cin>>cusneed; cout<<"请输入进程所请求的各资源的数量"<<endl; for(i=0;i<n;i+) cin>>REQUESTcusneedi; for(i=0;i<n;i+) if(REQUESTcusneedi>NEEDcusneedi) cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl; continue; if(REQUESTcusneedi>AVAILABLEi) cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl; continue; for(i=0;i<n;i+) AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() cout<<"同意分配请求!"<<endl; else cout<<"您的请求被拒绝!"<<endl; for(i=0;i<n;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;i<m;i+) FINISHi=false; cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl; cin>>again; if(again='y'|again='Y') continue; break; bool Safe() /*安全性算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作数组*/ for(i=0;i<n;i+) Worki=AVAILABLEi; for(i=0;i<m;i+) FINISHi=false; for(i=0;i<m;i+) if(FINISHi=true) continue; else for(j=0;j<n;j+) if(NEEDij>Workj) break; if(j=n) FINISHi=true; for(k=0;k<n;k+) Workk+=ALLOCATIONik; pl+=i; i=-1; else continue; if(l=m) cout<<"系统是安全的"<<endl; cout<<"安全序列:"<<endl; for(i=0;i<l;i+) cout<<pi; if(i!=l-1) cout<<"->" cout<<""<<endl; return true; cout<<"系统是不安全的"<<endl; return false; 16 运行结果及分析17 心得体会整个设计中最麻烦的就是程序模块的划分和各模块之间接口设计，编程经常犯想当然的错误，出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.在算法实现上要有一定的思路体现设计的目的。同时上机调试也是十分重要的，在调试的过程中能够不断的发现在编写算法时应该注意的一些细节和算法语句的非法使用，在调试过程中通过对算法的不断测试、更正、扩充功能、修饰细节，使算法程序不断的得到完善。题目3 磁盘调度算法的模拟11 题目的主要研究内容及预期达到的目标（1）编程序模拟实现磁盘调度算法中的FCFS、SSTF、SCAN和CSCAN算法。（2）基本完成了模拟实现FCFS、SSTF、SCAN和CSCAN调度算法。12 题目研究的工作基础或实验条件（1）硬件环境：windows系统（2）软件环境： C语言13 设计思想 （1） 先来先服务(First-Come，First-Served，FCFS):这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。(2) 最短寻道时间优先(ShortestSeekTimeFirst，SSTF):该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。(3) 扫描(SCAN)算法:SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。(4) 循环扫描(CSCAN)算法:处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种延迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。14 流程图（1）FCFS算法流程图：（2）SSTF算法流程图：（3）SCAN算法:（4）CSCAN算法：15 主要程序代码#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<math.h>#include<time.h>typedef struct int n;int visited;L;void fifo(int s,int a,int n);void zuijin(int s,int a,int n);void scan(int s,int a,int n,int z);void cscan(int s,int a,int n,int z);int a;int NG=0;float Nsum=0;void main() int string50; int i; int j=0; int n; int f; int N; printf("输入当前磁道号(0-200):"); scanf("%d",&a); printf("输入要访问的磁道数量(0-50)："); scanf("%d",&n); for(j;j<n;j+) printf("输入寻道序列串："); scanf("%d",&stringj); printf("-n"); printf("| 0.退出 |n"); printf("| 1.先来先服务 |n"); printf("| 2.最短寻道时间优先 |n"); printf("| 3.电梯调度算法 |n"); printf("| 4.循环扫描算法 |n"); printf("| 5.返回菜单 |n"); printf("-n"); printf("选择："); while(i!=0) scanf("%d",&i); switch(i) case 0:i=0; break; case 1:fifo(string,a,n); break; case 2:zuijin(string,a,n); break; case 3:printf("输入磁头移动方向(0 向内 1向外)："); scanf("%d",&f); scan(string,a,n,f); break; case 4:printf("输入磁头移动方向(0 向内 1向外)："); scanf("%d",&f); cscan(string,a,n,f); break; case 5:printf("-n"); printf("| 0.退出 |n"); printf("| 1.先来先服务 |n"); printf("| 2.最短寻道时间优先 |n"); printf("| 3.电梯调度算法 |n"); printf("| 4.循环扫描算法 |n"); printf("| 5.返回菜单 |n"); printf("-n"); printf("选择："); break; void fifo(int s,int a,int n)int i=0,m;float sum=0;printf("先来先服务算法：n");printf("-n");printf("磁道号|移动距离n");while(i<n)if(a>si)m=a-si;else m=si-a;a=si;printf("%6d|%6dn",si,m);sum=sum+float(m);i+;printf("n-n");printf("平均寻道数：%.1fn",sum/n);void zuijin(int s,int a,int n) int m; L l50;float sum=0; printf("最短寻道时间优先算法：n");printf("-n");printf("磁道号|移动距离n");for(int i=0;i<n;i+) li.n=si; li.visited=0;for(int j=0;j<n;j+)int s=1000;for(int k=0;k<n;k+)if(lk.visited=0) m=abs(lk.n-a); if(m<s)s=m; for(int p=0;p<n;p+)if(lp.visited=0)if(s=abs(lp.n-a)lp.visited=1;a=lp.n;printf("n%6d|%6d",lp.n,s);sum=sum+float(s);printf("n-n"); printf("平均寻道数：%.1fn",sum/n);void scan(int s,int a,int n,int z) int m;int count1=0,count2=0;int x=0;L l50;L k50;float sum=0; printf("电梯调度算法：n");printf("-n");printf("磁道号|移动距离n"); for(int i=0;i<n;i+)if(si>a)lcount1.n=si; lcount1.visited=0;count1+;for(int j=0;j<n;j+)if(sj<a)kcount2.n=sj; kcount2.visited=0;count2+; while(x<n) if(z=1)for(int i=0;i<count1;i+) int s=1000; for(int j=0;j<count1;j+) if(lj.visited=0) m=abs(lj.n-a); if(m<s)s=m; for(int p=0;p<count1;p+) if(lp.visited=0)if(s=abs(lp.n-a)lp.visited=1;a=lp.n;printf("n%6d|%6d",lp.n,s);sum=sum+float(s);x+; z=0; if(z=0)for(int i=0;i<count2;i+) int s=1000; for(int j=0;j<count2;j+) if(kj.visited=0) m=abs(kj.n-a); if(m<s)s=m; for(int p=0;p<count2;p+) if(kp.visited=0)if(s=abs(kp.n-a)kp.visited=1;a=kp.n;printf("n%6d|%6d",kp.n,s);sum=sum+float(s);x+; z=1; Nsum=sum;NG=a;
