2022年操作系统课程设计进程调度模拟设计--先来先服务,优先.doc

学 号： 课 程 设 计课程名字系统软件开发实训A题 目进程调度模仿设计先来先效劳、优先级法学 院计算机科学与技术学院专 业计算机科学与技术专业班 级姓 名指导老师李玉强2014年01月13日课程设计任务书学生姓名： 专业班级： 指导老师： 李玉强 工作单位： 计算机科学与技术学院 题 目: 进程调度模仿设计先来先效劳、优先级法 初始条件：1预备内容：阅读操作系统的处理机治理章节内容，对进程调度的功能以及进程调度算法有深化的理解。2实践预备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等详细要求）1模仿进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的根本信息，如进程名、优先级、到达时间和运转时间等； 依照选择的调度算法显示进程调度队列； 依照选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据构造或模块说明(功能与框图)； 源程序的主要部分； 测试用例，运转结果与运转情况分析； 自我评价与总结。时间安排：设计安排3周：查阅、分析材料 1天系统软件的分析与建模 4天系统软件的设计 5天系统软件的实现 3天撰写文档 1天课程设计验收辩论 1天设计验收安排：设计周的第三周的指定时间到实验室进展上机验收。设计报告书收取时间：课程设计验收辩论结束时。（考前须知：严禁抄袭，一旦发觉，抄与被抄的一律按0分记）指导老师签名： 2013 年 12 月 10日系主任（或责任老师）签名： 2013 年 12 月 10日课程设计报告书1.需求分析 1.1设计目的(1)阅读操作系统的处理机治理章节内容，对进程调度的功能以及进程调度算法有深化的理解。(2)掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等详细要求） 1.2程序流程图开 始选择调度算法先来先效劳法输入进程队列信息优先级法完毕？Y/N结 束YN切 换 算 法1.3设计要求(1)能够选择不同的调度算法（要求中给出的调度算法）；(2)能够输入进程的根本信息，如进程名、优先级、到达时间和运转时间等；(3)依照选择的调度算法显示进程调度队列；(4)依照选择的调度算法计算平均周转时间和平均带权周转时间。2.功能设计 2.1数据构造1. 进程的构造定义：struct processchar name10; /进程名int no; /进程序号double arrivetime; /进程到达时间double needtime; /进程运转时间 double starttime; /进程开场时间double endtime; /进程完毕时间int state; /进程状态，0表示未执行，1表示已执行int priority; /进程优先级process *next; process *head=Null;int count; ；2.使用链表存储进程并按照到达时间排序、开场链表空？只有一节点比拟当前节点的到达时间与连续两个节点（p1,p1->next）的到达时间至少两个节点结 束YN插 到 链 头比拟当前节点与已存在节点的到达时间在两节点之间？插入它们之间插 入p1=p1->nextvoid insert(process *current) if (head!=Null)if(head->next=Null) /假如只有一个节点if(current->arrivetime<head->arrivetime) /假如比链头到达时间早，则插入链头current->next=head;head=current;elsecurrent->next=Null;head->next=current; else /假如至少两个节点 process *p1=head; if(head->arrivetime >current->arrivetime ) current->next=head; head=current; else int flag=1; while(p1->next!=Null) /当head后面不为空时不断做 /假如在两个节点间 if(p1->arrivetime < current->arrivetime p1->next->arrivetime > current->arrivetime) current->next=p1->next; p1->next=current; flag=0; break; else p1=p1->next; /假如到达时间最大，则插到链尾 if (flag=1) p1->next=current; current->next=Null; else head=current;2.2先来先效劳算法设计 1.FCFS算法说明将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先效劳的方式进展调度处理，是一种最普遍和最简单的方法。在该算法中，每个作业或进程按照它们在队列中等待时间长短来决定它们是否优先享受效劳。在没有特别理由要优先调度某类作业或进程时，从处理的角度来看，FCFS方式是一种最适宜的方法，由于不管是追加依然取出一个队列元素在操作上都是最简单的。2.创立进程void createFCFS() process *q1=new process ; cout<<"请输入进程总数目" cin>>count; cout<<endl; int number=1; while(number<=count) q1=new process; q1->no=number; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"进程到达时间" cin>>q1->arrivetime; cout<<"进程运转时间" cin>>q1->needtime; q1->next=NULL; insert(q1); number+; cout<<endl<<endl; 3.进程调度及输出结果开 始链表空？Head节点：开场时间=到达时间 完毕时间=开场时间+执行时间 系统时间=完毕时间并计算周转时间和带权周转时间P=head->nextP=null结 束YN前一个完毕，后一个进程是否到达p节点：开场时间=到达时间 完毕时间=开场时间+执行时间 系统时间=完毕时间并计算周转时间和带权周转时间P=head->nextNp节点：开场时间=系统时间 完毕时间=开场时间+执行时间 系统时间=完毕时间并计算周转时间和带权周转时间P=head->nextYvoid printFCFS() process *p=new process; double systime=0; /记录系统时间 double turn=0; /平均周转时间 double turnw=0; /平均带权周转时间 if(head=NULL) cout<<"没有进程调度"<<endl; /处理第一个 else if(head!=NULL) head->starttime=head->arriveTime; head->endtime=head->arrivetime+head->needtime; systime=head->endtime; turn=turn+(head->endtime - head->arrivetime); turnw=turnw+(head->endtime - head->arrivetime) / head->needtime; p=head->next; while(p!=NULL) if(p->arrivetime>systime) /假如前一个完毕后一个还没到达 p->starttime=p->arrivetime; p->endtime=p->starttime+p->needtime; systime=p->endTime; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; else /假如前一个未完毕时后一个已经到达 p->starttime=systime; p->endtime=p->starttime+p->needtime; systime=p->endtime; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; cout.setf(ios:left); /设置对齐方式为left cout<<setw(10)<<"进程序号"<<setw(10)<<"进程名"<<setw(10)<<"到达时间"<<setw(10)<<"开场时间"<<setw(10)<<"执行时间"<<setw(10)<<"完毕时间"<<endl; process *temp=head; while(temp!=NULL) cout.setf(ios:left); cout<<setw(10)<<temp->no<<setw(10)<<temp->name<<setw(10)<<temp->arriveTime<<setw(10)<<temp->startTime<<setw(10)<<temp->needTime<<setw(10)<<temp->endTime<<endl; temp=temp->next; cout<<"平均周转时间"<<turn/count<<endl<<"平均带权周转时间"<<turnw/count<<endl; /清空链表 while(head->next!=NULL) /回收空间 process *t=new process; t=head->next; head->next=t->next; delete t; head=NULL; 2.3 优先级算法的设计1.PIRO算法及说明 优先级法可被用作作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。该算法的核心是确定进程或作业的优先级。 确定优先级的方法可分为两类。即动态法和静态法静态法依照作业或进程的静态特性，在作业或进程开场执行之前就确定它们的优先级，一旦开场执行之后就不能改变。动态法则不然，它把作业或进程的静态特性和动态特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。 静态优先级中，能够由用户本人依照作业的紧急程度输入一个适当的优先级，为防止各用户都将本人的作业冠以高优先级，系统应对高优先级用户收取较高的费用；也能够由系统或操作员依照作业类型指定优先级。动态优先级中，基于静态优先级的调度算法实现简单，系统开销小，但由于静态优先级一旦确定之后，直到执行完毕为止一直保持不变，从而系统效率较低，调度功能不高。如今的操作系统中，假如使用优先级调度的话，则大多采纳动态优先级的调度策略。2.创立进程void createPRIO() process *q1=new process; cout<<"请输入进程总数目" cin>>count; cout<<endl; int number=1; while(number<=count) q1=new process; q1->no=number; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"优先级" cin>>q1->priority; cout<<"进程到达时间" cin>>q1->arriveTime; cout<<"进程运转时间" cin>>q1->needTime; q1->next=NULL; insert(q1); number+; cout<<endl<<endl; 3.把最先到达的进程的排在链头，后面的进程按优先级大小重新排序void changePRIO(double systime) /把最先到达的放到链头 然后后面的结点按照优先级来排序 /排序的前提是结点数至少是3个 从第二个开场和后面的比拟 if(count>2) process *n0=head; process *n1=n0->next; process *n2=n1->next; for(int i=0;i<count-1;i+) while(n1!=NULL n2!=NULL n1->arrivetime <= systime n2->arrivetime <= systime) /假如前面的优先级大于后面的优先级，则交换 if(n1->priority < n2->priority) n1->next=n2->next; n0->next=n2; n2->next=n1; n1=n0->next; n2=n0->next->next; n0=n1; n1=n2; n2=n2->next; 4.输出调度结果开 始链表空？Head节点：开场时间=到达时间 完毕时间=开场时间+执行时间 系统时间=完毕时间并计算周转时间和带权周转时间P=head->nextP=null结 束N到达未执行p节点：开场时间=系统时间 完毕时间=开场时间+执行时间 系统时间=完毕时间标记为已执行并计算周转时间和带权周转时间P=head->nextYvoid printPRIO() process *p=new process; double sysTime=0; /记录系统时间 double turn=0; /平均周转时间 double turnw=0; /平均带权周转时间 if(head=NULL) cout<<"没有进程调度！"<<endl; else /先把最先到达的输出，然后再依照系统时间和优先级推断后续的进程 head->starttime=head->arrivetime; head->endtime=head->arrivetime+head->needtime; head->state=1; systime=head->endtime; turn=turn+(head->endtime - head->arrivetime); turnw=turnw+(head->endtime - head->arrivetime) / head->needtime; /推断后面的 for(int i=0;i<count-1;i+) p=head->next; while(p!=NULL) changePRIO(double systime); /假如优先级最大的进程已经到达，则执行 if(p->arrivetime <= systime p->state=0) p->starttime=systime; p->endtime=p->arrivetime+p->needtime; systime=p->endtime; p->state=1; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; else p=p->next; process *temp=head; cout.setf(ios:left); cout<<setw(10)<<"进程序号"<<setw(10)<<"进程名"<<setw(10)<<"优先级"<<setw(10)<<"到达时间"<<setw(10)<<"开场时间"<<setw(10)<<"执行时间"<<setw(10)<<"完毕时间"<<endl; while(temp!=NULL) cout<<setw(10)<<temp->no<<setw(10)<<temp->name<<setw(10)<<temp->priority<<setw(10)<<temp->arriveTime<<setw(10)<<temp->startTime<<setw(10)<<temp->needTime<<setw(10)<<temp->endTime<<endl; temp=temp->next; cout<<"平均周转时间："<<turn/count<<endl<<"平均带权周转时间："<<turnw/count<<endl; while(head->next!=NULL) process *t=new process; t=head->next; head->next=t->next; delete t; head=NULL; 3. 源程序的主要部分 主程序主要完成调用各个函数完成相应的功能，以及选择调度算法的输出提示，依照提示并完成相应的算法实现过程。/程序主要部分int main()int choice; /选择效劳int go=1;while (go)cout<<endl<<endl<<"-"<<"进程调度模仿设计"<<"-"<<endl<<endl; cout<<"1.先来先效劳算法"<<endl<<"2.优先级法"<<endl<<"3.退出"<<endl<<endl;cout<<"请选择："cin>>choice；switch(choice) case 1:FCFS();break; /调用先来先效劳算法 case 2:PRIO();break; /调用优先计算法 case 3:cout<<"退出"<<endl; go=0;break; /退出，返回首页 default:cout<<"选择有误，请重新输入选择！"<<endl;break;system("pause");return 0;void FCFS() createFCFS(); printFCFS(); void PRIO() createPRIO(); /changePRIO(); printPRIO(); 4.程序测试4.1先来先效劳测试用例进程序号进程名称到达时间执行时间1a042b133c224d334.2先来先效劳运转结果进程序号进程名称优先级到达时间执行时间1a1042b4163c2244d3354.3先来先效劳测试用例4.4优先级算法运转结果5.自我评价与总结本次课程设计的内容根本上是老师在课堂上所讲的，因此我依然比拟熟悉先来先效劳算法和优先级算法。看到这个标题时，我依然感受相当轻松的，由于我依然比拟熟悉该内容，比拟熟悉算法思想。设计过程中要留意流程的条理明晰，易于读明白和规划，程序编写完成以后，实现了预期的效果，到达了设计的要求。界面设计比拟明晰明了，易于阅读和理解。本程序中，有些地点有重复，能够通过设计函数来简化程序，例如程序的创立，能够通过函数调用来实现，从而不必在两个算法中分别编写。编写程序时要先画出程序的流程图是特别有必要的，依照流程图的顺序来实现程序，并要留意合理的使用函数调用来使程序得到简化，同时易读易明白。编写程序的时候一定要先画流程图，对应流程图设计函数来简化程序。这次课程设计中比拟失败的地点确实是优先级算法的输出开场时间和完毕时间出了点咨询题。 这次课程设计使得我收获颇丰，尤其是对优先级调度分析方法有了更深的理解和掌握。通过这次课程设计，我的编程才能又得到了进一步的提高，同时也培养了我的思维才能。总的说来，这次课程设计不仅丰富了我的理论知识，也加强了我的动手才能，还锻炼了我的思维才能。在实验程序编写和调试过程中我学会了特别多，也认识到了本人的缺乏，我还需要进一步的努力，以致获得更大的进步。我需要的确实是要对本人有决心，脚踏实地，持之以恒，遇到困难时要平复考虑，英勇面对，直到得出结果。在实验设计过程中，我也养成了较好地适应，先有框架，然后跟着框架开展，最后确实是要注重细节，要做到严谨和缜密。不可否认这种好适应让我受益无限，我也必须拥有它，以致我获得更多。6.源程序#include<iostream.h>#include<stdlb.h>#include<iomanip.h>struct processchar name10; /进程名int no; /进程序号double arrivetime; /进程到达时间double needtime; /进程运转时间 double starttime; /进程开场时间double endtime; /进程完毕时间int state; /进程状态int priority; /进程优先级process *next; process *head=Null;int count; ；void FCFS();void PRIO();void createFCFS();void insert(process *current); void printFCFS();void createPRIO();void changePRIO(double systime); void printPRIO() ;/程序主要部分int main()int choice; /选择效劳int go=1;while (go)cout<<endl<<endl<<"-"<<"进程调度模仿设计"<<"-"<<endl<<endl; cout<<"1.先来先效劳算法"<<endl<<"2.优先级法"<<endl<<"3.退出"<<endl<<endl;cout<<"请选择："cin>>choice；switch(choice) case 1:FCFS();break; /调用先来先效劳算法 case 2:PRIO();break; /调用优先计算法 case 3:cout<<"退出"<<endl; go=0;break; /退出，返回首页 default:cout<<"选择有误，请重新输入选择！"<<endl;break;system("pause");return 0;void FCFS() createFCFS(); printFCFS(); void PRIO() createPRIO(); /changePRIO(); printPRIO(); /使用链表构造 按到达时间的顺序将进程进展排序void insert(process *current) if (head!=Null)if(head->next=Null) /假如只有一个节点if(current->arrivetime<head->arrivetime) /假如比链头到达时间早，则插入链头current->next=head;head=current;elsecurrent->next=Null;head->next=current; else /假如至少两个节点 process *p1=head; if(head->arrivetime >current->arrivetime ) current->next=head; head=current; else int flag=1; while(p1->next!=Null) /当head后面不为空时不断做 /假如在两个节点间 if(p1->arrivetime < current->arrivetime p1->next->arrivetime > current->arrivetime) current->next=p1->next; p1->next=current; flag=0; break; else p1=p1->next; /假如到达时间最大，则插到链尾 if (flag=1) p1->next=current; current->next=Null; else head=current;void createFCFS() process *q1=new process ; cout<<"请输入进程总数目" cin>>count; cout<<endl; int number=1; while(number<=count) q1=new process; q1->no=number; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"进程到达时间" cin>>q1->arrivetime; cout<<"进程运转时间" cin>>q1->needtime; q1->next=NULL; insert(q1); number+; cout<<endl<<endl; void printFCFS() process *p=new process; double systime=0; /记录系统时间 double turn=0; /平均周转时间 double turnw=0; /平均带权周转时间 if(head=NULL) cout<<"没有进程调度"<<endl; /处理第一个 else i