操作系统实验报告
——（存储器管理实验）
一、实验目的
（1） 理解内存页面调度的机理
（2）掌握几种理论页面置换算法的实现方法 （3）了解HASH数据结构的使用
（4）通过实验比较几种调度算法的性能优劣
页面置换算法是虚拟存储管理实现的关键，通过本次实验理解内存页面调度的机制，在模拟实现FIFO、LRU、NRU和OPT几种经典页面置换算法的基础上，比较各种页面置换算法的效率及优缺点，从而了解虚拟存储实现的过程。
二、实验内容
对比以下几种算法的命中率：
（1）先进先出算法FIFO（First In First Out） （2）最近最少使用算法LRU（Least Recently Used） （3）最近未使用算法NUR（Never Used Recently） （4）最佳置换算法OPT（Optimal Replacement）
三、实验原理
1. FIFO算法
a)
在分配内存页面数（AP）小天进程页面数（PP）时，当然是最先运行的AP个页面放入内存；
b)
这时又需要处理新的页面，则将原来放的内存中的AP个页中最先进入的调出（FIFO），再将新页面放入；
以后如果再有新页面需要调入，则都按上述规则进行。
算法特点：所使用的内存页面构成一个队列。
2. LRU算法
（1）当内存分配页面数（AP）小于进程页面数（PP）时，把最先执行的AP个页面放入内存。
（2）当需调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那一页调出，以空出内存来放置新调入的页面（LRU）。
算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。
3. NUR算法
所谓“最近未使用”，首先是要对“近”做一个界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面。那么可能会有以下几种情况：
（1）如果这样的页面只有一个，就将其换出，放入需要处理的新页面。
（2）如果有这样的页面不止一个，就在这些页面中任取一个换出（可以是下标最小的或者最小的），放入需要处理的页面。
（3）如果没有一个这样的页面，就随意换出一个页面（可以是下标最小的或者最大的）。 算法特点：有一个循环周期，每到达这个周期，所有页面存放是否被CPU处理的信息的属性均被置于初始态（没有被访问）。
4. OPT算法
所谓的最佳算法是一种理想状况下的算法，它要求先遍历所有的CPU待处理的进程页面序列。在这些页面中，如果有些已经在内存中，而CPU不再处理的，就将其换出；而有些页面已在内存中而CPU即将处理，就从当前位置算起，取最后才会处理到的页面，将其换出。如CPU待处理的页面序列为： 1 3 2 2 4 5 2 5 1 4 3 4 1 1 5 5 3 4 2 1 如果已经处理了前5个页面（底纹为黑色），那么随后的页面5是第一个待处理的页面，这时若要将页面5调入内存，需选择页面3换出，因为页面3 是最后才会被处理到的。
四、设计与实现
1. FIFO算法 算法实现：
total_instruction来记录页面总共使用的次数，此外
还需要一个变量记录总共换入页面的次数diseffect（需要换出页面总是因为缺页中断而产生）。利用公式1-diseffect / total_instruction*100% 可以得到命中率。
（1） 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（这个序列由page[ap]的下标随机构成）表示待处理的进程页面顺序，diseffect置0。
（2） 看main[]中是否有下一个元素，若有，就由main[]中获取该页面下标，并转（3），如果没有则转（7）。
（3） 如果该页已在内存中，就转（2），否则转（4），同时未命中的diseffect加1。 （4） 观察pagecontrol是否占满，如果占满则须将使用队列（在第（6）步中建立的）中最先进入的（就是队列的第一个单元）pagecontrol单元“清干净”，同时将page[]单元置为“不在内存中”。
（5） 将该page[]与pagecontrol[]建立对应关系（可以改变pagecontrol[]的标志位，也可以采用指针链接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，二是哪个page[]单元使用的。page[]单元也包含两个信息：对应的pagecontrol单元号和本page[]单元已在内存中）。
（6） 将用到的pagecontrol置入使用队列（这里的队列是一种FIFO的数据结构），返回（2）。 （7） 显示计算1-diseffect / total_instruction*100%，完成。
2.LRU算法 算法实现：
与前述算法一样，只有先得到diseffect才能获得最终的命中率。
（1） 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分
配的页面数，并产生一个随机数序列main[total_instruction]（这个序列由page[ap]的下标随机构成）表示待处理的进程页面顺序，diseffect置0。
（2） 看序列main[]中是否有下一个元素，如果有，就由main[]中获取该页面下标，
并转（3），如果没有则转（6）。
（3） 如果该page[]单元在内存中便改变页面属性，使它保留“最近使用”的信息，转
（2），否则转（4），同时diseffect加1。
（4） 看是否有空闲页面，如果有，就返回页面指针，并转到（5），否则，在内存页
“清干净”，并返回该页面指针。
（5） 在需处理的page[]与（4）中得到的pagecontrol[]之间建立联系，同时让对应的
page[]单元保存“最新使用”的信息，转（2）。
（6） 如果序列处理完成，就输出计算1-diseffect / total_instruction*100%的结果，完成。
3.NUR算法 算法实现：
（1） 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分
配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]德下标随机构成）表示待处理的进程页面顺序，diseffect置0，设定循环周期CLEAR_PERIOD。
（2） 看main[]是否有下一个元素。若有，就从main[]中获得一个CPU将处理页面的
序号；如果没有就转到（8）。
（3） 如果待处理的页面在内存中，就转到（2）；否则diseffect加1，并转到（4）。 （4） 看是否有空闲得内存页面，如果有，返回空闲内存页面指针，并转到（5）；否则，在所有没有被访问且位于内存中的页面中按任意规则（或者取最近的一个页面；或者取下标最小的……）取出一个，返回清空后的内存页面指针。
（5） 在待处理进程页面与内存页面之间建立联系，并标注该页被访问。 （6） 如果CPU已处理了CLEAR_PERIOD个页面，就将所有页面均设为“未访问”。 （7） 返回（2）。
（8） 如果CPU所有处理工作完成，就返回1-(disaffect / total_instruction )*100%的结果，并结束。
4.OPT算法 算法实现：
为每个进程页面设一个“间隔”属性cDistance表示CPU将在第几步处理到该页面，如果页面不再被CPU处理，可以被设为某个很大的值（如32767），这样每次被换出的就是cDistance最大的那个页面。
（1） 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分
main[total_instruction]（这个序列由page[ap]
的下标随机构成）表示待处理的进程页面顺序，diseffect置0。然后扫描整个页面访问序列，对cDistance[TOTAL_VP]数组进行赋值，表示该页面将在第几步被处理。
（2） 看序列main[]中是否有下一个元素，如果有，就由main[]中获取一个CPU待处
理的页面号，并转（3），如果没有则转（6）。
（3） 如果该页面已经在内存中了，就转（2），否则转（4），同时diseffect加1。 （4） 看是否有空闲页面，如果有，就返回页面指针，并转到（5），否则，遍历所有
未处理的进程页面序列，如果有位于内存中的页面而以后CPU不再处理的，首将其换出，返回页面指针；如果没有这样的页面，找出CPU将最晚处理的页面，将其换出，并返回该页面指针。
（5） 在内存页面和待处理的进程页面之间建立联系，转（2）。
（6） 输出计算1-diseffect / total_instruction*100%的结果，完成。
五、实验结果
六、结果分析
以FIFO算法为例进行分析：
总共有7个页面，可用来存储的物理块数为3。系统随机生成7个页面，依次为6,2,6,8,4,10,5，共发生4次页面置换，缺页次数为4，缺页率为4/7=0.571429，命中率为1-0.571429=0.428571。
七、实验总结
通过本次实验，我更好的理解了四种页面置换算法的实现方法及其核心思想，增强了运用四种页面置换算法的解决页面置换的能力，同时也通过对四种页面置换算法的比较和总结，发现一般情况下OPT（最佳页面置换算法）的命中率最高，FIFO算法最简单也最轻易实现，性能相对最好。总之这次试验加深了我对本章的理解和掌握。
因篇幅问题不能全部显示，请点此查看更多更全内容