Method for mutual exclusion of locks in a remote-write globally ordered network of processors

• US 6,374,285 B1
• Filed: 05/15/1998
• Issued: 04/16/2002
• Est. Priority Date: 05/15/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Lamport, Leslie, Scales, Daniel J.
• Primary Examiner(s): COURTENAY III, ST JOHN
• Application Number:
  US09/079,540
• Time in Patent Office: 1,432 Days
• Field of Search: 710/200, 710/52, 710/108, 710/220, 710/240, 710/241, 710/242, 710/243, 710/244, 709/100-108
• US Class Current: 718/104
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The invention provides a method for acquiring a lock in a network of processors with globally ordered remote-writes. A process requesting a lock changes an associated ticket number from zero to one. Next, the process determines if every other process attempting to acquire the lock has a ticket number of zero. If true, the request for the lock is immediately granted. Otherwise, if false, the process changes its ticket number to a value greater than that of every other process, and the process waits until its ticket number is the lowest non-zero ticket number, in which case the lock is granted with mutual exclusion.

Claims

1. A method for acquiring a lock in a network of processors with globally ordered writes, the network of processors hosting a plurality of processes, each having a process identifier, the method comprising the steps of:

assigning an initial ticket number to a current process requesting a lock;

determining among the plurality of processes, other than the current process requesting the lock, a largest outstanding ticket number;

determining, based on the largest outstanding ticket number, whether there are other processes requesting the lock;

if there are no other processes requesting the lock, granting the lock to the current process; and

if there are other processes, each having a ticket number, requesting the lock;

obtaining, for the current process, a successor ticket number to the largest outstanding ticket number;

determining that the successor ticket number of the current process is less than the ticket number of any other process requesting the lock or, the process identifier of the current process is less than the process identifier of any other process having a ticket number equal to the successor ticket number; and

then granting the lock to the current process.

2. A method for acquiring a lock as recited in claim 1, wherein ticket numbers are integers and the initial ticket number is one.

3. A method for acquiring a lock as recited in claim 1, wherein the step of determining a largest outstanding ticket number includes:

setting the largest outstanding ticket number to zero; and

for each process other than the current process;

obtaining a ticket number for the other process; and

comparing the obtained ticket number of the other process against the largest outstanding ticket number and if the obtained ticket number of the other process is greater than the largest outstanding ticket number, updating the largest outstanding ticket number with the obtained ticket number.

4. A method for acquiring a lock as recited in claim 1, wherein the step of determining that the successor ticket number of the current process is less than the ticket number of any other process requesting the lock or, the process identifier of the current process is less than the process identifier of any other process having a ticket number equal to the successor ticket number includes, for each other process requesting the lock:

comparing the successor ticket number to the ticket number of the other process to determine which is the larger ticket number; and

if the ticket number of the other process is greater than the successor ticket number, waiting until the successor ticket number is less than or equal to the ticket number of the other process.

5. A method for acquiring a lock as recited in claim 4, further including, if the ticket number of the other process is equal to the successor ticket number, waiting until the processor identifier of the current process is less than the other process.

6. A method for acquiring a lock as recited in claim 1,

wherein the network provides for atomic modification of the ticket number;

and

wherein the steps of assigning and the step of obtaining a successor ticket number each include atomically changing the ticket number for the process requesting a lock.

7. A method for acquiring a lock as recited in claim 6, wherein the network provides for atomic modification of 32 bits and the ticket number is a 32 bit quantity.

8. A method for acquiring a lock as recited in claim 1,

wherein the network provides for atomic modification of a fixed unit of memory storage and the ticket number is an integer multiple of the fixed units of memory storage, including at least a least significant unit and a most significant unit;

and

wherein the steps of assigning and the step of obtaining a successor ticket number each include atomically changing each of the fixed units of the ticket number for the process requesting the lock in the order of least significant unit to most significant unit.

9. A method for acquiring a lock as recited in claim 8, wherein the steps of (i) determining among the plurality of processes, other than the current process requesting the lock, a largest outstanding ticket number, and (ii) determining that the successor ticket number of the current process is less than the ticket number of any other process requesting the lock or, the process identifier of the current process is less than the process identifier of any other process having a ticket number equal to the successor ticket number, each include reading each of the fixed units of a ticket number in the order of most significant unit to least significant unit.

10. A method for acquiring a lock as recited in claim 8, wherein the fixed unit of memory is a byte.

11. A method for acquiring a lock as recited in claim 8, wherein the least significant unit of the ticket number is non-zero.

12. A method for acquiring a lock as recited in claim 1, wherein ticket numbers range from zero to a predetermined maximum integer number.

13. A method for acquiring a lock as recited in claim 12, further including, prior to obtaining a successor ticket number, the steps of:

determining whether the largest outstanding ticket number is equal to or greater than the predetermined maximum ticket number; and

if the largest outstanding ticket number is equal to or greater than a predetermined maximum ticket number,

assigning a ticket number of zero to the current process,

waiting until all outstanding ticket numbers are less than the predetermined maximum ticket number, and

continuing at the step of assigning an initial ticket number to the current process.

14. A method for acquiring a lock as recited in claim 1,

wherein ticket numbers are integers;

and

wherein the successor ticket number is one more than the maximum outstanding ticket number.

15. A method for acquiring a lock as recited in claim 1,

wherein ticket numbers are maintained in a vector;

and

wherein each element corresponds to one of the processes and contains any outstanding ticket number for the process to which the element corresponds.

16. A method for acquiring a lock as recited in claim 1,

wherein the ticket number comprises multiple digits;

wherein the network provides atomic modification of one digit of the ticket number; and

wherein the successor ticket number is constrained to have a non-zero least significant digit.