一. 实验目的
1. 了解虚拟存储技术，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。
2. 掌握FIFO和LRU等置换算法，加强对地址转换过程的了解。
二. 实验内容
1. 产生一个需要访问的指令地址序列。它是一系列需要访问的指令的地址。为不失一般性，你可以适当地（用人工指定地方法或用随机数产生器）生成这个序列；要求，至少100条指令地址，并将其中50%打乱顺序，另有50%切分成两个不连续的部分，每部分内部是连续的。
注意，该地址在未来需要转换为页号与页内地址。
2. 实现页表数据结构，每个页表项为（页号，块号），最大允许1024个页表项，并对页表进行初始化。设每页4KB，页号地址结构如下
实现方法，采用C语言的“位域”定义实现，即
typedef struct {
unsigned shift:12 ; //位移量，页内地址
unsigned pageID:12 ; //页号
unsigned mem_add; //物理块号
unsigned status:1 //状态位
unsigned access:8 //访问字段
unsigned modify:1 //修改位
unsigned disk_add; //外存地址
} PageTable;
3. 缺页中断处理流程，参阅教材图5-2，省略快表的内容。
4. 置换算法，分别实现先进先出FIFO和最近最久未使用LRU。淘汰一页时，仅将该页所在位置的内容覆盖，无需判断是否被改写过，也无需写入硬盘。
基本模拟流程为：
每访问一个地址时，首先要计算该地址所在的页的页号，然后查页表，判断该页是否在主存——如果该页已在主存，则打印页表情况；如果该页不在主存且页表未满，则调入一页并打印页表情况；如果该页不在主存且页表已满，则按置换算法淘汰一页后调入所需的页，打印页表情况；
逐个地址访问，直到所有地址转换/访问完毕。
5. 实验报告中，应有主要步骤执行结果的截图。并附完整代码。
三. 实验结论
1. 算法理解
页面存储管理目的是将用户程序空间和内存空间划分成大小相同的区域，其中的用户空间每块区域称为一页，内存区域称为物理块。而页表将逻辑地址和物理地址联系起来，可以使用户通过查找页表而快速的找到程序所在的内存并调用。
在使用页表的过程中，由于逻辑内存与物理内存的结构和大小不同，因此常常会出现在页表中通过逻辑地址而找不到相应物理块号的情况也称缺页。因此，由于页表空间大小有限，当页表满时需要将一些不常用到的页换出从而将现在所用的页写入页表中，这就涉及到页面置换算法的使用。
2. 实验过程
1）初始化页表、物理块
首先要将结构体数组pagetable页表中的内容全部初始化，即将对应的状态位status设为0（为被调入内存）、访问字段access设为0、物理块号置为-1表示还未分配物理块。
for (int i = 0; i < PAGE_SIZE; i++) {
pagetable[i].pageID = i;
pagetable[i].mem_add = -1;
pagetable[i].status = 0;
pagetable[i].access = 0;
}
声明数组phb[KUA_SIZE]用来表示内存物理块空间，每个元素位置存放的是当前被调用的的页。初始化每个数组元素为-1。
for (int i = 0; i < KUA_SIZE; i++) {
phb[i] = -1;
}
2）先进先出算法FIFO实现
先进先出算法的思想为：总是淘汰最先进入内存的界面，即选择在内存中驻留时间最久的的界面将其淘汰。
在对页表进行访问时，会出现两种情况，即命中和缺页。缺页时还要看物理内存是否已满，根据不同的情况实施不同的操作。定义searchPage函数遍历整个页表，如果找到当前页号返回true，未找到则返回false。
（1）页表命中
根据当前的页号指令，判断页表中是否有当前页，如果返回的时true，则表示页表存在该页面，则访问该页面并将所用的页面在页表中的存在时间加1。
addtime(); //内存中的页面存在时间加1 printPhb(address[i]); cout << "\t\t未发生缺页...\n" << endl;
addtime函数内容为：检索整个页表，将status位为1的页表项的access位都加一。
printPhb函数即打印当前内存块的使用情况。
（2）页表缺页且物理块未满
定义searchKua函数用来查询物理内存空闲的块号，如果找到返回当前的物理块号数，未找到则返回标志数表示内存已满。
内存未满，即将页面放入空闲的物理块，并将返回的块号数赋值给页表的men_add，并将状态为置为1表示页面已在内存。然后增加每个页表项中页面的存在时间。
pagetable[address[i]].mem_add = k; pagetable[address[i]].status = 1; addtime(); phb[k] = address[i]; //页面号写入空闲物理块 que_count++; printPhb(address[i]); cout << "\t\t发生缺页!!!\n" << endl;
（3）页表缺页且物理块已满
遍历页表，找到access即存在时间最久的页将其淘汰并替换成当前的页，并将页表中的页存在时间加1。然后，把该页写入内存对应的物理块中。
int flag = 0;
int max = 0; //找到存在时间最久的页面
for (int j = 0; j < PAGE_SIZE; j++) {
if ((int)pagetable[j].access > max) {
max = pagetable[j].access;
flag = j; //找到在内存存在时间最久的页
}
}
//淘汰存在时间最久页面
pagetable[address[i]].mem_add = pagetable[flag].mem_add; //将物理块号移交给新的页
pagetable[address[i]].status = 1; //状态置为已在内存
ddtime(); //存在时间加1
phb[pagetable[flag].mem_add] = address[i];
pagetable[flag].mem_add = -1; //初始化已淘汰页面
pagetable[flag].status = 0;
pagetable[flag].access = 0;
que_count++; //缺页次数加1
printPhb(address[i]);
cout << "\t\t发生缺页!!!\n" << endl;
3）最近最久未使用算法LRU实现
最近最久未使用算法思想为：为每个页面赋予一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。淘汰掉的页面即为t为最大值的哪一个页面。
在本程序中，LRU算法的实现和FIFO的基本相同，只是淘汰页面时的依据不同。当页面命中时，将该页面的访问字段设为0而不是加1。然后再将所有的页面存在时间加1。
pagetable[address[i]].access = 0; addtime(); //内存中的页面存在时间加1 printPhb(address[i]); cout << "\t\t未发生缺页...\n" << endl;
其他的情况当页面缺页时的过程和FIFO算法十分相似，不再赘述。
3. 实验结果
为了测试方便，选择16条页面序列进行测试
int address[PAGE_SIZE] = { 1,4,1,5,10,6,4,3,9,8,8,9,5,4,2,5 };
（1）FIFO算法测试
由结果可知，经过FIFO置换算法访问页表发生了11次缺页，且每次的置换过程符合FIFO算法的基本要求。
（2）LRU算法测试
由图可知，经过LRU算法访问页表后发生了12次的缺页，并且满足LRU算法，生成了正确的结果。
经过对比可以发现在一些情况下LRU算法的缺页次数可能会比FIFO算法的缺页次数多。
4. 实验总结
本次实验实现了页面存储管理，并能通过c++语言熟练的模拟两种置换算法对页表操作的过程。在代码中通过对程序不断地试错、调试，最终理解了算法的过程与思想并且也终于达到了所期望的结果。
附录
本次实验完整代码如下：
1 #include <iostream>
2 #include <time.h>
3 #define ADD_NUM 100 //指令地址数
4 #define PAGE_SIZE 16 //页面号序列
5 #define KUA_SIZE 4 //物理块数
6
7 using namespace std;
8
9 typedef struct page{
10 unsigned shift : 12; //位移量，页内地址
11 unsigned pageID : 10; //页号
12 unsigned mem_add; //物理块号
13 unsigned status : 1; //状态位，1已调入内存，0未被调入内存
14 unsigned access : 8; //访问字段
15 unsigned modify : 1; //修改位
16 unsigned disk_add; //外存地址
17 } PageTable;
18 PageTable pagetable[PAGE_SIZE];
19 int address[PAGE_SIZE] = { 1,4,1,5,10,6,4,3,9,8,8,9,5,4,2,5 }; //指令页号引用串
20 int queue[KUA_SIZE]; //记录调入页面
21 int phb[KUA_SIZE]; //物理块标号
22 int que_count = 0; //记录缺页次数
23
24 //初始化页表
25 void updatePage() {
26 for (int i = 0; i < PAGE_SIZE; i++) {
27 pagetable[i].pageID = i;
28 pagetable[i].mem_add = -1;
29 pagetable[i].status = 0;
30 pagetable[i].access = 0;
31 }
32 for (int i = 0; i < KUA_SIZE; i++) {
33 phb[i] = -1;
34 }
35 }
36
37 //输出地址页面序列
38 void printAdd() {
39 for (int i = 0; i < PAGE_SIZE; i++) {
40 cout << address[i] << " ";
41 }
42 cout << endl;
43 }
44
45 //打印物理块中的页面情况
46 void printPhb(int add) {
47 cout << "加入页面为：" << add;
48 for (int j = 0; j < KUA_SIZE; j++) {
49 cout << "\t| ";
50 if (phb[j] == -1) {
51 cout << " ";
52 }
53 else {
54 cout << phb[j];
55 }
56 cout << " |";
57 }
58
59 // cout << "page time：";
60 // for (int i = 0; i < PAGE_SIZE; i++)
61 // {
62 // cout << pagetable[i].access << " ";
63 // }
64 // cout << "\n\n";
65 }
66
67 //搜索页是否调入内存
68 bool searchPage(int a) {
69 if (pagetable[a].status == 0) {
70 return false;
71 }
72 return true;
73 }
74
75 //搜索空闲物理块
76 int searchKua() {
77 for (int i = 0; i < KUA_SIZE; i++) {
78 if (phb[i] == -1) {
79 return i; //找到则返回物理块号
80 }
81 }
82 return 4; //未找到空闲的物理块
83 }
84
85 //先进先出增加每一个在内存页中的存在时间
86 void addtime() {
87 for (int i = 0; i < PAGE_SIZE; i++) {
88 if (pagetable[i].status == 1) {
89 pagetable[i].access++;
90 }
91 }
92 }
93
94 //实现先进先出置换算法
95 void findFIFO() {
96 for (int i = 0; i < PAGE_SIZE; i++) {
97 if (searchPage(address[i]) == true) { //内存存在该页面
98 addtime(); //内存中的页面存在时间加1
99 printPhb(address[i]);
100 cout << "\t\t未发生缺页...\n" << endl;
101 }
102 else { //内存不在该页中
103 int k = searchKua();
104 if (k == 4) { //物理块已满
105 int flag = 0;
106 int max = 0; //找到存在时间最久的页面
107 for (int j = 0; j < PAGE_SIZE; j++) {
108 if ((int)pagetable[j].access > max) {
109 max = pagetable[j].access;
110 flag = j; //找到在内存存在时间最久的页
111 }
112 }
113 //淘汰存在时间最久页面
114 pagetable[address[i]].mem_add = pagetable[flag].mem_add; //将物理块号移交给新的页
115 pagetable[address[i]].status = 1; //状态置为已在内存
116 addtime(); //存在时间加1
117 phb[pagetable[flag].mem_add] = address[i];
118
119 pagetable[flag].mem_add = -1; //初始化已淘汰页面
120 pagetable[flag].status = 0;
121 pagetable[flag].access = 0;
122
123 que_count++; //缺页次数加1
124 printPhb(address[i]);
125 cout << "\t\t发生缺页!!!\n" << endl;
126 }
127 else { //物理块未满
128 //将新的页面写入物理块中
129 pagetable[address[i]].mem_add = k;
130 pagetable[address[i]].status = 1;
131 addtime();
132 phb[k] = address[i]; //页面号写入空闲物理块
133
134 que_count++;
135 printPhb(address[i]);
136 cout << "\t\t发生缺页!!!\n" << endl;
137 }
138 }
139 }
140
141 cout << "使用FIFO置换算法后的缺页次数为：" << que_count << endl;
142 }
143
144 //最近未使用算法
145 void findLRU() {
146 for (int i = 0; i < PAGE_SIZE; i++) {
147 if (searchPage(address[i]) == true) { //内存存在该页面
148 pagetable[address[i]].access = 0;
149 addtime(); //内存中的页面存在时间加1
150 printPhb(address[i]);
151 cout << "\t\t未发生缺页...\n" << endl;
152 }
153 else { //内存不在该页中
154 int k = searchKua();
155 if (k == 4) { //物理块已满
156 int flag = 0;
157 int max = 0; //找到存在时间最久的页面
158 for (int j = 0; j < PAGE_SIZE; j++) {
159 if ((int)pagetable[j].access > max) {
160 max = pagetable[j].access;
161 flag = j; //找到在内存存在时间最久的页
162 }
163 }
164 //淘汰存在时间最久页面
165 pagetable[address[i]].mem_add = pagetable[flag].mem_add; //将物理块号移交给新的页
166 pagetable[address[i]].status = 1; //状态置为已在内存
167 addtime(); //存在时间加1
168 phb[pagetable[flag].mem_add] = address[i];
169
170 pagetable[flag].mem_add = -1; //初始化已淘汰页面
171 pagetable[flag].status = 0;
172 pagetable[flag].access = 0;
173
174 que_count++; //缺页次数加1
175 printPhb(address[i]);
176 cout << "\t\t发生缺页!!!\n" << endl;
177 }
178 else { //物理块未满
179 //将新的页面写入物理块中
180 pagetable[address[i]].mem_add = k;
181 pagetable[address[i]].status = 1;
182 addtime();
183 phb[k] = address[i]; //页面号写入空闲物理块
184
185 que_count++;
186 printPhb(address[i]);
187 cout << "\t\t发生缺页!!!\n" << endl;
188 }
189 }
190 }
191
192 cout << "使用LRU置换算法后的缺页次数为：" << que_count << endl;
193 }
194
195 int main(void) {
196
197 int select;
198 cout << "请选择：" << endl;
199 cout << "1、初始化页表" << "\n"
200 << "2、显示地址序列" << "\n"
201 << "3、先进先出算法（FIFO）" << "\n"
202 << "4、最近未使用算法（LRU）" << endl;
203 cout << "-------------------------------------" << endl;
204
205 do {
206 cin >> select;
207 switch (select) {
208 case 1: updatePage();
209 break;
210 case 2: printAdd();
211 break;
212 case 3:findFIFO();
213 break;
214 default: findLRU();
215 break;
216 }
217 cout << "-------------------------------------" << endl;
218 } while (select < 3);
219 return 0;
220 }
标签：存储管理,pagetable,--,内存,add,算法,页表,address,页面 From： https://www.cnblogs.com/wcq1345/p/16950593.html