Computer-implemented systems for resource level locking without resource level locks

• US 9,213,586 B2
• Filed: 03/18/2009
• Issued: 12/15/2015
• Est. Priority Date: 03/18/2009
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Shorb, Charles Scott
• Primary Examiner(s): PETRANEK, JACOB ANDREW
• Application Number:
  US12/406,371
• Publication Number:
  US 20100242043A1
• Time in Patent Office: 2,463 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Computer-implemented systems and methods regulate access to a plurality of resources in a pool of resources without requiring individual locks associated with each resource. Access to one of the plurality of resources is requested, where a resource queue for managing threads waiting to access a resource is associated with each of the plurality of resources. A resource queue lock associated with the resource is acquired, where a resource queue lock is associated with multiple resources.

Claims

1. A computer-implemented method, comprising:

receiving multiple requests for access to a resource when the resource is being accessed, wherein each of the received requests is generated by a different requesting thread, and wherein a request for access includes a request for read, write or mutex access to the resource;

dynamically forming a resource queue which orders the multiple requesting threads using a linked list structure, wherein dynamically forming the resource queue includes temporarily locking the resource queue; and

providing requesting threads with synchronized access to the resource, wherein synchronized access is provided to the requesting threads ordered by the resource queue, wherein providing is performed using the linked list structure and without activating an operating system lock associated with the resource, and wherein providing synchronized access further includes;

providing simultaneous read access to multiple requesting threads, wherein providing simultaneous read access includes updating the resource queue by removing the multiple requesting threads to which read access is provided; and

providing exclusive access to the resource, wherein the exclusive access to the resource is provided to a thread that is associated with a received request for write access to the resource.

2. The method of claim 1, wherein synchronized access is access that is unaffected by resource contention.

3. The method of claim 1, wherein the multiple requests for access to the resource are received in a first receiving order, and wherein dynamically forming the resource queue includes forming, for each of the multiple requesting threads, a specific resource queue entry corresponding to the requesting thread, wherein the resource queue entries are stored in a queuing order determined based on the first receiving order, and wherein a first one of the resource queue entries includes:

a first pointer indicating the requesting thread to which the first resource queue entry corresponds; and

a second pointer indicating a second one of the resource queue entries which immediately precedes the first resource queue entry in the queuing order.

4. The method of claim 3, further comprising:

altering the second pointer so that the second pointer is a null pointer, wherein altering is done when access to the resource is given to a requesting thread associated with the immediately preceding one of the resource queue entries.

5. The method of claim 4, wherein the first resource queue entry further includes a third pointer indicating a third one of the resource queue entries which immediately follows the first resource queue entry in the queuing order.

6. The method of claim 1, wherein providing requesting threads with synchronized access includes preventing mutex access to a resource from being obtained by more than one requesting thread at a time.

7. The method of claim 1, wherein providing simultaneous read access to multiple requesting threads includes:

maintaining a counter that indicates a number of the requesting threads to which simultaneous read access is provided;

detecting when read access is relinquished by a thread to which simultaneous read access was provided; and

decrementing the counter in response to the detection.

8. The method of claim 1, wherein providing requesting threads with synchronized access to the resource includes performing a memory fence operation.

9. The method of claim 1, further comprising:

imposing global lock in response to receiving a first one of the requests for access to the resource, wherein the first request for access to the resource is associated with a first one of the requesting threads, wherein the resource is included in a resource data store, and wherein the global lock facilitates protected searching for the resource within the resource data store.

10. The method of claim 9, wherein the first requesting thread locates the resource while the global lock is active, and wherein the method further includes releasing the global lock in response to the first requesting thread locating the resource.

11. The method of claim 1, wherein dynamically forming a resource queue includes using a resource queue pointer to indicate whether the resource is active or inactive.

12. The method of claim 1, wherein a resource queue pointer is set to NULL when the resource is inactive.

13. The method of claim 12, further comprising:

subsequent to receiving the multiple requests for access to the resource, receiving a new request for access to the resource while the resource is not being accessed, wherein the new request is associated with a first requesting thread;

imposing a global lock which facilitates locating the resource;

determining that the first requesting thread has located the resource; and

imposing a temporary resource queue lock in response to determining that the resource has been located.

14. The method of claim 13, further comprising:

while the resource queue is locked, determining that the resource queue pointer is set to NULL;

providing access the first requesting thread with access to the resource in response to determining that the resource queue pointer is set to NULL;

modifying the resource queue pointer to indicate that the resource is active; and

releasing the global lock and the temporary resource queue lock.

15. The method of claim 12, wherein receiving multiple requests for access to a resource when the resource is being accessed includes:

receiving a first request for access when the resource is being accessed, wherein the first request for access is associated with a first requesting thread; and

subsequent to receiving the first request for access, receiving a second request for access when the resource is being accessed, wherein the second request for access is associated with a second requesting thread,

and wherein providing requesting threads with synchronized access to the resource includes;

examining the resource queue in response to receiving the first request for access, wherein examining the resource queue includes determining that the resource queue is empty; and

initializing a first thread queue record associated with the first requesting thread, wherein the thread queue record includes a pointer which points to the first requesting thread.

16. The method of claim 15, wherein providing requesting threads with synchronized access to the resource includes:

examining the resource queue in response to the receiving the second request for access, wherein examining the resource queue includes determining that the resource queue is occupied; and

initializing a second thread queue record associated with the second requesting thread, wherein the second thread queue record includes a pointer indicating the first thread queue record.

17. The method of claim 1, wherein providing requesting threads with synchronized access to the resource includes locking the linked list when one or more of the requesting threads is given access to the resource.

18. A system, comprising:

one or more processors;

one or more non-transitory computer-readable storage mediums containing instructions configured to cause the one or more processors to perform operations including;

receiving multiple requests for access to a resource when the resource is being accessed, wherein each of the received requests is generated by a different requesting thread, and wherein a request for access includes a request for read, write or mutex access to the resource;

dynamically forming a resource queue which orders the multiple requesting threads using a linked list structure, wherein dynamically forming the resource queue includes temporarily locking the resource queue; and

providing requesting threads with synchronized access to the resource, wherein synchronized access is provided to the requesting threads ordered by the resource queue, wherein providing is performed using the linked list structure and without activating an operating system lock associated with the resource, and wherein providing synchronized access further includes;

providing simultaneous read access to multiple requesting threads, wherein providing simultaneous read access includes updating the resource queue by removing the multiple requesting threads to which read access is provided; and

providing exclusive access to the resource, wherein the exclusive access to the resource is provided to a thread that is associated with a received request for write access to the resource.

19. The system of claim 18, wherein synchronized access is access that is unaffected by resource contention.

20. The system of claim 18, wherein receiving multiple requests for access to the resource includes receiving the multiple requests in a first receiving order, and wherein dynamically forming the resource queue includes forming, for each of the multiple requesting threads, a specific resource queue entry corresponding to the requesting thread, wherein the operations further include storing the resource queue entries in a queuing order determined based on the first receiving order, and wherein a first one of the resource queue entries includes:

a first pointer indicating the requesting thread to which the first resource queue entry corresponds; and

a second pointer indicating a second one of the resource queue entries which immediately precedes the first resource queue entry in the queuing order.

21. The system of claim 20, further comprising:

altering the second pointer so that the second pointer is a null pointer, wherein altering is performed when access to the resource is given to a requesting thread associated with the immediately preceding one of the resource queue entries.

22. The system of claim 21, wherein the first resource queue entry further includes a third pointer indicating a third one of the resource queue entries which immediately follows the first resource queue entry in the queuing order.

23. The system of claim 18, wherein providing requesting threads with synchronized access includes preventing mutex or write access to a resource from being obtained by more than one requesting thread at a time.

24. The system of claim 18, wherein providing simultaneous read access to multiple requesting threads includes:

maintaining a counter that indicates a number of the requesting threads to which simultaneous read access is provided;

detecting when read access is relinquished by a thread to which simultaneous read access was provided; and

decrementing the counter in response to the detection.

25. The system of claim 18, wherein providing requesting threads with synchronized access to the resource includes performing a memory fence operation.

26. The system of claim 18, wherein the operations further include:

imposing global lock in response to receiving a first one of the requests for access to the resource, wherein the first request for access to the resource is associated with a first one of the requesting threads, wherein the resource is included in a resource data store, and wherein the global lock facilitates protected searching for the resource within the resource data store.

27. The system of claim 26, wherein imposing the global lock is such that the first requesting thread locates the resource while the global lock is active, and wherein the operations further include releasing the global lock in response to the first requesting thread locating the resource.

28. The system of claim 27, wherein dynamically forming a resource queue includes using a resource queue pointer to indicate whether the resource is active or inactive.

29. The system of claim 28, wherein using a resource queue pointer to indicate whether the resource is active or inactive includes setting the resource queue pointer to NULL when the resource is inactive.

30. The system of claim 29, wherein the operations further include:

subsequent to receiving the multiple requests for access to the resource, receiving a new request for access to the resource while the resource is not being accessed, wherein the new request is associated with a first requesting thread;

imposing a global lock which facilitates locating the resource;

determining that the first requesting thread has located the resource; and

imposing a temporary resource queue lock in response to determining that the resource has been located.

31. The system of claim 30, wherein the operations further include:

while the resource queue is locked, determining that the resource queue pointer is set to NULL;

providing access the first requesting thread with access to the resource in response to determining that the resource queue pointer is set to NULL;

modifying the resource queue pointer to indicate that the resource is active; and

releasing the global lock and the temporary resource queue lock.

32. The system of claim 29, wherein receiving multiple requests for access to a resource when the resource is being accessed includes:

receiving a first request for access when the resource is being accessed, wherein the first request for access is associated with a first requesting thread; and

subsequent to receiving the first request for access, receiving a second request for access when the resource is being accessed, wherein the second request for access is associated with a second requesting thread,

and wherein providing requesting threads with synchronized access to the resource further includes;

examining the resource queue in response to receiving the first request for access, wherein examining the resource queue includes determining that the resource queue is empty; and

initializing a first thread queue record associated with the first requesting thread, wherein the thread queue record includes a pointer which points to the first requesting thread.

33. The system of claim 32, wherein providing requesting threads with synchronized access to the resource includes:

examining the resource queue in response to receiving the second request for access, wherein examining the resource queue includes determining that the resource queue is occupied; and

initializing a second thread queue record associated with the second requesting thread, wherein the second thread queue record includes a pointer indicating the first thread queue record.

34. The system of claim 18, wherein providing requesting threads with synchronized access to the resource includes locking the linked list when one or more of the requesting threads is given access to the resource.

35. A computer-program product, tangibly embodied in a machine-readable non-transitory storage medium, including instructions configured to cause a data processing apparatus to perform operations including:

receiving multiple requests for access to a resource when the resource is being accessed, wherein each of the received requests is generated by a different requesting thread, and wherein a request for access includes a request for read, write or mutex access to the resource;

dynamically forming a resource queue which orders the multiple requesting threads using a linked list structure, wherein dynamically forming the resource queue includes temporarily locking the resource queue; and

providing requesting threads with synchronized access to the resource, wherein synchronized access is provided to the requesting threads ordered by the resource queue, wherein providing is performed using the linked list structure and without activating an operating system lock associated with the resource, and wherein providing synchronized access further includes;

providing simultaneous read access to multiple requesting threads, wherein providing simultaneous read access includes updating the resource queue by removing the multiple requesting threads to which read access is provided; and

providing exclusive access to the resource, wherein the exclusive access to the resource is provided to a thread that is associated with a received request for write access to the resource.

36. The computer-program product of claim 35, wherein synchronized access is access that is unaffected by resource contention.

37. The computer-program product of claim 35, wherein receiving multiple requests for access to the resource includes receiving the multiple requests in a first receiving order, and wherein dynamically forming the resource queue includes forming, for each of the multiple requesting threads, a specific resource queue entry corresponding to the requesting thread, wherein the operations further include storing the resource queue entries in a queuing order determined based on the first receiving order, and wherein a first one of the resource queue entries includes:

a first pointer indicating the requesting thread to which the first resource queue entry corresponds; and

a second pointer indicating a second one of the resource queue entries which immediately precedes the first resource queue entry in the queuing order.

38. The computer-program product of claim 37, wherein the operations further include:

altering the second pointer so that the second pointer is a null pointer, wherein altering is done when access to the resource is given to a requesting thread associated with the immediately preceding one of the resource queue entries.

39. The computer-program product of claim 38, wherein the first resource queue entry further includes a third pointer indicating a third one of the resource queue entries which immediately follows the first resource queue entry in the queuing order.

40. The computer-program product of claim 35, wherein providing requesting threads with synchronized access includes preventing mutex access to a resource from being obtained by more than one requesting thread at a time.

41. The computer-program product of claim 35, wherein providing simultaneous read access to multiple requesting threads includes:

maintaining a counter that indicates a number of the requesting threads to which simultaneous read access is provided;

detecting when read access is relinquished by a thread to which simultaneous read access was provided; and

decrementing the counter in response to the detection.

42. The computer-program product of claim 35, wherein providing requesting threads with synchronized access to the resource includes performing a memory fence operation.

43. The computer-program product of claim 35, wherein the operations further include:

imposing global lock in response to receiving a first one of the requests for access to the resource, wherein the first request for access to the resource is associated with a first one of the requesting threads, wherein the resource is included in a resource data store, and wherein the global lock facilitates protected searching for the resource within the resource data store.

44. The computer-program product of claim 43, wherein the first requesting thread locates the resource while the global lock is active, and wherein the operations further include releasing the global lock in response to the first requesting thread locating the resource.

45. The computer-program product of claim 35, wherein dynamically forming a resource queue includes using a resource queue pointer to indicate whether the resource is active or inactive.

46. The computer-program product of claim 45, wherein the operations further include:

setting the resource queue pointer to NULL when the resource is inactive.

47. The computer-program product of claim 46, wherein the operations further include:

subsequent to receiving the multiple requests for access to the resource, receiving a new request for access to the resource while the resource is not being accessed, wherein the new request is associated with a first requesting thread;

imposing a global lock which facilitates locating the resource;

determining that the first requesting thread has located the resource; and

imposing a temporary resource queue lock in response to determining that the resource has been located.

48. The computer-program product of claim 47, further comprising:

while the resource queue is locked, determining that the resource queue pointer is set to NULL;

providing access the first requesting thread with access to the resource in response to determining that the resource queue pointer is set to NULL;

modifying the resource queue pointer to indicate that the resource is active; and

releasing the global lock and the temporary resource queue lock.

49. The computer-program product of claim 46, wherein receiving multiple requests for access to a resource when the resource is being accessed includes:

receiving a first request for access when the resource is being accessed, wherein the first request for access is associated with a first requesting thread; and

subsequent to receiving the first request for access, receiving a second request for access when the resource is being accessed, wherein the second request for access is associated with a second requesting thread,

and wherein providing requesting threads with synchronized access to the resource includes;

examining the resource queue in response to receiving the first request for access, wherein examining the resource queue includes determining that the resource queue is empty; and

initializing a first thread queue record associated with the first requesting thread, wherein the thread queue record includes a pointer which points to the first requesting thread.

50. The computer-program product of claim 49, wherein providing requesting threads with synchronized access to the resource includes:

examining the resource queue in response to the receiving the second request for access, wherein examining the resource queue includes determining that the resource queue is occupied; and

initializing a second thread queue record associated with the second requesting thread, wherein the second thread queue record includes a pointer indicating the first thread queue record.

51. The computer-program product of claim 35, wherein providing requesting threads with synchronized access to the resource includes locking the linked list when one or more of the requesting threads is given access to the resource.