实验4 内存管理

实验 4 内存管理 学校 学校 FJUT 学号 学号 3131903229 班级 计算机班级 计算机 1302 姓名 姜峰姓名 姜峰 注 其中注 其中 LFU 和和 NRU 算法运行结果可能与其他人不同 只是实现方式不算法运行结果可能与其他人不同 只是实现方式不 同 基本思路符合就可以 同 基本思路符合就可以 一一 实验学时与类型实验学时与类型 学时 2 课外学时 自定 实验类型 设计性实验 二二 实验目的实验目的 模拟实现请求页式存储管理中常用页面置换算法 理会操作系统对内存的调度管理 三三 实验内容实验内容 要求 各算法要给出详细流程图以及执行结果截图 假设有一程序某次运行访问的页面依次是 0 1 2 4 3 4 5 1 2 5 1 2 3 4 5 6 请给 出采用下列各页面置换算法时页面的换进换出情况 并计算各调度算法的命中率 命中率 非缺页次数 总访问次数 初始物理内存为空 物理内存可在 4 20 页中选择 1 FIFO 最先进入的页被淘汰 2 LRU 最近最少使用的页被淘汰 3 OPT 最不常用的页被淘汰 选做 4 LFU 访问次数最少的页被淘汰 LFU 选做 源代码 include include include include define MAXNUM 100 struct Phy Memory 定义一个物理内存结构体定义一个物理内存结构体 char Page int time char OutPut struct Phy Memory Phy Page void Print char PageStr int Phy PageNum int absence 打印图解函数打印图解函数 int i j for i 0 i strlen PageStr i printf c PageStr i printf n for i 0 i strlen PageStr i printf printf n for i 0 i Phy PageNum i for j 0 j strlen PageStr j printf c OutPut i strlen PageStr j printf n printf 缺页数为缺页数为 d n absence printf 总访问次数为总访问次数为 d n strlen PageStr printf 缺页率为缺页率为 2f n double absence strlen PageStr int IsExist char Temp int Phy PageNum 判断某页面是否存在于物理内存中判断某页面是否存在于物理内存中 int i for i 0 iPage Temp i if i Phy PageNum return i 1 找到返回此页面位置加找到返回此页面位置加 1 return 0 void FIFO char PageStr int Phy PageNum 利用时间计数器方式 还可以用栈来实现利用时间计数器方式 还可以用栈来实现 char Temp PageStr 定义定义 Temp 指针指向指针指向 PageStr 首地址首地址 int i num location absence 0 int Flag 0 定义一个标记变量 标记插入位置定义一个标记变量 标记插入位置 while Temp 0 页面未访问完页面未访问完 num 0 if FlagPage Temp Flag absence else 若物理内存已满若物理内存已满 if IsExist Temp Phy PageNum 若此页面未被访问若此页面未被访问 for i 0 i Flag i 找到驻留时间最长的页找到驻留时间最长的页 if numtime location i num Phy Page i time Phy Page location Page Temp Phy Page location time 0 absence for i 0 itime OutPut i strlen PageStr Temp PageStr Phy Page i Page Temp Print PageStr Phy PageNum absence void LRU char PageStr int Phy PageNum 依旧利用计数器方式 也可用栈来实现依旧利用计数器方式 也可用栈来实现 char Temp PageStr 定义定义 Temp 指针指向指针指向 PageStr 首地址首地址 int i num location absence 0 int Flag 0 定义一个标记变量 标记插入位置定义一个标记变量 标记插入位置 while Temp 0 页面未访问完页面未访问完 num 0 if Flagtime 0 else 若此页面未被访问若此页面未被访问 Phy Page Flag Page Temp Flag absence else 若物理内存已满若物理内存已满 if location IsExist Temp Phy PageNum 若此页面已被访问若此页面已被访问 Phy Page location 1 time 0 else 若此页面未被访问若此页面未被访问 for i 0 i Flag i 找到最近最久未使用的页找到最近最久未使用的页 if numtime location i num Phy Page i time Phy Page location Page Temp Phy Page location time 0 absence for i 0 itime OutPut i strlen PageStr Temp PageStr Phy Page i Page Temp Print PageStr Phy PageNum absence int Distance char PageStr char Temp char Now 计算距离函数 计算距离函数 OPT 算法中使用 算法中使用 int i for i 1 Temp i 0 i if Temp i 0 return i return INT MAX void OPT char PageStr int Phy PageNum 实际中无法实现 知道访问串后顺序遍历实际中无法实现 知道访问串后顺序遍历 char Temp PageStr 定义定义 Temp 指针指向指针指向 PageStr 首地址首地址 int i num Size location absence 0 int Flag 0 定义一个标记变量 标记插入位置定义一个标记变量 标记插入位置 while Temp 0 页面未访问完页面未访问完 num 0 if FlagPage Temp Flag absence else 若物理内存已满若物理内存已满 if IsExist Temp Phy PageNum 若此页面未被访问若此页面未被访问 for i 0 iPage 调用调用 distance 函数返回值为与当前位置物理页面相同页号的距离函数返回值为与当前位置物理页面相同页号的距离 if numPage Temp absence for i 0 iPage Temp Print PageStr Phy PageNum absence char Create char PageStr 根据访问串建立计数字符数组 根据访问串建立计数字符数组 LFU 算法使用 算法使用 int i j Size Num 0 char Temp1 Temp2 int length strlen PageStr char NowPage char malloc length for i 0 i length i NowPage i PageStr i Temp1 Temp2 NowPage while Temp1 NowPage length 1 去除访问串中重复串去除访问串中重复串 if Temp1 0 for Temp2 Temp1 1 Temp2 NowPage length 1 Temp2 if Temp1 Temp2 Temp2 0 Num Temp1 Size length Num char Count char malloc Size 2 for i 0 i length i 将不重复的访问页置于计数器中将不重复的访问页置于计数器中 if NowPage i 0 Count Size 1 NowPage i Size Size length Num for i Size i 2 Size i 计数位置零计数位置零 Count i 0 return Count void Add char Ptr char Str int Size 相应计数器加一 相应计数器加一 LFU 算法使用 算法使用 int i for i 0 Ptr i Str i Ptr i Size 1 int Find char Ptr char Str int Size 在计数器中找到相应页面并返回其计数值在计数器中找到相应页面并返回其计数值 LFU 算法使用 算法使用 int i for i 0 Ptr i Str i return Ptr i Size 0 void Zero char Ptr int Size 将所有计数器清零 将所有计数器清零 LFU 算法使用 算法使用 int i for i Size i 2 Size i Ptr i 0 void LFU char PageStr int Phy PageNum 对每一页面设置一个计数对每一页面设置一个计数 器 每次选出最小的淘汰器 每次选出最小的淘汰 char Temp PageStr 定义定义 Temp 指针指向指针指向 PageStr 首地址首地址 char Count Create PageStr int i Size time num location absence 0 int Flag 0 定义一个标记变量 标记插入位置定义一个标记变量 标记插入位置 Size strlen Count 2 while Temp 0 页面未访问完页面未访问完 num INT MAX if FlagPage Size else 若此页面未被访问若此页面未被访问 Phy Page Flag Page Temp Flag absence else 若物理内存已满若物理内存已满 if location IsExist Temp Phy PageNum 若此页面已被访问若此页面已被访问 Add Count Phy Page location 1 Page Size else 若此页面未被访问若此页面未被访问 for i 0 iPage Size if num time location i num time Phy Page location Page Temp Zero Count Size absence for i 0 iPage Temp int j 打印每次访问后的计数器值打印每次访问后的计数器值 for i 0 i 2 i for j 0 j Size j printf c Count i Size j printf n printf n Print PageStr Phy PageNum absence void NRU char PageStr int Phy PageNum 对每个物理页设置一个标识对每个物理页设置一个标识 0 1 用指针循环访问淘汰标识为零的页面 用指针循环访问淘汰标识为零的页面 char Temp PageStr 定义定义 Temp 指针指向指针指向 PageStr 首地址首地址 int i location absence 0 int Flag 0 定义一个标记变量 标记插入位置定义一个标记变量 标记插入位置 struct Phy Memory Clock Phy Page 定义一个结构体指针指向物理内存首地址定义一个结构体指针指向物理内存首地址 while Temp 0 页面未访问完页面未访问完 if Flagtime 1 else 若此页面未被访问若此页面未被访问 Phy Page Flag Page Temp Phy Page Flag time 1 Flag absence Clock if Clock Phy Page Phy PageNum Clock Phy Page else 若物理内存已满若物理内存已满 if location IsExist Temp Phy PageNum 若此页面已被访问若此页面已被访问 Phy Page location 1 time 1 else 若此页面未被访问若此页面未被访问 while Clock time Clock time 0 Clock if Clock Phy Page Phy PageNum Clock Phy Page Clock Page Temp Clock time 1 Clock if Clock Phy Page Phy PageNum Clock Phy Page absence for i 0 iPage Temp Print PageStr Phy PageNum absence int main char Str int i n Num Str char malloc MAXNUM printf 输入程序运行时访问的页面次序以及物理内存的分页数输入程序运行时访问的页面次序以及物理内存的分页数 n scanf s d Str Phy Page struct Phy Memory malloc Num sizeof struct Phy Memory 初初 始化物理内存结构体始化物理内存结构体 OutPut char malloc Num strlen Str for i 0 itime 0 printf 选择置换算法选择置换算法 n1 FIFO 2 LRU 3 OPT 4 LFU 5 NRU n scanf d switch n case 1 printf n 以下为以下为 FIFO 算法图解算法图解 n FIFO Str Num break case 2 printf n 以下为以下为 LRU 算法图解算法图解 n LRU Str Num break case 3 printf n 以下为以下为 OPT 算法图解算法图解 n OPT Str Num break case 4 printf n 以下为以下为 LFU 算法图解算法图解 n 各时期计数器如下各时期计数器如下 n LFU Str Num break case 5 printf n 以下为以下为 NRU 算法图解算法图解 n NRU Str Num break free Phy Page free OutPut return 0 注 这里只对分页数为注 这里只对分页数为 4 进行运行截图进行运行截图 实验截图 实验截图 FIFO 算法流程图 算法流程图 判断物理内存是否已满 判断此页面是否被访 问 判断此页面是否被访 问 未满已满 缺页中断 入内 存 缺页数加一 找到驻留时间最长 的一页淘汰并缺页 中断 将当前页面 入内存 此未时间 置0 缺页数加一 否 否 将所有物理内存页 面计数器加一 是 是 是否页面访问 完 结束 是 否 开始 LRU 算法流程图 算法流程图 判断物理内存是否已满 判断此页面是否被访 问 判断此页面是否被访 问 未满已满 缺页中断 入内 存 缺页数加一 找到时间最长的一 页淘汰并缺页中 断 将当前页面入 内存 此未时间置 0 缺页数加一 否 否 将所有物理内存页 面计数器加一 是 是 是否页面访问 完 结束 是 否 开始 当前物理页面计数 器清零 OPT 算法流程图 算法流程图 判断物理内存是否已满 判断此页面是否被访 问 判断此页面是否被访 问 未满已满 缺页中断 入内 存 缺页数加一 淘汰在访问串中将 来再也不会出现的 或离当前最远的位 置上出现的页并缺 页中断 将当前页 面入内存 缺页数 加一 否 否 是 是 是否页面访问 完 结束 是 否 开始 LFU 算法流程图 算法流程图 判断物理内存是否已满 判断此页面是否被访 问 判断此页面是否被访 问 未满已满 缺页中断 入内 存 缺页数加一 淘汰被访问次数最 少的一页并缺页中 断 将当前页面入 内 存 缺 页 数 加 一 所有计数器清 零 相应页面计数 器加一 否 否 是 是 是否页面访问 完 结束 是 否 开始 将此页面的相应计 数器加一 NRU 算法流程图 算法流程图 判断物理内存是否已满 判断此页面是否被访 问 判断此页面是否被访 问 未满已满 缺页中断 入内 存 当前位标识置 一 缺页数加一 指针下移 否 否 是 是 是否页面访问 完 结束 是 否 开始 此页面所在物理页 面对应的标识为置 1 指针不动 当前指针位标 识是否为1 当前位标识置0 指针下移 是 将指针指向的当前 位页面淘汰 并将 当前位标识置一 指针下移 缺页数 加一 否 四四 思考与总结思考与总结 1 针对上述页面访问顺序 请比较上述各页面置换算法的性能 对于访问顺序对于访问顺序 0 1 2 4 3 4 5 1 2 5 1 2 3 4 5 60 1 2 4 3 4 5 1 2 5 1 2 3 4 5 6 当分页数为当分页数为 4 4 时 时 随着分页数增加它们的缺页数均降低 随着分页数增加它们的缺页数均降低 FIFOFIFO 算法对此访问串无算法对此访问串无 BeladyBelady 现象 现象 OPTOPT 算法表现最好 实际上我们将算法表现最好 实际上我们将 OPTOPT 算法当做最优的评判标准 算法当做最优的评判标准 LRULRU 算法理论上是优于算法理论上是优于 FIFOFIFO 算法的 但此时缺页率却高于算法的 但此时缺页率却高于 FIFOFIFO 算法 主要是受访问串以算法 主要是受访问串以 及分页数的影响 只能说此访问串更适合及分页数的影响 只能说此访问串更适合 FIFOFIFO 算法 所以在实际中 我们要选择最适合的算法 所以