System controller with plurality of memory queues for prioritized scheduling of I/O requests from priority assigned clients

• US 6,157,963 A
• Filed: 03/24/1998
• Issued: 12/05/2000
• Est. Priority Date: 03/24/1998
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Delaney, William P., Fredin, Gerald J., Courtright, William V. II
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Cao, Chun
• Application Number:
  US09/047,251
• Time in Patent Office: 987 Days
• Field of Search: 710/5, 710/6, 710/40, 710/74, 710/23, 710/44, 395/495, 395/725, 395/115, 364/200
• US Class Current: 710/5
• CPC Class Codes: G06F 3/061 Improving I/O performance
• 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 system for globally prioritizing and scheduling I/O requests from a plurality of storage users or clients to one or more storage objects. The system comprises a storage controller configured to receive I/O requests from the client workstations and prioritize and schedule those I/O requests in accordance with a scheduling algorithm. Specifically, the storage controller receives I/O requests from the storage users and places the I/O requests in memory queues associated with the particular storage users. The storage controller then selects the I/O requests from the various memory queues based on the scheduling algorithm.

Claims

1. A storage controller configured to prioritize and schedule I/O requests from a plurality of clients to at least one storage object, comprising:

processing means for processing I/O requests from said plurality of clients in a prioritized order;

first interface means for sending and receiving data between said clients and said processing means; and

second interface means for sending and receiving data between said processing means and said at least one storage object;

said processing means being configured to receive I/O requests from said clients via said first interface means, prioritize and schedule said I/O requests based on a priority assigned to each of said clients, conduct an I/O operation with said at least one storage object via said second interface means for an I/O request from a client having a highest priority, communicate results from said I/O operation back to the client which initiated the I/O request processed by the I/O operation, and change the priority assigned to the client which initiated the I/O request processed by the I/O operation.

2. The storage controller as recited in claim 1 wherein said storage controller is a disk array controller.

3. The storage controller as recited in claim 1 wherein said storage controller is a file server.

4. The storage controller as recited in claim 1 wherein said processing means periodically changes said priority assigned to each one of said plurality of clients in accordance with a priority decay algorithm.

5. The storage controller as recited in claim 1 further comprising a third interface means for receiving priority value information.

6. A storage controller configured to prioritize and schedule I/O requests from one or more clients to a plurality of storage objects, comprising:

processing means for processing I/O requests from said one or more clients in a prioritized order;

first interface means for sending and receiving data between said one or more clients and said processing means; and

second interface means for sending and receiving data between said processing means and said plurality of storage object;

said processing means being configured to receive I/O requests from said one or more clients via said first interface means, prioritize and schedule said I/O requests based on a priority assigned to each of said storage objects, conduct an I/O operation with one or more of said storage objects via said second interface means for an I/O request directed to a storage object having a highest priority, communicate results from said I/O operation back to the client which initiated the I/O request processed by the I/O operation, and change the priority assigned to the one or more storage objects with which the I/O operation was conducted.

7. A storage controller configured to prioritize and schedule I/O requests from a plurality of clients to at least one storage object, comprising:

a memory having a plurality of memory queues;

processing means for processing I/O requests from said plurality of clients in a prioritized order;

first interface means for sending and receiving data between said clients and said processing means; and

second interface means for sending and receiving data between said processing means and said at least one storage object;

said processing means being configured to receive I/O requests from said clients via said first interface means, place each one of said I/O requests into one of said plurality of memory queues based on a priority of said I/O request, remove an I/O request having a selected priority from one of said plurality of memory queues, conduct an I/O operation with said at least one storage object via said second interface means for the removed I/O request, and communicate results from said I/O operation back to the client which initiated the I/O request.

8. The storage controller as recited in claim 7 wherein each one of said memory queues are assigned a priority, and at least one of said plurality of memory queues is configured to receive I/O requests from at least one of said plurality of clients, and wherein said processing means selects an I/O request from one of said plurality of memory queues based on the priority assigned to each of said plurality of memory queues.

9. The storage controller as recited in claim 10 wherein each of said plurality of clients is assigned a priority, and wherein said processing means places I/O requests from a client having a certain priority into a memory queue having a similar priority.

10. The storage controller as recited in claim 7 wherein each one of said memory queues are assigned a priority, and at least one of said plurality of memory queues is configured to receive I/O requests directed to said at least one storage object, and wherein said processing means selects an I/O request from one of said plurality of memory queues based on the priority assigned to each of said plurality of memory queues.

11. The storage controller as recited in claim 10 wherein each of said at least one storage objects is assigned a priority, and wherein said processing means places I/O requests directed to a storage object having a certain priority into a memory queue having a similar priority.

12. The storage controller as recited in claim 7 wherein each one of said plurality of clients is assigned a first priority, and each of said at least one storage objects is assigned a second priority, and wherein said processing means calculates an I/O priority for each of said I/O requests based on said first priority and said second priority and places each of said I/O requests into a memory queue having a similar priority.

13. A method for prioritizing and scheduling I/O requests from a plurality of clients to one or more storage objects, comprising the steps of:

receiving via a first communication interface I/O requests from said plurality of clients;

prioritizing and scheduling said I/O requests based on a priority assigned to each of said clients;

conducting an I/O operation with said one or more storage objects for an I/O request from a client having a highest priority;

communicating results from said I/O operation back to the client which initiated the I/O request processed by the I/O operation; and

changing the priority assigned to the client which initiated the I/O request processed by the I/O operation.

14. The method as recited in claim 13 further comprising the step of periodically changing said priority assigned to each one of said plurality of clients in accordance with a priority decay algorithm.

15. A system for scheduling I/O requests to at least one storage object from a plurality of clients, comprising:

a processor;

a client interface configured to facilitate communications between said plurality of clients and said processor;

a storage object interface configured to facilitate communications between said processor and said at least one storage object; and

a memory having a plurality of memory queues;

wherein one or more of said plurality of clients send I/O requests to said processor via said client interface, said processor receives said I/O requests and places each one of said I/O requests in one of said plurality of memory queues based on a priority of said I/O requests, and at an approprate time said processor removes an I/O request having a selected priority value from one of said plurality of memory queues and conducts an I/O operation with said at least one storage object.

16. The system as recited in claim 15 wherein said client interface comprises a SCSI interface.

17. The system as recited in claim 15 wherein said client interface is ATM, CDDI, Fibre Channel, FDDI, Ethernet, Server Net or Token Ring.

18. The system as recited in claim 15 wherein said storage object interface comprises a SCSI interface.

19. The system as recited in claim 15 wherein said storage object interface is ATM, CDDI, Fibre Channel, FDDI, Ethernet, Server Net or Token Ring.

20. The system as recited in claim 15 wherein each one of said plurality of memory queues are assigned a priority, and at least one of said plurality of memory queues are configured to receive I/O requests from at least one of said plurality of clients, and wherein said processor selects an I/O request from one of said plurality of memory queues based on the priority assigned to each of said plurality of memory queues.

21. The storage controller as recited in claim 20 wherein each of said plurality of clients is assigned a priority, and wherein said processing means places I/O requests from a client having a certain priority into a memory queue having a similar priority.

22. The system as recited in claim 20 wherein said processor changes said priority assigned to a memory queue after said processor conducts an I/O operation for an I/O request from said memory queue.

23. The system as recited in claim 20 wherein said processor periodically changes said priority assigned to each one of said plurality of memory queues in accordance with a priority decay algorithm.

24. The system as recited in claim 15 wherein each one of said plurality of memory queues are assigned a priority, and at least one of said plurality of memory queues are configured to receive I/O requests directed to storage objects, and wherein said processor selects an I/O request from one of said plurality of memory queues based on the priority assigned to each of said plurality of memory queues.

25. The storage controller as recited in claim 24 wherein each of said at least one storage objects is assigned a priority, and wherein said processing means places I/O requests directed to a storage object having a certain priority into a memory queue having a similar priority.

26. The system as recited in claim 15 wherein each one of said plurality of clients is assigned a first priority, and each of said at least one storage objects is assigned a second priority, and wherein said processor calculates an I/O priority for said I/O requests based on said first priority and said second priority and places each of said I/O requests into a memory queue having a similar priority.

27. The system as recited in claim 15 wherein said system is configured to schedule I/O requests directed to a disk array.

28. The system as recited in claim 15 wherein said system is configured to schedule I/O requests directed to a file server.

29. The system as recited in claim 15 further comprising a priority value interface configured for receiving priority values from an external source.