操作系统原理的上机实验的报告一共有四个，其他的报告的地址是：
第一次：https://shiraha.cn/2020/class-FoDOS-experiment-1/ https://shiraha.cn/2020/class-FoDOS-experiment-2/ https://shiraha.cn/2020/class-FoDOS-experiment-3/ https://shiraha.cn/2020/class-FoDOS-experiment-4/
Front-matter 本次实验的所有源代码可以在https://dev.azure.com/Pure-Asahi/_git/2020_Spring_In_Class_Job?path=%2Fosnmb%2Fexp 查看到。
实验要求 本次上机实验的实验要求如下：
##### 《操作系统原理》第二次上机实验 一、实验目的
理解页面淘汰算法原理，编写程序演示页面淘汰算法； 验证 Linux 虚拟地址转化为物理地址的机制； 理解和验证程序运行局部性的原理； 二、实验内容
在 Windows 环境下编写一个程序，模拟实现 OPT, FIFO, LRU 等页面淘汰算法。可以使用数组模拟内存，数组中的元素模拟为指令或数据。写不同方式的程序去访问数组来模拟 CPU 访问内存的情况。分析运算结果，在分配不同的物理块情况下， 各算法的缺页情况有什么规律？可以 srand() 和 rand() 等函数定义和产生“指令”序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 例如，实验中可以产生 320 条“指令”，每个“虚拟页”存放 10 条指令。 进程分配的页框是 4（可变，例如 32）。在 Linux 环境下，编写一个小程序，获取该程序中的某个变量的虚拟地址，虚拟页号，页内偏移地址，物理页框号，页内偏移地址，物理地址，并将它们打 印出来。建议使用 /proc/pid/pagemap 技术。 在 Windows 环境下，编写一个函数（特点：比较耗时，比如大型的多维数组读写），用不同的方法测试其所花费的时间。在不同环境下比较其时间是否不同，并分析其含义。测量时间的函数请 baidu。 实验指南：参考网络，课件等。
实验内容 在 Windows 环境下编写一个程序，模拟实现 OPT, FIFO, LRU 等页面淘汰算法。可以使用数组模拟内存，数组中的元素模拟为指令或数据。写不同方式的程序去访问数组来模拟 CPU 访问内存的情况。分析运算结果，在分配不同的物理块情况下， 各算法的缺页情况有什么规律？可以 srand() 和 rand() 等函数定义和产生“指令”序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 例如，实验中可以产生 320 条“指令”，每个“虚拟页”存放 10 条指令。 进程分配的页框是 4（可变，例如 32）。 在 Linux 环境下，编写一个小程序，获取该程序中的某个变量的虚拟地址，虚拟页号，页内偏移地址，物理页框号，页内偏移地址，物理地址，并将它们打 印出来。建议使用 /proc/pid/pagemap 技术。 在 Windows 环境下，编写一个函数（特点：比较耗时，比如大型的多维数组读写），用不同的方法测试其所花费的时间。在不同环境下比较其时间是否不同，并分析其含义。测量时间的函数请 baidu。 实验过程 下面是对于每一个任务的原理和过程的简述：
算法模拟 要想完成这个任务，有两个问题需要解决：应该怎么模拟内存和指令？这些算法应该怎么实现？
现代计算机采用的大多是段页式内存管理，可以平衡达到不错的性能，这里就不展开详细介绍了（毕竟还要扯到好多别的东西）。简单的建模大概就是：我们有一个物理内存，按照页框分好了页。这里先不管那些用来维护这些信息的辅助空间，只关注存储了实际数据的空间；因为内存算法的目的就是让小内存尽可能运行需要内存较多的程序，所以还要有一个虚拟内存空间：它至少比物理内存要大；此外抽象每条指令都是需要内存中的一个确定页面的数据——这也没有什么问题，当然这个内存是虚拟内存。
这样，我们就可以开设代表物理内存的数组，并且存储了一些虚拟内存中的数据页面；假设所有的指令（毕竟二进制的情况下，指令就是数据，数据也是指令；为了模型更加清晰和直观，我们将命令和数据分离；假设所有指令都占用极小内存并且不占用数据段，数据分页并载入数据段的虚拟内存空间）都是需要数据段的某一页数据；那么，当指令需要的数据页面在物理空间内时命中，否则缺页。
接下来就是算法部分了。首先是 OPT：它代表着理想中的最佳情况，在现实计算机中不可能被达成。这是因为它的实现过程中，需要“预知未来”的指令才可以做出最优判断，有些动态规划的思想。称它为“离线算法”比较合适，但是在现实计算机的“强制要求在线”的环境下，并不能实现这样的算法。
OPT 本质上在替换物理内存中的虚拟页的时候，会根据对未来指令的“观测”，找到当前物理内存中持有的距离下次调用最久远的内存页进行替换——这样做的最优性是显然的。在实现的过程中，我们可以开设一个长度等于指令全长度的数组，从后向前进行一次扫描，将每一个指令的下一次执行的时间戳记录下来；开始模拟后只需要对数组进行 O(1) 访问就可以知道下一次调用该页面的时间戳了。
FIFO 就显得非常的简单粗暴：它认为所有的数据页面被指令访问到的机会是“均等”的——这样就可以得到一个显然的结论，即先进入内存（被访问）的内存页下次被指令使用的可能性更小，所以在替换的时候会优先的替换掉这些先进入物理内存的数据页面。
FIFO 的实现也非常的简单：我们假设将数据载入内存的时候是按某个顺序进行的，在替换的过程中我们只需要遵循这个顺序找到下一个要被替换掉的内存块就可以了；具体的说是开一个静态变量记录上次置换的页面的物理页框编号，之后的替换就是对于这个页框增加一就可以了。
LRU 是这几个算法中最为平衡的一个算法：不仅具有可行性，而且也可以保证较好的命中率；此外基于这个算法还可以进行一些数据结构上的调整，增加优先级和队列的设计，让它的命中率更高（当然，相对的运算代价也会增大）。但是因为这次上机实验没有要求，这里就不再赘述了。和 FIFO 不同，LRU 算法认为如果一个内存页面在最近被访问过，那么它在较短时间内被再次访问的概率会比其他页面更高。所以相对地，需要淘汰的页面是物理内存中最久没有被访问过的页面。这样的算法其实更加符合人们的生活常识，事实上它确实在一般情况下可以带来比起 FIFO 算法更高的命中率。
在 LRU 实现的过程中，我们可以维护一个链表——它维持了当前物理内存中所有的页面；每当需要卸载一个页面的时候，我们从队尾取出一个物理页框，将它与新数据页置换；当载入一个新的数据页的时候，我们将它放入的物理页框作为一个节点加入到链表的队首；当访问一个物理内存中已经载入的页面的时候，我们将它从链表中原位置取出，并放置在链表队首。
根据上面的分析，我们可以显然得出这个链表占用的空间（长度）不会超过物理内存页框的数量，所以为了避免开节点/删节点频繁的内存访问，可以使用“对象池”技术进行优化。但是在我公开的代码里，我为了更加直观的展现这个过程，并没有采用这种设计模式。
在算法正确性测试的过程中，我特别采用了{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}这组数据；这是来源于网络上的参考资料 中的数据，该博主给出了这组数据在这三种算法下的内存快照以供对比，可以验证我的算法的正确性。
4_1.png 可以在实验结果部分看到完整的程序输出。
在验证完正确性之后，为了方便之后的测试，我将整个测试流程提出作为接口；在我的源代码中可以看到它的定义以及使用方法，这里不再赘述；为了测试不同的算法在不同的物理内存/虚拟内存比率下的缺页率，我调用了这个接口创建了一组测试，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 dword institute[400 ]; cout << fixed << setprecision(4 );for (int i = 1 ; i <= 8 ; ++ i){ auto opt = new_process(i * 4 , 32 , 320 , institute, OPT, true ); auto fifo = new_process(i * 4 , 32 , 320 , institute, FIFO); auto lru = new_process(i * 4 , 32 , 320 , institute, LRU); cout << "物理内存 " << i * 4 << "，虚拟内存 32，命中率：\t" << "\t\tOPT = " << opt << "\t\tFIFO = " << fifo << "\t\tLRU = " << lru << endl ; }
可以将这段代码粘贴到公开的源代码的指定位置进行测试，可以获得输出。
检查 Linux 变量 本任务的实验原理在操作系统原理的课堂上都有介绍，这里不再详细介绍；大体步骤是：
使用getpagesize获得系统设定的页框大小，将指针类型转换为ulong获得虚拟地址； 虚拟地址整除页面大小可以得到虚拟页框号，取余数可以得到页框内的偏移地址； 打开/proc/self/pagemap文件，找到对应项的起始位置，读取并记录该值； 取上一步获得的项值的 0-55 位，其意义是变量的物理页框号，加上偏移地址就是物理地址； 将上述的过程写成 C++ 代码并输出指定的结果，本任务就完成了。
源代码已经公开，实验结果请参见“实验结果”部分。
检查函数运行时间 对于 Windows 平台，C++ 环境下，测量时间的方法可以分为以下三类：
C++ 标准库提供的方法：time、clock、std::chrono Windows 提供的系统调用：QueryPerformanceCounter、GetTickCount、timeGetTime 硬件平台提供的指令：__asm{_emit 0x0F;_emit 0x31;} 内联汇编比较的不靠谱，timeGetTime所需要的WinMM.Lib甚至不被包含在基础的 Windows SDK 内；所以选择剩下的五种方法予以实现。
源代码已经公开，实验结果请参见“实验结果”部分。
实验结果 这里是任务完成后的截图或其他证明，包含一些对实验结果的解释。
任务一：内存淘汰算法
这是测试数据使用三种算法执行后内存快照的输出，可以确保算法的正确性。
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 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 D:\Workspaces\ClionProjects\osnmb\cmake-build-debug\osnmb.exe 實驗： Windows 下的頁面淘汰算法模擬 基礎測試： 最佳置換算法（OPT）： ---------------------------------------------------------------------- 物理幀 虛擬頁 載入時間 最後使用 ---------------------------------------------------------------------- 第 0 條指令進行内存訪問： 虛擬頁[7] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 7 0 0 物理頁[1] INVALID INVALID INVALID 物理頁[2] INVALID INVALID INVALID ---------------------------------------------------------------------- 第 1 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 0 0 物理頁[1] * 0 1 1 物理頁[2] INVALID INVALID INVALID ---------------------------------------------------------------------- 第 2 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 0 0 物理頁[1] 0 1 1 物理頁[2] * 1 2 2 ---------------------------------------------------------------------- 第 3 條指令進行内存訪問： 虛擬頁[2] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 2 3 3 物理頁[1] 0 1 1 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 4 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 0 1 4 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 5 條指令進行内存訪問： 虛擬頁[3] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] 0 1 4 物理頁[2] * 3 5 5 ---------------------------------------------------------------------- 第 6 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 0 1 6 物理頁[2] 3 5 5 ---------------------------------------------------------------------- 第 7 條指令進行内存訪問： 虛擬頁[4] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 4 7 7 物理頁[2] 3 5 5 ---------------------------------------------------------------------- 第 8 條指令進行内存訪問： 虛擬頁[2] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] * 2 3 8 物理頁[1] 4 7 7 物理頁[2] 3 5 5 ---------------------------------------------------------------------- 第 9 條指令進行内存訪問： 虛擬頁[3] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 8 物理頁[1] 4 7 7 物理頁[2] * 3 5 9 ---------------------------------------------------------------------- 第 10 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 8 物理頁[1] * 0 10 10 物理頁[2] 3 5 9 ---------------------------------------------------------------------- 第 11 條指令進行内存訪問： 虛擬頁[3] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 8 物理頁[1] 0 10 10 物理頁[2] * 3 5 11 ---------------------------------------------------------------------- 第 12 條指令進行内存訪問： 虛擬頁[2] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] * 2 3 12 物理頁[1] 0 10 10 物理頁[2] 3 5 11 ---------------------------------------------------------------------- 第 13 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 12 物理頁[1] 0 10 10 物理頁[2] * 1 13 13 ---------------------------------------------------------------------- 第 14 條指令進行内存訪問： 虛擬頁[2] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] * 2 3 14 物理頁[1] 0 10 10 物理頁[2] 1 13 13 ---------------------------------------------------------------------- 第 15 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 14 物理頁[1] * 0 10 15 物理頁[2] 1 13 13 ---------------------------------------------------------------------- 第 16 條指令進行内存訪問： 虛擬頁[1] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 14 物理頁[1] 0 10 15 物理頁[2] * 1 13 16 ---------------------------------------------------------------------- 第 17 條指令進行内存訪問： 虛擬頁[7] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 7 17 17 物理頁[1] 0 10 15 物理頁[2] 1 13 16 ---------------------------------------------------------------------- 第 18 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 7 17 17 物理頁[1] * 0 10 18 物理頁[2] 1 13 16 ---------------------------------------------------------------------- 第 19 條指令進行内存訪問： 虛擬頁[1] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 7 17 17 物理頁[1] 0 10 18 物理頁[2] * 1 13 19 ---------------------------------------------------------------------- 命中率： 0.55 隊列置換算法（FIFO）： ---------------------------------------------------------------------- 物理幀 虛擬頁 載入時間 最後使用 ---------------------------------------------------------------------- 第 0 條指令進行内存訪問： 虛擬頁[7] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 7 0 0 物理頁[1] INVALID INVALID INVALID 物理頁[2] INVALID INVALID INVALID ---------------------------------------------------------------------- 第 1 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 0 0 物理頁[1] * 0 1 1 物理頁[2] INVALID INVALID INVALID ---------------------------------------------------------------------- 第 2 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 0 0 物理頁[1] 0 1 1 物理頁[2] * 1 2 2 ---------------------------------------------------------------------- 第 3 條指令進行内存訪問： 虛擬頁[2] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 2 3 3 物理頁[1] 0 1 1 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 4 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 0 1 4 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 5 條指令進行内存訪問： 虛擬頁[3] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 3 5 5 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 6 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] 3 5 5 物理頁[2] * 0 6 6 ---------------------------------------------------------------------- 第 7 條指令進行内存訪問： 虛擬頁[4] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 4 7 7 物理頁[1] 3 5 5 物理頁[2] 0 6 6 ---------------------------------------------------------------------- 第 8 條指令進行内存訪問： 虛擬頁[2] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 4 7 7 物理頁[1] * 2 8 8 物理頁[2] 0 6 6 ---------------------------------------------------------------------- 第 9 條指令進行内存訪問： 虛擬頁[3] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 4 7 7 物理頁[1] 2 8 8 物理頁[2] * 3 9 9 ---------------------------------------------------------------------- 第 10 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 0 10 10 物理頁[1] 2 8 8 物理頁[2] 3 9 9 ---------------------------------------------------------------------- 第 11 條指令進行内存訪問： 虛擬頁[3] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 0 10 10 物理頁[1] 2 8 8 物理頁[2] * 3 9 11 ---------------------------------------------------------------------- 第 12 條指令進行内存訪問： 虛擬頁[2] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 0 10 10 物理頁[1] * 2 8 12 物理頁[2] 3 9 11 ---------------------------------------------------------------------- 第 13 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 0 10 10 物理頁[1] * 1 13 13 物理頁[2] 3 9 11 ---------------------------------------------------------------------- 第 14 條指令進行内存訪問： 虛擬頁[2] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 0 10 10 物理頁[1] 1 13 13 物理頁[2] * 2 14 14 ---------------------------------------------------------------------- 第 15 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] * 0 10 15 物理頁[1] 1 13 13 物理頁[2] 2 14 14 ---------------------------------------------------------------------- 第 16 條指令進行内存訪問： 虛擬頁[1] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 0 10 15 物理頁[1] * 1 13 16 物理頁[2] 2 14 14 ---------------------------------------------------------------------- 第 17 條指令進行内存訪問： 虛擬頁[7] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 7 17 17 物理頁[1] 1 13 16 物理頁[2] 2 14 14 ---------------------------------------------------------------------- 第 18 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 17 17 物理頁[1] * 0 18 18 物理頁[2] 2 14 14 ---------------------------------------------------------------------- 第 19 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 17 17 物理頁[1] 0 18 18 物理頁[2] * 1 19 19 ---------------------------------------------------------------------- 命中率： 0.25 最近最久未使用置換算法（LRU）： ---------------------------------------------------------------------- 物理幀 虛擬頁 載入時間 最後使用 ---------------------------------------------------------------------- 第 0 條指令進行内存訪問： 虛擬頁[7] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 7 0 0 物理頁[1] INVALID INVALID INVALID 物理頁[2] INVALID INVALID INVALID ---------------------------------------------------------------------- 第 1 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 0 0 物理頁[1] * 0 1 1 物理頁[2] INVALID INVALID INVALID ---------------------------------------------------------------------- 第 2 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 7 0 0 物理頁[1] 0 1 1 物理頁[2] * 1 2 2 ---------------------------------------------------------------------- 第 3 條指令進行内存訪問： 虛擬頁[2] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 2 3 3 物理頁[1] 0 1 1 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 4 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 0 1 4 物理頁[2] 1 2 2 ---------------------------------------------------------------------- 第 5 條指令進行内存訪問： 虛擬頁[3] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] 0 1 4 物理頁[2] * 3 5 5 ---------------------------------------------------------------------- 第 6 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 2 3 3 物理頁[1] * 0 1 6 物理頁[2] 3 5 5 ---------------------------------------------------------------------- 第 7 條指令進行内存訪問： 虛擬頁[4] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 4 7 7 物理頁[1] 0 1 6 物理頁[2] 3 5 5 ---------------------------------------------------------------------- 第 8 條指令進行内存訪問： 虛擬頁[2] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 4 7 7 物理頁[1] 0 1 6 物理頁[2] * 2 8 8 ---------------------------------------------------------------------- 第 9 條指令進行内存訪問： 虛擬頁[3] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 4 7 7 物理頁[1] * 3 9 9 物理頁[2] 2 8 8 ---------------------------------------------------------------------- 第 10 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 0 10 10 物理頁[1] 3 9 9 物理頁[2] 2 8 8 ---------------------------------------------------------------------- 第 11 條指令進行内存訪問： 虛擬頁[3] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 0 10 10 物理頁[1] * 3 9 11 物理頁[2] 2 8 8 ---------------------------------------------------------------------- 第 12 條指令進行内存訪問： 虛擬頁[2] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 0 10 10 物理頁[1] 3 9 11 物理頁[2] * 2 8 12 ---------------------------------------------------------------------- 第 13 條指令進行内存訪問： 虛擬頁[1] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] * 1 13 13 物理頁[1] 3 9 11 物理頁[2] 2 8 12 ---------------------------------------------------------------------- 第 14 條指令進行内存訪問： 虛擬頁[2] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 1 13 13 物理頁[1] 3 9 11 物理頁[2] * 2 8 14 ---------------------------------------------------------------------- 第 15 條指令進行内存訪問： 虛擬頁[0] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 1 13 13 物理頁[1] * 0 15 15 物理頁[2] 2 8 14 ---------------------------------------------------------------------- 第 16 條指令進行内存訪問： 虛擬頁[1] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] * 1 13 16 物理頁[1] 0 15 15 物理頁[2] 2 8 14 ---------------------------------------------------------------------- 第 17 條指令進行内存訪問： 虛擬頁[7] 狀態：缺頁 ---------------------------------------------------------------------- 物理頁[0] 1 13 16 物理頁[1] 0 15 15 物理頁[2] * 7 17 17 ---------------------------------------------------------------------- 第 18 條指令進行内存訪問： 虛擬頁[0] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] 1 13 16 物理頁[1] * 0 15 18 物理頁[2] 7 17 17 ---------------------------------------------------------------------- 第 19 條指令進行内存訪問： 虛擬頁[1] 狀態：命中 ---------------------------------------------------------------------- 物理頁[0] * 1 13 19 物理頁[1] 0 15 18 物理頁[2] 7 17 17 ---------------------------------------------------------------------- 命中率： 0.4 自定義測試： 您可以使用源代碼中的 new_process 函數進行自定義測試。 實驗結束，程式將退出…… Process finished with exit code 0
执行了实验过程的测试之后，可以得到如下的输出：
4_1_1.png 可以看到 FIFO 算法的命中率是高于 LRU 的；对这种情况可以进行合理的解释之一是随机生成的指令不能代表实际指令的执行情况，并不具有实际指令频繁访问关键页面的特性，而更加的趋向于“均等”，从而导致了 FIFO 的算法的实验测试值高于 LRU 算法。
此外，即使物理内存和虚拟内存相等的情况下，命中率也无法达到 100%，是因为实验开始时内存被初始化为空，此时对任何页面的访问都是缺页的；这个极限值的大小取决于虚拟内存和指令条数的比例。
任务二：获得 Linux 变量的地址
在 WSL-CLion 环境下执行实验过程中描述并已经实现的代码，得到如下结果：
4_2_0.png 在 WSL 原生环境下执行代码，得到如下结果：
4_2_1.png 检查errno值之后，发现进程无法打开/proc/pid/pagemap文件；考虑到 WSL 实现的机制是将 Linux 程序的进程作为 Windows 进程挂载，可能没有包括这个部分的模拟。遂在同学的 Ubuntu 笔记本设备上执行代码，得到了如下的结果：
4_2_2.jpg 这说明了代码可以正常工作；也说明了 WSL 并不能和 Linux 等量齐观，进一步地加深了我对于 Windows 和 Linux 操作系统之间的差距的直观认知。
任务三：检查函数运行时间
五种方法分别是：标准库 time 函数、标准库 clock 函数、标准库 chrono 命名空间、Windows 的 QueryPerformanceCounter 函数、Windows 的 GetTickCount 函数。
4_3.png 可以看出第一种方法的准确度非常差。事实上 time 函数的精确度只到秒，而其他的方法的精确度都大于毫秒；出现这样的结果也在意料之中。
体会 通过本次上机实验，我了解了更多的 C++ 中的计时方法，拓宽了自己的视野；手动实现了经典的内存调度的页面置换（淘汰）算法，增进了自己对于三种经典算法的理解，也加深了对于内存调度优化这一概念的理解和认知。内存调度算法实际上也是将一些算法的思想融会贯通的产物；本次的实验还增进了我对于这些内存调度算法背后的算法思想有了更加深刻的认知。
此外，LRU 算法还有很多的优化方法，更加的拓宽了我的视野，让我更加的了解了当代计算机操作系统的一些实现方法；LRU 算法还广泛的利用于用户分层等多个生活中常见的生产场景中，增强了我对于这些抽象算法的理解，带来了更加直观的感受。
此外，在解决任务二程序在 WSL 上运行出现问题的问题的时候，我阅读了一些 API 相关的文档，加深了自己对于这些函数在 Linux 操作系统中运行过程的理解。
