Priority queue for exclusive locks

• US 10,409,800 B2
• Filed: 08/03/2015
• Issued: 09/10/2019
• Est. Priority Date: 08/03/2015
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Schaub, Thomas
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US14/816,588
• Publication Number:
  US 20170039234A1
• Time in Patent Office: 1,499 Days
• Field of Search: 707704
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details

Abstract

A system includes reception of a first request for a lock on a lock object, storage of a first entry associated with the first request and the lock object in a queue, determination of a first queue position associated with the first entry based on a first priority level of the first request and on a priority level of each of a plurality of entries in the queue associated with the lock object, determination of whether a predetermined expiration time associated with the first request has expired, and, if it is determined that the predetermined expiration time has expired, deletion of the first entry from the queue.

Claims

1. A system comprising:

a memory configured to implement a queue for managing application access to data objects in a database; and

a processor configured to;

receive a plurality of lock requests arising from a plurality of applications, respectively, for exclusively accessing a target data object stored in the database;

determine queue positions for the plurality of lock requests based on respective priority levels of the plurality of lock requests and timing of the plurality of lock requests; and

store the plurality of lock requests as queue entries at the determined queue positions in the queue,

wherein the processor is further configured to determine that a queued lock request has expired based on a predetermined expiration time, modify the queue via deletion of the queued lock request from within the queue, and transmit an error notification to an application associated with the deleted lock request indicating that access to the target data object failed.

2. A system according to claim 1, wherein the processor is configured to:

determine a first number of the queue entries which are associated with the target data object and either are associated with a priority level equal to or greater than a first priority level or associated with a queue position of 0 and any priority level;

determine a highest queue position of the first number of queue entries;

determine a maximum number of (the highest queue position+1) and the first number; and

determination a queue position associated with a first queue entry as equal to the maximum number.

3. A system according to claim 1, wherein the processor is configured to:

determine a second number of queue entries which are associated with the target data object, are associated with a priority level equal to or greater than a first priority level and a queue position of less than a first queue position, or are associated with a queue position of 0 and any priority level;

determine a highest queue position of the second number of queue entries;

determine a second maximum number of (the highest queue position+1) and the second number;

determine whether the second maximum number is less than the first queue position and none of the second number of queue entries is associated with a priority level greater than the first priority level and a queue position equal to the first queue position; and

if it is determined that the second maximum number is less than the first queue position and none of the second number of the plurality of entries is associated with a priority level greater than the first priority level and a queue position equal to the first queue position, determine the first queue position associated with a first queue entry as equal to the second maximum number.

4. A system according to claim 1, wherein the processor is further configured to:

receive a second request for a lock on the target data object, the second request associated with a long-term lock;

store a second entry associated with the second request and the target data object in the queue;

determine that a queue position of the second request is 0;

set a lock based on the second request based on the determination that a queue position of the second request is 0; and

in response to setting of the lock, delete the second entry.

5. A system according to claim 4, wherein the processor is further configured to:

receive a third request for a lock on the target data object;

store a third entry associated with the third request and the target data object in the queue;

determine that a queue position of the third request is 0;

receive a request to set the lock based on the third request and based on the determination that a queue position of the third request is 0;

in response to the request to set the lock based on the third request, determine that the second long term lock of the second request is still being held and provide an error message and delete the third entry.

6. The system of claim 1, wherein the processor is configured to call an enqueue operation which deletes the expired lock request from the queue.

7. A method comprising:

receiving a plurality of lock requests arising from a plurality of applications, respectively, for exclusively accessing a target data object stored in a database;

determining queue positions for the plurality of lock requests based on respective priority levels of the plurality of lock requests and timing of the plurality of lock requests; and

storing the plurality of lock requests as queue entries at the determined queue positions in the queue,

wherein the method further comprises determining that a queued lock request has expired based on a predetermined expiration time, modifying the queue via deletion of the queued lock request from within the queue, and transmitting an error notification to an application associated with the deleted lock request indicating that access to the target data object failed.

8. A method according to claim 7, wherein the determining comprises:

determining a first number of queue entries which are associated with the target data object and either are associated with a priority level equal to or greater than a first priority level or are associated with a queue position of 0 and any priority level;

determining a highest queue position of the first number of queue entries;

determining a maximum number of (the highest queue position+1) and the first number; and

determining a queue position associated with a first queue entry as equal to the maximum number.

9. A method according to claim 7, wherein the determining comprises:

determining a second number of queue entries which are associated with the target data object, are associated with a priority level equal to or greater than a first priority level and with a queue position of less than a first queue position, or are associated with a queue position of 0 and any priority level;

determining a highest queue position of the second number of queue entries;

determining a second maximum number of (the highest queue position+1) and the second number;

determining whether the second maximum number is less than the first queue position and none of the second number of queue entries is associated with a priority level greater than the first priority level and a queue position equal to the first queue position; and

if it is determined that the second maximum number is less than the first queue position and none of the second number of the plurality of entries is associated with a priority level greater than the first priority level and a queue position equal to the first queue position, determining the first queue position associated with a first queue entry as equal to the second maximum number.

10. A method according to claim 9, further comprising:

receiving a second request for a lock on the target data object, the second request associated with a long-term lock;

storing a second entry associated with the second request and the target data object in the queue;

determining that a queue position of the second request is 0;

setting a lock based on the second request based on the determination that a queue position of the second request is 0; and

in response to setting of the lock, deleting the second entry.

11. A method according to claim 10, further comprising:

receiving a third request for a lock on the target data object;

storing a third entry associated with the third request and the target data object in the queue;

determining that a queue position of the third request is 0;

receiving a request to set the lock based on the third request and based on the determination that a queue position of the third request is 0;

in response to the request to set the lock based on the third request, determining that the second long term lock of the second request is still being held and providing an error message and deleting the third entry.

12. A non-transitory computer-readable medium storing program code which when executed by a processor cases a computer system to:

receive a plurality of lock requests arising from a plurality of applications, respectively, for exclusively accessing a target data object stored in a database;

determine queue positions for the plurality of lock requests based on respective priority levels of the plurality of lock requests and timing of the plurality of lock requests; and

store the plurality of lock requests as queue entries at the determined queue positions in the queue,

wherein the program code further causes the computer system to determine that a queued lock request has expired based on a predetermined expiration time, modify the queue via deletion of the queued lock request from within the queue, and transmit an error notification to an application associated with the deleted lock request indicating that access to the target data object failed.

13. A non-transitory computer-readable medium according to claim 12, wherein the determination comprises:

determination of a first number of queue entries which are associated with the target data object and either are associated with a priority level equal to or greater than the first priority level, or associated with a queue position of 0 and any priority level;

determination of a highest queue position of the first number of queue entries;

determination of a maximum number of (the highest queue position+1) and the first number; and

determination of a first queue position associated with a first queue entry as equal to the maximum number.

14. A non-transitory computer-readable medium according to claim 12, wherein the determination comprises:

determination of a second number of queue entries which are associated with the target data object, are associated with a priority level equal to or greater than a first priority level and a queue position of less than a first queue position, or are associated with a queue position of 0 and any priority level;

determination of a highest queue position of the second number of queue entries;

determination of a second maximum number of (the highest queue position+1) and the second number;

determination of whether the second maximum number is less than the first queue position and none of the second number of queue entries is associated with a priority level greater than the first priority level and a queue position equal to the first queue position; and

if it is determined that the second maximum number is less than the first queue position and none of the second number of the plurality of entries is associated with a priority level greater than the first priority level and a queue position equal to the first queue position, determine the first queue position associated with a first queue entry as equal to the second maximum number.

15. A non-transitory computer-readable medium according to claim 14, wherein the program code further causes the computer system to:

receive a second request for a lock on the target data object, the second request associated with a long-term lock;

store a second entry associated with the second request and the target data object in the queue;

determine that a queue position of the second request is 0;

set a lock based on the second request based on the determination that a queue position of the second request is 0; and

in response to setting of the lock, delete the second entry.

16. A non-transitory computer-readable medium according to claim 15, wherein the program code further causes the computer system to:

receive a third request for a lock on the target data object;

store a third entry associated with the third request and the target data object in the queue;

determine that a queue position of the third request is 0;

receive a request to set the lock based on the third request and based on the determination that a queue position of the third request is 0;

in response to the request to set the lock based on the third request, determine that the second long term lock of the second request is still being held and provide an error message and delete the third entry.