Page Eviction Algorithm CAR. More...
#include <page_evictioner_other.hpp>
Public Member Functions | |
| PageEvictionerCAR (const BufferPool *bufferPool) | |
| Constructor for a CAR page evictioner. More... | |
| ~PageEvictionerCAR () final | |
| Destructor for a CAR page evictioner. More... | |
| bf_idx | pickVictim () noexcept final |
| Selects a page to be evicted from the buffer pool. More... | |
| void | updateOnPageHit (bf_idx idx) noexcept final |
| Updates the eviction statistics on page hit. More... | |
| void | updateOnPageUnfix (bf_idx idx) noexcept final |
| Updates the eviction statistics on page unfix. More... | |
| void | updateOnPageMiss (bf_idx idx, PageID pid) noexcept final |
| Updates the eviction statistics on page miss. More... | |
| void | updateOnPageFixed (bf_idx idx) noexcept final |
| Updates the eviction statistics of used pages during eviction. More... | |
| void | updateOnPageDirty (bf_idx idx) noexcept final |
| Updates the eviction statistics of dirty pages during eviction. More... | |
| void | updateOnPageBlocked (bf_idx idx) noexcept final |
| Updates the eviction statistics of pages that cannot be evicted at all. More... | |
| void | updateOnPageSwizzled (bf_idx idx) noexcept final |
| Updates the eviction statistics of pages containing swizzled pointers during eviction. More... | |
| void | updateOnPageExplicitlyUnbuffered (bf_idx idx) noexcept final |
| Updates the eviction statistics on explicit eviction. More... | |
| void | updateOnPointerSwizzling (bf_idx idx) noexcept final |
| Updates the eviction statistics of pages when its pointer got swizzled in its parent page. More... | |
| virtual void | releaseInternalLatches () noexcept final |
| Releases the internal latches of this page evictioner. More... | |
 Public Member Functions inherited from zero::buffer_pool::PageEvictioner | |
| PageEvictioner (const BufferPool *bufferPool) | |
| Constructs an abstract page evictioner. More... | |
| PageEvictioner (const PageEvictioner &)=delete | |
| Explicitly deleted copy constructor of an abstract page evictioner. More... | |
| PageEvictioner & | operator= (const PageEvictioner &)=delete |
| Explicitly deleted assignment operator of an abstract page evictioner. More... | |
| virtual | ~PageEvictioner () |
| Destructs an abstract page evictioner. More... | |
| bool | evictOne (bf_idx &victim) |
| Evicts a page from the buffer pool. More... | |
| Public Member Functions inherited from worker_thread_t | |
| worker_thread_t (int inverval_ms=-1) | |
| virtual | ~worker_thread_t () |
| void | wakeup (bool wait=false, int rounds_to_wait=-1) |
| void | stop () |
| void | wait_for_round (long round=0) |
| long | get_rounds_completed () const |
| bool | is_busy () const |
| Public Member Functions inherited from thread_wrapper_t | |
| thread_wrapper_t () | |
| virtual | ~thread_wrapper_t () |
| virtual void | before_run () |
| virtual void | after_run () |
| void | spawn () |
| void | fork () |
| void | join () |
Protected Types | |
| enum | clock_index { T_1 = 0, T_2 = 1 } |
| Clock names. More... | |
Protected Attributes | |
| multi_clock::MultiHandedClock< bf_idx, bool, 2, 0 > | _clocks |
| Clocks \(T_1\) and \(T_2\). More... | |
| hashtable_deque::HashtableDeque< PageID, 1|0x80000000 > | _b1 |
| LRU-list \(B_1\). More... | |
| hashtable_deque::HashtableDeque< PageID, 1|0x80000000 > | _b2 |
| LRU-list \(B_2\). More... | |
| u_int32_t | _p |
| Parameter \(p\). More... | |
| u_int32_t | _c |
| Parameter \(c\). More... | |
| bf_idx | _handMovement |
| Clock hand movements in current circulation. More... | |
| std::mutex | _latch |
| Latch of _clocks, _b1 and _b2. More... | |
| Protected Attributes inherited from zero::buffer_pool::PageEvictioner | |
| const bool | _maintainEMLSN |
| Maintain the page's EMLSNs on eviction. More... | |
| const bool | _flushDirty |
| Flush dirty pages. More... | |
| const bool | _logEvictions |
| Log page evictions. More... | |
| const uint_fast32_t | _evictionBatchSize |
| Target value of free buffer frames. More... | |
| const uint_fast32_t | _maxAttempts |
| Maximum number of unsuccessful picks of eviction victims. More... | |
| const uint_fast32_t | _wakeupCleanerAttempts = 42 |
| Number of unsuccessful picks of eviction victims before waking up the page cleaner. More... | |
Additional Inherited Members | |
| Protected Member Functions inherited from zero::buffer_pool::PageEvictioner | |
| bool | _doEviction (bf_idx victim) noexcept |
| Evicts a page from the buffer pool. More... | |
| Protected Member Functions inherited from worker_thread_t | |
| bool | should_exit () const |
| void | notify_one () |
| void | notify_all () |
| void | quit () |
| Static Protected Attributes inherited from zero::buffer_pool::PageEvictioner | |
| static constexpr bool | _enabledSwizzling = POINTER_SWIZZLER::usesPointerSwizzling |
| Pointer swizzling used in the buffer pool. More... | |
Detailed Description
template<bool on_page_unfix>
class zero::buffer_pool::PageEvictionerCAR< on_page_unfix >
Page Eviction Algorithm CAR.
Page replacement algorithm CAR as presented in "CAR: Clock with Adaptive Replacement" by Sorav Bansal and Dharmendra S. Modha.
- Template Parameters
-
on_page_unfix If set, the eviction statistics are updated on page unfix instead of page hit.
Member Enumeration Documentation
§ clock_index
|
protected |
Clock names.
Contains constants that map the names of the clocks used by the CAR algorithm to the indexes used by the _clocks data structure.
| Enumerator | |
|---|---|
| T_1 | |
| T_2 | |
Constructor & Destructor Documentation
§ PageEvictionerCAR()
|
inline |
Constructor for a CAR page evictioner.
This instantiates a page evictioner that uses the CAR algorithm to select victims for replacement. It will serve the specified bufferPool .
- Parameters
-
bufferPool The buffer pool the constructed page evictioner is used to select pages for eviction for.
§ ~PageEvictionerCAR()
|
inlinefinal |
Destructor for a CAR page evictioner.
Member Function Documentation
§ pickVictim()
|
inlinefinalvirtualnoexcept |
Selects a page to be evicted from the buffer pool.
This method uses the CAR algorithm to select one buffer frame which is expected to be used the furthest in the future (with the currently cached page).
- Postcondition
- The picked victim is latched in latch_mode_t::LATCH_EX mode as the buffer pool frame will be changed during eviction (page will be removed).
- Returns
- The buffer frame that can be freed.
Implements zero::buffer_pool::PageEvictioner.
§ releaseInternalLatches()
|
inlinefinalvirtualnoexcept |
Releases the internal latches of this page evictioner.
Releases the latch acquired and released in select() and updateOnPageMiss().
- Precondition
- The _latch might be acquired by this thread.
- Postcondition
- The _latch is not acquired by this thread.
- Warning
- The behavior of this method is undefined if the implementation of
std::mutex::unlock()does not allow too many invocations of it.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageBlocked()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics of pages that cannot be evicted at all.
As some pages are not allowed to be evicted at all (will never be allowed), those should be excluded from the eviction but that is not implemented yet.
- Parameters
-
idx The frame of the buffer pool that contains a page that cannot be evicted at all.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageDirty()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics of dirty pages during eviction.
As a dirty page shouldn't be picked for eviction until it is cleaned, it should be excluded from the eviction to increase the performance of the eviction but that is not implemented yet.
- Parameters
-
idx The frame of the buffer pool that was picked for eviction while the contained page is dirty.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageExplicitlyUnbuffered()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics on explicit eviction.
When a page is evicted explicitly, the corresponding buffer frame index is removed from the clock \(T_1\) or \(T_2\).
- Parameters
-
idx The frame of the buffer pool that is freed explicitly.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageFixed()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics of used pages during eviction.
As CAR logs page fixes in specific time intervals, a page fixed for a longer timespan must not set the corresponding referenced bit as this would be recognized as repeated usage and therefore the page would be promoted to \(T_2\).
- Parameters
-
idx The frame of the buffer pool that was picked for eviction while it was fixed.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageHit()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics on page hit.
Sets the referenced bit of the specified buffer frame (inside _refBits) if the template parameter on_hit is set.
- Parameters
-
idx The frame of the buffer pool that was fixed with a page hit.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageMiss()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics on page miss.
Classifies the specified buffer frame to be in clock \(T_1\) or \(T_2\) based on the membership of the referenced page in either \(B_1\), \(B_2\) of none of the LRU-lists. It also removes entries from the LRU-lists \(B_1\) or \(B_2\) if needed. The referenced bit of the specified buffer frame will be unset.
- Parameters
-
idx The frame of the buffer pool where the fixed page is cached in. pid The PageIDof the fixed page.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageSwizzled()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics of pages containing swizzled pointers during eviction.
As a page containing swizzled pointers shouldn't be picked for eviction until the pointers are unswizzled, it should be excluded from the eviction to increase the performance of the eviction but that is not implemented yet.
- Parameters
-
idx The frame of the buffer pool that was picked for eviction while containing a page with swizzled pointers.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPageUnfix()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics on page unfix.
Sets the referenced bit of the specified buffer frame (inside _refBits) if the template parameter on_hit is set.
- Parameters
-
idx The frame of the buffer pool that was unfixed.
Implements zero::buffer_pool::PageEvictioner.
§ updateOnPointerSwizzling()
|
inlinefinalvirtualnoexcept |
Updates the eviction statistics of pages when its pointer got swizzled in its parent page.
This page evictioner does not interact with pointer swizzling and therefore, this function does nothing.
- Parameters
-
idx The buffer frame index of the BufferPool whose pointer got swizzled in its corresponding parent page.
Implements zero::buffer_pool::PageEvictioner.
Member Data Documentation
§ _b1
|
protected |
LRU-list \(B_1\).
Represents the LRU-list \(B_1\) which contains the PageID s of pages evicted from \(T_1\).
§ _b2
|
protected |
LRU-list \(B_2\).
Represents the LRU-list \(B_2\) which contains the PageID s of pages evicted from \(T_2\).
§ _c
|
protected |
Parameter \(c\).
The number of buffer frames in the buffer pool.
§ _clocks
|
protected |
Clocks \(T_1\) and \(T_2\).
Represents the clocks \(T_1\) and \(T_2\) which contain eviction-specific metadata of the pages that are inside the buffer pool. Therefore there needs to be two clocks in the multi_clock::MultiHandedClock and the size of the clock equals the size of the buffer pool. As the CAR algorithm only stores a referenced bit, the value stored for each index is of Boolean type. And as the internal operation of multi_clock needs an invalid index (as well as a range of indexes starting from 0), the used invalid index is 0 which isn't used in the buffer pool as well.
§ _handMovement
|
protected |
Clock hand movements in current circulation.
The combined number of movements of the clock hands of \(T_1\) and \(T_2\). Is reset after _c movements.
§ _latch
|
protected |
Latch of _clocks, _b1 and _b2.
As the data structures _clocks, _b1 and _b2 are not thread-safe and as the pickVictim() and the updateOnPageMiss() methods might change those data structures concurrently, this lock needs to be acquired by those methods. The updateOnPageHit() and updateOnPageUnfix() functions are only called with the corresponding buffer frame latched and the access is also only atomic and therefore this method does not need to acquire this lock for its changes.
§ _p
|
protected |
Parameter \(p\).
Represents the parameter \(p\) which acts as a target size of \(T_1\).
The documentation for this class was generated from the following file:
- src/sm/page_evictioner_other.hpp
