Browse Prior Art Database

Chained Data Summary Updates

IP.com Disclosure Number: IPCOM000044922D
Original Publication Date: 1983-Jan-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 3 page(s) / 68K

Publishing Venue

IBM

Related People

Striemer, BL: AUTHOR

Abstract

It is quite common to chain data in computer systems. The serialization mechanism in U.S. Patent 4,249,241 maintains hold records (HRs) on a chain. There is a hold record for every hold that has been granted. When a task requests usage of some data, it is necessary to search the hold records to ensure that no hold records already exist that would conflict with the one being requested. The hold records are kept in main storage, and consequently the search is relatively time consuming To eliminate searching the entire hold record area, the hold records are grouped into serial chains according to the addresses of the data that they are locking.

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

Chained Data Summary Updates

It is quite common to chain data in computer systems. The serialization mechanism in U.S. Patent 4,249,241 maintains hold records (HRs) on a chain. There is a hold record for every hold that has been granted. When a task requests usage of some data, it is necessary to search the hold records to ensure that no hold records already exist that would conflict with the one being requested. The hold records are kept in main storage, and consequently the search is relatively time consuming To eliminate searching the entire hold record area, the hold records are grouped into serial chains according to the addresses of the data that they are locking. The chain which might contain the hold record being sought is located by hashing the data address to develop an index into a hash table to obtain a pointer to the beginning of the chain of hold records for that data and its hash synonyms.

The hold records (Fig. 1) contain the address of the data held (bytes 2-7), the type of hold that has been granted (byte 1), the identity of the task (TDE) that owns the hold record (bytes 8-9), flags (byte 0) and a field (bytes 10-11) pointing to the next hold record on the chain. When granting a hold, the hold record chain is searched for possible conflicts. To free a hold, the hold record chain is searched to find a match of the data address, the type of hold and the owning task's identification. The search time of the hold record chains is reduced if the chains are formed as primary chains containing hold records with different data addresses and secondary chains containing hold records with identical data addresses, as in Fig. 2. To further reduce the search time, a summary of all types of holds on the secondary chain is kept in a cumulative hold field at the head of the secondary chain. The cumulative hold field (byte 14) contains the logical OR of all the holds on the secondary chain. This cumulative field is compared with a test field or mask contained in an instruction issued by the task requesting usage of some data. If any bits in the cumulative field and the test field are equal to one, there is a potential conflict.

Although the cumulative hold field speeds the search process, the maintenance of this field can degrade performance. This is because it is not possible to logically un-OR the cumulative value when a hold is freed.

The obvious solution to this problem is to reference each hold record on the secondary chain, starting at the beginning and generate a new cumulative field. This would be time consuming. A more efficient solution is to use the chain field of a hold record on the secondary chain as a backward pointer. Additionally a cumulative hold field is provided in each hold record. The backward pointer and cumulative hold field are easy to create because new hold records are always placed at the head of the secondary chain. When placing a hold record at the head of the secondary chain,...