实验2 间片轮转RR进程调度算法
1、 实验目的
通过这次实验，加深对进程概念的理解，进1步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
2、 实验内容
问题描写：
设计程序摹拟进程的时间片轮转RR调度进程。假定有n个进程分别在T1,… ,Tn时刻到达系统，它们需要的服务时间分别为S1,… ,Sn。分别利用不同的时间片大小q，采取时间片轮转RR进程调度算法进行调度，计算每一个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
3、 程序要求：
1）进程个数n；每一个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；输入时间片大小q。
2）时间片轮转法RR调度进程运行，计算每一个进程的周转时间和带权周转时间，并且计算所有进程的平均周转时间和带权平均周转时间；
3）输出：摹拟全部调度进程，输出每一个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；
4）输出：输出计算出来的每一个进程的周转时间、带权周转时间、所有进程的平均周转时间和带权平均周转时间。
4、 需求分析
(1) 输入的情势和输入值的范围
真实进程数
各进程的到达时间
各进程的服务时间
(2) 输出的情势
摹拟全部调度进程、周转时间、带权周转时间、所有进程的平均周转时间和带权平均周转时间。
（3）测试用例
|
作业情况
时间片 |
进程名 |
A |
B |
C |
D |
E |
平均 |
|
到达时间 |
0 |
1 |
2 |
3 |
4 |
|
|
|
服务时间 |
4 |
3 |
5 |
2 |
4 |
|
|
|
RR q=1 |
完成时间 |
12 |
10 |
18 |
11 |
17 |
|
|
周转时间 |
12 |
9 |
16 |
8 |
13 |
11.6 |
|
|
带权周转时间 |
3 |
3 |
3.2 |
4 |
3.25 |
3.29 |
|
|
RR q=4 |
完成时间 |
4 |
7 |
18 |
13 |
17 |
|
|
周转时间 |
4 |
6 |
16 |
10 |
13 |
9.8 |
|
|
带权周转时间 |
1 |
2 |
3.2 |
5 |
3.25 |
2.89 |
5、 概要设计
抽象数据类型定义：
// 时间片
publicstatic int q = 0;
//允许的最大进程数
publicstatic int MaxNum = 100;
//真实的进程数
publicstatic int realNum;
//order数组的1个下标
publicstatic int number;
//当前时间
publicstatic int NowTime;
//各进程的到达时间
publicstatic int ArrivalTime[] = new int[MaxNum];
//各进程的服务时间
publicstatic int ServiceTime[] = new int[MaxNum];
//各进程的服务时间(用于记录进程服务时间随时间片轮转减少的进程)
public static int PServiceTime[] = new int[MaxNum];
//各进程的完成时间
publicstatic int FinishTime[] = new int[MaxNum];
//各进程的周转时间
publicstatic int WholeTime[] = new int[MaxNum];
// 进程调度队列（寄存的是各个进程的数字代号，如进程A数字代号为1）
public static int order[] = new int[MaxNum];
// 各进程的带权周转时间
publicstatic double WeightWholeTime[] = new double[MaxNum];
//平均周转时间、平均带权周转时间
public static double AverageWT, AverageWWT;
//周转时间总和
publicstatic int SumWT = 0;
//带权周转时间总和
publicstatic double SumWWT = 0;
//进程是不是已结束的标志
publicstatic boolean Finished[] = new boolean[MaxNum];
public static Scanner input;主程序的流程：
各模块之间的层次关系：只有Main方法
6、 详细设计
代码详见附录
7、 调试分析
（1）调试进程中遇到的问题及解决办法
本次实验比较简单。
（2）算法的性能分析
基本操作：all_add++;
时间复杂度：O（服务时间/ q * （n⑴））
（3）经验和体会
本次实验比较简单。
8、 测试结果
时间片q为1时的输出
时间片q为4输出
7、附录(java)
importjava.io.BufferedInputStream;
importjava.io.FileInputStream;
importjava.io.FileNotFoundException;
importjava.util.Scanner;
publicclass RR {
// 时间片
public static int q = 0;
// 允许的最大进程数
public static int MaxNum = 100;
// 真实的进程数
public static int realNum;
// order数组的1个下标
public static int number;
// 当前时间
public static int NowTime;
// 各进程的到达时间
public static int ArrivalTime[] = newint[MaxNum];
// 各进程的服务时间
public static int ServiceTime[] = newint[MaxNum];
// 各进程的服务时间(用于记录进程服务时间随时间片轮转减少的进程)
public static int PServiceTime[] = newint[MaxNum];
// 各进程的完成时间
public static int FinishTime[] = newint[MaxNum];
// 各进程的周转时间
public static int WholeTime[] = newint[MaxNum];
// 进程调度队列（寄存的是各个进程的数字代号，如进程A数字代号为1）
public static int order[] = new int[MaxNum];
// 各进程的带权周转时间
public static double WeightWholeTime[] = newdouble[MaxNum];
// 平均周转时间、平均带权周转时间
public static double AverageWT, AverageWWT;
// 周转时间总和
public static int SumWT = 0;
// 带权周转时间总和
public static double SumWWT = 0;
// 进程是不是已结束的标志
public static boolean Finished[] = newboolean[MaxNum];
public static Scanner input;
public static void main(String[] args)throws FileNotFoundException {
System.out.println("请输入时间片q：");
input = new Scanner(System.in);
q = input.nextInt();
// 从文件中输入数据
BufferedInputStream in = newBufferedInputStream(new FileInputStream("test.txt"));
System.setIn(in);
input = new Scanner(System.in);
realNum = input.nextInt(); // 真实进程数
for (int i = 0; i < realNum; i++) {// 各进程的到达时间
ArrivalTime[i] = input.nextInt();
}
for (int j = 0; j < realNum; j++) {// 各进程的服务时间
ServiceTime[j] = input.nextInt();
PServiceTime[j] =ServiceTime[j]; //用于记录进程服务时间随时间片轮转减少的进程
Finished[j] = false;
}
//关闭文件流
input.close();
int all_add = 1; //就绪队列中的进程个数
order[0] = 0; //进程调度队列（寄存的是各个进程的数字代号，如进程A数字代号为1）
number = 1;
NowTime = 0; //当前时间
while (order[0] != 100) { //order[0]为100，是认为规定进程调度结束的标志
// 调度进程A
char w = 'A';
System.out.println("时刻"+ NowTime + "：进程" + (char)(w + order[0]) + "开始运行;");
if (PServiceTime[order[0]] > q){ //进程还未完成
PServiceTime[order[0]] = PServiceTime[order[0]]- q; //对应进程的服务时间减去1个时间片
NowTime += q; //当前时间增加1个时间片
System.out.println("时刻"+ NowTime + "：进程" + (char)(w + order[0]) + "停止运行,加入就绪序列尾;");
} else { //进程剩1个时间片后结束
NowTime +=PServiceTime[order[0]]; //当前时间增加1个时间片
PServiceTime[order[0]] = 0; //对应进程的服务时间归零
System.out.println("时刻"+ NowTime + "：进程" + (char)(w + order[0]) + "运行结束;");
FinishTime[order[0]] = NowTime;
WholeTime[order[0]] = NowTime -ArrivalTime[order[0]];//周转时间 = 完成时间 - 到达时间
WeightWholeTime[order[0]] = 1.0* WholeTime[order[0]] / ServiceTime[order[0]];//带权周转时间 = 周转时间 / 服务时间
}
// 将到达的进程加入序列尾
if (all_add < realNum) {
for (int i = 1; i < realNum;i++) {
if (NowTime >=ArrivalTime[i] && Finished[i] == false) { //判断该进程是不是已在就绪队列中
order[number++] = i;
all_add++;
Finished[i] = true;
}
}
}
// 将序列首程序调到序列尾
int temp = order[0];
for (int i = 0; i < number - 1;i++){ //将order中的每一个数前移1位
order[i] = order[i + 1];
}
if (PServiceTime[temp] == 0){ //进程已将全部调度结束，通过将order的第1个数标记为100，来结束进程调度
order[--number] = MaxNum;
}else{ //进程还未调度结束
order[number - 1] = temp;//加入就绪队列队尾
}
}
double all = 0, all1 = 0;
for (int i = 0; i < realNum; i++) {//计算总周转时间和总带权周转时间
all += WholeTime[i];
all1 += WeightWholeTime[i];
}
System.out.println("\n进程名\t到达时间\t服务时间\t完成时间\t周转时间\t带权周转时间");
for (int i = 0; i <realNum; i++) {
System.out.println((char)(i + 'A') +"\t" + ArrivalTime[i] + "\t"
+ ServiceTime[i] +"\t" + FinishTime[i] + "\t"
+ WholeTime[i] +"\t" + WeightWholeTime[i]);
}
AverageWT = all / realNum; //平均周转时间 = 周转总时间 / 作业个数
System.out.println("平均周转时间:"+ AverageWT);
AverageWWT = all1 / realNum; //评均带权周转时间 = 带权周转总时间 / 作业个数
System.out.println("平均带权周转时间:" + AverageWWT);
}
}
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
