华北科技学院计算机系综合性实验
实 验 报 告
课程名称 操作系统
实验学期 至 学年 第 学期
学生所在系部
年级 专业班级
学生姓名 学号
任课教师 杜杏菁
实验成绩
计算机系制
《操作系统》课程综合性实验报告
开课实验室: 2011 年 05 月 17 日
武汉理工大学《计算机操作系统》课程设计
课 程 设 计
题 目 学 院
专 业
班 级
姓 名
指导教师
进程调度模拟设计——先来先服务、最高响应比优先调度算法 计算机科学与技术 计算机科学与技术 计算机009班 旭 汪 祥
莉
2012 年 1 月 9 日
武汉理工大学《计算机操作系统》课程设计
课程设计任务书
学生姓名: 旭 专业班级: 计算机009
指导教师: 汪祥莉 工作单位: 计算机科学与技术学院 题 目: 进程调度模拟设计——先来先服务、最高响应比优先调度算法
初始条件:
1.预备内容:阅读操作系统的处理机管理章节内容,对进程调度的功能以及进程
调度算法有深入的理解。
2.实践准备:掌握一种计算机高级语言的使用。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
1.模拟进程调度,能够处理以下的情形:
⑴ 能够选择不同的调度算法(要求中给出的调度算法);
⑵ 能够输入进程的基本信息,如进程名、到达时间和运行时间等;
⑶ 根据选择的调度算法显示进程调度队列;
⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。
2.设计报告内容应说明:
⑴ 课程设计目的与功能;
⑵ 需求分析,数据结构或模块说明(功能与框图);
⑶ 源程序的主要部分;
⑷ 测试用例,运行结果与运行情况分析;
⑸ 自我评价与总结:
i)你认为你完成的设计哪些地方做得比较好或比较出色;
ii)什么地方做得不太好,以后如何改正;
iii)从本设计得到的收获(在编写,调试,执行过程中的经验和教训);
iv)完成本题是否有其他方法(如果有,简要说明该方法);
v)对实验题的评价和改进意见,请你推荐设计题目。
时间安排:
设计安排一周:周1、周2:完成程序分析及设计。
周2、周3:完成程序调试及测试。
周4、周5:验收、撰写课程设计报告。
(注意事项:严禁抄袭,一旦发现,抄与被抄的一律按0分记)
指导教师签名: 年 月 日
系主任(或责任教师)签名: 年 月 日
武汉理工大学《计算机操作系统》课程设计
目录
1 设计题目 ................................ 1
2 需求分析 ................................ 1
2.1 功能需求 .................................... 1
2.1.1进程调度模拟设计先来先服务法.................. 1
2.1.2进程调度模拟设计最高响应比优先调度算法......... 2
2.2 环境需求 .................................... 3
2.3 用户界面需求 ................................ 3
3 功能设计 ................................ 3
3.1数据结构 ..................................... 3
3.2模块说明 ..................................... 4
4 开发平台及源程序的主要部分 ...............5
4.1 开发平台 ..................................... 5
4.2 源程序主要部分 ................................5
5 测试用例,运行结果与运行情况分析 .........6
5.1 测试用例 .................................... 6
5.2 运行结果 .....................................6
6 自我评价与总结 ..........................7
7 附加代码.................................8
武汉理工大学《计算机操作系统》课程设计
1. 设计题目
1. 先来先服务、最高响应比优先调度算法需求分析 模拟进程调度,能够处理以下的情形:
⑴ 能够选择不同的调度算法(要求中给出的调度算法); ⑵ 能够输入进程的基本信息,如进程名、到达时间和运行时间等;
⑶ 根据选择的调度算法显示进程调度队列;
⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。
2.1 功能需求
2.1.1 实现先来先服务法:
先来先服务算法基本思想:按照作业提交或进
程变为就绪状态的先后次序,调入系统或分派
CPU ,换句话说,调度程序每次选择的作业/
进程是等待时间最久的,而不管其运行时间的
长短。这种调度算法突出的优点是实现简单,
效率较低,在一些实 际的系统和一般应用程
序中采用这种算法的较多。因此,在设计中,
首先对输入的各进程的提交时间进行比较,对
- 1 -
武汉理工大学《计算机操作系统》课程设计
先进入等待队列的进程提供服务。
2.1.2 实现最高响应比优先调度算法:
最高响应比优先法(HRN)是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。
响应比R定义如下:
R=(W+T)/T=1+W/T
其中T为该作业估计需要的执行时间,W为作业在后备状态队列中的等待时间。
每当要进行作业调度时,系统计算每个作业的响应比,选择其中R最大者投入执行。这样,即使是长作业,随着它等待时间的增加,W/T也就随着增加,也就有机会获得调度执行。这种算法是介于FCFS和SJF 之间的一种折中算法。由于长作业也有机会投入运行,在同一时间内处理的作业数显然要少于SJF 法,从而采用HRN 方式时其吞吐量将小于采用SJF 法时的吞吐量。另外,
- 2 -
武汉理工大学《计算机操作系统》课程设计
由于每次调度前要计算响应比,系统开销也要相应增加。
2.2 环境需求
开发环境、运行环境及开发语言:
开发环境:Windows平台+Visual C++ 6.0 运行环境:Windows全系列平台
开发语言:C++
2.3 用户界面需求
输入输出均采用命令行界面。
格式如下:
首先 输入进程数。
其次 输入进程编号,姓名,到达时间,执行时间等 相关信息。
然后 选择算法,优先法或者是最高响应比算法。 最后,输出程序运行所得结果。
3 功能设计:
3.1 数据结构:
创建一个进程信息结构:
struct PCB
{
string name;//进程名
float ta;//进程到达时间
float ts;//进程估计运行的时间
float tb;//进程开始运行时间
float tm;//进程仍需运行的时间
float to;//进程完成的时间
float rn;//进程运行的次数
- 3 -
武汉理工大学《计算机操作系统》课程设计
float totalTime;//周转时间
double weightTotalTime;//带权周转时间(周转时间/估计运行时间)
PCB *next;//定义指向下一个进程的指针
};
此外,对输入信息进行创建链表队列:
PCB *create(PCB *head)
{
PCB *p1,*p2;
p1=p2=new PCB;
head=p1;
cout<<"请输入进程数:";
cin>>pronum;
for(int i=0;i<pronum;i++)
{
p2=p1;
p1=new PCB;
p1->next=NULL;
cout<<"请依次输入第"<<i+1<<"个进程的信息(进程名、到达时间、估计运行时间):";
cin>>p1->name>>p1->ta>>p1->ts;
p1->tm=p1->ts;
p1->rn=1;
p2->next=p1;
}
return head;
}
3.2 模块说明
首先选择调度算法,若选1先来先服务然则调用create()
- 4 -
武汉理工大学《计算机操作系统》课程设计
创建进程队列,然后调用fcfsrun()进行先来先服务算法,后Goto到起始点。若选择2最高响应比算法则调用create()创建进程队列,然后调用Hrn()进行最高响应比算法,后Goto到起始点。若选择3则退出,选择其他则报错。
4 开发平台及源程序的主要部分:
4.1 开发平台:
开发环境、运行环境及开发语言:
开发环境:Windows平台+Visual C++ 6.0
4.2 源程序主要部分:
struct PCB{};//进程结构
#define MAX_NUM 15
int pronum;//定义进程数为pronum
float total;//记录所有进程的总时间
double weight;//记录所有进程的带权周转时间
PCB *create(PCB *head);//创建进程队列
void deal(PCB *head);//FCFS记录处理
void sort(PCB *head);//将进程按到达的先后顺序排列 void fcfsrun(PCB *head);//先来先服务算法
void Hrn(PCB *head,int n);//最高响应比算法
void main(){}//主函数
- 5 -
武汉理工大学《计算机操作系统》课程设计
流程图如下:
5 测试用例,运行结果与运行情况分析:
5.1 测试用例:
正确的测试用例:
先来先服务算法结果:
- 6 -
武汉理工大学《计算机操作系统》课程设计
最高响应比结果:
其他:
六 自我评价与总结:
这次课程设计是让我们用已经学过的操作系统知识对先来先服务算法和最高响应比算法进行设计,使我在对进程调度的先来先服务和最高响应比优先算法充分理解的同时,也使我的实践编程能力和运用理论知识的能力得到进一步提高。
在此次实验中,我认为我比较出色的是自己一开始就有了一个整体的思路,不像以前的课程设计一样,对全局的规划不是很清楚,以至于在后来模块的衔接做得不到位,但是此次的设计由于初始就对各个功能块的相互调用也比较了解,所以对该课设的设计整体上比较轻松,也使程序的编写比较清晰。
- 7 -
武汉理工大学《计算机操作系统》课程设计
不过,在此次课设中我也出现了不少问题,尤其是在对先来先服务和最高响应比优先功能块的设计时,对其中每个进程之间的时间比较和响应比比较的具体代码还比较模糊,因此使得设计一度陷入了修改和编写中;此外,刚开始对程序的容错能力并未加入考虑的范围,所以使得程序的完整性和健壮性比较欠缺。所以,从中看出自己在具体细致的地方还约显不足,还有待提高。
通过此次课程设计,也使我见到对同一实验目的可以使用多种方法,C++的编程比较符合我们现在的编程设计能力,但是使用JAVA也可以完成相同功能,而且会使得某些步骤还比较简易。此外,使程序具有较强的容错能力也对程序设计的优劣性起到较为重要的因素。相信通过这次的设计,对我以后的学习和编程能力有一定的帮助。
七、附加代码
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
struct PCB
{
string name;//进程名 float ta;//进程到达时间 float ts;//进程估计运行的时间 float tb;//进程开始运行时间 float tm;//进程仍需运行的时间 float to;//进程完成的时间 float rn;//进程运行的次数 float totalTime;//周转时间
- 8 -
武汉理工大学《计算机操作系统》课程设计
};
double weightTotalTime;//带权周转时间(周转时间/估计运行时PCB *next;//定义指向下一个进程的指针
间)
#define MAX_NUM 15
int pronum;//定义进程数为pronum float total;//记录所有进程的总时间
double weight;//记录所有进程的带权周转时间
PCB *create(PCB *head);//创建进程队列 void deal(PCB *head);//FCFS记录处理
void sort(PCB *head);//将进程按到达的先后顺序排列 void fcfsrun(PCB *head);//先来先服务算法 void Hrn(PCB *head,int n); void main() {
cout<<"*进程调度模拟设计——先来先服务、最高响应比优先算cout<<"***********1.cout<<"***********2.cout<<"***********3
先最
高来响
先应
服比退
务优
先算算
法法出
法*"<<endl;
***************************"<<endl; *********************"<<endl;
*************************************"<<endl; l1: cout<<"请输入您的选择:"<<endl; l2: cin>>choice;
PCB *head=NULL;
- 9 -
int choice;
武汉理工大学《计算机操作系统》课程设计
}
switch(choice) { case 1:head=create(head);fcfsrun(head);goto l1; case 2:head=create(head);Hrn(head,pronum);goto l1; case 3:break; default:cout<<"输入错误!\n请重新输入:"<<endl;goto l2; }
PCB *create(PCB *head) {
PCB *p1,*p2; p1=p2=new PCB; head=p1; cout<<"请输入进程数:"; cin>>pronum; for(int i=0;i<pronum;i++) { } return head;
- 10 - p2=p1; p1=new PCB; p1->next=NULL; cout<<"请依次输入第"<<i+1<<"个进程的信息(进程名、到达时cin>>p1->name>>p1->ta>>p1->ts; p1->tm=p1->ts; p1->rn=1; 间、估计运行时间):"; p2->next=p1;
武汉理工大学《计算机操作系统》课程设计
}
void sort(PCB *head)//将进程按到达的先后顺序排列 {
}
void deal(PCB *head)//FCFS记录处理
{
sort(head);
- 11 - PCB *p,*q,*r,*s; if(head->next!=NULL) { } while(p) { } q=p; p=p->next; r=head; s=head->next; while(s&&s->ta<=q->ta) { } r->next=q; q->next=s; r=s; s=s->next; p=head->next->next; head->next->next=NULL;
武汉理工大学《计算机操作系统》课程设计
}
PCB *p,*q; q=head->next; q->tb=q->ta; q->to=q->tb+q->ts; q->totalTime=q->to-q->ta; total+=q->totalTime; q->weightTotalTime=q->totalTime/(double)q->ts; weight+=q->weightTotalTime; p=q->next; { p->tb=q->to; p->to=p->tb+p->ts; p->totalTime=p->to-p->ta; total+=p->totalTime; while(p!=NULL) p->weightTotalTime=p->totalTime/(double)p->ts; weight+=p->weightTotalTime; q=p; p=p->next; }
void fcfsrun(PCB *head)//先来先服务算法 {
- 12 -
武汉理工大学《计算机操作系统》课程设计
deal(head); PCB *p,*q,*s; p=head->next; cout<<"进程执行顺序为:"; while(p!=NULL) { } cout<<endl; cout<<"进程名 提交时间 开始时间 结束时间 周转时间 带cout<<"--"<<p->name; p=p->next; 权周转时间\n";
s=head->next;
cout<<setw(4)<<s->name<<setw(7)<<s->ta<<setw(10)<<s->tb<<setw(11)<<s->to<<setw(10)<<s->totalTime<<setw(10)<<s->weightTotalTime<<endl;
}
- 13 - while(s!=NULL) { } s=s->next; cout<<endl; cout<<"平均带权周转时间:"<<weight/(double)pronum<<endl; cout<<"******************************************************"<<endl; total=0; weight=0; cout<<" 平均周转时间:"<<total/(double)pronum<<endl;
武汉理工大学《计算机操作系统》课程设计
//最高响应比算法函数
void Hrn(PCB *head,int n) {
PCB *p,*p1; PCB *flag=NULL; PCB *q=NULL; int xuhao=0; string pname[MAX_NUM]; for(int ss=0;ss<MAX_NUM;ss++) pname[ss]=""; sort(head); cout<<endl; cout<<" 顺序 进程名 提交时间 开始时间 结束时间 周转head=head->next; p=head; while(head) { q=head; if(time < p->ta) //如果该进程提交时间早于其它进程,则先执 time=p->ta; double time=0,j=0,runTime=0, drunTime=0; 时间 带权周转时间\n"; 行该进程 flag=head; //用于暂存将要执行的进程 //计算当前链表中进程的响应比 while(q && q->ta <= time) { if((time - q->ta)/(q->ts) > (time - flag->ta)/(flag->ts)) flag=q;
- 14 -
武汉理工大学《计算机操作系统》课程设计
} q=q->next; if(time < flag->ta)//如果上一次结束时间比当前选中要执行进程的结束时间小
time=flag->ta; //则当前进程开始时间为提交时间
//输出当前执行进程的信息
cout<<setw(4)<<xuhao+1;
cout<<setw(8)<<flag->name;
cout<<setw(8)<<flag->ts;
cout<<setw(8)<<time;
cout<<setw(10)<<(time + flag->ts);
cout<<setw(10)<<(time - flag->ta + flag->ts);
cout<<" "<<setw(11)<<(double)((time-flag->ta flag->ts)/flag->ts)<<endl;
j=(time-flag->ta+flag->ts); //当前执行进程的周转时间 runTime +=j; //记录周转时间
time+=flag->ts;
drunTime+=j/flag->ts; //带权周转时间 pname[xuhao]=flag->name;
xuhao++;
//将执行过的进程从链表中删除
if(flag==head) //在链表头
head=head->next;
else
{ //在链表中
p1=head;
while(p1->next!=flag)
p1=p1->next;
- 15 - +
武汉理工大学《计算机操作系统》课程设计
}
} } p1->next=flag->next; delete flag; //删除这个进程所占的节点 cout<<"进程执行顺序为:"; for(ss=0;ss<n;ss++) { } cout<<endl; cout<<" 平均周转时间为:"<<runTime/n<<endl; cout<<"******************************************************"<<endl; cout<<pname[ss]; if(pname[ss+1] !="") cout<<" -> "; cout<<"平均带权周转时间为:"<<drunTime/n<<endl;
本科生课程设计成绩评定表
班级: 计算机009 姓名: 旭 学号:012091034001
- 16 -
武汉理工大学《计算机操作系统》课程设计
及格(60-69分)、60分以下为不及格
指导教师签名:
201 年 月 日
- 17 -
操作系统实验报告二实验题目进程调度算法实验环境C实验目的编程模拟实现几种常见的进程调度算法通过对几组进程分别使用不同的调度算法计算…
进程调度算法模拟专业XXXXX学号XXXXX姓名XXX实验日期20XX年XX月XX日一实验目的通过对进程调度算法的模拟加深对进程概…
操作系统教程进程调度算法院系计算机与软件学院班级08软件工程2班学号***姓名**进程调度算法的模拟实现●实验目的1.本实验模拟在…
操作系统实验报告实验一进程调度算法学生学号学院系别专业实验时间报告时间一实验内容按优先数调度算法实现处理器调度二实验目的在采用多道…
实验一进程调度一实验题目1编写并调试一个模拟的进程调度程序采用最高优先数优先调度算法对五个进程进行调度2编写并调试一个模拟的进程调…
20xx年上半年交通管理所工作总结及下半年工作计划20xx年上半年,我公路管理所在局党委、局领导的正确领导和大力支持下,坚持以邓小…
辞旧迎新,转眼又是新的一年,而我们在新的一年里已开展了一个月的工作了。这一个月可以说现将我本月的工作总结如下:1、人员管理。员工方…
经信局、泗河办片区改造开发项目搬迁推进组20xx年工作总结自4月x日经信局、泗河办片区搬迁推进组成立以来,积极作为,超常运作,一天…
暑期教师进企业实践总结20xx年暑假,我参加了学校组织的教师进企业实践培训,通过理论与实践相结合的学习方式,使我丰富了理论知识,增…
大学生艺术团工作总结光阴荏苒,岁月如梭,转眼间,20xx—20xx学年已结束,在这一学期里我们大学生艺术团又走过了一段新的发展历程…