Page 141 - DCAP403_Operating System

Operating System

Notes Least Frequently Used (LFU)

Often confused with LRU, Least Frequently Used (LFU) selects a page for replacement if it
has not been used often in the past. Instead of using a single age as in the case of LRU, LFU
defines a frequency of use associated with each page. This frequency is calculated throughout

the reference stream, and its value can be calculated in a variety of ways. The most common
frequency implementation begins at the beginning of the page reference stream, and continues
to calculate the frequency over an ever-increasing interval. Although this is the most accurate
representation of the actual frequency of use, it does have some serious drawbacks. Primarily,
reactions to locality changes will be extremely slow. Assuming that a program either changes its
set of active pages, or terminates and is replaced by a completely different program, the frequency
count will cause pages in the new locality to be immediately replaced since their frequency is
much less than the pages associated with the previous program. Since the context has changed,
and the pages swapped out will most likely be needed again soon (due to the new program’s
principal of locality), a period of thrashing will likely occur. If the beginning of the reference
stream is used, initialization code of a program can also have a profound influence. The pages

associated with initial code can influence the page replacement policy long after the main body
of the program has begun execution. One way to remedy this is to use a popular variant of LFU,
which uses frequency counts of a page since it was last loaded rather than since the beginning of
the page reference stream. Each time a page is loaded, its frequency counter is reset rather than

being allowed to increase indefinitely throughout the execution of the program. Although this

policy will for the most part prevent “old” pages from having a huge influence in the future of
the stream, it will still tend to respond slowly to locality changes.
7.10.2 Dynamic Page Replacement Algorithms

All of the static page replacement algorithms considered have one thing in common: they
assumed that each program is allocated a fixed amount of memory when it begins execution,

and does not request further memory during its lifetime. Although static algorithms will work
in this scenario, they are hardly optimized to handle the common occurrence of adjusting to
page allocation changes. This can lead to problems when a program rapidly switches between
needing relatively large and relatively small page sets or localities. Depending on the size of
the memory requirements of a program, the number of page faults may increase or decrease
rapidly; for Stack Algorithms, you know that as the memory size is decreased, the numbers
of page faults will increase. Other static algorithms may become completely unpredictable.
Generally speaking, any program can have its number of page faults statistically analyzed for a
variety of memory allocations. At some point the rate of increase of the page faults (derivative
of the curve) will peak; this point is sometimes referred to as the hysteresis point. If the memory
allocated to the program is less than the hysteresis point, the program is likely to thrash its page
replacement. Past the point, there is generally little noticeable change in the fault rate, making the
hysteresis the target page allocation. Since a full analysis is rarely available to a virtual memory
controller, and that program behavior is quite dynamic, finding the optimal page allocation can be

incredibly difficult. A variety of methods must be employed to develop replacement algorithms

that work hand-in-hand with the locality changes present in complex programs. Dynamic paging
algorithms accomplish this by attempting to predict program memory requirements, while
adjusting available pages based on reoccurring trends. This policy of controlling available pages
is also referred to as “prefetch” paging, and is contrary to the idea of demand paging. Although
localities (within the scope of a set of operations) may change, states, it is likely that within the
global locality (encompassing the smaller clusters), locality sets will be repeated.
7.11 Page Allocation Algorithm

How do you allocate the fixed amount of free memory among the various processes? If you have
93 free frames and two processes, how many frames does each process get? The simplest case of

134 LOVELY PROFESSIONAL UNIVERSITY