Offline Cache缓存调度算法实验报告.docx

Offline Cache实验报告学院：软件学院 学号：201421031059 姓名：吕吕一、 Question DescriptionConsider the management problem between adjacent levels:1)Main memory with n data items from a set U2)Cache can hold kn items Simplest version with no direct-mapping or other restrictions about where items can be1)Suppose cache is full initially 2)Holds k data items to start with Given a memory request d from U1)If d is stored in the cache we can access it quickly2) If not then we call it a cache miss and (since the cache is full) we must bring it into cache and evict some other data item from the cache which one to evict? Question: Given a sequence D=d1,d2,dm of elements from U corresponding to memory requests, Find a sequence of evictions (an eviction schedule) that has as few cache misses as possible。二、Commoncache replacementalgorithm comparison2.1 Traditional cache replacement algorithm2.1.1 FIFO(First Input First Output)Algorithm Idea: The algorithmeliminatethe page first to enter thecache.Advantage: The realization is simple.Disadvantage: Rarely used in practice,because page fault rate of the algorithmis high.2.1.2 LRU(Least Recently Used)Algorithm Idea: If the data has recently been visited, then in the future probability of access is also higher. Therefore, to eliminate the data most long time without access. LRU algorithm is based on recency .Advantage: The realization of LRU is simple andthe extra expenses are very few. Moreover, LRUs effect is obvious and the LRU have been widely used in practice.Disadvantage: Periodical and episodic batch operationwill cause theLRU hitrate decreasing sharply and the serious cache pollutionsituation.The most common implementation is to use a linked list to cache the data, the detailed implementation of the algorithm as following:1 New data is inserted into the list head;2 Whenever the cache hit (i.e. the cache data is accessed), data will be moved to the list head;3 When the list is full, the tail data of the list data is discarded.2.1.3 LFU(Least Frequently Used)Algorithm Idea: To eliminate the data with the minimum times of visit incertain period of time. LFU is based on frequency policy.Advantage: In general,the efficiency of LFUis better than LRU,and can avoid the periodic orsporadicoperation causing thecachehit rateproblem.Disadvantage: Once the data access patterns have changed, LFU needs take a long time to adapt to new data access mode.2.2 Single level cache replacement algorithm2.2.1 LRFU(Least Recently Frequently Used)Algorithm Idea: The combination of LRU and LFU by the weight function to take recency and frequency into consideration.The recent visitaccounts for themaximum weight, and the later visit accounts smallerweight.By weighting functionto calculate thevalue, determinatethe data to be exchanged out. The weight function is:Advantage: The tendency to replacement of different strategies by dynamically adjusting the lambda value Disadvantage: The lambda value dynamically adjusting is hard to implement, and the performance may be not very well.2.2.2 2Q(Two Queues)Algorithm Idea: The 2Q algorithmis similar to that of LRU-2,but the differentpointis that 2Qwill turn historical access queuein the LRU-2 algorithminto aFIFObuffer queue.2Q algorithmhas twobufferqueues,FIFO queue and LRUqueue.When thefirst dataaccess, 2Qalgorithm put the datacached into the FIFO queue, when the datais accessedsecondtimes,then the datafrom the FIFO queue ismoved to the LRUqueue. Two queueaccording to their ownmethods to eliminate thedata.Detailed implementationare as follows:1. Put the newaccess data into a FIFOqueue;2. If the datain the FIFO queue has not beenaccessed again,finallyaccording to the rules of FIFO to beeliminated;3. If the datais accessedagain in the FIFOqueue,data will beshiftedto LRUthe head of the queue;4. If the datais accessed againin the LRUqueue,data will beshiftedto LRUthe head of the queue;5. The LRU queueeliminate the dataat the end of queue.Advantage: The hit rate of 2Q algorithm is higher than that of LRU.Disadvantage: Need two queues,thealgorithmincreasesthe space overhead.3. Time complexity and space complexity of the LRUTaking the advantages and disadvantages into consideration, I decide to implement the cache replacement based on LRU algorithm.3.1 The design of the data structuremap _page stands for the cache pages；list history stands for the pages access history；3.2 Time complexity O(n), n stands for the cache pages size. The most time spend on the search for the element in the cache pages and history list.3.3 Space complexity O(n), n stands for the cache pages size. The space to store the cache pages and history list.4. References4.1 /yunhua_lee/article/details/75996714.2 /link?url=WlHbaodyMdYVwrhZUAg94D6qvWygXNkYx5PDMv3ygJQl1Z1UB2HjSK793NGK9MQhSjy3Z8VK29L5txV6mU5eiG8jd4chYLy7vxTpQIZ6MfS4.3 /content/13/0805/16/13247663_304916783.shtml4.4 /p-152097094.html5. Source Code(C+) and Program Results Screenshot5.1 Results Screenshot5.2 Source Codemain.cpp#include LRU.h#include using namespace std;int main()std:string str=7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1;int pageSize=0;std:string sequence;coutplease input cachepage size:pageSize;coutplease input the sequence of page numbers going to be accessed:endl; getchar();getline(cin,sequence);LRU lru(pageSize);cess(sequence);/getchar();_sleep(1000000);LRU.cpp:class LRUpublic:LRU ( int size ) : _page_size ( size ), _current_empty ( 0 ) LRU ( ) void process( std:string str );private:const int _page_size;int _current_empty;std:map _page;private:void _print_( char c );/implementation of the cache replacementvoid LRU:process ( std:string str ) /visit history liststd:list history;for ( size_t i = 0; i str.length(); i=i+2)/cache pages is fullif ( _current_empty = _page_size ) /element stri not exist in cache pagesif (_page str i = false )/return the first element of history listchar c = history.front();/delete the first element of hsitory listhistory.pop_front();/delete c from cache page _page.erase( c );_page str i = true;/element stri exist in cache pageselse his