Browse Prior Art Database

Dynamic I/O Load Balance Task Dispatching Algorithms

IP.com Disclosure Number: IPCOM000084930D
Original Publication Date: 1976-Jan-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 4 page(s) / 28K

Publishing Venue

IBM

Related People

Chiu, WW: AUTHOR [+2]

Abstract

The present dispatching algorithm utilizes the information of (1) input/ output (I/O) queue sizes (including the one being serviced), (2) estimated task CPU service time between I/O's, (3) estimated task I/O service time for each I/O resource (an I/O resource could be an I/O channel or I/O device or both), and (4) task I/O branching probabilities. Its intent is to achieve increased overlap of resource utilization and system throughput by dynamically balancing the load on the I/O resources.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 4

Dynamic I/O Load Balance Task Dispatching Algorithms

The present dispatching algorithm utilizes the information of (1) input/ output (I/O) queue sizes (including the one being serviced), (2) estimated task CPU service time between I/O's, (3) estimated task I/O service time for each I/O resource (an I/O resource could be an I/O channel or I/O device or both), and (4) task I/O branching probabilities. Its intent is to achieve increased overlap of resource utilization and system throughput by dynamically balancing the load on the I/O resources.

For existing task dispatching algorithms with predictive mechanisms, such as those in the IBM operating systems, OS/MVT, OS/VSI and OS/VS2, only the predicted task service time between I/O's (shall now be called task compute time) is employed for task selection decision. The tasks subjected to the prediction process is sometimes known as the Automatic Priority Group. Although in OS/VS 2 it is a group of address spaces (which are pointers to tasks), the idea is the same.

Associated with each task in the group is a predicted value c, for its next task compute time. This predicted value is recomputed periodically based on some function of past behavior. These tasks are ordered by their values of c, the one with the smallest c is selected first. They are subdivided into two subgroups in VS 2 release 1 called I/O and CPU subgroups (in VS 2 release 2, there are many subgroups), those tasks with a c greater than some parameter value (an adjustable time interval) are placed in the CPU subgroup, see the figure.

Only tasks in the CPU subgroup are preempted, tasks in the I/O subgroup are not preempted by another task belonging to the I/O subgroup to reduce task switch overhead. The idea is to prevent tasks with large compute times from hogging the CPU while tasks with small compute times are waiting, thus, reducing average waiting time for the CPU. The task mix in main memory are sometimes chosen deliberately to balance the load on the I/O resources, such as the case of OS/VS2 release 2.

The overall resource utilization may very well be approximately balanced, however, with the dispatching algorithm just described, the overlap of I/O resource utilization is not maximized, thus, neither is the throughput. This is true since the task dispatching algorithm does not maintain the instantaneous balance of I/O loads, therefore, instances of uneven I/O loads may occur, i.e., some I/O resources are idling while others are heavily congested.

To ensure instantaneous I/O load balance (i.e., to maintain a maximum number of I/O resources busy) the criteria for task selection must not only be based on their predicted compute times, c, but also on the current I/O load conditions and the task I/O branching probabilities. The algorithm is such that the task dispatched, is the one that will most likely maximize I/O resource utilization overlap from this task selection time to the next task selection time.

Two alternate alg...