【笔记】时间片轮转 RR 进程调度算法（Java 实现）

 时间片轮转（Round-Robin）调度算法是操作系统一种比较公平的进程调度的方式，这种方式使得就绪队列上的所有进程在每次轮转时都可以运行相同的一个时间片。

基本原理

 算法实现原理是，按进程到达顺序（FCFS 原则）将进程依次加入就绪队列当中，然后将 CPU 分配给位于队首的进程，确定一个时间片，让该进程执行一个时间片。当该进程执行时间到时，该进程可能已经执行完毕（可能在时间片未到时就以及执行完毕），或者未执行完毕，如果是前者只需将进程弹出队列即可，如果是后者则将该进程加入队尾，并将 CPU 分配给新的队首进程，如此循环。

进程切换时机

 进程在执行时分为两种情况

• 在该时间片内进程执行完毕，这种情况调度程序将立即把该进程弹出队列，并把 CPU 分配给新的队首进程
• 在该时间片内进程未执行完毕，调度程序将立即中断该进程执行，把该进程加入队尾，并将 CPU 分配给新的队首进程

时间片大小的确定

 在 RR 算法中，时间片的大小直接影响了系统的性能。

• 时间片过小，有利于短作业，但是会频繁地切换进程，增加了系统的开销，影响性能。
• 时间片过大，算法退化成 FCFS 算法，如果某个短作业进程之前的进程都是长作业，将导致后面的短作业进程长时间等待。

有关的计算

• 周转时间 = 进程完成时间 - 进程到达时间
• 带权周转时间 = 进程周转时间 / 进程实际运行时间
• 平均周转时间 = （进程1周转时间 + ... + 进程n周转时间）/ n
• 平均带权周转时间 = （进程1带权周转时间 + ... + 进程n带权周转时间）/ n

实现

package cn.vecrates.operatingSystem;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class RR {
    private int mProcessCount; //进程数
    private Queue<Process> mReadyQueue; //就绪队列，存放“待运行的进程
    private Queue<Process> mUnreachQueue; //存放“到达时间未到的进程”
    private int mTimeSlice; //时间片

    private Queue<Process> mExecutedQueue; //执行完毕的进程队列
    private double mTotalWholeTime = 0.0;
    private double mTotalWeightWholeTime = 0.0;

    private RR(int processCount, Queue<Process> processQueue, int timeSlice) {
        this.mProcessCount = processCount;
        this.mUnreachQueue = processQueue;
        mReadyQueue = new LinkedBlockingQueue<>();
        this.mTimeSlice = timeSlice;
        mExecutedQueue = new LinkedList<>();
    }

    /**
     * RR 算法实现
     */
    public void RRAlgorithm() {
        mReadyQueue.add(mUnreachQueue.poll());
        Process currProcess = mReadyQueue.poll();
        //第一个进程执行
        int currTime = executeProcess(currProcess, 0);

        while(!mReadyQueue.isEmpty() || !mUnreachQueue.isEmpty()) {
            //把所有“到达时间”达到的进程加入运行队列头部
            while(!mUnreachQueue.isEmpty()) {
                if(mUnreachQueue.peek().getArrivalTime() <= currTime) {
                    mReadyQueue.add(mUnreachQueue.poll());
                } else {
                    break;
                }
            }

            if(currProcess.getRemainServiceTime() > 0) mReadyQueue.add(currProcess);
            //运行队列不为空时
            if(!mReadyQueue.isEmpty()) {
                currProcess = mReadyQueue.poll();
                currTime = executeProcess(currProcess, currTime);
            } else {
                //当前没有进程执行，但还有进程为到达，时间直接跳转到到达时间
                currTime = mUnreachQueue.peek().getArrivalTime();
            }
        }
    }

    private int executeProcess(Process currProcess, int currTime) {
        if(currProcess.getRemainServiceTime() - mTimeSlice <= 0) {
            //当前进程在这个时间片内能执行完毕
            showExecuteMessage(currTime, currTime += currProcess.getRemainServiceTime(), currProcess.getName());
            currProcess.setFinishTime(currTime);
            currProcess.setRemainServiceTime(0);
            //对周转时间等进行计算
            calculeteWholeTime(currProcess);
            calculateWeightWholeTime(currProcess);
            mTotalWholeTime += currProcess.getWholeTime();
            mTotalWeightWholeTime += currProcess.getWeightWholeTime();
            mExecutedQueue.add(currProcess);
        } else {
            //不能执行完毕
            showExecuteMessage(currTime, currTime += mTimeSlice, currProcess.getName());
            currProcess.setRemainServiceTime(currProcess.getRemainServiceTime() - mTimeSlice);
        }
        return currTime;
    }

    /**
     * 计算周转时间
     * @param process
     */
    private void calculeteWholeTime(Process process) {
        process.setWholeTime(process.getFinishTime() - process.getArrivalTime());
    }

    /**
     * 计算带权周转时间
     * @param process
     */
    private void calculateWeightWholeTime(Process process) {
        process.setWeightWholeTime(process.getWholeTime() / (double)process.getServiceTime());
    }

    private void showExecuteMessage(int startTime, int endTime, String name) {
        System.out.println(startTime + "～" + endTime + "：【进程" + name + "】运行");
    }

    public void showResult() {
        System.out.print("进程名\t");
        System.out.print("周转时间\t");
        System.out.println("带权周转时间\t");
        Process process ;
        while(!mExecutedQueue.isEmpty()) {
            process = mExecutedQueue.poll();
            System.out.print("进程" + process.getName() + "\t");
            System.out.print("\t" + process.getWholeTime() + "\t");
            System.out.println("\t" + process.getWeightWholeTime() + "\t");
        }
        System.out.println("平均周转时间：" + mTotalWholeTime / (double) mProcessCount);
        System.out.println("平均带权周转时间：" + mTotalWeightWholeTime / (double) mProcessCount);
    }

    public static void printAll(Queue<Process> queue) {
        System.out.print("进程名\t");
        System.out.print("到达时间\t");
        System.out.println("服务时间\t");
        Process process = null;
        while (!queue.isEmpty()){
            process = queue.poll();
            System.out.print("进程" + process.getName() + "\t");
            System.out.print("\t" + process.getArrivalTime() + "\t");
            System.out.println("\t" + process.getServiceTime() + "\t");
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入进程个数：");
        int processCount = scanner.nextInt();
        if(processCount < 1) return;
        Queue<Process> queue = new LinkedBlockingQueue<>();
        System.out.println("依次输入每个进程的到达时间（按到达顺序）：");
        for(int i=0; i<processCount; i++) {
            Process process = new Process((char)(i + 65) + "");
            process.setArrivalTime(scanner.nextInt());
            queue.add(process);
        }
        System.out.println("依次输入每个进程的服务时间（按到达顺序）：");
        for(int i=0; i<processCount; i++) {
            Process process = queue.poll();
            int time = scanner.nextInt();
            process.setServiceTime(time);
            process.setRemainServiceTime(time);
            queue.add(process);
        }

        System.out.println("输入时间片大小");
        int timeSlice = scanner.nextInt();

        RR rr = new RR(processCount, queue, timeSlice);

        System.err.println("*******************进程情况*****************");
        Thread.sleep(1000);
        printAll(new LinkedBlockingQueue<>(queue));
        Thread.sleep(1000);

        System.err.println("******************运行过程*****************");
        Thread.sleep(1000);
        rr.RRAlgorithm();
        Thread.sleep(1000);

        System.err.println("*******************运行结果*****************");
        Thread.sleep(1000);
        rr.showResult();
    }

}

//进程
class Process {
    private String name;
    private int arrivalTime; //到达时间
    private int serviceTime; //服务时间
    private int remainServiceTime; //还需要服务的时间
    private int finishTime; //完成时间
    private int wholeTime; //周转时间
    private double weightWholeTime; //带权周转时间

    public int getRemainServiceTime() {
        return remainServiceTime;
    }

    public void setRemainServiceTime(int remainServiceTime) {
        this.remainServiceTime = remainServiceTime;
    }

    public Process(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getArrivalTime() {
        return arrivalTime;
    }

    public void setArrivalTime(int arrivalTime) {
        this.arrivalTime = arrivalTime;
    }

    public int getServiceTime() {
        return serviceTime;
    }

    public void setServiceTime(int serviceTime) {
        this.serviceTime = serviceTime;
    }

    public int getFinishTime() {
        return finishTime;
    }

    public void setFinishTime(int finishTime) {
        this.finishTime = finishTime;
    }

    public int getWholeTime() {
        return wholeTime;
    }

    public void setWholeTime(int wholeTime) {
        this.wholeTime = wholeTime;
    }

    public double getWeightWholeTime() {
        return weightWholeTime;
    }

    public void setWeightWholeTime(double weightWholeTime) {
        this.weightWholeTime = weightWholeTime;
    }
}

运行结果当时间片为 1 时：

时间片为 4 时：