课 程 设 计
题 目
学 院
专 业
班 级
姓 名 指导教师
进程调度模拟设计—先来先服务、最高响应比优先调度算法 计算机科学与技术学院 计算机科学与技术专业 计算机科学与技术0902班 庞竞强 郭羽成
2011 年 01 月 12 日
课程设计任务书
指导教师： 郭羽成 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计——先来先服务、最高响应比优先调度算法 初始条件：
1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。
2．实践准备：掌握一种计算机高级语言的使用。 学生姓名： 庞竞强 专业班级： 计算机0902班
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1．模拟进程调度，能够处理以下的情形：
⑴ 能够选择不同的调度算法（要求中给出的调度算法）；
⑵ 能够输入进程的基本信息，如进程名、到达时间和运行时间等；
⑶ 根据选择的调度算法显示进程调度队列；
⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．设计报告内容应说明：
⑴ 课程设计目的与功能；
⑵ 需求分析，数据结构或模块说明(功能与框图)；
⑶ 源程序的主要部分；
⑷ 测试用例，运行结果与运行情况分析；
⑸ 自我评价与总结：
i）你认为你完成的设计哪些地方做得比较好或比较出色；
ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；
iv）完成本题是否有其他方法（如果有，简要说明该方法）；
v）对实验题的评价和改进意见，请你推荐设计题目。
时间安排：
设计安排一周：周1、周2：完成程序分析及设计。
周2、周3：完成程序调试及测试。
周4、周5：验收、撰写课程设计报告。
（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）
指导教师签名： 年 月 日 系主任（或责任教师）签名： 年 月 日
进程调度模拟设计
——先来先服务、最高响应比优先调度算法
一、概述
1、设计目的
（1）加深对进程的概念地理解。
（2）掌握先来先服务算法、最高相应比优先算法。
（3）了解进程控制块的作用，以及进程控制块的内容和组织方式。
2、开发环境
实验平台：个人计算机机
操作系统：Windows XP
编译环境：microsoft visual c++ 6.0
二、需求分析
1、进程调度：
进程调度是处理机管理的核心内容。本实验要求编写和调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念，并体会和了解优先数和时间片轮转调度算法的具体实施办法。
在系统中将用户提交的多个进程都先存放在外存上，并排成一个队列，按照一定的算法调度，从队列中选择若干个进程调入内存，并允许它们根据某种算法交替执行，共享系统中的各种硬软件资源。
操作系统根据一定的算法从系统中选取若干进程把它们装入内存，使它们有机会获得处理
器运行这项进程被称为“进程调度”。实现这部分的功能程序就是“进程调度程序”。
3、进程调度的实现：
A．利用进程控制块将系统中的进程组织起来；
进程是根据进程控制块（JCB）组织起来的，进程控制块为每个进入系统的进程建立档案以记录和进程相关的信息，例如进程名、进程所需要的资源、进程执行的时间、进程进入系统的时间、进程信息在存储器中的位置、指向下一个进程控制块的指针等信息。,并将系统中等待进程调度的进程控制块组织成一个队列，这个队列称为后备队列。当一个进程全部信息进入系统后，就为其建立进程控制块，并挂入后备队列中。当一个进程全部进入系统后，就为其建立进程控制块，并挂入后备队列中。当进行进程调度时，从后备队列中查找选择进程。
B．利用优先级法进行进程调度；
在从后备队列中查找选择进程时，先根据进程控制块中的信息，选中一个优先级最高的进程，将
它们调入内存运行。
C．利用短进程优先算法进行进程调度；
在从后备队列中查找选择进程时，先根据进程控制块中的信息，选中一个短进程，也就
是执行时间最短的进程，将它们调入内存运行。
4、进程控制块：
A．进程控制块的内容：
①进程名 (name)；
②进程的提交时间（ReachTime）；
③进程估计执行时间（Runtime）；
④指向下一个进程控制块的指针（next）；
B．进程控制块的组织方式：
采用静态链接方式把进程控制块组织成一个后备队列。通过用进程控制块的指针
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) {
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);
}
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;
do
{
float R=0.0;
do
{
if(RReachTime+second->RunTime)/second->RunTime)) //响应比R =(W+T)/T = 1+W/T
{
R=(CountTime-second->ReachTime+second->RunTime)/second->RunTime; del=second;
// coutname
before=selected;
}
second=second->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判断，导致越界出错
}
}
四、源程序清单
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;
}
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()
{ 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() {
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;
//先找出一个最先到达的进程放
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(RReachTime+second->RunTime)/second->RunTime)) //响应比R =(W+T)/T = 1+W/T { R=(CountTime-second->ReachTime+second->RunTime)/second->RunTime; del=second; // coutnamenext; 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判断，导致越界出错
}
void ProcessManager::Show() { Process *start=Queue; do { start=start->next; coutnamenext!=NULL); }
int main() { ProcessManager prom; cout>filename; char ch; do { coutFCFS,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
prom.insert(inf); prom.HRN(); prom.CalculateTime(); cout
2，测验用例：
进程名 提交时间 运行时间 a 0 10 b 1 15 c 3 8 d 4 9
e 8 20 运行结果截图
4，运行结果分析与改进：
由以上运行结果的截图可知，该程序很好的实现了所要求的功能，对进程的调度做到了很好的模拟，程序中设计了为四个进程，可按需要更改和增加。
5，对该程序的评价：
本次设计的程序虽然功能比较单一，但是对进程调度起到了很好的模拟效果，有利于操作系统初学者用来加深对进程的理解。在有些方面还是可以改进的，例如本例中对时间的模拟是通过时间变量time++来实现的，并且预先设计时间以整数为单位自加，这对于进程的真实运行情况来说，可能是不合理的，可通过引用时间等待函数来进行改进，另外本次程序中用的是静态的先来先服务算法，这对于那些，可是执行时间短，提交时间晚的进程来说是很不合理的，这里可通过引进动态优先级来实现
五、结束语
1、心得与体会：
经过这次设计，我进一步加深了对进程基本原理的理解，加深了对课堂上知识的巩固，掌握先来先服务算法、最高响应比优先算法，了解进程控制块的作用，以及进程控制块的内容和组织方式。另外，通过亲手设计程序的过程也增强了程序设计的能力，学到了很多知识，计算机操作系统是一门很重要的课程，做好这次课程设计对后续课程的学习有很大的帮忙。
六、参考文献
1、张尧学、史美林 编：《计算机操作系统教程》，清华大学出版社 2、任爱华、王雷 编：《操作系统实用教程》，清华大学出版社
本科生课程设计成绩评定表
班级：计算机0902班 姓名：庞竞强 学号：[1**********]21
及格（60-69分）、60分以下为不及格
指导教师签名：
200 年 月 日