06060111-王江-先来先服务和短进程优先调度算法模拟.docx

西安建筑科技大学华清学院课程设计（论文）课程设计（论文）题 目: 先来先服务和短进程 优先调度算法模拟 院 （系）： 华清学院 专业班级： 计算机2011 姓 名： 王江 学 号： 11 指导教师： 曾应员 2013年 12 月 18日第16页 共16页西安建筑科技大学华清学院课程设计（论文）任务书专业班级： 计算机1101 学生姓名： 王江 指导教师（签名）： 一、课程设计（论文）题目先来先服务和短进程优先调度算法模拟（进程调度）：编写一个进程调度程序，允许多个进程并行执行，并能选择是先来先服务算法还是短进程优先算法。二、本次课程设计（论文）应达到的目的操作系统课程实践性比较强。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：深入掌握进程调度的概念原理和实现方法。三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等） 先来先服务调度算法是以进程的到达时间为判断标准，按各个进程所的到达时间先后顺序进行调度。短进程优先调度算法是按进程的预计运行时间长短进行排序，先执行短进程。四、应收集的资料及主要参考文献： 操作系统经典算法的编程实现资料非常丰富，可以在图书馆找书籍或在因特网上找资料，都很容易找到，但是大部分代码是不全的，不能直接运行，希望大家只是把它当参考，编码还是自己做。 参考文献：【1】汤小丹、梁红兵、哲凤屏、汤子瀛 编著.计算机操作系统（第三版）.西安：西安电子科技大学出版社，2007.5【2】史美林编.计算机操作系统教程.北京：清华大学出版社，1999.11【3】徐甲同编著.操作系统教程.西安：西安电子科技大学出版社，1996.8【4】Clifford，A.Shaffer编著.数决结构与算法分析(C+版).北京：电子工业出版社，2005.7【5】蒋立翔编著.C+程序设计技能百练.北京：中国铁道出版社，2004.1五、审核批准意见教研室主任（签字） 设计总说明能够选择不同的调度算法（先来先服务，非强占式短进程优先算法），通过给出进程名、进程的到达时间和进程的运行时间，根据调度算法计算出进程的平均周转时间和平均带权周转时间，比较调度算法的优劣。关键字：先来先服务 短进程优先调度 进程 平均周转时间 平均带权周转时间目录1.设计目的12.问题描述23.需求分析24.概要设计35.详细设计46.调试分析77.使用说明88.设计总结109.参考文献1110.程序源代码12操作系统课程设计先来先服务和短进程优先调度算法模拟1.设计目的“操作系统”是计算机专业的核心专业课，“操作系统课程设计”是理解和巩固操作系统基本理论、原理和方法的重要的实践环节。 操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统基本理论与管理方式。在算法基础上，解决实际的管理功能的问题，提高学生实际应用、编程的能力。课程设计要求学生在完成程序设计的同时能够撰写比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。2.问题描述此次做的进程调度模拟系统，用户可以输入各进程信息（包含进程名、到达时间、运行时间）。输入进程数，然后输入进程的提交时间和运行时间，显示先来先服务调度算法和非强占式短进程优先调度算法的作业号、提交时间、运行时间、开始时间、结束时间、周转时间、带权周转时间、执行时间、平均周转时间和平均带权周转时间。3.需求分析3.1 数据需求 需要用户自行键入进程数,进程提交时间和运行时间.3.2 基本功能需求模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。 3.3 非功能性需求用户界面需求：简洁、易用、易懂、友好的用户界面。硬件要求：装有Visual C+6.0的计算机。可靠性需求：保证用户在正常使用本系统时，用户的操作或误操作不会产生数据的丢失。4.概要设计4.1 数据结构此次程序从大的方面来说是利用链表来实现的，在程序中定义了一个结构体struct PCB用来保存每一条记录，每个结点包括进程名（作业名）、进程的提交时间、运行时间、开始时间、结束时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。定义一个double型的handtime（提交时间），一个double型的asktime（运行时间）、starttime（开始时间）、endtime（结束时间）、usetime（周转时间）、right（带权周转时间）以及整型的runorder（执行的顺序）和num（进程数），还定义一个指针next。4.2 系统包含的函数4.2.1 先来先服务调度算法：void FCFS(pro p,int n)4.2.2非强占式短进程优先调度算法：void SJF(pro p,int n)4.2.3主函数:int main()4.3 函数间的关系函数SJF和函数FCFS都在主函数中进行调用4.4 系统功能模块图图4-1系统功能模块图5.详细设计5.1 结构体的详细定义Struct pro的定义如下： struct prodouble handtime;double asktime;double starttime;double endtime;double usetime;double right;int runorder;int num;pro *next;5.2 系统函数详细介绍先来先服务调度算法有两种情况：一是进程的提交时间不一样，是根据到达的先后顺序来执行的，先到达先执行；二是进程的提交时间一样，即所有的进程的到达时间是一样的，要看进程的执行顺序，在前的进程先执行。非强占式短进程优先调度算法，有两种情况：一是进程的到达的时间不一样，那么首先执行第一个到达的进程，执行完后，然后比较剩下进程的到达时间和运行时间，先到达的和运行时间短的进程先运行；二是进程的到达时间一样，比较所有的进程的运行时间，运行时间短的进程先执行。5.3 系统功能模块介绍系统功能模块主要分为两大部分:先来先服务调度算法和非强占式短进程优先调度算法.5.4 具体模块设计5.4.1先来先服务调度算法(图1) 图5-1先来先服务调度5.4.2非强占式短进程优先调度算法图5-2非强占式短进程优先调度6.调试分析测试数据:到达时间不一样进程3（1.2 2.4 3.2）进程4（1.3 2.5 3.1 4.2）到达时间一样进程3（1.2 1.1 1.3）进程4（1.4 1.1 1.2 1.0.5）7.使用说明7.1到达时间不一样 7.1.1进程数为：3图7-17.1.2进程数为：4图7-27.2到达时间一样 7.2.1进程数为：3图7-37.2.2进程数为：4图7-48.设计总结这次课程设计给我一个很好的锻炼和实践的机会，让我对那些算法有了更深的了解。这次做的比较好的是直接把进程信息设定为一个结构体，如此以来对进程的操作比较方便，实现了基本信息的有效封装，充分利用链表来实现算法；还有就是基本上完成课程设计的要求，计算出平均周转时间和平均带权周转时间，比较了两种算法的优劣。不过，这次课设也有很多不足之处，比如说在提交时间一样的情况下，先来先服务是按照进程号的顺序执行，非强占式短进程优先调度算法先执行第一个进程，然后比较剩下进程的运行时间，运行时间最短的进程先进行。当提交时间一样时，对于短进程优先调度算法，应该是直接比较各个进程的运行时间，运行时间最短的进程先执行，这个不足之处需要改进。通过这次课程设计，提高了方面的水平。从这次课设，我不仅加深对操作系统知识的了解，而且更加提高自己的编程能力和实践水平。虽然这次课程设计结束了，然而对操作系统的学习不能间断，我要继续学习操作系统的知识，了解和掌握各种不同类型的操作系统；还要加强自己的编程能力，让自己的实践水平更上一层楼。但是，我觉得既然是操作系统课程设计应该涉及到多个操作系统，让我们了解更多不同的操作系统，通过不同的操作系统实践，掌握各个不同系统的特点和区别。9.参考文献【1】汤小丹、梁红兵、哲凤屏、汤子瀛 编著.计算机操作系统（第三版）.西安：西安电子科技大学出版社，2007.5【2】史美林编.计算机操作系统教程.北京：清华大学出版社，1999.11【3】徐甲同编著.操作系统教程.西安：西安电子科技大学出版社，1996.8【4】Clifford，A.Shaffer编著.数决结构与算法分析(C+版).北京：电子工业出版社，2005.7【5】蒋立翔编著.C+程序设计技能百练.北京：中国铁道出版社，2004.1 10程序源代码#include<iostream>using namespace std;struct prodouble handtime;double asktime;double starttime;double endtime;double usetime;double right;int runorder;int num;pro *next;/-void SJF(pro p,int n);void FCFS(pro p,int n);/-int pronum;int main()pro p20;cout<<"请输入进程的个数:"cin>>pronum;cout<<"按时间先后顺序输入进程的提交时间和运行时间"<<endl;for(int i=0;i<pronum;i+)pi.num=i+1; cout<<"第"<<i+1<<"个进程:" cin>>pi.handtime>>pi.asktime;while(pi.handtime<pi-1.handtime)cout<<"请从新输入第"<<i+1<<"个进程:" cin>>pi.handtime>>pi.asktime; FCFS(p,pronum); SJF(p,pronum); return 0; /cout<<p1->handtime <<p1->asktime<<endl;/-void SJF(pro p,int n)int i,order=1;pro *now=&p0;pro *temp,*nextrun;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=order;+order;for(i=0;i<n-1;i+)pi.next=&pi+1;/cout<<now->next->num<<endl;pn-1.next=NULL;/*while(now!=NULL)cout<<now->num<<"t"<<now->handtime<<endl;now=now->next;*/while(now->next!=NULL)nextrun=now->next;/cout<<nextrun->handtime<<"t"<<nextrun->asktime<<"asdfafdsa"<<endl;/while(nextrun!=NULL) /确定nextrun /if(nextrun->handtime>=now->endtime)nextrun->starttime=nextrun->handtime; elseif(nextrun->next!=NULL)temp=nextrun->next; while(temp->handtime<=now->endtime) /用来确定nextrun是否改变 if(temp->asktime<nextrun->asktime)nextrun=temp; if(temp->next!=NULL)temp=temp->next;else break; nextrun->starttime=now->endtime; /确定nextrun完毕 if(nextrun!=now->next)temp=now; /修改链表while(temp->next!=nextrun)temp=temp->next;temp->next=nextrun->next;temp=now->next; now->next=nextrun;nextrun->next=temp; /链表修改完毕 nextrun->endtime=nextrun->starttime+nextrun->asktime;nextrun->usetime=nextrun->endtime-nextrun->handtime;nextrun->right=nextrun->usetime/nextrun->asktime;nextrun->runorder=order;+order; /进程信息修改完毕 now=nextrun;double sumtime=0,sumright=0;cout<<"SJF"<<endl;cout<<"作业号t提交t运行t开始t结束t周转t带权t执行"<<endl;for(i=0;i<n;i+)sumtime+=pi.usetime;sumright+=pi.right;cout<<pi.num<<"t"<<pi.handtime<<"t"<<pi.asktime<<"t"<<pi.starttime<<"t"<<pi.endtime<<"t"<<pi.usetime<<"t"<<pi.right<<"t"<<pi.runorder<<endl;cout<<"平均ttttt"<<sumtime/n<<"t"<<sumright/n<<endl;/-void FCFS(pro p,int n)int i;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=1;for(i=1;i<n;i+)if(pi.handtime<pi-1.endtime) pi.starttime=pi-1.endtime;elsepi.starttime=pi.handtime;pi.endtime=pi.starttime+pi.asktime;pi.usetime=pi.endtime-pi.handtime;pi.right=pi.usetime/pi.asktime;pi.runorder=i+1;double sumtime=0,sumright=0;cout<<"FCFS"<<endl;cout<<"作业号t提交t运行t开始t结束t周转t带权t执行"<<endl;for(i=0;i<n;i+)sumtime+=pi.usetime;sumright+=pi.right;cout<<pi.num<<"t"<<pi.handtime<<"t"<<pi.asktime<<"t"<<pi.starttime<<"t"<<pi.endtime<<"t"<<pi.usetime<<"t"<<pi.right<<"t"<<pi.runorder<<endl;cout<<"平均ttttt"<<sumtime/n<<"t"<<sumright/n<<endl<<endl;