goeddek

Offline Paging Example

Nov 26th, 2016
431
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×