Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
1999-11-12
2003-12-16
Follansbee, John (Department: 2126)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C710S005000, C710S007000, C711S112000, C711S114000
Reexamination Certificate
active
06665740
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to data storage systems, and in particular, to job scheduling for I/O requests directed to devices in data storage systems.
In typical data storage systems, a storage controller serves as an interface between external host computers and the physical storage devices of the data storage system, and thus controls all back-end (or device-side) operations. The back-end operations can include services for read misses, as well as write destaging, read prefetching, RAID, data copy and other types of background operations. The scheduling of these types of operations has a major effect on the performance of the data storage system as a whole.
In prior art data storage systems, the storage controller typically strives to provide the lowest response time possible for host-waiting type operations (e.g., read misses) at the expense of its background duties. Favoring the host requests in this manner tends to starve the background operations. Moreover, when there are no pending host requests, the storage controller schedules a background operation for a logical device and decisions regarding the logical device selection are made entirely at the logical level.
Such an approach can have a detrimental impact on daa storage system performance. For instance, the execution of pending background operations requests that have accumulated in significant number while higher priority host requests were serviced can create a bottleneck for back-end operations. Also, the scheduling of jobs at the logical level can result in an uneven workload distribution at the physical level. That is, some physical resources (e.g., buses, physical storage devices, etc.) may be over-utilized while other physical resources are under-utilized.
SUMMARY OF THE INVENTION
This invention relates to a job scheduler that considers the loading of physical resources in a data storage system in selecting a logical volume for new job generation.
In an aspect of the invention, scheduling I/O requests directed to logical volumes that are associated with physical resources of a data storage system includes determining a job workload for each of the physical resources, choosing at least one of the physical resources based on the job workload and selecting one of the logical volumes associated with the chosen at least one physical resource. Once a logical volume has been selected, an I/O request directed to the selected one of the logical volumes is selected.
Embodiments of the invention may include one or more of the following features.
The physical resources can include Direct Memory Access (DMA) paths or “pipes” having at least one I/O bus for accessing physical devices. The workload determination can include determining the number of pending jobs associated with each of the pipes. Choosing one of the physical resources can include selecting one of the pipes based on the determined number of pending jobs associated with the pipes. The chosen one of the pipes is associated with a lowest number of pending jobs. The chosen one of the pipes can also be associated with a lowest number of pending jobs not in excess of a predetermined maximum pipe threshold number. If at least two of the pipes have a lowest number of pending jobs, then choosing at least one of the physical resources can include determining which of the at least two of the pipes is idle and, if more than one of the at least two of the pipes is idle, selecting from more than one of the at least two of the pipes. Selecting from more than one of the at least two of the physical devices is performed in a round robin manner. If only one of the at least two of the pipes is idle, the idle one of the at least two of the pipes is selected. Alternatively, if only one of the at least two of the pipes is idle, then the idle one of the at least two of the pipes is selected if the number of pending jobs is not in excess of the predetermined maximum pipe threshold number.
The physical resources can further include physical devices connected to the at least one I/O bus of each of the pipes. Choosing at least one physical resource can include determining the number of active jobs associated with each of the physical devices and selecting one of the physical devices based on the determined number of pending jobs associated with each of the physical devices. The selected one of the physical devices can be associated with a lowest number of pending jobs. Alternatively, the selected one of the physical devices can be associated with a lowest number of pending jobs not in excess of a predetermined maximum physical device threshold number. If at least two of the physical devices have a lowest number of pending jobs, then choosing the at least one of the physical resources can include selecting the one physical device having a next higher number of pending jobs than a most recently selected one of the physical devices. Alternatively, if at least two of the physical devices have a lowest number of pending jobs, choosing at least one of the physical resources includes selecting one of the physical devices having a next higher number of pending jobs than a most recently selected one of the physical devices not in excess of the predetermined maximum physical device threshold number.
Selecting one of the logical volumes can include determining a least recently selected one of those of the logical volumes associated with the selected one of the physical devices and selecting the least recently selected one.
The I/O scheduling can further include determining if any of the I/O requests are host I/O requests and, if any of the I/O requests are determined to be host I/O requests, deciding whether or not the host I/O requests are to be considered for scheduling. Deciding whether or not the host I/O requests are to be considered for scheduling can include using a parameter corresponding to the probability that the host I/O requests will be considered for scheduling if one or more of the I/O requests are not host I/O requests. One of any of the I/O requests determined to be host requests is selected if it is decided that the host I/O requests are to be considered for scheduling.
Among the advantages of the scheduling mechanism of the invention are the following. The scheduling mechanism provides the lowest response time possible for host requests while still performing its background duties in a timely manner. Additionally, because it uses a “bottom-up” approach to the selection of logical volumes, that is, it selects a pipe, then a physical device on that pipe, and then a logical volume on the selected physical device, overall system performance is much improved. Such an approach considers physical load balancing during the scheduling of background operations. Also, the total number of supported logical volumes is far greater than the number of physical resources, so considering the fewer physical resources for job scheduling purposes is more efficient.
REFERENCES:
patent: 4633387 (1986-12-01), Hartung et al.
patent: 5249290 (1993-09-01), Heizer
patent: 5381546 (1995-01-01), Servi et al.
patent: 5408663 (1995-04-01), Miller
patent: 5546535 (1996-08-01), Stallmo et al.
patent: 5819310 (1998-10-01), Vishlitzky et al.
patent: 5937428 (1999-08-01), Jantz
patent: 6112257 (2000-08-01), Mason, Jr. et al.
patent: 6145028 (2000-11-01), Shank et al.
patent: 6324580 (2001-11-01), Jindal et al.
patent: 6434637 (2002-08-01), D'Errico
Mason, Jr. Robert S.
Ofer Adi
Vishlitzky Natan
Cao Diem
Daly, Crowley & Mofford LLP
EMC Corporation
Follansbee John
LandOfFree
Logical volume selection in a probability-based job scheduler does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Logical volume selection in a probability-based job scheduler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logical volume selection in a probability-based job scheduler will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3135507