Browse Prior Art Database

Working-Set Coprocessor

IP.com Disclosure Number: IPCOM000036171D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Milenkovic, M: AUTHOR

Abstract

Disclosed are the essential principles of the design of a working-set coprocessor that can track the exact working set of a process in real time. The proposed approach has practically negligible effect on the operation of the processor that it is attached to, and its cost of implementation is reasonable.

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

Page 1 of 2

Working-Set Coprocessor

Disclosed are the essential principles of the design of a working-set coprocessor that can track the exact working set of a process in real time. The proposed approach has practically negligible effect on the operation of the processor that it is attached to, and its cost of implementation is reasonable.

The working-set theory defines the working set of a process as a set of distinct pages referenced during the last r memory references, where r is a parameter. The working-set page replacement and allocation policy is believed to yield near optimal space-time product and to have other attractive properties when used to manage virtual memory 1.

However, due to apparent difficulty and excessive overhead, there are no known practical implementations of the exact working-set policy as defined above. Its common software approximations often sacrifice accuracy to control overhead and suffer from anomalous behavior.

This article describes a practical hardware-assisted implementation of the exact working set in real time.

The working-set coprocessor (WSC) attaches to the page-level address lines of the primary processor whose page-referencing behavior the WSC is to monitor. The primary functions of the WSC are to: (1) maintain the list of pages referenced by a process

during its last r memory references (the working

set), where r is a programmable parameter, and

(2) track the page references made by the associated

primary processor while executing the process in

question.

Working Set Maintenance and Time Keeping: The WSC must maintain the time since the last reference for every page in the working set of a process in order to eject pages that remain unreferenced for more than r consecutive page references. In principle, this entire list must be updated following each memory (and page) reference made by the associated process.

The apparent O(n) complexity of this operation may be reduced to O(1) per page reference by applying one of the algorithms devised for timer processing in operating systems. One such algorithm is described in 2, pp 422-429. The algorithm works by arranging the entries into a linked list sorted by delays relative and additive to the previous entries. In this scheme, only the relative time of the first entry needs to be updated for each time tick (page reference).

Page-Reference Tracking: Internally, the WSC consists of registers that hold the most recent page references made by the associated primary processor, and of memory that stores the working set of the running process.

References to the most recently referenced pages are recorded in the WSC's register array. The register array should contain at least three registers - one

1

Page 2 of 2

each to record the last page reference to code, data, and stack issued by the running process. Whenever a page reference is made, the WSC determines whether that reference is recorded in its register array or not. Repeated references to pages already rec...