Establishing control of lock token for shared objects upon approval messages from all other processes

• US 6,041,383 A
• Filed: 07/22/1996
• Issued: 03/21/2000
• Est. Priority Date: 07/22/1996
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Crowley, Todd A., Jeffords, Jason, Dev, Roger
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US08/681,040
• Time in Patent Office: 1,338 Days
• Field of Search: 395/674, 395/726, 395/800.28, 395/200.59, 370/447, 710/200, 709/229
• US Class Current: 710/200
• CPC Class Codes: G06F 9/465 Distributed object oriented systems remote method invocation [RMI] G06F9/548
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A system and method for controlling access to a shared object among a plurality of interconnected processes. A lock token is associated with a shared object. In order for a process to access or modify the associated object, it must possess the lock token. Whenever a process establishes control of the lock token, it transmits a message to each other process indicating that the process controls the lock token. In some instances, in order for a process to establish control of the lock token, the process must receive approval from each other process. Further, when two or more processes request the lock token at the same time, neither process will gain control and each process will then wait for a random time period before again seeking control of the token.

Claims

1. A computer-implemented method of synchronizing a plurality of processes in a distributed system, the method comprising:

when a first process requires access to a shared object in an object-oriented programming environment, the first process establishing control of a transmittable lock token associated with the shared object and transmitting a message to each process of the plurality of processes indicating that the first process controls the lock token,

wherein the first process establishes control in response to receiving an object control approval message from each other process in the plurality of processes.

2. The method of claim 1, wherein establishing control further comprises:

requesting the lock token; and

when no other process is also requesting the lock token and when the lock token does not exist, the first process generating the lock token.

3. The method of claim 1, wherein establishing control includes:

requesting the lock token;

determining whether at least one other process is also requesting the lock token, and

when at least one other process is also requesting the lock token, generating a retry delay time period, and at an expiration of the retry delay time period, repeating the requesting and determining steps, and

when no other process is also requesting the lock token and when the lock token does not exist, the first process generating the lock token.

4. The method of claim 3, wherein the determining step includes:

granting access to another process requesting the lock token when the retry delay time period of the first process has not elapsed.

5. The method of claim 1, further comprising:

determining how many other processes are waiting for access to the shared object;

when only one other process is waiting for access to the shared object, defining the other process as a second process that needs access to the object and when the first process is done with the object, transmitting the lock token to the second process;

when more than one other process is waiting for access to the shared object, compiling a list of the other processes waiting for access to the object and determining which one of the other processes is to be the second process and when the first process is done with the object, transmitting the lock token and the list to the second process; and

when no other process is waiting for the lock token, storing the lock token local to the first process.

6. The method of claim 5, wherein the step of determining the second process from the list includes choosing, as the second process, a process different from the first process which is positioned downstream from the first process in the distributed system.

7. In a computer network system, a method of controlling access to a shared object in an object-oriented programing environment accessible by a plurality of processes running concurrently on the network, the method comprising:

associating a transmittable lock token with the shared object;

allowing a process to access the shared object only when the process controls the associated lock token; and

the process controlling the lock token transmitting a message to each process of the plurality of processes reporting that it controls the lock token,

wherein the process establishes control of the lock token in response to receiving an object control approval message from each other process of the plurality of processes.

8. The method of claim 7, further comprising:

the process possessing the lock token passing the same to a next process seeking access to the shared object.

9. A system comprising:

a network interconnecting a plurality of processors; and

each processor including;

means for establishing control of a transmittable lock token associated with a shared object in an object-oriented programming environment;

means for transmitting a message to each processor of the plurality of processors reporting that the respective processor has control of the lock token;

means for transmitting an object control approval message to each other processor of the plurality of processors; and

means for operating on the shared object only when the processor has established control of the associated lock token by receiving an object control approval message from each other processor.

10. The system of claim 9, wherein each processor further comprises means for transmitting and receiving the lock token.

11. The system of claim 10, wherein each processor further comprises means for determining a next processor to which the lock token is to be transmitted.

12. The system of claim 9, wherein each processor further comprises means for requesting the lock token.

13. A computer-implemented method of coordinating operations among a plurality of processes interconnected by a computer network, the method comprising:

(A) receiving a request for access to a first shared object in an object-oriented programming environment from a first process of the plurality of processes;

(B) determining whether at least one other process is requesting access to the first shared object at a same time as the first process;

(C) when no other process is requesting access to the first shared object, granting access to the first shared object to the first process when each process of the plurality of processes sends a message agreeing to grant access to the first process; and

(D) when the first process and at least one other process are requesting access to the shared object at the same time, delaying the first process from requesting access to the first object for a first delay time period and delaying the second process from requesting access to the first object for a second delay time period different from the first delay time period and repeating steps (A)-(C).

14. The method of claim 13, wherein step (C) comprises:

generating a first transmittable lock token associated with the first shared object; and

sending the first lock token to the first process to indicate that the first process has sole access to the first shared object.

15. The method of claim 13, wherein step (D) includes steps of:

determining the first and second delay time periods according to the formula;

space="preserve" listing-type="equation">delay=DF·

(R+C.sup.2)·

f(x)

where DF is a delay factor, R is a number of retries for the respective process of the plurality of processes, C is the total number of contending processes, and x is a random number from 0 to 1.

16. The method of claim 15, wherein ##EQU2##

17. The method of claim 14, further comprising steps of:

(E) receiving a request from a third process for access to the first shared object;

(F) determining when the first process has completed operating on the first shared object; and

(G) when the first process has completed operating on the first shared object, causing the first process to transfer the lock token to the third process giving sole access to the first object to the third process.