Browse Prior Art Database

Tag Sorting in a Virtual Memory

IP.com Disclosure Number: IPCOM000079296D
Original Publication Date: 1973-Jun-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 4 page(s) / 18K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

A desirable end to be obtained in carrying out sorting in a paged virtual memory system is to minimize the number of page faults which occur. In some paged virtual memory systems, the sorting algorithm may have to accomplish such minimization without knowledge of the quantity of real storage which is available.

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

Page 1 of 4

Tag Sorting in a Virtual Memory

A desirable end to be obtained in carrying out sorting in a paged virtual memory system is to minimize the number of page faults which occur. In some paged virtual memory systems, the sorting algorithm may have to accomplish such minimization without knowledge of the quantity of real storage which is available.

There are described herein tag sorting algorithms which can advantageously be used when tag sorting is appropriate, i.e., the length of a record is substantially greater than the length of a key.

Although these algorithms have been essentially developed for use in a real-memory system in order to minimize the number of accesses to secondary storage, they are directly applicable to a virtual-memory system wherein the records are stored in a storage device outside of the virtual memory. When the records are stored in the virtual memory, the algorithms still apply, however, the storage areas used will be portions of the virtual memory.

A tag sorting algorithm which has heretofore been developed for use in a real-memory system is one for the sequential recovery of the records of a file, wherein the records are randomly located on a Storage device which comprises a plurality of areas. The algorithm is based upon the principle that the recovery of the records in sequence, order is isomorphic to the distribution of the sequence of records into the specific locations on the storage device. In the algorithm, a directory is employed which contains the tags of the records in sequential order of key value, the tag comprising the record's key value and its address in the storage device. Utilizing the directory, a simulation of the distribution of the tags therein is performed and the result of the simulated distribution is written out in the form of a string of items, which includes portions of the tags grouped therein according to areas and information as to which records and how many are to be written out at respective visits to the storage device. The items in the string are then employed in the reverse order of their writing out, to determine the recovery or retrieval of the records in sequential order of key value.

In one aspect of this algorithm, the record recovery may be performed by scanning the areas of the storage device in a cyclic fashion. In another aspect, the record recovery may be achieved by selectively visiting chosen areas of the storage device, the determination of the selection of the area which may be visited at a particular juncture depending upon predetermined criteria, such as quantity of records that can be written out at a visit, etc. The algorithm can be executed either by a singlepass or multipass operation and is a substantial improvement over other sequential record recovery algorithms, which employ a tag sort and utilize the sorted tags to perform an ordered record retrieval by conventional methods. In another aspect of this algorithm, ordered substrings of the file are fo...