Recoverable spin lock system

• US 5,991,845 A
• Filed: 10/21/1996
• Issued: 11/23/1999
• Est. Priority Date: 10/21/1996
• Status: Expired due to Term

• Current Assignee: Sound View Innovations, LLC (Sound View Innovation Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lieuwen, Daniel Francis, Silberschatz, Abraham, Bohannon, Philip Lewis
• Primary Examiner(s): Sheikh, Ayaz R.
• Assistant Examiner(s): Vo, Tim T.
• Application Number:
  US08/729,658
• Time in Patent Office: 1,128 Days
• Field of Search: 395/726, 395/727, 395/728, 395/729, 395/730, 395/731, 395/732, 395/674, 709/5, 709/225, 709/200, 710/220, 710/240, 710/241, 710/242, 710/244
• US Class Current: 710/200
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for recovering spin locks in a system having one or more processes capable of accessing a shared resource, the system providing a lock indicating exclusive access to the shared resource by a single process and enabling one or more processes to repeatedly attempt to gain access to the lock when ownership of the shared resource is desired. The method includes generating a linked list queue structure containing a first process currently having exclusive access to the lock and one or more processes added to the queue structure to spin on the lock, each process capable of modifying the queue structure by obtaining exclusive access of the lock from a process having exclusive access of the lock and releasing the lock to another process in the linked list queue structure; detecting when one or more processes having exclusive access to the lock terminates, and upon detection, removing the terminated process from the queue structure, and restoring consistency to said linked list queue structure.

Claims

1. A method for recovering spin locks in a system having one or more processes capable of accessing a shared resource, the system providing a lock indicating exclusive access of the shared resource by a single process and enabling one or more processes to repeatedly attempt to gain ownership of the lock when exclusive access to the shared resource is desired, said method for recovering spin locks comprising the steps of:

generating a queue structure including a process currently having exclusive access to the lock and adding processes that desire ownership of the lock to said queue structure;

setting a first status flag indicating a desire of one of said processes to be added to said queue structure;

setting a second status flag indicating that said one process is currently modifying the queue structure;

monitoring a third status flag indicating whether said queue structure is being restored and not attempting to modify said queue structure if said queue structure is being restored;

conducting a cleanup process if one or more of said processes indicated by said first status flag set have terminated, said cleanup process removing said one or more of said terminated processes from said queue structure, setting said third status flag to indicate that recovery of said queue structure is in process, and recovering said queue structure after all modification activity on said queue structure has finished; and

resetting said third status flag after completion of said cleanup process to indicate that said recovery process has completed.

2. The method for recovering spin locks as claimed in claim 1, further including the step of determining whether one or more of said terminated processes has exclusive access to said lock and assigning to a new process exclusive access to said lock for said queue structure after restoring consistency to said queue structure.

3. The method for recovering spin locks as claimed in claim 1, wherein for each new process desiring to have exclusive access to the lock, the step of checking if said third status flag has been set before attempting to be added to said queue structure and resetting that process'"'"'s associated first and second status flags if said third status flag has been set.

4. The method for recovering spin locks as claimed in claim 1, wherein the modifying step further includes the step of waiting for said queue structure to stabilize by allowing processes currently modifying the queue structure to complete their respective modifications, and resetting their respective second status flags after the queue structure has been modified.

5. The method for recovering spin locks as claimed in claim 1, wherein each said data structure associated with each process of said queue structure further includes a pointing mechanism for pointing to a next process in said queue structure that may obtain exclusive access to said lock, and a fourth status flag indicating whether the process has exclusive access of or waiting to have exclusive access to said lock.

6. The method for recovering spin locks as claimed in claim 1, wherein the conducting step further includes the step of determining the status of all said processes waiting to own the lock by assembling a set of processes having their respective first status flags set and determining the status of all said processes that are currently modifying the queue structure by assembling a subset of the processes having their respective second status flags set.

7. The method for recovering spin locks as claimed in claim 1, wherein the step of recovering said queue structure includes repairing any break in said queue structure caused by removing said one or more terminated processes from said queue structure.

8. The method for recovering spin locks as claimed in claim 1, wherein said observing with a cleanup process step further includes the steps of polling said processes of said processing system to determine if one or more said processes has terminated.

9. The method for recovering spin locks as claimed in claim 1, wherein for each said one or more processes, generating a signal to indicate when that process has terminated.

10. The method for recovering spin locks as claimed in claim 1, wherein the system employs atomically implemented hardware instructions, said method including implementing a swap hardware instruction.

11. The method for recovering spin locks as claimed in claim 7, wherein said step of repairing any break in the queue structure includes deallocating the data structures of the respective terminated one or more processes.

12. The method for recovering spin locks as claimed in claim 10, further including implementing a compare-and-swap hardware instruction.

13. A method for providing multiple processes with mutually exclusive access to a shared resource in a system having a lock associated with the shared resource, possession of the lock signifying exclusive access to the shared resource, wherein processes desiring access to the shared resource spin on the lock until the lock is acquired, the method comprising the steps of:

maintaining a linked queue structure of data records corresponding to a queue of processes including processes spinning on the lock and a process possessing the lock, one data record per process;

transferring the lock from the process possessing the lock to a process next in the queue;

conducting a cleanup process if one or more processes in the queue have terminated, said cleanup process removing said one or more terminated processes from the queue and reassembling the linked queue structure.

14. The method for providing multiple processes with mutually exclusive access to a shared resource according to claim 13, wherein each of said data records comprises:

a locked flag representing status of the lock for a process corresponding to the data record;

a next pointer pointing to a data record immediately next in the queue;

a wants pointer indicating whether a process corresponding to the data record is in the queue or requests to be added to the queue, all wants pointers of the data records providing an over-estimation of ownership of the lock; and

a volatile flag indicating that the process corresponding to the data record intends to modify the linked queue structure.

15. The method for providing multiple processes with mutually exclusive access to a shared resource according to claim 14, wherein

said step of maintaining a linked queue structure of data records further includes the steps of:

maintaining a tail pointer pointing to last data record in the linked queue structure;

maintaining a cleanup-in-progress flag indicating whether the cleanup process is being conducted.

16. The method for providing multiple processes with mutually exclusive access to a shared resource according to claim 15, wherein

said step of maintaining a linked queue structure of data records further includes the step of preventing initiation of the cleanup process while the linked queue structure is being modified by one or more of the multiple processes;

and

said step of conducting the cleanup process further comprises the steps of;

preventing the multiple processes from modifying the linked queue structure during the cleanup process;

releasing the lock from the process possessing the lock;

providing an indication that the lock has been released, so that the process possessing the lock does not transfer the lock;

transferring the lock to a new owner process, the new owner process being one of the processes spinning on the lock.

17. A method for providing multiple processes with mutually exclusive access to a shared resource in a system having a lock associated with the shared resource, possession of the lock signifying exclusive access to the shared resource, wherein processes desiring access to the shared resource spin on the lock until the lock is acquired, the method comprising the steps of:

step for maintaining a linked queue structure of data records corresponding to a queue of processes including processes spinning on the lock and a process possessing the lock, one data record per process spinning on the lock or possessing the lock;

step for acquiring the lock by a first of said multiple processes;

step for releasing the lock by the first of said multiple processes;

step for preventing the multiple processes from modifying the linked queue structure during the cleanup process;

step for conducting a cleanup process if one or more processes in the queue have terminated, the cleanup process including removing said one or more terminated processes from the queue and reassembling the linked queue structure;

step for preventing the multiple processes from modifying the linked queue structure during the cleanup process; and

step for preventing initiation of the cleanup process while the linked queue structure is being modified.