Method, system, program, and data structure for implementing a locking mechanism for a shared resource

• US 7,107,267 B2
• Filed: 01/31/2002
• Issued: 09/12/2006
• Est. Priority Date: 01/31/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Taylor, Julian S.
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Hicks, Michael J
• Application Number:
  US10/066,362
• Publication Number:
  US 20030145210A1
• Time in Patent Office: 1,685 Days
• Field of Search: 709/229, 709/100, 395/726, 707/8, 707/10, 707/202, 713/182
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Provided are a method, system, program, and data structure for implementing a locking mechanism to control access to a shared resource. A request is received to access the shared resource. A determination is made of whether a first file has a first name. The first file is renamed to a second name if the first file has the first name. A second file is updated to indicate the received request in a queue of requests to the shared resource if the first file is renamed to the second name. An ordering of the requests in the queue is used to determine whether access to the shared resource is granted to the request. The first file is renamed to the first name after the second file is updated.

Claims

1. A method for implementing a locking mechanism to control access to a shared resource, comprising:

receiving a request to access the shared resource;

determining whether a first file has a first name;

renaming the first file to a second name if the first file has the first name;

updating a second file to indicate the received request in a queue of requests to the shared resource if the first file is renamed to the second name, wherein an ordering of the requests in the queue is used to determine whether access to the shared resource is granted to the request;

reading and buffering a checksum from the second file before updating the second file; and

renaming the first file to the first name after the second file is updated.

2. The method of claim 1, wherein updating the second file further comprises:

copying the second file to a temporary file;

updating the temporary file to indicate the received request; and

if the buffered checksum and checksum in the second file match, then replacing the second file with the updated temporary file.

3. The method of claim 2, further comprising:

calculating a revised checksum from the updated temporary file; and

including the revised checksum in the updated temporary file before replacing the second file with the updated temporary file.

4. The method of claim 2, further comprising:

returning retry if the buffered checksum and checksum in the second file do not match,

wherein the second file is not replaced with the updated temporary file if there is no match.

5. The method of claim 1, wherein the check sum is maintained in both the first file and the second file and the updating the second file further comprises:

copying the second file to a temporary file, wherein the temporary file is updated to indicate the received request; and

if the buffered checksum and the checksum in both the first file and second file all match, then replacing the second file with the updated temporary file.

6. The method of claim 5, further comprising:

calculating a revised checksum from the updated temporary file;

including the revised checksum in the updated temporary file before replacing the second file with the temporary file; and

including the revised checksum in the first file before renaming the first file to the first name.

7. The method of claim 1, wherein a lease data structure indicates at least one request indicated in the queue in the second file granted access to the shared resource and, for each request granted access to the shared resource, a lease time during which the request is granted access to the shared resource, further comprising:

determining whether one request in the queue is permitted access to the shared resource based on the ordering of the requests in the queue;

updating the lease data structure to indicate the determined request and the lease time if the determined request is permitted access to the shared resource; and

returning a message to the determined request indicating that access to the shared resource is granted and the lease time during which access is granted.

8. The method of claim 7, wherein the request to access is for exclusive access to the shared resource, wherein determining whether one request in the queue is permitted access to the shared resource further comprises:

determining the request following the request at a top of the queue after determining that the lease time has expired;

removing the request at the top of the queue;

updating the queue to indicate the determined request at the top of the queue; and

updating the lease data structure to identify the determined request and set a new lease time for the determined request in the lease data structure during which the request has exclusive access to the shared resource.

9. The method of claim 8, wherein the queue and lease structure are updated after renaming the first file from the first name to the second name.

10. The method of claim 7, wherein the lease data structure comprises a file and wherein updating the lease data structure further comprises:

reading and buffering a checksum from the lease data structure;

copying the lease data structure to a temporary lease file, wherein the temporary lease file is updated to indicate the determined request and the new lease time; and

if the buffered checksum and checksum in the lease data structure match, then replacing the lease data structure with the temporary lease file.

11. The method of claim 7, wherein the request to access is for non-exclusive access to the shared resource and wherein the lease data structure indicates a number of requests allowed simultaneous access to the shared resource, wherein determining whether one considered request in the queue is permitted access to the shared resource further comprises:

determining whether a number of current readers is less than the allowed readers;

determining whether less than the number of current readers precedes the considered request in the queue;

updating the lease data structure to identify the considered request and set a new lease time for the considered request to have non-exclusive access to the shared resource if the number of current readers is less than the allowed readers and less than the number of current readers precedes the considered request in the queue; and

incrementing the number of current readers after updating the lease data structure to indicate the considered request.

12. The method of claim 11, further comprising:

removing one request for non-exclusive access from the queue whose lease time has expired;

removing indication from the lease data structure of the request removed from the queue; and

decrementing a field in the lease data structure indicating the number of current readers.

13. The method of claim 11, wherein the queue is capable of including entries for exclusive and non-exclusive access to the shared resource, and wherein the lease data structure is updated to indicate the considered request and set a new least time for the considered request to have non-exclusive access to the shared resource if there is no exclusive access request between a top of the queue and the considered request.

14. The method of claim 7, further comprising:

returning a retry message to the request indicating to retry the request to access the shared resource and the lease time if the request is determined not to be permitted access to the shared resource, wherein the request is retried after the lease time has expired.

15. The method of claim 1, further comprising:

receiving a request to remove an entry from the queue;

determining whether the first file has the first name;

renaming the first file to the second name if the first file has the first name;

updating the second file to indicate that the request is removed from the queue; and

renaming the first file to the first name after the second file is updated.

16. The method of claim 1, wherein the locking mechanism is capable of being executed on multiple operating system platforms, and wherein the steps of renaming and updating correspond to native operating system commands implemented across operating system platforms.

17. The method of claim 16, wherein the locking mechanism is implemented in a cross-platform computer programming language that is called by applications seeking to access the shared resource.

18. The method of claim 17, wherein the cross-platform computer programming language comprises Java.

19. The method of claim 1, wherein the shared resource comprises a data structure and wherein the access comprises one of read or write access to the shared data structure.

20. A system for implementing a locking mechanism to control access to a shared resource, comprising;

a file system;

a processor in communication with a first computer readable medium and file system;

code implemented in the first computer readable medium executed by the processor to cause the processor to perform;

(i) receiving a request to access the shared resource;

(ii) determining whether a first file in the file system has a first name;

(iii) renaming the first file to a second name if the first file has the first name;

(iv) updating a second file in the file system to indicate the received request in a queue of requests to the shared resource if the first file is renamed to the second name, wherein an ordering of the requests in the queue is used to determine whether access to the shared resource is granted to the request;

(v) reading and buffering a checksum from the second file the computer readable medium before updating the second file; and

(vi) renaming the first file to the first name after the second file is updated.

21. The system of claim 20, further comprising:

a computer readable medium,

wherein the code far updating the second file further causes the processor to perform;

(i) copying the second file to a temporary file;

(ii) updating the temporary file to indicate the received request; and

(iii) if the buffered checksum and checksum in the second file match, then replacing the second file with the updated temporary file.

22. The system of claim 20, further comprising:

a computer readable medium;

a lease data structure in the computer readable medium indicating at least one request indicated in the queue in the second file granted access to the shared resource and, for each request granted access to the shared resource, a lease time during which the request is granted access to the shared resource;

wherein the code further causes the processor to perform;

(i) determining whether one request in the queue is permitted access to the shared resource based on the ordering of the requests in the queue;

(ii) updating the lease data structure to indicate the determined request and the lease time if the determined request is permitted access to the shared resource; and

(iii) returning a message to the determined request indicating that access to the shared resource is granted and the lease time during which access is granted.

23. The system of claim 22, wherein the request to access is for exclusive access to the shared resource, wherein the code causing the processor to determine whether one request in the queue is permitted access to the shared resource further causes the processor to perform:

determining the request following the request at a top of the queue after determining that the lease time has expired;

removing the request at the top of the queue;

updating the queue to indicate the determined request at the top of the queue; and

updating the lease data structure to identify the determined request and set a new lease time for the determined request in the lease data structure during which the request has exclusive access to the shared resource.

24. The system of claim 22, wherein the request to access is for non-exclusive access to the shared resource and wherein the lease data structure indicates a number of requests allowed simultaneous access to the shared resource, wherein the code causing the processor to determine whether one considered request in the queue is permitted access to the shared resource further causes the processor to perform:

determining whether a number of current readers is less than the allowed readers;

determining whether less than the number of current readers precedes the considered request in the queue;

updating the lease data structure to identify the considered request and set a new lease time for the considered request to have non-exclusive access to the shared resource if the number of current readers is less than the allowed readers and less than the number of current readers precedes the considered request in the queue; and

incrementing the number of current readers after updating the lease data structure to indicate the considered request.

25. The system of claim 20, wherein the code further causes the processor to perform:

receiving a request to remove an entry from the queue;

determining whether the first file has the first name;

renaming the first file to the second name if the first file has the first name;

updating the second file to indicate that the request is removed from the queue; and

renaming the first file to the first name after the second file is updated.

26. The system of claim 20, wherein the locking mechanism is capable of being executed on multiple operating system platforms, and wherein the steps of renaming and updating correspond to native operating system commands implemented across operating system platforms.

27. The system of claim 20, wherein the shared resource comprises a data structure and wherein the access comprises one of read or write access to the shared data structure.

28. A system for implementing a locking mechanism to control access to a shared resource, comprising:

a file system implemented including a first file and a second file;

means for receiving a request to access the shared resource;

means for determining whether the first file has a first name;

means for renaming the first file to a second name if the first file has the first name;

means for updating the second file to indicate the received request in a queue of requests to the shared resource if the first file is renamed to the second name, wherein an ordering of the requests in the queue is used to determine whether access to the shared resource is granted to the request and wherein the means for updating the second file further performs reading and buffering a checksum from the second file in the computer readable medium before updating the second file; and

means renaming the first file to first name after the second file is updated.

29. The system of claim 28, further comprising:

a computer readable medium;

wherein the means for updating the second file further performs;

(i) copying the second file to a temporary file in the file system;

(ii) updating to temporary file to indicate the received request; and

(iii) if the buffered checksum and checksum in the second file match, then replacing the second file with the updated temporary file.

30. The system of claim 28 wherein the checksum is maintained in both the first file and the second file and the system;

further comprising;

a computer readable medium;

wherein the means for updating the second file further performs;

(i) copying the second file to a temporary file in the file system, wherein the temporary file is updated to indicate the received request; and

(ii) if the buffered checksum and the checksum in both the first file and second file all match, then replacing the second file with the updated temporary file.

31. The system of claim 28, further comprising:

a computer readable medium;

a lease data structure in the compute readable medium that indicates at least one request indicated in the queue in the second file granted access to the shared resource and, for each request granted access to the shared resource, a lease time during which the request is granted access to the shared resource;

means for determining whether one request in the queue is permitted access to the shared resource based on the ordering of the requests in the queue;

means for updating the lease data structure to indicate the determined request and the lease time if the determined request is permitted access to the shared resource; and

means for returning a message to the determined request indicating that access to the shared resource is granted and the lease time during which access is granted.

32. The system of claim 31, wherein the request to access is for exclusive access to the shared resource, wherein the means for determining whether one request in the queue is permitted access to the shared resource further performs:

determining the request following the request at a top of the queue after determining that the lease time has expired;

removing the request at the top of the queue;

updating the queue to indicate the determined request at the top of the queue; and

updating the lease data structure to identify the determined request and set a new lease time for the determined request in the lease data structure during which the request has exclusive access to the shared resource.

33. The system of claim 31, wherein the lease data structure comprises a file and wherein the means for updating the lease data structure further performs:

reading and buffering a checksum from the lease data structure;

copying the lease data structure to a temporary lease file, wherein the temporary lease file is updated to indicate the determined request and the new lease time; and

if the buffered checksum and checksum in the lease data structure match, then replacing the lease data structure with the temporary lease file.

34. The system of claim 31, wherein the request to access is for non-exclusive access to the shared resource and wherein the lease data structure indicates a number of requests allowed simultaneous access to the shared resource, wherein the means for determining whether one considered request in the queue is permitted access to the shared resource further performs:

determining whether a number of current readers is less than the allowed readers;

determining whether less than the number of current readers precedes the considered request in the queue;

updating the lease data structure to identify the considered request and set a new lease time for the considered request to have non-exclusive access to the shared resource if the number of current readers is less than the allowed readers and less than the number of current readers precedes the considered request in the queue; and

incrementing the number of current readers after updating the lease data structure to indicate the considered request.

35. The system of claim 31, further comprising:

means for returning a retry message to the request indicating to retry the request to access the shared resource and the lease time if the request is determined not to be permitted access to the shared resource, wherein the request is retried after the lease time has expired.

36. The system of claim 28, further comprising:

means for receiving a request to remove an entry from the queue;

means for determining whether the first file has the first name;

means for renaming the first file to the second name if the first file has the first name;

means for updating the second file to indicate that the request is removed from the queue; and

means for renaming the first file to the first name after the second file is updated.

37. The system of claim 28, wherein the locking mechanism is capable of being executed on multiple operating system platforms, and wherein the means for renaming and updating utilize native operating system commands implemented across operating system platforms.

38. The system of claim 37, wherein the locking mechanism is implemented in a cross-platform computer programming language that is called by applications seeking to access the shared resource.

39. The system of claim 28, wherein the shared resource comprises a data structure and wherein the access comprises one of read or write access to the shared data structure.

40. An article of manufacture including code for implementing a locking mechanism to control access to a shared resource, wherein the code causes operations to be performed comprising:

receiving a request to access the shared resource;

determining whether a first file has a first name;

renaming the first file to a second name if the first file has the first name;

updating a second file to indicate the received request in a queue of requests to the shared resource if the first file is renamed to the second name, wherein an ordering of the requests in the queue is used to determine whether access to the shared resource is granted to the request;

reading and buffering a checksum from the second file before updating the second file; and

renaming the first file to the first name after the second file is updated.

41. The article of manufacture of claim 40, wherein updating the second file further comprises:

copying the second file to a temporary file;

updating the temporary file to indicate the received request; and

if the buffered checksum and checksum in the second file match, then replacing the second file with the updated temporary file.

42. The article of manufacture of claim 41, further comprising:

calculating a revised checksum from the updated temporary file; and

including the revised checksum in the updated temporary file before replacing the second file with the updated temporary file.

43. The article of manufacture of claim 41, further comprising:

returning retry if the buffered checksum and checksum in the second file do not match, wherein the second file is not replaced with the updated temporary file if there is no match.

44. The article of manufacture of claim 40, wherein the checksum is maintained in both the first file and the second file and the updating the second file further comprises:

copying the second file to a temporary file, wherein the temporary file is updated to indicate the received request; and

if the buffered checksum and the checksum in both the first file and second file all match, then replacing the second file with the updated temporary file.

45. The article of manufacture of claim 44, further comprising:

calculating a revised checksum from the updated temporary file;

including the revised checksum in the updated temporary file before replacing the second file with the temporary file; and

including the revised checksum in the first file before renaming the first file to the first name.

46. The article of manufacture of claim 40, wherein a lease data structure indicates at least one request indicated in the queue in the second file granted access to the shared resource and, for each request granted access to the shared resource, a lease time during which the request is granted access to the shared resource, further comprising:

determining whether one request in the queue is permitted access to the shared resource based on the ordering of the requests in the queue;

updating the lease data structure to indicate the determined request and the lease time if the determined request is permitted access to the shared resource; and

returning a message to the determined request indicating that access to the shared resource is granted and the lease time during which access is granted.

47. The article of manufacture of claim 46, wherein the request to access is for exclusive access to the shared resource, wherein determining whether one request in the queue is permitted access to the shared resource further comprises:

determining the request following the request at a top of the queue after determining that the lease time has expired;

removing the request at the top of the queue;

updating the queue to indicate the determined request at the top of the queue; and

updating the lease data structure to identify the determined request and set a new lease time for the determined request in the lease data structure during which the request has exclusive access to the shared resource.

48. The article of manufacture of claim 47, wherein the queue and lease structure are updated after renaming the first file from the first name to the second name.

49. The article of manufacture of claim 46, wherein the lease data structure comprises a file and wherein updating the lease data structure further comprises:

reading and buffering a checksum from the lease data structure;

copying the lease data structure to a temporary lease file, wherein the temporary lease file is updated to indicate the determined request and the new lease time; and

if the buffered checksum and checksum in the lease data structure match, then replacing the lease data structure with the temporary lease file.

50. The article of manufacture of claim 46, wherein the request to access is for non-exclusive access to the shared resource and wherein the lease data structure indicates a number of requests allowed simultaneous access to the shared resource, wherein determining whether one considered request in the queue is permitted access to the shared resource further comprises:

determining whether a number of current readers is less than the allowed readers;

determining whether less than the number of current readers precedes the considered request in the queue;

updating the lease data structure to identify the considered request and set a new lease time for the considered request to have non-exclusive access to the shared resource if the number of current readers is less than the allowed readers and less than the number of current readers precedes the considered request in the queue; and

incrementing the number of current readers after updating the lease data structure to indicate the considered request.

51. The article of manufacture of claim 50, further comprising:

removing one request for non-exclusive access from the queue whose lease time has expired;

removing indication from the lease data structure of the request removed from the queue; and

decrementing a field in the lease data structure indicating the number of current readers.

52. The article of manufacture of claim 50, wherein the queue is capable of including entries for exclusive and non-exclusive access to the shared resource, and wherein the lease data structure is updated to indicate the considered request and set a new least time for the considered request to have non-exclusive access to the shared resource if there is no exclusive access request between a top of the queue and the considered request.

53. The article of manufacture of claim 46, further comprising:

returning a retry message to the request indicating to retry the request to access the shared resource and the lease time if the request is determined not to be permitted access to the shared resource, wherein the request is retried after the lease time has expired.

54. The article of manufacture of claim 40, further comprising:

receiving a request to remove an entry from the queue;

determining whether the first file has the first name;

renaming the first file to the second name if the first file has the first name;

updating the second file to indicate that the request is removed from the queue; and

renaming the first file to the first name after the second file is updated.

55. The article of manufacture of claim 40, wherein the locking mechanism is capable of being executed on multiple operating system platforms, and wherein the steps of renaming and updating correspond to native operating system commands implemented across operating system platforms.

56. The article of manufacture of claim 55, wherein the locking mechanism is implemented in a cross-platform computer programming language that is called by applications seeking to access the shared resource.

57. The article of manufacture of claim 56, wherein the cross-platform computer programming language comprises Java.

58. The article of manufacture of claim 40, wherein the shared resource comprises a data structure and wherein the access comprises one of read or write access to the shared data structure.

59. A computer readable medium including data structures for implementing a locking mechanism to control access to a shared resource, comprising:

a first file having one of a first name or a second name, wherein in response to receiving a request to access the shared resource, the first file is renamed to the second name if the first file has the first name;

a second file indicating a queue of requests to the shared resource, wherein an ordering of the requests in the queue is used to determine whether access to the shared resource is granted to the request, and wherein the second file is updated to indicate the received request in the queue when the first file is renamed to the second name, wherein the first file is renamed to the first name alter the second file is updated; and

a checksum field in the second file, wherein the checksum is buffered before updating the second file.

60. The computer readable medium of claim 59, further comprising:

a temporary file, wherein the second file is copied to the temporary file and the temporary file is updated to indicate the received request, wherein the second file is replaced with the updated temporary file if the buffered checksum and checksum in the second file match.

61. The computer readable medium of claim 59, further comprising:

a lease data structure indicating at least one request indicated in the queue in the second file granted access to the shared resource and, for each request granted access to the shared resource, a lease time during which the request is granted access to the shared resource, wherein determining whether one request in the queue is permitted access to the shared resource is based on the ordering of the requests in the queue, and wherein the lease data structure is updated to indicate the determined request and the lease time if the determined request is permitted access to the shared resource.

62. The computer readable medium of claim 61, wherein the lease data structure comprises a file, further comprising:

a checksum field within the lease data structure, wherein the checksum from the checksum field is buffered when updating the lease data structure; and

a temporary lease file, wherein updating the lease data structure involves copying the lease data structure to the temporary lease file, wherein the temporary lease file is updated to indicate the determined request following the request at the top of the queue and the new lease time, wherein if the buffered checksum and checksum in the lease data structure match, then the lease data structure is replaced with the temporary lease file.

63. The computer readable medium of claim 61, wherein the request to access is for non-exclusive access to the shared resource, further comprising:

a number of allowed readers allowed simultaneous access to the shared resource indicated in the lease data structure, wherein the lease data structure is updated to identify the considered request and set a new lease time for the considered request to have nonexclusive access to the shared resource if a number of current readers is less than the allowed readers and less than the number of current readers preceding the considered request in the queue, wherein the number of current readers is incremented after updating the lease data structure to indicate the considered request.