devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统 实验9：页面置换算法模拟设计 （FIFO）（LRU)（OPT）（LFR）（NUR） --使用c++实现 （下）_opt置换算法模拟

作者：AllinToyou | 2024-02-29 04:25:26

赞

踩

opt置换算法模拟

目录

前言 

核心部分

 先进先出的算法（FIFO）

        代码

        运行

最近最久未使用算法（LRU)

        代码

        运行

最近最少访问页面算法（LFR）

        代码

        运行

最近未用过算法（NUR）

        代码

        运行

最佳页面置换算法（OPT）

        思路

        代码

        运行

前言 

        在上一篇简单介绍了5种算法，和代码总体的设计思路，与c++较c语言优势等。可以点击链接跳转：操作系统 实验9：页面置换算法模拟设计 （FIFO）（LRU)（OPT）（LFR）（NUR） --使用c++实现 （上） - CSDN App】

        这篇博客将深入去看这几种算法的实现，将剩余部分结束。

核心部分

 先进先出的算法（FIFO）

        代码

        这里有关链表的部分，不涉及增删，所以使用静态链表即可，通过索引进行访问。

        先进先出底层就是一个循环单指针队列，通过earliest 指针取余实现循环。一切都非常简单，这是最简单的也是最早出现的页面置换算法。

  1. class FIFO : public User
  2. {
  3. public:
  4.     FIFO(int memSize)
  5.         : User(memSize)
  6.     {
  7.     }
  8.  
  9.     bool Once(int incId) override
  10.     {
  11.         int pageId = incId / _1K_;
  12.         for (int i = 0; i < memoryCapacity; i++)
  13.         {
  14.             if (pageId == memory[i])
  15.             {
  16.                 haveRep = false;
  17.                 return haveRep;
  18.             }
  19.         }
  20.         lastRep = memory[earliest];
  21.         memory[earliest] = pageId;
  22.         haveRep = true;
  23.         lastRepNum = earliest;
  24.         earliest = (earliest + 1) % memoryCapacity;
  25.         return haveRep;
  26.     }
  27.  
  28. private:
  29.     int earliest = 0;
  30.  
  31. protected:
  32.     std::string Subjoin() const override
  33.     {
  34.         return std::string("\n(FIFO)  现在最早进入的页是第") +
  35.                std::to_string(earliest + 1) + "个";
  36.     }
  37. };

        运行

        主函数在上一篇博客中上过了，这里我直接放运行后的结果了。

最近最久未使用算法（LRU)

        代码

        故名思意，就是在内存当中距离现在-上一次访问在最早之前的页被替换掉，给每个节点定义了一个计时器，与先进先出的算法唯一的不一样就是，一个是选择进入时间最早，一个是选择等待时间最长，其他部分完全一样。

        需要注意的是先进先出算法因为是循环队列，所以完全可以只输出当前指针位置就行了，但是LRU如果只输出指针会非常不直观，所以就以表格对其的方式输出，美观又大气，一目了然。

  1. class LRU : public User // 最近最久未使用算法
  2. {
  3. public:
  4.     LRU(int memSize)
  5.         : User(memSize)
  6.         , time(new int[memSize])
  7.     {
  8.     }
  9.  
  10.     ~LRU()
  11.     {
  12.         delete[] time;
  13.     }
  14.  
  15.     bool Once(int incId) override
  16.     {
  17.         int pageId = incId / _1K_;
  18.         haveRep = true;
  19.         for (int i = 0; i < memoryCapacity; i++)
  20.         {
  21.             time[i]++;
  22.             if (pageId == memory[i])
  23.             {
  24.                 time[i] = 0;
  25.                 haveRep = false;
  26.             }
  27.         }
  28.         if (haveRep)
  29.         {
  30.             int repId = 0;
  31.             for (int i = 1; i < memoryCapacity; i++)
  32.             { // 找到访问时间间隔最大的进行替换
  33.                 if (time[i] > time[repId])
  34.                 {
  35.                     repId = i;
  36.                 }
  37.             }
  38.             lastRepNum = repId;
  39.             lastRep = memory[repId];
  40.             memory[repId] = pageId;
  41.             time[repId] = 0;
  42.         }
  43.         return haveRep;
  44.     }
  45.  
  46. private:
  47.     int* time; // 上次访问时间间隔
  48.  
  49. protected:
  50.     std::string Subjoin() const override
  51.     {
  52.         std::string str = "\n(LRU)";
  53.         int width = 3;
  54.         for (int i = 0; i < memoryCapacity; i++)
  55.         {
  56.             str += " | ";
  57.             std::string numberStr = std::to_string(time[i]);
  58.             int padding = 3 - numberStr.length();
  59.             str += std::string(padding, ' ') + numberStr;
  60.         }
  61.         return str + " |  (离上次访问时间)";
  62.     }
  63. };

        运行

最近最少访问页面算法（LFR）

        代码

        LFR和LRU同样也是非常相似，唯一的差别就是一个是记录上一次访问距离现在的时间，一个是记录访问次数。

        放在代码上看就是LRU是被访问的计数归0，其他都要+1，而LFR是被访问的次数+1，其他不变，最低的置换要置1 。

  1. class LFU : public User // 最少使用置换算法
  2. {
  3. public:
  4.     LFU(int memSize)
  5.         : User(memSize)
  6.         , times(new int[memSize])
  7.     {
  8.     }
  9.  
  10.     ~LFU()
  11.     {
  12.         delete[] times;
  13.     }
  14.  
  15.     bool Once(int incId) override
  16.     {
  17.         int pageId = incId / _1K_;
  18.         for (int i = 0; i < memoryCapacity; i++)
  19.         {
  20.             if (pageId == memory[i])
  21.             {
  22.                 times[i]++;
  23.                 haveRep = false;
  24.                 return haveRep;
  25.             }
  26.         }
  27.         int repId = 0;
  28.         for (int i = 1; i < memoryCapacity; i++)
  29.         { // 找到访问次数最少的进行替换
  30.             if (times[i] < times[repId])
  31.             {
  32.                 repId = i;
  33.             }
  34.         }
  35.         lastRepNum = repId;
  36.         lastRep = memory[repId];
  37.         memory[repId] = pageId;
  38.         times[repId] = 1;
  39.         haveRep = true;
  40.         return haveRep;
  41.     }
  42.  
  43. private:
  44.     int* times; // 访问次数
  45.  
  46. protected:
  47.     std::string Subjoin() const override
  48.     {
  49.         std::string str = "\n(LFU)";
  50.         int width = 3;
  51.         for (int i = 0; i < memoryCapacity; i++)
  52.         {
  53.             str += " | ";
  54.             std::string numberStr = std::to_string(times[i]);
  55.             int padding = 3 - numberStr.length();
  56.             str += std::string(padding, ' ') + numberStr;
  57.         }
  58.         return str + " |  (访问次数)";
  59.     }
  60. };

        运行

最近未用过算法（NUR）

        代码

         NUR算法是LFR的改版代码，LFR记录访问次数，而NUR是记录是否在前一个周期中访问过了。LFR的计数器是很多位，但是NUR的是标志位仅仅1位。NUR的一个周期是转一圈，和FIFO一样都是采用循环队列。

        NUR会循环遍历标志位，如果为1则清0，如果为0则置换。

  1. class NRU : public User // 最近未用算法
  2. {
  3. public:
  4.     NRU(int memSize)
  5.         : User(memSize)
  6.         , flag(new bool[memSize])
  7.         , last(0)
  8.     {
  9.         memset(flag, 0, sizeof(bool) * memSize);
  10.     }
  11.  
  12.     ~NRU()
  13.     {
  14.         delete[] flag;
  15.     }
  16.  
  17.     bool Once(int incId) override
  18.     {
  19.         int pageId = incId / _1K_;
  20.         for (int i = 0; i < memoryCapacity; i++)
  21.         {
  22.             if (pageId == memory[i])
  23.             {
  24.                 flag[i] = true;
  25.                 haveRep = false;
  26.                 return haveRep;
  27.             }
  28.         }
  29.         while (true)
  30.         {
  31.             last %= memoryCapacity;
  32.             for (; last < memoryCapacity; last++)
  33.             { // 找到标志位为0的进行替换
  34.                 if (!flag[last])
  35.                 {
  36.                     flag[last] = true;
  37.                     lastRepNum = last;
  38.                     lastRep = memory[last];
  39.                     memory[last] = pageId;
  40.                     haveRep = true;
  41.                     last++;
  42.                     return haveRep;
  43.                 }
  44.                 else
  45.                     flag[last] = false;
  46.             }
  47.         }
  48.     }
  49.  
  50. private:
  51.     bool* flag; // 访问标志位
  52.     int last;
  53.  
  54. protected:
  55.     std::string Subjoin() const override
  56.     {
  57.         std::string str = "\n(NRU)";
  58.         int width = 3;
  59.         for (int i = 0; i < memoryCapacity; i++)
  60.         {
  61.             str += " | ";
  62.             std::string numberStr = std::to_string(flag[i]);
  63.             int padding = 3 - numberStr.length();
  64.             str += std::string(padding, ' ') + numberStr;
  65.         }
  66.         return str + " |  (标志位)";
  67.     }
  68. };

        运行

最佳页面置换算法（OPT）

        最佳页面置换算法是一种基于未来的算法，它不可实现，但是可以作为评估其他页面置换算法的标准。

        选择在最久远未来才会访问的或者以后都不访问了的页进行置换，这样可以最大程度的命中，所以是”最佳“。

        前面的四种算法都是基于过去的，但是这个算法是基于未来的，所以参数需要将未来的所有指令序列传送进来，实现方法页比较复杂，也有其他方法实现，

        思路

        首先需要一个count计数直到当前已经执行到哪一条指令了，从当前指令向后遍历，每一个指令映射的页地址与内存中比较，是否有相同的，有相同的则将标志位标记上已经发现未来需要几步会执行到，直到仅剩下一个未标记的内存中的页，就是最远未来才会遇到的，可以替换掉。如果遍历到结束也没有标记满，说明未被标记的内存页以后再也不会访问，可以替换掉。

        代码

  1. class OPT : public User // 最近未用算法
  2. {
  3. public:
  4.     OPT(int memSize, IncSeq& incSeq)
  5.         : User(memSize)
  6.         , incSeq(incSeq)
  7.         , nextVst(new int[memSize])
  8.     {
  9.         memset(nextVst, -1, sizeof(int) * memoryCapacity);
  10.     }
  11.  
  12.     ~OPT()
  13.     {
  14.         delete[] nextVst;
  15.     }
  16.  
  17.     bool Once(int incId) override
  18.     {
  19.         ownCount++;
  20.         int pageId = incId / _1K_;
  21.         for (int i = 0; i < memoryCapacity; i++)
  22.         {
  23.             if (pageId == memory[i])
  24.             {
  25.                 haveRep = false;
  26.                 return haveRep;
  27.             }
  28.         }
  29.         NextVisit();
  30.         int repId = 0;
  31.         for (int i = 1; i < memoryCapacity; i++)
  32.         { // 找到最久后才访问的进行替换
  33.             if (nextVst[i] < nextVst[repId])
  34.             {
  35.                 repId = i;
  36.             }
  37.         }
  38.         lastRepNum = repId;
  39.         lastRep = memory[repId];
  40.         memory[repId] = pageId;
  41.         haveRep = true;
  42.         return haveRep;
  43.     }
  44.  
  45. private:
  46.     IncSeq& incSeq; // 指令序列
  47.     int* nextVst;
  48.     int ownCount = 0;
  49.  
  50.     void NextVisit()
  51.     {
  52.         memset(nextVst, -1, sizeof(int) * memoryCapacity);
  53.         bool flag[memoryCapacity];
  54.         memset(flag, 0, sizeof(bool) * memoryCapacity);
  55.         int num = memoryCapacity, ct = ownCount;
  56.         while (num != 1 && ct < incSeq.Size())
  57.         {
  58.             int page = incSeq[ct++] / _1K_;
  59.             for (int i = 0; i < memoryCapacity; i++)
  60.             {
  61.                 if (!flag[i] && page == memory[i])
  62.                 {
  63.                     flag[i] = true;
  64.                     nextVst[i] = ct - ownCount + 1;
  65.                     num--;
  66.                 }
  67.             }
  68.         }
  69.     }
  70.  
  71. protected:
  72.     std::string Subjoin() const override
  73.     {
  74.         for (int i = 0; i < memoryCapacity; i++)
  75.             if (nextVst[i] > 0)
  76.                 nextVst[i]--;
  77.             else if (nextVst[i] == 0)
  78.             {
  79.                 nextVst[i] = -2;
  80.                 for (int j = ownCount + 1; j < incSeq.Size(); j++)
  81.                 {
  82.  
  83.                     if (memory[i] == incSeq[j] / _1K_)
  84.                     {
  85.                         nextVst[i] = j - ownCount + 1;
  86.                         break;
  87.                     }
  88.                 }
  89.             }
  90.         if (haveRep)
  91.         {
  92.             nextVst[lastRepNum] = -1;
  93.             for (int i = ownCount + 1; i < incSeq.Size(); i++)
  94.             {
  95.  
  96.                 if (memory[lastRepNum] == incSeq[i] / _1K_)
  97.                 {
  98.                     nextVst[lastRepNum] = i - ownCount;
  99.                     break;
  100.                 }
  101.             }
  102.         }
  103.         std::string str = "\n(OPT)";
  104.         int width = 3;
  105.         for (int i = 0; i < memoryCapacity; i++)
  106.         {
  107.             str += " | ";
  108.             std::string numberStr = std::to_string(nextVst[i]);
  109.             int padding = 3 - numberStr.length();
  110.             str += std::string(padding, ' ') + numberStr;
  111.         }
  112.         return str + " |  (到下次访问的距离)";
  113.     }
  114. };

        运行

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号