页面置换算法--LRU(操作系统)_某系统采用lru页面置换算法和局部置换策略

页面置换算法–LRU

先初始化页面大小，和物理块数。连续输入页面的逻辑地址，以“-1”作为结束标志，采用LRU页面置换算法、固定分配局部置换分配策略。输出该页面的页号和页内位移，若该页不在内存，并且还有剩余的物理块，将该页调入内存，输出“该页不在内存中,调入!”输出当前在内存的物理块号和对应的页号（若当前物理块为空，则输出void）；若该页不在内存，并且没有剩余的物理块，按照FIFO算法选择一页调出后将该页调入内存，输出“已无空闲物理块,置换!”并输出当前在内存的物理块号和对应的页号（若当前物理块为空，则输出void）。

输入格式:

输入页面大小和物理块数，连续输入页面的逻辑地址，以“-1”作为结束标志。

输出格式:

第一行输出页号和页内偏移，第二行若不在内存，按照要求输出提示，若在内存则什么都不输出，随后输出“物理块号 页号”，再连续输出每个逻辑地址页面的物理块号和页内位移，以及当前内存的物理块号和页号的对应关系。请在这里描述输出格式。例如：对每一组输入，在一行中输出A+B的值。

输入样例1:

在这里给出一组输入。例如：

1024 3
1
-1
1
2
3

输出样例1:

在这里给出相应的输出。例如：

页号：0 页内偏移：1
该页不在内存中,调入!
物理块号 页号
0 0
1 void
2 void
1
2
3
4
5
6

输入样例2:

在这里给出一组输入。例如：

1024 3
1
1056
2096
3175
-1
1
2
3
4
5
6

输出样例2:

在这里给出相应的输出。例如：

页号：0 页内偏移：1
该页不在内存中,调入!
物理块号 页号
0 0
1 void
2 void
页号：1 页内偏移：32
该页不在内存中,调入!
物理块号 页号
0 0
1 1
2 void
页号：2 页内偏移：48
该页不在内存中,调入!
物理块号 页号
0 0
1 1
2 2
页号：3 页内偏移：103
已无空闲物理块,置换!
物理块号 页号
0 3
1 1
2 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Page> pages = new ArrayList<>();
        List<Integer> pageAddr = new ArrayList<>();
        int pageSize,blockNumber,pageAddress,i=0,j;
        pageSize = sc.nextInt();
        blockNumber = sc.nextInt();
        pageAddress = sc.nextInt();
        for (j = 0;j<blockNumber;j++){
            pages.add(new Page(i,-1,i));
            i++;
        }
        while (pageAddress != -1){
            pageAddr.add(pageAddress);
            pageAddress = sc.nextInt();
        }

        for (Integer integer : pageAddr) {
            int min = getMin(pages,integer,pageSize);

            System.out.println("页号："+integer / pageSize+" 页内偏移："+integer % pageSize);

            if (min != -3) {
                if (pages.get(min).pageNumber == -1) {
                    System.out.println("该页不在内存中,调入!");
                }else {
                    System.out.println("已无空闲物理块,置换!");
                }
                pages.get(min).flag = i;
                i++;
                pages.get(min).pageNumber = integer / pageSize;
            }
            else if (min == -3){
                for (Page page : pages) {
                    if (page.pageNumber == integer / pageSize){
                        page.flag = i;
                        i++; break;
                    }
                }
            }
            printf(pages);
        }


    }
   static class Page{
        private int blockNumber;
        private  int pageNumber;
        private int flag;

       public Page(int blockNumber, int pageNumber, int flag) {
           this.blockNumber = blockNumber;
           this.pageNumber = pageNumber;
           this.flag = flag;
       }

       public int getBlockNumber() {
           return blockNumber;
       }

       public void setBlockNumber(int blockNumber) {
           this.blockNumber = blockNumber;
       }

       public int getPageNumber() {
           return pageNumber;
       }

       public void setPageNumber(int pageNumber) {
           this.pageNumber = pageNumber;
       }

       public int getFlag() {
           return flag;
       }

       public void setFlag(int flag) {
           this.flag = flag;
       }
   }

   public static int getMin(List<Page> pages,int integer,int pageSize){
        int tmp = 1000,tmp01 = -1;
       for (int i = 0; i < pages.size(); i++) {
           if (pages.get(i).flag < tmp){
             tmp =   pages.get(i).flag;
             tmp01 = i;
           }
           if (pages.get(i).pageNumber == integer / pageSize) {
               tmp01 = -3;
               break;
           }
       }
       return tmp01;
   }

   public static void printf(List<Page> pages){
       System.out.println("物理块号 页号");
       for (int i = 0; i < pages.size(); i++) {
           System.out.print(i+" ");
           if (pages.get(i).pageNumber == -1)
               System.out.println("void");
           else System.out.println(pages.get(i).pageNumber);
       }
   }
}

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