Browse Prior Art Database

Home Address Exchange Algorithms

IP.com Disclosure Number: IPCOM000085587D
Original Publication Date: 1976-Apr-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

Dynamic data reorganization algorithms relieve the programmer of part of the burden of choosing a physical data organization. The class of algorithms described dynamically reorganizes data according to usage patterns.

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

Page 1 of 3

Home Address Exchange Algorithms

Dynamic data reorganization algorithms relieve the programmer of part of the burden of choosing a physical data organization. The class of algorithms described dynamically reorganizes data according to usage patterns.

In a storage hierarchy, performance depends not only on the choice of what data is at each level, but also on the grouping of data in the units of transfer between levels and the positioning of these units of transfer on the nonrandom access storage devices. Most commonly the unit of transfer (a block) is equal to the unit of management at the faster level (a page). However, hierarchies with multiple page blocks where the unreferenced pages in the block are replaced more quickly than the referenced may be more efficient. The efficiency of the multiple page block is directly related to the degree to which the pages in the block are referenced together.

In this description, algorithms are presented which dynamically reorganize the blocks by exchanging pages between the blocks. As the blocks normally represent the home address of a page, the algorithms are called home address exchange algorithms.

Reorganization by exchange of home address may be carried out in many ways, but the following guidelines are pertinent in a multiple process environment; 1. In order to reduce data movement, only pages in the faster level of storage or empty pages should be considered for exchange. 2. Pages referenced by several processes should be assigned to one for exchange purposes, for example, to the process which first referenced it during its stay at the faster level. 3. To prevent the mixing of data by concurrent processes referencing mutually exclusive sections of the data base, pages should be exchanged only between blocks referenced by the same process. 4. Consider the set of pages V which, during their current stay in the faster level of storage, are first referenced by a particular process Q. Some of these pages will already be in the faster level of storage, while others will cause faults. A fault causes the entire missing contents of the block which contains the faulted page to be brought into the faster level of storage. Thus a process Q will in general cause the fetching of a set of unreferenced as well as referenced pages. In order to group pages by current usage, the first referenced pages V should be grouped into a small a number of blocks as possible. This goal can be approached by exchanging referenced pages with unreferenced pages brought into the faster storage level by the same process. A set of unreferenced pages selected for exchange, all of which are members of the same block, will be termed a "cluster point".

These guidelines determine a class of home address exchange algorithms which can reorganize data according to multiple process usage patterns. A simple example of the class is presented. 1. The unreferenced pages brought into the faster level by the first fault of a process are...