国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > 综合技术 > 【计算机操作系统】操作系统--时间片轮转(RR)进程调度算法

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

来源:程序员人生   发布时间:2017-03-07 08:18:00 阅读次数:4051次

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

1、 实验目的

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

2、 实验内容

问题描写:

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

3、 程序要求

1)进程个数n;每一个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn;输入时间片大小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);

    }

}


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生