memory management and -trees the fifo strategy is quite simple to implementas it only requires queue to store references to the pages in the cache pages are enqueued in when they are referenced by browserand then are brought into the cache when page needs to be evictedthe computer simply performs dequeue operation on to determine which page to evict thusthis policy also requires ( additional work per page replacement alsothe fifo policy incurs no additional overhead for page requests moreoverit tries to take some advantage of temporal locality the lru strategy goes step further than the fifo strategyfor the lru strategy explicitly takes advantage of temporal locality as much as possibleby always evicting the page that was least-recently used from policy point of viewthis is an excellent approachbut it is costly from an implementation point of view that isits way of optimizing temporal and spatial locality is fairly costly implementing the lru strategy requires the use of an adaptable priority queue that supports updating the priority of existing pages if is implemented with sorted sequence based on linked listthen the overhead for each page request and page replacement is ( when we insert page in or update its keythe page is assigned the highest key in and is placed at the end of the listwhich can also be done in ( time even though the lru strategy has constant-time overheadusing the implementation abovethe constant factors involvedin terms of the additional time overhead and the extra space for the priority queue qmake this policy less attractive from practical point of view since these different page replacement policies have different trade-offs between implementation difficulty and the degree to which they seem to take advantage of localitiesit is natural for us to ask for some kind of comparative analysis of these methods to see which oneif anyis the best from worst-case point of viewthe fifo and lru strategies have fairly unattractive competitive behavior for examplesuppose we have cache containing pagesand consider the fifo and lru methods for performing page replacement for program that has loop that repeatedly requests pages in cyclic order both the fifo and lru policies perform badly on such sequence of page requestsbecause they perform page replacement on every page request thusfrom worst-case point of viewthese policies are almost the worst we can imagine--they require page replacement on every page request this worst-case analysis is little too pessimistichoweverfor it focuses on each protocol' behavior for one bad sequence of page requests an ideal analysis would be to compare these methods over all possible page-request sequences of coursethis is impossible to do exhaustivelybut there have been great number of experimental simulations done on page-request sequences derived from real programs based on these experimental comparisonsthe lru strategy has been shown to be usually superior to the fifo strategywhich is usually better than the random strategy