Panda3D
|
00001 // Filename: adaptiveLru.cxx 00002 // Created by: drose (03Sep08) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "adaptiveLru.h" 00016 #include "config_gobj.h" 00017 #include "clockObject.h" 00018 #include "indent.h" 00019 00020 static const int HIGH_PRIORITY_SCALE = 4; 00021 static const int LOW_PRIORITY_RANGE = 25; 00022 00023 //////////////////////////////////////////////////////////////////// 00024 // Function: AdaptiveLru::Constructor 00025 // Access: Published 00026 // Description: 00027 //////////////////////////////////////////////////////////////////// 00028 AdaptiveLru:: 00029 AdaptiveLru(const string &name, size_t max_size) : 00030 Namable(name) 00031 { 00032 _total_size = 0; 00033 _max_size = max_size; 00034 00035 _current_frame_identifier = 0; 00036 _weight = adaptive_lru_weight; 00037 _max_updates_per_frame = adaptive_lru_max_updates_per_frame; 00038 00039 // Initialize our list heads to empty. 00040 _static_list._next = &_static_list; 00041 _static_list._prev = &_static_list; 00042 00043 int index; 00044 for (index = 0; index < LPP_TotalPriorities; ++index) { 00045 _page_array[index]._next = &_page_array[index]; 00046 _page_array[index]._prev = &_page_array[index]; 00047 } 00048 } 00049 00050 //////////////////////////////////////////////////////////////////// 00051 // Function: AdaptiveLru::Destructor 00052 // Access: Published, Virtual 00053 // Description: 00054 //////////////////////////////////////////////////////////////////// 00055 AdaptiveLru:: 00056 ~AdaptiveLru() { 00057 #ifndef NDEBUG 00058 // We're shutting down. Force-remove everything remaining, but 00059 // don't explicitly evict it (that would force vertex buffers to 00060 // write themselves to disk unnecessarily). 00061 00062 while (_static_list._next != &_static_list) { 00063 nassertv(_static_list._next != (LinkedListNode *)NULL); 00064 AdaptiveLruPage *page = (AdaptiveLruPage *)(AdaptiveLruPageStaticList *)_static_list._next; 00065 00066 page->_lru = NULL; 00067 ((AdaptiveLruPageDynamicList *)page)->remove_from_list(); 00068 ((AdaptiveLruPageStaticList *)page)->remove_from_list(); 00069 } 00070 #endif 00071 } 00072 00073 //////////////////////////////////////////////////////////////////// 00074 // Function: AdaptiveLru::do_partial_lru_update 00075 // Access: Private 00076 // Description: This only updates a number of pages up to the 00077 // specified maximum_updates. Assumes the lock is held. 00078 //////////////////////////////////////////////////////////////////// 00079 void AdaptiveLru:: 00080 do_partial_lru_update(int num_updates) { 00081 // Iterate sequentially through the static list of pages. As we 00082 // process each page, pop it and push it back on the tail. Stop 00083 // when we have processed num_updates, or come back to the starting 00084 // one. 00085 00086 AdaptiveLruPageStaticList *start_node = (AdaptiveLruPageStaticList *)_static_list._next; 00087 if (start_node == &_static_list) { 00088 // List is empty. 00089 return; 00090 } 00091 00092 AdaptiveLruPageStaticList *node = start_node; 00093 do { 00094 AdaptiveLruPageStaticList *next = (AdaptiveLruPageStaticList *)node->_next; 00095 if (--num_updates <= 0) { 00096 return; 00097 } 00098 00099 update_page((AdaptiveLruPage *)node); 00100 node->remove_from_list(); 00101 node->insert_before(&_static_list); 00102 node = next; 00103 } while (node != start_node && node != &_static_list); 00104 } 00105 00106 //////////////////////////////////////////////////////////////////// 00107 // Function: AdaptiveLru::update_page 00108 // Access: Private 00109 // Description: This updates the page's average utilization. 00110 // Priority LPP_New is considered to be average usage 00111 // of 1.0 (which means the page is used once per frame 00112 // on average). Priorities < LPP_New are for pages 00113 // used more than once per frame and Priorities > 00114 // LPP_New are for pages used less than once per frame. 00115 // 00116 // Assumes the lock is held. 00117 //////////////////////////////////////////////////////////////////// 00118 void AdaptiveLru:: 00119 update_page(AdaptiveLruPage *page) { 00120 int target_priority = page->_priority; 00121 unsigned int lifetime_frames = _current_frame_identifier - page->_first_frame_identifier; 00122 if (lifetime_frames > 0) { 00123 if (page->_update_frame_identifier) { 00124 unsigned int update_frames; 00125 00126 update_frames = (_current_frame_identifier - page->_update_frame_identifier); 00127 if (update_frames > 0) { 00128 PN_stdfloat update_average_frame_utilization = 00129 (PN_stdfloat) (page->_update_total_usage) / (PN_stdfloat)update_frames; 00130 00131 page->_average_frame_utilization = 00132 calculate_exponential_moving_average(update_average_frame_utilization, 00133 page->_average_frame_utilization); 00134 00135 target_priority = page->_priority; 00136 if (page->_average_frame_utilization >= 1.0f) { 00137 int integer_average_frame_utilization; 00138 00139 integer_average_frame_utilization = 00140 (int) ((page->_average_frame_utilization - 1.0f) * 00141 (PN_stdfloat) HIGH_PRIORITY_SCALE); 00142 if (integer_average_frame_utilization >= LPP_New) { 00143 integer_average_frame_utilization = LPP_New; 00144 } 00145 integer_average_frame_utilization = LPP_New - 00146 integer_average_frame_utilization; 00147 target_priority = integer_average_frame_utilization; 00148 } else { 00149 int integer_average_frame_utilization; 00150 00151 integer_average_frame_utilization = (int) 00152 (page->_average_frame_utilization * 00153 (PN_stdfloat) LOW_PRIORITY_RANGE); 00154 integer_average_frame_utilization = LOW_PRIORITY_RANGE - 00155 integer_average_frame_utilization; 00156 target_priority = LPP_New + integer_average_frame_utilization; 00157 } 00158 } 00159 } 00160 00161 page->_update_frame_identifier = _current_frame_identifier; 00162 page->_update_total_usage = 0; 00163 } 00164 00165 if (target_priority != page->_priority) { 00166 page->_priority = min(max(target_priority, 0), LPP_TotalPriorities - 1); 00167 ((AdaptiveLruPageDynamicList *)page)->remove_from_list(); 00168 ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]); 00169 } 00170 } 00171 00172 //////////////////////////////////////////////////////////////////// 00173 // Function: AdaptiveLruPage::enqueue_lru 00174 // Access: Published 00175 // Description: Adds the page to the LRU for the first time, or marks 00176 // it recently-accessed if it has already been added. 00177 // 00178 // If lru is NULL, it means to remove this page from its 00179 // LRU. 00180 //////////////////////////////////////////////////////////////////// 00181 void AdaptiveLruPage:: 00182 enqueue_lru(AdaptiveLru *lru) { 00183 if (lru != _lru && _lru != (AdaptiveLru *)NULL) { 00184 // It was previously on a different LRU. Remove it first. 00185 _lru->do_remove_page(this); 00186 _lru = NULL; 00187 } 00188 00189 if (lru == _lru) { 00190 if (_lru != (AdaptiveLru *)NULL) { 00191 // It's already on this LRU. Access it. 00192 _lru->do_access_page(this); 00193 } 00194 } else { 00195 nassertv(lru != (AdaptiveLru *)NULL); 00196 // Add it to a new LRU. 00197 _lru = lru; 00198 00199 _priority = AdaptiveLru::LPP_New; 00200 _first_frame_identifier = _lru->_current_frame_identifier; 00201 _current_frame_identifier = _lru->_current_frame_identifier; 00202 _lru->do_add_page(this); 00203 } 00204 } 00205 00206 //////////////////////////////////////////////////////////////////// 00207 // Function: AdaptiveLru::count_active_size 00208 // Access: Published 00209 // Description: Returns the total size of the pages that were 00210 // enqueued since the last call to begin_epoch(). 00211 //////////////////////////////////////////////////////////////////// 00212 size_t AdaptiveLru:: 00213 count_active_size() const { 00214 size_t counted_size = 0; 00215 00216 AdaptiveLruPageStaticList *node = (AdaptiveLruPageStaticList *)_static_list._next; 00217 while (node != &_static_list) { 00218 AdaptiveLruPage *page = (AdaptiveLruPage *)node; 00219 if (page->_current_frame_identifier + 1 >= _current_frame_identifier) { 00220 counted_size += page->_lru_size; 00221 } 00222 node = (AdaptiveLruPageStaticList *)node->_next; 00223 } 00224 00225 return counted_size; 00226 } 00227 00228 //////////////////////////////////////////////////////////////////// 00229 // Function: AdaptiveLru::begin_epoch 00230 // Access: Published 00231 // Description: Marks the end of the previous epoch and the beginning 00232 // of the next one. This will evict any objects that 00233 // are pending eviction, and also update any internal 00234 // bookkeeping. 00235 //////////////////////////////////////////////////////////////////// 00236 void AdaptiveLru:: 00237 begin_epoch() { 00238 LightMutexHolder holder(_lock); 00239 do_partial_lru_update(_max_updates_per_frame); 00240 if (_total_size > _max_size) { 00241 do_evict_to(_max_size, false); 00242 } 00243 00244 _current_frame_identifier = ClockObject::get_global_clock()->get_frame_count(); 00245 } 00246 00247 //////////////////////////////////////////////////////////////////// 00248 // Function: AdaptiveLru::output 00249 // Access: Published 00250 // Description: 00251 //////////////////////////////////////////////////////////////////// 00252 void AdaptiveLru:: 00253 output(ostream &out) const { 00254 LightMutexHolder holder(_lock); 00255 out << "AdaptiveLru " << get_name() 00256 << ", " << _total_size << " of " << _max_size; 00257 } 00258 00259 //////////////////////////////////////////////////////////////////// 00260 // Function: AdaptiveLru::write 00261 // Access: Published, Virtual 00262 // Description: 00263 //////////////////////////////////////////////////////////////////// 00264 void AdaptiveLru:: 00265 write(ostream &out, int indent_level) const { 00266 indent(out, indent_level) << *this << ":\n"; 00267 00268 // We write out the list backwards. Things we write out first are 00269 // the freshest in the LRU. Things at the end of the list will be 00270 // the next to be evicted. 00271 00272 LightMutexHolder holder(_lock); 00273 00274 int index; 00275 for (index = 0; index < LPP_TotalPriorities; ++index) { 00276 AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._prev; 00277 if (node != &_page_array[index]) { 00278 indent(out, indent_level + 2) << "Priority " << index << ":\n"; 00279 while (node != &_page_array[index]) { 00280 AdaptiveLruPage *page = (AdaptiveLruPage *)node; 00281 indent(out, indent_level + 4) << *page; 00282 00283 if (page->_current_frame_identifier + 1 >= _current_frame_identifier) { 00284 out << " (active)"; 00285 } 00286 out << "\n"; 00287 00288 node = (AdaptiveLruPageDynamicList *)node->_prev; 00289 } 00290 } 00291 } 00292 00293 #ifndef NDEBUG 00294 ((AdaptiveLru *)this)->do_validate(); 00295 #endif 00296 } 00297 00298 //////////////////////////////////////////////////////////////////// 00299 // Function: AdaptiveLru::do_add_page 00300 // Access: Private 00301 // Description: Adds a new page the the LRU. 00302 //////////////////////////////////////////////////////////////////// 00303 void AdaptiveLru:: 00304 do_add_page(AdaptiveLruPage *page) { 00305 nassertv(page != (AdaptiveLruPage *)NULL && page->_lru == this); 00306 LightMutexHolder holder(_lock); 00307 00308 _total_size += page->_lru_size; 00309 ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]); 00310 ((AdaptiveLruPageStaticList *)page)->insert_before(&_static_list); 00311 } 00312 00313 //////////////////////////////////////////////////////////////////// 00314 // Function: AdaptiveLru::do_remove_page 00315 // Access: Private 00316 // Description: Removes a page from the LRU. 00317 //////////////////////////////////////////////////////////////////// 00318 void AdaptiveLru:: 00319 do_remove_page(AdaptiveLruPage *page) { 00320 nassertv(page != (AdaptiveLruPage *)NULL && page->_lru == this); 00321 LightMutexHolder holder(_lock); 00322 00323 _total_size -= page->_lru_size; 00324 ((AdaptiveLruPageDynamicList *)page)->remove_from_list(); 00325 ((AdaptiveLruPageStaticList *)page)->remove_from_list(); 00326 } 00327 00328 //////////////////////////////////////////////////////////////////// 00329 // Function: AdaptiveLru::do_access_page 00330 // Access: Private 00331 // Description: Marks a page accessed. 00332 //////////////////////////////////////////////////////////////////// 00333 void AdaptiveLru:: 00334 do_access_page(AdaptiveLruPage *page) { 00335 nassertv(page != (AdaptiveLruPage *)NULL && page->_lru == this); 00336 LightMutexHolder holder(_lock); 00337 00338 if (page->_current_frame_identifier == _current_frame_identifier) { 00339 // This is the second or more time this page is accessed this 00340 // frame. 00341 ++(page->_current_frame_usage); 00342 00343 } else { 00344 // This page has not yet been accessed this frame. Update it. 00345 page->_current_frame_identifier = _current_frame_identifier; 00346 page->_last_frame_usage = page->_current_frame_usage; 00347 page->_current_frame_usage = 1; 00348 } 00349 00350 // Move it to the tail of its priority list. 00351 ((AdaptiveLruPageDynamicList *)page)->remove_from_list(); 00352 ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]); 00353 00354 ++(page->_update_total_usage); 00355 } 00356 00357 //////////////////////////////////////////////////////////////////// 00358 // Function: AdaptiveLru::do_evict_to 00359 // Access: Private 00360 // Description: Evicts pages until the LRU is within the indicated 00361 // size. Assumes the lock is already held. If 00362 // hard_evict is false, does not evict "active" pages 00363 // that were added within this epoch. 00364 //////////////////////////////////////////////////////////////////// 00365 void AdaptiveLru:: 00366 do_evict_to(size_t target_size, bool hard_evict) { 00367 int attempts; 00368 00369 attempts = 0; 00370 do { 00371 // page out lower priority pages first 00372 int index; 00373 for (index = LPP_TotalPriorities - 1; index >= 0; index--) { 00374 00375 // Store the current end of the list. If pages re-enqueue 00376 // themselves during this traversal, we don't want to visit them 00377 // twice. 00378 AdaptiveLruPageDynamicList *end = (AdaptiveLruPageDynamicList *)_page_array[index]._prev; 00379 00380 AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._next; 00381 00382 while (node != &_page_array[index]) { 00383 AdaptiveLruPageDynamicList *next = (AdaptiveLruPageDynamicList *)node->_next; 00384 AdaptiveLruPage *page = (AdaptiveLruPage *)node; 00385 00386 if (attempts == 0 && 00387 (page->_current_frame_identifier + 1 >= _current_frame_identifier)) { 00388 // avoid swapping out pages used in the current and last 00389 // frame on the first attempt 00390 00391 } else { 00392 // We must release the lock while we call evict_lru(). 00393 _lock.release(); 00394 page->evict_lru(); 00395 _lock.acquire(); 00396 00397 if (_total_size <= target_size) { 00398 // We've evicted enough to satisfy our target. 00399 return; 00400 } 00401 } 00402 if (node == end) { 00403 // We've reached the former end of the list. Stop here; 00404 // everything after has been re-queued. 00405 break; 00406 } 00407 node = next; 00408 } 00409 } 00410 attempts++; 00411 } while (hard_evict && attempts < 2); 00412 } 00413 00414 //////////////////////////////////////////////////////////////////// 00415 // Function: AdaptiveLru::do_validate 00416 // Access: Private 00417 // Description: Checks that the LRU is internally consistent. Assume 00418 // the lock is already held. 00419 //////////////////////////////////////////////////////////////////// 00420 bool AdaptiveLru:: 00421 do_validate() { 00422 bool okflag = true; 00423 pset<AdaptiveLruPage *> pages; 00424 00425 // First, walk through the dynamic pages. 00426 size_t counted_size = 0; 00427 int index; 00428 for (index = 0; index < LPP_TotalPriorities; ++index) { 00429 AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._next; 00430 while (node != &_page_array[index]) { 00431 AdaptiveLruPage *page = (AdaptiveLruPage *)node; 00432 counted_size += page->_lru_size; 00433 if (page->_priority != index) { 00434 nout << "page " << page << " has priority " << page->_priority 00435 << " but is in queue " << index << "\n"; 00436 okflag = false; 00437 } 00438 00439 bool inserted_ok = pages.insert(page).second; 00440 if (!inserted_ok) { 00441 nout << "page " << page << " appears more than once in the dynamic index\n"; 00442 okflag = false; 00443 } 00444 node = (AdaptiveLruPageDynamicList *)node->_next; 00445 } 00446 } 00447 00448 if (counted_size != _total_size) { 00449 nout << "count " << counted_size << " bytes in dynamic index, but have " << _total_size << " on record\n"; 00450 okflag = false; 00451 } 00452 00453 // Now, walk through the static pages. 00454 counted_size = 0; 00455 AdaptiveLruPageStaticList *node = (AdaptiveLruPageStaticList *)_static_list._next; 00456 while (node != &_static_list) { 00457 AdaptiveLruPage *page = (AdaptiveLruPage *)node; 00458 counted_size += page->_lru_size; 00459 00460 if (pages.find(page) == pages.end()) { 00461 nout << "page " << page << " appears in dynamic index, but not in static index (or multiple times in static index)\n"; 00462 okflag = false; 00463 } else { 00464 pages.erase(page); 00465 } 00466 node = (AdaptiveLruPageStaticList *)node->_next; 00467 } 00468 00469 if (counted_size != _total_size) { 00470 nout << "count " << counted_size << " bytes in static index, but have " << _total_size << " on record\n"; 00471 okflag = false; 00472 } 00473 00474 return okflag; 00475 } 00476 00477 //////////////////////////////////////////////////////////////////// 00478 // Function: AdaptiveLruPage::Constructor 00479 // Access: Protected 00480 // Description: 00481 //////////////////////////////////////////////////////////////////// 00482 AdaptiveLruPage:: 00483 AdaptiveLruPage(size_t lru_size) : 00484 _lru(NULL), 00485 _lru_size(lru_size), 00486 _priority(0), 00487 _first_frame_identifier(0), 00488 _current_frame_identifier(0), 00489 _update_frame_identifier(0), 00490 _current_frame_usage(0), 00491 _last_frame_usage(0), 00492 _total_usage(0), 00493 _update_total_usage(0), 00494 _average_frame_utilization(1.0f) 00495 { 00496 } 00497 00498 //////////////////////////////////////////////////////////////////// 00499 // Function: AdaptiveLruPage::Copy Constructor 00500 // Access: Protected 00501 // Description: 00502 //////////////////////////////////////////////////////////////////// 00503 AdaptiveLruPage:: 00504 AdaptiveLruPage(const AdaptiveLruPage ©) : 00505 _lru(NULL), 00506 _lru_size(copy._lru_size), 00507 _priority(0), 00508 _first_frame_identifier(0), 00509 _current_frame_identifier(0), 00510 _update_frame_identifier(0), 00511 _current_frame_usage(0), 00512 _last_frame_usage(0), 00513 _total_usage(0), 00514 _update_total_usage(0), 00515 _average_frame_utilization(1.0f) 00516 { 00517 } 00518 00519 //////////////////////////////////////////////////////////////////// 00520 // Function: AdaptiveLruPage::Copy Assignment Operator 00521 // Access: Protected 00522 // Description: 00523 //////////////////////////////////////////////////////////////////// 00524 void AdaptiveLruPage:: 00525 operator = (const AdaptiveLruPage ©) { 00526 set_lru_size(copy.get_lru_size()); 00527 } 00528 00529 //////////////////////////////////////////////////////////////////// 00530 // Function: AdaptiveLruPage::Destructor 00531 // Access: Published, Virtual 00532 // Description: 00533 //////////////////////////////////////////////////////////////////// 00534 AdaptiveLruPage:: 00535 ~AdaptiveLruPage() { 00536 if (_lru != NULL) { 00537 dequeue_lru(); 00538 } 00539 } 00540 00541 //////////////////////////////////////////////////////////////////// 00542 // Function: AdaptiveLruPage::evict_lru 00543 // Access: Published, Virtual 00544 // Description: Evicts the page from the LRU. Called internally when 00545 // the LRU determines that it is full. May also be 00546 // called externally when necessary to explicitly evict 00547 // the page. 00548 // 00549 // It is legal for this method to either evict the page 00550 // as requested, do nothing (in which case the eviction 00551 // will be requested again at the next epoch), or 00552 // requeue itself on the tail of the queue (in which 00553 // case the eviction will be requested again much 00554 // later). 00555 //////////////////////////////////////////////////////////////////// 00556 void AdaptiveLruPage:: 00557 evict_lru() { 00558 dequeue_lru(); 00559 } 00560 00561 //////////////////////////////////////////////////////////////////// 00562 // Function: AdaptiveLruPage::output 00563 // Access: Published, Virtual 00564 // Description: 00565 //////////////////////////////////////////////////////////////////// 00566 void AdaptiveLruPage:: 00567 output(ostream &out) const { 00568 out << "page " << this << ", " << _lru_size; 00569 } 00570 00571 //////////////////////////////////////////////////////////////////// 00572 // Function: AdaptiveLruPage::write 00573 // Access: Published, Virtual 00574 // Description: 00575 //////////////////////////////////////////////////////////////////// 00576 void AdaptiveLruPage:: 00577 write(ostream &out, int indent_level) const { 00578 indent(out, indent_level) << *this << "\n"; 00579 } 00580 00581 //////////////////////////////////////////////////////////////////// 00582 // Function: AdaptiveLruPage::get_num_frames 00583 // Access: Published 00584 // Description: Returns the number of frames since the page was first 00585 // added to its LRU. Returns 0 if it does not have an 00586 // LRU. 00587 //////////////////////////////////////////////////////////////////// 00588 unsigned int AdaptiveLruPage:: 00589 get_num_frames() const { 00590 if (_lru == (AdaptiveLru *)NULL) { 00591 return 0; 00592 } 00593 return _lru->_current_frame_identifier - _first_frame_identifier; 00594 } 00595 00596 //////////////////////////////////////////////////////////////////// 00597 // Function: AdaptiveLruPage::get_num_inactive_frames 00598 // Access: Published 00599 // Description: Returns the number of frames since the page was last 00600 // accessed on its LRU. Returns 0 if it does not have 00601 // an LRU. 00602 //////////////////////////////////////////////////////////////////// 00603 unsigned int AdaptiveLruPage:: 00604 get_num_inactive_frames() const { 00605 if (_lru == (AdaptiveLru *)NULL) { 00606 return 0; 00607 } 00608 return _lru->_current_frame_identifier - _current_frame_identifier; 00609 } 00610 00611 00612 #if 0 00613 00614 //////////////////////////////////////////////////////////////////// 00615 // Function: test_adaptive_lru 00616 // Access: 00617 // Description: Unit test function for Lru. 00618 //////////////////////////////////////////////////////////////////// 00619 void 00620 test_adaptive_lru() { 00621 int maximum_memory = 3000000; 00622 AdaptiveLru *lru = new AdaptiveLru("test", maximum_memory); 00623 00624 AdaptiveLruPage *lru_page_0; 00625 AdaptiveLruPage *lru_page_1; 00626 AdaptiveLruPage *lru_page_2; 00627 AdaptiveLruPage *lru_page_3; 00628 AdaptiveLruPage *lru_page_4; 00629 AdaptiveLruPage *lru_page_5; 00630 00631 lru_page_0 = new AdaptiveLruPage(1000000); 00632 cerr << "created lru_page_0: " << lru_page_0 << "\n"; 00633 lru_page_0->enqueue_lru(lru); 00634 00635 lru_page_1 = new AdaptiveLruPage(1000000); 00636 cerr << "created lru_page_1: " << lru_page_1 << "\n"; 00637 lru_page_1->enqueue_lru(lru); 00638 00639 lru_page_2 = new AdaptiveLruPage(1000000); 00640 cerr << "created lru_page_2: " << lru_page_2 << "\n"; 00641 lru_page_2->enqueue_lru(lru); 00642 00643 lru_page_3 = new AdaptiveLruPage(1000000); 00644 cerr << "created lru_page_3: " << lru_page_3 << "\n"; 00645 lru_page_3->enqueue_lru(lru); 00646 00647 lru_page_4 = new AdaptiveLruPage(1000000); 00648 cerr << "created lru_page_4: " << lru_page_4 << "\n"; 00649 lru_page_4->enqueue_lru(lru); 00650 00651 lru_page_5 = new AdaptiveLruPage(1000000); 00652 cerr << "created lru_page_5: " << lru_page_5 << "\n"; 00653 lru_page_5->enqueue_lru(lru); 00654 00655 int total_frames = 300; 00656 int index; 00657 for (index = 0; index < total_frames; index++) { 00658 cerr << "FRAME " << index << "\n"; 00659 00660 lru->begin_epoch(); 00661 00662 if (index <= 5) { 00663 lru_page_0->mark_used_lru(lru); 00664 } 00665 00666 lru_page_1->mark_used_lru(lru); 00667 lru_page_1->mark_used_lru(lru); 00668 00669 if (index & 0x01) { 00670 lru_page_2->mark_used_lru(lru); 00671 } 00672 00673 if ((index % 10) == 0) { 00674 lru_page_3->mark_used_lru(lru); 00675 } 00676 00677 if (index >= 100) { 00678 lru_page_4->mark_used_lru(lru); 00679 } 00680 00681 if (index >= 200) { 00682 lru_page_5->mark_used_lru(lru); 00683 } 00684 00685 if (!lru->validate()) { 00686 cerr << "Failed validation\n"; 00687 break; 00688 } 00689 } 00690 00691 delete lru; 00692 delete lru_page_0; 00693 delete lru_page_1; 00694 delete lru_page_2; 00695 delete lru_page_3; 00696 delete lru_page_4; 00697 delete lru_page_5; 00698 } 00699 00700 #endif // test_adaptive_lru