Package edu.caltech.nanodb.storage

Interface PageReplacementPolicy

All Known Implementing Classes:

LRUReplacementPolicy

public interface PageReplacementPolicy

An interface specifying operations that must be provided by Buffer Manager page replacement policy implementations. Buffer Managers are somewhat unusual in that a candidate for eviction may not actually be evicted, for example if the buffer is currently pinned by some session. Therefore, the replacement policy provides suggestions for eviction, until all pages in the pool have been considered. If the Buffer Manager cannot free up enough space even after traversing the entire buffer pool, then an out-of-memory failure wil be reported.

The eviction process always starts with a call to startEvicting(). After this, one or more calls to suggestPageToEvict() are made, either until enough pages have been evicted, or until this method returns null to indicate that there are no more candidates for eviction.

Separately, the Buffer Manager will call accessPage(edu.caltech.nanodb.storage.DBPageID, boolean) and evictPage(edu.caltech.nanodb.storage.DBPageID) to indicate when pages are accessed and evicted. Note that these methods are never called during the above-described eviction process, since this will generate concurrent-modification exceptions for most simple implementations of replacement policies.

None of the methods in a page-replacement policy implementation need to be thread-safe, since the Buffer Manager always calls this interface in a synchronized context.

Method Summary

Modifier and Type	Method	Description
void	accessPage(DBPageID pageID, boolean alreadyResident)	Inform the replacement policy that a page in the buffer pool has been accessed.
void	evictPage(DBPageID pageID)	Inform the replacement policy that a page in the buffer pool has been evicted.
int	numResident()	This method returns the total number of pages that are resident, as recorded by the replacement policy.
void	startEvicting()	Inform the replacement policy that the Buffer Manager is ready to start evicting pages.
DBPageID	suggestPageToEvict()	After startEvicting() is called, this method suggests candidate pages for eviction to the Buffer Manager.

Method Details

accessPage

void accessPage(DBPageID pageID,
 boolean alreadyResident)

Inform the replacement policy that a page in the buffer pool has been accessed. The page may or may not have been resident before this access; this information is passed to the replacement policy.

Parameters:

pageID - the ID of the buffer-page that was accessed.

alreadyResident - a flag indicating whether the page was already resident in the buffer pool

evictPage

void evictPage(DBPageID pageID)

Inform the replacement policy that a page in the buffer pool has been evicted. This page definitely should have been resident when this method is called.

Parameters:

pageID - the ID of the buffer-page that was accessed.

startEvicting

void startEvicting()

Inform the replacement policy that the Buffer Manager is ready to start evicting pages. Replacement policy implementations should initialize their internal state such that subsequent calls to suggestPageToEvict() will provide candidate pages for eviction, with the most suitable for eviction returned first.

suggestPageToEvict

DBPageID suggestPageToEvict()

After startEvicting() is called, this method suggests candidate pages for eviction to the Buffer Manager. After all resident pages have been suggested, this method returns null.

Returns:

the next candidate page for eviction, or null if there are no more candidates for eviction.

numResident

int numResident()

This method returns the total number of pages that are resident, as recorded by the replacement policy. It is provided to sanity-check the operation of the Buffer Manager, which also records all buffers currently in use. If the count of entries doesn't match between the two objects, there is a bug in the system.

Returns:

the number of resident pages, as known by the replacement policy