进程调度算法模拟带答案版复习进程.doc

进程调度算法模拟带答案版

精品文档
实验二 进程管理
2.5 作业（进程）调度算法模拟
1．实验目的与要求
本实验的目的是通过作业或进程调度算法模拟设计，进一步加深对作业或进程调度算法的理解，通过计算平均周转时间和带权平均周转时间，进一步加深对算法的评价方法的理解。
2. 实验类型：验证型
3. 实验学时：4
4. 实验原理和知识点
（1） 掌握作业或进程调度算法。
（2） 平均周转时间和带权平均周转时间计算。
5. 实验环境（硬件环境、软件环境）：
（1） 硬件环境：Intel Pentium III 以上CPU，128MB以上内存，2GB以上硬盘。
（2） 软件环境：linux操作系统gcc编译器或windows操作系统vc++集成开发环境。
6. 实验内容
设定一组作业或进程，给定相关参数，对这组进程或作业按调度算法实施调度，输出调度次序，并计算平均周转时间和带权平均周转时间。使用的调度算法有：
① 先来先服务调度算法。
② 优先级调度算法。
③ 短作业（或进程）优先调度算法。
④ 响应比高优先调度算法
6.1 使用的主要数据结构：
（1） 定义一个结构体，结构体的主要成员有：序号、作业（进程）号或名称、提交时间、运行时间、优先数、进入输入井时间、开始运行时间、尚需运行时间、运行结束时间、周转时间、带权周转时间、运行次序等。
（2） 利用定义的结构体，定义一个结构体数组，用来记录系统中的作业或进程。
6.2 算法描述：
1．主控程序算法描述
进程（作业）参数输入
选择调度算法
0 1 2 3 4
调用先来先服务调度程序
调用短作业（进程）调度程序
调用响应比高者优先调度程序
重复执行
输出调度结果

2．数据输入算法
输入进程或作业个数
对每一个进程或作业
输入进程或作业名
输入进程或作业号
输入进程或作业到达时间
输入进程或作业运行时间
输入进程或作业优先级

3．数据输出算法
对每个作业执行
输出进程（或作业）号、进程（或作业）名、
到达时间、
开始运行时间、
运行结束时间、
优先级、
运行次序、
周转时间、
带权周转时间
计算并输出平均周转时间、带权周转时间
平均

4．先来先服务调度算法描述
系统中有未运行的作业
在未运行的作业中选择一个提交时间最早的作业
把运行次序填入数组相应位置；
分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。
调用输出程序输出结果

先来先服务调度算法

5．优先级调度算法
系统中有未运行的作业
把运行次序填入数组相应位置；
分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。
调用数据输出程序输出结果

优先级调度算法
在数组中找第一个未运行的作业
Pminß该作业的优先数
（当前最小的）
kß该作业的在数组中的下标
作业的优先数
与Pnim比较
有未运行的作业
未找到
找到
Pminß该作业
的优先数
kß该作业的
在数组中的下标
大

6．短作业（或进程）优先调度算法

作业的运行时间
与Rnim比较
有未运行的作业
未找到
找到
Rminß该作业
的运行时间
kß该作业的
在数组中的下标
长
短
选择运行时间最短作业的算法

7．响应比高优先调度算法

系统中有未运行的作业
在未运行的作业中选择一个响应比最高的作业运行
（响应比相同按先来先服务进行选择）
把运行次序填入数组相应位置；
分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。
调用数据输出程序输出结果

响应比高优先调度算法

6.3 C语言程序实现
#include<stdio.h>
//using namespace std;
#define MAX 10
struct task_struct
{
char name[10]; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志*/
}tasks[MAX];
int counter; /*实际进程个数*/
int fcfs(); /*先来先服务*/
int ps(); /*优先级调度*/
int sjf(); /*短作业优先*/
int hrrn(); /*响应比高优先*/
int pinput(); /*进程参数输入*/
int poutput(); /*调度结果输出*/

void main()
{ int option;
pinput();
printf("请选择调度算法（0~4）:\n");
printf("1.先来先服务\n");
printf("2.优先级调度\n");
printf(" 3.短作业优先\n");
printf(" 4.响应比高优先\n");
printf(" 0.退出\n");
scanf("%d",&option);
switch (option)
{ case 0:
printf("运行结束。\n");
break;
case 1:
printf("对进程按先来先服务调度。\n\n");
fcfs();
poutput();
break;
case 2:
printf("对进程按优先级调度。\n\n");
ps();
poutput();
break;
case 3:
printf("对进程按短作业优先调度。\n\n");
sjf();
poutput();
break;
case 4:
printf("对进程按响应比高优先调度。\n\n");
hrrn();
poutput();
break;
}
}
int fcfs() /*非抢占式先来先服务，该程序段默认进程已经按到达先后顺序排成了队列，如果考虑输入为乱序，还需要根据come_time对进程进行排队，形成一个先来后到的队列。*/
{
float time_temp=0;
int i;
int number_schedul;
time_temp=tasks[0].come_time;
for(i=0;i<counter;i++)
{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;
tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;
number_schedul=i;
tasks[number_schedul].order=i+1;
}
return 0;
}
/*非抢占式优先级调度，默认tasks[0]是最早到达的进程，进程已按到达先后顺序排成了队列。*/
int ps()
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/
int max_priority;
max_priority=tasks[i].priority;
j=1;
/* 从从到达时间最早且相同的进程中遍历，查找第一个被调度的进程*/
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))/*寻找到达时间相同优先级最高的进程。*/
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
}
/*对第一个被调度的进程求相应的参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;

/*循环查找下一个被调度的进程，直到所有的tasks[j].run_flag ==1*/
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{ if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schedul=j;
}
}

/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schedul].run_begin_time=temp_time; tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter;
}
return 0;
}

int sjf() /*非抢占式短作业优先，默认tasks[0]是最早到达的进程，进程已按到达先后顺序排成了队列。*/
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/
float run_time; /*借助该局部变量可以帮助找到执行时间run_time最短进程*/
run_time=tasks[i].run_time;
j=1;
/*从到达时间最早且相同的进程中查找第一个被调度的进程*/
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].run_time<tasks[i].run_time)
{
run_time=tasks[j].run_time;
i=j;
}
j++;
}
/*对第一个被调度的进程求相应的参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;
/*循环查找下一个被调度的进程，直到所有的tasks[j].run_flag ==1*/
while (temp_counter<counter)
{ /*找到在上一个进程执行期间（到“目前”为止）到达时间最晚的一个进程*/
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{ run_time=tasks[j].run_time;number_schedul=j;break;}
}
/* 找到到“目前”为止，最短的进程，即run_time 最小的进程*/
for(j=0;j<counter;j++)
{ if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if(tasks[j].run_time<run_time)
{run_time=tasks[j].run_time;
number_schedul=j;
}
}
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schedul].run_begin_time=temp_time; tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter;
}
return 0;
}
/*非抢占式响应比高优先，默认tasks[0]是最早到达的进程，进程已按到达先后顺序排成了队列。*/
int hrrn()
{ int j,number_schedul,temp_counter;
float temp_time,respond_rate,max_respond_rate;
/*第一个进程被调度，系统刚开始运行时，同时到达的进程响应比都为0（按该程序所采用的等待时间/运行时间这个公式算），因此按队列顺序必然是第一个进程最先被调度*/
tasks[0].run_begin_time=tasks[0].come_time;
tasks[0].run_end_time=tasks[0].run_begin_time+tasks[0].run_time;
temp_time=tasks[0].run_end_time;
tasks[0].run_flag=1;
tasks[0].order=1;
temp_counter=1;
/*调度其他进程*/
while(temp_counter<counter)
{
max_respond_rate=0;
/*找响应比高的进程*/
for(j=1;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{ respond_rate=(temp_time-tasks[j].come_time)/tasks[j].run_time;
if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate;
number_schedul=j;
}
}
}
tasks[number_schedul].run_begin_time=temp_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].run_flag=1;
temp_counter+=1;
tasks[number_schedul].order=temp_counter;
}
return 0;
}
int pinput() /*进程参数输入*/
{ int i;
printf("please input the process counter:\n");
scanf("%d",&counter);

for(i=0;i<counter;i++)
{ printf("******************************************\n");
printf("please input the process of %d th :\n",i+1);
printf("please input the name:\n");
scanf("%s",tasks[i].name);
printf("please input the number:\n");
scanf("%d",&tasks[i].number);
printf("please input the come_time:\n");
scanf("%f",&tasks[i].come_time);
printf("please input the run_time:\n");
scanf("%f",&tasks[i].run_time);
printf("please input the priority:\n");
scanf("%d",&tasks[i].priority);
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
return 0;
}
int poutput() /*调度结果输出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("name number come_time run_time run_begin_time run_end_time priority order turn_round_time\n");
for(i=0;i<counter;i++)
{
f1=tasks[i].run_end_time-tasks[i].come_time;
turn_round_time+=f1;
w+=(f1/tasks[i].run_time);
printf(" %s, %d, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d, %5.3f\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].order,f1);
}
printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
printf("weight_average_turn_round_timer=%5.2f\n",w/counter);
return 0;
}
7. 验证与设计
（1）用程序验证下列题目，结果与理论课所讲是否一致，如果不一致，请分析原因：
题1:下表给出作业1，2，3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各是多少？

1
2
3

4
1
2

8
0
1
周转
时间
完成
时间
开始
时间
运行
时间
到达
时间
作业号
Rminß该作业的运行时间
（当前最短的）
kß该作业的在数组中的下标
在数组中找第一个未运行的作业

把运行次序填入数组相应位置；
分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。

调用优先级调度程序
退出
程序

题2、在下表中给出进程的到达时间、执行时间和优先级，请给出三种种调度算法的进程执行次序和三种调度算法的平均周转时间。这三种调度算法是：短作业优先调度算法、优先级高者优先调度算法和简单轮转法（简单轮转法中的时间片为2个单位）。（抢占式调度策略）（目前，只需要验证短作业优先调度算法、优先级高者优先调度算法）

轮转调度算法
首次运行
运行情况
记录开始运行时间
是
否
计算尚需运行时间
时间片到
运行结束
系统中存在未运行完的作业
记录开始时间
计算运行结束时间
计算周转时间
记录结束次序
计算平均周转时间
输出结果
（2）参考给出的源代码，试设计时间片轮转调度算法，并验证题2中的简单轮转法（简单轮转法中的时间片为2个单位）.

参考源代码：
#include<stdio.h>
//using namespace std;
#define MAX 10
struct task_struct
{
char name[10]; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志，在轮转中，0表示没有运行完，1表示已经运行完*/
}tasks[MAX];
int counter; /*实际进程个数*/
int fcfs(); /*先来先服务*/
int ps(); /*优先级调度*/
int sjf(); /*短作业优先*/
int hrrn(); /*响应比高优先*/
int pinput(); /*进程参数输入*/
int poutput(); /*调度结果输出*/
int rr(); /*轮转*/

void main()
{ int option;
float rr_time;
pinput();
printf("请选择调度算法（0~4）:\n");
printf("1.先来先服务\n");
printf("2.优先级调度\n");
printf(" 3.短作业优先\n");
printf(" 4.响应比高优先\n");
printf(" 5.轮转调度算法\n");
printf(" 0.退出\n");
scanf("%d",&option);
switch (option)
{ case 0:
printf("运行结束。\n");
break;
case 1:
printf("对进程按先来先服务调度。\n\n");
fcfs();
poutput();
break;
case 2:
printf("对进程按优先级调度。\n\n");
ps();
poutput();
break;
case 3:
printf("对进程按短作业优先调度。\n\n");
sjf();
poutput();
break;
case 4:
printf("对进程按响应比高优先调度。\n\n");
hrrn();
poutput();
break;
case 5:
printf("进行时间片轮转调度。\n");
rr();
poutput();
break;
}
}

int rr() /*轮转*/
{
float rr_time; /* */
int i,temp_counter=0;
int run_begin_flag[MAX]={0};
/*循环变量、已经全部完成的进程数量、进程是否第一次运行用于计算进程的开始运行时间*/
float time_temp,rest_time[MAX]={0};
/*当前时间、被调度的进程还剩下多少时间没被执行*/

printf("请输入时间片包含的单位时间个数：\n");
scanf("%f",&rr_time);

time_temp=tasks[0].come_time;
//计算各个进程的初始剩余时间
for(i=0;i<counter;i++)
{
rest_time[i]=tasks[i].run_time;
}

/*轮转调度*/

while (temp_counter<counter)
{
for(i=0;i<counter;i++)
{
if(tasks[i].run_flag==0) //判断是否运行完，为0表示还没有运行完
{
if(run_begin_flag[i]==0)//如果是第一次轮转
{
tasks[i].run_begin_time=time_temp;
run_begin_flag[i]=1;
/*如果开始第一次运行标志为0，记录开始运行时间、改变标记*/
}

if(rest_time[i]<=rr_time) //如果是最后一次轮转
{
time_temp=time_temp+rest_time[i];
tasks[i].run_end_time=time_temp;
rest_time[i]=0;
temp_counter++;
tasks[i].order=temp_counter;
tasks[i].run_flag=1;
}
else //如果不是最后一次轮转
{
rest_time[i]=rest_time[i]-rr_time;
time_temp=time_temp+rr_time;
}
}
}
}
return 0;
}

int fcfs() /*非抢占式先来先服务，该程序段默认进程已经按到达先后顺序排成了队列，如果考虑输入为

乱序，还需要根据come_time对进程进行排队，形成一个先来后到的队列。*/
{
float time_temp=0;
int i;
int number_schedul;
time_temp=tasks[0].come_time;
for(i=0;i<counter;i++)
{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;
tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;
number_schedul=i;
tasks[number_schedul].order=i+1;
}
return 0;
}
/*非抢占式优先级调度，默认tasks[0]是最早到达的进程，进程已按到达先后顺序排成了队列。*/
int ps()
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/
int max_priority;
max_priority=tasks[i].priority;
j=1;
/* 从从到达时间最早且相同的进程中遍历，查找第一个被调度的进程*/
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))/*寻找到达时间相同优先级最高的

进程。*/
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
}
/*对第一个被调度的进程求相应的参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;

/*循环查找下一个被调度的进程，直到所有的tasks[j].run_flag ==1*/
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{ if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schedul=j;
}
}

/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schedul].run_begin_time=temp_time; tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter;
}
return 0;
}

int sjf() /*非抢占式短作业优先，默认tasks[0]是最早到达的进程，进程已按到达先后顺序排成了队列

。*/
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_