程序员人生网站导航

【计算机操作系统】操作系统--时间片轮转（RR）进程调度算法

栏目：综合技术时间：2017-03-07 08:18:00

实验2 间片轮转RR进程调度算法

1、实验目的

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

2、实验内容

问题描写：

设计程序摹拟进程的时间片轮转RR调度进程。假定有n个进程分别在T₁,… ,T_n时刻到达系统，它们需要的服务时间分别为S₁,… ,S_n。分别利用不同的时间片大小q，采取时间片轮转RR进程调度算法进行调度，计算每一个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

3、程序要求：

1）进程个数n；每一个进程的到达时间T₁, … ,T_n和服务时间S₁, … ,S_n；输入时间片大小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);

    }

}

------分隔线----------------------------

上一篇 Leetcode 165 Compare Version Numbers

下一篇 php数据库操作--数据预处理、更新、删除

------分隔线----------------------------