SHARE
TWEET

Offline Paging Example

goeddek Nov 26th, 2016 170 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <memory>
  3.  
  4. using namespace std;
  5.  
  6. const int cacheSize     = 3;
  7. const int requestLength = 16;
  8.  
  9. const char request[]    = {'a','a','d','e','b','b','a','c','f','d','e','a','f','b','e','c'};
  10. char cache[]            = {'a','b','c'};
  11.  
  12. // for reset
  13. char originalCache[]    = {'a','b','c'};
  14.  
  15. // character for empty page
  16. char emptyPage          = 'X';
  17.  
  18. class Strategy {
  19.  
  20. public:
  21.     Strategy(std::string name) : strategyName(name) {}
  22.     virtual ~Strategy() = default;
  23.  
  24.     // calculate which cache place should be used
  25.     virtual int apply(int requestIndex)                                     = 0;
  26.  
  27.     // updates information the strategy needs
  28.     virtual void update(int cachePlace, int requestIndex, bool cacheMiss)   = 0;
  29.  
  30.     const std::string strategyName;
  31. };
  32.  
  33. bool updateCache(int requestIndex, Strategy* strategy)
  34. {
  35.     // calculate where to put request
  36.     int cachePlace = strategy->apply(requestIndex);
  37.  
  38.     // proof whether its a cache hit or a cache miss
  39.     bool isMiss = (request[requestIndex] != cache[cachePlace]) && (cache[cachePlace] != emptyPage);
  40.  
  41.     // update strategy (for example recount distances)
  42.     strategy->update(cachePlace, requestIndex, isMiss);
  43.  
  44.     // write to cache
  45.     cache[cachePlace] = request[requestIndex];
  46.  
  47.     return isMiss;
  48. }
  49.  
  50. class FIFO : public Strategy {
  51. public:
  52.     FIFO() : Strategy("FIFO")
  53.     {
  54.         for (int i=0; i<cacheSize; ++i) age[i] = 0;
  55.     }
  56.  
  57.     int apply(int requestIndex) override
  58.     {
  59.         int oldest = 0;
  60.  
  61.         for(int i=0; i<cacheSize; ++i)
  62.         {
  63.             if(cache[i] == request[requestIndex])
  64.                 return i;
  65.  
  66.             else if(age[i] > age[oldest])
  67.                 oldest = i;
  68.         }
  69.  
  70.         return oldest;
  71.     }
  72.  
  73.     void update(int cachePos, int requestIndex, bool cacheMiss) override
  74.     {
  75.         // nothing changed we dont need to update the ages
  76.         if(!cacheMiss)
  77.             return;
  78.  
  79.         // all old pages get older, the new one get 0
  80.         for(int i=0; i<cacheSize; ++i)
  81.         {
  82.             if(i != cachePos)
  83.                 age[i]++;
  84.  
  85.             else
  86.                 age[i] = 0;
  87.         }
  88.     }
  89.  
  90. private:
  91.     int age[cacheSize];
  92. };
  93.  
  94. class LIFO : public Strategy {
  95. public:
  96.     LIFO() : Strategy("LIFO")
  97.     {
  98.         for (int i=0; i<cacheSize; ++i) age[i] = 0;
  99.     }
  100.  
  101.     int apply(int requestIndex) override
  102.     {
  103.         int newest = 0;
  104.  
  105.         for(int i=0; i<cacheSize; ++i)
  106.         {
  107.             if(cache[i] == request[requestIndex])
  108.                 return i;
  109.  
  110.             else if(age[i] < age[newest])
  111.                 newest = i;
  112.         }
  113.  
  114.         return newest;
  115.     }
  116.  
  117.     void update(int cachePos, int requestIndex, bool cacheMiss) override
  118.     {
  119.         // nothing changed we dont need to update the ages
  120.         if(!cacheMiss)
  121.             return;
  122.  
  123.         // all old pages get older, the new one get 0
  124.         for(int i=0; i<cacheSize; ++i)
  125.         {
  126.             if(i != cachePos)
  127.                 age[i]++;
  128.  
  129.             else
  130.                 age[i] = 0;
  131.         }
  132.     }
  133.  
  134. private:
  135.     int age[cacheSize];
  136. };
  137.  
  138. class LRU : public Strategy {
  139. public:
  140.     LRU() : Strategy("LRU")
  141.     {
  142.         for (int i=0; i<cacheSize; ++i) age[i] = 0;
  143.     }
  144.  
  145.     // here oldest mean not used the longest
  146.     int apply(int requestIndex) override
  147.     {
  148.         int oldest = 0;
  149.  
  150.         for(int i=0; i<cacheSize; ++i)
  151.         {
  152.             if(cache[i] == request[requestIndex])
  153.                 return i;
  154.  
  155.             else if(age[i] > age[oldest])
  156.                 oldest = i;
  157.         }
  158.  
  159.         return oldest;
  160.     }
  161.  
  162.     void update(int cachePos, int requestIndex, bool cacheMiss) override
  163.     {
  164.         // all old pages get older, the used one get 0
  165.         for(int i=0; i<cacheSize; ++i)
  166.         {
  167.             if(i != cachePos)
  168.                 age[i]++;
  169.  
  170.             else
  171.                 age[i] = 0;
  172.         }
  173.     }
  174.  
  175. private:
  176.     int age[cacheSize];
  177. };
  178.  
  179. class LFU : public Strategy {
  180. public:
  181.     LFU() : Strategy("LFU")
  182.     {
  183.         for (int i=0; i<cacheSize; ++i) requestFrequency[i] = 0;
  184.     }
  185.  
  186.     int apply(int requestIndex) override
  187.     {
  188.         int least = 0;
  189.  
  190.         for(int i=0; i<cacheSize; ++i)
  191.         {
  192.             if(cache[i] == request[requestIndex])
  193.                 return i;
  194.  
  195.             else if(requestFrequency[i] < requestFrequency[least])
  196.                 least = i;
  197.         }
  198.  
  199.         return least;
  200.     }
  201.  
  202.     void update(int cachePos, int requestIndex, bool cacheMiss) override
  203.     {
  204.         if(cacheMiss)
  205.             requestFrequency[cachePos] = 1;
  206.  
  207.         else
  208.             ++requestFrequency[cachePos];
  209.     }
  210.  
  211. private:
  212.  
  213.     // how frequently was the page used
  214.     int requestFrequency[cacheSize];
  215. };
  216.  
  217. class LFD : public Strategy {
  218. public:
  219.     LFD() : Strategy("LFD")
  220.     {
  221.         // precalc next usage before starting to fullfill requests
  222.         for (int i=0; i<cacheSize; ++i) nextUse[i] = calcNextUse(-1, cache[i]);
  223.     }
  224.  
  225.     int apply(int requestIndex) override
  226.     {
  227.         int latest = 0;
  228.  
  229.         for(int i=0; i<cacheSize; ++i)
  230.         {
  231.             if(cache[i] == request[requestIndex])
  232.                 return i;
  233.  
  234.             else if(nextUse[i] > nextUse[latest])
  235.                 latest = i;
  236.         }
  237.  
  238.         return latest;
  239.     }
  240.  
  241.     void update(int cachePos, int requestIndex, bool cacheMiss) override
  242.     {
  243.             nextUse[cachePos] = calcNextUse(requestIndex, cache[cachePos]);
  244.     }
  245.  
  246. private:
  247.  
  248.     int calcNextUse(int requestPosition, char pageItem)
  249.     {
  250.         for(int i = requestPosition+1; i < requestLength; ++i)
  251.         {
  252.             if (request[i] == pageItem)
  253.                 return i;
  254.         }
  255.  
  256.         return requestLength + 1;
  257.     }
  258.  
  259.     // next usage of page
  260.     int nextUse[cacheSize];
  261. };
  262.  
  263. class FWF : public Strategy {
  264. public:
  265.     FWF() : Strategy("FWF")
  266.     {
  267.     }
  268.  
  269.     int apply(int requestIndex) override
  270.     {
  271.         for(int i=0; i<cacheSize; ++i)
  272.         {
  273.             if(cache[i] == request[requestIndex])
  274.                 return i;
  275.  
  276.             // after first empty page all others have to be empty
  277.             else if(cache[i] == emptyPage)
  278.                 return i;
  279.         }
  280.  
  281.         // no free pages
  282.         return 0;
  283.     }
  284.  
  285.     void update(int cachePos, int requestIndex, bool cacheMiss) override
  286.     {
  287.  
  288.         // no pages free -> miss -> clear cache
  289.         if(cacheMiss && cachePos == 0)
  290.         {
  291.             for(int i = 1; i < cacheSize; ++i)
  292.                 cache[i] = emptyPage;
  293.         }
  294.     }
  295.  
  296. private:
  297.  
  298. };
  299.  
  300. int main()
  301. {
  302.     Strategy* selectedStrategy[] = { new FIFO, new LIFO, new LRU, new LFU, new LFD, new FWF };
  303.  
  304.     for (int strat=0; strat < 6; ++strat)
  305.     {
  306.         // reset cache
  307.         for (int i=0; i < cacheSize; ++i) cache[i] = originalCache[i];
  308.  
  309.         cout <<"\nStrategy: " << selectedStrategy[strat]->strategyName << endl;
  310.  
  311.         cout << "\nCache initial: (";
  312.         for (int i=0; i < cacheSize-1; ++i) cout << cache[i] << ",";
  313.         cout << cache[cacheSize-1] << ")\n\n";
  314.  
  315.         cout << "Request\t";
  316.         for (int i=0; i < cacheSize; ++i) cout << "cache " << i << "\t";
  317.         cout << "cache miss" << endl;
  318.  
  319.         int cntMisses = 0;
  320.  
  321.         for(int i=0; i<requestLength; ++i)
  322.         {
  323.             bool isMiss = updateCache(i, selectedStrategy[strat]);
  324.             if (isMiss) ++cntMisses;
  325.  
  326.             cout << "  " << request[i] << "\t";
  327.             for (int l=0; l < cacheSize; ++l) cout << "  " << cache[l] << "\t";
  328.             cout << (isMiss ? "  x" : "") << endl;
  329.         }
  330.  
  331.         cout<< "\nTotal cache misses: " << cntMisses << endl;
  332.     }
  333.  
  334.     for(int i=0; i<6; ++i) delete selectedStrategy[i];
  335. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top