08级操作系统课程设计报告书

课程设计报告书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#include#include#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=5) /*while循环选择算法*/coutPlease select a number(1,2,3,4):i;switch(i) /*switch语句选择执行函数*/ case 1:FCFS();break;case 2:SJF();break;case 3:HRN();break;void init() /*对定义的变量进行赋值的函数*/int i=0;while(i=2000)coutInput the JCB number:(1-2000)i;jcbnum=i;for(i=0;ijcbnum;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赋值*/coutThis is frist come fist server:endl;for(i=0;ijcbnum;i+)/*for循环语句*/coutThe NO.jcbi.IDJCB enter Memory.endl;Waittime+=jcbi.requesttime;w=(Waittime-t)/(jcbi.requesttime);cout带权周转时间为：wendl; t+;void SJF()/*SJF函数*/int i,j,dest ,Waittime,w,t=0;/*定义的变量*/coutThis is shortest job first:0)dest=0;for(i=0;ijcbi.requesttime)/*条件语句*/dest=i;coutThe NO.jcbdest.IDJCB enter Mermoryendl; Waittime+=jcbdest.requesttime;w=(Waittime-t)/(jcbdest.requesttime);cout带权周转时间为：wendl;t+;for(j=dest;jjcbnum-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赋值*/coutThis is Highest responseratio first0)dest=0;for(i=0;i(waittime/(jcbi.requesttime)/*条件语句*/dest=i;coutThe NO.jcbdest.IDJCB enter Memory.endl;waittime+=jcbdest.requesttime;/*给waittime赋新值*/for(j=dest;j Needij出错返回：return(error)Requestij Availablej出错返回：(进程阻塞)return(error)Availablej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：输入初始参数（资源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化银行家算法流程图14 流程图15 主要程序代码#include 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; coutm; coutn; cout请输入每个进程最多所需的各资源数,按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jMAXij; cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij0) cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl; j-; continue; cout请输入各个资源现有的数目:endl; for(i=0;iAVAILABLEi; void Dijkstra() /*银行家算法*/ int i,cusneed; char again; while(1) cout请输入要申请资源的进程号(注:第1个进程号为0,依次类推)cusneed; cout请输入进程所请求的各资源的数量endl; for(i=0;iREQUESTcusneedi; for(i=0;iNEEDcusneedi) cout您输入的请求数超过进程的需求量!请重新输入!AVAILABLEi) cout您输入的请求数超过系统有的资源数!请重新输入!endl; continue; for(i=0;in;i+) AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() cout同意分配请求!endl; else cout您的请求被拒绝!endl; for(i=0;in;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;im;i+) FINISHi=false; cout您还想再次请求分配吗?是请按y/Y,否请按其它键again; if(again=y|again=Y) continue; break; bool Safe() /*安全性算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作数组*/ for(i=0;in;i+) Worki=AVAILABLEi; for(i=0;im;i+) FINISHi=false; for(i=0;im;i+) if(FINISHi=true) continue; else for(j=0;jWorkj) break; if(j=n) FINISHi=true; for(k=0;kn;k+) Workk+=ALLOCATIONik; pl+=i; i=-1; else continue; if(l=m) cout系统是安全的endl; cout安全序列:endl; for(i=0;il;i+) coutpi; if(i!=l-1) cout; coutendl; 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#include#include#include#includetypedef 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;jn;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(isi)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;in;i+) li.n=si; li.visited=0;for(int j=0;jn;j+)int s=1000;for(int k=0;kn;k+)if(lk.visited=0) m=abs(lk.n-a); if(ms)s=m; for(int p=0;pn;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;ia)lcount1.n=si; lcount1.visited=0;count1+;for(int j=0;jn;j+)if(sja)kcount2.n=sj; kcount2.visited=0;count2+; while(xn) if(z=1)for(int i=0;icount1;i+) int s=1000; for(int j=0;jcount1;j+) if(lj.visited=0) m=abs(lj.n-a); if(ms)s=m; for(int p=0;pcount1;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;icount2;i+) int s=1000; for(int j=0;jcount2;j+) if(kj.visited=0) m=abs(kj.n-a); if(ms)s=m; for(int p=0;pcount2;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; printf(n-n); printf(平均寻道数：%.1fn,sum/n);void cscan(int s,int a,int n,int z)int m;L l50;int t;int y=0;float sum=0.0; printf(循环扫描算法：n);printf(-n);printf(磁道号|移动距离n); for(int i=0;in;i+) li.n=si; li.visited=0;for(int k=0;kn-1;k+) t=lk+1.n; for(int p=0;pt)break; if(pk)continue; for(int j=k;jp-1;j-)lj+1.n=lj.n; lp.n=t;while(yn)int j;if(z=1) for(j=0;ja)break; for(int k=j;kn;k+) m=lk.n-a; lk.visited=1; a=lk.n; y+; printf(n%6d|%6d,lk.n,m); sum=sum+float(m); for(int h=0;hj;h+) m=abs(lh.n-a); lh.visited=1; a=lh.n; y+; printf(n%6d|%6d,lh.n,m); sum=sum+float(m); if(z=0) for(j=0;jn;j+)if(lj.na)break; for(int h=0;hj;h+) m=abs(lh.n-a); lh.visited=1; a=lh.n; y+; printf(n%6d|%6d,lh.n,m); sum=sum+float(m); for(int k=j;kn;k+) m=abs(lk.n-a); lk.visited=1; a=lk.n; y+; printf(n%6d|%6d,lk.n,m); sum=sum+float(m); printf(n-n);printf(平均寻道数：%.1fn,sum/n);16 运行结果及分析(1)先来先服务算法运行结果：（2）最短寻道时间优先算法运行结果：（3）SCAN算法运行结果：（4）CSCAN算法运行结果：17 心得体会整个设计中最麻烦的就是程序模块的划分和各模块之间接口设计，编程经常犯想当然的错误，出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.在算法实现上要有一定的思路体现设计的目的。同时上机调试也是十分重要的，在调试的过程中能够不断的发现在编写算法时应该注意的一些细节和算法语句的非法使用，在调试过程中通过对算法的不断测试、更正、扩充功能、修饰细节，使算法程序不断的得到完善。题目4 读者/写者问题11 题目的主要研究内容及预期达到的目标（1）利用多进程或多线程模拟实现读者/写者问题。（2）基本完成了利用多进程或多线程模拟实现读者/写者问题。12 题目研究的工作基础或实验条件（1）硬件环境：windows系统（2）软件环境： C语言13 设计思想（1）读者优先 如果没有写者正在操作，则读者不需要等待，用一个整型变量g_NumOfReading记录读者数目，用于确定是否释放读者线程，g_NumOfReading的初值为0.当线程开始调入时.每个读者准备读. 等待互斥信号,保证对g_NumOfReading的访问,修改互斥.即g_NumOfReading+.而当读者线程进行读操作时,则读者数目减少(g_NumOfReading-).当g_NumOfReading=0 时，说明所有的读者都已经读完.（2）写者优先写者优先与读者不同之处在于一旦一个写者到来，它应该尽快对文件进行写操作，如果有一个写者在等待，则新到来的读者不允许进行读操作。为此应当填加一个整形变量g_NumOfWriteRequest，用于记录正在等待的写者的数目，g_NumOfWriteRequest的初值为0.当线程开始调入时.只允许一个写者准备读. 等待互斥信号,保证对g_NumOfWriteRequest 的访问,修改互斥.即g_NumOfWriteRequest+.而当写者线程进行读操作时,则相应写者数目减少(g_NumOfWriteRequest-).当g_NumOfWriteRequest=0 时，说明所有的读者都已经读完，离开临界区唤醒读者,释放互斥信号.14 流程图（1）读者优先流程图：（2）写者优先流程图：15 主要程序代码#include windows.h #include #include #include #include #include #include #define READER R /读者 #define WRITER W /写者 #define INTE_PER_SEC 1000 /每秒时钟中断的数目 #define MAX_THREAD_NUM 64 /最大线程数 #define MAX_FILE_NUM 32 /最大文件数目数 #define MAX_STR_LEN 32 /字符串的长度 int readcount=0; /读者数目 int writecount=0; /写者数目 CRITICAL_SECTION RP_Write; /临界资源 CRITICAL_SECTION cs_Write; CRITICAL_SECTION cs_Read; struct ThreadInfo int serial; /线程序号 char entity; /线程类别(判断是读者还是写者线程) double delay; /线程延迟时间 double persist; /线程读写操作时间 ; / / 读者优先-读者线程 /P:读者线程信息 void RP_ReaderThread(void *p) /互斥变量 HANDLE h_Mutex; h_Mutex=OpenMutex(MUTEX_ALL_ACCESS,FALSE,mutex_for_readcount); DWORD wait_for_mutex; /等待互斥变量所有权 DWORD m_delay; /延迟时间 DWORD m_persist; /读文件持续时间 int m_serial; /线程序号 / 从参数中获得信息 m_serial=(ThreadInfo*)(p)-s