当前位置：文档之家› 操作系统-先来先服务FCFS和短作业优先SJF进程调度算法

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

操作系统作业算法调

度报告

学院：

专业班级：

学生姓名：

学号：

报告题目：先来先服务和短作业优先算法

完成日期： 2016年10月25日星期二

先来先服务FCFS和短作业优先SJF进程调度算法

1、实验目的

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

2、实验内容

问题描述：

设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。

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

3、程序要求：

1）进程个数n；每个进程的到达时间T1, … ,T n和服务时间S1, … ,S n；选择算法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("到达时间 :");