Browse Prior Art Database

AUTOMATED CONTROL OF CONCU RRENCY IN MULTI-USER HIERARCHICAL INFORMATION' SYSTEMS

IP.com Disclosure Number: IPCOM000128003D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 12 page(s) / 34K

Publishing Venue

Software Patent Institute

Related People

Alan F. Sweet: AUTHOR [+4]

Abstract

In this paper, we present a systematic approach to providing a high degree of concurrent access to information structures in a hierarchical information system. The technique may be applied to existing systems which operate on tree-structured information and which appears as levels of functionally decomposed procedures. It may also be applied to the successive levels of procedures and information tree refinements during the top-down .design process of.. information systems. The basic approach is to analyze concurrent processes, at a given level,. for interference and to automatically place requests for access capabilities to structures at: those points where the structures are first referenced. Releases are automatically placed after those points where the structures are last referenced., As a nevi level of procedures are specified and the information trees are refined, the analysis is repeated resulting in the introduction of new controls and possible movement of old ones. Since the infor-mation is tree-structured, the access to a substructure may, in certain cases, result in the release of the access capabilities. to the predecessor node in the tree, thereby clearing the way for concur-rent access to substructures at the same level in different branches of the tree.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AUTOMATED CONTROL OF CONCU RRENCY IN MULTI-USER HIERARCHICAL INFORMATION' SYSTEMS*

by

Alan F. Sweet and Arthur E. Oldehoeft

Technical Report #77-3 March 1977 *This work was supported in part by the National Science Foundation under Grant No., MCS72-03642 A04 and by the Sciences and Humanities Research Institute of Iowa State University. It also appears as Cyclone Laboratory Technical Report ISU-CL-7702.

I. Introduction

In this paper, we present a systematic approach to providing a high degree of concurrent access to information structures in a hierarchical information system. The technique may be applied to existing systems which operate on tree-structured information and which appears as levels of functionally decomposed procedures. It may also be applied to the successive levels of procedures and information tree refinements during the top-down .design process of.. information systems. The basic approach is to analyze concurrent processes, at a given level,. for interference and to automatically place requests for access capabilities to structures at: those points where the structures are first referenced. Releases are automatically placed after those points where the structures are last referenced., As a nevi level of procedures are specified and the information trees are refined, the analysis is repeated resulting in the introduction of new controls and possible movement of old ones. Since the infor-mation is tree- structured, the access to a substructure may, in certain cases, result in the release of the access capabilities. to the predecessor node in the tree, thereby clearing the way for concur- rent access to substructures at the same level in different branches of the tree.

Numerous systems have been proposed and implemented using the concept of a hierarchical structure [1,5,8,91. Our worlc,.however, is restricted to subsystems (file systems, data base systems, etc.) dedicated to a single language which might typically run as a module in a host operating system. These systems manage their own resources and control the flow of information to the users.

The complicating factor, and the major focus of this paper, is the assumption of a multi-user environment in which each user interacts with the system sharing, and possibly modifying, infor- mation. It is now critically important that our design process satisfy two additional constraints;

1) the introduction of potential concurrency wherever possible, and 2) the guarantee that the system will be correct with respect to three problems of concurrency a) preservation of information .integrity among inter-fering independent processes. b) deadlock avoidance, and c) determinacy within a single process These two requirements place significant analytic burdens on the designer of such a system. Later, we will present an algorithm which can relieve the designer of these burdens. We first, however, more rigorously define...