Data structures and algorithms for managing lock states of addressable element ranges
First Claim
1. Apparatus including a lock manager means for representing possibly overlapping lock ranges of addressed elements, said apparatus includingmeans for creating and maintaining at least one singular description of at least one range of addressable elements representing one or more addressable elements, andmeans responsive to at least requests for locks for controlling said means for creating and maintaining at least one singular description to at least divide overlapping descriptions of ranges of said addressable elements into non-overlapping, singular descriptions of ranges of said addressable elements.
1 Assignment
0 Petitions
Accused Products
Abstract
An efficient algorithm for addressable element range locking in shared resources, such as files and memory, of a multi-tasking or multi-processor data processing system provides a very fast mechanism that can properly handle overlapping requests to lock ranges of data of the data processing system while locking or granting wait status to a requestor for any more of the shared resource than is actually requested. This is accomplished by providing singular descriptions of locked and requested ranges of addressable elements. As further requests are received or locks released on overlapping ranges of addressable elements, these singular descriptions are divided or recombined into other singular descriptions of non-overlapping ranges. Problems of overlapping requests are thus handled by dynamically decomposing requests into non-overlapping segments which are then granted atomically. Fast searching for potential deadlocks is accomplished by placing control information about locked areas into a binary tree structure.
154 Citations
26 Claims
-
1. Apparatus including a lock manager means for representing possibly overlapping lock ranges of addressed elements, said apparatus including
means for creating and maintaining at least one singular description of at least one range of addressable elements representing one or more addressable elements, and means responsive to at least requests for locks for controlling said means for creating and maintaining at least one singular description to at least divide overlapping descriptions of ranges of said addressable elements into non-overlapping, singular descriptions of ranges of said addressable elements.
-
5. Apparatus including
a lock manager means for maintaining a representation of at least one lock state range of addressable elements, means for maintaining said representation of said at least one lock state range as at least one singular description of at least one range of said addressable elements, wherein said means for maintaining said representation as at least one singular description includes means responsive to a lock request for dividing at least one said singular description into at least two singular descriptions of non-overlapping ranges of said addressable elements.
-
9. A method of managing lock states of overlapping ranges of addressable elements including the steps of
creating and maintaining at least one singular description of a range of said addressable elements, said addressable elements corresponding to each aid singular description having a continuous sequence of addresses, representing all of said lock states by one of said singular descriptions, and dividing at least one said singular description into at least two singular descriptions of non-overlapping ranges of said addressable elements.
-
10. A method of managing lock requests for locks on addressable elements of a shared resource including the steps of
granting a lock on a requested range of a shared resource, said lock having a range coextensive with a request for said lock by a user of said shared resource, creating and storing a singular description of at least a portion of said range of said lock, creating a description of said lock and a further request for a lock on a range of said shared resource by another user of said shared resource, including at least one of a) creating and storing a divided description of said lock; - one portion of said divided description of said lock being a singular description of a range of said addressable elements coextensive with a portion of said further request on which a wait is granted,
b) creating and storing a divided description of said further request;
one portion of said divided description of said further request being a singular description of a range of said addressable elements coextensive with a portion of said lock on which a wait is granted, andc) creating and storing, within said singular description of said lock, a wait on a range coextensive with said further request. - View Dependent Claims (11, 12)
- one portion of said divided description of said lock being a singular description of a range of said addressable elements coextensive with a portion of said further request on which a wait is granted,
-
13. A lock manager including
a data structure containing data identifying locks granted and requested for ranges of addressable elements within a shared resource wherein, when both locks and requests for locks are present, the data structure comprises only singular descriptions defining ranges of consecutive addresses of addressable elements which are at least one of fully held and fully requested, and means responsive to a lock request for dividing at least one said singular description into at least two singular descriptions of non-overlapping ranges of said addressable elements.
-
19. A method for locking ranges of addressable elements in shared resources of a multi-tasking or multi-processor data processing system to properly handle overlapping requests to lock ranges of data and files in the data processing system, including the steps of
dynamically decomposing requests into non-overlapping segments having singular descriptions of addressable element ranges and then granting the decomposed requests atomically.
-
20. An apparatus for locking ranges of addressable elements in shared resources of a multi-tasking or multi-processor data processing system to properly handle overlapping requests to lock ranges of data and files in the data processing system, said apparatus including
means for dynamically decomposing requests into non-overlapping segments having singular descriptions of addressable element ranges, and means for then granting the decomposed requests atomically.
-
21. A means for managing a multiplicity of addressable elements, each of said addressable elements having at least two different possible ownership conditions, one of said ownership conditions being an owned condition identifying at least one owner corresponding to said owned condition, wherein a multiplicity of users may share the use of said multiplicity of addressable elements, each said user being able to make a request to obtain said owned condition for one or more ranges of said addressable elements, said means for managing a multiplicity of addressable elements comprising,
means for dynamically partitioning said multiplicity of addressable elements into non-overlapping subranges of said addressable elements, means for creating and maintaining a list of owners of each said subrange of addressable elements, each owner in said owner list having said owned condition with respect to each said addressable element in said subrange, means for creating and maintaining a list of waiters associated with each said subrange of addressable elements, each waiter in said waiter list waiting for release of an owned condition with respect to each said addressable element in at least one subrange, means for linking each owner in any said owner list with the same owner in other owner lists, said linking forming a linked list corresponding to one said request for said owned condition granted to said same owner, means for linking each waiter in any said waiter list with the same waiter in other waiter lists, said linking forming a linked list corresponding to one said request for said owned condition granted to said same waiter, means responsive to a further request by a requestor for an owned condition of at least one range of addressable elements, including addressable elements which are included within at least one said subrange of addressable elements, for further dynamically partitioning at least one said subrange of said multiplicity of addressable elements to separate said addressable elements in said further request included within said at least one subrange of addressable elements from addressable elements in said at least one subrange of said addressable elements which are not included in said further request, if any, said means for further dynamically partitioning said subrange of addressable elements including means for adding said requestor to one of said owner lists and said waiter lists of at least one subrange resulting from at least one of said dynamic partitioning and said further dynamic partitioning of said addressable elements.
Specification