内存管理本文会结合下面的例题讲解先进先出算法和最近最久未经使用算法首先先对两种算法进行介绍1.先进先出 顾名思义 每一次都置换出最先进入物理块的页面2.最近最久未经使用 顾名思义 是置换出最先进入物理块或者最先被命中的页面 也就是最久未使用访问加入物理块或者被命中都算访问该页面接下来我们看一道例题例内存管理在一个请求分页系统中假定系统为进程分配了3个物理块。进程的页面访问顺序为1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。请分别采用先进先出FIFO 和最近最久未使用LRU置换算法计算各自产生的缺页次数和缺页率。假设初始时物理块均为空第一次访问即产生缺页这里我将用c和伪代码结合的形式讲解该题 本意是便于大家理解 解题的时候不用把这些写到试卷上 完整的答案会放在后面 也会附上完整的代码计算公式缺页率 缺页次数/访问总次数先进先出(FIFO)算法思路将其看成一个长度为3的数组根据物理块的数量决定本题中物理块数为3所以长度是3。将给定访问顺序中的元素与对应物理块的数组中的元素作比较如果不存在 依次存入数组最后一个元素并且缺页次数加一如果数组已满但是新元素不存在于当前数组中则将当前数组中最先进入的元素删除后续元素的索引依次 - 1 并且在末尾加入当前的新元素缺页次数也需要加一若该元素已经存在于数组之中则数组不需要变动。对比的顺序为题目中给出的页面访问顺序。最后根据缺页率 缺页次数/总次数的公式计算出缺页率根据上述原则 我们来看本题这里可以采用算法中先进先出、缓存数组的思想去理解这两个不一样 但是这样想可以更好的理解这个思路1.创建数组创建一个长度为3的空数组使用动态便于处理数据constintMAX_BUF3//限定长度vetorintv;intcount0;2.将序列中的数据与数组的数据进行比对 如果没有则加入有则维持原数组不变。加入时顺次放在数组的最后一个元素。若数组已满则将第一个元素删除并且将当前的数字放入数组。例如//访问1:1 1不存在于v中 那么记录为缺页 并且将1加入到数组中v.push_back(1);count;//访问2 2不存在于v中 那么记录为缺页 并且将2加入到数组中v.push_back(2);count;//访问3 3不存在于v中 那么记录为缺页 并且将3加入到数组中v.push_back(3);count;此时 数组中已经有了三个元素并且缺页次数为3此时 数组中的三个元素为1,2,3继续访问序列中的页访问4 4不存在于v中 那么记录缺页 但是原数组已经有了三个元素 则将最先进入的1删除 将4放到末尾 2、3顺次往前移 数组变更为2,3,4v.erase(v.begin());v.push_back(4);count;访问1 1不存在 记录为缺页 再次更新数组 数组变更为3,4,1v.erase(v.begin());v.push_back(1);count;访问2 2不存在 记录为缺页 再次更新 数组变更为4,1,2v.erase(v.begin());v.push_back(2);count;访问5 5不存在 记录为缺页 再次更新 数组变更为1,2,5v.erase(v.begin());v.push_back(5);count;访问1 数组中存在 命中 保持数组中的元素不变访问2 数组中存在 命中 保持数组中的元素不变访问3 3不存在 记录为缺页 再次更新 数组变更为2,5,3v.erase(v.begin());v.push_back(3);count;访问4 不存在 记录为缺页 再次更新 数组变更为5,3,4v.erase(v.begin());v.push_back(4);count;访问5 数组中存在 命中 保持元素不变3.统计未命中/缺页次数 共计9次 一共访问12次 所以结果为9/12 75%完整答案(考试的时候写这个就行FIFO先进先出算法 访问 1缺页物理块[1]- 缺页次数1 访问 2缺页物理块[1, 2]- 缺页次数2 访问 3缺页物理块[1, 2, 3]- 缺页次数3 访问 4缺页换出1物理块[2, 3, 4]- 缺页次数4 访问 1缺页换出2物理块[3, 4, 1]- 缺页次数5 访问 2缺页换出3物理块[4, 1, 2]- 缺页次数6 访问 5缺页换出4物理块[1, 2, 5]- 缺页次数7 访问 1命中物理块[1, 2, 5] 访问 2命中物理块[1, 2, 5] 访问 3缺页换出1物理块[2, 5, 3]- 缺页次数8 访问 4缺页换出2物理块[5, 3, 4]- 缺页次数9 访问 5命中物理块[5, 3, 4] 结果缺页次数 9缺页率 9/12 75%完整c代码上述代码是一步一步来的 比较繁琐 这里采用先进先出 完整写出该过程的c代码 便于大家理解该思路 不需要写到试卷上//经常写c的小伙伴如果为了省事头文件可以写万能头//也就是 #incluce bits/stdc.h#includeiostream#includevectorusingnamespacestd;//查找元素 存在返回索引 不存在返回-1intisExist(constvectorintv,intnum){for(inti0;iv.size();i){if(v[i]num){returni;}}return-1;}intmain(){//访问序列1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5vectorintv{1,2,3,4,1,2,5,1,2,3,4,5};//内存块固定长度3intMaxLen3;vectorintvec;intaddcount0;for(intnum:v){intposisExist(vec,num);if(pos!-1){// 内存中已存在该页面不操作continue;}// 缺页计数1addcount;if(vec.size()MaxLen){vec.push_back(num);}else{// 内存满淘汰最先进入的元素vec.erase(vec.begin());vec.push_back(num);}}cout缺页次数addcountendl;return0;}输出结果缺页次数9最近最久未使用LRU置换算法思路将其看成一个长度为3的数组根据物理块的数量决定本题中物理块数为3所以长度是3。将给定访问顺序中的元素与对应物理块的数组中的元素作比较如果不存在 依次存入数组最后一个元素并且缺页次数加一如果数组已满但是新元素不存在于当前数组中则将当前数组中最久没有被访问也就是最久没有被命中的元素删除后续元素的索引依次 - 1 并且在末尾加入当前的新元素缺页次数也需要加一若该元素已经存在于数组之中则将该元素挪至数组的末尾保证第一个元素就是最久未被访问的元素 便于处理物理块中的数据。对比的顺序为题目中给出的页面访问顺序。1.创建数组创建一个长度为3的空数组使用动态数组便于处理数据constintMAX_BUF3//限定长度vetorintv;intcount0;2.将序列中的数据与数组的数据进行比对 如果没有则加入有则维持原数组不变。加入时顺次放在数组的最后一个元素。若数组已满则将第一个元素删除并且将当前的数字放入数组。例如访问 1不存在于v中 缺页v.push_back(1);count;访问 2不存在于v中 缺页v.push_back(2);count;访问 3不存在于v中 缺页v.push_back(3);count;3.现在数组中已经有了三个元素 分别为1,2,3 但是4不存在由于1是最先加入数组 也就是最久未被访问的 所以删除1后面元素索引-1 并且将4加入到数组中这里虽然和刚刚先进先出操作相同 但是原理是不一样 大家注意区分更新之后的数组为2,3,4v.erase(v.begin());v.push_back(4);count;继续往后访问1 1不存在 同理 删除数组中最久未被访问的元素2 并且将1加入数组中 更新之后的数组为3,4,1v.erase(v.begin());v.push_back(1);count;继续访问2 2不存在 删除中最久未被访问的3 将2存入数组 更新之后的数组为4,1,2v.erase(v.begin());v.push_back(2);count;继续访问5 5不存在 删除最久未被访问的4 将5存入数组 更新之后的数组为1,2,5v.erase(v.begin());v.push_back(5);count;继续访问1 1 存在 更新使用顺序为{2,5,1}1刚刚被命中了 所以是最近被使用的 接下来是5 最久未被使用的是2 所以顺序更新为251继续访问2 同理 更新为{5,1,2}继续访问3 3不存在 删除最久未被访问的5 将3存入数组 更新之后的数组为1,2,3v.erase(v.begin());v.push_back(3);count;继续访问4 4不存在 删除最久未被访问的1 将4存入数组 更新之后的数组为2,3,4v.erase(v.begin());v.push_back(4);count;继续访问5 5不存在 删除最久未被访问的2 将5存入数组 更新之后的数组为3,4,5v.erase(v.begin());v.push_back(5);count;4.统计未命中/缺页次数 共计10次 一共访问12次 所以结果为10/12 ≈ 83.3%完整答案考试这么写就行了 代码是辅助理解的LRU最近最久未使用算法 访问 1缺页物理块[1]- 缺页次数1 访问 2缺页物理块[1, 2]- 缺页次数2 访问 3缺页物理块[1, 2, 3]- 缺页次数3 访问 4缺页淘汰最久未用的1物理块[2, 3, 4]- 缺页次数4 访问 1缺页淘汰最久未用的2物理块[3, 4, 1]- 缺页次数5 访问 2缺页淘汰最久未用的3物理块[4, 1, 2]- 缺页次数6 访问 5缺页淘汰最久未用的4物理块[1, 2, 5]- 缺页次数7 访问 1命中更新使用顺序物理块[2, 5, 1] 访问 2命中更新使用顺序物理块[5, 1, 2] 访问 3缺页淘汰最久未用的5物理块[1, 2, 3]- 缺页次数8 访问 4缺页淘汰最久未用的1物理块[2, 3, 4]- 缺页次数9 访问 5缺页淘汰最久未用的2物理块[3, 4, 5]- 缺页次数10 结果缺页次数 10缺页率 10/12 ≈ 83.3%完整代码//经常写c的小伙伴如果为了省事头文件可以写万能头 //也就是#inclucebits/stdc.h#includeiostream#includevectorusingnamespacestd;// 查找元素存在返回下标不存在返回 -1intisExist(constvectorintbuf,inttarget){for(inti0;ibuf.size();i){if(buf[i]target)returni;}return-1;}intmain(){//访问序列1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5vectorintv{1,2,3,4,1,2,5,1,2,3,4,5};//内存块固定长度3intMaxLen3;vectorintvec;intaddcount0;// 3. 遍历每个访问元素执行LRU最近最久未使用算法for(intnum:v){intidxisExist(vec,num);if(idx-1){// 情况1元素不存在缺页计数1addcount;if(vec.size()MaxLen){// 缓存未满直接尾部存入vec.push_back(num);}else{// 缓存已满删除最久未使用的队首元素其余索引自动-1vec.erase(vec.begin());vec.push_back(num);}}else{// 情况2元素已存在若不在末尾挪到末尾刷新使用时间if(idx!vec.size()-1){vec.erase(vec.begin()idx);vec.push_back(num);}// 如果本身就在末尾无需操作}}// 输出运行结果cout缺页新增元素总次数addcountendl;return0;}