Object lock management system with improved local lock management and global deadlock detection in a parallel data processing system

A method for lock management in a parallel data processing system having a plurality of computing nodes, a plurality of processing activities that are active on selectable ones of the computing nodes, and a plurality of selectable objects to lock, wherein a local lock control element is available on each of the plurality of computing nodes for coordinating locking of objects that are local to the respective computing nodes, a global deadlock detector is established on a predetermined one of the computing nodes, and a deadlock preprocessor is established on each of the computing nodes, the method comprising the steps of:

• submitting object lock requests from the processing activities to the local lock control elements, wherein each object lock requests indicates an object to lock;
• granting a lock for an object if there is not a lock conflict for said object, whereby a respective processing activity is identified as a lock owner for said object;
• enqueuing an object lock request if there is a lock conflict, whereby a respective processing activity is identified as a queued lock-requester for said object;
• performing steps (i) and (ii) by each of the deadlock preprocessors:
• (i) identifying timed-out requests, wherein said timed-out requests are object lock requests that have been queued for longer than a predetermined period of time;
• (ii) reporting to the global deadlock detector queued lock-requesters of said timed-out requests and respective lock owners for objects of said timed-out requests;
• detecting deadlocked queued lock-requesters at the global deadlock detector;
• and
• instructing said local lock control elements to release locks held by said deadlocked queued lock-requesters and to release timed-out requests of said deadlocked queued lock-requesters.

A method for lock management in a parallel data processing system having a plurality of computing nodes, a plurality of processing activities active on selectable ones of the computing nodes, and a plurality of selectable objects to lock, wherein a local lock control element is available on each of the plurality of computing nodes for coordinating locking of objects that are local to the respective computing nodes, a global deadlock detector is established on a predetermined one of the computing nodes, and a deadlock preprocessor is established on each of the computing nodes, the method comprising the steps of:

• submitting object lock requests from the processing activities to the local lock control elements, wherein each object lock request indicates an object to lock;
• granting a lock for an object in response to an object lock request if there is not a lock conflict for said object, whereby a respective processing activity is identified as a lock owner for said object, and wherein said granting step comprises the step of
• linking a lock structure to a lock-list having other lock structures for said object;
• enqueuing an object lock request if there is a lock conflict for an object specified in said object lock request, whereby a respective processing activity is identified as a queued lock-requester for said object, and wherein said enqueuing step comprises the steps of (a) and (b);
• (a) linking a request structure for said object lock request to a queue-list of other request structures;
• and
• (b) linking said request structure to a corresponding lock-list of said object;
• performing steps (c) through (e) by each of the deadlock preprocessors;
• (c) scanning said queue-list for timed-out requests, wherein a timed-out request is a request structure that has been queued for longer than a predetermined period of time;
• (d) assembling a requester-owner pair for each lock-requester of said timed-out requests in combination with lock owners of objects of said timed-out requests;
• (e) reporting said requester-owner pairs to the global deadlock detector;
• detecting deadlocked queued lock-requesters at the global deadlock detector from said requester-owner pairs;
• and
• instructing said local lock control elements to release locks held by said deadlocked queued lock-requesters and to release timed-out requests of said deadlocked queued lock requesters.

An apparatus for lock management in a parallel data processing system having a plurality of computing nodes, a plurality of processing activities active on selectable ones of the computing nodes, and a plurality of selectable objects to lock, wherein a local lock control element is available on each of the plurality of computing nodes for coordinating locking of objects that are local to the respective computing nodes, a global deadlock detector is established on a predetermined one of the computing nodes, the apparatus comprising:

• lock-grant means within the lock control elements for granting a lock for an object in response to an object lock request if there is not a lock conflict and for identifying a respective processing activity as a lock owner for said object;
• enqueue means within the lock control elements for enqueuing said object lock request if there is a lock conflict and for identifying a respective processing activity as a queued lock-requester for said object;
• identification means coupled to said enqueue means for identifying timed-out requests, wherein said turned-out requests are object lock requests that have been queued for longer than a predetermined period of time;
• and
• report means coupled to said identification means for reporting to the global deadlock detector queued lock-requesters of said timed-out requests and respective lock owners for objects of said timed-out requests;
• detection means within the global deadlock detector for detecting deadlocked queued lock-requesters;
• and
• instruction means coupled to said detection means for instructing the local lock control elements to release locks held by said deadlocked queued lock-requesters and to release timed-out requests of said deadlocked queued lock-requesters.

The apparatus of claim I 1, wherein

• said identification means includes means for periodically identifying said timed-out requests;
• said report means includes means for periodically reporting to the global deadlock detector queued lock-requesters of said timed-out requests and respective lock owners for objects of said timed-out requests;
• and
• said detection means includes means for periodically detecting said deadlocked queued lock-requesters.

A parallel database deadlock detection system, comprising:

• a mesh network;
• a plurality of compute nodes coupled to said mesh network;
• a plurality of database servers, predetermined ones of which are active on predetermined ones of said plurality of compute nodes;
• a plurality of database clients, predetermined ones of which are active on predetermined ones of said plurality of compute nodes, wherein each of said plurality of database clients is coupled to each of said plurality of database servers;
• a plurality of local lock control elements, wherein each of said plurality of database servers has an associated lock control element and each of said plurality of local lock control elements processes lock requests from each of said plurality of database clients, wherein each of said lock control element comprises
• lock-grant means for granting a lock for an object in response to a lock request if there is not a lock conflict and for identifying a respective database client as a lock owner for said object;
• and
• enqueue means for enqueuing said lock request if there is a lock conflict and for identifying a respective database client as a queued lock-requester for said object;
• a plurality of deadlock preprocessors, wherein each of said plurality of database servers has an associated deadlock preprocessor;
• and
• a deadlock detector coupled to each of said plurality of deadlock preprocessors, wherein each of said deadlock preprocessors reports queued lock-requesters and respective lock owners for objects of queued lock requests to said deadlock detector, and said deadlock detector checks for deadlocked queued lock-requesters and instructs said local lock control elements to release locks held by said deadlocked queued lock-requesters and to release queued lock requests of said deadlocked queued lock-requesters.