操作系统之三种页面置换算法(OPT,FIFO,LRU)--Java实现

页面置换算法的定义：
程序运行过程中，有时要访问的页面不在内存中，而需要将其调入内存。但是内存已经无空闲空间存储页面，为保证程序正常运行，系统必须从内存中调出一页程序或数据送到磁盘对换区，此时需要一定的算法来决定到低需要调出那个页面。通常将这种算法称为“页面置换算法”。

页面置换算法有三种：分别是最佳置换算法、先进先出置换算法、最近最久未使用置换算法

其中最好的是最佳置换算法，但最佳置换算法只是个理想化模型，缺页率最高的是先进先出置换算法。

最佳置换算法的原理：每次从物理块内选择未来最长时间不被访问或者以后永久不被访问的页面进行淘汰
上图为OPT的原理
图中我们可以看到，前三个7、0、1依次进入物理块，紧接着要读2页面，，看一下7、0、1，发现下一次读取7的时间最长，那么就把7移除，2进入物理块，后面以此类推。

上图为FIFO原理，由图可知，7、0、1依次进入物理块，轮到2时由于物理块中没有2页，所以第一个进来的7被淘汰然后2进入，下一个0，块中存在，不缺页，然后到来的3，缺页，把0移除，3进入，后面以此类推。这就是先进先出置换算法

上图为LRU最近最久未使用页面置换算法原理，可以看到7、0、1依次进入物理块然后轮到2，由于7是最久没被使用的，7移除，2进入，然后0不缺页，轮到3，前面是0->2->1，可以看出1是最久没被使用的，那么1移除，3进入，后面以此类推，这就是最近最久未使用页面置换算法

下面是代码实现

先定义一个控制开始方法，由主函数调用：

      private static void Chance() {
        input();
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入想要选择的算法  1:LRU 2:FIFO 0:退出");
        int choice = sc.nextInt();
        switch (choice){           
            case 1:
                System.out.println("最近最久未使用算法LRU");
                LRU();
                Output();
                break;
            case 2:
                System.out.println("先进先出 FIFO");
                FIFO();
                Output();
                break;
            case 0:
                break;
            default:
                System.out.println("你的输入不对 重新输入");
                Chance();

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

然后定义变量，全都是全局变量，方便所有方法直接调用，这里就省略类名包名之类的无关紧要的语句了

 private static int MaxPage_num = 100;
    
    private static int[] PageSequence = new int[MaxPage_num];
    
    private static int[][] ProcessBlocks = new int[MaxPage_num][MaxPage_num];
    
    private static int[] PageCount = new int[MaxPage_num];
    
    private static int PageNum;
   
    private static int MissingPageNum;
    
    private static double MissingPageRate;
    private static boolean found;
    
    private static int BlockNum;

    private static int j;
    private static int i;
    private static int k;
    
    private static int NULL = -1;

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

然后定义个方法初始化数组

public static void original(){
        for ( i = 0; i <PageNum ; i++) {
            for ( j = 0; j <BlockNum ; j++) {
                ProcessBlocks[i][j] = NULL;
            }
        }
        MissingPageNum =1;
    }
1
2
3
4
5
6
7
8

然后定义一个方法输入物理块大小 页面数量和页面序列

    public static void input(){
        Scanner sc  = new Scanner(System.in);
        System.out.println("分别输入物理块数量 页面数 页面序列");
        BlockNum = sc.nextInt();
        PageNum = sc.nextInt();
        for ( i = 0; i <PageNum ; i++) {
            PageSequence[i] = sc.nextInt();
        }
    }
1
2
3
4
5
6
7
8
9

然后就可以开始按照逻辑写算法了

    /**
     * 先进先出算法 FIFO
     */
    public static void FIFO(){
        original();
     
        ProcessBlocks[0][0] = PageSequence[0];
        int temp=0,flag=0;
        for ( i = 0; i <PageNum ; i++) {
            
            for ( j = 0; j <BlockNum ; j++) {
                if(PageSequence[i] == ProcessBlocks[flag][j]) {
                    break;
                }
            }
            
            if(j==BlockNum){
                for ( k = 0; k <BlockNum ; k++) {
                    if(ProcessBlocks[flag][k] == NULL) {
                        break;
                    } else {
                        ProcessBlocks[i][k] = ProcessBlocks[flag][k];
                    }
                }
               
                temp++;
               
                temp = temp%BlockNum;
                ProcessBlocks[i][temp] = PageSequence[i];
               
                MissingPageNum++;
                flag = i;
            }else{
                continue;
            }
        }
    }


    /**
     * LRU最近最久未使用算法
     */
    public static void LRU(){
        original();
        ProcessBlocks[0][0] = PageSequence[0];
       
        int temp,flag=0;
       
        PageCount[0] = 0;
        
        for ( i = 0;  i< PageNum; i++) {
            for (j=0;j<BlockNum;j++){
                if (PageSequence[i]== ProcessBlocks[flag][j]){
                    PageCount[j] = i;
                    break;
                }
            }
            
            if(j!=BlockNum){
                continue;
            }
            for (k=0;k<BlockNum;k++){
                if(ProcessBlocks[flag][k]==NULL){
                    break;
                }else{
                    ProcessBlocks[i][k] = ProcessBlocks[flag][k];
                }
            }
            
            for (j=0;j<BlockNum;j++){
                if(ProcessBlocks[i][j]==NULL){
                  
                    ProcessBlocks[i][j] = PageSequence[i];
                    PageCount[j]=i;
                    MissingPageNum++;
                    flag=i;
                    break;
                }
            }
            if(j!=BlockNum){
                continue;
            }
           
            temp=0;
            for(j=0;j<BlockNum;j++){
                
                if(PageCount[temp]>PageCount[j]){
                    temp=j;
                }
            }
            ProcessBlocks[i][temp] = PageSequence[i];
            PageCount[temp]=i;
            MissingPageNum++;
            flag=i;
        }
    }
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

每种算法执行完，再调用一个输出方法，分别输出页面序列对应每个物理块内的页面、缺页次数、缺页率即可，输出格式按自己喜好即可，这里不放输出方法了。下面是例子运行截图：

补发输出方法和主函数：
输出：

/**
     * 输出结果
     */
    public static void Output() {
        MissingPageRate = (double) MissingPageNum / PageNum;
        for (i = 0; i < PageNum; i++) {
            System.out.print("====");
        }
        System.out.println(" ");
        for (i = 0; i < PageNum; i++) {
            System.out.print(PageSequence[i] + " ");
        }
        System.out.println(" ");
        for (i = 0; i < PageNum; i++) {
            System.out.print("====");
        }
        System.out.println(" ");
        for (j = 0; j < BlockNum; j++) {
            for (i = 0; i < PageNum; i++) {
                if (ProcessBlocks[i][j] == NULL) {
                    System.out.print("  ");
                } else {
                    System.out.print(ProcessBlocks[i][j] + " ");
                }
            }
            System.out.println(" ");
        }

        System.out.println("缺页次数=" + MissingPageNum + "\n" + "缺页率=" + MissingPageRate * 100 + "%");
    }

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

主函数：

    public static void main(String[] args) {
        Chance();
    }
    
1
2
3
4

LRU算法：

FIFO算法：

这里的截图就是简单照书上的数据举个例子。

因为OPT算法理论上是不能实现的 所以 没有放在程序中，下面的代码输出的结果也不完全正确，就当个参考吧

    /**
     * OPI最佳置换算法
     */
    public static void OPI(){
        original();
        ProcessBlocks[0][0] = PageSequence[0];
        int temp,flag = 0;//flag是上一个进入内存的页面的下标

        for ( i = 0; i <PageNum ; i++) {
            for (j = 0; j < BlockNum; j++) {
                if (PageSequence[i] == ProcessBlocks[flag][i]) {
                    break;
                }
            }
            if (j != BlockNum) { //代表页面已经在内存块中 不缺页
                continue;
            }
            for (k = 0; k < BlockNum; k++) {
                if (ProcessBlocks[flag][k] == NULL) {
                    break;
                } else {
                    ProcessBlocks[i][k] = ProcessBlocks[flag][k];
                }
            }
            /**
             * 内存中对页面进行选择
             * 分为内存块已满和内存块不满两种情况
             */
            for (j = 0; j < BlockNum; j++) {
                if (ProcessBlocks[i][j] == NULL) {
                    ProcessBlocks[i][j] = PageSequence[i];
                    MissingPageNum++;
                    flag = i;
                    break;
                }
            }
            /*
            内存块不满情况
             */
            if (j != BlockNum) {
                continue;
            }
            /**
             * 内存块已满的情况 temp：要置换的页面的下标
             */
            temp = 0;
            for (j = 0; j < BlockNum; j++) {
                /*
                选择要置换的页面的下标
                 */
                for (k = i + 1; k < PageNum; k++) {
                    /*
                    寻找最长时间内不被访问的页面 k是内存页面序列下标 存进PageCount数组内
                     */
                    if (ProcessBlocks[i][j] == PageSequence[k]) {
                        PageCount[j] = k;
                        break;
                    }
                }
            }
            if (k == PageNum) {//如果k等于了PageNum 就说明剩下的页面序列内没有和当前内存块内页面一样的页面  就把页面数赋值给下标数组的第j个下标 j=BlocknUM
                PageCount[j] = PageNum;
            }
            if (PageCount[temp] < PageCount[j]) {
                temp = j;
            }

            ProcessBlocks[i][temp] = PageSequence[i];
            MissingPageNum++;
            flag = i;
        }
    }
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