Priority differentiated subtree locking

Abstract

A locking arrangement for data structures is provided that prevents deadlocks, but still allows different threads to simultaneously obtain locks on different nodes of a data structure for both read and write operations. The locking system differentiates locks based on a priority hierarchy. The locking system will fail a request to lock one or more resources in a data structure if access to those resources has already been restricted by a conflicting lock of an equal or higher priority. The locking system may also employ preemptable and non-preemptable locks such that, if a preemptable lock with a lower priority has restricted access to resources, then the locking system will preempt the lower priority lock in favor of a conflicting higher priority lock. Alternately, if a non-preemptable lock with a lower priority has restricted access to resources, then the locking system will wait until the lower priority lock is removed before implementing a requested conflicting higher priority lock. This locking arrangement allows high priority operations that require higher performance and efficiency to receive preferential access to a data structure without preventing lower priority operations from accessing the data structure, while preventing deadlocks between different operations.