计算机操作系统 — 四种调度算法java篇
大家好！我是小笙！国庆作业，老师给我们留下了四道算法题，今天记录一下！
1.先来先服务FCFS
2.短作业优先SJF
3.高相应比优先HRRN
4.时间片大小的确定RR
四种调度算法
任务具体要求
我们需要计算完成时间,周转时间,带权周转时间
任务概念分析
完成时间
进程(A,B,C,D,E)完成各自进程服务所需要的时间被称为完成时间即进程结束的时间节点
周转时间
从作业被提交给系统开始，到作业完成为止这段时间间隔
周转时间 = 作业(进程)完成时间 - 作业(进程)到达时间
带权周转时间
作业的周转时间与系统为它提供服务的时间之比，反映作业（或进程）长短问题。带权周转时间越大，作业（或进程）越短；带权周转时间越小，作业（或进程）越长。
带权周转时间 = 作业(进程)周转时间 / 作业(进程)服务时间
四种算法分析
1.先来先服务FCFS
FCFS是一种非抢占式调度
概念
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。
优缺点
FCFS算法简单易行，是一种非抢占式策略，但性能却不大好
有利于长作业以及CPU繁忙的作业；不利于短作业以及I/O繁忙的作业
2.短作业优先SJF
SJF是一种非抢占式调度
概念
SJF算法是以进入系统的作业所要求的CPU时间为标准，是指对短作业或者短进程优先调度的算法，将每个进程与其估计运行时间进行关联选取估计计算时间最短的作业投入运行。
优缺点
SJF的平均作业时间比FCFS要小，故它的调度性能比FCFS好，算法易于实现
但效率不高，主要弱点是忽视了作业等待时间，会出现饥饿现象。
3.高响应比优先HRRN
响应比 =（等待时间+要求服务时间）/ 要求服务时间
概念
高响应比优先调度算法（Highest Response Ratio Next）是一种对CPU中央控制器响应比的分配的一种算法。
HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。
基本思想
短作业优先调度算法 + 动态优先权机制
既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。
4.时间片大小的确定RR
概念
时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称RR调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
进程切换时机
进程在执行时分为两种情况
- 在该时间片内进程执行完毕，这种情况调度程序将立即把该进程弹出队列，并把 CPU 分配给新的队首进程
- 在该时间片内进程未执行完毕，调度程序将立即中断该进程执行，把该进程加入队尾，并将 CPU 分配给新的队首进程
时间片大小的确定
在 RR 算法中，时间片的大小直接影响了系统的性能。
- 时间片过小，有利于短作业，但是会频繁地切换进程，增加了系统的开销，影响性能。
- 时间片过大，算法退化成 FCFS 算法，如果某个短作业进程之前的进程都是长作业，将导致后面的短作业进程长时间等待。
接下来就是程序代码的讲述，这也是大家最想了解的，毕竟理论这么的枯燥，待我慢慢述来~
主体框架
菜单流程图
代码显示
主函数
public static void main(String[] args) {
String processName[]; // 进程名
int[]arrTime; // 对象到达时间
int[]runLength; // 对象执行长度
Scanner sc = new Scanner(System.in);
while(true){
/**
* 初始化一些参数
*/
System.out.println("先生们/女士们,请问你需要使用几个进程？");
int ProcessNum = sc.nextInt(); // ProcessNum 进程数
if(ProcessNum <= 1){
System.out.println("先生/女士，你觉得你的输入好嘛~~");
break;
}
arrTime = new int[ProcessNum]; // 对象到达时间
runLength = new int[ProcessNum]; // 对象执行长度
processName = new String[ProcessNum];
Process.setCount(ProcessNum);
/**
* 进程的录入
*/
System.out.println("********************************************");
System.out.println("录入开始!");
while(ProcessNum > 0){
ProcessNum--;
System.out.println("请输入进程名,到达时间,执行长度!(中间用空格间隔)");
processName[Process.getCount()-1-ProcessNum] = sc.next();
arrTime[Process.getCount()-1-ProcessNum] = sc.nextInt();
runLength[Process.getCount()-1-ProcessNum] = sc.nextInt();
new Process(processName[Process.getCount()-1-ProcessNum],arrTime[Process.getCount()-1-ProcessNum],runLength[Process.getCount()-1-ProcessNum]);
// System.out.println(new Process(processName[Process.getCount()-1-ProcessNum],arrTime[Process.getCount()-1-ProcessNum],runLength[Process.getCount()-1-ProcessNum]).toString());
}
sort(processName,arrTime,runLength); // 排序算法,根据进程到达时间来进行排序
// System.out.println(processName[0]+" "+arrTime[0]+" "+runLength[0]);
// System.out.println(processName[Process.getCount()-1]+" "+arrTime[Process.getCount()-1]+" "+runLength[Process.getCount()-1]);
System.out.println("录入结束!");
System.out.println("********************************************");
/**
* 调度算法的选择
* 1.先来先服务FCFS
* 2.短作业优先SJF
* 3.高相应比优先HRRN
* 4.时间片大小的确定RR
*/
while(true){
System.out.println("先生们/女士们,请问你想要使用哪种算法？");
System.out.println("1.先来先服务FCFS");
System.out.println("2.短作业优先SJF");
System.out.println("3.高相应比优先HRRN");
System.out.println("4.时间片大小的确定RR");
System.out.println("0.退出");
int num = sc.nextInt(); // 记录用户的选择
if(num == 0) break;
switch(num){
case 1: Fcfs(processName,arrTime,runLength);
break;
case 2: Sjf(processName,arrTime,runLength);
break;
case 3: Hrrn(processName,arrTime,runLength);
break;
case 4: System.out.println("先生们/女士们,请输入时间片~~");
int timeSlice = sc.nextInt(); // 时间片的记录
Rr(processName,arrTime,runLength,timeSlice);
break;
default:
System.err.println("先生们/女士们,输入错误哦!");
}
}
System.out.println("********************************************");
}
进程Process类
// 创建进程
class Process{
private String name; // 进程名
private int arriveTime; // 到达时间
private int runtimeLength; // 执行长度
private static int count = 0; // 进程数目
public Process(String name,int arriveTime,int runtimeLength){
this.arriveTime = arriveTime;
this.name = name;
this.runtimeLength = runtimeLength;
}
public static void setCount(int count) {
Process.count = count;
}
public static int getCount() {
return count;
}
public String getName() {
return name;
}
public double getArriveTime() {
return arriveTime;
}
public int getRuntimeLength() {
return runtimeLength;
}
@Override
public String toString() {
return "ProcessName: "+getName()+" ProcessTime: "+getArriveTime()+" ProcessLength: "+getRuntimeLength();
}
}
五大算法
为啥这里称为五大算法，因为在计算四大调度算法的时候，发现排序对于这些算法的实现有很大的帮助！所以我这里称为五大算法
排序算法
排序的目的
为了简便以下四个调度算法
到达时间： 快 ------- 慢
相同到达时间下，服务时间 短 ------ 长
/**
* 排序算法,根据进程到达时间来进行排序
*/
public static void sort(String[]processName,int[]arrTime,int[]runLength){
String turn;
int temp;
for(int i=0;i<arrTime.length-1;i++){
for(int j=i+1;j<arrTime.length;j++){
if(arrTime[i]>arrTime[j]){ // 到达时间排序
// 进程名交换
turn = processName[i];
processName[i] = processName[j];
processName[j] = turn;
// 进程到达时间交换
temp = arrTime[i];
arrTime[i] = arrTime[j];
arrTime[j] = temp;
// 进程长度的交换
temp = runLength[i];
runLength[i] = runLength[j];
runLength[j] = temp;
}else if(arrTime[i]==arrTime[j]&&runLength[i]>runLength[j]){ // 解决到达时间相同,服务时间优先级问题
// 进程名交换
turn = processName[i];
processName[i] = processName[j];
processName[j] = turn;
// 进程到达时间交换
temp = arrTime[i];
arrTime[i] = arrTime[j];
arrTime[j] = temp;
// 进程长度的交换
temp = runLength[i];
runLength[i] = runLength[j];
runLength[j] = temp;
}
}
}
}
1.先来先服务调度算法FCFS 非抢占式
这个算法很简单，就是遍历进程，就可以计算出 完成时间 周转时间 带权周转时间
// 解决进程进程之间的等待 例如：A进程结束了，但是其他进程都没到来，就是这段时间的等待时间
public static void Fcfs(String[]processName,int[]arrTime,int[]runLength){
int sum = arrTime[0]; // 时间轴，记录经过的时间
int[] completeTime = new int[arrTime.length]; // 完成时间
int[] turnaroundTime = new int[arrTime.length]; // 周转时间
double[] weightedTurnaroundTime = new double[arrTime.length]; // 带权周转时间
// 逻辑运算
for(int i=0;i<arrTime.length;i++){
if(i > 0 && arrTime[i] > sum){ // 解决进程进程之间的等待
sum += arrTime[i] - sum;
}
sum += runLength[i];
completeTime[i] = sum;
turnaroundTime[i] = completeTime[i] - arrTime[i];
weightedTurnaroundTime[i] = turnaroundTime[i]*1.0/runLength[i];
}
// 显示数据
show(processName,arrTime,runLength,completeTime,turnaroundTime,weightedTurnaroundTime);
}
2.短作业（进程）优先调度算法SJF/SPF 非抢占式
算法思路
1.判断并且比较到达的进程中的进程服务时间 index记录服务时间最短的数字的下标
2.判断index是否为-1 来判断是不是进程处在等待状态 （解决进程进程之间的等待）
3.如果index不为-1则让该进程运行，记录下改进程的完成时间，周转时间，带权周转时间
4.最后显示数据
public static void Sjf(String[]processName,int[]arrTime,int[]runLength){
int sum = arrTime[0]; // 时间轴
int minRunLength = Integer.MAX_VALUE ; // 整数最大值
int count = arrTime.length ; // 记录进程结束判断
boolean[] processFlag = new boolean[arrTime.length]; // 记录进程是否完成
int[] completeTime = new int[arrTime.length]; // 完成时间
int[] turnaroundTime = new int[arrTime.length]; // 周转时间
double[] weightedTurnaroundTime = new double[arrTime.length]; // 带权周转时间
// 逻辑运算
while(count > 0){ // 判断有无全部进程完成
int index = -1; // 记录最小服务长度的进程的服务时间的下标
minRunLength = Integer.MAX_VALUE; // 当多个进程到达时，记录最小服务长度的进程的服务时间
for(int i=0;i<arrTime.length;i++){
// 该进程未完成 该进程已经到达 服务时间比之前的进程短
if(processFlag[i] == false && arrTime[i] <= sum && runLength[i] < minRunLength) {
minRunLength = runLength[i];
index = i; // 记录下标，好整活~
}
}
if(index == -1){ // 解决进程进程之间的等待
for(int i=1;i<arrTime.length;i++){
if(processFlag[i] == false){
sum = arrTime[i];
break;
}
}
}else{
processFlag[index] = true;
sum += runLength[index];
completeTime[index] = sum;
turnaroundTime[index] = completeTime[index] - arrTime[index];
weightedTurnaroundTime[index] = turnaroundTime[index]*1.0/runLength[index];
count--;
}
}
// 显示数据
show(processName,arrTime,runLength,completeTime,turnaroundTime,weightedTurnaroundTime);
}
3.高响应比优先调度算法HRRN
类比于算法二：短作业（进程）优先调度算法SJF/SPF
我这里再加一张思路流程图，方便大家理解!!
public static void Hrrn(String[]processName,int[]arrTime,int[]runLength){
int sum = arrTime[0]; // 时间轴
double maxPriority = Integer.MIN_VALUE; // 整数最小值
int count = arrTime.length; // 记录进程结束判断
boolean[] processFlag = new boolean[arrTime.length]; // 记录进程是否完成
int[] completeTime = new int[arrTime.length]; // 完成时间
int[] turnaroundTime = new int[arrTime.length]; // 周转时间
double[] weightedTurnaroundTime = new double[arrTime.length]; // 带权周转时间
// 逻辑运算
while(count > 0) { // 判断有无全部进程完成
int index = -1; // 记录高响应的进程下标
maxPriority = Integer.MIN_VALUE; // 记录高响应比
for(int i=0;i<arrTime.length;i++){
// 进程是否完成 进程是否已经达到 高响应比是否比之前的进程的大
if(processFlag[i] == false && arrTime[i] <= sum && ((sum-arrTime[i])+runLength[i])*1.0/runLength[i] > maxPriority) {
maxPriority = ((sum-arrTime[i])+runLength[i])*1.0/runLength[i] ;
index = i; // 记录下标，好整活~
}
}
if(index == -1){ // 解决进程进程之间的等待
for(int i=1;i<arrTime.length;i++){
if(processFlag[i] == false){
sum = arrTime[i];
break;
}
}
}else{
processFlag[index] = true;
sum += runLength[index];
completeTime[index] = sum;
turnaroundTime[index] = completeTime[index] - arrTime[index];
weightedTurnaroundTime[index] = turnaroundTime[index]*1.0/runLength[index];
count--;
}
}
// 显示数据
show(processName,arrTime,runLength,completeTime,turnaroundTime,weightedTurnaroundTime);
}
4.时间片大小的确定调度算法RR 抢占式
public static void Rr(String[]processName,int[]arrTime,int[]runLength,int q){ // q 时间片大小
int sum = arrTime[0]; // 记录完成时间
int maxLength; // 记录最大等待时间
int[]ReRunLength = (int[])runLength.clone(); // 克隆runLength,用来记录剩余运行长度
int []lastRun = new int[arrTime.length]; // 运行的进程中最后一个时间片节点记录
boolean[]isEnter= new boolean[arrTime.length]; // 是否进入进程等待
int count = arrTime.length; // 记录进程结束判断
boolean[] processFlag = new boolean[arrTime.length]; // 记录该进程是否完成
int[] completeTime = new int[arrTime.length]; // 完成时间
int[] turnaroundTime = new int[arrTime.length]; // 周转时间
double[] weightedTurnaroundTime = new double[arrTime.length]; // 带权周转时间
// 逻辑运算
while(count > 0){ // 判断有无全部进程完成
for(int i=0;i<arrTime.length;i++){ // 判断是否有新进程进入
if(arrTime[i] <= sum && isEnter[i] == false){ // 满足新进程进入 && 该进程之前未进入
if(ReRunLength[i]>q) { // 判断该进程是否可以用完该时间片
isEnter[i] = true;
sum += q;
ReRunLength[i] -= q;
lastRun[i] = sum;
}else if(ReRunLength[i]<=q){
isEnter[i] = true;
sum += ReRunLength[i];
ReRunLength[i] = 0;
processFlag[i] = true;
count--;
lastRun[i] = sum;
}
}
}
int index = -1;
maxLength = 0; // 记录离当前的时间轴的间隔时长
for(int i=0;i<arrTime.length;i++){ // 判断下一个时间片的运行进程
if(arrTime[i] <= sum && processFlag[i] == false && (sum-lastRun[i] >= maxLength)){
maxLength = sum-lastRun[i];
index = i;
}
}
if(index != -1){
if(ReRunLength[index]>q) {
sum += q;
ReRunLength[index] -= q;
lastRun[index] = sum;
}else if(ReRunLength[index]<=q){
sum += ReRunLength[index];
ReRunLength[index] = 0;
processFlag[index] = true;
count--;
lastRun[index] = sum;
}
}else{
sum += 1;
}
}
// 记录完成时间 周转时间 带权周转时间
for(int i=0;i<arrTime.length;i++){
completeTime[i] = lastRun[i];
turnaroundTime[i] = completeTime[i] - arrTime[i];
weightedTurnaroundTime[i] = turnaroundTime[i]*1.0/runLength[i];
}
//显示数据
show(processName,arrTime,runLength,completeTime,turnaroundTime,weightedTurnaroundTime);
}
显示函数
public static void show(String[]processName,int[]arrTime,int[]runLength,int[]completeTime,int[]turnaroundTime,double[]weightedTurnaroundTime){
// show data
double average = 0;
System.out.print(" 进程名:\t\t");
for(int i=0;i<arrTime.length;i++) System.out.print(processName[i]+"\t");
System.out.println("平均");
System.out.print(" 到达时间:\t\t");
for(int i=0;i<arrTime.length;i++) System.out.print(arrTime[i]+"\t");
System.out.println();
System.out.print(" 服务时间:\t\t");
for(int i=0;i<arrTime.length;i++) System.out.print(runLength[i]+"\t");
System.out.println();
System.out.print(" 完成时间:\t\t");
for(int i=0;i<arrTime.length;i++){
average += completeTime[i];
System.out.print(completeTime[i]+"\t");
}
System.out.println(average/Process.getCount());
average = 0;
System.out.print(" 周转时间:\t\t");
for(int i=0;i<arrTime.length;i++){
average += turnaroundTime[i];
System.out.print(turnaroundTime[i]+"\t");
}
System.out.println(average/Process.getCount());
average = 0;
System.out.print("带权周转时间:\t\t");
for(int i=0;i<arrTime.length;i++){
average += weightedTurnaroundTime[i];
System.out.print(String.format("%.1f",weightedTurnaroundTime[i])+"\t");
}
System.out.println(String.format("%.2f",average/Process.getCount()));
}