Method and apparatus for managing access requests from a plurality of devices using dual level queue locking scheme and a doubly-linked circular queue

• US 6,321,308 B1
• Filed: 03/21/1997
• Issued: 11/20/2001
• Est. Priority Date: 03/21/1997
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Arnon, Dan, Ofek, Yuval
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): MCLEAN MAYO, KIMBERLY N
• Application Number:
  US08/822,971
• Time in Patent Office: 1,705 Days
• Field of Search: 711/147, 711/148, 711/149, 711/150, 711/151, 711/152, 710/39, 710/54, 710/52, 710/112
• US Class Current: 711/147
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method of managing a storage system which includes a local and remote systems is provided. Link services between the two subsystems are provided though the use of a task queue. The task queue resides in a global memory of the local storage system and receives requests from the various host controllers, device, and remote controllers connected to the local storage. The remote controllers of the local storage service the requests placed in the task queue to enable data transfer between the local and remote storage systems. The task queue may be a doubly linked list of records including forward and backward pointers in addition to the request data. A two level locking scheme is employed to prevent the addition of incompatible requests to the queue and to enable maximum parallelism in servicing requests in the queue. The first level of locking applies to the entire queue and is used when records are added to and deleted from the queue. The second level of locking applies to the individual queue records. Each queue record is locked when being serviced by an associated controller. Locked records and records corresponding to device requests having another locked record are ignored by the servicing controllers.

Claims

1. In a storage system having two types of controllers, requesting controllers and servicing controllers, the requesting controllers including a host controller and a disk controller, and the servicing controllers including a remote adapter, a request management system comprising:

a task queue accessible by each of said requesting and servicing controllers, said task queue including a plurality of records for storing requests from said requesting controllers;

a queue lock mechanism for preventing addition of records to and deletion of records from said task queue; and

a record lock mechanism for locking individual records and indicating that a request associated with a particular record in the queue is being serviced by one of the servicing controllers;

wherein a queue lock imposed on the task queue by the queue lock mechanism is recognized by a particular requesting controller only when the particular requesting controller is to perform a task queue record addition operation, the queue lock is recognized by a particular servicing controller only when the particular servicing controller is to perform a task queue record deletion operation, the requests stored in the records in the task queue include respective requests from a first controller and a second controller, the first and second controllers are comprised in the requesting controllers, the first controller is of a first type, the second controller is of a second type, and if the first type is different from the second type, the respective requests may be for execution by a same device, but if the first type matches the second type, the respective requests are for execution by different respective devices.

2. The request management system of claim 1 wherein each respective record of said task queue includes respective forward and backward pointers for storing a respective address of a next record and a previous record respectively relative to said respective record.

3. The request management system of claim 2 wherein said forward pointer of a last record in said task queue includes an address of a first record in said task queue and wherein said backward pointer of said first record included an address of said last record in said task queue.

7. The request management system of claim 1, wherein, if the controller of the first type and the controller of the second type are respective host controllers, the first type is considered to match the second type.

8. The request management system of claim 1, wherein, if the controller of the first type is the host controller and the controller of the second type is the disk controller, the first type is considered to be different from the second type.

9. The request management system of claim 1, wherein, if a first copy request to a track of a disk device is present in the task queue, then a second copy request to the track may not be added to the task queue while the first copy request is present in the task queue.

4. In a system having a plurality of requesting devices and a plurality of servicing devices where said servicing devices perform tasks requested by said requesting devices and wherein said tasks include accessing shared resources, the requesting devices including a host controller and a disk controller, and the servicing devices including a remote adapter, a method for managing multiple requests comprising the steps of:

providing a task queue accessible by said plurality of requesting devices and said plurality of servicing devices, said task queue including a plurality of records for storing requests from the requesting devices;

locking, by one of said plurality of requesting devices, said task queue, said locking step including preventing other ones of said plurality of requesting devices from accessing said task queue;

after said locking step, adding a record to said task queue, said record including information corresponding to a particular request to a shared resource by said one requesting device;

after said adding step, unlocking said task queue;

choosing, by one of said servicing devices, a record from said task queue;

locking by said servicing device, said chosen record;

performing a task defined by said chosen record; and

after said performing step, deleting said chosen record from said task queue;

wherein the locking of the task queue by the one of the plurality of requesting devices is recognized by a particular requesting device only when the particular requesting device is to perform a task queue record addition operation, the locking of the task queue by the one of the plurality of requesting devices is recognized by a particular servicing device only when the particular servicing device is to perform a task queue record deletion operation, the requests stored in the records in the task queue include respective requests from a first controller and a second controller, the first and second controllers are comprised in the requesting devices, the first controller is of a first type, the second controller is of a second type, and if the first type is different from the second type, the respective requests may be for execution by a same device, but if the first type matches the second type, the respective requests are for execution by different respective devices.

5. The method of claim 4 wherein said choosing step further includes the steps of:

resetting a counter;

determining a length associated with said task queue, said length being equal to the number of records in said task queue;

a) examining a record in said queue;

b) determining whether said record is valid;

c) if said record is not valid, incrementing said counter, and otherwise determining whether said record is in a locked state;

if said record is in a locked state, recording device information associated with said record, incrementing said counter and proceeding to step d, otherwise

determining whether said device information matches any recorded device information associated with locked records;

if said device information matches said recorded device information, incrementing said counter and proceeding to step d

otherwise choosing said record as being serviceable;

d) comparing said counter to said queue length;

e) if said counter is less than said queue length, repeating steps a through d.

6. The method as in claim 4 wherein said adding and said choosing steps occur simultaneously.

10. The method of claim 4, wherein, if the controller of the first type and the controller of the second type are respective host controllers, the first type is considered to match the second type.

11. The method claim 4, wherein, if the controller of the first type is the host controller and the controller of the second type is the disk controller, the first type is considered to be different from the second type.

12. The method of claim 4, wherein, if a first copy request to a track of a disk device is present in the task queue, then a second copy request to the track may not be added to the task queue while the first copy request is present in the task queue.