Please enable JavaScript.
Coggle requires JavaScript to display documents.
Low Overhead High Perfromance Buffer Management Replacement Algorithm…
Low Overhead High Perfromance Buffer Management Replacement Algorithm
Abstract
Self tuning improvement to
LRU
called
LRU/k
. The improvement advocates giving priority to buffer pages based on
k
th most recent access
Background
Fetching data from disk is at leasts 100 times more expensive in terms of time requiured than fetching data from RAM
LRU never replaces more than a factor
B
as many elements as an optimal algorithm, with
B
being the size of the buffer.
Designing a query plan-based buffering algorithm that works in a multitasking system is difficult.
LRU/2 Important Parameters
Correlated Reference Period
A page will have low buffer priority even if it has been accessed multiple times, if those accesses occurred within a
correlated reference period
Retained Information Period
The length of time a page's access history is remembered after it is ejected from the buffer (200s recommended)
2Q Algorithm Description
As with
LRU/2, 2Q
tests pages for their second reference time
On the first reference to a page, the page is placed in a FIFO queue, called
A1
Partitioned into...
A1in
Retains newly referenced pages to satisfy repeated requests
A1out
Older first accesses will be thrown out of memory, but remembered here as pointers of pages
If a page in
A1
is referenced, it is moved to an LRU queue, called
Am
Experimental Results
Show that 2Q and LRU/2 have a considerably higher hit rate than LRU.
Trace Data from a DB2 Commercial Application
The results show that both 2Q and LRU/2 provide a significnatly higher hit rate than LRU and Gclock.
Trace Data from Program Text Accesses of a Windowing Application
The results show that both LRU/B and 2Q provide a significantly higher hit rate than LRU and Gclock.
Trace Data from an On-line Transaction Processing System
Same conclusions about relative performance.