页面调度算法实现
实验目的
理解操作系统中的几种页面调度算法，尝试用 C++ 语言实现它们。
步骤
重要的数据结构
1 |
|
1 |
|
算法示意
- 初始化。设置两个数组
page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面顺序，diseffect置 0。 - 看
main[]中是否有下一个元素，有就由main[]中获取该页面下标，并转到 3；没有，就转到 7。 - 如果该
page页已在内存中，就转到 2；否则就到 4，同时未命中的diseffect加 1。 - 观察
pagecontrol是否占满，如果占满需将使用队列（6 中建立的）中最先进入的（就是队列第一个单元）pagecontrol单元 “清干净”，同时将对应的page[]单元置为 “不在内存中”。 - 将该
page[]与pagecontrol[]建立关系（可以改变pagecontrol[]的标示位，也可以采用指针连接。总之，至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，二是哪个page[]单元使用的；page[]单元包含两个信息：对应的pagecontrol单元号、本page[]单元已在内存中）； - 将用到的
pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构），返回 2； - 显示命中率，算法完成。
graph TD
A(["初始化"]) --> B{"main[] 中是否有下一个元素"} B --> |Y|C["由main获取下一个元素页面下标"]
B --> |N|D(["显示命中率，算法完成"])
C --> E{"该页是否在内存中"} E --> |Y|B E --> |N|F["diseffect++"]
F --> G{Pagecontrol是否占满} G --> |Y|H["将最先进入的单元清干净，并重置状态"]
G --> |N|I["建立page和pagecontrol的关系"]
H --> I I --> J["用到的Pagecontrol置入使用队列"]
J --> B
1 | void CMemory::FIFO(const int nTotal_pf){ |
易于实现
容易淘汰常用页面
- 初始化。主要是进程页面
page[]和分配的内存页面pagecontrol[]，同时产生随机序列main[]，diseffect置 0。 - 看序列
main[]是否有下一个元素，有就由main[]中获取该页面下标，并转到 3；没有，就转到 6。 - 如果该
page页已在内存中，便改变页面属性，使它保留 “最近使用” 的信息，转到 2；否则就到 4，同时未命中的diseffect加 1。 - 判断是否有空闲的内存页面，如果有，就返回页指针，转到 5；否则在内存页面中找出最长时间没有使用到的页面，将其 “清干净”，并返回该页面指针。
- 在需要处理的
page[]与 4 中得到的pagecontrol[]建立关系，同时让对应的page[]单元保存 “最新使用” 的信息，返回 2； - 如果序列处理完成，就输出命中率，算法结束。
graph TD
A(["初始化"]) --> B{"main[] 中是否有下一个元素"} B --> |Y|C["由main获取下一个元素页面下标"]
B --> |N|D(["显示命中率，算法完成"])
C --> E{"该页是否在内存中"} E --> |Y|E_1["修改页面属性，使它保留“最近使用”的信息"]
E_1 --> B E --> |N|F["diseffect++"]
F --> G{是否有空闲页面} G --> |Y|H["返回该页面指针"]
G --> |N|I["在内存页面中找出最长时间没有使用到的页面,将其清理"]
I --> H H --> J[内存页面和待处理的进程页面建立关系,对应单元保存最新使用信息]
J --> B
1 | void CMemory::LRU(const int nTotal_pf){ |
页面利用率有显著提升
代价很大
- 初始化。设置两个数组
page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面顺序，diseffect置 0，设定循环周期CLEAR_PERIOD。 - 看
main[]中是否有下一个元素，有就从main[]中获得一个 CPU 将处理页面的序号；没有，就转到 8。 - 如果待处理的页面已在内存中，就转到 2；否则
diseffect加 1，并转到 4。 - 看是否有空闲的内存页面，如果有，返回空闲页面指针，转到 5；否则，在所有没有被访问且位于内存中的页面中按任意规则（或者取最近的一个页面；或者取下标最小的页面，等等）取出一个，返回清空后的内存页面指针。
- 在待处理进程页面与内存页面之间建立联系，并标注该页面被访问。
- 如果 CPU 已处理了
CLEAR_PERIOD个页面，就将所有页面均设为 “未访问”。 - 返回 2。
- 如果 CPU 所有处理工作完成，就返回命中率的结果，算法结束。
graph TD
A(["初始化"]) --> B{"main[] 中是否有下一个元素"} B --> |Y|C["由main获取下一个元素页面下标"]
B --> |N|D(["显示命中率，算法完成"])
C --> E{"该页是否在内存中"} E --> B E --> |N|F["diseffect++"]
F --> G{是否有空闲页面} G --> |Y|H["返回该页面指针"]
G --> |N|I["在所有没有被访问且位于内存中的页面中按任意规则（或者取最近的一个页面；或者取下标最小的页面，等等）取出一个"]
I --> H H --> J[内存页面和待处理的进程页面建立关系,标注页面被访问]
J --> K{"CPU已经处理了CLEAR_PERIOD个页面"} K --> |N|B K --> |Y|B'["将所有页面设置为'未访问'"]
B'--> B
1 | void CMemory::NRU(const int nTotal_pf) { |
易于理解，容易实现。
- 初始化。设置两个数组
page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]
的下标随机构成），表示待处理的进程页面顺序，diseffect置 0。然后扫描整个页面访问序列，对vDistance[TOTAL_VP]数组进行赋值，表示该页面将在第几步被处理。 - 看
main[]中是否有下一个元素，有就从main[]中获取一个 CPU 待处理的页面号；没有，就转到 6。 - 如果该
page页已在内存中，就转到 2；否则就到 4，同时未命中的diseffect加 1。 - 看是否有空闲的内存页面。如果有，就直接返回该页面指针。如果没有，遍历所有未处理的进程页面序列，如果有位于内存中的页面，而以后 CPU 不再处理，首先将其换出，返回页面指针；如果没有这样的页面，找出 CPU 最晚处理到的页面，将其换出，返回该内存页面指针。
- 在内存页面和待处理的进程页面之间建立联系，返回 2。
- 输出命中率，算法结束。（命中率在扫描时完成计算）
从以上算法描述中，可以看出，OPT 是一种理想化的算法，因为操作系统中页面处理顺序是不一定的，所以页面将在哪一步被处理是不可预测的。但是，可以以此为标准来评价其他页面置换算法。
graph TD
A(["初始化"]) --> B{"main[] 中是否有下一个元素"} B --> |Y|C["由main获取下一个元素页面下标"]
B --> |N|D(["显示命中率，算法完成"])
C --> E{"该页是否在内存中"} E --> |Y|B E --> |N|F["diseffect++"]
F --> G{是否有空闲页面} G --> |Y|H["返回该页面指针"]
G --> |N|I["遍历所有未处理的进程页面序列"]
I --> J{"存在位于内存中的页面，而以后CPU不再处理"} J --> |Y|K[将其换出]
J --> |N|L[找出CPU最晚处理到的页面]
L --> K K --> H H --> M[内存页面和待处理的进程页面建立关系]
M --> B
1 | void CMemory::OPT(const int nTotal_pf) |
实验关键里程碑数据与结果
用 g++ 编译 kernel.cpp，运行截图如下 
可以看到，随着页面数的增多，FIFO、LRU、NRU 三种算法的命中率无限趋近于 OPT 算法，且每一种算法的命中率都在单调上升。（第三列输出写错成 NUR 了）
实验难点与收获
这次实验仍然是编程，主要是使用了 C++ 语言，借助类和结构体实现了常见的页面置换算法。实现过程中主要的困难是将算法语言表示转化为代码语言，需要考虑的东西有很多。通过对于实验结果的观察，我对于页面置换算法有了更加直观的理解，了解到其随所处理页面数的增加，命中率也在增加，FIFO、LRU、NRU 三种算法各有利弊，总体来说，它们都是操作系统中较为常用的页面置换算法。
实验思考
其实这个实验只是模拟了页面比较少的时候，几种页面置换算法的准确率变化，页面置换的顺序也都是随机生成的序列。实际上，我们的操作系统所要操作的页面情况远比模拟情况要复杂，命中率的上升可能也不会是单调的。
如果在输出中加上每次生成的操作序列和每次换入换出的情况的话，就会更加直观了，准确率从何而来也能看得更加清楚了。