操作系统 先来先服务FCFS和短作业优先SJF进程调度算法 java版

1、 实验目的

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 2、 试验内容

问题描述：

设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。 3、 程序要求：

1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；选择算法1-FCFS，2-SJF。

2）要求采用先来先服务FCFS和短作业优先SJF分别调度进程运行，计算每个进程的周转时间和带权周转时间，并且计算所有进程的平均周转时间和带权平均周转时间；

3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；

4）输出：要求输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。

4、 需求分析

(1) 输入的形式和输入值的范围 算法选择：FCFS-“1”，选SJF-“2” 真实进程数 各进程的到达时间 各进程的服务时间 (2) 输出的形式

模拟整个调度过程、周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。 (3) 程序所能达到的功能

输入进程个数Num，每个进程到达时间ArrivalTime[i]，服务时间ServiceTime[i]。采用先来先服务FCFS或者短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计Num个进程的平均周转时间和平均带权周转时间。 (4)测试用例

5、 调试分析

(1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析

1开始的时候没有判断进程是否到达，○导致短进程优先算法运行结果

错误，后来加上了判断语句后就解决了改问题。

2基本完成的设计所要实现的功能，总的来说，FCFS编写容易，SJF○

需要先找到已经到达的进程，再从已经到达的进程里找到进程服务时间最短的进程，再进行计算。

3根据我所写的FCFS和SJF算法，如果用户输入的数据没有按照到达○

时间的先后顺序，程序将出现问题？

解决办法：利用冒泡排序，根据达到时间的先后顺序进行排序。

4从第二个进程开始，○算法需要判断已在等待的进程，如果分批进行

判断与处理，规律性不强，代码很难实现？

解决办法：通过牺牲效率的方式，进行一个个判断与处理。为此，引入变量当前时间、用零标记已处理过进程等方式，实现已在等待进程的判断与判断。 (2)算法的改进设想

改进：即使用户输入的进程到达时间没有先后顺序也能准确的计算出结果。（就是再加个循环，判断各个进程的到达时间先后，组成一个有序的序列） (3)经验和体会

通过本次实验，深入理解了先来先服务和短进程优先进程调度算法的

思想，培养了自己的动手能力，通过实践加深了记忆。 6、 测试结果 (1)FIFS算法:

文件流输入算法选择,进程个数,进程的达到时间和服务时间

输出

(2)FIFS算法:

文件流输入算法选择,进程个数,进程的达到时间和服务时间

输出

7、附录(java)

package experiment;

import java.io.BufferedInputStream; import java.io.FileInputStream;

import java.io.FileNotFoundException; import java.text.DecimalFormat; import java.util.Scanner;

//先来先服务FCFS和短作业优先SJF进程调度算法 public class A_FJFS_SJF {

// 声明变量

// 允许的最大进程数

public static int MaxNum = 100; // 真正的进程数

public static int realNum; // 当前时间

public static int NowTime;

// 各进程的达到时间

public static int ArrivalTime[] = new int[MaxNum]; // 各进程的服务时间

public static int ServiceTime[] = new int[MaxNum]; // 各进程的服务时间(用于SJF中的临时数组)

public static int ServiceTime_SJF[] = new int[MaxNum]; // 各进程的完成时间

public static int FinishTime[] = new int[MaxNum]; // 各进程的周转时间

public static int WholeTime[] = new int[MaxNum]; // 各进程的带权周转时间

public static double WeightWholeTime[] = new double[MaxNum]; // FCFS和SJF的平均周转时间

public static double AverageWT_FCFS, AverageWT_SJF; // FCFS和SJF的平均带权周转时间

public static double AverageWWT_FCFS, AverageWWT_SJF; // FCFS中的周转时间总和

public static int SumWT_FCFS = 0; // FCFS中的带权周转时间总和

public static double SumWWT_FCFS = 0; // SJF中的周转时间总和

public static int SumWT_SJF = 0; // SJF中的带权周转时间总和

public static double SumWWT_SJF = 0; public static Scanner stdin;

public static void main(String args[]) throws FileNotFoundException {

// 从文件中输入数据

BufferedInputStream in = new BufferedInputStream(new FileInputStream( \"./file/01\")); System.setIn(in);

stdin = new Scanner(System.in);

int choice = stdin.nextInt(); // 算法选择：FCFS-“1”，选SJF-“2” realNum = stdin.nextInt(); //真实进程数

for (int i = 0; i < realNum; i++) { //各进程的到达时间 ArrivalTime[i] = stdin.nextInt(); }

for (int j = 0; j < realNum; j++) { //各进程的服务时间 ServiceTime[j] = stdin.nextInt(); ServiceTime_SJF[j] = ServiceTime[j]; }

stdin.close();

// 算法选择：1-FCFS，2-SJF； if (choice == 1) { FCFS();

} else if (choice == 2) { SJF(); } else {

System.out.println(\"算法选择错误\"); } }

//先来先服务FCFS进程调度算法 public static void FCFS() {

// 到达时间的冒泡排序，完成时间随之变动（使先到者排在前面，后到者排在后面）

sort();

// 计算每个进程的完成时间、周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间

FinishTime[0] = ArrivalTime[0] + ServiceTime[0]; WholeTime[0] = ServiceTime[0];

WeightWholeTime[0] = (double) WholeTime[0] / ServiceTime[0]; AverageWT_FCFS = AverageWWT_FCFS = 0;

AverageWT_FCFS = AverageWT_FCFS + WholeTime[0];

AverageWWT_FCFS = AverageWWT_FCFS + WeightWholeTime[0];

for (int j = 1; j < realNum; j++) { //从第二个进程开始计算完成时间、周转时间、带权周转时间

if (ArrivalTime[j] > FinishTime[j-1]) { //该进程是否在等待 FinishTime[j] = ArrivalTime[j] + ServiceTime[j]; WholeTime[j] = ServiceTime[j]; } else { //该进程已在等待

FinishTime[j] = FinishTime[j-1] + ServiceTime[j];

WholeTime[j] = FinishTime[j-1] - ArrivalTime[j] + ServiceTime[j]; }

WeightWholeTime[j] = (double)WholeTime[j] / ServiceTime[j]; }

for (int i = 0; i < realNum; i++) { //计算总周转时间、总带权周转时间 SumWT_FCFS = SumWT_FCFS + WholeTime[i];

SumWWT_FCFS = SumWWT_FCFS + WeightWholeTime[i]; }

AverageWT_FCFS = (double)SumWT_FCFS / realNum; //平均周转时间

AverageWWT_FCFS = (double)SumWWT_FCFS / realNum; //平均带权周转时间

// 输出每个进程的完成时间、周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间 outPUT(1); }

//短作业优先SJF进程调度算法 public static void SJF() {

// 到达时间的冒泡排序，完成时间随之变动（使先到者排在前面，后到者排在后面）

sort();

int min = 0;

NowTime = ArrivalTime[0] + ServiceTime[0];// 计算第一次的NowTIme FinishTime[0] = ServiceTime[0];// 计算第一个进程的完成时间 ServiceTime_SJF[0]=1000;//赋初值。 int allin = 0, j, k;

for (int i = 1; i < realNum; i++)// 进入循环，从第二个到达的进程开始 {

k = 1; min = 0;

if (allin == 0)// 找到已经到达的进程个数 {

for (j = 0; ArrivalTime[j] <= NowTime && j < realNum ; j++) { if (j >= realNum) { allin = 1; } } } else {

j = realNum; }

j = j - 1;// j是已经到达的进程数（减去已经计算过的第一个进程）

while (k <= j)// 从已经到达的进程里找到服务时间最短的进程 {

if(ServiceTime_SJF[k]==0)//进程的服务时间如果等于0，则跳过该进程 k++; else {

if(ServiceTime_SJF[min]>ServiceTime_SJF[k])//比较，找到服务时间最短的进程

min=k; k++;

}

}

ServiceTime_SJF[min] = 0;// 找完后置零，便于下一次循环时跳过 NowTime += ServiceTime[min];// 累加当前时间 FinishTime[min] = NowTime;// 完成时间 }

for (int i = 0; i < realNum; i++)// 计算周转时间，带权周转时间，总的周转时间和总的带权周转时间 {

WholeTime[i] = FinishTime[i] - ArrivalTime[i];

WeightWholeTime[i] = (double)WholeTime[i] / ServiceTime[i]; SumWT_SJF += WholeTime[i];

SumWWT_SJF += WeightWholeTime[i]; }

AverageWT_SJF = (double)SumWT_SJF / realNum;// 平均周转时间

AverageWWT_SJF = (double)SumWWT_SJF / realNum;// 平均带权周转时间

// 输出每个进程的完成时间、周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间 outPUT(2); }

// 到达时间的冒泡排序，完成时间随之变动（使先到者排在前面，后到者排在后面） public static void sort() { int temp1 = 0; int temp2 = 0;

for (int i = 0; i < realNum - 1; i++) { for (int j = 0; j < realNum - 1; j++) {

if (ArrivalTime[j] > ArrivalTime[j + 1]) { temp1 = ArrivalTime[j]; temp2 = ServiceTime[j];

ArrivalTime[j] = ArrivalTime[j + 1]; ServiceTime[j] = ServiceTime[j + 1]; ArrivalTime[j + 1] = temp1; ServiceTime[j + 1] = temp2; } } } }

// 输出每个进程的完成时间、周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间

// a=1:输出FCFS结果 a=2:输出SJF结果 public static void outPUT(int a) { int k;

DecimalFormat format = new DecimalFormat(\"#.00\"); System.out.print(\"到达时间 :\"); for (k = 0; k < realNum; k++) {

System.out.print(ArrivalTime[k] + \" \"); }

System.out.println(\"\");

System.out.print(\"服务时间 :\"); for (k = 0; k < realNum; k++) {

System.out.print(ServiceTime[k] + \" \"); }

System.out.println(\"\");

System.out.print(\"完成时间 :\"); for (k = 0; k < realNum; k++) {

System.out.print(FinishTime[k] + \" \"); }

System.out.println(\"\");

System.out.print(\"周转时间 :\"); for (k = 0; k < realNum; k++) {

System.out.print(WholeTime[k] + \" \"); }

System.out.println(\"\");

System.out.print(\"带权周转时间:\"); for (k = 0; k < realNum; k++) {

System.out.print(format.format(WeightWholeTime[k]) + \" \"); }

System.out.println(\"\");

if(a==1){

System.out.println(\"平均周转时间 :\" + format.format(AverageWT_FCFS));

System.out.println(\"平均带权周转时间:\" + format.format(AverageWWT_FCFS)); }else{

System.out.println(\"平均周转时间 :\" + format.format(AverageWT_SJF));

System.out.println(\"平均带权周转时间:\" + format.format(AverageWWT_SJF)); }

// 模拟整个调度过程，输出每个时刻的进程运行状态

System.out.println(\"时刻\" + ArrivalTime[0] + \":进程\" + 1 + \"开始运行\");

}

}

for (int i = 1; i < realNum; i++) {

System.out.println(\"时刻\" + FinishTime[i - 1] + \":进程\" + (i + 1) + \"开始运行\"); }