TwoQVictimPolicy< PageT > Class Template Reference

TwoQVictimPolicy implements the 2Q page victimization policy as described in the VLDB '94 paper "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm" by Johnson and Shasha. More...

#include <TwoQVictimPolicy.h>

List of all members.

Public Types

typedef TwoQPageListIter<
PageT > 		PageIterator
 All models for VictimPolicy must define a nested public type PageIterator, which is used by CacheImpl to iterate over candidate victims in optimal order.
typedef TwoQDirtyPageListIter<
PageT > 		DirtyPageIterator
 All models for VictimPolicy must define a nested public type DirtyPageIterator, which is used by CacheImpl to iterate over pages that can potentially be flushed by the lazy page writer that runs in a background thread.
typedef SXMutexSharedGuard SharedGuard
 All models for VictimPolicy must define a nested public type SharedGuard, which is held by CacheImpl while iterating over candidate victims.
typedef SXMutexExclusiveGuard ExclusiveGuard
 Guard for write access to mutex.

Public Member Functions

 TwoQVictimPolicy ()
 All models for VictimPolicy must have a default constructor.
 TwoQVictimPolicy (const CacheParams &params)
void setAllocatedPageCount (uint nCachePagesInit)
 Receives notification from CacheImpl, indicating the total number of buffer pages in the cache.
void registerPage (PageT &page)
 Receives notification from CacheImpl when a page is allocated, giving the VictimPolicy a chance to initialize its own data structures for this page.
void unregisterPage (PageT &page)
 Receives notification from CacheImpl when a page is freed, giving the VictimPolicy a chance to deinitialize its own data structures for this page.
void notifyPageAccess (PageT &page, bool pin)
 Receives notification from CacheImpl when a page is accessed.
void notifyPageNice (PageT &page)
 Receives notification from CacheImpl on a hint that a page is a good candidate for victimization.
void notifyPageMap (PageT &page, bool pin)
 Receives notification from CacheImpl just after a page is mapped.
void notifyPageUnmap (PageT &page, bool discard)
 Receives notification from CacheImpl just before a page is unmapped.
void notifyPageUnpin (PageT &page)
 Receives notification from CacheImpl that a page no longer needs to be pinned.
void notifyPageDirty (PageT &page)
 Receives notification from CacheImpl that a page has been marked as dirty.
void notifyPageClean (PageT &page)
 Receives notification from CacheImpl that a page is no longer dirty.
void notifyPageDiscard (BlockId blockId)
 Receives notification from CacheImpl that a page has been discarded from the cache.
SXMutex & getMutex ()
 Provides an SXMutex to CacheImpl to be acquired before calling getVictimRange().
std::pair< PageIterator, PageIterator > getVictimRange ()
 Provides a range of candidate victims to CacheImpl.
std::pair< DirtyPageIterator,
DirtyPageIterator > 		getDirtyVictimRange ()
 Provides a range of candidate victims for flushing to CacheImpl.

Private Member Functions

void init ()
 Initializes various queue variables.
bool isPageClean (PageT &page)
 
Returns:
true if a page's state is non-dirty and its dirty state is clean

void notifyPopularPageAccess (PageT &page, bool pin)
 Notifies the policy that a page that's being accessed needs to be put into the popular queue.

Private Attributes

SXMutex mutex
 SXMutex protecting the queues.
TwoQPageQueue popularPinnedQueue
 FIFO queue of popular, pinned pages.
TwoQPageQueue popularUnpinnedQueue
 LRU queue of popular, unpinned pages.
TwoQPageQueue freshmenQueue
 FIFO queue of freshmen pages.
TwoQPageQueue dirtyPopularUnpinnedQueue
 Companion queue to popularUnpinnedQueue, except it only includes dirty pages and contains pointers to TwoQDirtyPage objects.
TwoQPageQueue dirtyFreshmenQueue
 Companion queue to freshmenQueue, except it only includes dirty pages and contains pointers to TwoQDirtyPage objects.
std::vector< BlockId > historyQueue
 FIFO history queue.
uint historyQueueStart
 Index corresponding to the first element in the historyQueue.
uint currHistoryQueueLen
 Current length of the historyQueue.
boost::dynamic_bitset historyBitmap
 Bitmap used to quickly approximate whether a page exists in the history queue based on the page's BlockId.
uint nCachePages
 Total number of buffer pages in the cache.
uint maxFreshmenQueueLen
 Maximum number of pages in the freshmen queue.
uint maxHistoryQueueLen
 Maximum number of pages in the history queue.
uint freshmenQueuePercentage
 Percentage of the total cache set aside for the freshmen queue.
uint pageHistoryQueuePercentage
 The percentage of the total number of cache pages that dictates the number of pages in this history queue.

Detailed Description

template<class PageT>
class TwoQVictimPolicy< PageT >

TwoQVictimPolicy implements the 2Q page victimization policy as described in the VLDB '94 paper "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm" by Johnson and Shasha.

The 2Q refers to the fact that the algorithm separates the pages in the cache into two separate queues -- a LRU popular queue for frequently accessed pages and a FIFO freshmen queue for less frequently accessed pages. There is also a FIFO history queue that keeps track of pages that have been victimized from the freshmen queue. That history queue is what's used to determine whether a page is a popular one. In other words, when a page is first added to the cache, it's added to the freshmen queue. Once it's victimized from the freshmen queue, it's added to the history queue. If a page is re-referenced while it's in the history queue, it's added to the popular queue. By keeping two separate queues, the algorithm is scan resistant. Therefore, if you are doing large sequential scans, the scan resistant property prevents the scan pages from flooding the cache, paging out index pages that are more commonly referenced, particularly, index root pages. Ideally, you want to keep index root pages cached and page out the scan pages instead, even if the latter was more recently referenced.

Note that the naming of the queues is different from the less intuitive terms used in the original Johnson/Shasha paper -- Am (popular), A1in (freshmen), and A1out (history). Also, the popular queue is divided into two separate queues -- pinned vs unpinned pages. This makes locating a page for victimization more efficient.

One other extension in our implementation is we maintain separate queues of dirty pages for pages currently in the freshmen and popular-unpinned queues. These queues are subsets of their "parent" queues. By separating out dirty pages, this makes locating candidate pages for flushing more efficient when you have a large number of cache pages, many of which aren't dirty.

Any realization for PageT must inherit both CachePage and TwoQVictim as bases.

Definition at line 474 of file TwoQVictimPolicy.h.

Member Typedef Documentation

template<class PageT>
typedef TwoQPageListIter<PageT> TwoQVictimPolicy< PageT >::PageIterator

All models for VictimPolicy must define a nested public type PageIterator, which is used by CacheImpl to iterate over candidate victims in optimal order.

This type must be a model for a standard forward iterator. For TwoQVictimPolicy, this is accomplished by iterating over two doubly-linked list of pages corresponding to queues, one after the other.

Definition at line 656 of file TwoQVictimPolicy.h.

template<class PageT>
typedef TwoQDirtyPageListIter<PageT> TwoQVictimPolicy< PageT >::DirtyPageIterator

All models for VictimPolicy must define a nested public type DirtyPageIterator, which is used by CacheImpl to iterate over pages that can potentially be flushed by the lazy page writer that runs in a background thread.

In the case of TwoQVictimPolicy, this iterator only returns dirty pages, avoiding clean pages.

Definition at line 665 of file TwoQVictimPolicy.h.

template<class PageT>
typedef SXMutexSharedGuard TwoQVictimPolicy< PageT >::SharedGuard

All models for VictimPolicy must define a nested public type SharedGuard, which is held by CacheImpl while iterating over candidate victims.

This guard must provide any synchronization required to protect the iteration against concurrent modifications. The guard will be initialized with the result of getMutex(). For TwoQVictimPolicy, the guard is a read guard protecting the various queues, meaning notifications are blocked during iteration since they have to modify the chain.

Definition at line 677 of file TwoQVictimPolicy.h.

template<class PageT>
typedef SXMutexExclusiveGuard TwoQVictimPolicy< PageT >::ExclusiveGuard

Guard for write access to mutex.

Definition at line 682 of file TwoQVictimPolicy.h.

Constructor & Destructor Documentation

template<class PageT>
TwoQVictimPolicy< PageT >::TwoQVictimPolicy (  )  [inline]

All models for VictimPolicy must have a default constructor.

Definition at line 687 of file TwoQVictimPolicy.h.

References CacheParams::defaultFreshmenQueuePercentage, CacheParams::defaultPageHistoryQueuePercentage, TwoQVictimPolicy< PageT >::freshmenQueuePercentage, TwoQVictimPolicy< PageT >::init(), and TwoQVictimPolicy< PageT >::pageHistoryQueuePercentage.

00688     {
00689         init();
00690         freshmenQueuePercentage = CacheParams::defaultFreshmenQueuePercentage;
00691         pageHistoryQueuePercentage =
00692             CacheParams::defaultPageHistoryQueuePercentage;
00693     }

template<class PageT>
TwoQVictimPolicy< PageT >::TwoQVictimPolicy ( const CacheParams &  params  )  [inline]

Definition at line 695 of file TwoQVictimPolicy.h.

References CacheParams::freshmenQueuePercentage, TwoQVictimPolicy< PageT >::freshmenQueuePercentage, TwoQVictimPolicy< PageT >::init(), CacheParams::pageHistoryQueuePercentage, and TwoQVictimPolicy< PageT >::pageHistoryQueuePercentage.

00696     {
00697         init();
00698         freshmenQueuePercentage = params.freshmenQueuePercentage;
00699         pageHistoryQueuePercentage = params.pageHistoryQueuePercentage;
00700     }

Member Function Documentation

template<class PageT>
void TwoQVictimPolicy< PageT >::init (  )  [inline, private]

Initializes various queue variables.

Definition at line 566 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::currHistoryQueueLen, TwoQVictimPolicy< PageT >::historyQueueStart, TwoQVictimPolicy< PageT >::maxFreshmenQueueLen, TwoQVictimPolicy< PageT >::maxHistoryQueueLen, and TwoQVictimPolicy< PageT >::nCachePages.

Referenced by TwoQVictimPolicy< PageT >::TwoQVictimPolicy().

00567     {
00568         nCachePages = 0;
00569         maxFreshmenQueueLen = 0;
00570         maxHistoryQueueLen = 0;
00571         historyQueueStart = 0;
00572         currHistoryQueueLen = 0;
00573     }

template<class PageT>
bool TwoQVictimPolicy< PageT >::isPageClean ( PageT &  page  )  [inline, private]

Returns:
true if a page's state is non-dirty and its dirty state is clean

Definition at line 578 of file TwoQVictimPolicy.h.

References TwoQDirtyPage::PAGE_CLEAN.

Referenced by TwoQVictimPolicy< PageT >::notifyPageAccess(), TwoQVictimPolicy< PageT >::notifyPageNice(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), TwoQVictimPolicy< PageT >::notifyPageUnpin(), and TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

00579     {
00580         return
00581             (!page.isDirty() &&
00582                 page.getDirtyPageNode().getDirtyState() ==
00583                     TwoQDirtyPage::PAGE_CLEAN);
00584     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPopularPageAccess ( PageT &  page,
bool  pin 
) [inline, private]

Notifies the policy that a page that's being accessed needs to be put into the popular queue.

Depending on the "pin" parameter, it's either put into the popular-pinned queue or the popular-unpinned queue.

Parameters:
page the page being accessed
pin whether the page is being pinned

Definition at line 594 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQPageQueue::insertAtTail(), SXMutex::isLocked(), TwoQVictimPolicy< PageT >::isPageClean(), LOCKMODE_X, TwoQPageQueue::moveToTail(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQVictimPolicy< PageT >::popularPinnedQueue, TwoQVictimPolicy< PageT >::popularUnpinnedQueue, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

Referenced by TwoQVictimPolicy< PageT >::notifyPageAccess().

00595     {
00596         assert(mutex.isLocked(LOCKMODE_X));
00597         TwoQVictim::PageState state = page.TwoQVictim::getState();
00598         assert(
00599             state != TwoQVictim::PAGE_STATE_FRESHMAN &&
00600             state != TwoQVictim::PAGE_STATE_POPULAR_PINNED);
00601 
00602         if (pin) {
00603             // Remove the page from the popular-unpinned queues and add
00604             // it to the popular-pinned queue.
00605             if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
00606                 popularUnpinnedQueue.remove(page);
00607                 TwoQDirtyPage &dirtyPageNode =
00608                     page.TwoQVictim::getDirtyPageNode();
00609                 if (dirtyPageNode.getDirtyState() ==
00610                     TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
00611                 {
00612                     dirtyPopularUnpinnedQueue.remove(dirtyPageNode);
00613                     dirtyPageNode.setDirtyState(
00614                         TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED);
00615                 } else {
00616                     assert(isPageClean(page));
00617                 }
00618             }
00619             popularPinnedQueue.insertAtTail(page);
00620             page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_POPULAR_PINNED);
00621 
00622         } else {
00623             // Move the page to the end of the popular-unpinned queues.
00624             if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
00625                 popularUnpinnedQueue.moveToTail(page);
00626                 TwoQDirtyPage &dirtyPageNode =
00627                     page.TwoQVictim::getDirtyPageNode();
00628                 if (dirtyPageNode.getDirtyState() ==
00629                     TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
00630                 {
00631                     dirtyPopularUnpinnedQueue.moveToTail(dirtyPageNode);
00632                 } else {
00633                     assert(isPageClean(page));
00634                 }
00635             } else {
00636                 // The page was originally free and now needs to be put
00637                 // into the popular-unpinned queue.
00638                 assert(isPageClean(page));
00639                 popularUnpinnedQueue.insertAtTail(page);
00640                 page.TwoQVictim::setState(
00641                     TwoQVictim::PAGE_STATE_POPULAR_UNPINNED);
00642             }
00643         }
00644     }

template<class PageT>
void TwoQVictimPolicy< PageT >::setAllocatedPageCount ( uint  nCachePagesInit  )  [inline]

Receives notification from CacheImpl, indicating the total number of buffer pages in the cache.

Parameters:
nCachePagesInit number of buffer pages in the cache

Definition at line 708 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::currHistoryQueueLen, TwoQVictimPolicy< PageT >::freshmenQueuePercentage, TwoQVictimPolicy< PageT >::historyBitmap, TwoQVictimPolicy< PageT >::historyQueue, TwoQVictimPolicy< PageT >::historyQueueStart, TwoQVictimPolicy< PageT >::maxFreshmenQueueLen, TwoQVictimPolicy< PageT >::maxHistoryQueueLen, TwoQVictimPolicy< PageT >::mutex, TwoQVictimPolicy< PageT >::nCachePages, NULL_BLOCK_ID, opaqueToInt(), and TwoQVictimPolicy< PageT >::pageHistoryQueuePercentage.

00709     {
00710         ExclusiveGuard exclusiveGuard(mutex);
00711 
00712         if (nCachePagesInit == nCachePages) {
00713             return;
00714         }
00715 
00716         uint newHistoryQueueLen =
00717             nCachePagesInit * pageHistoryQueuePercentage / 100;
00718         if ((currHistoryQueueLen > newHistoryQueueLen) ||
00719             (historyQueueStart != 0))
00720         {
00721             // If the new queue is smaller than the currently used size,
00722             // copy the existing history queue into a temporary vector,
00723             // truncating the front of the queue to match the size of
00724             // the new vector.  We also need to recreate the vector if
00725             // the new queue is larger than the currently used size,
00726             // and the existing history queue has cycled around such
00727             // that the starting element is no longer at position 0.
00728             std::vector<BlockId> temp;
00729             temp.resize(newHistoryQueueLen);
00730             uint excess =
00731                 (currHistoryQueueLen > newHistoryQueueLen)
00732                     ? (currHistoryQueueLen - newHistoryQueueLen) : 0;
00733             currHistoryQueueLen -= excess;
00734             for (uint i = 0; i < currHistoryQueueLen; i++) {
00735                 temp[i] =
00736                     historyQueue[
00737                         (historyQueueStart + excess + i) %
00738                         maxHistoryQueueLen];
00739             }
00740             historyQueueStart = 0;
00741             historyQueue.resize(newHistoryQueueLen);
00742             historyQueue.swap(temp);
00743         } else {
00744             historyQueue.resize(newHistoryQueueLen);
00745         }
00746 
00747         // It's possible that a blockId has been removed from the history
00748         // bitmap, but the corresponding update hasn't been made in the
00749         // history queue itself.  If so, remove the blockId from the queue
00750         // so when we rebuild the bitmap below, that blockId won't be included.
00751         assert(historyQueueStart == 0);
00752         for (uint i = 0; i < currHistoryQueueLen; i++) {
00753             if (!historyBitmap.test(
00754                 opaqueToInt(historyQueue[i] % historyBitmap.size())))
00755             {
00756                 historyQueue[i] = NULL_BLOCK_ID;
00757             }
00758         }
00759 
00760         nCachePages = nCachePagesInit;
00761         maxFreshmenQueueLen = nCachePages * freshmenQueuePercentage / 100;
00762         maxHistoryQueueLen = newHistoryQueueLen;
00763 
00764         historyBitmap.resize(maxHistoryQueueLen * 64);
00765         // Rebuild the history bitmap, if there are existing entries in the
00766         // history queue.  Ignore the invalid blockIds.
00767         if (currHistoryQueueLen > 0) {
00768             historyBitmap.reset();
00769             for (uint i = 0; i < currHistoryQueueLen; i++) {
00770                 if (historyQueue[i] != NULL_BLOCK_ID) {
00771                     historyBitmap.set(
00772                         opaqueToInt(historyQueue[i]) % historyBitmap.size());
00773                 }
00774             }
00775         }
00776     }

template<class PageT>
void TwoQVictimPolicy< PageT >::registerPage ( PageT &  page  )  [inline]

Receives notification from CacheImpl when a page is allocated, giving the VictimPolicy a chance to initialize its own data structures for this page.

Parameters:
page the page being allocated

Definition at line 785 of file TwoQVictimPolicy.h.

References TwoQDirtyPage::PAGE_CLEAN, and TwoQVictim::PAGE_STATE_FREE.

00786     {
00787         page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_FREE);
00788         page.TwoQVictim::getDirtyPageNode().setParentPage(page);
00789         page.TwoQVictim::getDirtyPageNode().setDirtyState(
00790             TwoQDirtyPage::PAGE_CLEAN);
00791     }

template<class PageT>
void TwoQVictimPolicy< PageT >::unregisterPage ( PageT &  page  )  [inline]

Receives notification from CacheImpl when a page is freed, giving the VictimPolicy a chance to deinitialize its own data structures for this page.

Parameters:
page the page being freed

Definition at line 800 of file TwoQVictimPolicy.h.

References TwoQDirtyPage::PAGE_CLEAN, and TwoQVictim::PAGE_STATE_FREE.

00801     {
00802         assert(page.TwoQVictim::getState() == TwoQVictim::PAGE_STATE_FREE);
00803         assert(
00804             page.TwoQVictim::getDirtyPageNode().getDirtyState() ==
00805             TwoQDirtyPage::PAGE_CLEAN);
00806     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageAccess ( PageT &  page,
bool  pin 
) [inline]

Receives notification from CacheImpl when a page is accessed.

On entry, the page's mutex is held by the calling thread, so the state of the page (e.g. its mapped BlockId) is guaranteed to remain stable. This is true for all other notify methods as well. For TwoQVictimPolicy, depending on the current state of the page, that determines what happens to the page.

Parameters:
page the page being accessed
pin if true, the page being accessed will be pinned in the cache

Definition at line 834 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::freshmenQueue, TwoQVictimPolicy< PageT >::historyBitmap, TwoQPageQueue::insertAtTail(), TwoQVictimPolicy< PageT >::isPageClean(), TwoQVictimPolicy< PageT >::mutex, TwoQVictimPolicy< PageT >::notifyPopularPageAccess(), opaqueToInt(), TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, and TwoQVictim::PAGE_STATE_POPULAR_UNPINNED.

Referenced by TwoQVictimPolicy< PageT >::notifyPageMap().

00835     {
00836         ExclusiveGuard exclusiveGuard(mutex);
00837 
00838         switch (page.TwoQVictim::getState()) {
00839         case TwoQVictim::PAGE_STATE_FRESHMAN:
00840         case TwoQVictim::PAGE_STATE_POPULAR_PINNED:
00841             return;
00842 
00843         case TwoQVictim::PAGE_STATE_POPULAR_UNPINNED:
00844             notifyPopularPageAccess(page, pin);
00845             break;
00846 
00847         case TwoQVictim::PAGE_STATE_FREE:
00848             if (historyBitmap.test(
00849                 opaqueToInt(page.getBlockId()) % historyBitmap.size()))
00850             {
00851                 notifyPopularPageAccess(page, pin);
00852             } else {
00853                 assert(isPageClean(page));
00854                 page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_FRESHMAN);
00855                 freshmenQueue.insertAtTail(page);
00856             }
00857             break;
00858 
00859         default:
00860             permAssert(false);
00861         }
00862     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageNice ( PageT &  page  )  [inline]

Receives notification from CacheImpl on a hint that a page is a good candidate for victimization.

For TwoQVictimPolicy, this results in the page being moved to the head of the queue if the page is in either the popular-unpinned or freshmen queues.

Parameters:
page the page to which the hint pertains

Definition at line 872 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQVictimPolicy< PageT >::freshmenQueue, TwoQDirtyPage::getDirtyState(), TwoQVictimPolicy< PageT >::isPageClean(), TwoQPageQueue::moveToHead(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, and TwoQVictimPolicy< PageT >::popularUnpinnedQueue.

00873     {
00874         ExclusiveGuard exclusiveGuard(mutex);
00875         TwoQVictim::PageState state = page.TwoQVictim::getState();
00876         assert(state != TwoQVictim::PAGE_STATE_FREE);
00877 
00878         if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
00879             popularUnpinnedQueue.moveToHead(page);
00880             TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
00881             if (dirtyPageNode.getDirtyState() ==
00882                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
00883             {
00884                 dirtyPopularUnpinnedQueue.moveToHead(dirtyPageNode);
00885             } else {
00886                 assert(isPageClean(page));
00887             }
00888         } else if (state == TwoQVictim::PAGE_STATE_FRESHMAN) {
00889             freshmenQueue.moveToHead(page);
00890             TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
00891             if (dirtyPageNode.getDirtyState() ==
00892                 TwoQDirtyPage::PAGE_DIRTY_FRESHMAN)
00893             {
00894                 dirtyFreshmenQueue.moveToHead(dirtyPageNode);
00895             } else {
00896                 assert(isPageClean(page));
00897             }
00898         }
00899     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageMap ( PageT &  page,
bool  pin 
) [inline]

Receives notification from CacheImpl just after a page is mapped.

This implies an access as well, so for efficiency, no corresponding notifyPageAccess notification is received.

Parameters:
page the page being mapped
pin if true, the page being mapped will be pinned in the cache

Definition at line 909 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::notifyPageAccess().

00910     {
00911         // first access for a newly mapped page will not get a corresponding
00912         // call to notifyPageAcces, so do it now
00913         notifyPageAccess(page, pin);
00914     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageUnmap ( PageT &  page,
bool  discard 
) [inline]

Receives notification from CacheImpl just before a page is unmapped.

The Page object still has the ID being unmapped.

Parameters:
page the page being unmapped
discard if true, page is being discarded from the cache

Definition at line 924 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::currHistoryQueueLen, TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQVictimPolicy< PageT >::freshmenQueue, TwoQDirtyPage::getDirtyState(), TwoQVictimPolicy< PageT >::historyBitmap, TwoQVictimPolicy< PageT >::historyQueue, TwoQVictimPolicy< PageT >::historyQueueStart, TwoQVictimPolicy< PageT >::isPageClean(), TwoQVictimPolicy< PageT >::maxHistoryQueueLen, TwoQVictimPolicy< PageT >::mutex, opaqueToInt(), TwoQDirtyPage::PAGE_CLEAN, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQVictimPolicy< PageT >::popularUnpinnedQueue, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

00925     {
00926         ExclusiveGuard exclusiveGuard(mutex);
00927         TwoQVictim::PageState state = page.TwoQVictim::getState();
00928         assert(
00929             state != TwoQVictim::PAGE_STATE_POPULAR_PINNED &&
00930             state != TwoQVictim::PAGE_STATE_FREE);
00931 
00932         if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
00933             popularUnpinnedQueue.remove(page);
00934             TwoQDirtyPage &dirtyPageNode =
00935                 page.TwoQVictim::getDirtyPageNode();
00936             if (dirtyPageNode.getDirtyState() ==
00937                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
00938             {
00939                 dirtyPopularUnpinnedQueue.remove(dirtyPageNode);
00940                 dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
00941             } else {
00942                 assert(isPageClean(page));
00943             }
00944         } else {
00945             // If the page is currently in the freshmen queue, add it to
00946             // the history queue, unless the page is being discarded.
00947             // Remove the page currently at the head of the history queue,
00948             // if the history queue is at max capacity.  Also make the
00949             // corresponding updates in the history bitmap.
00950             if (!discard) {
00951                 if (currHistoryQueueLen >= maxHistoryQueueLen) {
00952                     historyBitmap.set(
00953                         opaqueToInt(historyQueue[historyQueueStart])
00954                             % historyBitmap.size(),
00955                         false);
00956                     historyQueueStart =
00957                         (historyQueueStart + 1) % maxHistoryQueueLen;
00958                     currHistoryQueueLen--;
00959                 }
00960                 uint currIdx =
00961                     (historyQueueStart + currHistoryQueueLen) %
00962                         maxHistoryQueueLen;
00963                 historyQueue[currIdx] = page.getBlockId();
00964                 historyBitmap.set(
00965                     opaqueToInt(page.getBlockId()) % historyBitmap.size());
00966                 currHistoryQueueLen++;
00967             }
00968 
00969             freshmenQueue.remove(page);
00970             TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
00971             if (dirtyPageNode.getDirtyState() ==
00972                 TwoQDirtyPage::PAGE_DIRTY_FRESHMAN)
00973             {
00974                 dirtyFreshmenQueue.remove(dirtyPageNode);
00975                 dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
00976             } else {
00977                 assert(isPageClean(page));
00978             }
00979         }
00980 
00981         // If the page is being discarded, remove it from the history bitmap.
00982         // Just clear the blockId from the history bitmap, but leave the
00983         // blockId in the history queue itself.  The page will get cleaned out
00984         // if we need to resize the history queue.
00985         if (discard) {
00986             historyBitmap.set(
00987                 opaqueToInt(page.getBlockId()) % historyBitmap.size(),
00988                 false);
00989         }
00990 
00991         page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_FREE);
00992         assert(page.getNext() == NULL && page.getPrev() == NULL);
00993     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageUnpin ( PageT &  page  )  [inline]

Receives notification from CacheImpl that a page no longer needs to be pinned.

Parameters:
page the unpinned page

Definition at line 1001 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQPageQueue::insertAtTail(), TwoQVictimPolicy< PageT >::isPageClean(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQVictimPolicy< PageT >::popularPinnedQueue, TwoQVictimPolicy< PageT >::popularUnpinnedQueue, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

01002     {
01003         ExclusiveGuard exclusiveGuard(mutex);
01004         TwoQVictim::PageState state = page.TwoQVictim::getState();
01005         assert(
01006             state != TwoQVictim::PAGE_STATE_POPULAR_UNPINNED &&
01007             state != TwoQVictim::PAGE_STATE_FREE);
01008 
01009         // If the page is poular and pinned, move it to the popular-unpinned
01010         // queues.
01011         if (state == TwoQVictim::PAGE_STATE_POPULAR_PINNED) {
01012             popularPinnedQueue.remove(page);
01013             popularUnpinnedQueue.insertAtTail(page);
01014             TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
01015             if (dirtyPageNode.getDirtyState() ==
01016                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED)
01017             {
01018                 dirtyPopularUnpinnedQueue.insertAtTail(dirtyPageNode);
01019                 dirtyPageNode.setDirtyState(
01020                     TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED);
01021             } else {
01022                 assert(isPageClean(page));
01023             }
01024             page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_POPULAR_UNPINNED);
01025         }
01026         // If the page state is free or a freshman, then there's nothing to do
01027     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageDirty ( PageT &  page  )  [inline]

Receives notification from CacheImpl that a page has been marked as dirty.

Parameters:
page the dirty page

Definition at line 1035 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQPageQueue::insertAtTail(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_CLEAN, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, and TwoQDirtyPage::setDirtyState().

01036     {
01037         ExclusiveGuard exclusiveGuard(mutex);
01038         TwoQVictim::PageState state = page.TwoQVictim::getState();
01039         assert(state != TwoQVictim::PAGE_STATE_FREE);
01040 
01041         TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
01042         assert(
01043             dirtyPageNode.getDirtyState() == TwoQDirtyPage::PAGE_CLEAN);
01044 
01045         // Set the dirty state to match the queue containing the page, and
01046         // then if appropriate, add the dirty node to the corresponding
01047         // dirty queue.  In the case of pages that are in the popular-pinned
01048         // queue, just set the dirty state since we don't have a dirty queue
01049         // for popular-pinned pages.  But we need to set the dirty state so
01050         // we know that the page is dirty when it's unpinned and moved to
01051         // the popular-unpinned queue.
01052         if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
01053             dirtyPopularUnpinnedQueue.insertAtTail(dirtyPageNode);
01054             dirtyPageNode.setDirtyState(
01055                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED);
01056         } else if (state == TwoQVictim::PAGE_STATE_FRESHMAN) {
01057             dirtyFreshmenQueue.insertAtTail(dirtyPageNode);
01058             dirtyPageNode.setDirtyState(
01059                     TwoQDirtyPage::PAGE_DIRTY_FRESHMAN);
01060         } else if (state == TwoQVictim::PAGE_STATE_POPULAR_PINNED) {
01061             dirtyPageNode.setDirtyState(
01062                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED);
01063         }
01064     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageClean ( PageT &  page  )  [inline]

Receives notification from CacheImpl that a page is no longer dirty.

Parameters:
page the clean page

Definition at line 1071 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_CLEAN, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

01072     {
01073         ExclusiveGuard exclusiveGuard(mutex);
01074         TwoQVictim::PageState state = page.TwoQVictim::getState();
01075         // Note that it is possible for the page to be in the popular-pinned
01076         // queue if the page has just been pinned and the thread accessing
01077         // the page is waiting for I/O on the page to complete before using it.
01078         assert(state != TwoQVictim::PAGE_STATE_FREE);
01079 
01080         // Remove the dirty node from the queue if it's currently in a
01081         // queue, and then reset its dirty state to indicate that the page
01082         // is now clean.
01083         TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
01084         if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
01085             assert(
01086                 dirtyPageNode.getDirtyState() ==
01087                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED);
01088             dirtyPopularUnpinnedQueue.remove(dirtyPageNode);
01089         } else if (state == TwoQVictim::PAGE_STATE_FRESHMAN) {
01090             assert(
01091                 dirtyPageNode.getDirtyState() ==
01092                 TwoQDirtyPage::PAGE_DIRTY_FRESHMAN);
01093             dirtyFreshmenQueue.remove(dirtyPageNode);
01094         } else if (state == TwoQVictim::PAGE_STATE_POPULAR_PINNED) {
01095             assert(
01096                 dirtyPageNode.getDirtyState() ==
01097                 TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED);
01098         }
01099         dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
01100     }

template<class PageT>
void TwoQVictimPolicy< PageT >::notifyPageDiscard ( BlockId  blockId  )  [inline]

Receives notification from CacheImpl that a page has been discarded from the cache.

This allows TwoQVictimPolicy to remove the page from its history queue.

Parameters:
blockId the blockId of the page being deallocated

Definition at line 1109 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::historyBitmap, TwoQVictimPolicy< PageT >::mutex, and opaqueToInt().

01110     {
01111         ExclusiveGuard exclusiveGuard(mutex);
01112         // Just clear the blockId from the history bitmap, but leave the
01113         // blockId in the history queue itself.  The page will get cleaned out
01114         // if we need to resize the history queue.
01115         historyBitmap.set(opaqueToInt(blockId % historyBitmap.size()), false);
01116     }

template<class PageT>
SXMutex& TwoQVictimPolicy< PageT >::getMutex (  )  [inline]

Provides an SXMutex to CacheImpl to be acquired before calling getVictimRange().

The mutex guard is held for the duration of the iteration.

Returns:
a reference to the RW_Mutex protecting the queues

Definition at line 1125 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::mutex.

01126     {
01127         return mutex;
01128     }

template<class PageT>
std::pair<PageIterator,PageIterator> TwoQVictimPolicy< PageT >::getVictimRange (  )  [inline]

Provides a range of candidate victims to CacheImpl.

Returns:
a pair of PageIterators, where pair.first references the best victim and pair.second is the end of the victim range

Definition at line 1136 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::freshmenQueue, TwoQPageQueue::getHead(), TwoQVictimPolicy< PageT >::maxFreshmenQueueLen, TwoQVictimPolicy< PageT >::popularUnpinnedQueue, and TwoQPageQueue::size().

01137     {
01138         // If the freshmen queue has hit its size limit, victimize from
01139         // that queue first.  If all of its pages are pinned, then try
01140         // victimizing from the popular-unpinned page queue.  Do the
01141         // reverse if the freshmen queue has hit its size limit.
01142 
01143         if (freshmenQueue.size() < maxFreshmenQueueLen) {
01144             return std::pair<PageIterator, PageIterator>(
01145                 PageIterator(
01146                     static_cast<PageT *>(popularUnpinnedQueue.getHead()),
01147                     static_cast<PageT *>(freshmenQueue.getHead())),
01148                 PageIterator());
01149         } else {
01150             return std::pair<PageIterator, PageIterator>(
01151                 PageIterator(
01152                     static_cast<PageT *>(freshmenQueue.getHead()),
01153                     static_cast<PageT *>(popularUnpinnedQueue.getHead())),
01154                 PageIterator());
01155         }
01156     }

template<class PageT>
std::pair<DirtyPageIterator,DirtyPageIterator> TwoQVictimPolicy< PageT >::getDirtyVictimRange (  )  [inline]

Provides a range of candidate victims for flushing to CacheImpl.

Returns:
a pair of DirtyPageIterators, where pair.first references the best victim and pair.second is the end of the victim range

Definition at line 1164 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQVictimPolicy< PageT >::freshmenQueue, TwoQPageQueue::getHead(), TwoQVictimPolicy< PageT >::maxFreshmenQueueLen, and TwoQPageQueue::size().

01165     {
01166         // If the freshmen queue has hit its size limit, victimize from
01167         // that queue first.  If all of its pages are pinned, then try
01168         // victimizing from the popular-unpinned page queue.  Do the
01169         // reverse if the freshmen queue has hit its size limit.
01170 
01171         if (freshmenQueue.size() < maxFreshmenQueueLen) {
01172             return std::pair<DirtyPageIterator, DirtyPageIterator>(
01173                 DirtyPageIterator(
01174                     static_cast<TwoQDirtyPage *>(
01175                         dirtyPopularUnpinnedQueue.getHead()),
01176                     static_cast<TwoQDirtyPage *>(dirtyFreshmenQueue.getHead())),
01177                 DirtyPageIterator());
01178         } else {
01179             return std::pair<DirtyPageIterator, DirtyPageIterator>(
01180                 DirtyPageIterator(
01181                     static_cast<TwoQDirtyPage *>(dirtyFreshmenQueue.getHead()),
01182                     static_cast<TwoQDirtyPage *>(
01183                         dirtyPopularUnpinnedQueue.getHead())),
01184                 DirtyPageIterator());
01185         }
01186     }

Member Data Documentation

template<class PageT>
SXMutex TwoQVictimPolicy< PageT >::mutex [private]

SXMutex protecting the queues.

Definition at line 479 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getMutex(), TwoQVictimPolicy< PageT >::notifyPageAccess(), TwoQVictimPolicy< PageT >::notifyPageClean(), TwoQVictimPolicy< PageT >::notifyPageDirty(), TwoQVictimPolicy< PageT >::notifyPageDiscard(), TwoQVictimPolicy< PageT >::notifyPageNice(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), TwoQVictimPolicy< PageT >::notifyPageUnpin(), TwoQVictimPolicy< PageT >::notifyPopularPageAccess(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
TwoQPageQueue TwoQVictimPolicy< PageT >::popularPinnedQueue [private]

FIFO queue of popular, pinned pages.

No need to make it LRU since pages from this queue can't be victimized.

Definition at line 485 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::notifyPageUnpin(), and TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

template<class PageT>
TwoQPageQueue TwoQVictimPolicy< PageT >::popularUnpinnedQueue [private]

LRU queue of popular, unpinned pages.

Definition at line 490 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getVictimRange(), TwoQVictimPolicy< PageT >::notifyPageNice(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), TwoQVictimPolicy< PageT >::notifyPageUnpin(), and TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

template<class PageT>
TwoQPageQueue TwoQVictimPolicy< PageT >::freshmenQueue [private]

FIFO queue of freshmen pages.

Definition at line 495 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getDirtyVictimRange(), TwoQVictimPolicy< PageT >::getVictimRange(), TwoQVictimPolicy< PageT >::notifyPageAccess(), TwoQVictimPolicy< PageT >::notifyPageNice(), and TwoQVictimPolicy< PageT >::notifyPageUnmap().

template<class PageT>
TwoQPageQueue TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue [private]

Companion queue to popularUnpinnedQueue, except it only includes dirty pages and contains pointers to TwoQDirtyPage objects.

Definition at line 501 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getDirtyVictimRange(), TwoQVictimPolicy< PageT >::notifyPageClean(), TwoQVictimPolicy< PageT >::notifyPageDirty(), TwoQVictimPolicy< PageT >::notifyPageNice(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), TwoQVictimPolicy< PageT >::notifyPageUnpin(), and TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

template<class PageT>
TwoQPageQueue TwoQVictimPolicy< PageT >::dirtyFreshmenQueue [private]

Companion queue to freshmenQueue, except it only includes dirty pages and contains pointers to TwoQDirtyPage objects.

Definition at line 507 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getDirtyVictimRange(), TwoQVictimPolicy< PageT >::notifyPageClean(), TwoQVictimPolicy< PageT >::notifyPageDirty(), TwoQVictimPolicy< PageT >::notifyPageNice(), and TwoQVictimPolicy< PageT >::notifyPageUnmap().

template<class PageT>
std::vector<BlockId> TwoQVictimPolicy< PageT >::historyQueue [private]

FIFO history queue.

Definition at line 512 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::notifyPageUnmap(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
uint TwoQVictimPolicy< PageT >::historyQueueStart [private]

Index corresponding to the first element in the historyQueue.

Definition at line 517 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::init(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
uint TwoQVictimPolicy< PageT >::currHistoryQueueLen [private]

Current length of the historyQueue.

Definition at line 522 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::init(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
boost::dynamic_bitset TwoQVictimPolicy< PageT >::historyBitmap [private]

Bitmap used to quickly approximate whether a page exists in the history queue based on the page's BlockId.

The determination is approximate because multiple BlockIds can map to the same position in the bitmap. However, the likelihood of those collisions occuring should be small, given the size of the bitmap.

Definition at line 531 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::notifyPageAccess(), TwoQVictimPolicy< PageT >::notifyPageDiscard(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
uint TwoQVictimPolicy< PageT >::nCachePages [private]

Total number of buffer pages in the cache.

Definition at line 536 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::init(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
uint TwoQVictimPolicy< PageT >::maxFreshmenQueueLen [private]

Maximum number of pages in the freshmen queue.

This number can be exceeded if there are not enough popular pages, or freshmen pages can't be victimized because they're all pinned.

Definition at line 543 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getDirtyVictimRange(), TwoQVictimPolicy< PageT >::getVictimRange(), TwoQVictimPolicy< PageT >::init(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
uint TwoQVictimPolicy< PageT >::maxHistoryQueueLen [private]

Maximum number of pages in the history queue.

Definition at line 548 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::init(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), and TwoQVictimPolicy< PageT >::setAllocatedPageCount().

template<class PageT>
uint TwoQVictimPolicy< PageT >::freshmenQueuePercentage [private]

Percentage of the total cache set aside for the freshmen queue.

Note that this is a "soft" percentage, and the number of pages in the freshmen queue can exceed this number.

Definition at line 555 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::setAllocatedPageCount(), and TwoQVictimPolicy< PageT >::TwoQVictimPolicy().

template<class PageT>
uint TwoQVictimPolicy< PageT >::pageHistoryQueuePercentage [private]

The percentage of the total number of cache pages that dictates the number of pages in this history queue.

Definition at line 561 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::setAllocatedPageCount(), and TwoQVictimPolicy< PageT >::TwoQVictimPolicy().

The documentation for this class was generated from the following file:
Generated on Mon Jun 22 04:00:48 2009 for Fennel by  doxygen 1.5.1