【Java学习笔记】45：优先级队列PriorityQueue和比较器Comparator_java priorityqueue comparator

作者：笔触狂放9 | 2024-04-03 10:09:55

踩

java priorityqueue comparator

模拟进程调度时的优先数法和简单时间片轮转法，前者可以为进程设定以优先数PRIORITY为优先级，为了更好地并发，每次获得处理机后优先数减少3而重新选取。
在简单轮转法中则仅仅是一个普通队列，按照FIFO的方式出队获得处理机。

如果要使用比较器Comparator给优先级队列，在创建时就应作为参数传入进去。Comparator通过覆写返回int值的正负来做判断，常使用匿名内部类。

Main.java

import java.util.Scanner;

//主类
public class Main {

    static int proNUM=5;//进程数目

    public static void main(String[] args) {
        System.out.println("请输入priority(优先数法)或者RR(轮转法):");
        //从键盘读入字符串
        Scanner s=new Scanner(System.in);
        String str=null;
        str=s.next();
        //比较
        if(true==str.equals("priority"))//使用优先数法
            new fun_priority();
        else if(true==str.equals("RR"))//使用简单轮转法
            new fun_myRR();
        else//输的不对
            System.out.println("错误的输入!再见!");
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

PCB.java

//进程控制块
class PCB {
    int PID;//进程标识符
    int PRIORITY;//进程优先级
    int CPUTIME;//占用CPU时间片数
    int ALLTIME;//还需时间片数
    boolean STATE;//刚刚进程的状态(有无获得处理机)
    //构造器(初始化)
    PCB(int i){
        PID=i;
        //(数据类型)(最小值+Math.random()*(最大值-最小值+1))
        PRIORITY=(int)(1+Math.random()*(60-1+1));
        CPUTIME=0;
        ALLTIME=(int)(1+Math.random()*(4-1+1));
        STATE=false;//阻塞
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

fun_priority.java

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

//优先数法
class fun_priority {

    static PCB[] pcb=null;//PCB数组

    //有关PCB优先级,用下标i和j的匿名比较器
    public static Comparator<Integer> PriCmp = new Comparator<Integer>(){
        @Override
        public int compare(Integer i, Integer j) {
            return -(pcb[i].PRIORITY-pcb[j].PRIORITY);//这样优先级队列中是大的先出
        }
    };

    //显示PCB数组的内容
    void display(){
        System.out.println("=================================================");
        System.out.println("PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE");

        for(int i=0;i<Main.proNUM;i++)
        {
            System.out.print(pcb[i].PID+"        "+pcb[i].PRIORITY+"         "+
                    pcb[i].CPUTIME+"      "+pcb[i].ALLTIME+"       "+pcb[i].STATE);
            if(pcb[i].ALLTIME==0)
                System.out.print(" 已死");
            System.out.println("");
        }

    }

    //优先数法的构造器
    fun_priority(){

        //分配数组空间
        pcb=new PCB[Main.proNUM];

        //创建空的优先级队列,指定使用PriCmp作为比较器
        Queue<Integer> myPriQ= new PriorityQueue<Integer>(Main.proNUM,PriCmp);

        //初始化PCB,同时把下标扔进优先级队列
        for(int i=0;i<Main.proNUM;i++)
        {
            pcb[i]=new PCB(i);
            myPriQ.add(new Integer(i));
        }

        display();//显示(初始情况)

        Integer index;//临时用
        //循环做优先数法
        while(false==myPriQ.isEmpty()){
            index=myPriQ.poll();//取一个
            //优先级缩减
            if(pcb[index].PRIORITY>3)
                pcb[index].PRIORITY-=3;
            else
                pcb[index].PRIORITY=0;
            //运行时间缩减,已执行时间增加
            pcb[index].ALLTIME-=1;
            pcb[index].CPUTIME+=1;
            if(pcb[index].ALLTIME>0)//如果还没运行完
                myPriQ.add(index);//再放回去
            pcb[index].STATE=true;//先设为true
            display();//显示(每次变化)
            pcb[index].STATE=false;//显示完设回false
        }   
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

fun_myRR.java

import java.util.LinkedList;
import java.util.Queue;

//简单轮转法
class fun_myRR {
    static PCB[] pcb=null;//PCB数组

    //显示PCB数组的内容
    void display(){
        System.out.println("===========================================================");
        System.out.println("PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE");

        for(int i=0;i<Main.proNUM;i++)
        {
            System.out.print(pcb[i].PID+"           "+pcb[i].PRIORITY+"                "+
                    pcb[i].CPUTIME+"      "+pcb[i].ALLTIME+"       "+pcb[i].STATE);
            if(pcb[i].ALLTIME==0)
                System.out.print(" 已死");
            System.out.println("");
        }

    }

    //构造器
    fun_myRR(){
        //分配数组空间
        pcb=new PCB[Main.proNUM];

        //创建空的队列(LinkedList类实现了Queue接口)
        Queue<Integer> myQ=new LinkedList<Integer>();

        //初始化PCB,同时把下标扔进队列
        for(int i=0;i<Main.proNUM;i++)
        {
            pcb[i]=new PCB(i);
            myQ.add(new Integer(i));
        }

        display();//显示(初始情况)

        Integer index;//临时用
        //循环做RR法
        while(false==myQ.isEmpty()){
            index=myQ.poll();//取一个
            //运行时间缩减,已执行时间增加,这里时间片设为2
            int k=pcb[index].ALLTIME>=2 ? 2 : 1;//这次用掉的时间片
            pcb[index].ALLTIME-=k;
            pcb[index].CPUTIME+=k;
            if(pcb[index].ALLTIME>0)//如果还没运行完
                myQ.add(index);//再放回去
            pcb[index].STATE=true;//先设为true
            display();//显示(每次变化)
            pcb[index].STATE=false;//显示完设回false
        }   

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

运行结果1

请输入priority(优先数法)或者RR(轮转法):
priority
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        35         0      3       false
2        9         0      4       false
3        13         0      4       false
4        20         0      4       false
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        32         1      2       true
2        9         0      4       false
3        13         0      4       false
4        20         0      4       false
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        29         2      1       true
2        9         0      4       false
3        13         0      4       false
4        20         0      4       false
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       true 已死
2        9         0      4       false
3        13         0      4       false
4        20         0      4       false
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        9         0      4       false
3        13         0      4       false
4        17         1      3       true
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        9         0      4       false
3        13         0      4       false
4        14         2      2       true
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        9         0      4       false
3        13         0      4       false
4        11         3      1       true
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        9         0      4       false
3        10         1      3       true
4        11         3      1       false
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        9         0      4       false
3        10         1      3       false
4        8         4      0       true 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        9         0      4       false
3        7         2      2       true
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        9         0      2       false
1        26         3      0       false 已死
2        6         1      3       true
3        7         2      2       false
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        6         1      1       true
1        26         3      0       false 已死
2        6         1      3       false
3        7         2      2       false
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        6         1      1       false
1        26         3      0       false 已死
2        6         1      3       false
3        4         3      1       true
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        3         2      0       true 已死
1        26         3      0       false 已死
2        6         1      3       false
3        4         3      1       false
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        3         2      0       false 已死
1        26         3      0       false 已死
2        3         2      2       true
3        4         3      1       false
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        3         2      0       false 已死
1        26         3      0       false 已死
2        3         2      2       false
3        1         4      0       true 已死
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        3         2      0       false 已死
1        26         3      0       false 已死
2        0         3      1       true
3        1         4      0       false 已死
4        8         4      0       false 已死
=================================================
PID  PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0        3         2      0       false 已死
1        26         3      0       false 已死
2        0         4      0       true 已死
3        1         4      0       false 已死
4        8         4      0       false 已死
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

运行结果2

请输入priority(优先数法)或者RR(轮转法):
RR
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                0      2       false
1           42                0      4       false
2           33                0      1       false
3           7                0      3       false
4           60                0      3       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       true 已死
1           42                0      4       false
2           33                0      1       false
3           7                0      3       false
4           60                0      3       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                2      2       true
2           33                0      1       false
3           7                0      3       false
4           60                0      3       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                2      2       false
2           33                1      0       true 已死
3           7                0      3       false
4           60                0      3       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                2      2       false
2           33                1      0       false 已死
3           7                2      1       true
4           60                0      3       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                2      2       false
2           33                1      0       false 已死
3           7                2      1       false
4           60                2      1       true
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                4      0       true 已死
2           33                1      0       false 已死
3           7                2      1       false
4           60                2      1       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                4      0       false 已死
2           33                1      0       false 已死
3           7                3      0       true 已死
4           60                2      1       false
===========================================================
PID  (无意义的)PRIORITY  CPUTIME  ALLTIME  (Last Time)STATE
0           25                2      0       false 已死
1           42                4      0       false 已死
2           33                1      0       false 已死
3           7                3      0       false 已死
4           60                3      0       true 已死
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/355103