LRU算法-模拟页面置换(C语言)_页面置换算法c语言

1.LRU算法

LRU算法(Least Recently Used):最近最久未使用法,操作系统中页面置换中的经典算法, 当内存中分配的页面满的时候, 则需要将内存中最久未被使用的页面用新的页面替换出去.

2.运行结果

例子:

先看运行结果:

3.算法实现

3.1 数据结构

定义页面的数据结构

#define PAGE_COUNT_MAX 20  //页面最大数量
#define DEFAULT_NUM -1  //默认的初值页面号码

typedef struct Page {
    int num;//页面号码
    int time;//在内存中未访问的时间段
}PINFO;
1
2
3
4
5
6
7

这里定义了PAGE_COUNT_MAX,表示输入的时候,内存中最多同时存储的页面数量.
DEFAULT_NUM表示初始化的时候,在未输入页面走向的时,默认的页面号码值,为了后面便于判断和操作.
Page:页面数据结构.
num:页面的号码.
time:在内存中的未访问的时间长度(目前这个字段没有起到很大的作用,留作扩展用).

3.2 模拟的核心思想

使用数组模拟.
1.定义了内存中存放的数组M.
2.初始化页面的走向数组P.
3.当有新的页面(N)需要调入内存的时候.
3.1.判断此时内存中(M)是否有这个页面(N),如果M中存在此页面(不缺页),则将当前页面和内存中的M[0]位置页面互换位置.
3.2,如果M中不存在此页面(缺页了),则需要判断,此时内存中(M)是否满了.
如果M未满,则顺序添加到数组的末尾.
如果M满了,则将末尾之前的页面顺序往后移动一个位置,将新页面N添加到M[0]位置.

3.3定义的方法

//重置页面走向
void resetInputPagesInfo(void);
//重置内存页面
void  resetMemoryPagesInfo(void);
//初始化内存页面容量
void  initMemoryPages(void);
//初始化页面走向
void  initInputPages(void);
//打印内存中页面最大容量
void  printfMemoryPageSize(void);
//打印页面的走向列表
void  printfInputPage(void);
//页面操作菜单
int  menuPage(void);
//打印分割线
void printfPageLine(int num,char c,int nextLine);
//打印内存中的集合. length:当前内存的长度
void printfMemoryPages(PINFO  pageInfos[],int length);
//内存中的队列是否满
//返回值:下一个空的位置角标. -1:表示已经满了
int  isMemoryFull(void);
//将新的页面添加到内存未满的集合中(不包含)
void  addPageToNoFullByNoContain(PINFO pInfo,int nextEmptyPosition);
//将新的页面添加到内存集合满的状态(不包含)
void  addPageToFullByNoContain(PINFO pInfo);
//将新的页面添加到内存中包含此页面集合中,containPosition为角标
void  addPageByContain(PINFO pInfo,int containPosition);
//开始调度
void  startDispatch(void);

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

3.4定义数组

1.定义内存页面数组.
2.定义页面走向数组.
3.定义内存中待输入页面数量(大于0小于等于PAGE_COUNT_MAX数值).
4.定义待输入的页面走向的数组大小.

#include "LruAlgorithm.h"

PINFO pagesMemory[PAGE_COUNT_MAX];//在内存中存储的页面数量(按照最近一次在内存中访问的时间:从小到大排列,最后访问的在第一个位置,依次类推
PINFO pagesInpuntPage[PAGE_COUNT_MAX*2];//可以输入的页面的数量
int memory_size;//内存中页面的数量
int input_size;//页面走向的数量
1
2
3
4
5
6

3.5方法实现

//判断队列中是否包含此页面
//返回值:当前页面在内存中的位置角标,-1表示不包含
int  isContainPage(PINFO array[],int length,PINFO value){
    for(int i=0;i<length;i++){
        if(array[i].num==value.num){
            return i;
        }
    }
    return -1;
}

//重置内存页面
void  resetMemoryPagesInfo(){
    memory_size=0;
    for(int i=0;i<PAGE_COUNT_MAX;i++){
        pagesMemory[i].num=DEFAULT_NUM;
        pagesMemory[i].time=DEFAULT_NUM;
    }
    resetInputPagesInfo();
}

//重置页面走向
void resetInputPagesInfo(){
    input_size=0;
    for(int i=0;i<PAGE_COUNT_MAX*2;i++){
         pagesInpuntPage[i].num=DEFAULT_NUM;
         pagesInpuntPage[i].time=DEFAULT_NUM;
    }
}

//初始化内存页面
void  initMemoryPages(){
    resetMemoryPagesInfo();
    printf("请输入内存中页面容量数量(大于0):");
    scanf("%d",&memory_size);
    //如果超过了最大值,则设置为最大值
    if(memory_size>PAGE_COUNT_MAX){
       memory_size=PAGE_COUNT_MAX;
    }
    if(memory_size<=0){
        printf("内存容量页面应该大于0");
    }
}


//初始化页面走向
void  initInputPages(void){
    resetInputPagesInfo();
    printf("请输入页面调度的走向(输入-1结束):\n");
    int position=0;
    do{
        int num;
        scanf("%d",&num);
        if(num==-1){
            break;
        }
        pagesInpuntPage[position].num=num;
        position++;
        input_size=position;
    }while(position<PAGE_COUNT_MAX*2);
    //如果页面走向为0,那么直接退出
    if(input_size<=0){
        printf("页面数量应该大于0\n");
    }else{
        printfInputPage();
    }
   
}

//打印内存中页面最大容量
void  printfMemoryPageSize(void){
    if(memory_size<=0){
         printf("还未初始化内存页面容量(菜单编号1)\n");
    }else{
         printf("内存中可以存储的最大页面数:%d\n",memory_size);
    }
   
}
//打印页面的走向列表
void  printfInputPage(void){
    if(input_size<=0){
        printf("页面走向序列:还未初始化页面走向(菜单编号2)\n");
    }else{
        printf("页面走向序列(%d):",input_size);
        printf("[");
        for(int i=0;i<input_size;i++){
            if(i==0){
                printf("%d",pagesInpuntPage[i].num);
            }else{
                printf(",%d",pagesInpuntPage[i].num);
            }
        }
        printf("]\n");
    }
}

//打印分割线
void printfPageLine(int num,char c,int nextLine){
    for(int i=0;i<num;i++){
        printf("%c",c);
    }
    if(nextLine==1){
        printf("\n");
    }
}

//打印内存中的集合.
void printfMemoryPages(PINFO  pageInfos[],int length){
    printf("按照在内存中未访问的时间从短到长排列(%d):",length);
    printf("[");
    for(int i=0;i<length;i++){
        if(i==0){
            printf("%d",pageInfos[i].num);
        }else{
             printf(",%d",pageInfos[i].num);
        }
    }
    printf("]\n");
}
//内存中的队列是否满
//返回值:下一个空的位置角标. -1:表示已经满了
int  isMemoryFull(){
    for(int i=0;i<PAGE_COUNT_MAX;i++){
        if(pagesMemory[i].num==-1){
            //找到了空的位置
            if(i==memory_size){
                return -1;
            }else{
                return i;
            }
        }else if(i==PAGE_COUNT_MAX-1 &&pagesMemory[i].num!=-1){
            return -1;
        }
    }
    return -1;
}

//将新的页面添加到内存未满的集合中(不包含)
void  addPageToNoFullByNoContain(PINFO pInfo,int nextEmptyPosition){
    printf("缺页了->新页码:%d,移除的页码:%s\n",pInfo.num,"无");
    //1.首先逆向遍历移动集合中元素:位置+1,并且time+1.
    for(int i=nextEmptyPosition-1;i>=0;i--){
        pagesMemory[i+1].num=pagesMemory[i].num;
        pagesMemory[i+1].time=pagesMemory[i].time+1;
    }
    //2.将新的页面添加到0的位置,并且时间设置为0
    pagesMemory[0].num=pInfo.num;
    pagesMemory[0].time=0;
}
//将新的页面添加到内存集合满的状态(不包含)
void  addPageToFullByNoContain(PINFO pInfo){
    printf("缺页了->新页码:%d,移除的页码:%d\n",pInfo.num,pagesMemory[memory_size-1].num);
    //1.首先逆向移动集合中元素:位置+1,并且time+1.
    for(int i=memory_size-1-1;i>=0;i--){
        pagesMemory[i+1].num=pagesMemory[i].num;
        pagesMemory[i+1].time=pagesMemory[i].time+1;
    }
    //2.将新的页面添加到0的位置,并且时间设置为0
    pagesMemory[0].num=pInfo.num;
    pagesMemory[0].time=0;
}

//将新的页面添加到内存中包含此页面集合中,containPosition为角标
void  addPageByContain(PINFO pInfo,int containPosition){
     printf("不缺页->新页码:%d\n",pInfo.num);
    //1.先查找当前结点在集合中的位置角标i
    int position=containPosition;
    //2.将i结点之后的结点time+1
    for(int i=position+1;i<memory_size;i++){
        if(pagesMemory[i].time!=-1){
           pagesMemory[i].time=pagesMemory[i].time+1;
        }
    }
    //3.将i结点之前的结点往后移动位置+1,并且时间time+1
    for(int i=position-1;i>=0;i--){
        pagesMemory[i+1].num= pagesMemory[i].num;
        pagesMemory[i+1].time= pagesMemory[i].time+1;
    }
    //4.将i结点添加到第0的位置,时间设置为0
    pagesMemory[0].num=pInfo.num;
    pagesMemory[0].time=0;
}

//开始调度
void  startDispatch(){
    printf("<<开始调度>>\n");
    int  lackPageCount=0;
    //页面调度顺序
    for(int i=0;i<input_size;i++){
        int containPosition=isContainPage(pagesMemory, memory_size, pagesInpuntPage[i]);
        if(containPosition!=-1){
            //内存中存在此页面--不缺页
            addPageByContain(pagesInpuntPage[i],containPosition);
            printfMemoryPages(pagesMemory,memory_size);
        }else{
            lackPageCount++;
            //内存中不存在此页面--缺页
            int position=isMemoryFull();
            if(position!=-1){
                //表示内存集合未满
                addPageToNoFullByNoContain(pagesInpuntPage[i],position);
                printfMemoryPages(pagesMemory,position+1);
            }else{
                //内存中集合满了
                addPageToFullByNoContain(pagesInpuntPage[i]);
                printfMemoryPages(pagesMemory,memory_size);
            }
        }
    }
    printf("调度结果:页面总数:%d,缺页次数:%d,缺页率:%.2f%s\n",input_size,lackPageCount,(float)lackPageCount/input_size*100,"%");
    printf("<<调度结束>>\n");
}
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213

3.6菜单

调用的顺序:
1.首先必须先初始化内存页面容量.
2.再初始化内存页面走向.
3.然后才可以页面调度.
如果操作后面的步骤,则前面的步骤必须完成.

//页面操作菜单
int  menuPage(void){
    
    int  result=1;
    
    printfPageLine(50,'*',1);
    printf("%*s%s\n",18,"","<<页面管理(LRU算法)>>");
    printf("%*s%s\n",20,"","1.初始化内存页面容量");
    printf("%*s%s\n",20,"","2.查看内存页面大小");
    printf("%*s%s\n",20,"","3.初始化页面走向");
    printf("%*s%s\n",20,"","4.查看页面走向");
    printf("%*s%s\n",20,"","5.开始调度页面");
    printf("%*s%s\n",20,"","6.退出系统");
    printf("%*s%s",18,"","请输入菜单编号(1-6):");
    int  menuNum;
    do{
        scanf("%d",&menuNum);
        if(menuNum<1 || menuNum>6){
            printf("%*s%s",18,"","输入错误,请重新输入:");
        }
    }while(menuNum<1 || menuNum>6);
    
    
    printfPageLine(50,'*',1);
    
    switch (menuNum) {
        case 1:
            initMemoryPages();
            menuPage();
            break;
        case 2:
            printfMemoryPageSize();
            menuPage();
            break;
        case 3:
            initInputPages();
            menuPage();
            break;
        case 4:
            printfInputPage();
            menuPage();
            break;
        case 5:
            if(memory_size<=0){
                printf("请先初始化内存容量(菜单编号1)\n");
            }else if(input_size<=0){
                printf("请先初始化页面走向(菜单编号2)\n");
            }else{
                startDispatch();
            }
            menuPage();
            break;
        case 6:
            printf("退出成功,欢迎下次使用\n");
//            exit(0);
            result=0;
            break;
    }
     return  result;
}
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

4.注意

1.此代码是在mac系统上的开发工具xcode上开发的,如果下载的代码要在WIndow系统上的VC6.0或者DevC++开发工具上运行,可能会存在中文乱码问题.
解决办法:
1.1可以在window上使用记事本打开,另存为:选择window系统上开发工具支持的编码方式.
1.2可以使用笨方法:在window开发工具上新建文件,然后使用记事本打开源代码后复制到新建的文件上.

2.如果出现不能运行的问题,就是方法中局部变量问题.
例如:

//判断队列中是否包含此页面
//返回值:当前页面在内存中的位置角标,-1表示不包含
int  isContainPage(PINFO array[],int length,PINFO value){
    for(int i=0;i<length;i++){
        if(array[i].num==value.num){
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10

就需要把i抽取到方法体的顶部.

//判断队列中是否包含此页面
//返回值:当前页面在内存中的位置角标,-1表示不包含
int  isContainPage(PINFO array[],int length,PINFO value){
    int i;
    for(i=0;i<length;i++){
        if(array[i].num==value.num){
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11

自己亲测在window上使用上述两种办法,解决了问题.mac编译工具到window编译工具可以运行.