Browse Prior Art Database

Modified LRU Page Replacement Algorithm

IP.com Disclosure Number: IPCOM000051431D
Original Publication Date: 1981-Jan-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Bach, SE: AUTHOR [+3]

Abstract

A page replacement algorithm is generally required for a virtual storag multi-programming computer system. The page replacement algorithm may operate as a strict least recently used (LRU) replacement algorithm or as a modified LRU algorithm. The operation of the modified LRU algorithm is dependent upon specified parameters which control the amount of real storage allocated to one or more program applications. The amount of real storage allocated to an application may be controlled within minimum and maximum amounts or the amount of real storage may be controlled so that the number of page faults incurred by the application during a given interval of execution time will be within prescribed bounds.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Modified LRU Page Replacement Algorithm

A page replacement algorithm is generally required for a virtual storag multi- programming computer system. The page replacement algorithm may operate as a strict least recently used (LRU) replacement algorithm or as a modified LRU algorithm. The operation of the modified LRU algorithm is dependent upon specified parameters which control the amount of real storage allocated to one or more program applications. The amount of real storage allocated to an application may be controlled within minimum and maximum amounts or the amount of real storage may be controlled so that the number of page faults incurred by the application during a given interval of execution time will be within prescribed bounds.

Real storage is allocated to applications in page size units called page frames. With a strict LRU algorithm, the number of frames allocated to any one application depends on its page reference activity as well as the page reference activity of all other applications sharing the fixed amount of real storage available. Therefore, the number of page faults that occur for the application to perform some unit of work can vary considerably from one execution interval to another. The modified LRU algorithm can be used to reduce the number of page faults and the variability in the number of page faults incurred to perform the work unit. If the application is performing the work units on behalf of terminal operators, the control over the page fault rate can result in improved and more consistent response times for the terminal users.

The parameters can be used by the system manager to affect the amount of real storage allocated to an application. The system manager can specify that an application should always have a minimum amount of real storage available to back its virtual pages, regardless of the interval of time that the pages are unreferenced. Although the basic page replacement algorithm is still LRU, the frames holding the application's pages will not be candidates for stealing unless the application has more than the specified minimum amount of real storage. If the application has more real storage than the minimum specified, its frames are candidates for stealing within the LRU concept. That is, any frames stolen must be unreferenced for at least as long as any other candidate frames in the system. Stealing a frame must not reduce the amount of storage owned by the application to less than a minimum, unless there are no other steal candidates.

The system manager can also specify a maximum amount of real storage that an application can have allocated. This can be used to protect all other applications from page replacement when an application is active that can reference a great number of pages with high frequency. Such an application can acquire a great deal of real storage, since its pages tend not to be candidates for stealing by the LRU algorithm as long as other applications do not referenc...