second_chance_rp.hh revision 12685
112685Sodanrc@yahoo.com.br/** 212685Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 312685Sodanrc@yahoo.com.br * All rights reserved. 412685Sodanrc@yahoo.com.br * 512685Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 612685Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 712685Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 812685Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 912685Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1012685Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1112685Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1212685Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1312685Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1412685Sodanrc@yahoo.com.br * this software without specific prior written permission. 1512685Sodanrc@yahoo.com.br * 1612685Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712685Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812685Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912685Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012685Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112685Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212685Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312685Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412685Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512685Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612685Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712685Sodanrc@yahoo.com.br * 2812685Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2912685Sodanrc@yahoo.com.br */ 3012685Sodanrc@yahoo.com.br 3112685Sodanrc@yahoo.com.br/** 3212685Sodanrc@yahoo.com.br * @file 3312685Sodanrc@yahoo.com.br * Declaration of a Second-Chance replacement policy. 3412685Sodanrc@yahoo.com.br * The victim is chosen using the timestamp. The oldest entry is chosen 3512685Sodanrc@yahoo.com.br * to be evicted, if it hasn't been touched since its insertion. If it 3612685Sodanrc@yahoo.com.br * has been touched, it is given a second chance and re-inserted at the 3712685Sodanrc@yahoo.com.br * end of the queue. 3812685Sodanrc@yahoo.com.br */ 3912685Sodanrc@yahoo.com.br 4012685Sodanrc@yahoo.com.br#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_SECOND_CHANCE_RP_HH__ 4112685Sodanrc@yahoo.com.br#define __MEM_CACHE_REPLACEMENT_POLICIES_SECOND_CHANCE_RP_HH__ 4212685Sodanrc@yahoo.com.br 4312685Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/fifo_rp.hh" 4412685Sodanrc@yahoo.com.br#include "params/SecondChanceRP.hh" 4512685Sodanrc@yahoo.com.br 4612685Sodanrc@yahoo.com.brclass SecondChanceRP : public FIFORP 4712685Sodanrc@yahoo.com.br{ 4812685Sodanrc@yahoo.com.br protected: 4912685Sodanrc@yahoo.com.br /** Second-Chance-specific implementation of replacement data. */ 5012685Sodanrc@yahoo.com.br struct SecondChanceReplData : public FIFOReplData 5112685Sodanrc@yahoo.com.br { 5212685Sodanrc@yahoo.com.br /** 5312685Sodanrc@yahoo.com.br * This is different from isTouched because isTouched accounts only 5412685Sodanrc@yahoo.com.br * for insertion, while this bit is reset every new re-insertion. 5512685Sodanrc@yahoo.com.br * @sa SecondChanceRP. 5612685Sodanrc@yahoo.com.br */ 5712685Sodanrc@yahoo.com.br bool hasSecondChance; 5812685Sodanrc@yahoo.com.br 5912685Sodanrc@yahoo.com.br /** 6012685Sodanrc@yahoo.com.br * Default constructor. 6112685Sodanrc@yahoo.com.br */ 6212685Sodanrc@yahoo.com.br SecondChanceReplData() : FIFOReplData(), hasSecondChance(false) {} 6312685Sodanrc@yahoo.com.br }; 6412685Sodanrc@yahoo.com.br 6512685Sodanrc@yahoo.com.br /** 6612685Sodanrc@yahoo.com.br * Use replacement data's second chance. 6712685Sodanrc@yahoo.com.br * 6812685Sodanrc@yahoo.com.br * @param replacement_data Entry that will use its second chance. 6912685Sodanrc@yahoo.com.br */ 7012685Sodanrc@yahoo.com.br void useSecondChance( 7112685Sodanrc@yahoo.com.br const std::shared_ptr<SecondChanceReplData>& replacement_data) const; 7212685Sodanrc@yahoo.com.br 7312685Sodanrc@yahoo.com.br public: 7412685Sodanrc@yahoo.com.br /** Convenience typedef. */ 7512685Sodanrc@yahoo.com.br typedef SecondChanceRPParams Params; 7612685Sodanrc@yahoo.com.br 7712685Sodanrc@yahoo.com.br /** 7812685Sodanrc@yahoo.com.br * Construct and initiliaze this replacement policy. 7912685Sodanrc@yahoo.com.br */ 8012685Sodanrc@yahoo.com.br SecondChanceRP(const Params *p); 8112685Sodanrc@yahoo.com.br 8212685Sodanrc@yahoo.com.br /** 8312685Sodanrc@yahoo.com.br * Destructor. 8412685Sodanrc@yahoo.com.br */ 8512685Sodanrc@yahoo.com.br ~SecondChanceRP() {} 8612685Sodanrc@yahoo.com.br 8712685Sodanrc@yahoo.com.br /** 8812685Sodanrc@yahoo.com.br * Invalidate replacement data to set it as the next probable victim. 8912685Sodanrc@yahoo.com.br * Invalid entries do not have a second chance, and their last touch tick 9012685Sodanrc@yahoo.com.br * is set as the oldest possible. 9112685Sodanrc@yahoo.com.br * 9212685Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be invalidated. 9312685Sodanrc@yahoo.com.br */ 9412685Sodanrc@yahoo.com.br void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 9512685Sodanrc@yahoo.com.br const override; 9612685Sodanrc@yahoo.com.br 9712685Sodanrc@yahoo.com.br /** 9812685Sodanrc@yahoo.com.br * Touch an entry to update its re-insertion tick and second chance bit. 9912685Sodanrc@yahoo.com.br * 10012685Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be touched. 10112685Sodanrc@yahoo.com.br */ 10212685Sodanrc@yahoo.com.br void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 10312685Sodanrc@yahoo.com.br override; 10412685Sodanrc@yahoo.com.br 10512685Sodanrc@yahoo.com.br /** 10612685Sodanrc@yahoo.com.br * Reset replacement data. Used when an entry is inserted or re-inserted 10712685Sodanrc@yahoo.com.br * in the queue. 10812685Sodanrc@yahoo.com.br * Sets its insertion tick and second chance bit. 10912685Sodanrc@yahoo.com.br * 11012685Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be reset. 11112685Sodanrc@yahoo.com.br */ 11212685Sodanrc@yahoo.com.br void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 11312685Sodanrc@yahoo.com.br override; 11412685Sodanrc@yahoo.com.br 11512685Sodanrc@yahoo.com.br /** 11612685Sodanrc@yahoo.com.br * Find replacement victim using insertion timestamps and second chance 11712685Sodanrc@yahoo.com.br * bit. 11812685Sodanrc@yahoo.com.br * 11912685Sodanrc@yahoo.com.br * @param cands Replacement candidates, selected by indexing policy. 12012685Sodanrc@yahoo.com.br * @return Replacement entry to be replaced. 12112685Sodanrc@yahoo.com.br */ 12212685Sodanrc@yahoo.com.br ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 12312685Sodanrc@yahoo.com.br override; 12412685Sodanrc@yahoo.com.br 12512685Sodanrc@yahoo.com.br /** 12612685Sodanrc@yahoo.com.br * Instantiate a replacement data entry. 12712685Sodanrc@yahoo.com.br * 12812685Sodanrc@yahoo.com.br * @return A shared pointer to the new replacement data. 12912685Sodanrc@yahoo.com.br */ 13012685Sodanrc@yahoo.com.br std::shared_ptr<ReplacementData> instantiateEntry() override; 13112685Sodanrc@yahoo.com.br}; 13212685Sodanrc@yahoo.com.br 13312685Sodanrc@yahoo.com.br#endif // __MEM_CACHE_REPLACEMENT_POLICIES_SECOND_CHANCE_RP_HH__ 134