Adaptive delay of polling frequencies in a distributed system with a queued lock

• US 6,353,869 B1
• Filed: 05/14/1999
• Issued: 03/05/2002
• Est. Priority Date: 05/14/1999
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Ofer, Adi, Leneman, Tuvia, Vishlitzky, Natan
• Primary Examiner(s): THAI, XUAN MARIAN
• Application Number:
  US09/312,146
• Time in Patent Office: 1,026 Days
• Field of Search: 710/200, 710/220, 710/240, 710/241, 710/244, 711/100, 711/147, 711/150, 711/151, 711/154, 711/167, 711/169, 713/502
• US Class Current: 710/200
• CPC Class Codes: G06F 13/22 using successive scanning, e.g. polling G06F13/24 takes precedence

Abstract

A queued lock prioritizes access to a shared resource in a distributed system. Each unsuccessful requestor adaptively delays its next poll for the lock by a period determined as a function of its priority in the lock request queue and the average duration of a significant processor operation involving the resource.

Claims

1. In a computer system wherein

a plurality of processors contend for access to a shared resource through a queued lock including a lock request queue associated with said shared resource and implemented in a shared memory,

wherein said lock request queue identifies a successful requestor from among said processors as the current holder of the lock on said shared resource, and further indicates the priority of requests for subsequent locks on said shared resource by one or more unsuccessful requesters from among said processors,

a method of improving system performance wherein each unsuccessful requestor implements a lock polling delay procedure that periodically polls said lock request queue for information on both the status and the priority of said requestor'"'"'s pending lock request and adaptively determines said requestor'"'"'s polling period as a function of its priority in said lock request queue.

2. A system according to claim 1 wherein said lock polling delay procedure also determines said requestor'"'"'s polling period as a function of the average duration of a significant processor operation involving the shared resource.

3. A system according to claim 2 wherein said lock polling delay procedure records the duration of one or more of its periodic polls of said lock request queue, and wherein said average duration of a significant processor operation involving the shared resource is estimated as a function of one or more of the polling durations recorded by said polling delay procedure.

4. A method of improving performance in computer system systems including data storage wherein each of a plurality of controllers may obtain access to a shared data resource through at least one first common channel by invoking a lock allocation procedure implemented in each of said controllers and associated with said shared data resource to request a lock on the shared data resource,

and wherein a lock request queue implemented in a shared memory accessible over at least one second common channel to all of the controllers identifies a successful requestor from among said controllers as the current holder of the lock on said shared data resource, and further indicates the priority of requests for subsequent locks on said shared data resource by one or more unsuccessful requesters from among said controllers, said method comprising the steps of:

a) making by the controllers a plurality of requests for locks on the shared data resource;

b) obtaining a lock by a successful requester from among said controllers and identifying said successful requester as the current holder of the lock in the lock request queue;

c) storing by each unsuccessful requestor from among said controllers in the lock request queue in accordance with a predetermined priority algorithm, its request for a lock on the shared data resource;

d) polling, by an unsuccessful requester from among said controllers, the lock request queue;

e) determining, by said unsuccessful requester, whether it has become the current holder of the lock and, if not, the estimated number of prior entries in the lock request queue;

f) finding as a function of the estimated number of prior entries in the lock queue, by said unsuccessful requestor, the number of significant operations expected to be performed before said unsuccessful requester obtains the lock;

g) finding, by said unsuccessful requester, the average duration of a significant processor operation involving the shared resource,

h) calculating as the product of the previously found average duration of a significant processor operation involving the shared resource and the previously found number of significant operations expected to be performed, by said unsuccessful requester, the expected duration of the wait before said unsuccessful requestor obtains the lock; and

,

i) delaying, by said unsuccessful requester, for said expected duration of said wait before repeating its poll; and

j) repeating, by said unsuccessful processor, steps, d) through i) until it obtains the lock.

5. The method according to claim 4 further comprising the steps of:

a) during said polling step, polling said lock request queue through one or more of said first common communication channels;

b) recording, by said unsuccessful requestor, the duration of one or more of such polls; and

,

c) during said step of finding, by said unsuccessful requestor, the average duration of a significant processor operation involving the shared resource, estimating said average duration of a significant processor operation involving the shared resource as a function of one or more of said polling durations recorded by said unsuccessful requestor.

6. An intelligent data storage system comprising:

a shared data resource coupled to one or more first common communication channels;

a plurality of controllers coupled to said shared data resource through said first common communication channels;

a lock allocation procedure implemented in each of said controllers and associated with said shared data resource, for requesting a lock on the shared resource by each said controller and determining in accordance with a predetermined priority algorithm the priority of each said controller'"'"'s unsuccessful lock requests;

a lock request queue, responsive to said lock allocation procedures, implemented in a shared memory accessible over one or more second common communication channels to all of the controllers, said lock request queue identifying a successful requester from among said controllers as the current holder of the lock on said shared resource, and further indicating the priority of requests for subsequent locks on said shared resource by one or more unsuccessful requestors from among said controllers,

wherein each of said unsuccessful requesters implements in its lock allocation procedure a lock polling delay procedure that periodically polls said lock request queue for information on the status and priority of its pending lock request and adaptively determines said unsuccessful requestor'"'"'s polling period as a function of its priority in said lock request queue.

7. A system according to claim 6 wherein said function which determines said unsuccessful requestor'"'"'s polling period as a function of its priority in the lock request queue is the product of the number of significant processor operations expected to be performed before said unsuccessful requestor obtains the lock as a function of the number of prior entries in said lock request queue and the average duration of a significant processor operation involving the shared resource.

8. A system according to claim 7 wherein said first and second common communication channels are the same, wherein each of said unsuccessful requestors records during its lock polling delay procedure the duration of one or more of its periodic polls, and wherein said average duration of a significant processor operation involving the shared resource is estimated as a function of one or more of said polling durations recorded by said unsuccessful requestor.

9. In a computer system wherein a lock request queue implemented in shared memory indicates the priority of the unsuccessful requestors from among a plurality of processors for locks on a shared resource and wherein each of said unsuccessful requesters periodically polls said lock request queue, a method of improving system performance wherein each unsuccessful requestor estimates, upon each poll, the number of prior entries in said lock request queue and adaptively determines said requestor'"'"'s polling period as a function of said number of prior entries in said lock request queue.