15 #include "adaptiveLru.h"
16 #include "config_gobj.h"
17 #include "clockObject.h"
20 static const int HIGH_PRIORITY_SCALE = 4;
21 static const int LOW_PRIORITY_RANGE = 25;
29 AdaptiveLru(
const string &name,
size_t max_size) :
35 _current_frame_identifier = 0;
36 _weight = adaptive_lru_weight;
37 _max_updates_per_frame = adaptive_lru_max_updates_per_frame;
40 _static_list._next = &_static_list;
41 _static_list._prev = &_static_list;
44 for (index = 0; index < LPP_TotalPriorities; ++index) {
45 _page_array[index]._next = &_page_array[index];
46 _page_array[index]._prev = &_page_array[index];
62 while (_static_list._next != &_static_list) {
87 if (start_node == &_static_list) {
95 if (--num_updates <= 0) {
100 node->remove_from_list();
101 node->insert_before(&_static_list);
103 }
while (node != start_node && node != &_static_list);
120 int target_priority = page->_priority;
121 unsigned int lifetime_frames = _current_frame_identifier - page->_first_frame_identifier;
122 if (lifetime_frames > 0) {
123 if (page->_update_frame_identifier) {
124 unsigned int update_frames;
126 update_frames = (_current_frame_identifier - page->_update_frame_identifier);
127 if (update_frames > 0) {
128 PN_stdfloat update_average_frame_utilization =
129 (PN_stdfloat) (page->_update_total_usage) / (PN_stdfloat)update_frames;
131 page->_average_frame_utilization =
132 calculate_exponential_moving_average(update_average_frame_utilization,
133 page->_average_frame_utilization);
135 target_priority = page->_priority;
136 if (page->_average_frame_utilization >= 1.0f) {
137 int integer_average_frame_utilization;
139 integer_average_frame_utilization =
140 (int) ((page->_average_frame_utilization - 1.0f) *
141 (PN_stdfloat) HIGH_PRIORITY_SCALE);
142 if (integer_average_frame_utilization >= LPP_New) {
143 integer_average_frame_utilization = LPP_New;
145 integer_average_frame_utilization = LPP_New -
146 integer_average_frame_utilization;
147 target_priority = integer_average_frame_utilization;
149 int integer_average_frame_utilization;
151 integer_average_frame_utilization = (int)
152 (page->_average_frame_utilization *
153 (PN_stdfloat) LOW_PRIORITY_RANGE);
154 integer_average_frame_utilization = LOW_PRIORITY_RANGE -
155 integer_average_frame_utilization;
156 target_priority = LPP_New + integer_average_frame_utilization;
161 page->_update_frame_identifier = _current_frame_identifier;
162 page->_update_total_usage = 0;
165 if (target_priority != page->_priority) {
166 page->_priority = min(max(target_priority, 0), LPP_TotalPriorities - 1);
199 _priority = AdaptiveLru::LPP_New;
200 _first_frame_identifier = _lru->_current_frame_identifier;
201 _current_frame_identifier = _lru->_current_frame_identifier;
214 size_t counted_size = 0;
217 while (node != &_static_list) {
219 if (page->_current_frame_identifier + 1 >= _current_frame_identifier) {
220 counted_size += page->_lru_size;
240 if (_total_size > _max_size) {
253 output(ostream &out)
const {
255 out <<
"AdaptiveLru " << get_name()
256 <<
", " << _total_size <<
" of " << _max_size;
265 write(ostream &out,
int indent_level)
const {
266 indent(out, indent_level) << *
this <<
":\n";
275 for (index = 0; index < LPP_TotalPriorities; ++index) {
277 if (node != &_page_array[index]) {
278 indent(out, indent_level + 2) <<
"Priority " << index <<
":\n";
279 while (node != &_page_array[index]) {
281 indent(out, indent_level + 4) << *page;
283 if (page->_current_frame_identifier + 1 >= _current_frame_identifier) {
308 _total_size += page->_lru_size;
323 _total_size -= page->_lru_size;
338 if (page->_current_frame_identifier == _current_frame_identifier) {
341 ++(page->_current_frame_usage);
345 page->_current_frame_identifier = _current_frame_identifier;
346 page->_last_frame_usage = page->_current_frame_usage;
347 page->_current_frame_usage = 1;
354 ++(page->_update_total_usage);
373 for (index = LPP_TotalPriorities - 1; index >= 0; index--) {
382 while (node != &_page_array[index]) {
387 (page->_current_frame_identifier + 1 >= _current_frame_identifier)) {
397 if (_total_size <= target_size) {
411 }
while (hard_evict && attempts < 2);
426 size_t counted_size = 0;
428 for (index = 0; index < LPP_TotalPriorities; ++index) {
430 while (node != &_page_array[index]) {
432 counted_size += page->_lru_size;
433 if (page->_priority != index) {
434 nout <<
"page " << page <<
" has priority " << page->_priority
435 <<
" but is in queue " << index <<
"\n";
439 bool inserted_ok = pages.insert(page).second;
441 nout <<
"page " << page <<
" appears more than once in the dynamic index\n";
448 if (counted_size != _total_size) {
449 nout <<
"count " << counted_size <<
" bytes in dynamic index, but have " << _total_size <<
" on record\n";
456 while (node != &_static_list) {
458 counted_size += page->_lru_size;
460 if (pages.find(page) == pages.end()) {
461 nout <<
"page " << page <<
" appears in dynamic index, but not in static index (or multiple times in static index)\n";
469 if (counted_size != _total_size) {
470 nout <<
"count " << counted_size <<
" bytes in static index, but have " << _total_size <<
" on record\n";
483 AdaptiveLruPage(
size_t lru_size) :
487 _first_frame_identifier(0),
488 _current_frame_identifier(0),
489 _update_frame_identifier(0),
490 _current_frame_usage(0),
491 _last_frame_usage(0),
493 _update_total_usage(0),
494 _average_frame_utilization(1.0f)
506 _lru_size(copy._lru_size),
508 _first_frame_identifier(0),
509 _current_frame_identifier(0),
510 _update_frame_identifier(0),
511 _current_frame_usage(0),
512 _last_frame_usage(0),
514 _update_total_usage(0),
515 _average_frame_utilization(1.0f)
524 void AdaptiveLruPage::
566 void AdaptiveLruPage::
567 output(ostream &out)
const {
568 out <<
"page " <<
this <<
", " << _lru_size;
576 void AdaptiveLruPage::
577 write(ostream &out,
int indent_level)
const {
578 indent(out, indent_level) << *
this <<
"\n";
593 return _lru->_current_frame_identifier - _first_frame_identifier;
608 return _lru->_current_frame_identifier - _current_frame_identifier;
620 test_adaptive_lru() {
621 int maximum_memory = 3000000;
632 cerr <<
"created lru_page_0: " << lru_page_0 <<
"\n";
636 cerr <<
"created lru_page_1: " << lru_page_1 <<
"\n";
640 cerr <<
"created lru_page_2: " << lru_page_2 <<
"\n";
644 cerr <<
"created lru_page_3: " << lru_page_3 <<
"\n";
648 cerr <<
"created lru_page_4: " << lru_page_4 <<
"\n";
652 cerr <<
"created lru_page_5: " << lru_page_5 <<
"\n";
655 int total_frames = 300;
657 for (index = 0; index < total_frames; index++) {
658 cerr <<
"FRAME " << index <<
"\n";
663 lru_page_0->mark_used_lru(lru);
666 lru_page_1->mark_used_lru(lru);
667 lru_page_1->mark_used_lru(lru);
670 lru_page_2->mark_used_lru(lru);
673 if ((index % 10) == 0) {
674 lru_page_3->mark_used_lru(lru);
678 lru_page_4->mark_used_lru(lru);
682 lru_page_5->mark_used_lru(lru);
686 cerr <<
"Failed validation\n";
700 #endif // test_adaptive_lru
static ClockObject * get_global_clock()
Returns a pointer to the global ClockObject.
void release() const
Releases the lightMutex.
unsigned int get_num_inactive_frames() const
Returns the number of frames since the page was last accessed on its LRU.
void acquire() const
Grabs the lightMutex if it is available.
void do_remove_page(AdaptiveLruPage *page)
Removes a page from the LRU.
void set_lru_size(size_t lru_size)
Specifies the size of this page, presumably in bytes, although any unit is possible.
size_t get_lru_size() const
Returns the size of this page as reported to the LRU, presumably in bytes.
virtual void evict_lru()
Evicts the page from the LRU.
size_t count_active_size() const
Returns the total size of the pages that were enqueued since the last call to begin_epoch().
unsigned int get_num_frames() const
Returns the number of frames since the page was first added to its LRU.
bool do_validate()
Checks that the LRU is internally consistent.
void dequeue_lru()
Removes the page from its AdaptiveLru.
This just stores the pointers to implement a doubly-linked list of some kind of object.
void enqueue_lru(AdaptiveLru *lru)
Adds the page to the LRU for the first time, or marks it recently-accessed if it has already been add...
bool validate()
Checks that the LRU is internally self-consistent.
A base class for all things which can have a name.
Similar to MutexHolder, but for a light mutex.
void begin_epoch()
Marks the end of the previous epoch and the beginning of the next one.
void update_page(AdaptiveLruPage *page)
This updates the page's average utilization.
int get_frame_count(Thread *current_thread=Thread::get_current_thread()) const
Returns the number of times tick() has been called since the ClockObject was created, or since it was last reset.
One atomic piece that may be managed by a AdaptiveLru chain.
void do_add_page(AdaptiveLruPage *page)
Adds a new page the the LRU.
A basic LRU-type algorithm, except that it is adaptive and attempts to avoid evicting pages that have...
void do_access_page(AdaptiveLruPage *page)
Marks a page accessed.
void do_partial_lru_update(int num_updates)
This only updates a number of pages up to the specified maximum_updates.
void do_evict_to(size_t target_size, bool hard_evict)
Evicts pages until the LRU is within the indicated size.
This is our own Panda specialization on the default STL set.