Panda3D
 All Classes Functions Variables Enumerations
lru.h
00001 // Filename: lru.h
00002 // Created by: aignacio (12Dec05)
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 #ifndef LRU_H
00016 #define LRU_H
00017 
00018 #define ENABLE_MUTEX 1
00019 
00020 #if ENABLE_MUTEX
00021 #include "lightMutex.h"
00022 #include "lightMutexHolder.h"
00023 #define LruMutexHolder(mutex) MutexHolder(mutex)
00024 #else
00025 #define LruMutexHolder(mutex)
00026 #endif
00027 
00028 
00029 static const int MAXIMUM_LRU_PAGE_TYPES = 8;
00030 static const int FRAME_MAXIMUM_PRIORITY_CHANGES = 256;
00031 
00032 
00033 class Lru;
00034 class LruPage;
00035 
00036 enum LruPagePriority
00037 {
00038   LPP_Highest = 0,
00039   LPP_High = 10,
00040   LPP_New = 20,
00041   LPP_Normal = 25,
00042   LPP_Intermediate = 30,
00043   LPP_Low = 40,
00044   LPP_TotalPriorities = 50,
00045 
00046   LPP_PageOut = LPP_TotalPriorities - 1
00047 };
00048 
00049 typedef union _LruPageType
00050 {
00051   void *pointer;
00052 
00053 }
00054 LruPageType;
00055 
00056 typedef struct
00057 {
00058   int total_pages;
00059   int total_pages_in;
00060   int total_pages_out;
00061   int total_memory_in;
00062   int total_memory_out;
00063 }
00064 PageTypeStatistics;
00065 
00066 typedef bool (*LruPageTypeFunction) (LruPage *lru_page);
00067 
00068 class EXPCL_PANDA_DISPLAY LruPage
00069 {
00070 
00071 protected:
00072 
00073   LruPage ( );
00074   ~LruPage ( );
00075   void change_priority (int delta);
00076 
00077 public:
00078 
00079   typedef struct _LruPageVariables
00080   {
00081     LruPageType lru_page_type;  // pointer to memory type
00082 
00083     int size;
00084     LruPagePriority priority;
00085     int priority_change;
00086 
00087     struct
00088     {
00089       unsigned int type : 8;
00090       unsigned int lock : 1;
00091       unsigned int in_cache : 1;
00092       unsigned int in_memory : 1;
00093       unsigned int on_disk : 1;
00094       unsigned int pre_allocated : 1;
00095       unsigned int allocated : 1;
00096       unsigned int in_lru : 1;
00097     } v;
00098 
00099     int first_frame_identifier;   // creation time
00100     int last_frame_identifier;    // previous time page was used
00101     int current_frame_identifier;
00102     int update_frame_identifier;
00103 
00104     int current_frame_usage;
00105     int last_frame_usage;
00106 
00107     int total_frame_page_faults;
00108     int total_page_faults;
00109 
00110     int total_usage;
00111     int update_total_usage;
00112 
00113     int identifier;
00114 
00115     PN_stdfloat average_frame_utilization;
00116 
00117     LruPage *previous;
00118     LruPage *next;
00119     Lru *lru;
00120     
00121     string name;
00122   }
00123   LruPageVariables;
00124 
00125   LruPageVariables _m;
00126 
00127   friend class Lru;
00128 };
00129 
00130 ////////////////////////////////////////////////////////////////////
00131 //       Class : Lru
00132 // Description : Least Recently Used algorithm implementation:
00133 // In the Lru, each "memory page" has an associated class LruPage.
00134 // The Lru has a range of priorities from LPP_Highest to
00135 // LPP_PagedOut. Each priority has a doubly linked list of LruPages.
00136 // The algorithim uses an adaptive method based on the average
00137 // utilization of each page per frame (or time slice). The
00138 // average utilization is calculated with an exponetial moving
00139 // average. This is superior to a standard average since a standard
00140 // average becomes less and less adaptive the longer a page exists.
00141 // The average utilization is used to set the priority of each page.
00142 // A higher average utilization automatically raises the priority
00143 // of a page and a lower average utilization automatically lowers
00144 // the priority of a page. Therefore, pages with a higher average
00145 // utilization have a higher chance of being kept in memory or
00146 // cached and pages with a lower average utilization have a higher
00147 // chance of being paged out.  When a page is paged in and there
00148 // is not enough memory available, then the lowest priority pages
00149 // will be paged out first until there is enough memory available.
00150 ////////////////////////////////////////////////////////////////////
00151 class EXPCL_PANDA_DISPLAY Lru
00152 {
00153 public:
00154 
00155   Lru (int maximum_memory, int maximum_pages, int maximum_page_types);
00156   ~Lru ( );
00157 
00158   bool register_lru_page_type (int index, LruPageTypeFunction page_in_function, LruPageTypeFunction page_out_function);
00159 
00160   LruPage *allocate_page (int size);
00161   void update_start_update_lru_page (LruPage *lru_page);
00162 
00163   void free_page (LruPage *lru_page);
00164 
00165   void add_page (LruPagePriority priority, LruPage *lru_page);
00166   void add_cached_page (LruPagePriority priority, LruPage *lru_page);
00167   void remove_page (LruPage *lru_page);
00168 
00169   void lock_page (LruPage *lru_page);
00170   void unlock_page (LruPage *lru_page);
00171 
00172   void access_page (LruPage *lru_page);
00173 
00174   void set_maximum_frame_bandwidth_utilization (PN_stdfloat maximum_frame_bandwidth_utilization);
00175 
00176   void begin_frame ( );
00177 
00178   void update_entire_lru ( );
00179   void partial_lru_update (int maximum_updates);
00180 
00181   // set maximum number of page updates per frame
00182   // pause/resume updates/current_frame_identifier
00183 
00184   void unlock_all_pages (void);
00185 
00186   void count_priority_level_pages (void);
00187 
00188   void calculate_lru_statistics (void);
00189 
00190   bool page_out_lru (int memory_required);
00191 
00192 private:
00193   void update_page_priorities (void);
00194   void update_lru_page (LruPage *lru_page);
00195   void update_lru_page_old (LruPage *lru_page);
00196 
00197 public:
00198   typedef struct _LruVariables
00199   {
00200     // LruPagePriority lists
00201     LruPage *lru_page_array [LPP_TotalPriorities];
00202 
00203     int total_pages;
00204     int available_memory;
00205     int current_frame_identifier;
00206 
00207     int maximum_memory;
00208     int minimum_memory; // target amount of memory to keep free if possible
00209     int maximum_page_types;
00210 
00211     int total_lifetime_page_ins;
00212     int total_lifetime_page_outs;
00213 
00214     int total_page_ins_last_frame;
00215     int total_page_outs_last_frame;
00216 
00217     int total_page_ins;
00218     int total_page_outs;
00219 
00220     int total_page_access;
00221     double total_page_access_size;
00222     double total_page_all_access_size;
00223 
00224     int start_priority_index;
00225     LruPage *start_update_lru_page;
00226 
00227     int identifier; // the number of pages created during the lifetime of the LRU
00228 
00229     PN_stdfloat weight; // used for exponential moving average
00230     PN_stdfloat maximum_frame_bandwidth_utilization;
00231 
00232     PN_stdfloat frame_bandwidth_factor;
00233 
00234     LruPageTypeFunction page_in_function_array [MAXIMUM_LRU_PAGE_TYPES];
00235     LruPageTypeFunction page_out_function_array [MAXIMUM_LRU_PAGE_TYPES];
00236 
00237     int total_lru_page_priority_changes;
00238     LruPage *lru_page_priority_change_array [FRAME_MAXIMUM_PRIORITY_CHANGES];
00239 
00240     int maximum_pages;
00241     int total_lru_pages_in_pool;
00242     int total_lru_pages_in_free_pool;
00243     LruPage **lru_page_pool;
00244     LruPage **lru_page_free_pool;
00245 
00246     int lru_page_count_array [LPP_TotalPriorities];
00247     PageTypeStatistics *page_type_statistics_array;
00248 
00249     void *context;  // user specified data
00250 
00251 #if ENABLE_MUTEX
00252     Mutex *mutex;
00253 #endif
00254   }
00255   LruVariables;
00256 
00257   LruVariables _m;
00258 
00259   friend class LruPage;
00260 };
00261 
00262 PN_stdfloat calculate_exponential_moving_average (PN_stdfloat value, PN_stdfloat weight, PN_stdfloat average);
00263 bool default_page_in_function (LruPage *lru_page);
00264 bool default_page_out_function (LruPage *lru_page);
00265 
00266 void test_ema (void);
00267 void test_lru (void);
00268 
00269 #endif
 All Classes Functions Variables Enumerations