00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #define LRU_UNIT_TEST 0
00018
00019 #include <stdio.h>
00020 #include <stdlib.h>
00021
00022
00023 #include "lru.h"
00024
00025
00026 static const int HIGH_PRIORITY_SCALE = 4;
00027 static const int LOW_PRIORITY_RANGE = 25;
00028
00029
00030
00031
00032
00033
00034 Lru::Lru (int maximum_memory, int maximum_pages, int maximum_page_types)
00035 {
00036 if(this) {
00037 int index;
00038
00039 memset(&this->_m, 0, sizeof (LruVariables));
00040
00041 this->_m.maximum_memory = maximum_memory;
00042 this->_m.maximum_pages = maximum_pages;
00043 this->_m.maximum_page_types = maximum_page_types;
00044 this->_m.available_memory = maximum_memory;
00045 this->_m.current_frame_identifier = 1;
00046 this->_m.weight = 0.20f;
00047
00048 this->set_maximum_frame_bandwidth_utilization(2000000.0f);
00049
00050 for(index = 0; index < MAXIMUM_LRU_PAGE_TYPES; index++) {
00051 this->_m.page_in_function_array[index] = default_page_in_function;
00052 this->_m.page_out_function_array[index] = default_page_out_function;
00053 }
00054
00055 if(maximum_pages > 0) {
00056 this -> _m.lru_page_pool = new LruPage * [maximum_pages];
00057 this -> _m.lru_page_free_pool = new LruPage * [maximum_pages];
00058 for(index = 0; index < maximum_pages; index++) {
00059 LruPage * lru_page;
00060
00061 lru_page = new LruPage ( );
00062 if(lru_page) {
00063 lru_page->_m.v.pre_allocated = true;
00064 this->_m.lru_page_pool[index] = lru_page;
00065 }
00066 else {
00067
00068 }
00069 }
00070 }
00071
00072 if(maximum_page_types > 0) {
00073 this -> _m.page_type_statistics_array =
00074 new PageTypeStatistics [maximum_page_types];
00075 }
00076
00077 #if ENABLE_MUTEX
00078 this -> _m.mutex = new Mutex ("lru");
00079 #endif
00080
00081 }
00082 }
00083
00084
00085
00086
00087
00088
00089 Lru::~Lru ( )
00090 {
00091 int index;
00092 LruPage * lru_page;
00093
00094
00095 if(this->_m.maximum_pages > 0) {
00096 if(this->_m.lru_page_free_pool) {
00097 for(index = 0; index < this->_m.maximum_pages; index++) {
00098 lru_page = this->_m.lru_page_pool[index];
00099 if(lru_page->_m.v.in_lru) {
00100 this->remove_page(lru_page);
00101 }
00102
00103 delete lru_page;
00104 }
00105
00106 delete this -> _m.lru_page_free_pool;
00107 }
00108 if(this->_m.lru_page_pool) {
00109 delete this -> _m.lru_page_pool;
00110 }
00111 }
00112
00113
00114 for(index = 0; index < LPP_TotalPriorities; index++) {
00115 LruPage * next_lru_page;
00116
00117 lru_page = this->_m.lru_page_array[index];
00118 while(lru_page) {
00119 next_lru_page = lru_page->_m.next;
00120
00121 delete lru_page;
00122
00123 lru_page = next_lru_page;
00124 }
00125 }
00126
00127 if(this->_m.page_type_statistics_array) {
00128 delete this -> _m.page_type_statistics_array;
00129 }
00130
00131 #if ENABLE_MUTEX
00132 if(this->_m.mutex) {
00133 delete this -> _m.mutex;
00134 }
00135 #endif
00136
00137 }
00138
00139
00140
00141
00142
00143
00144
00145 LruPage::LruPage ( )
00146 {
00147 if(this) {
00148 memset(&this->_m, 0, sizeof (LruPageVariables));
00149 _m.name = "";
00150 }
00151 }
00152
00153
00154
00155
00156
00157
00158
00159 LruPage::~LruPage ( )
00160 {
00161
00162 }
00163
00164
00165
00166
00167
00168
00169 void LruPage::change_priority (int delta)
00170 {
00171 this->_m.priority_change += delta;
00172 }
00173
00174
00175
00176
00177
00178
00179
00180 bool Lru::register_lru_page_type (int index,
00181 LruPageTypeFunction page_in_function,
00182 LruPageTypeFunction page_out_function)
00183 {
00184 bool state;
00185
00186 state = false;
00187 if(index >= 0 && index < MAXIMUM_LRU_PAGE_TYPES) {
00188 this->_m.page_in_function_array[index] = page_in_function;
00189 this->_m.page_out_function_array[index] = page_out_function;
00190 state = true;
00191 }
00192
00193 return state;
00194 }
00195
00196
00197
00198
00199
00200
00201 LruPage *Lru::allocate_page (int size)
00202 {
00203 LruPage * lru_page;
00204
00205 lru_page = 0;
00206 if(size <= this->_m.maximum_memory) {
00207 if(this->_m.maximum_pages) {
00208 if(this->_m.total_lru_pages_in_free_pool > 0) {
00209 lru_page =
00210 this->_m.lru_page_free_pool [this->_m.total_lru_pages_in_free_pool - 1];
00211 this->_m.total_lru_pages_in_free_pool--;
00212
00213 memset (&lru_page -> _m, 0, sizeof (LruPage::LruPageVariables));
00214 lru_page->_m.v.pre_allocated = true;
00215 }
00216 else {
00217 if(this->_m.total_lru_pages_in_pool < this->_m.maximum_pages) {
00218 lru_page = this->_m.lru_page_pool[this->_m.total_lru_pages_in_pool];
00219 this->_m.total_lru_pages_in_pool++;
00220 }
00221 else {
00222
00223 lru_page = new LruPage ( );
00224 }
00225 }
00226 }
00227 else {
00228 lru_page = new LruPage;
00229 }
00230 if(lru_page) {
00231 lru_page->_m.lru = this;
00232 lru_page->_m.size = size;
00233 lru_page->_m.first_frame_identifier = this->_m.current_frame_identifier;
00234 lru_page->_m.last_frame_identifier = this->_m.current_frame_identifier;
00235
00236 lru_page->_m.v.allocated = true;
00237 lru_page->_m.identifier = this->_m.identifier;
00238
00239 lru_page->_m.average_frame_utilization = 1.0f;
00240
00241 this->_m.total_pages++;
00242 this->_m.identifier++;
00243 }
00244 else {
00245
00246
00247
00248 }
00249 }
00250 else {
00251
00252
00253
00254 }
00255
00256 return lru_page;
00257 }
00258
00259
00260
00261
00262
00263
00264 void Lru::update_start_update_lru_page (LruPage *lru_page)
00265 {
00266 if(lru_page) {
00267 if(this->_m.start_update_lru_page == lru_page) {
00268 if(lru_page->_m.next) {
00269 this->_m.start_update_lru_page = lru_page->_m.next;
00270 }
00271 else {
00272 if((this->_m.start_priority_index + 1) >= LPP_TotalPriorities) {
00273 this->_m.start_priority_index = 0;
00274 }
00275 else {
00276 this->_m.start_priority_index = this->_m.start_priority_index + 1;
00277 }
00278
00279 this->_m.start_update_lru_page = 0;
00280 }
00281 }
00282 }
00283 }
00284
00285
00286
00287
00288
00289
00290 void Lru::free_page (LruPage *lru_page)
00291 {
00292 if(this->_m.total_pages > 0) {
00293 if(lru_page) {
00294 LruMutexHolder(this->_m.mutex);
00295
00296 this->update_start_update_lru_page(lru_page);
00297
00298 if(lru_page->_m.v.in_cache) {
00299 this->_m.available_memory += lru_page->_m.size;
00300 }
00301
00302 if(lru_page->_m.v.pre_allocated) {
00303 if(this->_m.maximum_pages) {
00304 lru_page->_m.v.allocated = false;
00305 this->_m.lru_page_free_pool [this->_m.total_lru_pages_in_free_pool] =
00306 lru_page;
00307 this->_m.total_lru_pages_in_free_pool++;
00308 }
00309 else {
00310
00311 }
00312 }
00313 else {
00314 delete lru_page;
00315 }
00316
00317 this->_m.total_pages--;
00318 }
00319 }
00320 else {
00321
00322
00323
00324 }
00325 }
00326
00327
00328
00329
00330
00331
00332 void Lru::add_page (LruPagePriority priority, LruPage *lru_page)
00333 {
00334 if(lru_page) {
00335 LruMutexHolder(this->_m.mutex);
00336
00337 LruPage * first_lru_page;
00338
00339 lru_page->_m.priority = priority;
00340
00341 first_lru_page = this->_m.lru_page_array[lru_page->_m.priority];
00342 if(first_lru_page) {
00343 first_lru_page->_m.previous = lru_page;
00344 lru_page->_m.next = first_lru_page;
00345 }
00346
00347 this->_m.lru_page_array[lru_page->_m.priority] = lru_page;
00348
00349 lru_page->_m.v.in_lru = true;
00350 }
00351 }
00352
00353
00354
00355
00356
00357
00358
00359 void Lru::add_cached_page (LruPagePriority priority, LruPage *lru_page)
00360 {
00361 if(lru_page) {
00362 LruMutexHolder(this->_m.mutex);
00363
00364 lru_page->_m.v.in_cache = true;
00365
00366 if(lru_page->_m.size > this->_m.available_memory) {
00367 int memory_required;
00368
00369 memory_required = lru_page->_m.size - this->_m.available_memory;
00370
00371
00372 this->page_out_lru(memory_required);
00373 }
00374
00375 this->_m.available_memory -= lru_page->_m.size;
00376
00377 this->add_page(priority, lru_page);
00378 }
00379 }
00380
00381
00382
00383
00384
00385
00386 void Lru::remove_page (LruPage *lru_page)
00387 {
00388 if(this) {
00389 if(this->_m.total_pages > 0) {
00390 if(lru_page) {
00391 LruMutexHolder(this->_m.mutex);
00392
00393 this->update_start_update_lru_page(lru_page);
00394
00395 if(lru_page->_m.previous) {
00396 lru_page->_m.previous->_m.next = lru_page->_m.next;
00397 if(lru_page->_m.next) {
00398 lru_page->_m.next->_m.previous = lru_page->_m.previous;
00399 }
00400 }
00401 else {
00402 this->_m.lru_page_array[lru_page->_m.priority] =
00403 lru_page->_m.next;
00404 if(lru_page->_m.next) {
00405 lru_page->_m.next->_m.previous = 0;
00406 }
00407 }
00408
00409 lru_page->_m.next = 0;
00410 lru_page->_m.previous = 0;
00411
00412 lru_page->_m.v.in_lru = false;
00413 }
00414 }
00415 else {
00416
00417
00418
00419 }
00420 }
00421 else {
00422
00423
00424
00425 }
00426 }
00427
00428
00429
00430
00431
00432
00433 void Lru::lock_page (LruPage *lru_page)
00434 {
00435 lru_page->_m.v.lock = true;
00436 }
00437
00438
00439
00440
00441
00442
00443 void Lru::unlock_page (LruPage *lru_page)
00444 {
00445 lru_page->_m.v.lock = false;
00446 }
00447
00448
00449
00450
00451
00452
00453
00454
00455 void Lru::access_page (LruPage *lru_page)
00456 {
00457 if(lru_page) {
00458 if(lru_page->_m.current_frame_identifier
00459 == this->_m.current_frame_identifier) {
00460 lru_page->_m.current_frame_usage++;
00461 this->_m.total_page_all_access_size += lru_page->_m.size;
00462 }
00463 else {
00464
00465 lru_page->_m.last_frame_identifier = lru_page->_m.current_frame_identifier;
00466 lru_page->_m.current_frame_identifier = this->_m.current_frame_identifier;
00467 lru_page->_m.last_frame_usage = lru_page->_m.current_frame_usage;
00468 lru_page->_m.current_frame_usage = 1;
00469 lru_page->_m.total_frame_page_faults = 0;
00470
00471 this->_m.total_page_access_size += lru_page->_m.size;
00472 }
00473
00474
00475 if(lru_page->_m.v.in_cache == false) {
00476 bool state;
00477
00478 state = true;
00479
00480 LruMutexHolder(this->_m.mutex);
00481
00482
00483 if(lru_page->_m.size > this->_m.available_memory) {
00484 int memory_required;
00485
00486 memory_required = lru_page->_m.size - this->_m.available_memory;
00487
00488
00489 state = this->page_out_lru(memory_required);
00490 }
00491
00492
00493 if(state) {
00494
00495 if(this->_m.page_in_function_array[lru_page->_m.v.type](lru_page)) {
00496 this->_m.available_memory -= lru_page->_m.size;
00497 lru_page->_m.v.in_cache = true;
00498
00499
00500 this->remove_page(lru_page);
00501 this->add_page(LPP_New, lru_page);
00502
00503 this->_m.total_lifetime_page_ins++;
00504 }
00505 }
00506
00507 lru_page->_m.total_frame_page_faults++;
00508 lru_page->_m.total_page_faults++;
00509 }
00510
00511 lru_page->_m.total_usage++;
00512 lru_page->_m.update_total_usage++;
00513
00514 this->_m.total_page_access++;
00515 }
00516 }
00517
00518
00519
00520
00521
00522
00523 void Lru::set_maximum_frame_bandwidth_utilization
00524 (PN_stdfloat maximum_frame_bandwidth_utilization)
00525 {
00526 this->_m.maximum_frame_bandwidth_utilization =
00527 maximum_frame_bandwidth_utilization;
00528
00529 this->_m.frame_bandwidth_factor = (PN_stdfloat) LPP_TotalPriorities
00530 / this->_m.maximum_frame_bandwidth_utilization;
00531 }
00532
00533
00534
00535
00536
00537
00538 void Lru::begin_frame ( )
00539 {
00540 this->_m.current_frame_identifier++;
00541
00542 this->_m.total_page_ins_last_frame = this->_m.total_page_ins;
00543 this->_m.total_page_outs = this->_m.total_page_outs;
00544
00545 this->_m.total_page_ins = 0;
00546 this->_m.total_page_outs = 0;
00547 }
00548
00549
00550
00551
00552
00553
00554
00555 void Lru::update_page_priorities (void)
00556 {
00557 int index;
00558 LruPage *lru_page;
00559
00560 for(index = 0; index < this->_m.total_lru_page_priority_changes; index++) {
00561 int priority;
00562
00563 lru_page = this->_m.lru_page_priority_change_array[index];
00564
00565 this->remove_page(lru_page);
00566
00567 priority = (( int ) lru_page->_m.priority + lru_page->_m.priority_change);
00568 if(priority < 0) {
00569 priority = 0;
00570 }
00571 if(priority >= LPP_TotalPriorities) {
00572 priority = LPP_TotalPriorities - 1;
00573 }
00574
00575 this->add_page((LruPagePriority) priority, lru_page);
00576 lru_page->_m.priority_change = 0;
00577 }
00578 this->_m.total_lru_page_priority_changes = 0;
00579 }
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594 void Lru::update_lru_page (LruPage *lru_page)
00595 {
00596
00597 #if LRU_UNIT_TEST
00598 if(false) {
00599 char string[256];
00600
00601 sprintf(string, " UPDATE %d\n", lru_page->_m.identifier);
00602 OutputDebugString(string);
00603 }
00604 #endif
00605
00606 if(lru_page->_m.v.lock == false && lru_page->_m.v.in_cache) {
00607 int delta_priority;
00608 int lifetime_frames;
00609
00610 delta_priority = 0;
00611
00612 lifetime_frames = this->_m.current_frame_identifier -
00613 lru_page->_m.first_frame_identifier;
00614 if(lifetime_frames >= 1) {
00615 if(lru_page->_m.update_frame_identifier) {
00616 int target_priority;
00617 int integer_update_frames;
00618 PN_stdfloat update_frames;
00619 PN_stdfloat one_over_update_frames;
00620 PN_stdfloat update_average_frame_utilization;
00621
00622 integer_update_frames = (this->_m.current_frame_identifier -
00623 lru_page->_m.update_frame_identifier);
00624 if(integer_update_frames > 0) {
00625 update_frames = ( PN_stdfloat ) integer_update_frames;
00626 one_over_update_frames = 1.0f / update_frames;
00627
00628 update_average_frame_utilization =
00629 (PN_stdfloat) (lru_page->_m.update_total_usage)* one_over_update_frames;
00630
00631 lru_page->_m.average_frame_utilization =
00632 calculate_exponential_moving_average(
00633 update_average_frame_utilization, this->_m.weight,
00634 lru_page->_m.average_frame_utilization);
00635
00636 target_priority = lru_page->_m.priority;
00637 if(lru_page->_m.average_frame_utilization >= 1.0f) {
00638 int integer_average_frame_utilization;
00639
00640 integer_average_frame_utilization =
00641 (int) ((lru_page->_m.average_frame_utilization - 1.0f) *
00642 (PN_stdfloat) HIGH_PRIORITY_SCALE);
00643 if(integer_average_frame_utilization >= LPP_New) {
00644 integer_average_frame_utilization = LPP_New;
00645 }
00646 integer_average_frame_utilization = LPP_New -
00647 integer_average_frame_utilization;
00648 target_priority = integer_average_frame_utilization;
00649 }
00650 else {
00651 int integer_average_frame_utilization;
00652
00653 integer_average_frame_utilization = (int)
00654 (lru_page->_m.average_frame_utilization *
00655 (PN_stdfloat) LOW_PRIORITY_RANGE);
00656 integer_average_frame_utilization = LOW_PRIORITY_RANGE -
00657 integer_average_frame_utilization;
00658 target_priority = LPP_New + integer_average_frame_utilization;
00659 }
00660
00661 delta_priority = target_priority - lru_page->_m.priority;
00662 lru_page->change_priority(delta_priority);
00663 }
00664 }
00665
00666 lru_page->_m.update_frame_identifier = this->_m.current_frame_identifier;
00667 lru_page->_m.update_total_usage = 0;
00668 }
00669
00670 if(lru_page->_m.priority_change) {
00671 if(this->_m.total_lru_page_priority_changes
00672 < FRAME_MAXIMUM_PRIORITY_CHANGES)
00673 {
00674 this->_m.lru_page_priority_change_array
00675 [this->_m.total_lru_page_priority_changes] = lru_page;
00676 this->_m.total_lru_page_priority_changes++;
00677 }
00678 }
00679 }
00680 }
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690 void Lru::update_lru_page_old (LruPage *lru_page)
00691 {
00692 }
00693
00694
00695
00696
00697
00698
00699
00700
00701 void Lru::update_entire_lru ( )
00702 {
00703 if(this->_m.total_pages > 0) {
00704 int index;
00705 LruPage *lru_page;
00706
00707 LruMutexHolder(this->_m.mutex);
00708
00709 for(index = 0; index < LPP_TotalPriorities; index++) {
00710
00711 LruPage * next_lru_page;
00712
00713 lru_page = this->_m.lru_page_array[index];
00714 while(lru_page) {
00715 next_lru_page = lru_page->_m.next;
00716
00717 this->update_lru_page(lru_page);
00718
00719 lru_page = next_lru_page;
00720 }
00721 }
00722
00723 this->update_page_priorities( );
00724 }
00725 }
00726
00727
00728
00729
00730
00731
00732
00733 void Lru::partial_lru_update (int maximum_updates)
00734 {
00735 int total_page_updates;
00736
00737 if (maximum_updates <= 0) {
00738
00739 maximum_updates = 1;
00740 }
00741
00742 total_page_updates = 0;
00743 if(this->_m.total_pages > 0) {
00744 int index;
00745 int start_priority;
00746 LruPage *lru_page;
00747
00748 LruMutexHolder(this->_m.mutex);
00749
00750 start_priority = this->_m.start_priority_index;
00751
00752 {
00753 for(index = start_priority; index < LPP_TotalPriorities; index++) {
00754
00755 LruPage *next_lru_page;
00756
00757 if(index == start_priority) {
00758 if(this->_m.start_update_lru_page) {
00759 lru_page = this->_m.start_update_lru_page;
00760 }
00761 else {
00762 lru_page = this->_m.lru_page_array[index];
00763 }
00764 }
00765 else {
00766 lru_page = this->_m.lru_page_array[index];
00767 }
00768 while(lru_page) {
00769 next_lru_page = lru_page->_m.next;
00770
00771 this->update_lru_page(lru_page);
00772
00773 total_page_updates++;
00774 if(total_page_updates >= maximum_updates) {
00775 if(next_lru_page) {
00776 this->_m.start_priority_index = index;
00777 this->_m.start_update_lru_page = next_lru_page;
00778 }
00779 else {
00780 if((index + 1) >= LPP_TotalPriorities) {
00781 this->_m.start_priority_index = 0;
00782 }
00783 else {
00784 this->_m.start_priority_index = index + 1;
00785 }
00786
00787 this->_m.start_update_lru_page = 0;
00788 }
00789
00790 break;
00791 }
00792
00793 lru_page = next_lru_page;
00794 }
00795
00796 if(total_page_updates >= maximum_updates) {
00797 break;
00798 }
00799 }
00800 }
00801
00802 if(total_page_updates < maximum_updates) {
00803 for(index = 0; index <= start_priority; index++) {
00804 LruPage *next_lru_page;
00805
00806 lru_page = this->_m.lru_page_array[index];
00807 while(lru_page) {
00808 next_lru_page = lru_page->_m.next;
00809
00810 this->update_lru_page(lru_page);
00811
00812 total_page_updates++;
00813 if(total_page_updates >= maximum_updates) {
00814 if(next_lru_page) {
00815 this->_m.start_priority_index = index;
00816 this->_m.start_update_lru_page = next_lru_page;
00817 }
00818 else {
00819 if((index + 1) >= LPP_TotalPriorities) {
00820 this->_m.start_priority_index = 0;
00821 }
00822 else {
00823 this->_m.start_priority_index = index + 1;
00824 }
00825
00826 this->_m.start_update_lru_page = 0;
00827 }
00828
00829 break;
00830 }
00831
00832 lru_page = next_lru_page;
00833 }
00834
00835 if(total_page_updates >= maximum_updates) {
00836 break;
00837 }
00838 }
00839 }
00840
00841 if(total_page_updates < maximum_updates) {
00842 this->_m.start_priority_index = 0;
00843 this->_m.start_update_lru_page = 0;
00844 }
00845
00846 this->update_page_priorities( );
00847 }
00848 }
00849
00850
00851
00852
00853
00854
00855 void Lru::unlock_all_pages (void)
00856 {
00857 if(this->_m.total_pages > 0) {
00858 int index;
00859
00860 for(index = 0; index < LPP_TotalPriorities; index++) {
00861 LruPage *lru_page;
00862 LruPage *next_lru_page;
00863
00864 lru_page = this->_m.lru_page_array[index];
00865 while(lru_page) {
00866 next_lru_page = lru_page->_m.next;
00867
00868 lru_page->_m.v.lock = false;
00869
00870 lru_page = next_lru_page;
00871 }
00872 }
00873 }
00874 }
00875
00876
00877
00878
00879
00880
00881
00882
00883 bool Lru::page_out_lru (int memory_required)
00884 {
00885 bool state;
00886 int attempts;
00887
00888 state = false;
00889 attempts = 0;
00890 if(this->_m.total_pages > 0) {
00891 LruMutexHolder(this->_m.mutex);
00892
00893 do {
00894 int index;
00895 int minimum_frame_identifier;
00896
00897 minimum_frame_identifier = this->_m.current_frame_identifier - 1;
00898
00899
00900 for(index = LPP_PageOut - 1; index >= 0; index--) {
00901 LruPage *lru_page;
00902 LruPage *next_lru_page;
00903
00904 lru_page = this->_m.lru_page_array[index];
00905 while(lru_page) {
00906 next_lru_page = lru_page->_m.next;
00907
00908 if(attempts == 0 && (lru_page->_m.current_frame_identifier >= minimum_frame_identifier)) {
00909
00910 }
00911 else {
00912 if(lru_page->_m.v.lock == false && lru_page->_m.v.in_cache) {
00913 memory_required -= lru_page->_m.size;
00914 this->_m.available_memory += lru_page->_m.size;
00915 lru_page->_m.v.in_cache = false;
00916
00917
00918 this->_m.page_out_function_array[lru_page->_m.v.type](lru_page);
00919 this->_m.total_lifetime_page_outs++;
00920
00921
00922 this->remove_page(lru_page);
00923 this->add_page(LPP_PageOut, lru_page);
00924
00925 if(memory_required <= 0) {
00926 break;
00927 }
00928 }
00929 }
00930
00931 lru_page = next_lru_page;
00932 }
00933
00934 if(memory_required <= 0) {
00935 break;
00936 }
00937 }
00938
00939 if(memory_required > 0) {
00940 state = false;
00941 }
00942 else {
00943 state = true;
00944 }
00945
00946 attempts++;
00947 } while(state == false && attempts < 2);
00948 }
00949
00950 return state;
00951 }
00952
00953
00954
00955
00956
00957
00958
00959 void Lru::count_priority_level_pages (void)
00960 {
00961 int index;
00962
00963 LruMutexHolder(this->_m.mutex);
00964
00965 for(index = 0; index < LPP_TotalPriorities; index++) {
00966 int total_pages;
00967 LruPage *lru_page;
00968 LruPage *next_lru_page;
00969
00970 total_pages = 0;
00971 lru_page = this->_m.lru_page_array[index];
00972 while(lru_page) {
00973 next_lru_page = lru_page->_m.next;
00974
00975 total_pages++;
00976
00977 lru_page = next_lru_page;
00978 }
00979
00980 this->_m.lru_page_count_array[index] = total_pages;
00981 }
00982 }
00983
00984
00985
00986
00987
00988
00989 void Lru::calculate_lru_statistics (void)
00990 {
00991 LruMutexHolder(this->_m.mutex);
00992
00993 if(this->_m.maximum_page_types > 0) {
00994 int index;
00995
00996 memset(this->_m.page_type_statistics_array, 0,
00997 sizeof (PageTypeStatistics) * this->_m.maximum_page_types);
00998 for(index = 0; index < LPP_TotalPriorities; index++) {
00999 LruPage *lru_page;
01000 LruPage *next_lru_page;
01001 PageTypeStatistics *page_type_statistics;
01002
01003 lru_page = this->_m.lru_page_array[index];
01004 while(lru_page) {
01005 int type;
01006
01007 next_lru_page = lru_page->_m.next;
01008
01009 type = lru_page->_m.v.type;
01010 page_type_statistics = &this->_m.page_type_statistics_array[type];
01011 page_type_statistics->total_pages++;
01012
01013 if(lru_page->_m.v.in_cache) {
01014 page_type_statistics->total_pages_in++;
01015 page_type_statistics->total_memory_in += lru_page->_m.size;
01016 }
01017 else {
01018 page_type_statistics->total_pages_out++;
01019 page_type_statistics->total_memory_out += lru_page->_m.size;
01020 }
01021
01022 lru_page = next_lru_page;
01023 }
01024 }
01025 }
01026 }
01027
01028
01029
01030
01031
01032
01033 PN_stdfloat calculate_exponential_moving_average(PN_stdfloat value,
01034 PN_stdfloat weight, PN_stdfloat average)
01035 {
01036 return ((value - average) * weight) + average;
01037 }
01038
01039
01040
01041
01042
01043
01044 bool default_page_in_function(LruPage *lru_page)
01045 {
01046
01047 #if LRU_UNIT_TEST
01048 char string[256];
01049
01050 sprintf(string, " PAGE IN %d\n", lru_page->_m.identifier);
01051 OutputDebugString(string);
01052 #endif
01053
01054 return true;
01055 }
01056
01057
01058
01059
01060
01061
01062 bool default_page_out_function(LruPage *lru_page)
01063 {
01064
01065 #if LRU_UNIT_TEST
01066 char string[256];
01067
01068 sprintf(string, " PAGE OUT %d\n", lru_page->_m.identifier);
01069 OutputDebugString(string);
01070 #endif
01071
01072 return true;
01073 }
01074
01075 #if LRU_UNIT_TEST
01076
01077
01078
01079
01080
01081
01082 void test_ema(void)
01083 {
01084 int index;
01085 PN_stdfloat usage;
01086 PN_stdfloat weight;
01087 PN_stdfloat average;
01088
01089 weight = 0.2;
01090 average = 1.0f;
01091 for(index = 0; index < 50; index++) {
01092 if(index < 25) {
01093 usage = (PN_stdfloat) (index & 0x01);
01094 }
01095 else {
01096 usage = 0.0f;
01097 }
01098 average =
01099 calculate_exponential_moving_average(usage, weight, average);
01100
01101 char string[256];
01102 sprintf(string, "%d %f\n", index, average);
01103 OutputDebugString(string);
01104 }
01105 }
01106
01107
01108
01109
01110
01111
01112 void test_lru(void)
01113 {
01114 int maximum_memory;
01115 int maximum_pages;
01116 int maximum_page_types;
01117 Lru *lru;
01118
01119 test_ema( );
01120
01121 maximum_memory = 3000000;
01122 maximum_pages = 3;
01123 maximum_page_types = 4;
01124 lru = new Lru (maximum_memory, maximum_pages, maximum_page_types);
01125 if(lru) {
01126 lru->_m.minimum_memory = 1000000;
01127
01128 LruPage *lru_page_0;
01129 LruPage *lru_page_1;
01130 LruPage *lru_page_2;
01131 LruPage *lru_page_3;
01132 LruPage *lru_page_4;
01133 LruPage *lru_page_5;
01134
01135 lru_page_0 = lru->allocate_page(1000000);
01136 if(lru_page_0) {
01137 lru->add_page(LPP_PageOut, lru_page_0);
01138 }
01139
01140 lru_page_1 = lru->allocate_page(1000000);
01141 if(lru_page_1) {
01142 lru->add_page(LPP_PageOut, lru_page_1);
01143 }
01144
01145 lru_page_2 = lru->allocate_page(1000000);
01146 if(lru_page_2) {
01147 lru->add_page(LPP_PageOut, lru_page_2);
01148 }
01149
01150 lru_page_3 = lru->allocate_page(1000000);
01151 if(lru_page_3) {
01152 lru->add_page(LPP_PageOut, lru_page_3);
01153 }
01154
01155 lru_page_4 = lru->allocate_page(1000000);
01156 if(lru_page_4) {
01157 lru->add_page(LPP_PageOut, lru_page_4);
01158 }
01159
01160 lru_page_5 = lru->allocate_page(1000000);
01161 if(lru_page_5) {
01162 lru->add_page(LPP_PageOut, lru_page_5);
01163 }
01164
01165 int index;
01166 int total_frames;
01167
01168 total_frames = 300;
01169 for(index = 0; index < total_frames; index++) {
01170 char string[256];
01171
01172 sprintf(string, "FRAME %d\n", index);
01173 OutputDebugString(string);
01174
01175 lru->begin_frame( );
01176
01177 if(index <= 5) {
01178 lru->access_page(lru_page_0);
01179 }
01180
01181 lru->access_page(lru_page_1);
01182 lru->access_page(lru_page_1);
01183
01184 if(index & 0x01) {
01185 lru->access_page(lru_page_2);
01186 }
01187
01188 if((index % 10) == 0) {
01189 lru->access_page(lru_page_3);
01190 }
01191
01192 if(index >= 100) {
01193 lru->access_page(lru_page_4);
01194 }
01195
01196 if(index >= 200) {
01197 lru->access_page(lru_page_5);
01198 }
01199
01200 if(false) {
01201 lru->update_entire_lru( );
01202 }
01203 else {
01204 int maximum_updates;
01205
01206 maximum_updates = 3;
01207 lru->partial_lru_update(maximum_updates);
01208 }
01209 }
01210
01211 if(!true) {
01212 lru->remove_page(lru_page_2);
01213 lru->free_page(lru_page_2);
01214
01215 lru->remove_page(lru_page_3);
01216 lru->free_page(lru_page_3);
01217
01218 lru->remove_page(lru_page_1);
01219 lru->free_page(lru_page_1);
01220 }
01221
01222 delete lru;
01223 }
01224 }
01225
01226 #endif