Lock leasing method for solving deadlock

• US 8,966,147 B2
• Filed: 08/22/2012
• Issued: 02/24/2015
• Est. Priority Date: 08/22/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Wang, Wenguang, Spillane, Richard Paul
• Primary Examiner(s): AUVE, GLENN ALLEN
• Application Number:
  US13/592,282
• Publication Number:
  US 20140059261A1
• Time in Patent Office: 916 Days
• Field of Search: 710/200, 718/100, 718/102, 718/104, 718/107, 718/108
• US Class Current: 710/200
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A method for resolving deadlock in a multi-threaded computing system using a novel lock lease is disclosed. A first thread leases a lock held by the first thread to a second thread different from the first thread. The leasing transfers control of the lock to the second thread while the first thread retains ownership of the lock. To lease the lock: (1) the second thread applies for the lease from the first thread; (2) the first thread grants the lease; (3) the first thread waits for the second thread to complete a task; (4) the second thread terminates the lease; (5) the first thread confirms termination of the lease. The first thread receives control of the lock back from the second thread after the second thread has finished using resources controlled by the lock. The second thread also can sublease the lock to a third thread.

Claims

1. A method for resolving deadlock in a multi-threaded computing system, the method comprising:

leasing, by a first thread, a lock held by the first thread to a second thread different from the first thread, wherein leasing the lock comprises transferring control of the lock to the second thread while the first thread retains ownership of the lock; and

receiving, by the first thread, the control of the lock back from the second thread after the second thread has finished using the lock.

2. The method of claim 1, further comprising:

applying for a lease on the lock by the second thread;

granting the lease on the lock by the first thread;

waiting for the second thread to complete a task by the first thread;

terminating the lease on the lock by the second thread; and

confirming termination of the lease on the lock by the first thread.

3. The method of claim 2, wherein the second thread belongs to a plurality of select threads given authorization to lease the lock.

4. The method of claim 3, wherein:

when two or more threads from the plurality of select threads attempt to lease the lock at the same time, the second thread is chosen based on one of the following queues;

a priority based scheduling queue, a round robin queue, a first in first out queue, and a shortest remaining time queue.

5. The method of claim 2, wherein only one thread is given authorization to lease the lock.

6. The method of claim 2, wherein confirming termination of the lease on the lock by the first thread is performed before terminating the lease on the lock by the second thread.

7. The method of claim 1, wherein the first thread and the second thread are used to interact with a hardware device.

8. The method of claim 7, wherein the second thread is used to synchronize cache.

9. The method of claim 1, wherein the method further comprises:

subleasing by the second thread, during a lease on the lock, the lock leased by the second thread to a third thread different from the first and second threads, wherein subleasing the lock transfers control of the lock to the third thread while the first thread retains ownership of the lock; and

receiving, by the second thread, the control of the lock back from the third thread after the third thread has finished using the lock.

10. The method of claim 1, wherein the method further comprises:

subleasing by the second thread, during a lease on the lock, the lock leased by the second thread to a third thread different from the first and second threads, wherein subleasing the lock transfers control of the lock to the third thread while the first thread retains ownership of the lock; and

receiving, by the first thread, the control of the lock directly back from the third thread after the third thread has finished using the lock without having the control of the lock pass through the second thread.

11. An electronic device for resolving deadlock in a multi-threaded computing system, the electronic device comprising:

a processor configured to;

lease, by a first thread, a lock held by the first thread to a second thread different from the first thread, wherein the lease enables the second thread to use one or more resources controlled by the lock while the first thread continues to own the lock; and

return the use of the one or more resources controlled by the lock back to the first thread after the second thread has finished using the one or more resources controlled by the lock.

12. The electronic device of claim 11, wherein the processor is further configured to:

apply for the lease on the lock by the second thread,

grant the lease on the lock by the first thread,

wait for the second thread to complete a task by the first thread,

terminate the lease on the lock by the second thread, and

confirm termination of the lease on the lock by the first thread.

13. The electronic device of claim 12, wherein the second thread belongs to a plurality of select threads given authorization to lease the lock.

14. The electronic device of claim 13, wherein:

when two or more threads from the plurality of select threads attempt to lease the lock at the same time, the second thread is chosen based on one of the following queues;

a priority based scheduling queue, a round robin queue, a first in first out queue, and a shortest remaining time queue.

15. The electronic device of claim 11, wherein the first thread and the second thread are used to interact with a hardware device.

16. The electronic device of claim 15, wherein the second thread is used to synchronize cache.

17. A non-transitory computer readable medium storing instructions that, when executed by a processor included in a computing device, cause the computing device to resolve deadlock in a multi-threaded computing system, by carrying out the steps that include:

leasing, by a first thread, a lock held by the first thread to a second thread different from the first thread,

wherein leasing the lock comprises transferring control of the lock to the second thread, while the first thread retains ownership of the lock and does not use one or more resources controlled by the lock during leasing the lock; and

receiving, by the first thread, the control of the lock back from the second thread after the second thread has finished using the one or more resources controlled by the lock.

18. The non-transitory computer readable medium of claim 17, wherein the steps further include:

applying for a lease on the lock by the second thread;

granting the lease on the lock by the first thread;

waiting for the second thread to complete a task by the first thread;

terminating the lease on the lock by the second thread; and

confirming termination of the lease on the lock by the first thread.

19. The non-transitory computer readable medium of claim 18, wherein the second thread belongs to a plurality of select threads given authorization to lease the lock.

20. The non-transitory computer of claim 19, wherein:

when two or more threads from the plurality of select threads attempt to lease the lock at the same time, the second thread is chosen based on one of the following queues;

a priority based scheduling queue, a round robin queue, a first in first out queue, and a shortest remaining time queue.

21. The non-transitory computer readable medium claim 17, wherein the first thread and the second thread are used to interact with a hardware device.

22. The non-transitory computer readable medium of claim 21, wherein the second thread is used to synchronize cache.