时间片轮转RR进程调度算法(华侨大学)

《操作系统》实验二内实验报告

作者:mo

实验题目时间片轮转RR进程调度算法

实验目的

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

实验内容

问题描述:

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

程序要求如下:

1)进程个数n;每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn;输入时间片大小q。

2)要求时间片轮转法RR调度进程运行,计算每个进程的周转时间,带权周转时间,并且计算所有进程的平均周转时间,带权平均周转时间;

3)输出:要求模拟整个调度过程,输出每个时刻的进程运行状态,如“时刻3:进程B开始运行”等等;

4)输出:要求输出计算出来的每个进程的周转时间,带权周转时间,所有进程的平均周转时间,带权平均周转时间。

[ 源程序 ]

程序结构:

Process.java

package com.RoundRobin;

/**

 * 功能:

 * 定义进程类

 * method:

 * 进程按到达时间排序

 * 进程 RR 时间片轮转法

 * @author Rain

 *

 */

class Process {

       private String name; //进程名

       private int arriveTime;       //到达时间

       private int serviceTime;     //服务时间

       private int finishTime;              //完成时间

       private int roundTime;              //周转时间

       private double weightroundTime;          //带权周转时间

       private double aveweightroundTime;    //     平均带权周转时间

       private double averoundTime; //平均带权周转时间

       private int temp;

       private boolean isAction;

       public Process() {

              name = "";

              arriveTime = 0;

              serviceTime = 0;

              finishTime = 0;

              roundTime = 0;

              weightroundTime = 0;

              averoundTime = 0;

              aveweightroundTime = 0;

              temp = 0;

              isAction = false;

       }

       public void setName(String name) {

              this.name = name;

       }

       public void setArriveTime(int arriveTime) {

              this.arriveTime = arriveTime;

       }

       public void setServiceTime(int serviceTime) {

              this.serviceTime = serviceTime;

              this.temp = serviceTime;

       }

       public void sort(Process[] a) { //对进程进行排序

              for (int j = 1; j < a.length; j++) {

                     Process b = a[j];

                     int temp = a[j].arriveTime;

                     int jj = j - 1;

                     while (jj >= 0) {

                            if (temp < a[jj].arriveTime) {

                                   a[jj + 1] = a[jj];

                                   jj--;

                            } else

                                   break;

                     }

                     a[jj + 1] = b;

              }//for

       }//sort

       /**

        *

        * @param a

        * @param q

        * 时间片轮转算法

        */

       public void RR(Process[] a, int q) {

              Queue aQueue = new Queue();

              aQueue.enqueue(0);

              int j;

              int i = 1;

              int time = a[0].finishTime;

              int count = 0;

              for (int m = 0; m < a.length; m++)

                     count += a[m].serviceTime;

              int temp = -1;

              while (!aQueue.isEmpty()) {

                     a[aQueue.front()].temp = a[aQueue.front()].temp - q;

                     if (a[aQueue.front()].temp >= 0) {

                            System.out.print("第"+time);

                            time = q + time;

                            a[aQueue.front()].finishTime = time;

                            System.out.println("到" + a[aQueue.front()].finishTime + "时间刻"+"进程"

                                          + a[aQueue.front()].name+"在运行");

                     }

                     if (a[aQueue.front()].temp < 0) {

                            System.out.print("第"+time);

                            time = a[aQueue.front()].temp + q + time;

                            a[aQueue.front()].finishTime = time;

                            System.out.println("到" + a[aQueue.front()].finishTime + "时间刻" + "进程"

                                          + a[aQueue.front()].name + "在运行");

                            a[aQueue.front()].temp = 0;

                     }

                     for (j = i; j < a.length; j++) {

                            if (a[j].arriveTime <= time) {

                                   a[j].isAction = true;

                                   aQueue.enqueue(j);

                                i++;

                            }

                            else continue;}   

                     if (a[aQueue.front()].temp== 0){

                               a[aQueue.front()].finishTime = time;

                                   if(aQueue.isEmpty() != true)

                                   {

                                          aQueue.dequeue();

                                   }

                                   }

                            else 

                            {

                                   temp=aQueue.front();

                                   aQueue.dequeue();

                                   aQueue.enqueue(temp);

                                   }

                                   }

              for(int jj=0; jj<a.length; jj++)

              {

                     a[jj].roundTime = a[jj].finishTime - a[jj].arriveTime;

                     a[jj].weightroundTime = (double)a[jj].roundTime / a[jj].serviceTime;

                     a[0].aveweightroundTime += a[jj].weightroundTime;

                     a[0].averoundTime += a[jj].roundTime;

              }

              a[0].aveweightroundTime = a[0].aveweightroundTime / a.length;

              a[0].averoundTime = a[0].averoundTime / a.length;

             

       }//RR

      

              /**

               * 打印结果

               * @param a

               *               

               *  */

       public void print(Process[] a) {

              System.out.println("进程名" + " " + "到达时间" + " " + "服务时间" + " " + "完成时间"

                            + " " + "周转时间" + " " + "带权周转时间");

              //DecimalFormat df = new DecimalFormat("#.00");

              for (int ii = 0; ii < a.length; ii++) {

                     System.out.println("  " + a[ii].name + "      " + a[ii].arriveTime

                                   + "       " + a[ii].serviceTime + "      "

                                   + a[ii].finishTime + "       " + a[ii].roundTime

                                   + "        " + Math.floor( a[ii].weightroundTime*100+0.5 )/100 );

              }

              System.out.println("RR算法的平均周转时间为:" + Math.floor( a[0].averoundTime*100+0.5 )/100 );

              System.out.println("RR算法的平均带权周转时间:"

                            + Math.floor( a[0].aveweightroundTime*100 + 0.5 )/100 );

       }//print

}

Queue.java

package com.RoundRobin;

import java.util.NoSuchElementException;

/**

 * 自定义队列来存储进程

 * 通过数组来实现队列

*

*/

class Queue {

       // 字段

       public static int[] data;

       // 队列的元素个数

       protected int size;

       // 队列头

       protected int head;

       // 队列尾

       public static int tail;

       // 无参数构造函数

       public Queue() {

              final int INITIAL_LENGTH = 100;

              data = new int[INITIAL_LENGTH];

              size = 0;

              head = 0;

              tail = -1;

       }

       // 队列元素个数方法

       public int size() {

              return size;

       }

       public boolean isEmpty() {

              return size == 0;

       }

       // 得到队列头元素

       public int front() {

              if (size == 0)

                     throw new NoSuchElementException();

              else return data[head];

       }

       // 进入队列enqueue()方法

       public void enqueue(int obj) {

              // 此时队列已经满

              if (size == data.length) {

                     int[] oldData = data;

                     data = new int[data.length * 2];

                     if(head == 0)

                     System.arraycopy(oldData, head, data, 0, oldData.length - head);

                     if (head > 0)

                            System.arraycopy(oldData, 0, data, head + 1, tail + 1);

                     head = 0;

                     tail = oldData.length - 1;

              }

              tail = (tail + 1) % data.length;

              size++;

              data[tail] = obj;

       }

       // 队列的元素出队

       public int dequeue() {

              if (size == 0)

                     throw new NoSuchElementException();

              int ele = data[head];

              // 循环队列

              //head++;

              head = (head + 1) % data.length;

              size--;

              return ele;

       }

}

RR.java

package com.RoundRobin;

import java.io.*;

import java.util.Scanner;

import com.RoundRobin.Process ;

public class RR {

       /**

        * @param args

        */

       public static void main(String[] args) {

              // TODO Auto-generated method stub

              System.out.println("\n--------模拟操作系统进程调度---- 时间片轮转法-----");

              int i = 0;

              String[] S1 = new String[20];

              try {

                     FileReader aFileReader = new FileReader("data.txt");

                     BufferedReader in = new BufferedReader(aFileReader);

                     String s = null;

                     while ((s = in.readLine()) != null) {

                            S1[i] = s;

                            i++;

                     }

                     aFileReader.close();

                     in.close();

              } catch (IOException ioe) {

                     System.out.println( ioe.getMessage() );

              }

             

              int choice=-1;

              while( true )

              {

                     System.out.println(" 1.开始或继续:");

                     System.out.println(" 0.退出。");

                     System.out.print(" 请输入选择:");

                     try{

                            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

                            String inputString = in.readLine();

                            choice = Integer.valueOf(inputString);

                            if(0 == choice){

                                   //System.exit(0);

                                   break ;

                            }

                            if(1 == choice){ 

                                   Process[] a = new Process[i];

                                   for (int ii = 0; ii < i; ii++) {

                                          a[ii] = new Process();

                                          String[] temp = S1[ii].split(" ");

                                          int j = 0;

                                          a[ii].setName( temp[j] );

                                          a[ii].setArriveTime( Integer.parseInt( temp[j + 1] ) );

                                          a[ii].setServiceTime( Integer.parseInt( temp[j + 2] ) );

                            }

                            Process test = new Process();

                         test.sort(a);

                            System.out.print("请输入时间片的大小:");

                            Scanner reader=new Scanner(System.in);

                            int q = reader.nextInt();

                            if( q <= 0 ){

                                   System.out.println("输入不合法!");

                                   break;

                            }

                            test.RR(a, q);

                            test.print(a);

                                  

                            }

                     }

                     catch (Exception e) {

                            // TODO: handle exception

                            System.out.println("输入有误!");

                     }//catch

                    

              }//while

             

       }//main end

}//class end 

 [ 程序运行效果 ]

接下图

相关推荐