Method and apparatus for coordination of a shared object in a distributed system

• US 6,510,478 B1
• Filed: 10/31/2000
• Issued: 01/21/2003
• Est. Priority Date: 06/12/1997
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Aprisma Management Technologies Incorporated (Broadcom, Inc.)
• Inventors: Jeffords, Jason, Crowley, Todd, Sexton, Donald, Hazel, Thomas
• Primary Examiner(s): Etienne, Ario
• Application Number:
  US09/702,535
• Time in Patent Office: 812 Days
• Field of Search: 709/200, 709/201, 709/202, 709/210, 709/213, 709/216, 709/211, 710/200, 710/108, 710/220, 710/244, 710/240, 710/36, 710/39, 710/40, 710/112
• US Class Current: 710/200
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Method and apparatus for coordinating access to a shared object amongst a plurality of processes in a distributed system. One process is identified as a lock owner process controlling a lock associated with the shared object. When a process needs to access the shared object, it requests control of the lock from the lock owner process. When no other process controls the lock, the lock owner process grants control to the requesting process. When another process controls the lock, the lock owner process places the requesting process in a queue and waits for the lock to become available. All accesses to the shared object are processed through the lock owner processes thus assuring coordination and synchronization among the processes.

Claims

1. A method of controlling access to an object shared amongst a plurality of processes in a distributed system, the method comprising:

(a) receiving a first lock request for a lock associated with the shared object, the first lock request received from a first requesting process of the plurality of processes that requires control of the shared object;

(b) in response to the request, determining whether any of the plurality of processes has control of the lock, comprising sending, to each of the plurality of processes, a lock-control request inquiring if the process currently controls the lock associated with the shared object; and

(c) if it is determined that none of the plurality of processes has control of the lock, granting control of the lock to the first requesting process.

2. The method of claim 1, wherein the lock is owned by a lock owner process of the plurality of processes.

3. The method as recited in claim 2, further comprising:

in response to the lock owner process failing, choosing a new lock owner from amongst the remaining processes in the plurality of processes.

4. The method as recited in claim 2, wherein step (b) comprises:

determining whether the lock owner process is currently accessing the shared object associated with the lock.

5. The method as recited in claim 1, further comprising:

(d) granting control of the lock to the first requesting process; and

(e) in response to the first requesting process failing, releasing control of the lock from the first requesting process.

6. The method as recited in claim 1, further comprising:

(d) granting control of the lock to the first requesting process;

(e) receiving a lock release message from the first requesting process indicating that the first requesting process no longer requires access to the shared object; and

(f) releasing control of the lock from the first requesting process.

7. The method as recited in claim 6, further comprising:

(g) prior to receiving the lock release message, receiving a second lock request from a second requesting process;

(h) placing the second requesting process in a queue;

(i) in response to receiving the lock release message, accessing the queue to determine the next requesting process in the queue; and

(j) granting control of the lock to the next requesting process.

8. The method as recited in claim 7, wherein the queue operates on a first-in, first-out basis.

9. The method as recited in claim 7, wherein the queue is a priority queue in that the next requesting process is that requesting process having a priority higher than any other requesting process in the queue.

10. The method as recited in claim 6, further comprising:

(g) in response to receiving the lock release message, determining whether there are any processes in a queue of processes requesting control of the lock.

11. The method as recited in claim 1, further comprising:

(d) prior to performance of (b), placing the first requesting process in a queue of processes waiting to receive control of the lock.

12. The method as recited in claim 11, further comprising:

(e) placing the first requesting process in the queue according to a priority level assigned to each requesting process,

wherein a second requesting process in the queue with a priority level higher than a priority level of a third requesting process in the queue will be granted control of the lock before the third requesting process.

13. The method as recited in claim 12, wherein the first requesting process is one of either the second requesting process or the third requesting process.

14. The method as recited in claim 11, further comprising:

(e) granting control to the first requesting process;

(f) receiving a lock release message from the first requesting process;

(g) retrieving a next requesting process from the queue; and

(h) granting control of the lock to the retrieved process.

15. The method as recited in claim 1, wherein step (b) further comprises:

in response to receiving a negative response to the lock-control request from each of the plurality of processes, granting control of the lock to the first requesting process.

16. The method as recited in claim 15, wherein step (b) further comprises:

in response to receiving a positive response to the lock-control request from one of the plurality of processes, denying the control of the lock to the first requesting process.

17. The method of claim 1, wherein the method is implemented on a computer.

18. A system of controlling access to an object shared amongst a plurality of processes in a distributed system, the system comprising:

means for receiving a first lock request for a lock associated with the shared object, the first lock request received from a first requesting process of the plurality of processes that requires control of the shared object;

means for determining, in response to the request, whether any of the plurality of processes has control of the lock, comprising means for sending, to each of the plurality of processes, a lock-control request inquiring if the process currently controls the lock associated with the shared object; and

means for granting control of the lock to the first requesting process if it is determined that none of the plurality of processes has control of the lock.

19. The system of claim 18, wherein the lock is owned by a lock owner process of the plurality of processes.

20. The system as recited in claim 19, further comprising:

means for choosing, in response to the lock owner process failing, a new lock owner from amongst the remaining processes in the plurality of processes.

21. The system as recited in claim 19, wherein the means for determining further comprises:

means for determining whether the lock owner process is currently accessing the shared object associated with the lock.

22. The system as recited in claims 18, further comprising:

means for granting control of the lock to the first requesting process; and

means for releasing, in response to the first requesting process failing, control of the lock from the first requesting process.

28. The system as recited in claim 18, further comprising:

means for placing the first requesting process in a queue of processes waiting to receive control of the lock prior to determining whether any of the plurality of processes has control of the lock.

29. The system as recited in claim 28, further comprising:

means for placing the first requesting process in the queue according to a priority level assigned to each requesting process,

wherein a second requesting process in the queue with a priority level higher than a priority level of a third requesting process in the queue will be granted control of the lock before the third requesting process.

31. The system as recited in claim 28, further comprising:

means for granting control to the first requesting process;

means for receiving a lock release message from the first requesting process;

means for retrieving a next requesting process from the queue; and

means for granting control of the lock to the retrieved process.

32. The system as recited in claim 18, wherein the means for determining further comprises:

means for granting control of the lock to the first requesting process in response to receiving a negative response to the lock-control request from each of the plurality of processes.

33. The system as recited in claim 18, wherein the means for determining further comprises:

means for denying the control of the lock to the first requesting process in response to receiving a positive response to the lock-control request from one of the plurality of processes.

34. A computer program product, comprising:

a computer-readable medium; and

computer-readable signals stored on the computer-readable medium that define instructions that, as a result of being executed by a computer, instruct the computer to perform a process of controlling access to an object shared amongst a plurality of processes in a distributed system, the process comprising;

(a) receiving a first lock request for a lock associated with the shared object, the first lock request received from a first requesting process of the plurality of processes that requires control of the shared object;

(b) in response to the request, determining whether any of the plurality of processes has control of the lock, comprising sending, to each of the plurality of processes, a lock-control request inquiring if the process currently controls the lock associated with the shared object; and

(c) if it is determined that none of the plurality of processes has control of the lock, granting control of the lock to the first requesting process.

23. The system as recited in claim 35, further comprising:

means for granting control of the lock to the first requesting process;

means for receiving a lock release message from the first requesting process indicating that the first requesting process no longer requires access to the shared object; and

means for releasing control of the lock from the first requesting process.

24. The system as recited in claim 23, further comprising:

means for receiving a second lock request from a second requesting process prior to receiving the lock release message;

means for placing the second requesting process in a queue;

means for accessing the queue to determine the next requesting process in the queue in response to receiving the lock release message; and

means for granting control of the lock to the next requesting process.

25. The system as recited in claim 24, wherein the queue operates on a first-in, first-out basis.

26. The system as recited in claim 24, herein the queue is a priority queue in that the next requesting process is that requesting process having a priority higher than any other requesting process in the queue.

27. The system as recited in claim 23, further comprising:

means for determining whether there are any processes in a queue of processes requesting control of the lock, in response to receiving the lock release message.

30. The system as recited in claim 27, wherein the first requesting process is one of either the second requesting process or the third requesting process.

35. The computer program product of claim 34, wherein the lock is owned by a lock owner process of the plurality of processes.

36. The computer program product as recited in claim 35, wherein the process further comprises:

in response to the lock owner process failing, choosing a new lock owner from amongst the remaining processes in the plurality of processes.

38. The computer program product as recited in claim 34, wherein the process further comprises:

(d) granting control of the lock to the first requesting process; and

(e) in response to the first requesting processing failing, releasing control of the lock from the first requesting process.

39. The computer program product as recited in claim 34, wherein the process further comprises:

(d) granting control of the lock to the first requesting process;

(e) receiving a lock release message from the first requesting process indicating that the first requesting process no longer requires access to the shared object; and

(f) releasing control of the lock from the first requesting process.

40. The computer program product as recited in claim 39, wherein the process further comprises:

(g) prior to receiving the lock release message, receiving a second lock request from a second requesting process;

(h) placing the second requesting process in a queue;

(i) in response to receiving the lock release message, accessing the queue to determine the next requesting process in the queue; and

(J) granting control of the lock to the next requesting process.

41. The computer program product as recited in claim 40, wherein the queue operates on a first-in, first-out basis.

42. The computer program product as recited in claim 40, wherein the queue is a priority queue in that the next requesting process is that requesting process having a priority higher than any other requesting process in the queue.

43. The computer program product as recited in claim 39, herein the process further comprises:

(g) in response to receiving the lock release message, determining whether there are any processes in a queue of processes requesting control of the lock.

48. The computer program product as recited in claim 34, wherein step (b) further comprises:

in response to receiving a negative response to the lock-control request from each of the plurality of processes, granting control of the lock to the first requesting process.

49. The computer program product as recited in claim 48, wherein step (b) further comprises:

in response to receiving a positive response to the lock-control request from one of the plurality of processes, denying the control of the lock to the first requesting process.

37. The computer program product as recited in claim 52, wherein step (b) further comprises:

determining whether the lock owner process is currently accessing the shared object associated with the lock.

44. The computer program product as recited in claim 51, wherein the process further comprises:

(d) prior to performance of (b), placing the first requesting process in a queue of processes waiting to receive control of the lock.

45. The computer program product as recited in claim 44, wherein the process further comprises:

(e) placing the first requesting process in the queue according to a priority level assigned to each requesting process,

wherein a second requesting process in the queue with a priority level higher than a priority level of a third requesting process in the queue will be granted control of the lock before the third requesting process.

46. The computer program product as recited in claim 45, wherein the first requesting process is one of either the second requesting process or the third requesting process.

47. The computer program product as recited in claim 44, wherein the process further comprises:

(e) granting control to the first requesting process;

(f) receiving a lock release message from the first requesting process;

(g) retrieving a next requesting process from the queue; and

(h) granting control of the lock to the retrieved process.