进程调度模拟设计——先来先服务、最高响应比优先调度算法.doc
学 号: 0120810340621
进程调度模拟设计—先来先服题 目
务、最高响应比优先调度算法 学 院 计算机科学与技术学院 专 业 计算机科学与技术专业 班 级 计算机科学与技术0902班 姓 名 庞竞强
指导教师 郭羽成
2011 年 01 月 12 日
课程设计任务书
学生姓名: 庞竞强 专业班级: 计算机0902班
指导教师: 郭羽成 工作单位: 计算机科学与技术学院
题 目: 进程调度模拟设计——先来先服务、最高响应比优先调度算法
初始条件:
1(预备内容:阅读操作系统的处理机管理章节内容,对进程调度的功能以及进程调度算法有深入的理解。
2(实践准备:掌握一种计算机高级语言的使用。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体
要求)
1(模拟进程调度,能够处理以下的情形:
? 能够选择不同的调度算法(要求中给出的调度算法);
? 能够输入进程的基本信息,如进程名、到达时间和运行时间等;
? 根据选择的调度算法显示进程调度队列;
? 根据选择的调度算法计算平均周转时间和平均带权周转时间。
2(设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
内容应说明:
? 课程设计目的与功能;
? 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
,数据结构或模块说明(功能与框图);
? 源程序的主要部分;
? 测试用例,运行结果与运行情况分析;
? 自我评价与总结:
i)你认为你完成的设计哪些地方做得比较好或比较出色;
ii)什么地方做得不太好,以后如何改正;
iii)从本设计得到的收获(在编写,调试,执行过程中的经验和教训);
iv)完成本题是否有其他方法(如果有,简要说明该方法);
v)对实验题的评价和改进意见,请你推荐设计题目。
时间安排:
设计安排一周:周1、周2:完成程序分析及设计。
周2、周3:完成程序调试及测试。
周4、周5:验收、撰写课程设计报告。
(注意事项:严禁抄袭,一旦发现,抄与被抄的一律按0分记)
指导教师签名: 年 月 日 系主任(或责任教师)签名: 年 月 日
2
进程调度模拟设计
——先来先服务、最高响应比优先调度算法
一、概述
1、设计目的
(1)加深对进程的概念地理解。
(2)掌握先来先服务算法、最高相应比优先算法。
(3)了解进程控制块的作用,以及进程控制块的内容和组织方式。
2、开发环境
实验平台:个人计算机机
操作系统:Windows XP
编译环境:microsoft visual c++ 6.0
二、需求分析
1、进程调度:
进程调度是处理机管理的核心内容。本实验要求编写和调试一个简单的进程调度程序。通
过本实验可以加深理解有关进程控制块、进程队列的概念,并体会和了解优先数和时间片轮转
调度算法的具体实施办法。
在系统中将用户提交的多个进程都先存放在外存上,并排成一个队列,按照一定的算法调
度,从队列中选择若干个进程调入内存,并允许它们根据某种算法交替执行,共享系统中的各
种硬软件资源。
操作系统根据一定的算法从系统中选取若干进程把它们装入内存,使它们有机会获得处理
3
器运行这项进程被称为“进程调度”。实现这部分的功能程序就是“进程调度程序”。 3、进程调度的实现:
A(利用进程控制块将系统中的进程组织起来;
进程是根据进程控制块(JCB)组织起来的,进程控制块为每个进入系统的进程建立档
案以记录和进程相关的信息,例如进程名、进程所需要的资源、进程执行的时间、进程进入
系统的时间、进程信息在存储器中的位置、指向下一个进程控制块的指针等信息。,并将系统
中等待进程调度的进程控制块组织成一个队列,这个队列称为后备队列。当一个进程全部信
息进入系统后,就为其建立进程控制块,并挂入后备队列中。当一个进程全部进入系统后,
就为其建立进程控制块,并挂入后备队列中。当进行进程调度时,从后备队列中查找选择进
程。
B(利用优先级法进行进程调度;
在从后备队列中查找选择进程时,先根据进程控制块中的信息,选中一个优先级最高的进程,将
它们调入内存运行。
C(利用短进程优先算法进行进程调度;
在从后备队列中查找选择进程时,先根据进程控制块中的信息,选中一个短进程,也就
是执行时间最短的进程,将它们调入内存运行。
4、进程控制块:
A(进程控制块的内容:
?进程名 (name);
?进程的提交时间(ReachTime);
?进程估计执行时间(Runtime);
?指向下一个进程控制块的指针(next);
B(进程控制块的组织方式:
采用静态链接方式把进程控制块组织成一个后备队列。通过用进程控制块的指针
4
next指向下一个进程控制块来链接各进程控制块。当在队列中插入一个新的进程控制块
时,先修改没插入该新进程控制块之前队尾进程控制块的指向下一个进程控制块的指针,
再将该新的进程控制块放在队尾。
三、数据结构设计
1(进程控制块类型的定义:
typedef struct process
{
char name; //进程名
int ReachTime; //到达时间
int RunTime; //运行时间;
struct process *next;
};
2(先来先服务算法:
void ProcessManager::FCFS() //先来先服务算法 {
Process *Start=Queue;
Process *before,*second,*selected,*del;
before=selected=first;
second=del=first->next;
float T=0.0;
do
{
T=second->ReachTime;
do
{
if(second->next==NULL)
{
5
del=second;
before=selected;
break;
}
if(T>second->ReachTime)
{
T=second->ReachTime;
del=second;
before=selected;
}
second=second->next;
selected=selected->next;
}while(second->next!=NULL);
before->next=del->next;
del->next=Start->next;
Start->next=del;
Start=Start->next;
before=first;
second=before->next;
selected=first;
del=second;
if(second->next==NULL)
{
second->next=Start->next;
Start->next=second;
break;
}
}while(second->next!=NULL); }
6
3(最高响应比优先算法:
void ProcessManager::HRN()
{
Process *Start=Queue;
Process *before,*second,*selected,*del;
before=selected=first;
second=del=first->next;
float T=second->ReachTime;
float CountTime=0.0; // 记录每次开始调度的时间
if(Start->next==NULL) //先找出一个最
先到达的进程放入队列
{
do
{
if(second->next==NULL)
{
del=second;
before=selected;
break;
}
if(T>second->ReachTime)
{
T=second->ReachTime;
del=second;
before=selected;
}
second=second->next;
selected=selected->next;
}while(second->next!=NULL);
CountTime+=(del->RunTime-del->ReachTime);
before->next=del->next;
del->next=Start->next;
Start->next=del;
Start=Start->next;
}
before=first;
second=first->next;
selected=first;
del=second;
//float R=(CountTime-second->ReachTime+second->RunTime)/second->RunTime;
7
do
{
float R=0.0;
do
{
if(R<((CountTime-second->ReachTime+second->RunTime)/second->RunTime))
//响应比R =(W+T)/T = 1+W/T
{
R=(CountTime-second->ReachTime+second->RunTime)/second->RunTime;
del=second;
// cout<
name<next;
selected=selected->next;
}while(second->next!=NULL);
CountTime+=del->RunTime;
before->next=del->next; //减掉最高响应比节点
del->next=Start->next;
Start->next=del; //把求得的最高响应比节点接入Queue
Start=Start->next; //未指向下一节点,存储错误
before=first;
selected=first;
second=first->next;
del=second;
if(second->next==NULL)
{
second->next=Start->next;
Start->next=second;
break;
}
}while(second->next!=NULL); //选用first->next!=NULL判断,导致越界出错
}
}
8
四、源程序清单
1,源代码文件
// FCFS and HRN.cpp : 定义控制台应用程序的入口点。 #include #include
#include #include using namespace std; struct Process
{
Process(/*string str=" ",int RT=0,int RunT=0*/)
{
name="";
ReachTime=0;
RunTime=0;
next=NULL;
}
string name; //进程名字
int ReachTime; //到达时间
int RunTime; //运行时间
Process *next; //指向下一个进程
};
class ProcessManager:public Process //管理进程 {
public:
ProcessManager()
{
first=new Process();
Queue=new Process();
Stime=0.0;
AverTime=0.0;
AverWTime=0.0;
}
void empty();
void insert(ifstream &inf); //初始化数据
void FCFS(); //执行先来先服务算法
void HRN(); //执行最高相应比优先
void CalculateTime();
float ShowAverTime() //输出平均周转时间
{
return AverTime;
}
9
float ShowAverWTime() //输出平均带权周转时间
{
return AverWTime;
}
void ShowQueue(); //输出调度队列
void Show();
protected:
Process *first; //输入的进程的头指针
Process *Queue; //经算法排列后的进程序列的头指针
float Stime;//记录每次调度的开始时间,默认0时,指从0时刻开始
float AverTime;
float AverWTime;
};
void ProcessManager::empty()
{
Stime=0.0;
AverTime=0.0;
AverWTime=0.0;
if(first->next!=NULL)
{
delete first;
first=new Process();
}
if(Queue->next!=NULL)
{
delete Queue;
Queue=new Process();
}
}
void ProcessManager::insert(ifstream &inf)
{
Process *pro=first;
while(1)
{
if(inf.eof())
break;
pro->next=new Process;
pro=pro->next;
inf>>pro->name;
inf>>pro->ReachTime;
inf>>pro->RunTime;
}
}
void ProcessManager::FCFS()
10
{
Process *Start=Queue;
Process *before,*second,*selected,*del;
before=selected=first;
second=del=first->next;
float T=0.0;
do
{
T=second->ReachTime;
do
{
if(second->next==NULL)
{
del=second;
before=selected;
break;
}
if(T>second->ReachTime)
{
T=second->ReachTime;
del=second;
before=selected;
}
second=second->next;
selected=selected->next;
}while(second->next!=NULL);
before->next=del->next;
del->next=Start->next;
Start->next=del;
Start=Start->next;
before=first;
second=before->next;
selected=first;
del=second;
if(second->next==NULL)
{
second->next=Start->next;
Start->next=second;
break;
}
}while(second->next!=NULL); }
void ProcessManager::CalculateTime()
{
11
int a=0;
Process *Start=Queue;
do
{
Start=Start->next;
Stime+=Start->RunTime;
AverTime+=(Stime-Start->ReachTime);
AverWTime+=(Stime-Start->ReachTime)/Start->RunTime;
a++;
}while(Start->next!=NULL);
AverTime/=a;
AverWTime/=a;
}
void ProcessManager::HRN()
{
Process *Start=Queue;
Process *before,*second,*selected,*del;
before=selected=first;
second=del=first->next;
float T=second->ReachTime;
float CountTime=0.0; // 记录每次开始调度的时间
if(Start->next==NULL) //先找出一个最先到达的进程放
入队列
{
do
{
if(second->next==NULL)
{
del=second;
before=selected;
break;
}
if(T>second->ReachTime)
{
T=second->ReachTime;
del=second;
before=selected;
}
second=second->next;
selected=selected->next;
}while(second->next!=NULL);
CountTime+=(del->RunTime-del->ReachTime);
before->next=del->next;
del->next=Start->next;
12
Start->next=del;
Start=Start->next;
}
before=first;
second=first->next;
selected=first;
del=second;
//float R=(CountTime-second->ReachTime+second->RunTime)/second->RunTime;
do
{
float R=0.0;
do
{
if(R<((CountTime-second->ReachTime+second->RunTime)/second->RunTime)) //响应
比R =(W+T)/T = 1+W/T
{
R=(CountTime-second->ReachTime+second->RunTime)/second->RunTime;
del=second;
// cout<name<next;
selected=selected->next;
}while(second->next!=NULL);
CountTime+=del->RunTime;
before->next=del->next; //减掉最高响应比节点
del->next=Start->next;
Start->next=del; //把求得的最高响应比节点接入Queue
Start=Start->next; //未指向下一节点,存储错误
before=first;
selected=first;
second=first->next;
del=second;
if(second->next==NULL)
{
second->next=Start->next;
Start->next=second;
break;
}
}while(second->next!=NULL); //选用first->next!=NULL判断,导致越界出错
13
}
void ProcessManager::Show() {
Process *start=Queue;
do
{
start=start->next;
cout<name<next!=NULL); }
int main()
{
ProcessManager prom;
cout<<"Please input your Filename: ";
char filename[100];
cin>>filename;
char ch;
do
{
cout<<"请选择调度算法:f->FCFS,h->HRN:";
cin>>ch;
switch(ch)
{
case 'f':
{
ifstream inf;
inf.open(filename,ios::in);
prom.empty();
prom.insert(inf);
prom.FCFS();
prom.CalculateTime();
cout<<"调度队列为:"<
教程
人力资源管理pdf成真迷上我教程下载西门子数控教程protel99se入门教程fi6130z安装使用教程
》,清华大学出版社
2、任爱华、王雷 编:《操作系统实用教程》,清华大学出版社
16
本科生课程设计成绩评定表 班级:计算机0902班 姓名:庞竞强 学号:0120810340621 序号
评分
售楼处物业服务评分营养不良炎症评分法中国大学排行榜100强国家临床重点专科供应商现场质量稽核
项目 满分 实得分 1 10 学习态度认真、遵守纪律
2 10 设计分析合理性
3 20 设计
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
正确性、可行性、创造性
4 40 设计结果正确性
5 10 设计报告的规范性
6 10 设计验收
总得分/等级 评语:
注:最终成绩以五级分制记。优(90-100分)、良(80-89分)、中(70-79分)、
及格(60-69分)、60分以下为不及格
指导教师签名:
200 年 月 日
17