DATA STRUCTURES AND ALGORITHMS FOR MANAGING LOCK STATES OF ADDRESSABLE ELEMENT RANGES

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.