Systems and methods for managing concurrent access requests to a shared resource

• US 20070094431A1
• Filed: 10/21/2005
• Published: 04/26/2007
• Est. Priority Date: 10/21/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Fachan, Neal
• Granted Patent: US 7,346,720 B2
• Time in Patent Office: Days
• US Class Current: 710/200
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The systems and methods manage concurrent access requests to a shared resource. The systems and methods utilize an access management algorithm that permits multiple processes to concurrently obtain shared locks on the shared resource, but also limits access to only one process when an exclusive lock is granted. In doing so, the systems and methods avoid the problems of starvation and deadlock.

Claims

1. A method of managing concurrent access requests to a data segment, comprising:

tracking shared lock requests from a plurality of processes in a first data structure when no exclusive waiter is present, wherein the first data structure tracks the total number of shared locks;

tracking shared lock requests in a second data structure when an exclusive waiter is present and the total number of shared locks is greater than zero, wherein the second data structure tracks the number of shared locks held by each of the plurality of processes;

tracking recursive shared lock requests in the second data structure when an exclusive waiter is present and the total number of shared locks is zero;

granting an exclusive lock to the exclusive waiter when the total number of shared locks is zero and the number of shared locks held by each of the plurality of processes is zero.

2. A method of managing concurrent access requests to a shared resource, comprising:

receiving a first plurality of shared requests;

granting the first plurality of shared requests;

tracking completion of the first plurality of shared requests;

receiving an exclusive request;

receiving a second plurality of shared requests before the first plurality of shared requests has been completed;

granting the second plurality of shared requests;

tracking completion of the second plurality of shared requests on a per-process basis;

receiving a third plurality of shared requests after the first plurality of shared requests has been completed;

determining whether each of the third plurality of shared requests is a recursive request;

for each of the recursive requests,

granting the recursive request; and

tracking completion of the recursive request on a per-process basis; and

after completion of the third plurality of shared requests and the recursive requests, granting the exclusive request

3. A method of managing concurrent access requests to a shared resource, wherein a first at least one process has a shared lock on the shared resource, comprising:

storing a representation of the number of a second at least one processes waiting to obtain an exclusive lock on the shared resource in an exclusive waiting count, wherein the exclusive waiting count is a first data structure and the second at least one processes waiting to obtain an exclusive lock on the shared resource are put to sleep;

storing a representation of the number of first at least one processes that have a shared lock on the shared resource in a global count if the exclusive waiting count indicates that none of the second at least one processes are waiting to obtain an exclusive lock on the shared resource, wherein the global count is a second data structure;

adjusting a per-process count when one of the first at least one processes obtains a shared lock on the shared resource if the exclusive waiting count indicates that at least one of the second at least one processes is waiting to obtain an exclusive lock on the shared resource, wherein the per-process count is a third data structure that stores a representation of the number of shared locks held by each of the first at least one processes;

adjusting the per-process count when one of the first at least one processes terminates a shared lock on the shared resource if the exclusive waiting count indicates that at least one of the second at least one processes is waiting to obtain an exclusive lock on the shared resource and the global count indicates that at least one of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that the one of the first at least one processes does not hold a shared lock on the shared resource;

adjusting the global count when at least one of the first at least one processes terminates a shared lock on the shared resource if the exclusive waiting count indicates that at least one of the second at least one processes is waiting to obtain an exclusive lock on the shared resource and the global count indicates that at least one of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first at least one processes holds a shared lock on the shared resource; and

granting all shared lock requests from the first at least one processes if the global count indicates that at least one of the first at least one processes holds a shared lock on the shared resource.

4. The method of managing concurrent access requests to a shared resource of claim 3, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that at least one of the first at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that at least one of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further comprising:

putting to sleep all requests for a first-time lock by the first at least one processes;

granting all requests for a recursive lock by the first at least one processes;

adjusting the per-process count when at least one of the first at least one processes requests a recursive lock on the shared resource; and

adjusting the per-process count when at least one of the first at least one processes terminates a shared lock on the shared resource.

5. The method of managing concurrent access requests to a shared resource of claim 4, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that at least one of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further comprising:

putting to sleep all requests for a shared lock by the first at least one processes;

granting an exclusive lock to one of the second at least one processes waiting to obtain an exclusive lock on the shared resource; and

adjusting the exclusive waiting count.

6. The method of managing concurrent access requests to a shared resource of claim 3, wherein the third data structure is a hash table.

7. The method of managing concurrent access requests to a shared resource of claim 5, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first-at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that at least one of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further comprising:

granting an exclusive lock to each of the second at least one processes waiting to obtain an exclusive lock in turn until the exclusive waiting count indicates that none of the second at least one process is waiting to obtain an exclusive lock.

8. The method of managing concurrent access requests to a shared resource of claim 5, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first-at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that none of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further comprising:

granting a shared lock to at least one of the first at least one processes that are sleeping.

9. An access management system for managing concurrent access requests to a shared resource comprising:

a shared resource;

a processor module, wherein a first at least one process has a shared lock on the shared resource, configured to;

receive requests from the first at least one processes for a shared lock on the shared resource;

receive requests from a second at least one process for an exclusive lock on the shared resource;

store a representation of the number of a second at least one processes waiting to obtain an exclusive lock on the shared resource in an exclusive waiting count, wherein the exclusive waiting count is a first data structure and the second at least one processes waiting to obtain an exclusive lock on the shared resource are put to sleep;

store a representation of the number of the first at least one processes that have a shared lock on the shared resource in a global count if the exclusive waiting count indicates that none of the second at least one processes are waiting to obtain an exclusive lock on the share resource, wherein the global count is a second data structure;

adjust a per-process count when one of the first at least one processes obtains a shared lock on the shared resource if the exclusive waiting count indicates that at least one of the second at least on processes is waiting to obtain an exclusive lock on the shared resource, wherein the per-process count is a third data structure that stores a representation of the number of shared locks held by each of the first at least one processes;

adjust the per-process count when one of the first at least one processes terminates a shared lock on the shared resource if the exclusive waiting count indicates that at least one of the second at least one processes is waiting to obtain an exclusive lock on the shared resource and the global count indicates that at least one of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that one of the first at least one processes holds a shared lock on the shared resource;

adjust the global count when one of the first at least one processes terminates a shared lock on the shared resource if the exclusive waiting count indicates that at least one of the second at least one processes is waiting to obtain an exclusive lock on the shared resource and the global count indicates that at least one of the first at least processes holds a shared lock on the shared resource and the per-process count indicates that the one of the first at least one processes does not hold a shared lock on the shared resource; and

grant all shared lock requests from the first at least one processes if the global count indicates that at least one of the first at least one processes holds a shared lock on the shared resource.

10. The access management system of claim 9, further comprising:

the processor module, wherein the writers waiting counter indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that at least one of the first at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that at least one of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further configured to;

put to sleep all requests for a first-time lock by the first at least one processes;

grant all requests for a recursive lock by the first at least one processes;

adjust the per-process count when at least one of the first at least one processes requests a recursive lock on the shared resource; and

adjust the per-process count when at least one of the first at least one processes terminates a shared lock on the shared resource.

11. The access management system of claim 10, further comprising:

the processor module, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that at least one of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further configured to;

put to sleep all requests for a shared lock by the first at least one processes;

grant an exclusive lock to one of the second at least one processes waiting to obtain an exclusive lock on the shared resource; and

adjust the exclusive waiting count.

12. The access management system of claim 9, wherein the third data structure is a hash table.

13. The access management system of claim 11, further comprising:

the process module, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first-at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that at least one of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further configured to;

grant an exclusive lock to each of the second at least one processes waiting to obtain an exclusive lock in turn until the exclusive waiting count indicates that none of the second at least one process is waiting to obtain an exclusive lock.

14. The access management system of claim 11, further comprising:

the processor module, wherein the global count indicates that none of the first at least one processes holds a shared lock on the shared resource and the per-process count indicates that none of the first-at least one processes holds a shared lock on the shared resource and the exclusive waiting count indicates that none of the second at least one second processes is waiting to obtain an exclusive lock on the shared resource, further configured to;

grant a shared lock to at least one of the first at least one processes that are sleeping.

15. The access management system of claim 9, wherein the first and second at least one processes are received from a plurality of sources.

16. The access management system of claim 9, further comprising:

the shared resource, wherein the shared resource is located on a standalone computer; and

the processor module, wherein the processor module is located on the standalone computer.

17. The access management system of claim 9, wherein the shared resource is remotely located from the processor module.