System and method for synchronization for enforcing mutual exclusion among multiple negotiators

• US 7,149,853 B2
• Filed: 09/20/2002
• Issued: 12/12/2006
• Est. Priority Date: 09/21/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: PolyServe, Inc. (HP Inc.)
• Inventors: Krueger, Phillip E.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Thomas, Shane M.
• Application Number:
  US10/251,689
• Publication Number:
  US 20030065896A1
• Time in Patent Office: 1,544 Days
• Field of Search: 711/147, 711/150, 711/154, 711/155, 711/152, 711/158, 711/156, 711/163, 711/164, 711/168, 710200-244, 714/42, 714/51, 714/52, 707/8
• US Class Current: 711/150
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method are disclosed for providing a synchronization mechanism for access to shared information. According to an embodiment of the present invention, a lock with more than one part can be obtained or leased by writing to the first part, writing to the second part, reading the first part to determine whether the first part reads what was written to it, and obtaining the lock if what is read is the same as what was written.

Claims

1. A method of synchronizing access comprising:

providing a lock, wherein the lock includes a first part and a second part;

writing a first entry to the first part without determining that the second part is available, wherein the first entry includes an identifier associated with a first negotiator;

determining, subsequent to writing the first entry to the first part, that the second part is available;

writing a second entry to the second part based at least in part on the determination that the second part is available;

reading the first part;

determining whether the first entry is read from the first part; and

obtaining the lock if the first entry is read from the first part.

2. The method of claim 1, wherein writing a first entry to the first part occurs after determining that the first part is available.

3. The method of claim 1, wherein writing a second entry to the second part occurs after determining that the second part is available.

4. The method of claim 1, further comprising:

writing a time stamp;

waiting a predetermined amount of time; and

updating the time stamp.

5. The method of claim 1, further comprising:

writing a mark;

waiting a predetermined amount of time; and

updating the mark.

6. The method of claim 1, further comprising:

reading a time stamp;

determining whether the time stamp has changed within a predetermined amount of time; and

writing the first entry to the first part if the time stamp has not changed within the predetermined amount of time.

10. A method as recited in claim 1, further comprising:

waiting a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determining whether a second negotiator is attempting to obtain the lock; and

renewing the lock if it is determined that no negotiator is attempting to obtain the lock or if the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

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

waiting a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determining whether a second negotiator is attempting to obtain the lock; and

renewing the lock if it is determined that the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than is lower than a current priority associated with the lock owner.

12. A method as recited in claim 1, further comprising:

waiting a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock; and

renewing the lock by modifying at least a portion of data contained in the second part if more time is needed to continue accessing the data associated with the lock.

7. A system of synchronizing access comprising:

a shared storage including a lock, wherein the lock includes a first part and a second part; and

a plurality of negotiators, wherein at least one of the plurality of negotiators is configured to;

write a first entry to the first part without determining that the second part is available, wherein the first entry includes an identifier associated with a first negotiator;

determine, subsequent to writing the first entry to the first part, that the second part is available;

write a second entry to the second part based at least in part on the determination that the second part is available,

read the first part;

determine whether the first entry is read from the first part; and

obtain the lock if the first entry is read from the first part.

13. A system as recited in claim 7, wherein the at least one of the plurality of negotiators is further configured to:

wait is predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determine whether a second negotiator is attempting to obtain th lock; and

renew the lock if it is determined than no negotiator is attempting to obtain the lock or if the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

14. A system as recited in claim 7, wherein the at least one of the plurality of negotiators is further configured to:

wait a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determine whether a second negotiator is attempting to obtain the lock; and

renew the lock if it is determined that the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

15. A system as recited in claim 7, wherein the at least one of the plurality of negotiators is further configured to:

wait a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock; and

renew the lock by modifying at least a portion of data contained in the second part if more time is needed to continue accessing the data associated with the lock.

8. A system of synchronizing access comprising:

a processor configured to;

write a first entry to a first part of a lock without determining that a second part of the lock is available, wherein the first entry includes an identifier associated with a first negotiator;

determine, subsequent to writing the first entry to the first part, that the second part is available;

write a second entry to the second part based at least in part on the determination that the second part is available;

write a second entry to the second part of the lock;

read the first part;

determine whether the first entry is read from the first part; and

obtain the lock if the first entry is read from the first part;

a memory coupled to the processor, the memory being configured to provide the processor with instructions.

16. A system as recited in claim 8, wherein the processor is further configured to:

wait a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determine whether a second negotiator is attempting to obtain the lock; and

renew the lock if it is determined that no negotiator is attempting to obtain the lock or if the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

17. A system as recited in claim 8, wherein the processor is further configured to:

wait a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determine whether a second negotiator is attempting to obtain the lock; and

renew the lock if it is determined that the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

18. A system as recited in claim 8, wherein the processor is further configured to:

wait a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock; and

renew the lock by modifying at least a portion of data contained in the second part if more time is needed to continue accessing the data associated with the lock.

9. A computer program product for synchronizing access, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

providing a lock, wherein the lock includes a first part and a second part;

writing a first entry to the first part without determining that the second part is available, wherein the first entry includes an identifier associated with a first negotiator;

determining, subsequent to writing the first entry to the first part, that the second part is available;

writing a second entry to the second part based at least in part on the determination that the second part is available;

reading the first part;

determining whether the first entry is read from the first part; and

obtaining the lock if the first entry is read from the first part.

19. A computer program product as recited in claim 9, further computer instructions for:

waiting a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determining whether a second negotiator is attempting to obtain the lock; and

renewing the lock if it is determined that no negotiator is attempting to obtain the lock or if the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

20. A computer program product as recited in claim 9, further comprising computer instructions for:

waiting a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock;

determining whether a second negotiator is attempting to obtain the lock; and

renewing the lock if it is determined that the second negotiator attempting to obtain the lock has associated with it a first priority that is lower than a current priority associated with the lock owner.

21. A computer program product as recited in claim 9, further comprising computer instructions for:

waiting a predetermined amount of time, during which data associated with the lock can be accessed by a lock owner associated with the lock; and

renewing the lock by modifying at least a portion of data contained in the second part if more time is needed to continue accessing the data associated with the lock.