Composite lock for computer systems with multiple domains

• US 7,117,481 B1
• Filed: 11/06/2002
• Issued: 10/03/2006
• Est. Priority Date: 11/06/2002
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Agesen, Ole, Adams, Keith M.
• Primary Examiner(s): CHAVIS, JOHN Q
• Application Number:
  US10/289,728
• Time in Patent Office: 1,427 Days
• Field of Search: 717/120
• US Class Current: 717/120
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

In a multi-domain computer system in which several processes are running, a composite lock provides mutually exclusive access to a resource. The composite lock has a back-end component and a front-end component. The back-end component is platform-dependent and operates as a semaphore, with Wait and Signal functions. The front-end component conditionally calls the Wait and Signal functions depending on whether the lock is currently contested when a new process wishes to acquire the lock, and on whether any process is currently suspended, waiting to acquire the lock. The front-end and back-end components may execute in different domains. In the uncontested case, the invention avoids costly domain crossings. The front-end component may also include a spinning feature to further reduce the need to invoke the back-end component and cause a domain crossing. The composite lock is particularly advantageous in computer systems that include a virtual machine.

Claims

1. In a computer system that has a hardware platform, a software platform and a plurality of processes running in user-defined domains, a lock comprising:

A) a platform-dependent lock component that operates as a semaphore with a wait function and a signal function;

B) a front-end lock component comprising computer instructions

i) for acquiring the lock by performing a first operation on a variable, which indicates how many of the processes currently hold or wish to acquire the lock,

a) by atomically changing the variable by a first predetermined amount as part of the first operation; and

b) by calling the wait function of the platform-dependent lock component if the variable meets a first comparison condition relative to a predetermined first threshold value,

ii) for releasing the lock by performing a second operation on the variable

a) by atomically changing the variable by a second predetermined amount as part of the second operation; and

b) by calling the signal function of the platform-dependent lock component if the variable meets a second comparison condition relative to a predetermined second threshold value;

C) the processes calling the front-end lock component in order to acquire the lock regardless of the domain in which each process is currently executing;

D) the platform-dependent lock component and the front-end lock component being accessible from different domains;

E) only one of the processes at a time thereby being allowed to acquire the lock.

2. A lock as in claim 1, in which the first operation is fetch-and-increment.

3. A lock as in claim 1, in which the second operation is fetch-and-decrement.

4. A lock as in claim 1, in which the first operation is fetch-and-increment and the second operation is fetch-and-decrement.

5. A lock as in claim 1, in which the first comparison condition is that the variable indicates that at least one of the processes currently holds or wishes to acquire the lock.

6. A lock as in claim 1, in which the second comparison condition is that the variable indicates that at least one of the processes wishes to acquire the lock in addition to the process that currently holds the lock.

7. A lock as in claim 1, in which the front-end lock component comprises further computer instructions for testing, when a calling process requests the lock and for a finite number of iterations, whether any process currently holds the lock and,

if not, for giving the lock to the calling process and

if so, at the end of the finite number of iterations, for proceeding with atomically changing the variable and calling the wait function.

8. A lock as in claim 1, in which the lock is interposed between the processes and a resource for providing exclusive access to the resource to whichever process holds the lock.

9. In a computer system that has a hardware platform, a software platform, a resource and a plurality of user-defined domains, a lock for controlling access to the resource by a plurality of processes, the lock comprising:

A) a platform-dependent lock component that operates as a semaphore with a wait function and a signal function;

B) a front-end lock component comprising computer instructions

i) for acquiring the lock and granting access to the resource by performing a fetch-and-increment operation on a variable, which indicates how many of the processes currently hold or wish to acquire the lock,

a) by atomically changing the variable by a first predetermined amount as part of the first operation; and

b) by calling the wait function of the platform-dependent lock component if the variable meets a first comparison condition relative to a predetermined first threshold value,

ii) for releasing the lock by performing a fetch-and-decrement operation on the variable

a) by atomically changing the variable by a second predetermined amount as part of the second operation; and

b) by calling the signal function of the platform-dependent lock component if the variable meets a second comparison condition relative to a predetermined second threshold value;

C) the processes calling the front-end lock component in order to acquire the lock and access the resource regardless of the current domain in which each process is currently executing;

D) the platform-dependent lock component and the front-end lock component being accessible from different domains;

E) only one of the processes at a time thereby being allowed to hold the lock;

in which;

F) the first comparison condition is that the variable indicates that at least one of the processes currently holds or wishes to acquire the lock; and

G) the second comparison condition is that the variable indicates that at least one of the processes wishes to acquire the lock in addition to the process that currently holds the lock.

10. A computer system comprising:

a host hardware platform;

host software that includes a platform-provided lock component;

a virtual machine (VM);

a virtual machine monitor that forms a software interface between the VM and the host hardware platform;

a plurality of user-defined domains including a host domain and a VM domain;

a composite lock that has a front-end component that is accessible to processes running in both the host domain and the VM domain and that conditionally calls the platform-provided lock component in the case of contention for the composite lock.

11. A computer system as in claim 10, in which:

the platform-provided lock component operates as a semaphore with a wait function and a signal function;

the front-end lock component comprises computer instructions

i) for calling the wait function of the platform-provided lock component if a first condition is met;

ii) for calling the signal function of the platform-provided lock component if a second condition is met;

the processes call the front-end lock component to acquire the lock regardless of the current domain in which each process is currently executing;

only one of the processes at a time thereby being allowed to hold the lock.

12. A computer system as in claim 11, in which:

the first condition is that any of the processes currently holds the lock;

the second condition is that at least one of the processes has attempted to acquire the lock and is still currently waiting to acquire the lock;

in the absence of contention for the lock, calls into the platform-provided lock component and corresponding switching of domains thereby being avoided.

13. A computer system as in claim 12, in which the front-end lock component further comprises computer instructions

i) for acquiring the lock by performing a first operation on a variable, which indicates how many of the processes currently hold or wish to acquire the lock and access the resource,

a) by atomically changing the variable by a first predetermined amount as part of the first operation;

and

b) by calling the wait function of the platform-provided lock component if the variable meets a first condition relative to a predetermined first threshold value,

ii) for releasing the lock by performing a second operation on the variable

a) by atomically changing the variable by a second predetermined amount as part of the second operation; and

b) by calling the signal function of the platform-provided lock component if the variable meets a second condition relative to a predetermined second threshold value.

14. A computer system as in claim 13, in which the first operation is fetch-and-increment.

15. A computer system as in claim 13, in which the second operation is fetch-and-decrement.

16. A computer system as in claim 13, in which the first operation is fetch-and-increment and the second operation is fetch-and-decrement.

17. A computer system as in claim 13, in which the first condition is that the variable indicates that at least one of the processes currently holds or wishes to acquire the lock.

18. A computer system as in claim 13, in which the second condition is that the variable indicates that at least one of the processes wishes to acquire the lock in addition to the process that currently holds the lock and has access to the resource.

19. A computer system as in claim 13, in which the front-end lock component comprises further computer instructions for testing, when a calling process requests the lock and for a finite number of iterations, whether any process currently holds the lock and,

if not, for giving the lock to the calling process and

if so, at the end of the finite number of iterations, for proceeding with the steps of atomically changing the variable and calling the wait function.

20. A computer system as in claim 10, in which the lock is interposed between the processes and a resource for providing exclusive access to the resource to whichever process holds the lock.

21. In a computer system that has a hardware platform, a software platform and a plurality of user-defined domains, a method for controlling concurrently running processes comprising:

A) running as a semaphore a platform-dependent lock component with a wait function and a signal function;

B) running a front-end lock component to include the following sub-steps;

i) acquiring the lock by performing a first operation on a variable, which indicates how many of the processes currently hold or wish to acquire the lock,

a) by atomically changing the variable by a first predetermined amount as part of the first operation; and

b) by calling the wait function of the platform-dependent lock component if the variable meets a first comparison condition relative to a predetermined first threshold value,

ii) releasing the lock by performing a second operation on the variable

a) by atomically changing the variable by a second predetermined amount as part of the second operation; and

b) by calling the signal function of the platform-dependent lock component if the variable meets a second comparison condition relative to a predetermined second threshold value;

C) processes calling the front-end lock component in order to access the resource regardless of the current domain in which each process is currently executing;

D) the platform-dependent lock component and the front-end lock component being accessible from different domains;

E) thereby allowing only one of the processes at a time to acquire the lock.

22. A method as in claim 21, in which the first operation is fetch-and-increment.

23. A method as in claim 21, in which the second operation is fetch-and-decrement.

24. A method as in claim 21, in which the first operation is fetch-and-increment and the second operation is fetch-and-decrement.

25. A method as in claim 21, in which the first comparison condition is that the variable indicates that at least one of the processes currently holds or wishes to acquire the lock.

26. A method as in claim 21, in which the second comparison condition is that the variable indicates that at least one of the processes wishes to acquire the lock in addition to the process that currently holds the lock.

27. A method as in claim 21, further comprising, when a calling process requests the lock and for a finite number of iterations, testing, in the front-end lock component, whether any process currently holds the lock and, if not, giving the lock to the calling process and if so, at the end of the finite number of iterations, proceeding with the steps of atomically changing the variable and calling the wait function.

28. A method as in claim 21, further comprising interposing the lock between the processes and a resource for providing exclusive access to the resource to whichever process holds the lock.

29. In a computer system that has a hardware platform, a software platform and a plurality of user-defined domains, a method for controlling concurrently running processes comprising:

A) running as a semaphore a platform-dependent lock component with a wait function and a signal function;

B) running a front-end lock component to include the following sub-steps;

i) acquiring the lock by performing a fetch-and-increment operation on a variable, which indicates how many of the processes currently hold or wish to acquire the lock,

a) by atomically changing the variable by a first predetermined amount as part of the first operation; and

b) by calling the wait function of the platform-dependent lock component if the variable meets a first comparison condition relative to a predetermined first threshold value, in which the first comparison condition is that the variable indicates that at least one of the processes currently holds or wishes to acquire the lock;

ii) releasing the lock by performing a fetch-and-decrement operation on the variable

a) by atomically changing the variable by a second predetermined amount as part of the second operation; and

b) by calling the signal function of the platform-dependent lock component if the variable meets a second comparison condition relative to a predetermined second threshold value, in which the second comparison condition is that the variable indicates that at least one of the processes wishes to acquire the lock in addition to the process that currently holds the lock;

C) processes calling the front-end lock component in order to access the resource regardless of the current domain in which each process is currently executing;

D) the platform-dependent lock component and the front-end lock component being accessible from different domains;

E) thereby allowing only one of the processes at a time to acquire the lock.

30. In a computer system that has a host hardware platform, a host software platform, a virtual machine monitor running on the hardware platform, and a virtual machine (VM) running on the virtual machine monitor, a method for controlling concurrently running processes comprising:

defining a plurality of domains, including a host domain and a VM domain; and

running a composite lock that has a front-end component that is accessible to processes running in both the host domain and the VM domain and that conditionally calls a platform-provided lock component in the case of contention for the composite lock.

31. A method as in claim 30, further comprising:

running as a semaphore a platform-dependent lock component with a wait function and a signal function;

running a front-end lock component according to the following sub-steps;

i) calling the wait function of the platform-provided lock component if a first condition is met;

ii) calling the signal function of the platform-provided lock component if a second condition is met;

the processes calling the front-end lock component to acquire the lock regardless of the domain in which each process is currently executing;

thereby allowing only one of the processes at a time to acquire the lock.

32. A method as in claim 31, in which:

the first condition is that any of the processes currently holds the lock;

the second condition is that at least one of the processes has attempted to acquire the lock and is still currently waiting to acquire the lock;

in the absence of contention for the lock, calls into the platform-provided lock component and corresponding switching of domains thereby being avoided.

33. A method as in claim 32, further comprising, in the front-end lock component:

i) acquiring the lock by performing a first operation on a variable, which indicates how many of the processes currently hold or wish to acquire the lock and access the resource,

a) by atomically changing the variable by a first predetermined amount as part of the first operation; and

b) by calling the wait function of the platform-provided lock component if the variable meets a first condition relative to a predetermined first threshold value,

ii) releasing the lock by performing a second operation on the variable

a) by atomically changing the variable by a second predetermined amount as part of the second operation; and

b) by calling the signal function of the platform-provided lock component if the variable meets a second condition relative to a predetermined second threshold value.

34. A method as in claim 33, in which the first operation is fetch-and-increment.

35. A method as in claim 33, in which the second operation is fetch-and-decrement.

36. A method as in claim 33, in which the first operation is fetch-and-increment and the second operation is fetch-and-decrement.

37. A method as in claim 33, in which the first condition is that the variable indicates that at least one of the processes currently holds or wishes to acquire the lock.

38. A computer system as in claim 33, in which the second condition is that the variable indicates that at least one of the processes wishes to acquire the lock and in addition to the process that currently holds the lock and has access to the resource.

39. A method as in claim 30, further comprising, when a calling process requests the lock and for a finite number of iterations, testing, in the front-end lock component, whether any process currently holds the lock and,

if not, giving the lock to the calling process and

if so, at the end of the finite number of iterations, proceeding with the steps of atomically changing the variable and calling the wait function.

40. A method as in claim 30, further comprising interposing the lock between the processes and a resource for providing exclusive access to the resource to whichever process holds the lock.