【計算機操作系統】操作系統--時間片輪轉（RR）進程調度算法

實驗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）測試用例

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);

    }

}

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈