操作系统：多级反馈队列调度算法模拟（Java实现）_多级反馈队列调度算法的模拟实现_NAREN_BLOG的博客

三、实现思路：

采用自定义类Progress实例化进程对象，组成进程数组；
初始化三个优先级从高到低（时间片长：2、4、8）的队列；
按照：
首次加入的进程入最高优先级队列尾等待；
某队列内时间片完而进程还没结束就立即调入次级优先级队列尾等待继续运行；
只要有进程进入高优先级队列内，便对低优先级队列中的进程进行抢占式运行；

的思想每一秒对每个队列内的进程具有的进程标识符、到达时间、运行时间、仍需运行时间（方便显示）等属性进行更新和输出，以此模拟实际操作系统的调度状态。
四、主要的数据结构：

/*三个队列*/
private static Queue<Progress> firstQueue = new LinkedList<>();
private static Queue<Progress> secondQueue = new LinkedList<>();
private static Queue<Progress> thirdQueue = new LinkedList<>();
 * 内部进程类：模拟进程
private static class Progress implements Comparable<Progress> {
    String id;     //进程标识符
    int reachTime; //到达时间
    int cpuTime;   //运行时间
    int needTime;  //仍需时间
    char state;    //进程状态
    /*重写比较器*/
    @Override
    public int compareTo( Progress b ) {
        //按reachTime从小到大排序
        return Float.compare(reachTime, b.reachTime);
/*进程数组*/
Progress[] pro = new Progress[proNum];
五、程序流程图：
 
六、源代码：
 
package com.algorithm.multiStageFeedback;
import java.util.*;
 * @Class MSFQS
 * @Description 多级反馈队列调度算法
 * @Author Naren
 * @Date 2020/5/30 10:46
 * @Version 1.0
public class MSFQS {
    /*三个队列*/
    private static Queue<Progress> firstQueue = new LinkedList<>();
    private static Queue<Progress> secondQueue = new LinkedList<>();
    private static Queue<Progress> thirdQueue = new LinkedList<>();
    private static int firstTime;  //第一队列cpu时间片
    private static int secondTime; //第二队列cpu时间片
    private static int thirdTime;  //第三队列cpu时间片
    private static int proNum;     //进程数量
    private static Scanner sc = new Scanner(System.in);
     * 内部进程类：模拟进程
    private static class Progress implements Comparable<Progress> {
        String id;     //进程标识符
        int reachTime; //到达时间
        int cpuTime;   //运行时间
        int needTime;  //仍需时间
        char state;    //进程状态
        /*重排输出格式*/
        @Override
        public String toString() {
            System.out.println();
            return String.format("进程%s: %10d %7d %8d %7c\n", id, reachTime, cpuTime, needTime, state);
        /*重写比较器*/
        @Override
        public int compareTo( Progress b ) {
            //按reachTime从小到大排序
            return Float.compare(reachTime, b.reachTime);
     * 进程调度算法：Multi-stage feedback queue scheduling algorithm
    private static void progressScheduling(Progress[] pro){
        int firstCpu = firstTime;
        int secondCpu = secondTime;
        int thirdCpu = thirdTime;
        int currentTime = 0;
        int num = 0;
        //System.out.println(Arrays.toString(pro));
        /*当有进程未运行时或进程队列不为空时，以每1时间片为单位*/
        while(num < proNum || !firstQueue.isEmpty() || !secondQueue.isEmpty() || !thirdQueue.isEmpty()){
            /*当前时刻有进程到达，则添加入第一队列*/
            while(num < proNum && pro[num].reachTime == currentTime)
                firstQueue.offer(pro[num++]);
            //打印上一秒各队列进程状态
            viewMenu(currentTime);
            /*当前为队列1在运行进程*/
            if(!firstQueue.isEmpty()){
                if (secondQueue.peek() != null) secondQueue.peek().state = 'R';
                if (thirdQueue.peek() != null) thirdQueue.peek().state = 'R';
                //仍需时间：-1
                firstQueue.peek().needTime -= 1;
                //CPU剩余时间片：-1
                firstTime -= 1;
                //更新当前时间：+1
                currentTime++;
                //进程正在运行，状态：E.
                if(firstQueue.peek().needTime > 0){
                    firstQueue.peek().state = 'E';
                    //当前队列CPU时间片用完而进程仍未运行完时，进程出队，入次优先级队尾
                    if




    
(firstTime == 0) {
                        firstQueue.peek().state = 'R';
                        secondQueue.offer(firstQueue.poll());
                        firstTime = firstCpu;
                //进程运行完毕，状态：F，记录完成时刻并出队
                else if(firstQueue.peek().needTime == 0){
                    firstQueue.peek().state = 'F';
                    System.out.printf("\n当前时刻：%d,此进程运行结束：\n",currentTime);
                    System.out.println(firstQueue.peek());
                    Objects.requireNonNull(firstQueue.poll());
                    firstTime = firstCpu;
            /*当前为队列2在运行进程*/
            else if(!secondQueue.isEmpty()){
                if (thirdQueue.peek() != null) thirdQueue.peek().state = 'R';
                //仍需时间：-1
                secondQueue.peek().needTime -= 1;
                //CPU剩余时间片：-1
                secondTime -= 1;
                //更新当前时间：+1
                currentTime++;
                //进程运行完毕，状态：F，记录完成时刻并出队
                if(secondQueue.peek().needTime == 0){
                    secondTime = secondCpu;
                    secondQueue.peek().state = 'F';
                    System.out.printf("\n当前时刻：%d,此进程运行结束：\n",currentTime);
                    System.out.println(secondQueue.peek());
                    Objects.requireNonNull(secondQueue.poll());
                //进程正在运行，状态：E.
                else if(secondQueue.peek().needTime > 0){
                    secondQueue.peek().state = 'E';
                    //当前队列CPU时间片用完而进程仍未运行完时，进程出队，入次优先级队尾
                    if(secondTime == 0) {
                        secondQueue.peek().state = 'R';
                        thirdQueue.offer(secondQueue.poll());
                        secondTime = secondCpu;
            /*当前为队列3在运行进程*/
            else if(!thirdQueue.isEmpty()){
                //仍需时间：-1
                thirdQueue.peek().needTime -= 1;
                //CPU剩余时间片：-1
                thirdTime -= 1;
                //更新当前时间：+1
                currentTime++;
                //进程正在运行，状态：R.
                if(thirdQueue.peek().needTime > 0){
                    thirdQueue.peek().state = 'E';
                    //当前队列CPU时间片用完而进程仍未运行完时，进程出队，入次优先级队尾
                    if(thirdTime == 0) {
                        thirdQueue.peek().state = 'R';
                        thirdQueue.offer(thirdQueue.poll());
                        thirdTime = thirdCpu;
                //进程运行完毕，状态：F，记录完成时刻并出队
                else{
                    firstTime = firstCpu;
                    thirdQueue.peek().state = 'F';
                    System.out.printf("\n当前时刻：%d,此进程运行结束：\n",currentTime);
                    System.out.println(thirdQueue.peek());
                    Objects.requireNonNull(thirdQueue.poll());
     * 输入面板：获取到进程数组
    private static Progress[] operator(){
        System.out.println("-----------------3118004950 柴政-----------------\n");
        System.out.println("欢迎进入多级队列反馈调度模拟系统，队列个数：3。\n\n");
        System.out.println("请按队列优先级从高到低的顺序输入各个队列的时间片长度：");
        firstTime = sc.nextInt();
        secondTime = sc.nextInt();
        thirdTime = sc.nextInt();
        System.out.print( "请输入进程数:" );
        proNum = sc.nextInt();
        /*获取到进程数组*/
        Progress[] pro = new Progress[proNum];
        System.out.println( "请依次输入进程标识符,进程到达时间,进程运行时间:" );
        for( int i = 0; i < proNum; i++ ) {
            pro[i] = new Progress();
            pro[i].id = sc.next();
            pro[i].reachTime = sc.nextInt();
            pro[i].cpuTime = sc.nextInt();
            pro[i].needTime = pro[i].cpuTime;
            pro[i].state = 'R';
        //对进程按照compareTo()的要求按照到达时间排序
        Arrays.sort(pro);
        return pro;
     * 输出面板：实时输出运行结果
    private static void viewMenu(int currentTime){
        System.out.printf("\n当前时刻：%d\n",currentTime);
        System.out.println("---------------------------------------------");
        System.out.println("            到达时间 运行时间  剩余时间  状态");
        if(firstQueue.isEmpty()) System.out.println("队列一：空");
        else System.out.println("队列一：\n"+ firstQueue.toString()
                .replace("[", "").replace("]", "")
                .replace(", ", ""));
        if(secondQueue.isEmpty()) System.out.println("队列二：空");
        else System.out.println("队列二：\n"+ secondQueue.toString()
                .replace("[", "").replace("]", "")
                .replace(", ", ""));
        if(thirdQueue.isEmpty()) System.out.println("队列三：空");
        else System.out.println("队列三：\n"+ thirdQueue.toString()
                .replace("[", "").replace("]", "")
                .replace(", ", ""));
        System.out.println("=============================================");
     * main()
    public static void main(String[] args) {
        progressScheduling(operator());
七、运行测试：
 
测试数据：
 
 时间片到了以后进程出队到次优先级队列等待调度：（上下图）
 
 
 上图中进程C运行结束出队；下图中时刻17进程E抢占成功：
 
 最终：全部进程运行结束。
  
八、总结：
 
多级反馈调度算法非常神奇，关键在于这三点： 
首次加入的进程入最高优先级队列尾等待；
某队列内时间片完而进程还没结束就立即调入次级优先级队列尾等待继续运行；
只要有进程进入高优先级队列内，便对低优先级队列中的进程进行抢占式 运行； 
多级反馈队列调度算法的特点是适合大中小进程同时到达时的情况，对于大进程多的情况，其性能与资源的使用远优于短作业优先、先来先服务等算法。并且对于时间片完而未结束的进程、会在次优先级队列中为其提供倍增的时间等待继续运行。
运行的结果中会使得到达时间晚的进程可能也会先运行结束。它对于各个进程的统筹调度安排非常合理，使得每个进程都有机会执行。我模拟的是三级反馈调度，在此过程中其实可以将其拓展为更多级，只需要新建一个自定义队列类，最后按照用户意愿的个数初始化队列数组即可。
                                    多级反馈队列调度算法可以如下原理：
1、设有N个队列（Q1,Q2…QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。
2、对于优先级最低的队列来
                                    在多级反馈队列调度算法中，不同队列拥有不同大小的时间片，这是为了能够更好地平衡对不同进程的调度。一般来说，高优先级的队列拥有更短的时间片，这样可以更快地获得CPU时间片，而低优先级的队列拥有更长的时间片，以避免过多的上下文切换开销。如果一个进程在当前队列中运行的时间超过了分配给它的时间片大小，但仍未完成，则该进程将被移到更高优先级的队列中，以便更快地获得CPU时间片。在多级反馈队列调度算法中，高优先级队列中的进程优先被调度，直到该队列中没有可运行的进程，然后才会调度下一个较低优先级队列中的进程。
在该时间片内进程执行完毕，这种情况调度程序将立即把该进程弹出队列，并把CPU分配给新的队首进程
在该时间片内进程未执行完毕，调度程序将立即中断该进程执行，把该进程加入队尾，并将CPU分配给新的队首进程
该时间片未结束时有一个新的进程到达，就把新进程放到队尾，并继续执行该时间片（自己的理解，不一定对~）
第3种情况，在实现时的简单做法就是：
直接把运行时间加到该时间片结束或进程执行完毕，接着while循环把所有时间已到达的进程从pr
  不得不说，利用IDEA的GUI Form对Swing的支持，使得我们可以直接在一个没有父类的（也就是不用继承JFrame）的普通类起步来构建我们的GUI Application。不得不承认，虽然现...
一. 主要实现方法和代码介绍
	1.编写进程类,其只包含所需的运行时间和进程编号两个属性,还有一个运行方法,此方法就是将所需的运行时间属性减去.传入的运行时间.
	2.创建进程函数:创建maxp个进程,(应该不超过10,在此创建九个,即暂时不进行进程队列越界处理),其运行时间符合均值为0,方差为20的高斯分布,并取整取绝对之后所得到的值, (此处是为了全自动创建进程),进程号自己自增. 在创建进程时,使用mutex库将每一个queue 加锁和解锁,以实现互斥访问.
                                    1.	多级反馈队列调度算法
编写一个控制台程序模拟多级反馈对列调度算法。设需要调度的进程情况存放在文本文件“process.text”中，如下图所示（进程情况可以自己设置）
1	0	7
2	1	8
3	2	10
4	3	4
5	4	3
6	5	2
7	6	6
8	7	5
每一行描述一个进程，包含若干个字段字段间用Tab建或空格隔开。第一个字段代表进程的编号，第二个字段代表进程到达的时间，第三个字段代表 	。
队列个数和每个队列的时间片长度可以由自己设置他们的值。要求程序必须能够正确给出各个进程到达，调度，运行和完成的时序，并将相应的信息打印出来。举列如下：
T=0时刻，进程1到达。。。
T=0时刻，进程1开始被调度执行。。。。
T=1时刻，进程2到达。。。
最后，计算并打印出各个进程的周转时间和带权周转时间。
                                    最近在学习过程中了解到了关于CPU的调度算法，试着用Java简单模拟了多级反馈队列调度算法（学习阶段，可能存在bug）。
在CPU的多调度算法中，多级反馈队列算法是一种比较优秀的算法，其能够在快速响应高优先级的进程的同时兼顾到服务时间短的进程。该算法的原理就是：
①假设有多级队列，队列的优先级是从高到低的，处于优先级高的队列中的进程优先执行，每次有新的进程进入就将该进程放到第一级队列（优先级最高）...