Page 192 - DCAP103_Principle of operating system

Unit 5: Memory Management

5.11.1 Counters Notes

In the simplest case, we associate with each page-table entry a time-of-use field, and add to the
CPU a logical clock or counter. The clock is incremented for every memory reference. Whenever
a reference to a page is made, the contents of the clock register are copied to the time-of-use
field in the page-table entry for that page. In this way, we always have the “time” of the
last reference to each page. We replace the page with the smallest time value. This scheme
requires a search of the page table to find the LRU page, and a write to memory (to the
time-of-use field in the page table) for each memory access. The times must also be
maintained when page tables are changed (due to CPU scheduling). Overflow of the
clock must be considered.
5.11.2 Stack

Another approach to implementing LRU replacement is to keep a stack of page numbers.
Whenever a page is referenced, it is removed from the stack and put on the top. In this
way, the top of the stack is always the most recently used page and the bottom is the LRU
page (figure). Because entries must be removed from the middle of the stack, it is best
implemented by a doubly linked list, with a head and tail pointer. Removing a page and
putting it on the top of the stack then requires changing six pointers at worst. Each update
is a little more expensive, but there is no search for a replacement; the tail pointer points to
the bottom of the stack, which is the LRU page. This approach is particularly appropriate
for software or microcode implementations of LRU replacement.
Neither optimal replacement nor LRU replacement suffers from Belady’s anomaly. There
is a class of page-replacement algorithms, called stack algorithms, that can never exhibit
Belady’s anomaly. A stack algorithm is an algorithm for which it can be shown that the
set of pages in memory for n frames is always a subset of the set of pages that would be
in memory with n + 1 frames. For LRU replacement, the set of pages in memory would be
the n most recently referenced pages. If the number of frames is increased, these n pages
will still be the most recently referenced and so will still be in memory. Note that neither
implementation of LRU would be conceivable without hardware assistance beyond the
standard TLB registers. The updating of the clock fields or stack must be done for every
memory reference. If we were to use an interrupt for every reference, to allow software to
update such data structures, it would slow every memory reference by a factor of at least ten,
hence slowing every user process by a factor of ten. Few systems could tolerate that level of
overhead for memory management.

How to use stack in memory give steps?

5.11.3 LRU Approximation Page Replacement
Few computer systems provide sufficient hardware support for true LRU page replacement.
Some systems provide no hardware support, and other page-replacement algorithms (such
as a FIFO algorithm) must be used. Many systems provide some help, however, in the form
of a reference bit. The reference bit for a page is set, by the hardware, whenever that page is
referenced (either a read or a write to any byte in the page). Reference bits are associated with
each entry in the page table. Initially, all bits are cleared (to 0) by the operating system. As a
user process executes, the bit associated with each page referenced is set (to 1) by the hardware.
After some time, we can determine which pages have been used and which have not been used
by examining the reference bits. We do not know the order of use, but we know which pages
were used and which were not used. This partial ordering information leads to many page-
replacement algorithms that approximate LRU replacement.

LOVELY PROFESSIONAL UNIVERSITY 185