一、实验目的
1.对进程调度的工作做进一步的理解。
2.了解进程调度的任务。
3.通过编程掌握基于优先数的时间片轮转调度算法具体实现过程。
二、实验内容及实验要求
1.设计一个程序模拟实现基于优先数的时间片轮转调度算法调度处理。
2.每个进程用一个进程控制块PCB来代表，建议进程控制块的结构如下所示：
进程名 到达时间 要求运行时间 优先数 已运行时间 周转时间 指针
1)进程名：作为进程的标识。
2)到达时间：进程进入系统时间。
3)要求运行时间：假设进程需要运行的单位时间数。
4)已运行时间：假设进程已经运行的单位时间数，初值为0。
5)状态：可假设有三种状态：未进入状态、就绪状态和结束状态。进程的初始状态都为未进入状态，到达时间-当前时间数时=0进程从未进入状态进入就绪状态；当要求运行时间-已运行时间=0时进程进入结束状态。
6)优先数：范围0－100，优先数越小，级别越高。
7)周转时间：进程从到达开始到结束运行所经历时间数。
8)指针：进程按顺序排成链表(不同队列进程排列顺序不一样)，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址。
3.程序开始运行时输入多个进程信息，用于实现对进程控制块的初始化。测试输入数据表1所示：
表1 输入数据表
进程名 A B C D E F
到达时间 0 0 1 1 3 5
要求运行时间 4 5 5 4 4 4
优先数 3 2 0 10 5 2
4.程序在没有开始运行前，全部进程所处的状态都处于未进入状态。
5.程序当中应该组织三个队列：未进入队列、就绪队列和结束队列。
6.就绪队列中的就绪进程按优先数由小到大排列，优先级最高的进程，获得 被调度的资格。当某一进程运行完一个时间片后，其优先级应下调（如优先数加3）。
7.启动自动调度，系统时间单位开始自动计时，系统开始自动调度执行。程序显示每个时间单位的各个队列的 PCB信息。
8.最后输出每个进程的周转时间。
三、实验时间
4个学时
五、实验报告
1.程序中使用的数据结构及符号说明。
2.主要算法的流程图或详细说明。
3.程序运行时的初值和运行结果截图。
4.程序清单并附上注释
5.实验小结
RR.java
package 时间片轮盘调度算法模拟;
import java.util.LinkedList;
import java.util.Scanner;
/**
*
* @author wangh
*/
public class RR {
//进程控制块PCB
class PCB {
String name;//进程名
int startTime;//到达时间
int needTime;//要求运行时间
int priority;//优先数
int runTime;//已运行时间
int trunTime;//周转时间
}
int n;//进程数
int t;//时间片大小
int count = 0;//当前时间片
int acount = 0;//当前时间
Scanner scanner = new Scanner(System.in);
//未进入队列输入
void noreinput(LinkedList<PCB> noreList) {
for (int i = 0; i < n; i++) {
PCB a = new PCB();
System.out.print("进程名：");
a.name = scanner.next();
System.out.print("到达时间：");
a.startTime = scanner.nextInt();
System.out.print("要求运行时间：");
a.needTime = scanner.nextInt();
System.out.print("优先数：");
a.priority = scanner.nextInt();
noreList.addLast(a);
System.out.println();
}
}
//,输入从aList到bList
void readyInput(LinkedList<PCB> aList, LinkedList<PCB> bList, int u) {
switch (u) {
//未进入队列->就绪队列
case 0: {
if (!aList.isEmpty()) {
for (int i = 0; i < aList.size(); i++) {
if (aList.get(0).startTime <= acount) {
PCB b = new PCB();
b.name = aList.get(0).name;
b.needTime = aList.get(0).needTime;
b.priority = aList.get(0).priority;
b.runTime = 0;
bList.addLast(b);
aList.remove(0);
i--;
}
}
}
}
break;
//就绪队列->运行队列
case 1: {
if (!aList.isEmpty()) {
PCB b = new PCB();
b.name = aList.get(0).name;
b.needTime = aList.get(0).needTime;
b.priority = aList.get(0).priority;
b.runTime = aList.get(0).runTime;
bList.addLast(b);
aList.remove(0);
}
}
break;
//运行队列->就绪队列
case 2: {
if (!aList.isEmpty()) {
PCB b = new PCB();
b.name = aList.get(0).name;
b.needTime = aList.get(0).needTime;
b.priority = aList.get(0).priority + 3;
b.runTime = aList.get(0).runTime + t;
bList.addLast(b);
aList.remove(0);
}
}
break;
//运行队列->结束队列
case 3: {
if (!aList.isEmpty()) {
PCB b = new PCB();
b.name = aList.get(0).name;
b.needTime = aList.get(0).needTime;
b.runTime = aList.get(0).runTime + t;
b.trunTime = acount - aList.get(0).startTime;
bList.addLast(b);
aList.remove(0);
}
}
break;
default:
break;
}
}
//未进入队列排序
void sorted(LinkedList<PCB> list) {
PCB temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
//按到达时间排序
if (list.get(j).startTime > list.get(j + 1).startTime) {
temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}//按优先数排序,数字小优先数高
else if (list.get(j).startTime == list.get(j + 1).startTime && list.get(j).priority > list.get(j + 1).priority) {
temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
//优先数排序
void sort(LinkedList<PCB> list) {
if (list.size() >= 2) {
PCB temp;
for (int i = 0; i < list.size() - 1; i++) {
for (int j = 0; j < list.size() - 1 - i; j++) {
if (list.get(j).priority > list.get(j + 1).priority) {
temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
}
void sorti(LinkedList<PCB> list) {
PCB temp;
for (int i = 0; i < list.size() - 1; i++) {
for (int j = 0; j < list.size() - 1 - i; j++) {
if (list.get(j).trunTime < list.get(j + 1).trunTime) {
temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
void output(LinkedList<PCB> runList, LinkedList<PCB> readyList, LinkedList<PCB> noreList, LinkedList<PCB> endList) {
//运行队列
System.out.println("--------------运行队列--------------");
System.out.printf("(%7s,%7s,%7s,%7s)", "进程名", "要求运行时间", "优先数", "已运行时间");
System.out.println();
if (runList.isEmpty()) {
System.out.println(" 队列为空");
} else {
for (int i = 0; i < runList.size(); i++) {
System.out.printf("%10s", runList.get(i).name);
System.out.printf("%10d", runList.get(i).needTime);
System.out.printf("%10d", runList.get(i).priority);
System.out.printf("%10d", runList.get(i).runTime);
System.out.println();
}
}
//就绪队列
System.out.println("--------------就绪队列--------------");
System.out.printf("(%7s,%7s,%7s,%7s)", "进程名", "要求运行时间", "优先数", "已运行时间");
System.out.println();
if (readyList.isEmpty()) {
System.out.println(" 队列为空");
} else {
for (int i = 0; i < readyList.size(); i++) {
System.out.printf("%10s", readyList.get(i).name);
System.out.printf("%10d", readyList.get(i).needTime);
System.out.printf("%10d", readyList.get(i).priority);
System.out.printf("%10d", readyList.get(i).runTime);
System.out.println();
}
}
//未进入队列
System.out.println("--------------未进入队列-------------");
System.out.printf("(%7s,%7s,%7s,%7s)", "进程名", "到达时间", "要求运行时间", "优先数");
System.out.println();
if (noreList.isEmpty()) {
System.out.println(" 队列为空");
} else {
for (int i = 0; i < noreList.size(); i++) {
System.out.printf("%10s", noreList.get(i).name);
System.out.printf("%10s", noreList.get(i).startTime);
System.out.printf("%10s", noreList.get(i).needTime);
System.out.printf("%10s", noreList.get(i).priority);
System.out.println();
}
}
//结束队列
System.out.println("--------------结束队列--------------");
System.out.printf("(%7s,%7s,%7s,%7s)", "进程名", "要求运行时间", "已运行时间", "周转时间");
System.out.println();
if (endList.isEmpty()) {
System.out.println(" 队列为空");
} else {
for (int i = 0; i < endList.size(); i++) {
System.out.printf("%10s", endList.get(i).name);
System.out.printf("%10d", endList.get(i).needTime);
System.out.printf("%10d", endList.get(i).runTime);
System.out.printf("%10d", endList.get(i).trunTime);
System.out.println();
}
}
}
}
test.java
package 时间片轮盘调度算法模拟;
import java.util.LinkedList;
import java.util.Scanner;
/**
*
* @author wangh
*/
public class test {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
RR r = new RR();
//未进入队列
LinkedList<RR.PCB> noreList = new LinkedList<>();
noreList.clear();
//就绪队列
LinkedList<RR.PCB> readyList = new LinkedList<>();
readyList.clear();
//运行队列
LinkedList<RR.PCB> runList = new LinkedList<>();
runList.clear();
//结束队列
LinkedList<RR.PCB> endList = new LinkedList<>();
endList.clear();
Scanner scanner = new Scanner(System.in);
System.out.print("请输入时间片大小：");
r.t = scanner.nextInt();
System.out.print("请输入进程数：");
r.n = scanner.nextInt();
r.noreinput(noreList);
r.sorted(noreList);
System.out.println("未开始调度时");
r.output(runList, readyList, noreList, endList);
System.out.println("开始调度时");
do {
r.readyInput(noreList, readyList, 0);
r.sort(readyList);
r.readyInput(readyList, runList, 1);
r.count++;
r.acount = r.acount + r.t;
System.out.println("第" + r.count + "个时间片时");
r.output(runList, readyList, noreList, endList);
if (runList.get(0).runTime <= runList.get(0).needTime - r.t) {
r.readyInput(runList, endList, 3);
} else {
r.readyInput(runList, readyList, 2);
r.sort(readyList);
}
} while (endList.size()!=r.n);
r.readyInput(runList, endList, 3);
r.sorti(endList);
System.out.println("所有进程运行完毕，显示各个进程的周转时间:");
System.out.println("(按周转时间从大到小排列)");
System.out.printf("(%7s,%7s)", "进程名","周转时间");
System.out.println();
for (int i = 0; i < endList.size(); i++) {
System.out.printf("%10s", endList.get(i).name);
System.out.printf("%10d", endList.get(i).trunTime);
System.out.println();
}
}
}
六、实验报告
计算机与软件工程学院
上机实验报告
（ 2021 - 2022学年 第1学期 ）
课程名称 操作系统
课程代码
任课教师
学生姓名
学号 专业
实验成绩
实验名称 基于优先数的时间片轮转调度算法调度处理模拟程序设计 实验地点
实验类型 设计 实验学时 4 实验日期 2021/11/22
★【注意】文档各种格式已经设置好并不得更改，填入内容即可
1.对进程调度的工作做进一步的理解。
2.了解进程调度的任务。
3.通过编程掌握基于优先数的时间片轮转调度算法具体实现过程。
1.实验任务
设计一个程序模拟实现基于优先数的时间片轮转调度算法调度处理
2.算法与程序设计
1）数据结构说明
定义一个PCB类，模拟进程控制块（PCB)，实例化一个PCB代表一个进程
利用Java LinkedList<E>泛型类，定义进程调度模拟中的各个链表队列，并储存其PCB
每个PCB具有属性
class PCB {
String name;//进程名
int startTime;//到达时间
int needTime;//要求运行时间
int priority;//优先数
int runTime;//已运行时间
int trunTime;//周转时间
}
用于表示储存的四个状态队列分别是
LinkedListPCB> noreList //未进入队列
LinkedList<PCB> readyList //就绪队列
LinkedList<PCB> runList //运行队列
LinkedList<PCB> endList //结束队列
设置int t控制时间片大小
2）数据输入（输入哪些数据、个数、类型、来源、输入方式）
未进入队列输入为键入，使用for循环输入{进程名，到达时间，要求运行时间，优先数}，实现对任意个进程的调度模拟
实验模拟数据为：
进程名 A B C D E F
到达时间 0 0 1 1 3 5
要求运行时间 4 5 5 4 4 4
优先数 3 2 0 10 5 2
就绪队列，运行队列，结束队列间的输入输出通过方法void readyInput(LinkedList<PCB> aList, LinkedList<PCB> bList, int u)实现
3）数据处理（正确绘制流程图，说明数据处理步骤）
4）数据输出（程序运行结果截图。图幅大小适当，能看清楚的情况下尽量小）
数据输入截图
未开始调度截图
调度过程中
调度完毕
通过这个实验，使我对Java（LinkedList）的一些方法的认识更为清晰，进程在状态队列间移动时，使用了remove（）删除某个元素后，因为删除元素后，后面的元素都往前移动了一位，而我的索引+1，导致出现越界。
同时使我对进程调度的认识更加清晰，了解到时间片轮转调度算法的具体实现过程，在完成实验的同时，编程能力也会有所提高。
1.操作系统：WINDOWS 7及以上
2.开发工具：Netbeans IDE 8.2
3.实验设备：PC