Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Least Likely to be Serviced Page Replacement Algorithm

IP.com Disclosure Number: IPCOM000084733D
Original Publication Date: 1975-Dec-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Anderson, HA: AUTHOR

Abstract

The present memory manager mechanism utilizes the scheduling and dispatching priorities of processes when it is necessary to select the pages that should be replaced from main memory. It has as its intent, the establishment of a single resource management policy for controlling the order in which processes are scheduled for service and page frames allocated or deallocated.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Least Likely to be Serviced Page Replacement Algorithm

The present memory manager mechanism utilizes the scheduling and dispatching priorities of processes when it is necessary to select the pages that should be replaced from main memory. It has as its intent, the establishment of a single resource management policy for controlling the order in which processes are scheduled for service and page frames allocated or deallocated.

In existing virtual memory systems, the scheduling/dispatching mechanism is autonomous of the memory manager mechanism. The primary information shared between them is a system variable that estimates the number of available page frames. This variable is used to control both the level of multiprogramming and the replacement of page frames. This is not a satisfactory situation, because the known approaches to performance tuning exploit the use of the scheduling/dispatching mechanism. In order to coordinate the memory manager with the scheduler/dispatcher, information on the priority of active processes needs to be used as a basis for decisions by both of them.

The scheduler/dispatcher treats processes as being queued in one of three queues (Fig. 1), i.e., a queue is implemented as a list of processes. Inactive processes are queued in the inactive queue. Active processes awaiting to be allocated main memory are queued in the eligible queue (ready queue). Whenever a process is enqueued in the eligible queue a priority is computed for it. Eligible processes are ordered by their priority.

In scheduling, a search is made of the list of eligible processes to find the next process to be allowed to occupy the available main memory. The first one that satisfies the search criterion is the one enqueued in the dispatchable queue. Active processes that have been allocated main memory and are sharing the processor(s) are enqueued in the dispatchable queue. Dispatchable processes are ordered by their priority. The dispatching priority may be the same priority as the eligible priority or is recomputed by the dispatcher.

In dispatching, a search is made of the list of dispatchable processes to find the next process to be assigned to an available processor. Usually the first dispatchable process is the one assigned. The dispatchable and eligible process lists can be merged into a single list of active processes. All that is required is that dispatchable processes be assigned higher priorities than eligible processes, and that pointers exist that delimit the extent of the dispatchable...